A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Pretty Printer
A pretty printer is a tool that analyzes a program and prints it in such a way that the structure of the program becomes
clearly visible. For example, comments may appear in a special font, and statements may appear with
an amount of identation proportional to the depth of their nesting in the hierachical organization of the statements.
Parser
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.
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: L (LL & LR) Parsers