Parsing is the phase where a flat stream of tokens becomes a tree that matches the language's grammar. It is also the heaviest-scoring area of compiler design, because it splits into two families, top-down and bottom-up, each with its own tables and traps. If you can compute FIRST and FOLLOW sets and trace one parse of each kind, most parsing questions become mechanical.
Top-down versus bottom-up: the core split
A top-down parser builds the parse tree from the root down, starting at the grammar's start symbol and trying to derive the input. It corresponds to a leftmost derivation. A bottom-up parser works from the leaves up, starting at the tokens and reducing them back to the start symbol. It corresponds to a rightmost derivation in reverse.
The practical difference: top-down parsers are simpler and can be hand-written, but they need the grammar cleaned of left recursion. Bottom-up parsers are table-driven and handle a strictly larger class of grammars. The LR family recognised by bottom-up parsers properly contains the LL family recognised by top-down predictive parsers.
FIRST and FOLLOW sets
Both predictive parsing and SLR table construction rest on two sets:
FIRST of a string is the set of terminals that can begin some string derived from it. If the string can derive the empty string, then the empty string is also in FIRST.
FOLLOW of a non-terminal is the set of terminals that can appear immediately to its right in some derivation. The end-marker is in FOLLOW of the start symbol.
Take this expression grammar, already rewritten to remove left recursion so it is suitable for top-down parsing. Here E' is the tail that turns the original left recursion into right recursion, and the empty string is written as epsilon:
E goes to T E'
E' goes to plus T E', or epsilon
T goes to id
Computing the sets: FIRST of E and of T is { id }. FIRST of E' is { plus, epsilon }. FOLLOW of E and E' is { end-marker }, and FOLLOW of T is { plus, end-marker }.
LL(1) predictive parsing: a worked table
An LL(1) parser uses one lookahead token and a table indexed by non-terminal and terminal. The rule: for a production A goes to alpha, place it under every terminal in FIRST of alpha; if alpha can be empty, also place it under every terminal in FOLLOW of A. Applying that to the grammar gives:
Non-terminal | id | plus | end-marker |
|---|---|---|---|
E | E goes to T E' | ||
E' | E' goes to plus T E' | E' goes to epsilon | |
T | T goes to id |
Because no cell holds two productions, the grammar is LL(1). Now trace parsing the input id plus id, using a stack with its top on the left, and matching or expanding at each step:
Stack | Input | Action |
|---|---|---|
E | id plus id | expand E goes to T E' |
T E' | id plus id | expand T goes to id |
id E' | id plus id | match id |
E' | plus id | expand E' goes to plus T E' |
plus T E' | plus id | match plus |
T E' | id | expand T goes to id |
id E' | id | match id |
E' | (end) | expand E' goes to epsilon |
(empty) | (end) | accept |
The stack empties exactly as the input ends, so the string is accepted. This match-or-expand loop is the whole of predictive parsing.
LR and SLR shift-reduce parsing
Bottom-up parsers are shift-reduce parsers. They keep a stack and repeatedly either shift the next token onto it, or reduce a group of symbols on top, called a handle, back to the non-terminal that produces them. The LR family builds a table of states from the grammar's items; SLR(1) is the simplest such table, using FOLLOW sets to decide reductions, with LALR(1) and canonical LR(1) handling progressively more grammars. A reduction is legal only when the lookahead permits it, and that is where the FOLLOW sets earn their keep: an SLR(1) table reduces by A goes to alpha only when the next token lies in FOLLOW of A.
Trace a shift-reduce parse of id plus id on the natural left-recursive grammar E goes to E plus T or T, and T goes to id, which bottom-up parsing handles directly. The stack top sits on the right here, the way shift-reduce tables are conventionally written:
Stack | Input | Action |
|---|---|---|
(empty) | id plus id | shift |
id | plus id | reduce T goes to id |
T | plus id | reduce E goes to T |
E | plus id | shift |
E plus | id | shift |
E plus id | (end) | reduce T goes to id |
E plus T | (end) | reduce E goes to E plus T |
E | (end) | accept |
Two of those reductions are worth checking against that rule. For this grammar FOLLOW of T and FOLLOW of E are both { plus, end-marker }. At step two the lookahead is plus, which is in FOLLOW of T, so reducing id to T is allowed; at step three the lookahead is still plus, which is in FOLLOW of E, so reducing T to E is allowed as well. Deciding reductions this way is exactly what makes an SLR(1) table SLR(1), the states themselves coming from the grammar's LR(0) items, and it is also where SLR breaks: if a state offers a shift on some token and a reduce whose FOLLOW set contains that same token, the cell holds two entries and the grammar is not SLR(1). The SLR, CLR and LALR parsers compared deep-dive works those conflicts and the stronger tables that resolve them.
Notice the direction: the top-down trace expanded the start symbol toward the tokens, while the bottom-up trace reduced the tokens toward the start symbol. The two traces also ran on different grammars, and that difference is the price top-down parsing charges. The left-recursive rule E goes to E plus T had to be rewritten as E goes to T E' before a predictive parser could touch it, while the shift-reduce parser consumed it unchanged. Put both directions on the one left-recursive grammar, as the figure does, and the parse tree comes out identical; only the order in which its nodes are built changes.
Recursive descent versus shift-reduce
The two families show up in practice as two coding styles. Recursive descent is a top-down parser written as one function per non-terminal, calling each other to mirror the grammar; predictive recursive descent uses the FIRST and FOLLOW sets to pick a production without backtracking. Shift-reduce parsers are bottom-up and table-driven, generated by tools such as Yacc and Bison from the grammar. Recursive descent is easy to write and debug by hand; shift-reduce accepts more grammars and is what production compiler generators use.
How parsing is tested in GATE
GATE CS leans hard on this topic. Expect a FIRST or FOLLOW computation, a question on whether a grammar is LL(1), an LL(1) or SLR table cell to fill, a shift-reduce trace to complete, and a conflict question asking why a grammar is not SLR(1). The recurring skill is exactly the two traces above, so practise producing them under time.
Parsing consumes the output of the scanner and depends on the grammar theory beneath it. Our context-free grammars and pushdown automata deep-dive covers the grammar machinery parsers are built on, and the Compiler Design learn module sequences syntax analysis after the scanner. To drill each family, work the FIRST and FOLLOW set and the SLR parser conflicts set from previous years.
Practise it, do not just read it
Reading a trace is easy; producing one under time pressure is what actually gets marked. Learn to compute FIRST and FOLLOW, build one LL(1) table, and trace one shift-reduce parse until both are routine.
Work the previous-year FIRST and FOLLOW set and SLR parser conflicts set with worked solutions.
For compiler design across the whole GATE CS syllabus, GATE Guidance by Sanchit Sir sequences parsing with theory of computation.
Browse the neighbouring topics in the CS Fundamentals category.
Master FIRST and FOLLOW, keep the two directions cleanly apart, and hand-trace one parse of each kind. Do that, and parsing turns from the hardest part of compiler design into its most dependable marks.
