Parsing is the process of determining if a string of tokens can be generated by a grammar. It is helpful to think of a parse tree being constructed (even though a compiler may not actually construct such tree).

__EFFICIENCY CONSIDERATIONS.__

- A parser can be constructed from any gammar.
- However grammars used in practice have a special form.
- For any context-free grammar there is a parser that takes
at most
(
*n*^{3}) time to parse a string of*n*tokens. - But in fact there are linear algorithms to parse all languages that arise in practice.
- Programming language parsers almost always make a single left-to-right scan over the input, looking ahead one token at a time

__METHODS.__ Most parsing methods fall into one of the two
following classes

**Top-down parsing.**-
- Construction starts at the root and proceeds towards the leaves.
- Efficient top-down parsers can be constructed by hands.

**Bottom-up parsing.**-
- Construction starts at the leaves and proceeds towards the root.
- Bottom-up parsers can handle a larger class of grammars.
- Software for generating parsers tend to produce bottom-up parsers.

- Top-down parsing
- Predictive parsing
- Non-recursive implementation of predictive parsing
*LL*(1) Grammars

2004-12-02