Structures

A context free or regular grammar consisting of a set of productions

In context free grammars, the left side of productions (in this framework also referred to as pattern) is always a single non-terminal.

Grammars might be ambiguous. For example, the grammar

<expr> ::= <expr> '+' <expr> | 'a'

can recognize the expression a+a+a+a in 5 different ways: ((a+a)+a)+a, (a+(a+a))+a, a+(a+(a+a)), a+((a+a)+a), (a+a)+(a+a).

A parser based on the CYK algorithm.

The parser can parse non-deterministic and deterministic grammars. It requires O(n^3) runtime.

For ambiguous grammars, the runtime for parses may increase, as some expressions have exponentially many possible parse trees depending on expression length. This exponential growth can be avoided by only generating a single parse tree with syntaxTree(for:).

For unambiguous grammars, the Earley parser should be used instead, as it has linear or quadratic runtime.

The original CYK parsing can only recognize grammars in Chomsky normal form. This parser automatically transforms the recognized grammar into Chomsky normal form and transforms the parse tree back to the original grammar. Nullable items are ommited in the parse tree of the CYK parser.

A set of terminal or non-terminal symbols

A string of symbols which can be used in a production of a grammar

A string of non-terminal symbols

A production result contains multiple possible production strings which can all be generated from a given non-terminal.

A production result can be used when creating a production rule with different possible productions:

"A" --> n("B") <|> t("x")
                ^ generates a production result

A parser generator implementation that internally uses the Earley algorithm.

Creates a syntax tree in O(n^3) worst case run time. For unambiguous grammars, the run time is O(n^2). For almost all LR(k) grammars, the run time is O(n). Best performance can be achieved with left recursive grammars.

For ambiguous grammars, the runtime for parses may increase, as some expressions have exponentially many possible parse trees depending on expression length. This exponential growth can be avoided by only generating a single parse tree with syntaxTree(for:).

For unambiguous grammars, the Earley parser performs better than the CYK parser.

A syntax error which was generated during parsing or tokenization

A production describing what symbols can be generated starting from a given non-terminal pattern

A non-terminal symbol, which cannot occurr in a word recognized by a parser

A simple tokenizer which uses a all terminals in a grammar for tokenization.

Terminals may not overlap partially. If two terminals, ab and bc exist and abc is tokenized, the tokenizer will not find an occurrence of the second terminal.