Home > Parser

The task of the parser can be summarized as to determine if and how the input can be derived from the start symbol with the rules of the formal grammar. A parser can do this in essentially two ways: it can start with the input and attempt to rewrite it to the start symbol, a so-called bottom-up parser, or it can start with the start symbol and try to rewrite it to the input, a so-called top-down parser. For example LL parsers are top-down parsers and LR parsers are bottom-up parsers.

Another important distinction is whether the parser generates a leftmost derivation or a rightmost derivation (see context-free grammar). LL parsers will generate a leftmost derivationThere are several meanings of derivation A derivation in abstract algebra is a linear map that satisfies Leibniz' law. A derivation in computer science is a parse tree representing one possible way to parse a string using a context-free grammar. A derivat and LR parsers will generate a rightmost derivation (although usually in reverse).

1 Overview of Parsers

1.1 Top-down parsers

Some of the parsers that use top-down parsing include:

• Recursive descent parserA recursive descent parser is a top-down parser built from a set of mutually-recursive procedures or a non-recursive equivalent where each such procedure usually implements one of the production rules of the grammar. Thus the structure of the resulting pr
• LL parser
• Packrat parserA packrat parser is a form of parser similar to a recursive descent parser in construction, except that during the parsing process it memoizes the intermediate results of all invocations of the mutually recursive parsing functions. Because of this memoiza
• Unger parser

1.2 Bottom-up parsers

Some of the parsers that use bottom-up parsing include:

• LR parser
  • SLR parser
  • LALR parser
  • Canonical LR parser
• Earley parser
• CYK parser
• Tomita parser

2 See also

• Chart parser
• Compiler-compiler
• SableCC
• JavaCC
• Yacc
• Lex
• pass
• Spirit Parser Framework