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.
This post teaches both families on one small grammar, with the worked tables and traces the exam actually asks you to produce. It assumes you know what a context-free grammar is; if not, read that first.
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 makes the recursion right-associative, 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.
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:
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 |
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. Same tree, opposite construction order.
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
Parsing is confirmed on questions. 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.
