Parsing

Role of syntax analysis

Definition. A parser receives the token stream from the scanner and determines whether it can be derived from the grammar. It builds a parse tree or abstract syntax tree and reports syntax errors. Top-down methods expand from the start symbol; bottom-up methods reduce input toward the start symbol.

Example. Tokens ID PLUS ID can be parsed as an expression if the grammar has an addition production.

Exam point. Parsing consumes tokens, not raw characters, unless a question explicitly combines scanning and parsing.

Solved example

Example — grammar membership. Grammar E→E+T|T, T→id receives id+id.

1. Derive E⇒E+T.
2. Left E⇒T⇒id; right T⇒id.
3. The yield is id+id.
4. The token sequence is syntactically valid. The sequence id+ + id is not generated.

Ambiguity and operator precedence

Definition. A grammar is ambiguous when one terminal string has multiple parse trees. Operator precedence and associativity are encoded by separating grammar levels or by parser declarations; multiplication typically binds more tightly than addition, while left associativity groups repeated operators from the left.

Example. Grammar E→E+E|E*E|id gives two parses for id+id*id.

Exam point. A parser generator's precedence directives can resolve a conflict operationally but do not make the original CFG unambiguous.

Solved examples

Example 1 — identify grouping. Interpret a-b-c under left-associative subtraction.

1. Left associativity groups the first two operands.
2. The tree is (a-b)-c.
3. It is not a-(b-c).

Example 2 — expression grammar. Use E→E+T|T, T→T*F|F, F→(E)|id to group id+id*id.

1. The top-level E uses E+T.
2. The left E derives id.
3. The right T uses TF, deriving idid.
4. The tree groups as id+(id*id).

Left recursion and left factoring

Definition. A top-down predictive parser cannot use a production that immediately recurses on the same leftmost variable without consuming input. Immediate left recursion A→Aα|β can be transformed to A→βA', A'→αA'|ε when β does not begin with A. Left factoring extracts common prefixes to defer a choice until more input is seen.

Example. A→ab|ac factors to A→aA', A'→b|c.

Exam point. These transformations help predictive parsing but do not guarantee the resulting grammar is LL(1).

Solved examples

Example 1 — remove recursion. Convert E→E+T|T.

1. Recursive suffix is +T; base alternative is T.
2. Introduce E'.
3. E→TE', E'→+TE'|ε.
4. The new grammar is right recursive and represents zero or more additions.

Example 2 — factor alternatives. Convert S→if E then S else S | if E then S.

1. Shared prefix is if E then S.
2. Let S→if E then S S'.
3. Let S'→else S|ε.
4. The common prefix is parsed before selecting whether else follows. This grammar may still have the dangling-else ambiguity.

FIRST sets

Definition. FIRST(X) is the set of terminals that can begin strings derived from X; include ε if X can derive ε. For a sequence, add FIRST sets left to right until reaching a nonnullable symbol. FIRST of a terminal is itself.

Example. If A→a|ε and B→b, then FIRST(AB)={a,b}.

Exam point. ε belongs to FIRST of a sequence only if every symbol in the sequence is nullable.

Worked FIRST/FOLLOW grammar

Use the grammar:

• E → T E'
• E' → + T E' | ε
• T → F T'
• T' → * F T' | ε
• F → ( E ) | id

Terminals are id,+,*,(,),$.

Solved example — compute FIRST step by step

1. F begins with ( or id, so FIRST(F)={(,id}; F is not nullable.
2. T→FT' begins with F, so FIRST(T)={(,id}; T is not nullable.
3. T' has alternatives *FT' and ε, so FIRST(T')={*,ε}.
4. E' has alternatives +TE' and ε, so FIRST(E')={+,ε}.
5. E→TE' begins with T, so FIRST(E)={(,id}.

Variable	FIRST
E	{(, id}
E'	{+, ε}
T	{(, id}
T'	{*, ε}
F	{(, id}

Result. Only E' and T' are nullable.

FOLLOW sets

Definition. FOLLOW(A) contains terminals that may appear immediately after A in a sentential form. Put $ in FOLLOW(start). For production A→αBβ, add FIRST(β)−{ε} to FOLLOW(B); if β is nullable or absent, add FOLLOW(A) to FOLLOW(B). Repeat to a fixed point.

Example. In S→AB, FIRST(B)−{ε} enters FOLLOW(A); FOLLOW(S) enters FOLLOW(B) if B is at the end.

Exam point. FOLLOW contains terminals, not ε.

Solved example — build FOLLOW sets fully

1. E is start, so $∈FOLLOW(E).
2. In F→(E), ) follows E, giving FOLLOW(E)={),$}.
3. In E→TE', E' is at the end, so FOLLOW(E)⊆FOLLOW(E'). The + in E'→+TE' means E' can be followed by anything following E' through recursion; fixed point gives FOLLOW(E')={),$}.
4. In E'→+TE', T is followed by E'. Add FIRST(E')−{ε}={+} to FOLLOW(T); because E' is nullable, add FOLLOW(E')={),$}. Thus FOLLOW(T)={+,),$}.
5. In T→FT', T' is at the end, so FOLLOW(T)⊆FOLLOW(T'). This yields FOLLOW(T')={+,),$}.
6. In T'→*FT', F is followed by T'. Add * and, since T' nullable, FOLLOW(T') to FOLLOW(F).
7. In T→FT', F is followed by T', adding * and FOLLOW(T) because T' nullable.
8. FOLLOW(E)={),$}; FOLLOW(E')={),$}; FOLLOW(T)={+,),$}; FOLLOW(T')={+,),$}; FOLLOW(F)={*,+,),$}.

Variable	FOLLOW
E	{), $}
E'	{), $}
T	{+, ), $}
T'	{+, ), $}
F	{*, +, ), $}

LL(1) parsing table

Definition. For each production A→α, place it in M[A,a] for every a∈FIRST(α)−{ε}. If α is nullable, also place it in M[A,b] for every b∈FOLLOW(A). A grammar is LL(1) when no table cell contains conflicting productions.

Example. For E'→ε, place the production in columns in FOLLOW(E'), namely ) and $.

Exam point. Empty table cells are errors; a cell with two productions is a predictive parsing conflict.

Solved example — fill the expression table

1. E→TE' uses FIRST(T)={(,id}: put it in E rows under ( and id.
2. E'→+TE' goes under +; E'→ε goes under ) and $.
3. T→FT' goes under ( and id.
4. T'→*FT' goes under *; T'→ε goes under +,),$.
5. F→(E) goes under (; F→id goes under id.

Nonterminal	id	+	*	(	)	$
E	E→TE'	—	—	E→TE'	—	—
E'	—	E'→+TE'	—	—	E'→ε	E'→ε
T	T→FT'	—	—	T→FT'	—	—
T'	—	T'→ε	T'→*FT'	—	T'→ε	T'→ε
F	F→id	—	—	F→(E)	—	—

Conclusion. Every occupied cell has one production, so the grammar is LL(1).

Predictive parsing trace

Definition. A table-driven LL(1) parser uses a stack initialized with start symbol and $. If the top is a terminal, it must match the lookahead; if it is a variable, use the table entry and push the production's right side in reverse order. Accept when both stack and input contain only $.

Example. On input id+id*id, the parser expands E, then T, matches id, and uses E' to process +.

Exam point. The stack top is conventionally shown at the right; state this before tracing.

Solved example — parse id+id*id

Stack (top right)	Input	Action
$ E	id + id * id $	E→TE'
$ E' T	id + id * id $	T→FT'
$ E' T' F	id + id * id $	F→id
$ E' T' id	id + id * id $	match id
$ E' T'	+ id * id $	T'→ε
$ E'	+ id * id $	E'→+TE'
$ E' T +	+ id * id $	match +
$ E' T	id * id $	T→FT'
$ E' T' F	id * id $	F→id
$ E' T' id	id * id $	match id
$ E' T'	* id $	T'→*FT'
$ E' T' F *	* id $	match *
$ E' T' F	id $	F→id
$ E' T' id	id $	match id
$ E' T'	$	T'→ε
$ E'	$	E'→ε
$	$	accept

Trace conclusion. The table selects a unique production at each step; multiplication is grouped within T before E handles addition.

LL(1) conflicts and grammar limitations

Definition. LL(1) requires a unique production choice from one lookahead token. FIRST/FIRST conflicts arise when alternatives can start alike; FIRST/FOLLOW conflicts arise when a nullable alternative overlaps the FOLLOW set. Some grammars are not LL(1) but generate valid CFLs.

Example. A→aB|aC has a FIRST/FIRST conflict on a.

Exam point. Left factoring can remove a shared prefix but may not eliminate all conflicts.

Solved examples

Example 1 — FIRST/FIRST conflict. For S→aA|aB, build the relevant table cell.

1. FIRST(aA)={a} and FIRST(aB)={a}.
2. Both productions are placed in M[S,a].
3. The cell has two rules, so the grammar is not LL(1).

Example 2 — nullable conflict. Grammar A→a|ε, with a∈FOLLOW(A).

1. A→a enters M[A,a] by FIRST.
2. A→ε enters M[A,a] because a∈FOLLOW(A).
3. This FIRST/FOLLOW collision prevents LL(1) parsing.