README
¶
A Universal Dynamic LL(*) Parser
written in and for the Go programming language.
romshark/llparser is a dynamic recursive-descent top-down parser which parses any given input stream by trying to recursively match the root rule. It's universal in that it supports any LL(*) grammar.
This library allows building parsers in Go with relatively good error messages and flexible, even dynamic LL(*) grammars which may mutate at runtime. It parses the input stream into a typed parse-tree and allows action hooks to be executed when a particular rule is matched.
Getting Started
Rules
A grammar always begins with a root rule. A rule is a non-terminal symbol. Non-terminals are nodes of the parse-tree that consist of other non-terminals or terminals while terminals are leaf-nodes. A rule consists of a Designation, a Pattern, a Kind and an Action:
mainRule := &llparser.Rule{
Designation: "name of the rule",
Kind: 100,
Pattern: llparser.TermExact{
Kind: 101,
Expectation: "string",
},
Action: func(f llparser..Fragment) error {
log.Print("the rule was successfuly matched!")
return nil
},
}
Designationdefines the optional logical name of the rule and is used for debugging and error reporting purposes.Kinddefines the type identifier of the rule. If this field isn't set then zero (untyped) is used by default.Patterndefines the expected pattern of the rule. This field is required.Actiondefines the optional callback which is executed when this rule is matched. The action callback may return an error which will make the parser stop and fail immediately.
Rules can be nested:
ruleTwo := &llparser.Rule{
Pattern: llparser.TermExact{
Kind: 101,
Expectation: "string",
},
}
ruleOne := &llparser.Rule{
Pattern: ruleTwo,
}
Rules can also recurse:
rule := &llparser.Rule{Kind: 1}
rule.Pattern = llparser.Sequence{
llparser.TermExact{Expectation: "="},
llparser.Optional{Pattern: rule}, // potential recursion
}
Terminals
Pattern: Term
Term expects a particular fragment kind to be lexed:
Pattern: llparser.Term(SomeKindConstant),
Pattern: TermExact
TermExact expects a particular sequence of characters to be lexed:
Pattern: llparser.TermExact{
Kind: SomeKindConstant,
Expectation: "some string",
},
Pattern: Checked
Checked expects the lexed fragment to pass an arbitrary user-defined validation function:
Pattern: llparser.Checked{
Designation: "some checked terminal",
Fn: func(str string) bool { return len(str) > 5 },
},
Combinators
Pattern: Optional
Optional tries to match a specific pattern but doesn't expect it to be matched:
Pattern: llparser.Optional{
Pattern: somePattern,
},
Pattern: Sequence
Sequence expects a specific sequence of patterns:
Pattern: llparser.Sequence{
somePattern,
llparser.Term(SomeKindConstant),
llparser.Optional{
Pattern: llparser.TermExact{
Kind: SomeKindConstant,
Expectation: "foo",
},
},
},
Pattern: ZeroOrMore
ZeroOrMore tries to match one or many instances of a specific pattern but doesn't expect it to be matched:
Pattern: llparser.ZeroOrMore{
Pattern: somePattern,
},
Pattern: OneOrMore
OneOrMore expects at least one or many instances of a specific pattern:
Pattern: llparser.OneOrMore{
Pattern: somePattern,
},
Pattern: Either
Either expects either of the given patterns selecting the first match:
Pattern: llparser.Either{
somePattern,
anotherPattern,
},
Lexer
The lexer is an abstract part of the parser which tokenizes the input stream:
type Lexer interface {
Read() (*Token, error)
ReadExact(
expectation string,
kind FragmentKind,
) (
token *Token,
matched bool,
err error,
)
Position() Cursor
Set(Cursor)
}
A default lexer implementation is available out-of-the-box but sometimes implementing your own parser makes more sense. Some examples for when a custom lexer might be useful:
- Sometimes you don't care how many white-spaces, tabs and line-breaks there are between the patterns you care about and thus it doesn't make any sense to make each individual space character a terminal leaf-node, instead the lexer would read a sequence of whitespaces, tabs and line-breaks as a single typed terminal node (in fact, this is the behavior of the default lexer implementation linked aboved, it will treat these kinds of sequences as
misc.FrSpace) reducing the complexity of the resulting parse-tree. - If you want to disallow certain kinds of runes in the source code you can make the custom lexer implementation return an
ErrUnexpectedTokenerror when approaching one.
The Parse-Tree
A parse-tree defines the serialized representation of the parsed input stream and consists of Fragment interfaces represented by the main fragment returned by llparser.Parse. A fragment is a typed chunk of the source code pointing to a start and end position in the source file, defining the kind of the chunk and referring to its child-fragments.
Documentation
¶
Index ¶
- func PrintFragment(fragment Fragment, out io.Writer, indent string) (bytesWritten int, err error)
- type Action
- type Checked
- type Construct
- type Cursor
- type Either
- type Err
- type ErrUnexpectedToken
- type Fragment
- type FragmentKind
- type Lexer
- type OneOrMore
- type Optional
- type Parser
- type Pattern
- type Rule
- type Scanner
- func (sc *Scanner) Append(pattern Pattern, fragment Fragment)
- func (sc *Scanner) Fragment(kind FragmentKind) Fragment
- func (sc *Scanner) New() *Scanner
- func (sc *Scanner) Read() (*Token, error)
- func (sc *Scanner) ReadExact(expectation string, kind FragmentKind) (*Token, bool, error)
- func (sc *Scanner) Set(cursor Cursor)
- func (sc *Scanner) TidyUp() int
- type Sequence
- type SourceFile
- type Term
- type TermExact
- type Token
- type ZeroOrMore
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Action ¶
Action represents a callback function that's called when a certain fragment is matched
type Checked ¶
Checked represents an arbitrary terminal token pattern matched by a function
func (Checked) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type Cursor ¶
type Cursor struct {
Index uint
Column uint
Line uint
File *SourceFile
}
Cursor represents a source-code location
func NewCursor ¶
func NewCursor(file *SourceFile) Cursor
NewCursor creates a new cursor location based on the given source file
type Either ¶
type Either []Pattern
Either represents either of the arbitrary patterns
func (Either) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type ErrUnexpectedToken ¶
ErrUnexpectedToken represents a parser error
func (*ErrUnexpectedToken) Error ¶
func (err *ErrUnexpectedToken) Error() string
type Fragment ¶
type Fragment interface {
Kind() FragmentKind
Begin() Cursor
End() Cursor
Src() string
Elements() []Fragment
}
Fragment represents an abstract fragment
type Lexer ¶
type Lexer interface {
Read() (*Token, error)
ReadExact(
expectation string,
kind FragmentKind,
) (
token *Token,
matched bool,
err error,
)
Position() Cursor
Set(Cursor)
}
Lexer defines the interface of an abstract lexer implementation
type OneOrMore ¶
type OneOrMore struct{ Pattern }
OneOrMore represents at least one arbitrary patterns
func (OneOrMore) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type Optional ¶
type Optional struct{ Pattern }
Optional represents an arbitrary optional pattern
func (Optional) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type Pattern ¶
type Pattern interface {
// Container returns true for container patterns
Container() bool
// TerminalPattern returns the terminal pattern for composite patterns
// and nil for non-terminal patterns
TerminalPattern() Pattern
// Desig returns the textual designation of the pattern
Desig() string
}
Pattern represents an abstract pattern
type Rule ¶
type Rule struct {
Designation string
Pattern Pattern
Kind FragmentKind
Action Action
}
Rule represents a grammatic rule
func (*Rule) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type Scanner ¶
Scanner represents a sequence-recording lexing source-code scanner
func (*Scanner) Fragment ¶
func (sc *Scanner) Fragment(kind FragmentKind) Fragment
Fragment returns a typed composite fragment
func (*Scanner) New ¶
New creates a new scanner succeeding the original one dropping its record history
func (*Scanner) Read ¶
Read advances the scanner by 1 token returning either the read fragment or an error if the lexer failed
func (*Scanner) ReadExact ¶
ReadExact advances the scanner by 1 exact token returning either the read fragment or nil if the expectation didn't match
type Sequence ¶
type Sequence []Pattern
Sequence represents an exact sequence of arbitrary patterns
func (Sequence) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type SourceFile ¶
SourceFile represents a source file
type Term ¶
type Term FragmentKind
Term represents a concrete terminal token pattern
func (Term) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type TermExact ¶
type TermExact struct {
Kind FragmentKind
Expectation string
}
TermExact represents an exact terminal token pattern
func (TermExact) TerminalPattern ¶
TerminalPattern implements the Pattern interface
type Token ¶
type Token struct {
VBegin Cursor
VEnd Cursor
VKind FragmentKind
}
Token represents a terminal fragment
func (*Token) Kind ¶
func (tk *Token) Kind() FragmentKind
Kind returns the kind of the token fragment
type ZeroOrMore ¶
type ZeroOrMore struct{ Pattern }
ZeroOrMore represents zero or more arbitrary patterns
func (ZeroOrMore) Container ¶
func (ZeroOrMore) Container() bool
Container implements the Pattern interface
func (ZeroOrMore) Desig ¶
func (zom ZeroOrMore) Desig() string
Desig implements the Pattern interface
func (ZeroOrMore) TerminalPattern ¶
func (zom ZeroOrMore) TerminalPattern() Pattern
TerminalPattern implements the Pattern interface
Source Files
Directories