Compiler Design · topic
Handles and shift-reduce parsing, operator precedence, LR(0) items and automata, SLR, CLR(1) and LALR(1) tables, shift-reduce and reduce-reduce conflicts, state counts, and which grammar falls in which class.
A bottom-up parser builds the parse tree from the leaves up to the root. It starts from the input string and repeatedly replaces a substring that matches the body of a production by the production's head, a step called a reduction, until only the start symbol remains.
An LR parser is a shift-reduce parser that decides each action from a table indexed by a state on top of its stack and the next input token. The states are the states of a DFA that recognises viable prefixes, so the parser always knows which productions it might be in the middle of.
SLR places a reduction A → α on every token in FOLLOW(A). FOLLOW is a global set: it collects every token that can follow A anywhere in the grammar, even when, in the particular state the parser is in, only a few of those tokens can actually come next.
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.
