Compiler Design · topic
Derivations, parse trees and ambiguity, left recursion removal and left factoring, FIRST and FOLLOW computed to a fixed point, the LL(1) table and its conflicts, predictive parsing traces and recursive descent.
A context-free grammar written to describe a language is often unsuitable for a parser. An ambiguous grammar gives a parser two trees to choose from. A left-recursive grammar sends a top-down parser into an infinite loop.
A predictive parser must decide which production to apply by looking only at the next input token. A bottom-up SLR parser must decide whether to reduce by looking at the same token.
A top-down parser builds the parse tree from the root down, in preorder, and in doing so produces a leftmost derivation of the input. At each step it holds a leftmost nonterminal and must choose one of its productions.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
