Next: Top-down parsing
Up: Compiler Theory: Syntax Analysis
Previous: Left factoring
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
(n3) 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.
Subsections
Next: Top-down parsing
Up: Compiler Theory: Syntax Analysis
Previous: Left factoring
Marc Moreno Maza
2004-12-02