Parsing

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 $\cal {O}$(n³) 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.