lrparser

README

lrparser

This is a library for creating LR parsers. It's similar to attribute grammars in that you can equip every rule with a lambda function that represents the semantic counterpart of the syntactic rule (for example, it can generate the value of an expression, as illustrated in the example below).

Example:

gr := lrparser.NewGrammar(lrparser.MustBuildRules([]*lrparser.SynSem{
	{Syn: `Init -> Expr`, Sem: func(args []any) any { return args[0] }},
	{Syn: `Expr -> "expr" AddExpr`, Sem: func(args []any) any { return args[1] }},
	{Syn: `AddExpr -> AddExpr "+" MulExpr`, Sem: func(args []any) any { return args[0].(int) + args[2].(int) }},
	{Syn: `AddExpr -> AddExpr "-" MulExpr`, Sem: func(args []any) any { return args[0].(int) - args[2].(int) }},
	{Syn: `AddExpr -> MulExpr`, Sem: func(args []any) any { return args[0] }},
	{Syn: `MulExpr -> MulExpr "*" ConstExpr`, Sem: func(args []any) any { return args[0].(int) * args[2].(int) }},
	{Syn: `MulExpr -> MulExpr "/" ConstExpr`, Sem: func(args []any) any { return args[0].(int) / args[2].(int) }},
	{Syn: `MulExpr -> ConstExpr`, Sem: func(args []any) any { return args[0] }},
	{Syn: `ConstExpr -> integer`, Sem: func(args []any) any { return args[0] }},
}))

See cmd/example

Documentation

Overview

Package lrparser is an LR-parser.

Index

• func CoalesceSymbols(tokens []*textkit.Token, clusters []string) []*textkit.Token
• type Grammar
  • func NewGrammar(rules ...[]*Rule) *Grammar
  • func (gr *Grammar) BuildItems()
  • func (gr *Grammar) Parse(tokens []*textkit.Token) (any, error)
• type Item
  • func (it Item) Less(it2 Item) bool
• type Located
• type Operator
  • func (op Operator) Name() string
• type OperatorAssociativity
• type ParseError
  • func (err *ParseError) Error() string
• type Rule
  • func BuildListRules(root, leaf string, canBeEmpty bool, leftBracket, sep, rightBracket string, ...) []*Rule
  • func BuildOperatorRules(root, leaf string, ops []Operator, builder func(string, any, any) any) []*Rule
  • func BuildOptSeq(root string, head, tail []string, builder func([]any, []any) any) []*Rule
  • func BuildRule(def string, f func([]any) any) (*Rule, error)
  • func BuildRules(list []*SynSem) ([]*Rule, error)
  • func MustBuildRule(def string, f func([]any) any) *Rule
  • func MustBuildRules(list []*SynSem) []*Rule
  • func NewRule(lhs string, rhs []string, conv func([]any) any) *Rule
  • func (r *Rule) String() string
• type State
• type SynSem

Functions

func CoalesceSymbols

func CoalesceSymbols(tokens []*textkit.Token, clusters []string) []*textkit.Token

CoalesceSymbols joins symbols together.

Types

type Grammar

type Grammar struct {
	// The rules of the grammar.
	Rules             []*Rule
	ErrorOnNonlocated bool
	// contains filtered or unexported fields
}

Grammar is a formal grammar.

func NewGrammar

func NewGrammar(rules ...[]*Rule) *Grammar

NewGrammar returns a new grammar.

func (*Grammar) BuildItems

func (gr *Grammar) BuildItems()

BuildItems builds the items of the automaton.

func (*Grammar) Parse

func (gr *Grammar) Parse(tokens []*textkit.Token) (any, error)

Parse parses a list of tokens.

type Item

type Item struct {
	LHS    string
	RHS    list.List[string]
	DotPos int
}

Item is an item of the parser.

func (Item) Less

func (it Item) Less(it2 Item) bool

Less compares the two items.

type Located

type Located interface {
	Location() *textkit.Location
	SetLocation(*textkit.Location)
}

Located specifies methods for AST node location.

type Operator

type Operator struct {
	Associativity OperatorAssociativity
	Priority      int
	Symbols       []string
}

Operator ...

func (Operator) Name

func (op Operator) Name() string

Name returns the operator's name.

type OperatorAssociativity

type OperatorAssociativity int

OperatorAssociativity ...

const (
	LeftAssociative OperatorAssociativity = iota
	RightAssociative
	NonAssociative
)

constants for OperatorAssociativity

type ParseError

type ParseError struct {
	Message string
	Loc     *textkit.Location
}

ParseError is a parse error.

func (*ParseError) Error

func (err *ParseError) Error() string

type Rule

type Rule struct {
	LHS  string
	RHS  []string
	Conv func([]any) any
	// contains filtered or unexported fields
}

Rule is a context-free rule with a builder function.

func BuildListRules

func BuildListRules(root, leaf string, canBeEmpty bool, leftBracket, sep, rightBracket string, builder func([]any) any) []*Rule

BuildListRules builds list rules.

func BuildOperatorRules

func BuildOperatorRules(root, leaf string, ops []Operator, builder func(string, any, any) any) []*Rule

BuildOperatorRules builds operator rules.

func BuildOptSeq

func BuildOptSeq(root string, head, tail []string, builder func([]any, []any) any) []*Rule

BuildOptSeq builds an optional sequence.

func BuildRule

func BuildRule(def string, f func([]any) any) (*Rule, error)

BuildRule builds a grammar rule from a string.

func BuildRules

func BuildRules(list []*SynSem) ([]*Rule, error)

BuildRules creates rules from a slice of `SynSem`s.

func MustBuildRule

func MustBuildRule(def string, f func([]any) any) *Rule

MustBuildRule builds a grammar rule from a string. It panics on error.

func MustBuildRules

func MustBuildRules(list []*SynSem) []*Rule

MustBuildRules creates rules from a slice of `SynSem`s. It panics on error.

func NewRule

func NewRule(lhs string, rhs []string, conv func([]any) any) *Rule

NewRule creates a new rule.

func (*Rule) String

func (r *Rule) String() string

String returns a string representation of the rule.

type State

type State struct {
	Items list.List[Item]
}

State is a state of the parser.

type SynSem

type SynSem struct {
	Syn string
	Sem func([]any) any
}

SynSem is a syntactic rule with its semantic counterpart (a lambda function).