A parser is a computer program or a component of a program that analyses the grammatical structure of an input, with respect to a given formal grammar, a process known as parsing. Typically, a parser transforms some input text into a data structure that can be processed easily, e.g. for semantic checking, code generation or simply to ease the further understanding of the input. Such a data structure usually captures the implied hierarchy of the input and forms a tree or even a graph.

Parsers can be made both for natural languages and for programming languages. Programming language parsers tend to be based on context free grammars as fast and efficient parsers can be written for them. Context free grammars however are limited in their expressiveness, i.e. the kinds of languages which can be described with them is limited. Informally, the range of memorization is limited. E.g., one cannot memorize the occurance of a construct over an arbitrary length of input which is necessary if in a language a construct has to be mentioned first before one can refer to it. More powerful grammars however cannot be parsed efficiently or are not intuitive at all. Thus, a common strategy to accept such language constructs is to relax the parser, i.e. let it accept a broader language with invalid constructs and filter these afterwards. Note that it is usually not a problem to find a context free grammar including all desired language constructs. Rather, it is often impossible to restrict a context free grammar to descibe only valid constructs.

For example LALR parsers are capable of efficiently analysing a wide class of context free grammars. Such parsers are usually not written by hand but generated by parser generators.

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 derivation and LR parsers will generate a rightmost derivation (although usually in reverse).

Overview of parsers

Top-down parsers

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

• Recursive descent parser
• LL parser
• Packrat parser
• Unger parser

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

See also

• Chart parser
• Compiler-compiler
• SableCC
• JavaCC
• Yacc
• Lex
• pass
• Spirit parser framework
• Shallow parsing

References

External links

• Citations from CiteSeer
• UCalc Fast Math Parser A commercial expression parser