SYNTAX ANALYSIS

Module 3: Syntax Analysis [9L]

The Role of a Parser | Context-Free Grammars | Writing a Grammar |

Top-Down Parsing | Non-Recursive Predictive (LL) Parsing | Bottom-Up Parsing |
Handles | Viable Prefixes | Operator Precedence Parsing |
LR Parsers (SLR, LALR) | Parser Generators (YACC) | Error Recovery Strategies

MAKAUT (WBUT) — [Link] CSE / IT • Detailed Study Notes

 Table of Contents

1. The Role of a Parser 3

2. Context-Free Grammars 5

3. Writing a Grammar 7

3.1 Ambiguity 3.2 Left Recursion 3.3 Left Factoring

4. Top-Down Parsing 10

4.1 Recursive Descent Parsing 4.2 FIRST and FOLLOW

5. Non-Recursive Predictive Parsing (LL(1)) 13

6. Bottom-Up Parsing 16

6.1 Shift-Reduce Parsing 6.2 Handles 6.3 Viable Prefixes

7. Operator Precedence Parsing 19

8. LR Parsers 22

8.1 LR(0) Items 8.2 SLR Parsing 8.3 CLR / LALR Parsing

9. Parser Generators — YACC 28

10. Error Recovery Strategies 30

11. Quick Revision Summary 33

12. Important Exam Question Bank 34

 1. The Role of a Parser

A parser (syntax analyzer) obtains a string of tokens from the lexical analyzer, and verifies that the string can be generated by the grammar for the source
language. It reports any syntax errors, and constructs, at least conceptually, a parse tree representing the syntactic structure of the token stream, which
is passed on (often implicitly, via syntax-directed translation) to the rest of the compiler.

Source ┌────────────────┐ token ┌──────────┐ parse tree ┌────────────────┐

Program ───────▶│ Lexical Analyzer │───────▶│ Parser │──────────────▶│ Rest of Front End │
└────────────────┘◀────────└──────────┘ └────────────────┘
getNextToken() │
▼
┌────────────┐
│ Symbol Table │
└────────────┘

1.1 Position of the Parser in the Compiler Model

The parser calls the lexical analyzer, using a call such as getNextToken() , whenever it needs another token. It then checks whether the sequence of token
names can be generated by the grammar for the source language; if not, it must report a syntax error and, ideally, recover so that it can continue to look for
further errors.

1.2 Types of Parsers

Universal parsing methods (e.g. the Cocke-Younger-Kasami algorithm, Earley's algorithm) can parse any grammar, but are too inefficient for production
compilers. Instead, compilers use one of two efficient classes of methods:

Category Description Examples

Top-Down Build the parse tree from the root downward to the leaves; can be viewed as attempting to find a leftmost Recursive Descent, LL(1) Predictive
Parsers derivation for the input string Parsing

Bottom-Up Build the parse tree from the leaves upward to the root; can be viewed as reducing the input string down to the Shift-Reduce, Operator-Precedence, LR
Parsers start symbol (a reverse rightmost derivation) (SLR, CLR, LALR)

Exam Tip: Both classes only efficiently handle restricted subsets of grammars — top-down methods generally require the grammar to be free of left
recursion and left-factored (ideally LL(1)); bottom-up LR methods can handle a much larger class of grammars, which is why virtually all parser generators
(like YACC) use LR-based techniques.
 2. Context-Free Grammars

A context-free grammar (CFG) consists of terminals, nonterminals, a start symbol, and productions. It gives a precise, easy-to-understand syntactic
specification of a programming language, and its structure can often expose ambiguities that might otherwise go unnoticed in an initial design.

2.1 Formal Definition

A CFG G is a 4-tuple (V, T, P, S) where:

Component Meaning

V (or N) A finite set of nonterminals (syntactic variables) denoting sets of strings

T A finite set of terminals — the basic symbols (tokens) from which strings are formed; T ∩ V = ∅

P A finite set of productions, each of the form A → α, where A is a nonterminal and α is a string of terminals and nonterminals (including ε)

S A designated nonterminal called the start symbol, from which derivations begin

2.2 Example Grammar

Grammar for simple arithmetic expressions:

E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id

Here E, T, F are nonterminals (start symbol E); +, -, *, /, (, ), id are terminals.

2.3 Derivations

A derivation is a sequence of production applications starting from the start symbol and ending at a string of terminals (a sentence). At each step, a
nonterminal in the current string is replaced by the right side of one of its productions.

Type Rule

Leftmost Derivation At each step, the leftmost nonterminal in the current string is replaced

Rightmost Derivation At each step, the rightmost nonterminal in the current string is replaced

Leftmost derivation of id + id * id using the grammar above:

E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + T * F
⇒ id + F * F ⇒ id + id * F ⇒ id + id * id

2.4 Parse Trees

A parse tree can be viewed as a graphical representation of a derivation that filters out the order in which productions are applied to replace
nonterminals. Each interior node represents the application of a production; its label is the nonterminal A on the left of the production, and its children are
labelled by the symbols on the right side of that production, left to right.

Parse tree for id + id * id:

E
/ | \
E + T
| /|\
T T * F
| | |
F F id
| |
id id

2.5 Ambiguity

A grammar that produces more than one parse tree for some sentence is said to be ambiguous. Equivalently, an ambiguous grammar is one that
produces more than one leftmost (or more than one rightmost) derivation for the same sentence.

The grammar E → E + E | E * E | ( E ) | id is ambiguous — the string id + id * id has two distinct parse trees, one where + is applied last
(giving id + (id*id) ) and one where * is applied last (giving (id+id)*id ), so the grammar does not by itself fix operator precedence.

Exam Tip: "Show that the grammar E → E+E | E*E | (E) | id is ambiguous" is a classic question — always show two distinct parse trees (or two distinct
leftmost derivations) for the same string, such as id+id*id, to prove ambiguity.
 3. Writing a Grammar

Even though the syntax of programming-language constructs can typically be specified by a context-free grammar, not every such grammar is suitable for
automatic parsing. Certain transformations are needed to prepare a grammar for use with a particular parsing method.

3.1 Regular Expressions vs Context-Free Grammars

Every construct that can be described by a regular expression can also be described by a grammar, but not vice-versa (CFGs are strictly more powerful — e.g.,
they can express balanced/nested parentheses, which regular expressions cannot). Regular expressions are generally preferred for lexical structure since they
lead to a simpler and more efficient lexical analyzer.

3.2 Eliminating Ambiguity

Ambiguity can sometimes be eliminated by rewriting the grammar, typically by imposing explicit precedence and associativity through the grammar's structure.

The classic dangling-else ambiguity:

stmt → if expr then stmt

| if expr then stmt else stmt
| other

This grammar is ambiguous — for if E1 then if E2 then S1 else S2 , it is unclear whether "else S2" matches the first or second "if". The standard
convention (and rewritten unambiguous grammar) matches each else with the closest previous unmatched then, by distinguishing "matched" and
"unmatched" statements:

stmt → matchedStmt | unmatchedStmt

matchedStmt → if expr then matchedStmt else matchedStmt
| other
unmatchedStmt → if expr then stmt
| if expr then matchedStmt else unmatchedStmt

3.3 Elimination of Left Recursion

A grammar is left recursive if it has a nonterminal A such that there is a derivation A ⇒+ Aα for some string α. Top-down parsing methods cannot handle
left-recursive grammars, so such recursion must be eliminated before top-down parsing.

Immediate Left Recursion — Elimination Rule

Given: A → A α | β (β does not begin with A)

Rewrite as: A → β A'

A' → α A' | ε

Example: Eliminate left recursion from E → E + T | T :

E → T E'
E' → + T E' | ε

General Left Recursion Elimination Algorithm

1. Arrange the nonterminals in some order A1, A2, ..., An.

2. for i = 1 to n:
for j = 1 to i-1:
replace each production Ai → Aj γ
with the productions Ai → δ1 γ | δ2 γ | ... | δk γ
where Aj → δ1 | δ2 | ... | δk are all current Aj-productions
eliminate the immediate left recursion among the Ai productions

This handles indirect left recursion (e.g., A → Bα, B → Aβ), which can be less obvious than the immediate case.

3.4 Left Factoring

Left factoring is a grammar transformation useful when it is not clear which of two or more alternative productions to use to expand a nonterminal,
because they share a common prefix. In such cases, we can rewrite the productions to defer the decision until enough of the input has been seen to make
the right choice.

Given: A → α β1 | α β2 (common prefix α)

 Rewrite as: A → α A'
A' → β1 | β2

Example: Left-factor stmt → if expr then stmt else stmt | if expr then stmt :

stmt → if expr then stmt stmt'

stmt' → else stmt | ε

Exam Tip: "Eliminate left recursion and perform left factoring" on a given grammar is one of the most frequently repeated numerical questions. Always
apply left-recursion elimination first, then check for any remaining common prefixes to left-factor.
 4. Top-Down Parsing

Top-down parsing can be viewed as an attempt to find a leftmost derivation for an input string, or equivalently, an attempt to construct a parse tree for
the input starting from the root and creating the nodes in preorder.

4.1 Recursive Descent Parsing

A recursive-descent parser consists of a set of procedures, one for each nonterminal. Execution begins with the procedure for the start symbol, which
halts and announces success if its procedure body scans the entire input string. A general recursive-descent parsing method may require backtracking,
i.e., it may need to repeatedly scan the input.

Example: Recursive Descent Procedure

For the production A → α1 | α2 | ... | αn :

void A() {
choose a production A → α_i by looking at input & lookahead;
for each symbol X on the right side of α_i (left to right):
if X is a nonterminal: call procedure X();
else if X matches current input token: advance input;
else: report a parsing error (or backtrack, if supported);
}

Backtracking
When a general recursive-descent parser tries a production and fails, it must backtrack and retry with a different alternative — this requires the parser to be
able to "reset" the input to a previous position, which can be costly and is avoided in efficient predictive parsers by choosing productions deterministically using
lookahead.

4.2 FIRST and FOLLOW

The construction of both top-down and bottom-up parsers is aided by two functions, FIRST and FOLLOW, associated with a grammar G. These allow us to fill
in the entries of a predictive parsing table, whenever one exists.

Definition of FIRST

FIRST(α) is the set of terminals that begin the strings derivable from α. If α can derive ε, then ε is also in FIRST(α).

Rules for Computing FIRST(X)

1. If X is a terminal, FIRST(X) = { X }.
2. If X → ε is a production, add ε to FIRST(X).
3. If X is a nonterminal and X → Y1 Y2 ... Yk is a production:
add FIRST(Y1) - {ε} to FIRST(X);
if ε is in FIRST(Y1), also add FIRST(Y2) - {ε}; and so on...
if ε is in FIRST(Y1)...FIRST(Yk) (all of them), add ε to FIRST(X).

Definition of FOLLOW

FOLLOW(A), for a nonterminal A, is the set of terminals a that can appear immediately to the right of A in some sentential form derived from the start
symbol, i.e. S ⇒* αAaβ. If A can be the rightmost symbol in some sentential form, then $ (the input end-marker) is also in FOLLOW(A).

Rules for Computing FOLLOW(A)

1. Place $ in FOLLOW(S), where S is the start symbol.

2. For a production A → αBβ:
everything in FIRST(β) except ε is in FOLLOW(B).
3. For a production A → αB, or A → αBβ where FIRST(β) contains ε
(i.e. β can derive ε):
everything in FOLLOW(A) is also in FOLLOW(B).

Worked example for grammar (after left-recursion elimination):

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

Nonterminal FIRST FOLLOW

E { (, id } { $, ) }

E' { +, ε } { $, ) }

T { (, id } { +, $, ) }

T' { *, ε } { +, $, ) }

F { (, id } { +, *, $, ) }
 5. Non-Recursive Predictive Parsing (LL Parsing)

A non-recursive (table-driven) predictive parser can be built by maintaining a stack explicitly, rather than implicitly via recursive calls. The parser
mimics a leftmost derivation, using an explicit stack containing a sequence of grammar symbols, and a predictive parsing table M that tells it which
production to apply, based on the nonterminal on top of the stack and the current input symbol.

5.1 Model of a Table-Driven Predictive Parser

┌────────────────┐
Input a + b $ ─▶│ │
│ Predictive │──▶ Output (sequence of
Stack X │ Parser │ productions applied)
Y ◀────────────── │ (uses table M) │
Z │ │
$ └────────┬─────────┘
│
┌───────▼────────┐
│ Parsing Table M │
└────────────────┘

5.2 Construction of the LL(1) Parsing Table

For each production A → α of the grammar:

1. for each terminal a in FIRST(α):
add A → α to M[A, a]
2. if ε is in FIRST(α):
for each terminal b in FOLLOW(A):
add A → α to M[A, b]
if $ is in FOLLOW(A):
add A → α to M[A, $]
3. All undefined entries of M are marked "error".

5.3 LL(1) Grammar

A grammar is said to be LL(1) if the parsing table constructed as above has at most one production in each table entry M[A, a] — i.e., no cell of the table
is multiply defined. ("LL(1)" = scan input Left to right, produce a Leftmost derivation, using 1 symbol of lookahead.)

5.4 Worked Example: LL(1) Parsing Table

Using the grammar and FIRST/FOLLOW sets from Section 4.2:

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)

5.5 Predictive Parsing Algorithm

set ip to point to the first symbol of the input string w$

push $, then S (start symbol) onto the stack (S on top)
repeat:
let X be the top stack symbol, a the symbol pointed to by ip
if X is a terminal or $:
if X == a: pop X, advance ip
else: error()
else if M[X, a] is a production X → Y1Y2...Yk:
pop X; push Yk, ..., Y2, Y1 (Y1 on top)
output the production X → Y1Y2...Yk used
else:
error()
until X == $ (stack empty and input consumed successfully)

5.6 Grammars That Are Not LL(1)

A grammar with left recursion, or an ambiguous grammar, can never be LL(1). Furthermore, some grammars that are neither ambiguous nor left-recursive still
fail to be LL(1) — this happens whenever the parsing-table construction leads to a table entry with more than one production, typically because the grammar is
not sufficiently left-factored, or the parser genuinely needs more than one token of lookahead to decide.

Exam Tip: "Check whether the given grammar is LL(1)" — always compute FIRST and FOLLOW carefully first, build the table, and explicitly point out any
cell with two or more productions as the reason the grammar fails to be LL(1).
 6. Bottom-Up Parsing

Bottom-up parsing corresponds to the construction of a parse tree for an input string beginning at the leaves and working up towards the root. It can be
described as a reduction of the input string to the start symbol of the grammar, and corresponds to producing a rightmost derivation in reverse.

6.1 Shift-Reduce Parsing

Shift-reduce parsing is a general style of bottom-up parsing in which a stack holds grammar symbols, and an input buffer holds the rest of the string to
be parsed. At each step, the parser either shifts the next input symbol onto the stack, or reduces a string of symbols at the top of the stack (matching the
right side of some production) to the corresponding left-side nonterminal.

The Four Basic Shift-Reduce Actions

Action Meaning

Shift Push the next input symbol onto the top of the stack

Reduce Replace a string β at the top of the stack (matching the right-hand side of a production A → β) with the nonterminal A

Accept Announce successful completion of parsing (stack contains just the start symbol, and input is exhausted)

Error Discover a syntax error and invoke an error-recovery routine

Trace of shift-reduce parsing for id * id using E → E+T | T, T → T*F | F, F → (E) | id :

Stack Input Action

$ id * id $ shift

$ id * id $ reduce by F→id

$F * id $ reduce by T→F

$T * id $ shift

$T* id $ shift

$ T * id $ reduce by F→id

$T*F $ reduce by T→T*F

$T $ reduce by E→T

$E $ accept

6.2 Handles

A handle of a right-sentential form γ is a production A → β together with a position in γ where the string β may be found, such that replacing β at that
position by A yields the previous right-sentential form in a rightmost derivation of γ. That is, if S ⇒*rm αAw ⇒rm αβw, then A → β in the position following α
is a handle of αβw.

The string w to the right of the handle contains only terminal symbols.
Informally, a handle is a substring that matches the right side of a production, and whose reduction represents one step along the reverse of a rightmost
derivation.
Because the string to the right of a handle contains only terminals, the string left of and including a handle in a right-sentential form is called a viable
prefix.

6.3 Viable Prefixes

A viable prefix of a right-sentential form is any prefix of that sentential form that does not extend past the right end of the rightmost handle. Equivalently,
viable prefixes are exactly the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser at any point, i.e., they never
overshoot the handle so that the parser can always still find a way to reduce back to the start symbol.

Illustration: for the rightmost sentential form E + T * F with handle F (about to be reduced by F→id if F derives from id, or otherwise), any prefix of
the stack contents that stops at or before the end of the handle — e.g. E , E+ , E+T , E+T* , E+T*F — is a viable prefix. A string like E+T*F) (extending
past the handle onto the unscanned input) would not be viable.

Exam Tip: "Define handle and viable prefix" is a very common short-answer question. Remember: the handle is "what gets reduced next"; the viable
prefix is "everything on the stack up to and including the handle" — the set of strings that can legitimately appear on a shift-reduce parser's stack without
forcing an error.
 7. Operator Precedence Parsing

Operator precedence parsing is a simple, easy-to-implement bottom-up parsing technique applicable to a class of grammars called operator grammars,
in which no production's right side is empty (ε) or has two adjacent nonterminals.

7.1 Operator Precedence Relations

Instead of full LR tables, operator-precedence parsing defines just three precedence relations between pairs of terminals a and b:

Relation Symbol Meaning

Yields precedence to a⋖b a has lower precedence than b

Equal precedence a≡b a and b have equal precedence (used mainly for matched delimiters like ( and ))

Takes precedence over a⋗b a has higher precedence than b

7.2 Example: Precedence Table for Simple Expressions

For a grammar with operators +, *, (, ), id , a typical operator precedence table is:

+ * ( ) id $

+ ⋗ ⋖ ⋖ ⋗ ⋖ ⋗

* ⋗ ⋗ ⋖ ⋗ ⋖ ⋗

( ⋖ ⋖ ⋖ ≡ ⋖ —

) ⋗ ⋗ — ⋗ — ⋗

id ⋗ ⋗ — ⋗ — ⋗

$ ⋖ ⋖ ⋖ — ⋖ —

7.3 Operator-Precedence Parsing Algorithm

Initialize: push $ onto the stack; append $ to end of input.

repeat:
let a = topmost terminal on the stack, b = current input symbol
if a ⋖ b or a ≐ b: shift b (and push it) onto the stack; advance input
else if a ⋗ b: reduce -- pop symbols off the stack until the
topmost terminal on the stack is related by ⋖
to the terminal most recently popped; pop that
handle and push the corresponding nonterminal
else: error()
until the stack contains only $ and the start symbol, and input is just $

7.4 Constructing Precedence Relations Using Associativity/Precedence Rules

In practice, the precedence table is constructed directly from the desired precedence and associativity of the operators, rather than derived formally from the
grammar:

If operator θ1 has higher precedence than θ2, then θ1 ⋗ θ2 and θ2 ⋖ θ1.

If θ1 and θ2 have equal precedence, they are both taken as left-associative (θ1 ⋗ θ2 and θ2 ⋗ θ1) or right-associative, according to the language's rules.
id ⋗ op and op ⋖ id for all operators op, since an operand always takes precedence over a following/preceding operator.
( ⋖ op , op ⋖ ) , ( ≡ ) , and $ ⋖ anything , anything ⋗ $ to handle parentheses and the end markers correctly.

7.5 Advantages and Disadvantages

Advantages Disadvantages

Simple and easy to implement by hand Only a small class of grammars (operator grammars) can be parsed this way

The precedence table is typically small Difficult to handle constructs like the unary minus, which has different precedence behavior than binary minus

Fast — parsing decisions made from a single table lookup Errors are detected quite late, and it is hard to give good diagnostics

Not all context-free grammars can be adapted into operator grammars, limiting general applicability

Exam Tip: Because of its limitations, operator precedence parsing has largely been superseded by LR parsing in modern parser generators. It is
nonetheless important academically as a simple, hand-implementable illustration of precedence-driven bottom-up parsing.
 8. LR Parsers

An LR(k) parser reads input Left to right, constructs a Rightmost derivation in reverse, using at most k symbols of lookahead. LR parsing is attractive
because: (i) it can be used to parse virtually all programming-language constructs expressible by a context-free grammar, (ii) it is the most general non-
backtracking shift-reduce method known, yet can be implemented as efficiently as other shift-reduce methods, (iii) an LR parser can detect a syntax error
as soon as it is possible to do so on a left-to-right scan.

8.1 Types of LR Parsers

Type Description Power / Table Size

SLR (Simple Uses LR(0) items; resolves shift/reduce and reduce/reduce Least powerful; smallest tables; easiest to construct
LR) conflicts using FOLLOW sets

CLR (Canonical Uses LR(1) items, which carry an explicit lookahead symbol with Most powerful; largest number of states/tables
LR) each item

LALR (Look- Merges LR(1) states that have the same "core" (set of LR(0) Same number of states as SLR, almost as powerful as CLR; the method of choice for
Ahead LR) items), keeping the lookaheads most parser generators (e.g. YACC)

8.2 LR(0) Items

An LR(0) item of a grammar G is a production of G with a dot (•) at some position of the right side, indicating how much of a production we have seen at a
given point in the parsing process.

For the production A → XYZ , the possible items are:

A → • X Y Z
A → X • Y Z
A → X Y • Z
A → X Y Z •

(The production A → ε generates only one item: A → • .)

8.3 Augmented Grammar

To construct the canonical collection of item sets systematically, the grammar G is first augmented with a new start symbol S' and a production S' → S , so
acceptance can be recognized as the unique moment the parser reduces by this production.

8.4 Closure and GOTO Operations

closure(I):
add every item in I to closure(I)
repeat until no more items can be added:
if A → α • B β is in closure(I), and B → γ is a production,
add the item B → • γ to closure(I) (if not already there)

goto(I, X):
let J = { items A → αX • β such that A → α • X β is in I }
return closure(J)

8.5 Construction of the Canonical Collection of LR(0) Item Sets

C = { closure({ S' → •S }) }
repeat until no more sets can be added to C:
for each set of items I in C, and each grammar symbol X:
if goto(I, X) is not empty and not already in C:
add goto(I, X) to C

8.6 SLR Parsing Table Construction

For each state (item set) Ii in the canonical collection:

1. if [A → α • aβ] is in Ii and goto(Ii, a) = Ij (a is a terminal):
set ACTION[i, a] = "shift j"
2. if [A → α •] is in Ii (A ≠ S'):
for each terminal a in FOLLOW(A):
set ACTION[i, a] = "reduce A → α"
3. if [S' → S •] is in Ii:
set ACTION[i, $] = "accept"
4. if goto(Ii, A) = Ij for nonterminal A:
set GOTO[i, A] = j
5. All entries not defined by rules 1-4 are "error".
8.7 Worked Example: SLR Table for a Small Grammar

Augmented grammar:

(0) S' → S
(1) S → S ; S
(2) S → id

Selected canonical LR(0) item sets (abbreviated):

I0: S'→•S, S→•S;S, S→•id

I1: S'→S•, S→S•;S
I2: S→id•
I3: S→S;•S, S→•S;S, S→•id
I4: S→S;S•, S→S•;S

Resulting (partial) ACTION/GOTO table:

State id ; $ GOTO(S)

0 shift 2 1

1 shift 3 accept

2 reduce S→id reduce S→id

3 shift 2 4

4 shift 3 / reduce S→S;S reduce S→S;S

Note state 4 shows a shift/reduce conflict on ";" — this simple grammar for a list of statements separated by ";" is ambiguous, illustrating a classic pitfall
when writing grammars for SLR parsing.

8.8 SLR Parsing Algorithm (Driver)

Initialize stack with state 0 (i.e. push s0).

repeat:
let s = state on top of stack, a = current input symbol
if ACTION[s, a] = "shift s'":
push a, then push s'; advance input
else if ACTION[s, a] = "reduce A → β":
pop 2*|β| symbols (β and the states below each symbol)
let s' = state now on top of stack
push A, then push GOTO[s', A]
output the production A → β
else if ACTION[s, a] = "accept": stop, parsing successful
else: error()

8.9 Why SLR Can Fail — Reduce/Reduce and Shift/Reduce Conflicts

SLR may place two actions in the same table cell (a conflict) because it uses FOLLOW(A), computed for the grammar as a whole, to decide when to reduce by
A → α — but the correct lookahead set that is valid in a specific state may be a smaller, more context-specific set. This over-approximation is exactly what
canonical LR(1) and LALR(1) parsing address by attaching lookaheads directly to items.

8.10 Canonical LR(1) Items and CLR Parsing

An LR(1) item is a pair [A → α • β, a] consisting of an LR(0) item together with a terminal a (or $) which is a lookahead symbol valid in the context
represented by that item. The extra lookahead component lets the parser reduce A → α only when the actual next input symbol is a, rather than for every
symbol in FOLLOW(A) — this eliminates many of the conflicts that arise in SLR construction.

CLR parsing tables are built the same way as SLR (closure, goto, canonical collection), except items now carry explicit lookaheads, and reductions are only
placed for the specific lookahead symbols attached to each completed item — this produces the most powerful and most conflict-free tables of the three
methods, but typically results in a much larger number of states than SLR or LALR.

8.11 LALR Parsing

The LALR (Look-Ahead LR) method is constructed by taking the canonical LR(1) collection of item sets, and merging together all sets that have the
same "core" (i.e., the same set of first components / LR(0) items, ignoring lookaheads). The resulting parser has exactly as many states as the SLR parser
for the same grammar, but with a more refined, context-sensitive lookahead — able to handle a strictly larger class of grammars than SLR, while remaining
much smaller than the corresponding CLR table.

Comparison of the Three LR Techniques

Method Items Used Number of States (typical) Grammar Class Handled

SLR(1) LR(0) items + FOLLOW sets Fewest Smallest class

LALR(1) Merged LR(1) items (by core) Same as SLR Larger than SLR; sufficient for almost all programming-language grammars
CLR(1) (Canonical LR) Full LR(1) items Many more than SLR/LALR Largest class; most powerful

Exam Tip: "Why is LALR preferred over CLR in practical parser generators such as YACC?" — Answer: LALR tables have the same number of states as
SLR (making them compact enough for practical use) while still being powerful enough to handle essentially all standard programming-language grammar
constructs, unlike the much larger and more memory-intensive CLR tables.
 9. Parser Generators — YACC

YACC ("Yet Another Compiler-Compiler") is a widely used parser generator that takes a context-free grammar specification (with embedded actions) as
input, and automatically produces a bottom-up LALR(1) parser (as C code) for that grammar.

9.1 The YACC Compilation Process

translate.y ┌──────────────┐
(YACC source with ────▶│ YACC Compiler │────▶ [Link].c
grammar + actions) └──────────────┘ (C source of
the parser)
│
lex.l ──▶ Lex Compiler ──▶ [Link].c ───┤
▼
┌──────────────┐
│ C Compiler │
└──────┬───────┘
▼
[Link]
(executable parser)
│
input stream ─────────────────────────▶ │ ──▶ output

9.2 Structure of a YACC Specification

Like Lex, a YACC source file (conventionally with extension .y ) is divided into three sections separated by %% :

{ declarations }
%%
{ translation rules (grammar productions with actions) }
%%
{ supporting C routines }

Section Contents

Declarations Token declarations ( %token ), precedence/associativity declarations ( %left , %right , %nonassoc ), and any C code copied verbatim

Translation Rules A series of grammar productions of the form head : body { semantic action } ; , where semantic actions are C code fragments executed on a
corresponding reduction

Supporting Auxiliary C functions, and typically a main() that calls the generated function yyparse()
Routines

9.3 Example YACC Specification

A simple desk-calculator grammar:

%{
#include <stdio.h>
%}
%token NUMBER
%left '+' '-'
%left '*' '/'

%%
expr : expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| NUMBER { $$ = $1; }
;
%%

int main() { yyparse(); return 0; }

int yyerror(char *s) { fprintf(stderr, "%s\n", s); return 0; }

Here $$ refers to the semantic value of the left-side nonterminal, and $1, $2, $3, ... refer to the semantic values of the corresponding right-side
symbols — this is the standard YACC convention for attaching syntax-directed actions to productions.

9.4 Handling Ambiguity in YACC — Precedence Declarations

Rather than rewriting the grammar to remove ambiguity (as required for pure LL/LR parsing by hand), YACC allows the grammar writer to resolve shift/reduce
conflicts arising from operator ambiguity by declaring operator precedence and associativity directly:

Declaration Meaning
 %left Declares a group of tokens as left-associative, at increasing levels of precedence for successive %left / %right lines

%right Declares a group of tokens as right-associative

%nonassoc Declares tokens as non-associative (e.g. relational operators, where a < b < c is disallowed)

Tokens declared later have higher precedence. On a shift/reduce conflict, YACC by default resolves it in favor of shift unless overridden by these precedence
rules — this default is exactly why the classic dangling-else ambiguity is automatically resolved correctly (matching each else with the nearest unmatched then)
without any grammar rewriting.

9.5 YACC Conflict Reports

When YACC constructs the LALR parsing table and finds a state with more than one possible action, it reports the number of shift/reduce and reduce/reduce
conflicts found. It resolves shift/reduce conflicts by preferring shift, and reduce/reduce conflicts by preferring the rule listed first in the specification — but a
grammar writer should treat such reports as warnings that the grammar may not behave exactly as intended, and should ideally investigate and resolve them
explicitly.

Exam Tip: "Explain the structure and working of YACC as a parser generator" — mention: (1) three-section input format similar to Lex, (2) automatic
LALR(1) table construction from the grammar, (3) semantic actions tied to productions using $$ / $1 / $2 notation, (4) precedence declarations to resolve
ambiguity without grammar rewriting, and (5) integration with a Lex-generated scanner via yylex() .
 10. Error Recovery Strategies

A parser should be able to detect and report the presence of errors in the source program clearly and accurately, and should recover from each error quickly
enough to be able to detect subsequent, unrelated errors — ideally without an excessive number of cascading, spurious errors caused by an earlier one.

10.1 General Strategies (Applicable Across Parsing Methods)

Strategy Description

Panic-Mode On discovering an error, the parser discards input symbols one at a time until one of a designated set of synchronizing tokens (e.g. ; , } ) is found. It is
Recovery simple, guaranteed not to loop, and widely used, but may skip a considerable amount of input without checking it for other errors.

Phrase- On discovering an error, the parser performs local correction on the remaining input — it may replace a prefix of the remaining input with some string that
Level allows parsing to continue (e.g. inserting a missing semicolon, or replacing a comma with a semicolon).
Recovery

Error If common errors are anticipated, the grammar writer can augment the grammar with productions that explicitly generate erroneous constructs; the parser
Productions then uses these to detect the anticipated errors and generate appropriate diagnostics.

Global Given the incorrect input string x and grammar G, algorithms exist to find a parse tree for a related string y "close to" x (minimizing
Correction insertions/deletions/changes) — this is theoretically interesting but too costly to implement in practice.

10.2 Error Recovery in Lexical Analysis

Deleting an extraneous character, or inserting a missing character.
Replacing an incorrect character with a correct one, or transposing two adjacent characters.
Panic-mode: simply skip characters until a well-formed token can be found (common in practice, e.g. skipping an illegal character and reporting it).

10.3 Error Recovery in Predictive (LL) Parsing

In predictive (table-driven LL) parsing, error handling is aided by the fact that an error is detected as soon as the current input symbol does not match
what the parser expects, i.e. an empty entry in the predictive parsing table.

Panic-Mode Recovery for LL Parsers

Compute FOLLOW(A) for each nonterminal A and use these as synchronizing sets stored in the empty table entries.
If the parser looks up M[A, a] and finds it "error" (empty), it skips input symbols until a symbol in synch(A) (typically FOLLOW(A), possibly augmented with
FIRST(A)) is found, then continues.
If the current input symbol does not match a terminal on top of the stack, a simple approach: pop the terminal, issue a message that it was inserted, and
continue.
If a nonterminal A is on top of the stack and the input symbol is in synch(A), the parser pops A from the stack (effectively treating that nonterminal's
construct as if it had matched, on the assumption that A is simply missing).

10.4 Error Recovery in Bottom-Up (LR) Parsing

An LR parser will detect an error when it consults the ACTION table and finds an "error" entry — this happens as soon as the prefix of the input read so far
is not a viable prefix of the grammar, which is the earliest possible point at which an error can be detected in a left-to-right scan.

Panic-Mode Recovery for LR Parsers

1. Scan down the parsing stack until a state s with a GOTO on a

particular nonterminal A is found (A is chosen as one likely
to represent a major program construct, e.g. "stmt" or "expr").
2. Discard zero or more input symbols until a symbol a is found
that can legitimately follow A (i.e. a is in a chosen
synchronizing/resynchronization set).
3. Push the state GOTO[s, A] onto the stack, and resume normal
parsing from this new configuration.

Phrase-Level Recovery for LR Parsers

Each empty entry in the LR ACTION table is individually examined by the compiler writer and filled with a specific error routine — for example, inserting a
missing operand or operator, or deleting a spurious token — tailored to the most common errors expected at that particular parsing state.

10.5 Error Recovery in Operator-Precedence Parsing

When no precedence relation holds between the topmost stack terminal and the current input symbol, the parser has detected an error; recovery typically
follows a panic-mode style, skipping input (or popping the stack) until relations can once again be established, sometimes guided by a small table of common
fix-up rules for typical mistakes (e.g. missing operators between two operands).

10.6 Summary Comparison of Error Recovery Across Methods

Parsing When Error Detected Typical Recovery

Method

Lexical Analysis No pattern matches remaining input Skip/insert/replace characters; panic-mode skip

LL (Predictive) Empty entry in M[A,a], or terminal mismatch Panic-mode using FOLLOW-based synchronizing sets; pop-on-synch for nonterminals

Operator No precedence relation defined between two Panic-mode skipping / localized fix-up rules
Precedence terminals

LR Empty entry in ACTION table (earliest possible Panic-mode stack unwinding to a state with a GOTO on a chosen nonterminal; or phrase-level
(SLR/CLR/LALR) detection point) per-entry fix-up routines

Exam Tip: "Compare error recovery in LL and LR parsing" — key point to mention: LR parsers can detect an error as soon as it is theoretically
possible to do so on a left-to-right scan (before an erroneous handle could ever be reduced), whereas predictive LL parsers detect the error as soon as an
unexpected token doesn't match the predicted production — both are considered "early detecting" compared to weaker methods, but LR is provably at
least as prompt as any other shift-reduce technique.
 11. Quick Revision Summary

Concept One-line Takeaway

Parser Verifies the token stream against the grammar and builds a parse tree, reporting syntax errors.

CFG 4-tuple (V, T, P, S) used to formally define the syntax of a language.

Ambiguity A grammar producing more than one parse tree/derivation for some string.

Left Recursion Elimination A → Aα|β rewritten as A → βA', A' → αA'|ε; required for top-down parsing.

Left Factoring Defers the parser's choice between alternatives sharing a common prefix.

Recursive Descent One procedure per nonterminal; may need backtracking for a general grammar.

FIRST / FOLLOW Sets used to build predictive parsing tables and guide parser decisions.

LL(1) Parsing Table-driven, non-recursive, top-down parsing using 1 lookahead symbol; needs a conflict-free table.

Shift-Reduce Parsing General bottom-up strategy: shift input, reduce handles, until start symbol remains.

Handle The substring to be reduced next, matching a production's right side at the correct position.

Viable Prefix Any prefix of a right-sentential form that does not go past the rightmost handle.

Operator Precedence Parsing Simple bottom-up method using just 3 relations (⋖, ≐, ⋗) between terminals.

SLR LR(0) items + FOLLOW sets; smallest tables, least powerful.

CLR Full LR(1) items with per-item lookahead; most powerful, largest tables.

LALR LR(1) states merged by core; same size as SLR, almost as powerful as CLR — used in YACC.

YACC Parser generator that builds an LALR(1) parser from a grammar + actions specification.

Error Recovery Panic-mode, phrase-level, error-productions, and global-correction strategies, adapted per parsing method.
12. Important Exam Question Bank

Long Answer / Descriptive Questions (5–15 marks)

1. Explain the role of a parser in a compiler with a suitable diagram. Differentiate between top-down and bottom-up parsing.
2. Define context-free grammar formally. Explain leftmost and rightmost derivations with an example.
3. What is an ambiguous grammar? Show that E → E+E | E*E | (E) | id is ambiguous, and rewrite it to remove the ambiguity.
4. Eliminate left recursion from the grammar E → E+T | T, T → T*F | F, F → (E) | id . Compute FIRST and FOLLOW for the resulting grammar.
5. What is left factoring? Left-factor the given grammar for if-then-else statements.
6. Explain non-recursive (table-driven) predictive parsing. Construct the LL(1) parsing table for a given grammar and trace the parsing of a sample input
string.
7. Define handle and viable prefix with suitable examples. Explain shift-reduce parsing with a trace for a sample input.
8. What is operator precedence parsing? Construct the operator precedence table for a simple expression grammar and parse a sample string.
9. Explain the construction of the canonical collection of LR(0) items using closure and goto operations, for a given grammar.
10. Construct the SLR parsing table for a given grammar and trace the parsing of a sample input string.
11. Differentiate between SLR, CLR, and LALR parsing techniques.
12. Explain the design and working of YACC as a parser generator, including how it resolves grammar ambiguity using precedence declarations.
13. Explain the various error recovery strategies used in parsing: panic-mode, phrase-level, error productions, and global correction.
14. Compare error recovery techniques in LL parsers versus LR parsers.

Short Answer Questions (2–3 marks)

15. Define handle. How is it different from a viable prefix?
16. What is meant by an LL(1) grammar?
17. State the rule used to eliminate immediate left recursion.
18. What are the three basic actions in a shift-reduce parser?
19. Why is LALR parsing preferred over canonical LR (CLR) parsing in practical compilers?
20. What is a shift/reduce conflict? How does YACC resolve it by default?
21. Define synchronizing tokens in the context of panic-mode error recovery.
22. What is the difference between %left and %right declarations in YACC?

Prepared as detailed study notes for MAKAUT [Link] Compiler Design — Module 3: Syntax Analysis [9L].
Content structured for conceptual clarity and exam preparation.