From eplmediawiki
This is the approved revision of this page; it is not the most recent. View the most recent revision.
Jump to: navigation, search

Strictly speaking, parser is something that separates data into more easily understood chunks. More practically, a parser is the part of a compiler that goes through a program and cuts it into identifiable chunks before translation. Assuming that a parser is written reliably, if the parser cannot parse a program then the program contains syntax errors. Also, we can say that a parser is an algorithm or program to determine the syntactic structure of a sentence or string of symbols in some language. A parser normally takes as input a sequence of tokens output by a lexical analyser and the grammar that defines language under consideration. It may produce some kind of abstract syntax tree as output. One of the best known parser generators is yacc[INSERIR LINK].

The task of the parser to determine if and how the input can be derived from the start symbol within the rules of the formal grammar can be done in essentially two ways:


Top-down parsing

A parser can start with the start symbol and try to transform it to the input. Intuitively, the parser starts from the largest elements and breaks them down into incrementally smaller parts.

Examples of top-down parsers

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

Bottom-up parsing

A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on.

Examples of bottom-up parsers

  • BC (bounded context) parsing
  • Canonical LR parser
  • CYK parser
  • Earley parser
  • GLR parser
  • LALR parser
  • LR parsers
  • Precedence parsing
  • SLR parser

Another term used for this type of parser is Shift-Reduce parsing.

See also: LALR parsers, LL(k) ---- LL(1) Parsers, LR(0) ---- SLR(1) Parsers, LR(k) ---- LR(1) Parsers and LR vs. LL Parsers

Personal tools