Chapter 4: Syntax Analysis

4.1 Introduction
Syntax Analysis, also called Parsing, is the second main
phase of a compiler, coming right after Lexical Analysis.
The lexical analyzer divides the source program into a
sequence of tokens, and the parser’s job is to check how
these tokens form valid statements according to the
grammar rules of the programming language.
The syntax analyzer verifies whether the sequence of
tokens is arranged in a structure that follows the rules of
the language’s grammar. It constructs a hierarchical
representation known as a parse tree (or syntax tree) that
shows how the source program is built from its smaller
components.
Purpose of Syntax Analysis
1. Syntax Verification:
The parser checks that tokens form grammatically
valid sentences.
Example: if (x > 0) y = 5; is valid, while if x
> 0) y = 5; is not.
2. Structure Building:
It constructs a tree-like representation that explains
how different parts of the source program are
combined.
 3. Error Reporting:
It detects syntax errors and gives helpful error
messages to locate them easily.
4. Basis for Semantic Analysis:
The parse tree produced in this phase serves as input
for the semantic analyzer. It helps understand
meaning and relationships between language
components.
Input and Output of Syntax Analysis
Input: The parser receives a stream of tokens from the
lexical analyzer such as identifiers, keywords, operators,
and delimiters.
Output: The parser produces a parse tree that shows the
syntactic structure of the program according to grammar
rules.
For example, if the input is id + id * id, the parser
produces a tree where multiplication is performed before
addition, reflecting operator precedence.
Role of Grammar
The grammar defines the structure of a programming
language. It specifies how tokens and smaller components
combine to form larger statements and expressions.
A Context-Free Grammar (CFG) is commonly used in
compilers because it can represent nested and recursive
structures that occur frequently in programming
languages.
Example grammar for arithmetic expressions:
E → E + T | T
T → T * F | F
F → (E) | id

This means an expression (E) may be an expression

followed by + and a term, or just a term. Similarly, a term
(T) may include multiplication or a single factor.
Importance of Syntax Analysis
1. It ensures that the program follows the correct syntax
rules before moving to the next phase.
2. It helps detect programmer errors early in
compilation.
3. It serves as a bridge between lexical and semantic
analysis.
4. It provides the structural foundation for later
compiler stages like code generation and
optimization.
Example
For a program statement like a = b + c * d;
The lexical analyzer produces tokens: id(a), =,
id(b), +, id(c), *, id(d), ;
The parser then constructs the tree:
=
/ \
a +
/ \
 b *
/ \
c d

This shows that multiplication has higher precedence than

addition.

4.2 The Role of the Parser

The parser is one of the most important components of a
compiler. Its main responsibility is to analyze the
sequence of tokens produced by the lexical analyzer and
determine whether they form a syntactically correct
program according to the grammar of the programming
language.
The parser not only checks for syntax errors but also
builds a structural representation of the program that can
be used in later compiler phases. This structure is usually
in the form of a parse tree or an abstract syntax tree
(AST).
In simple words, the parser acts as a bridge between the
lexical analyzer and the semantic analyzer, ensuring
that the program’s structure is valid before meaning or
behavior is checked.
Main Functions of the Parser
1. To Check Syntax:
The parser ensures that the tokens appear in an order
 that matches the grammar of the programming
language. It verifies if statements, expressions, loops,
and function calls are written correctly.
Example:
o Valid: while (x < 10) { x = x + 1; }

o Invalid: while x < 10) { x = x + 1; }

The parser detects such mismatched parentheses

or misplaced symbols.
2. To Build a Parse Tree:
The parser constructs a tree structure that represents
how tokens relate to each other according to grammar
rules. This tree clearly shows which symbols and
operators combine to form valid statements.
3. To Report and Recover from Errors:
The parser identifies syntax errors and tries to
recover from them to continue parsing the remaining
part of the program. This helps the compiler detect
multiple errors in one compilation attempt instead of
stopping at the first one.
4. To Provide Input for Semantic Analysis:
Once the syntactic structure is verified, the parser
sends the parse tree (or syntax tree) to the next
compiler phase, which performs semantic checks
such as type compatibility and scope validation.
5. To Guide Intermediate Code Generation:
The parser’s output is used to produce intermediate
representations like three-address code, which
simplifies optimization and machine code generation
later.
How the Parser Works
The parser reads one token at a time from the lexical
analyzer and tries to match it against the grammar rules of
the language.
There are two general strategies for doing this:
 Top-Down Parsing: Starts from the root (the start
symbol) of the grammar and tries to predict the
structure of the input. Examples include recursive-
descent parsing and predictive parsing.
 Bottom-Up Parsing: Starts from the input tokens
and gradually reduces them to the start symbol.
Examples include shift-reduce parsing and LR
parsing.
Both methods aim to check whether the input tokens can
be generated by the grammar and to construct the parse
tree if they can.
Example
Consider this expression:
id + id * id

The parser needs to determine how this can be derived

using the grammar.
If the grammar is:
E → E + T | T
T → T * F | F
F → id
The parser must choose derivations that correctly handle
operator precedence. It should recognize that
multiplication has higher precedence, so the structure
must group id * id first before applying the addition.
The corresponding parse tree will be:
E
/ \
E +
/ \
T F
/ \
F *
id id

This tree correctly shows that id * id is evaluated

before id + ....
Parser and Grammar Relationship
The parser’s behavior is completely dependent on the
grammar of the language.
A poorly designed grammar may lead to ambiguity or
make parsing difficult.
Hence, grammars are often rewritten to make them
suitable for efficient parsing.
For example, left-recursive grammars cause problems in
top-down parsers, so they are converted into right-
recursive or non-recursive forms.
Types of Parsers
 1. Top-Down Parsers:
o Start constructing the parse tree from the root

(start symbol) and move toward the leaves

(tokens).
o Predict which production to apply by looking at

the current token.

o Examples: Recursive-Descent Parser,

Predictive Parser (LL Parser).

2. Bottom-Up Parsers:
o Start from the input tokens and attempt to reduce

them step by step until the start symbol is

reached.
o Construct the parse tree from leaves to root.

o Examples: Shift-Reduce Parser, LR Parser,

LALR Parser.
Both kinds of parsers serve the same purpose but use
different strategies depending on grammar type and
implementation complexity.
Error Handling in Parsing
A parser must be capable of handling unexpected or
incorrect input gracefully.
When an error occurs, it should not abruptly stop
compilation; instead, it should attempt error recovery to
detect more errors in one run.
Common error-recovery techniques include:
 Panic mode recovery: Skip tokens until a
synchronizing token (like ; or }) is found.
  Phrase-level recovery: Insert or delete tokens to
repair the input.
 Error productions: Add special grammar rules to
handle known mistakes.
 Global correction: Attempt to make minimal
changes to input to make it valid.
Importance of the Parser in Compiler Design
 It validates the syntactic correctness of the program.
 It ensures that subsequent phases operate on a well-
structured input.
 It provides meaningful error messages to assist
programmers.
 It generates structural representations essential for
optimization and code generation.

4.3 Context-Free Grammars

A Context-Free Grammar (CFG) is a formal way to
describe the syntactic structure of a programming
language. It tells how smaller pieces (like tokens)
combine to form valid expressions, statements, and
programs.
Every modern compiler relies on CFGs because they can
represent the nested and hierarchical structure of
programming languages naturally — for example,
expressions inside parentheses, loops inside functions, or
functions inside classes.
What is a Grammar?
A grammar is a set of rules that defines how strings
(sentences or statements) can be formed in a language.
Just as English grammar defines how words form correct
sentences, programming language grammars define how
symbols form valid programs.
A grammar provides the syntactic blueprint of a
language — the structure that the parser checks.

Formal Definition of a Context-Free Grammar

A context-free grammar (CFG) is defined as a 4-tuple:
G = (V, T, P, S)
where
 V → a finite set of non-terminal symbols (also
called variables).
 T → a finite set of terminal symbols (tokens or
actual words of the language).
 P → a finite set of productions (or production rules).
 S → a start symbol, which is one of the non-
terminals.
Each production rule in P has the form:
A → α,
where
  A is a non-terminal symbol, and
 α is a sequence of terminals and/or non-terminals
(possibly empty).
The idea is: the non-terminal A can be replaced by α
whenever A appears in a sentence being derived.

Example of a Simple Grammar

Let’s define a small grammar for arithmetic expressions:
E → E + T | T
T → T * F | F
F → (E) | id

Here,
 Terminals (T): id, +, *, (, )
 Non-terminals (V): E, T, F
 Start symbol (S): E
 Productions (P): the three rules above
This grammar says that:
 An expression E can be another expression plus a
term (E + T) or simply a term (T).
 A term T can be another term multiplied by a factor
(T * F) or just a factor (F).
 A factor F can be an identifier (id) or a parenthesized
expression (E).
This structure correctly defines operator precedence —
multiplication has higher precedence than addition, and
parentheses can override it.

Derivations in a Grammar
A derivation is a sequence of rule applications that show
how the start symbol generates a string of terminals.
Derivations can be done in two main ways: leftmost and
rightmost.
1. Leftmost Derivation:
Always replace the leftmost non-terminal first in
each step.
Example: Using the grammar above, derive id + id
* id

Step 1: E
Step 2: E → E + T
Step 3: E → T + T
Step 4: T → F (for the first T)
Step 5: F → id, giving id + T
Step 6: T → T * F
Step 7: T → F * F
Step 8: F → id and F → id
Final string: id + id * id
2. Rightmost Derivation:
Always replace the rightmost non-terminal first.
 The sequence of steps may differ, but the final string
is the same.
Both derivations lead to the same string if the grammar is
unambiguous, but the intermediate steps may differ.

Sentential Form
A sentential form is any string of terminals and non-
terminals that can appear at some stage during a
derivation.
 The derivation starts with the start symbol (S).
 Intermediate results are sentential forms.
 The derivation ends when only terminals remain.
Example using the same grammar:

⇒
E

⇒
E + T

⇒
T + T

⇒
F + T

⇒
id + T

⇒
id + T * F

⇒
id + F * F
id + id * id

Here, strings like E + T, T + T, F + T are sentential

forms.
Language Generated by a Grammar
The language generated by a grammar G (written as
L(G)) is the set of all terminal strings that can be derived
from the start symbol using the grammar rules.

L(G) = { w | S ⇒* w, w ∈ T* }
Formally,

where ⇒* means “derives in zero or more steps.”

Example:
For the arithmetic grammar above,
L(G) = { id, id + id, id * id, id + id * id, (id + id) * id, ... }
It represents all possible valid arithmetic expressions
formed by the grammar rules.

Recursive Nature of CFGs

CFGs are naturally recursive because they often define a
symbol in terms of itself.
For instance,
E → E + T | T

means that an expression can contain another expression.

This recursive property allows CFGs to describe nested
constructs such as:
 expressions within parentheses,
 nested function calls,
 or nested blocks in programming languages.
Example:
if (x > 0)
if (y > 0) z = 1;

Such nested structures can easily be represented using

recursive grammar rules.

Left and Right Recursion

A grammar is said to be left-recursive if a non-terminal
calls itself immediately on the left side of its production.
Example:
E → E + T | T
Here, E appears on the leftmost side of its own definition
— hence, it’s left-recursive.
A grammar is right-recursive if recursion occurs on the
right side of the production:
E → T + E | T

Left recursion causes problems for top-down parsers

(like recursive-descent parsers), because they may enter
infinite recursion.
To fix this, left recursion is converted to right recursion or
removed using special transformations.
Example (Removing left recursion):
E → T E'
E' → + T E' | ε
This new form avoids left recursion and is suitable for
predictive parsers.

Parse Trees (or Derivation Trees)

A parse tree is a tree representation that shows how a
string (program statement or expression) is derived from
the start symbol according to grammar rules.
It is a visual form of derivation, showing which
grammar rules are used and in what order.
Each node in the tree represents a grammar symbol, and
each interior node corresponds to a production rule. The
leaves of the tree are terminals (tokens), which together
form the final string.
Structure of a Parse Tree

1. The root of the tree is the start symbol (S) of the

grammar.
2. Each internal node represents a non-terminal
symbol.
3. Each leaf node represents a terminal symbol.
4. The children of any node correspond to the right-
hand side of a production rule used for that non-
terminal.
5. Reading all leaf nodes from left to right gives the
final sentence (the derived string).
Example

Consider the grammar:

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

and the input string:

id + id * id

The parse tree is constructed as follows:

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

Reading the leaf nodes from left to right gives the original
input string:
id + id * id
This tree clearly shows that the * operation is evaluated
before +, because multiplication occurs lower in the tree,
confirming operator precedence.

Derivation vs Parse Tree

  A derivation is a step-by-step sequence of applying
grammar rules (a textual process).
 A parse tree is a visual or structural representation of
the same derivation.
Both represent the same syntactic structure, but a parse
tree is easier for the compiler to analyze later (for
semantic checking or code generation).

Leftmost and Rightmost Derivations in Parse

Trees
Even though the sequence of derivations may differ
(leftmost or rightmost), both can lead to the same parse
tree if the grammar is unambiguous.
However, if the grammar is ambiguous, multiple parse
trees can be formed for the same input string, leading to
different interpretations.

Ambiguity in Grammars
A grammar is called ambiguous if there exists at least
one string that can have more than one parse tree (or
more than one leftmost or rightmost derivation).
Ambiguity means that the grammar allows more than one
possible structure for the same input. This can create
confusion during parsing, since the compiler wouldn’t
know which interpretation to follow.
Example of Ambiguity

Consider this grammar:

E → E + E | E * E | (E) | id

Now for the input string:

id + id * id

We can derive it in two different ways:

1. Interpretation 1 (Addition before Multiplication):
E → E + E
→ id + E
→ id + E * E
→ id + id * id

2. Interpretation 2 (Multiplication before Addition):

E → E * E
→ E + E * E
→ id + id * id

These two derivations produce two different parse trees

— one where + is the main operation, and one where * is
the main operation.
This makes the grammar ambiguous.

Why Ambiguity Is a Problem

1. Multiple Interpretations:
The same program or expression can have different
 meanings, which is unacceptable in programming
languages.
2. Compiler Confusion:
The parser would not know which parse tree to
choose, causing unpredictable results.
3. Optimization Issues:
Optimizations rely on a clear structure. Ambiguous
grammars make it impossible to apply consistent
transformations.
Therefore, grammars used in compilers must be
unambiguous.

Removing Ambiguity
Ambiguity can often be removed by rewriting grammar
rules so that operator precedence and associativity are
explicit.
Example: Arithmetic Expressions

Ambiguous grammar:
E → E + E | E * E | (E) | id

Unambiguous grammar:
E → E + T | T
T → T * F | F
F → (E) | id

Here:
  Multiplication (*) has higher precedence than
addition (+).
 Parentheses can override precedence.
 The structure ensures a unique parse tree for every
valid expression.
Example of Associativity

For left-associative operators like addition or subtraction,

the grammar ensures that the operation groups from left
to right:
E → E + T | T

This allows a + b + c to be interpreted as (a + b) +

c, which is correct.

Simplifying and Refining Grammars

Sometimes grammars are written in ways that are
convenient for humans but not efficient for parsers.
They can be simplified by removing unnecessary
complexity, such as:
1. Removing Useless Symbols:
Non-terminals that never produce any terminals can
be removed.
2. Removing Unit Productions:
Rules like A → B that only redirect to another non-
terminal can be replaced by directly substituting B’s
productions.
 3. Eliminating Null Productions:
Rules like A → ε (which produce the empty string)
can be replaced by alternate rules, unless empty
strings are necessary.
4. Eliminating Left Recursion:
As seen earlier, left recursion is replaced with right
recursion to make grammars suitable for top-down
parsers.

Use of CFGs in Compiler Design

1. Language Definition:
CFGs define the syntax of programming languages
formally.
2. Parser Construction:
Parsers (like LL or LR) use CFGs to check whether
input code follows language syntax.
3. Error Detection:
Using CFGs, parsers can detect syntactic errors
precisely and generate helpful error messages.
4. Intermediate Representation:
The parse tree or abstract syntax tree generated from
CFGs serves as the foundation for semantic analysis
and code generation.
4.4 Top-Down Parsing
Top-down parsing is one of the two main strategies used
to analyze the structure of a program. It starts from the
top (the start symbol of the grammar) and tries to
derive the input string by repeatedly expanding non-
terminals using grammar rules.
In other words, top-down parsing begins with the root of
the parse tree and builds it downward, choosing
productions that could generate the sequence of tokens
provided by the lexical analyzer.
The term “top-down” refers to this direction of tree
construction — from the start symbol to the terminals.

Basic Idea
A top-down parser tries to find a leftmost derivation of
the input string.
That means it starts from the start symbol S, chooses one
of its productions, replaces non-terminals step by step,
and continues until it generates a sequence of terminals
that matches the input.
If the wrong production is chosen, the parser may
backtrack and try another one — this is called
backtracking parsing.
The parser stops when:
 all input tokens are successfully consumed, and
 the start symbol is completely reduced to those
tokens.
If this happens, the input is syntactically correct.
If not, the parser reports a syntax error.

Example to Illustrate Top-Down Parsing

Let’s consider this small grammar:
S → a A b
A → c | ε

and an input string:

a c b

Step 1: Start with S

Step 2: Expand S → a A b
Step 3: Match a in input → success
Step 4: Now parse A
A → c works because the next input is c
Step 5: Match c
Step 6: Match final b
All input tokens are matched successfully → parsing
successful.
If the input were a b, the parser would instead choose A
→ ε, which also leads to success.
Thus, this grammar accepts both a b and a c b.
This example shows how top-down parsing predicts
which production to use and builds the tree downward.
Top-Down Parsing Process
1. Start from the start symbol of the grammar.
2. Choose a production rule that could produce the next
expected token.
3. Replace the non-terminal with the right-hand side of
the chosen rule.
4. Match the next input symbol.
5. Continue until the entire input is consumed.
If no rule can produce the expected token, or if the input
cannot be matched, an error is reported.

Advantages of Top-Down Parsing

1. Simple and Intuitive:
It follows the same reasoning a human would use
when reading code from top to bottom.
2. Builds Parse Tree Directly:
It constructs the parse tree in the same order as the
program’s syntactic structure.
3. Predictive in Nature:
For some grammars, it can choose the correct
production without backtracking.
4. Good for Small and Well-Defined Grammars:
Particularly useful for languages or expressions with
limited ambiguity.

Disadvantages of Top-Down Parsing

 1. Backtracking Can Be Expensive:
In many grammars, the parser might need to try
multiple alternatives (productions), leading to
inefficiency.
2. Cannot Handle Left Recursion:
A top-down parser goes into infinite recursion for
grammars like
E → E + T | T.
Therefore, such grammars must be rewritten before
parsing.
3. Limited to Predictive Grammars:
Only grammars that allow easy prediction of which
rule to choose (called LL grammars) can be parsed
efficiently.
4. Not Suitable for All Languages:
Some complex languages require bottom-up parsing
(like LR parsing), which handles a broader class of
grammars.

Relation to Parse Tree Construction

In top-down parsing, the parser starts building the parse
tree from the start symbol (root) and keeps expanding
the non-terminals downward until the tree’s leaves
correspond exactly to the tokens in the input.
Example (using the grammar above and input a c b):
S
/|\
 a A b
|
c

This structure grows downward, hence the term “top-

down.”

4.4 Recursive-Descent Parsing

Recursive-Descent Parsing is one of the simplest and
most intuitive methods of implementing top-down
parsing.
It directly uses the structure of the grammar to create a set
of recursive procedures (or functions), one for each
non-terminal in the grammar.
Each function in the parser tries to recognize and process
a particular non-terminal by calling other functions for the
non-terminals that appear on the right-hand side of its
productions.
Hence, the name “recursive-descent” — because the
parser descends recursively through the grammar rules.

Basic Concept
Suppose we have a grammar with several non-terminals.
For each non-terminal, we write a procedure (function)
that:
  checks which production rule to apply,
 matches tokens from the input, and
 calls other functions for the remaining non-terminals.
If the input matches the grammar rules exactly, the
parsing succeeds. Otherwise, an error is reported.
Each procedure consumes some part of the input and
returns when the part it represents has been successfully
parsed.

Example Grammar
Let us take a simple grammar:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → (E) | id

This grammar defines arithmetic expressions with

addition and multiplication operators and uses right
recursion (no left recursion), so it is suitable for top-down
parsing.

How Recursive-Descent Parser Works

1. The parser begins with the start symbol, here E, so
the function E() is called first.
 2. E() will call T(), which handles terms, and E'() for
further addition operations.
3. T() will call F() to handle factors, and T'() for
further multiplications.
4. Each function will match the input tokens step by
step and return once its non-terminal is completely
recognized.
5. If any mismatch occurs between expected and actual
tokens, an error is reported.
Step-by-Step Example
Let’s parse the input:
id + id * id

Step 1: Start with E()

 E() calls T()
 T() calls F()
 F() matches id
 Then T() calls T'() → next token is +, not *, so
return
 Back to E(), it calls E'()
Step 2: Now in E'()
 nextToken == '+', so match it
 Call T() again to parse the next term
Step 3: Inside the new T()
 T() calls F(), which matches id
  Then T() calls T'()
 Now nextToken == '*', so match it and call F()
again
 F() matches the final id
 T'() is called again, but no more *, so return

Step 4: E'() is called again after the term, no more +, so

return.
All input is successfully matched, and the parse is
successful.

Parse Tree for the Example

The resulting parse tree for id + id * id is:
E
/ \
T E'
/ \ \
F T' + T E'
| | / \
e id F T'
| \
id * F
|
id

The tree shows that multiplication (*) is evaluated before

addition (+), matching the operator precedence.
Advantages of Recursive-Descent Parsing
1. Easy to Implement:
Each non-terminal corresponds to one function, so
the structure of the grammar and parser match
directly.
2. Readable and Modular:
The code is clear, and each function has a single
responsibility.
3. Good for Simple Grammars:
Works very well for small, unambiguous grammars
that are free of left recursion.
4. Error Reporting:
Errors can be detected early and reported clearly with
specific function and position details.

Limitations of Recursive-Descent Parsing

1. Left Recursion Problem:
Grammars like E → E + T | T cause infinite
recursion. Such grammars must be rewritten.
2. Backtracking Issue:
For grammars where multiple productions start
similarly, the parser might need to backtrack, which
can be inefficient.
3. Grammar Restrictions:
It only works for grammars that are LL(1) —
meaning they can be parsed from Left-to-right,
 producing a Leftmost derivation, using 1 token
lookahead.
4. Complex for Large Grammars:
For very large programming languages, writing one
recursive function per non-terminal becomes tedious
and error-prone.

How to Handle Backtracking

Some recursive-descent parsers use backtracking:
If one production fails to match, the parser goes back and
tries another one.
However, this can become very slow.
For example, consider the grammar:
S → a A | a B
A → c
B → d

When parsing input a d, the parser might first try S → a

A, fail, and then go back to try S → a B.
This is backtracking.
To avoid it, we use predictive parsing — which chooses
the correct production using lookahead (without trial and
error).

4.4 Predictive Parsing

Predictive Parsing is an advanced and more efficient
version of top-down parsing.
It removes the need for backtracking, which was a major
limitation in recursive-descent parsing.
A predictive parser can predict which production rule to
use based on the next input token, hence the name.
It is designed for LL(1) grammars, meaning:
 it scans the input Left to right (first L),
 constructs a Leftmost derivation (second L),
 and uses 1 token of lookahead (1) to make parsing
decisions.
Predictive parsing can be implemented in two main ways:
1. Recursive Predictive Parser – using a set of
recursive functions (like improved recursive-descent
parsing without backtracking).
2. Non-Recursive Predictive Parser (Table-Driven) –
using a parsing table and an explicit stack
(implemented iteratively).

Goal of Predictive Parsing

The main goal of predictive parsing is to decide which
production rule to apply without trying all alternatives.
It does this by looking ahead at the next input token and
using two important sets — FIRST and FOLLOW.
These sets help determine which production to choose so
that parsing proceeds deterministically (without
guessing).

Eliminating Left Recursion Before Predictive

Parsing
Predictive parsing only works on grammars that are free
from left recursion.
So before building a predictive parser, any left-recursive
grammar must be rewritten.
Example of removing left recursion:
Left-recursive grammar:
E → E + T | T

After elimination:
E → T E'
E' → + T E' | ε

This new form is suitable for predictive parsing.

Understanding FIRST and FOLLOW Sets

FIRST Set

The FIRST set of a grammar symbol is the set of

terminals that can appear first in some string derived
from that symbol.
Rules to find FIRST:
1. If X is a terminal, then FIRST(X) = { X }.
2. If X is a non-terminal and has a production X → Y₁
Y₂ Y₃..., then:
o Add FIRST(Y₁) to FIRST(X).

o If Y₁ can produce ε (epsilon), then include

FIRST(Y₂), and so on.

3. If X can derive ε (the empty string), include ε in
FIRST(X).
Example:
E → T E'
T → F T'
F → (E) | id

Then:
FIRST(F) = { (, id }
FIRST(T) = { (, id }
FIRST(E) = { (, id }

All three have the same FIRST sets because each starts
with either an identifier or a parenthesis.

FOLLOW Set

The FOLLOW set of a non-terminal is the set of

terminals that can appear immediately to the right of that
non-terminal in some sentential form.
Rules to find FOLLOW:
 1. Place $ (end of input marker) in FOLLOW(S), where
S is the start symbol.
2. If there is a production A → αBβ, then add FIRST(β)
(except ε) to FOLLOW(B).

⇒ ε, then add FOLLOW(A) to FOLLOW(B).

3. If there is a production A → αB or A → αBβ where β

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

Compute FOLLOW sets:

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

These sets tell us what can legally appear after each non-
terminal during parsing.

Building a Predictive Parsing Table

Once the FIRST and FOLLOW sets are known, we can
build a predictive parsing table M[A, a], where:
 A = non-terminal (row)
  a = terminal (column)
The table tells which production to use when the current
non-terminal is A and the next input symbol is a.
Construction Rules:
1. For each production A → α
o For each terminal a in FIRST(α), add A → α to

2. If ε ∈ FIRST(α), then for each terminal b in

M[A, a].

3. If ε ∈ FIRST(α) and $ ∈ FOLLOW(A), add A →

FOLLOW(A), add A → α to M[A, b].

αtoM[A, $]`.
If any cell in the table gets more than one entry, the
grammar is not LL(1) (not suitable for predictive
parsing).

Example: Predictive Parsing Table

Using our arithmetic grammar:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → (E) | id

We already have:
FIRST(E) = { (, id }
FIRST(E') = { +, ε }
FIRST(T) = { (, id }
FIRST(T') = { *, ε }
FIRST(F) = { (, id }

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

Now the Predictive Parsing Table:

Non-Terminal Input Production Used
Symbol
E (, id E → T E'
E' + E' → + T E'
E' ), $ E' → ε
T (, id T → F T'
T' * T' → * F T'
T' +, ), $ T' → ε
F ( F → (E)
F id F → id
This table guides the parser to select the right production
using only the current input symbol.

Working of a Table-Driven Predictive Parser

A non-recursive predictive parser uses an explicit stack
instead of recursive function calls.
The stack holds the symbols that still need to be matched
or expanded.
Algorithm:
1. Push the start symbol and $ onto the stack.
2. Read the next token from the input.
3. Repeat until the stack is empty:
o If the top of the stack is a terminal and matches

the current input token → pop it and read the

next token.
o If the top of the stack is a non-terminal A, look

up the table entry M[A, a], where a is the

current input symbol.
 If an entry exists → replace A with the right-

hand side of the rule.

 If the entry is empty → syntax error.

4. If both stack and input are empty at the end, parsing

succeeds.

Example: Table-Driven Parsing

Input string:
id + id * id $

Initial stack:
$ E

Step-by-step actions (simplified):

 Ste Stack Input Action
p
1 $E id + id * id Use E → T E'
$
2 $ E' T id + id * id Use T → F T'
$
3 $ E' T' F id + id * id Use F → id
$
4 $ E' T' id id + id * id Match id
$
5 $ E' T' + id * id $ Use T' → ε
6 $ E' + id * id $ Use E' → + T
E'
7 $ E' T + + id * id $ Match +
8 $ E' T id * id $ Use T → F T'
9 $ E' T' F id * id $ Use F → id
10 $ E' T' id id * id $ Match id
11 $ E' T' * id $ Use T' → * F
T'
12 $ E' T' F * id $ Match *
*
13 $ E' T' F id $ Use F → id
14 $ E' T' id id $ Match id
15 $ E' T' $ Use T' → ε
16 $ E' $ Use E' → ε
17 $ $ Accept
Parsing successful — the input is syntactically correct.
Advantages of Predictive Parsing
1. No Backtracking:
Each decision is made using lookahead; no need to
retry alternatives.
2. Efficient and Fast:
Works in linear time for LL(1) grammars.
3. Simple Implementation:
The parsing table and algorithm are straightforward.
4. Clear Error Detection:
Empty table entries directly point to syntax errors.

Limitations of Predictive Parsing

1. Only for LL(1) Grammars:
It cannot handle left-recursive or highly ambiguous
grammars.
2. Complex for Real Programming Languages:
Large languages (like C or Java) often need more
powerful parsers (like LR parsers).
3. Requires Grammar Simplification:
Left recursion and left factoring must be removed
before building the parser.

Excellent — that’s the right approach again.

Section 4.5 – Bottom-Up Parsing is one of the most
important and conceptually rich parts of compiler design,
so writing it in four detailed parts will make it easier for
students to follow.
Here is how I’ll structure it:
 4.5 (Part 1): Introduction to bottom-up parsing and
basic concepts
 4.5 (Part 2): Reductions, handles, and shift-reduce
parsing mechanism
 4.5 (Part 3): Conflicts in shift-reduce parsing
(shift/reduce, reduce/reduce) and examples
 4.5 (Part 4): Operator-precedence parsing and
precedence handling
Let’s begin with 4.5 Part 1 — introduction and
fundamental idea.

4.5 Bottom-Up Parsing (Introduction and Basic

Concepts)
Bottom-up parsing is the second major strategy of
syntax analysis (the opposite of top-down parsing).
Instead of starting from the start symbol and predicting
what to generate, bottom-up parsing starts from the input
string and tries to reconstruct the start symbol by
reversing the derivation process.
In simple words:
Top-down parsing builds the parse tree from the root to
the leaves,
while bottom-up parsing builds it from the leaves to the
root.

Main Idea
Bottom-up parsing works by taking the input tokens and
reducing them step by step into higher-level grammar
symbols until the entire input reduces to the start symbol.
It tries to find the sequence of reductions that represent
the reverse of a rightmost derivation in the grammar.
Hence, bottom-up parsing constructs the rightmost
derivation in reverse order, which is why it is also
called shift-reduce parsing or rightmost derivation in
reverse.

Analogy
Think of bottom-up parsing like rebuilding a puzzle:
You start with small individual pieces (tokens) and keep
joining them according to the grammar rules until you
form the full picture (the start symbol).
In contrast, top-down parsing starts with the whole picture
and breaks it down into smaller parts.

How Bottom-Up Parsing Works

Bottom-up parsing continuously performs two main
operations:
1. Shifting:
Moves (or shifts) the next input token onto a stack.
2. Reducing:
Replaces a sequence of symbols on the top of the
stack (called a handle) with a single non-terminal
using a grammar rule.
These two actions repeat until:
 The entire input is consumed, and
 The stack contains only the start symbol (which
means successful parsing).
If no valid reduction can be made at some point, a syntax
error is reported.

Example Grammar
Consider this simple grammar:
E → E + T | T
T → T * F | F
F → (E) | id

And input string:

id + id * id
Bottom-up parsing will begin with this sequence of tokens
and repeatedly apply shift and reduce operations to reach
the start symbol E.

Parse Tree Perspective

In top-down parsing, we expand non-terminals
downward to match input tokens.
In bottom-up parsing, we combine tokens upward to form
non-terminals.
For the input id + id * id, bottom-up parsing starts
from the terminals:
id + id * id

and gradually combines them as:

id → F
F → T
T → E
E + id * id → E + T → E

ending at the start symbol E.

So, it constructs the same parse tree as top-down parsing,
but in the opposite direction.

Rightmost Derivation in Reverse

To understand this key idea, recall that in a rightmost
derivation, we always replace the rightmost non-
terminal first when expanding.
In bottom-up parsing, we reverse this process — we start
with the full input and repeatedly reduce the rightmost
substring that matches the right-hand side of a production.
This reduction sequence corresponds to performing the
rightmost derivation in reverse order.
Example:
E ⇒ E + T ⇒ E + T
* F ⇒ E + T * id
Rightmost Derivation:

Reverse of this process: id → F → T * F → T

→ E + T → E

That is how bottom-up parsing reconstructs the

derivation.

Key Terms in Bottom-Up Parsing

1. Handle:
A substring of the input that matches the right-hand
side of a grammar production and whose reduction
represents one step in the reverse of a rightmost
derivation.
2. Reduction:
The process of replacing a handle by the
 corresponding non-terminal (the left-hand side of the
rule).
3. Shift:
Moving the next input token onto the stack.
4. Accept:
The action that signifies the successful completion of
parsing when the start symbol is derived.
5. Error:
A condition when no valid handle or shift exists,
meaning the input cannot be parsed by the grammar.

Steps in Bottom-Up Parsing

1. Start with an empty stack and the input string
followed by $.
2. Repeat until input is fully parsed:
o Shift the next token from input onto the stack.

o Check if the top of the stack matches the right-

hand side of any grammar rule.

o If yes, reduce that part to the corresponding non-

terminal.
3. If, after all reductions, only the start symbol remains
on the stack and the input is $, parsing is successful.

Example Overview
Using the grammar:
E → E + T | T
T → T * F | F
F → id

Input: id + id * id
The parsing process (details in later parts) will look like
this:
Step Stack Input Action
1 (empty) id + id * id shift id
$
2 id + id * id $ reduce F → id
3 F + id * id $ reduce T → F
4 T + id * id $ reduce E → T
5 E + id * id $ shift +
6 E+ id * id $ shift id
7 E + id * id $ reduce F → id
8 E+F * id $ reduce T → F
9 E+T * id $ shift *
10 E + T * id $ shift id
11 E + T * $ reduce F → id
id
12 E + T * F $ reduce T → T *
F
13 E+T $ reduce E → E +
T
14 E $ accept
Parsing complete — input accepted.
Advantages of Bottom-Up Parsing
1. Can handle a larger class of grammars than top-
down parsing.
2. No need to eliminate left recursion — it can handle
left-recursive grammars naturally.
3. Efficient and deterministic when implemented
using LR techniques.
4. Suitable for complex programming languages used
in real compilers.

Disadvantages
1. Difficult to understand manually — process is less
intuitive than top-down parsing.
2. Parser generation tools (like YACC or Bison) are
often required.
3. More complex to implement because of the use of
stacks, parsing tables, and states.

4.5 Bottom-Up Parsing (Reductions, Handles, and

Shift-Reduce Parsing Mechanism)
What is Reduction?
A reduction is the process of replacing a substring of the
input (that matches the right-hand side of a grammar rule)
with the non-terminal on the left-hand side of that rule.
Each reduction step corresponds to one step in the
reverse of a rightmost derivation.
For example, if the grammar has:
E → E + T

and during parsing we find the substring E + T on the

stack,
we can reduce it to E.
Thus, reduction is like recognizing that “this piece of
input represents a higher-level construct.”

What is a Handle?
A handle is a substring of the input (or of the stack
contents) that matches the right-hand side of a grammar
rule and whose reduction represents one valid step in the
reverse of a rightmost derivation.
In simple terms:
 A handle is the part of the input that should be
reduced next.
 It represents a complete, valid unit (like an
expression, term, or factor) that can be collapsed into
a single non-terminal.
Finding handles is the key job of a bottom-up parser.

Formal Definition

If S ⇒ αAω ⇒ αβω is a rightmost derivation,

then the substring β in the sentential form αβω is called a
handle.
When we reduce β to A, we get the previous sentential
form αAω.

Example of Handles
Given grammar:
E → E + T | T
T → T * F | F
F → id

And input:
id + id * id

Possible handles (in reverse derivation steps):

1. id → F
2. F → T
3. T → E
4. id * id → T * F → T
5. E + T → E
Each handle corresponds to one reduction.
Detecting handles in the right order is how a bottom-up
parser works.

Operations in Bottom-Up Parsing

Bottom-up parsers perform four main operations: shift,
reduce, accept, and error.
1. Shift

Move (shift) the next input symbol from the input buffer
to the top of the stack.
It indicates that the parser has not yet seen enough
symbols to form a handle.
2. Reduce

When the top of the stack contains a handle, replace it by

the corresponding non-terminal using a grammar
production rule.
Example:
If stack top = E + T, and grammar has E → E + T,
then reduce that portion to E.
3. Accept

If the stack contains only the start symbol, and the input
is fully consumed (usually only $ remains), the parser
accepts the input as syntactically correct.
4. Error

If neither a valid shift nor a reduction is possible, the

parser reports a syntax error and may attempt recovery.

Shift-Reduce Parser
A shift-reduce parser is the simplest form of a bottom-
up parser.
It uses a stack to hold symbols and performs a sequence
of shifts and reductions to process the input.
At each step, the parser decides:
 whether to shift the next input symbol onto the stack,
or
 to reduce the top part of the stack using a production
rule.

Structure of a Shift-Reduce Parser

A shift-reduce parser uses:
1. Input Buffer:
Holds the remaining part of the input string (tokens
from the lexical analyzer).
2. Stack:
Holds grammar symbols that have been shifted or
reduced.
 3. Parsing Table or Logic:
Decides whether to shift, reduce, accept, or report an
error.
4. Output:
The sequence of reductions that lead from input to
start symbol.

Working Example of Shift-Reduce Parsing

Let’s use the same grammar:
E → E + T | T
T → T * F | F
F → id

and input string:

id + id * id $

We’ll show the sequence of shift and reduce actions.

Step Stack Input Action Rule
Applied
1 (empty) id + id * Shift
id $
2 id + id * id Reduce F → id
$
3 F + id * id Reduce T → F
$
4 T + id * id Reduce E → T
$
 5 E + id * id Shift
$
6 E+ id * id $ Shift
7 E + id * id $ Reduce F → id
8 E+F * id $ Reduce T → F
9 E+T * id $ Shift
10 E+T* id $ Shift
11 E+T* $ Reduce F → id
id
12 E+T*F $ Reduce T → T * F
13 E+T $ Reduce E → E + T
14 E $ Accept
Parsing successful.
The parser built the structure from the leaves (id) up to
the start symbol (E).

Key Observations from the Example

 The parser uses the stack to store partially processed
input.
 Shift moves tokens from input to stack until a
recognizable pattern (handle) forms.
 Reduce replaces the handle with a non-terminal.
 The order of reductions follows the reverse of a
rightmost derivation.
 When the entire input is reduced to the start symbol,
the parser accepts.
Implementation of Shift-Reduce Parsing
A typical shift-reduce parser uses a loop like this:
Initialize stack with $.
Repeat:
if (canReduce(stackTop)):
performReduction()
else if (canShift(nextInput)):
shiftInputToStack()
else if (stackTop == startSymbol and
input == $):
accept()
else:
error()

This logic ensures the parser continuously checks for

handles on the stack and processes tokens one by one.

4.5 Bottom-Up Parsing (Part 3 – Conflicts in Shift-

Reduce Parsing)
In this part, we will study one of the most critical aspects
of bottom-up parsing — conflicts that occur during the
shift-reduce parsing process.
While the shift-reduce parser is conceptually simple, it
often faces situations where the next action (shift or
reduce) is not clear.
These situations are called parsing conflicts.
1. What is a Conflict?
A conflict occurs when the parser encounters a situation
in which:
 It can perform more than one valid action (for
example, both shift and reduce), or
 It is uncertain which reduction rule to apply.
Conflicts usually arise because the grammar is
ambiguous or not suitable for the particular parsing
strategy being used.
There are mainly two kinds of conflicts:
1. Shift/Reduce Conflict
2. Reduce/Reduce Conflict

2. Shift/Reduce Conflict
A shift/reduce conflict happens when the parser cannot
decide whether to:
 Shift the next input symbol onto the stack, or
 Reduce the current symbols on the stack using a
grammar production.
In other words, the parser is unsure whether the handle is
complete or if more tokens should be shifted before
reducing.
Example of a Shift/Reduce Conflict

Consider this grammar:

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

and the input:

if E1 then if E2 then S1 else S2

At the position after S1, the parser sees the else token.
Now it has two possible actions:
 Reduce the inner if expr then stmt (treating it
as a complete statement), or
 Shift the else and associate it with the nearest
unmatched if.
Both seem valid — this is a shift/reduce conflict.

The Dangling Else Problem

This is the most famous example of shift/reduce conflict.

It arises because grammars for conditional statements
allow ambiguity in matching each else with an if.
In the example:
if E1 then if E2 then S1 else S2

Should the else be paired with the inner if or the outer

if?
Humans naturally pair it with the nearest unmatched if,
so the correct interpretation is:
if E1 then (if E2 then S1 else S2)

But for the parser, both interpretations are possible until

disambiguated.

How Compilers Handle This Conflict

1. Grammar Modification:
Redefine the grammar to explicitly state that each
else belongs to the nearest if.
For example:
2. stmt → matched_stmt | unmatched_stmt
3. matched_stmt → if expr then
matched_stmt else matched_stmt | other
4. unmatched_stmt → if expr then stmt | if
expr then matched_stmt else
unmatched_stmt

This version removes the ambiguity.

5. Parser Convention:
Many parser generators (like YACC or Bison)
automatically resolve this by shifting rather than
reducing —
i.e., they associate each else with the closest
unmatched if.
So, the shift action is preferred over reduce in such cases.
3. Reduce/Reduce Conflict
A reduce/reduce conflict occurs when the parser finds
that two or more different grammar rules could be applied
for reduction at the same time.
That means the top of the stack matches more than one
right-hand side of different productions.

Example of Reduce/Reduce Conflict

Consider this grammar:

S → A | B
A → x
B → x

and input:
x

When the parser sees x on the stack, both rules

A → x and B → x are valid reductions.

So, should it reduce using A → x or B → x?

Both are valid — hence, a reduce/reduce conflict.

Another Example
stmt → id | id := expr

and input:
id
Here again, id could be reduced to stmt directly (stmt
→ id),
or it could be part of a larger construct (id := expr).
At this point, the parser cannot decide — a
reduce/reduce conflict arises.

4. Why Do Conflicts Occur?

Conflicts arise mainly due to:
1. Ambiguous grammars — multiple parse trees
possible for the same input.
2. Grammar overlap — two or more rules can apply to
the same substring.
3. Incomplete lookahead — the parser does not have
enough tokens to disambiguate the situation.
4. Operator precedence issues — unclear rules about
which operator binds more tightly.

5. Ways to Handle Conflicts

(a) Rewrite the Grammar

Modify the grammar to eliminate ambiguities, left

recursion, or overlapping rules.
Example: replacing ambiguous if-else grammar with
matched/unmatched rules.
(b) Use Precedence and Associativity Rules

Define which operator has higher precedence and how

associativity should be handled.
For example:
 Multiplication * has higher precedence than addition
+.
 Operators like + and - are left-associative.
Such rules help the parser decide whether to shift or
reduce in ambiguous arithmetic expressions.
(c) Prefer Shift over Reduce

Parser generators (like YACC) usually resolve

shift/reduce conflicts by preferring shift,
because shifting often allows reading more tokens to
resolve the ambiguity.
(d) Prefer One Reduction

For reduce/reduce conflicts, parser generators usually

report an error or require user intervention to specify
which rule to prefer.

6. Detecting Conflicts
Conflicts are detected while building the parsing table
(especially in LR parsers).
When a table entry contains more than one possible action
(e.g., both a shift and a reduce), it indicates a shift/reduce
conflict.
When it contains two reductions, it’s a reduce/reduce
conflict.
Example (simplified view):
State Input Symbol Action
5 else shift or reduce (conflict)

This means the grammar or parser construction must be

refined.

7. Summary of Conflicts
Type Meaning Example Typical Solution
Parser can Prefer shift or
Dangling
Shift/Reduce either shift or rewrite
else
reduce grammar
Multiple Modify
Two
rules for grammar or
Reduce/Reduce reductions
same specify
possible
substring precedence

8. Importance in Compiler Design

Understanding and handling these conflicts is crucial
because:
  They directly affect parser correctness and
determinism.
 Unresolved conflicts lead to ambiguous syntax
trees.
 Properly resolving them ensures the parser behaves
consistently with the language’s grammar and
semantics.

4.5 Bottom-Up Parsing (Part 4 – Operator-

Precedence Parsing)
Operator-precedence parsing is a special type of
bottom-up parsing used mainly for arithmetic and
logical expressions where operators such as +, -, *, /, ^,
etc., have a natural hierarchy of precedence and
associativity.
This technique avoids the full complexity of LR parsing
but still handles many useful grammars effectively.
It works well when the grammar has clear precedence
relations among operators and does not contain
ambiguous or complicated productions.

1. Basic Idea of Operator-Precedence Parsing

The key concept is to assign precedence relations
between grammar symbols (usually operators) to
determine when to shift or reduce during parsing.
Instead of constructing complex parsing tables (as in LR
parsing), we create a simpler operator-precedence table,
which tells:
 when one symbol has lower precedence than another
→ shift
 when one symbol has higher precedence → reduce
The parser uses these relationships to decide what to do
next.

2. Grammar Requirements
An operator-precedence grammar must satisfy the
following conditions:
1. No epsilon (ε) productions.
(Every production must produce at least one terminal
symbol.)
2. No two adjacent non-terminals.
(This ensures clear precedence relations between
terminals.)
3. Operators must have clear precedence and
associativity.
If these conditions are met, we can define precedence
relations between terminals.

3. Operator-Precedence Relations
Three precedence relations are defined among terminals:
Symbol Meaning
a <· b a yields precedence to b — shift b onto the stack.
a has equal precedence to b — both are part of the
a =· b
same handle.
a takes precedence over b — reduce the handle
a >· b
before shifting b.

These symbols guide the parser on whether to shift or

reduce when two terminals are adjacent on the stack and
input.

4. Operator-Precedence Table Example

Let’s take this simple grammar for arithmetic expressions:
E → E + E | E * E | (E) | id

Operators:
 * has higher precedence than +
 Parentheses ( and ) control grouping
 Both + and * are left-associative
Now we define the precedence relations among the
terminals:
 id + * ( ) $
id >· >· >· >·
+<· >· <· <· >· >·
*<· >· >· <· >· >·
(<· <· <· <· =·
) >· >· >· >·
$<· <· <· <·

This table shows how each operator relates to the others:

 ( yields precedence to everything until it meets )
 * takes precedence over +
 Operands (id) have higher precedence over
subsequent operators

5. Steps of Operator-Precedence Parsing

Operator-precedence parsing uses a stack and an input
buffer, similar to shift-reduce parsing.
The parser decides whether to shift or reduce by looking
at the precedence relation between the top terminal on
the stack and the next input symbol.
Algorithm Steps

1. Push the end marker $ onto the stack.

2. Read tokens from input (also ending with $).
 3. Repeat until stack = $E$:
o Let a = topmost terminal on the stack

o Let b = next input symbol

o Find the relation between a and b using the

precedence table:
 If a <· b or a =· b, shift b (push onto

stack).
 If a >· b, reduce (pop symbols until a <·

relation is found).
 If no relation exists → syntax error.

4. When both stack and input contain only $, parsing

succeeds.

6. Example: Parsing id + id * id
Grammar:
E → E + E | E * E | (E) | id

Precedence: * > +, both left-associative.

Initial setup:
Stack: $
Input: id + id * id $

Step-by-Step Parsing Table

Step Stack Input Relation Action
1 $ id + id * <· Shift id
Step Stack Input Relation Action
id $
+ id * id id >·
2 $ id
$ +
Reduce id → E

+ id * id
3 $ E E <· + Shift +
$
4 $ E + id * id $ <· Shift id
id >·
5 $ E + id * id $
*
Reduce id → E

6 $ E + E * id $ + <· * Shift *

7 $ E + E * id $ <· Shift id
$ E + E * id >·
8 id
$
$
Reduce id → E

$ E + E * Reduce E * E
9 E
$ * >· $
→ E
Reduce E + E
10 $ E + E $ + >· $
→ E
11 $ E $ Accept

Parsing successful — expression is syntactically valid.

7. Constructing the Operator-Precedence Table

To build the precedence table systematically:
 1. List all terminals (operators and operands).
2. Determine precedence and associativity of each
operator.
o Example: * > +, and both are left-associative.

3. For each pair (a, b) of terminals:

o Assign <· if a yields precedence to b.

o Assign >· if a takes precedence over b.

o Assign =· if a and b belong to the same

subexpression (e.g., parentheses).

4. Fill in the table accordingly.
5. Leave blank entries where no valid relation exists
(those are syntax errors).

8. Operator Associativity
Operator-precedence parsing also depends on
associativity rules:
Associativity Example Meaning
a - b - Evaluate left to right: (a -
Left-Associative c
b) - c
Right- a ^ b ^ Evaluate right to left: a ^ (b
Associative c ^ c)

 Left-associative operators use > when the same

operator repeats.
 Right-associative operators use < when the same
operator repeats.
Example for ^ (right-associative):
a ^ b ^ c → a ^ (b ^ c)

means the parser must shift rather than reduce when

encountering another ^.

9. Advantages of Operator-Precedence Parsing

1. Simple to implement — no need for large parsing
tables or complex automata.
2. Fast and deterministic for expressions involving
operators.
3. Natural fit for arithmetic and logical expressions
where precedence rules are well-defined.
4. No need for grammar rewriting if precedence rules
are already known.

10. Limitations
1. Limited grammar scope — cannot handle all
context-free grammars.
2. Cannot handle ambiguous or nested constructs
like if-then-else.
3. No epsilon productions allowed.
4. Not used for full programming languages —
mainly used as part of larger parsers for expressions.
Excellent — we’ll now begin Section 4.6 – Introduction
to LR Parsing: Simple LR (SLR).
This is one of the most important and advanced sections
in Syntax Analysis, so we’ll divide it carefully into four
detailed parts for better understanding:

Structure Plan for Section 4.6 – Introduction to

LR Parsing: Simple LR (SLR)
 Part 1: Introduction to LR Parsing and Core
Concepts
 Part 2: LR(0) Items and The Canonical Collection of
LR(0) Items
 Part 3: Constructing SLR Parsing Tables
 Part 4: Example of SLR Parsing Process and
Advantages

Let’s begin with 4.6 (Part 1) – Introduction to LR

Parsing and Core Concepts

4.6 Introduction to LR Parsing: Simple LR

(SLR) (Part 1 – Basic Concepts)
1. What is LR Parsing?
LR parsing is a powerful bottom-up parsing method
that can handle a wide range of context-free grammars
efficiently and deterministically.
The term LR stands for:
 L → Left-to-right scanning of input
 R → Produces a Rightmost derivation in reverse
So, LR parsers read input from left to right and
reconstruct the rightmost derivation in reverse order —
exactly like bottom-up parsers, but with more systematic
control using state machines.
LR parsing is the most widely used parsing method in
modern compilers (for languages like C, Java, and
Python), because it is fast, accurate, and handles non-
trivial grammars.

2. Why LR Parsers Are Important

LR parsers can recognize virtually all programming
language constructs because:
 They handle left recursion naturally.
 They detect syntax errors early and precisely.
 They are deterministic (no backtracking or
guessing).
 They can be implemented automatically by parser
generators like YACC and Bison.

3. The Basic Idea of LR Parsing

The LR parser uses two main components:
1. A stack — to store grammar symbols and parsing
states.
2. A parsing table — to decide whether to shift,
reduce, accept, or signal an error.
The parser works like a finite automaton that recognizes
valid prefixes of the input string, augmented with rules for
grammar-based reductions.

4. Actions in an LR Parser
At each step, the parser looks at:
 The current state (on top of the stack), and
 The next input symbol (lookahead).
Then it consults the parsing table, which tells it what to
do:
1. Shift:
Push the input symbol and move to a new state.
2. Reduce:
Replace the handle on the stack with the
corresponding non-terminal (according to a grammar
rule).
3. Accept:
Input successfully parsed (stack and input form the
start symbol and $).
 4. Error:
No valid entry in the parsing table — syntax error.

5. Components of an LR Parser
An LR parser consists of:
1. Input Buffer:
Contains tokens from the lexical analyzer, ending
with $.
2. Stack:
Stores both grammar symbols and their
corresponding states.
Example:
3. Stack: [0 E 2 + 6 T 3]

Here, numbers like 0, 2, 6, 3 are states.

4. Parsing Table:
Divided into two parts:
o ACTION table – tells whether to shift, reduce,

accept, or error.
o GOTO table – tells which state to move to after

a reduction.
5. Parsing Algorithm:
Uses the stack and tables to guide parsing decisions.

6. Structure of the Parsing Table

The LR parsing table has two main parts:
 Current Input Action
State Symbol (Shift/Reduce/Accept/Error)
Non-terminal Next State (for GOTO)

Example (simplified view):

State id + * ( ) $ E T F
0 S5 S4 123
1 S6 Acc
2 R2 S7 R2 R2
3 R4 R4 R4 R4

Here:
 S5 = Shift and go to state 5
 R2 = Reduce using production 2
 Acc = Accept the input

7. Types of LR Parsers
There are several variants of LR parsers depending on
how powerful and complex they are:
Parser Type Description Power Complexity
SLR (Simple Basic, easy to Moderate Simple
LR) construct, uses
 Parser Type Description Power Complexity
FOLLOW sets
Canonical LR Full LR parser with 1-
Very High Complex
(LR(1)) token lookahead
LALR (Look- Optimized form of
High Efficient
Ahead LR) LR(1); smaller tables
CLR Same as LR(1) — Largest
Highest
(Canonical LR) most powerful form tables

We start with SLR (Simple LR) parsing — the easiest to

understand conceptually and suitable for many practical
grammars.

8. How LR Parsing Works (Conceptually)

LR parsing works as a state machine guided by grammar
rules.
1. Initially, the stack contains the starting state (0).
2. The parser reads the next input symbol.
3. The current state and input symbol determine an
action (Shift/Reduce/Accept/Error) from the table.
4. For Shift, it pushes the input symbol and new state
onto the stack.
5. For Reduce, it pops symbols corresponding to the
right-hand side of the rule, then pushes the left-hand
 side and transitions to a new state (via the GOTO
table).
6. The process repeats until the input is accepted or an
error occurs.

9. Example Overview (Conceptual)

Grammar:
E → E + T | T
T → T * F | F
F → (E) | id

Input:
id + id * id $

Parsing steps:
1. Start in state 0, read id.
2. Shift id and move to a new state.
3. Reduce id → F, then F → T.
4. Encounter +, shift it.
5. Continue similar steps until all input reduces to E.
(The detailed working with tables and states will be
shown in later parts.)

10. Advantages of LR Parsing

 1. Can handle all deterministic context-free
grammars (including left-recursive ones).
2. Detects errors early — as soon as an invalid prefix
appears.
3. Efficient — parsing is linear in time (O(n)).
4. Systematic construction — can be built by
algorithms or parser generators.
5. No backtracking — deterministic and reliable.

11. Limitations
1. Table construction is complex (especially for large
grammars).
2. Large tables in canonical LR make manual
construction hard.
3. Difficult to understand manually without tools like
YACC/Bison.
4. Grammar must be unambiguous and fit
deterministic parsing rules.

4.6 Introduction to LR Parsing: Simple LR (SLR)

(Part 2 – LR(0) Items and The Canonical Collection of
LR(0) Items)

1. What Are LR(0) Items?

An LR(0) item is a production rule of a grammar with a
dot (·) marking a position in its right-hand side.
The dot (·) represents how much of the production has
been seen or recognized so far.

Example

For a production:
E → E + T

The corresponding LR(0) items are:

1. [E → · E + T] → Nothing seen yet
2. [E → E · + T] → E recognized, + T remains
3. [E → E + · T] → E + recognized, T remains
4. [E → E + T ·] → Entire right-hand side seen
(ready for reduction)
Each position of the dot corresponds to a different state
of progress in parsing that production.

2. Purpose of LR(0) Items

Each LR(0) item represents a possible situation in the
parser —
what the parser has seen so far and what it expects next.
For example:
  [E → E + · T] means the parser has recognized E
+ and now expects something that can derive T.
 [E → E + T ·] means the parser has seen the entire
right-hand side and can now reduce it to E.
Thus, LR(0) items define the states of the LR parser.

3. Augmented Grammar
Before constructing LR(0) items, we always augment the
grammar.
This means adding a new start symbol and a new
production that derives the old start symbol.
If the original grammar is:
E → E + T | T

The augmented grammar becomes:

E' → E
E → E + T | T

The augmented grammar ensures that when the parser

reduces the entire input to E', it can accept the string.

4. Closure of Items
The closure of a set of LR(0) items** adds all the items
that represent what can come next** after a non-terminal
immediately following the dot.
Closure Algorithm

For a set of items I:

1. Start with all items in I.
2. For each item [A → α · B β] in I,
if B is a non-terminal,
add all items of the form [B → · γ] for every
production B → γ in the grammar.
3. Repeat until no more new items can be added.

Example

Given grammar:
E' → E
E → E + T | T
T → T * F | F
F → (E) | id

Start with:
I₀ = closure([E' → · E])

Now apply closure:

 Since the dot is before E, and E is a non-terminal,
add all productions of E with the dot at the beginning.
So:
I₀ = {
 [E' → · E],
[E → · E + T],
[E → · T],
[T → · T * F],
[T → · F],
[F → · (E)],
[F → · id]
}

This is the initial state of the LR(0) automaton.

5. The GOTO Function

The GOTO function tells us how to move from one state
to another when the parser recognizes a grammar
symbol (terminal or non-terminal).
If I is a set of items and X is a grammar symbol,
then:
GOTO(I, X)

is the closure of all items [A → α X · β] such that [A

→ α · X β] is in I.

In other words, when the parser sees symbol X next,

the dot moves one step to the right past X,
and we take the closure of all those new items.

Example of GOTO

If:
I = {[E → E · + T], [E → E · * F]}

and the parser sees +,

then:
GOTO(I, +) = closure([E → E + · T])

This new set of items represents the new state of the

parser after recognizing +.

6. Building the Canonical Collection of LR(0)

Items
The Canonical Collection is the complete set of all
unique item sets (states) that can be reached through
GOTO transitions.

Algorithm to Build Canonical Collection

1. Start with:
2. I₀ = closure([S' → · S])

where S' is the new start symbol.

3. For each item set I and each grammar symbol X
(terminal or non-terminal):
o Compute GOTO(I, X)

o If it produces a new set of items, add it to the

collection.
4. Repeat until no new item sets can be added.
Each unique item set corresponds to a state in the LR
parsing automaton.

Example of Canonical Collection (Simplified)

For the grammar:

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

You’ll get item sets like:

I₀: [E' → · E], [E → · E + T], [E → ·
T], ...
I₁: [E' → E ·], [E → E · + T], ...
I₂: [E → T ·], [T → T · * F], ...
I₃: [T → F ·], ...
...

Each I₀, I₁, I₂, etc., is a state in the parsing automaton.

7. Constructing the LR(0) Automaton

Once all the item sets (states) are found using closure and
goto:
 Each item set becomes a state.
 Each GOTO(I, X) defines a transition from one
state to another.
This automaton recognizes viable prefixes — prefixes of
the input that can appear on the parser’s stack at some
stage of parsing.

Example of a Transition
I₀ --E--> I₁
I₀ --T--> I₂
I₂ --*--> I₃
I₁ --+--> I₄

These transitions form the DFA (Deterministic Finite

Automaton) of LR parsing states.

8. Importance of Canonical Collection

The Canonical Collection of LR(0) items is the
foundation for constructing:
 The ACTION table (for Shift, Reduce, Accept,
Error), and
 The GOTO table (for state transitions on non-
terminals).
Each item set defines how the parser behaves in a certain
situation,
and all possible item sets together define the entire
parser’s behavior.
4.6 Introduction to LR Parsing: Simple LR (SLR)
(Part 3 – Constructing SLR Parsing Tables)
In the previous part, we learned how to construct LR(0)
items and form their Canonical Collection, which
together define all possible states of an LR parser.
Now, in this part, we’ll learn how to use these states to
build the actual SLR (Simple LR) Parsing Table — the
key structure that guides the parser to perform shift,
reduce, accept, or error actions.

1. What Is an SLR Parsing Table?

The SLR (Simple LR) parsing table is a simplified
version of a full LR(1) parsing table.
It tells the parser what action to take based on:
 The current state (from the stack), and
 The next input symbol (lookahead).
The SLR table is divided into two main parts:
Table Part Purpose
ACTION For terminals — specifies whether to shift,
Table reduce, accept, or error
For non-terminals — specifies which state to go
GOTO Table
to after a reduction
2. Structure of the SLR Parsing Table
Input
Non-
State Symbols ACTION GOTO
terminals
(terminals)
id, +, *, (, ), Shift/Reduce/Accept/ New
0 E, T, F
$ Error State

Each cell in the table specifies an action:

 Sₙ → Shift and go to state n
 Rₖ → Reduce using production k
 Acc → Accept (if parsing completed)
 Blank → Error (invalid move)

3. Steps to Construct an SLR Parsing Table

Let’s go step by step.

Step 1: Compute LR(0) Item Sets

We already know how to build these from closure and

goto functions.
Each item set becomes one state of the LR parser.
Step 2: Number the Item Sets

Assign numbers (0, 1, 2, …) to each LR(0) item set, as

they will represent states in the table.

Step 3: Compute FIRST and FOLLOW Sets

These are needed to determine reduce actions in the

table.
 FIRST(X): terminals that begin strings derived from
X
 FOLLOW(X): terminals that can appear
immediately after X in sentential forms
For example, for the grammar:
E' → E
E → E + T | T
T → T * F | F
F → (E) | id

We have:
FIRST(F) = { (, id }
FIRST(T) = { (, id }
FIRST(E) = { (, id }

FOLLOW(E) = { ), $ }
FOLLOW(E') = { ), $ }
FOLLOW(T) = { +, ), $ }
FOLLOW(F) = { *, +, ), $ }
Step 4: Fill the ACTION and GOTO Entries

We now use the item sets and grammar to fill the parsing
table according to a fixed set of rules.

4. Rules for Constructing the SLR Table

For each item set (state) Iᵢ:
(a) Shift Rule

If the item [A → α · a β] is in state Iᵢ,

and a is a terminal, and
GOTO(Iᵢ, a) = Iⱼ,
then:
ACTION[i, a] = shift j
(b) Reduce Rule

If the item [A → α ·] is in state Iᵢ (dot at the end),

then for every terminal a in FOLLOW(A):
ACTION[i, a] = reduce A → α
(c) Accept Rule

If [S' → S ·] is in state Iᵢ,

then:
ACTION[i, $] = accept
(d) GOTO Rule

If GOTO(Iᵢ, A) = Iⱼ,
and A is a non-terminal, then:
GOTO[i, A] = j

All other cells are errors.

5. Example: Building an SLR Table (Step-by-Step)

Let’s use the simple grammar:
E' → E
E → E + T | T
T → T * F | F
F → (E) | id

Step 1: Build Item Sets

We already have from Part 2 (simplified view):

I₀: [E' → · E], [E → · E + T], [E → · T],
[T → · T * F], [T → · F], [F → · (E)], [F →
· id]
I₁: [E' → E ·], [E → E · + T]
I₂: [E → T ·], [T → T · * F]
I₃: [T → F ·]
I₄: [F → ( · E )], [E → · E + T], [E → ·
T], ...
I₅: [F → id ·]
...
Each item set corresponds to a state.

Step 2: Create Transitions (GOTO Function)

From On Symbol To
I₀ E I₁
I₀ T I₂
I₀ F I₃
I₀ id I₅
I₀ ( I₄
I₂ * I₆
I₁ + I₇
I₄ E I₈
… … …

These transitions define shift and goto movements.

Step 3: Fill ACTION Table

State id + * ( ) $ ACTION
0 S5 S4
1 S7 Acc
2 R2 S6 R2 R2
3 R4 R4 R4 R4
State id + * ( ) $ ACTION
4 S5 S4
5 R6 R6 R6 R6
6 S5 S4
7 S5 S4
8 S7 S9
9 R1 R1 R1 R1

Each S means Shift, R means Reduce, Acc means Accept.

Step 4: Fill GOTO Table

State E T F
0 12 3
4 82 3
6 10 3
7 11 3
… …… …

These define transitions after reductions on non-terminals.

6. Interpretation of Table Entries

  ACTION[0, id] = S5 → In state 0, if id is next
input, shift it and go to state 5.
 ACTION[2, +] = R2 → In state 2, if + appears,
reduce using production 2.
 ACTION[1, $] = Accept → Input successfully
parsed.
 GOTO[0, E] = 1 → If we reduce to E in state 0,
move to state 1.

7. Detecting Conflicts
If any cell in the ACTION table has multiple entries, the
grammar is not SLR(1).
Two common conflicts:
1. Shift/Reduce conflict — both shift and reduce
possible.
2. Reduce/Reduce conflict — two reductions possible.
Example:
if expr then stmt | if expr then stmt else
stmt

creates a shift/reduce conflict (dangling else).

Such conflicts mean the grammar cannot be parsed by an
SLR parser.

8. Parsing Using SLR Table (Overview)

At runtime, the SLR parser uses this table as follows:
1. Initialize stack:
2. Stack = [0]
3. Input = id + id * id $

4. Look at top of stack (state) and next input token.

5. Consult ACTION table → perform shift or reduce.
6. After a reduction, use GOTO table to move to the
next state.
7. Repeat until accept or error.
The detailed parsing trace will be shown in Part 4.

9. Advantages of SLR Parsing

1. Systematic table construction — clear rules using
FOLLOW sets.
2. Efficient and deterministic — one parse per input,
no backtracking.
3. Good for simple unambiguous grammars.
4. Automatable — used in parser generators.

10. Limitations
1. Less powerful than canonical LR(1) — cannot
handle all deterministic grammars.
2. Conflicts possible for certain ambiguous structures
(e.g., “dangling else”).
 3. Hard to build manually for large grammars — best
done with tools.

4.6 Introduction to LR Parsing: Simple LR (SLR)

(Part 4 – Example of SLR Parsing Process and
Advantages)
In this final part of Section 4.6, we will now see how the
SLR parsing table is used to actually parse an input
string step by step.
We will trace each action (Shift, Reduce, Accept) and
observe how the stack, input, and actions evolve during
the process.
After that, we’ll summarize the strengths and practical
importance of the SLR method.

1. The Example Grammar

We’ll use the same simple arithmetic grammar that we
used in the previous parts:
E' → E
E → E + T | T
T → T * F | F
F → (E) | id

This grammar handles expressions like id + id * id.

We already have its SLR parsing table constructed
earlier.
2. Input to Parse
Let’s parse the input:
id + id * id $

(where $ marks the end of input).

We will now simulate the parser’s working using the
ACTION and GOTO tables step by step.

3. Initial Configuration
Stack Input Action
0 id + id * id $ Start (State 0)

 Stack stores states and symbols.

 Initially, only state 0 is in the stack.
 The parser reads the first input symbol id.
 It consults the ACTION[0, id] entry → Shift 5.

4. Step-by-Step Parsing Trace

Step Stack Input Action Explanation
id + id *
1 0 Shift 5 ACTION[0, id] = S5
id $
+ id * id Reduce F Because [F → id·]
2 0 id 5
$ → id found in state 5
Step Stack Input Action Explanation
+ id * id Reduce T Because [T → F·]
3 0F3
$ →F found in state 3
+ id * id Reduce E Because [E → T·]
4 0T2
$ →T found in state 2
+ id * id
5 0E1 Shift 6 ACTION[1, +] = S6
$
6 0E1+6 id * id $ Shift 5 ACTION[6, id] = S5
0 E 1 + 6 id Reduce F
7 * id $ [F → id·]
5 → id
0E1+6F Reduce T
8 * id $ [T → F·]
3 →F
0E1+6T
9 * id $ Shift 7 ACTION[2, *] = S7
2
0E1+6T
10 id $ Shift 5 ACTION[7, id] = S5
2*7
0E1+6T Reduce F
11 $ [F → id·]
2 * 7 id 5 → id
0E1+6T Reduce T
12 $ [T → T * F·]
2*7F8 →T*F
0E1+6T Reduce E
13 $ [E → E + T·]
2 →E+T
14 0E1 $ Accept [E' → E·]
5. Understanding the Trace
Let’s break down what’s happening conceptually:
 Shifts push symbols (like id, +, *) onto the stack and
advance input.
 Reductions replace sequences of symbols on the
stack with a non-terminal (using grammar rules).
 The GOTO table guides which state to go to after
each reduction.
 The Accept action occurs when the parser recognizes
the start symbol E' with all input consumed.
Thus, the input string id + id * id is successfully
parsed, and the grammar confirms it as syntactically
correct.

6. Parsing as a Rightmost Derivation in

Reverse
The sequence of reductions represents a rightmost
derivation in reverse order.
Let’s see the sequence of reductions:
1. F → id
2. T → F
3. E → T
4. F → id
5. T → F
 6. F → id
7. T → T * F
8. E → E + T
Reversing these gives the rightmost derivation:
E ⇒ E + T ⇒ E + T * F ⇒ E + T * id ⇒ E +
F * id ⇒ E + id * id

This confirms that LR parsing always corresponds to a

rightmost derivation in reverse.

7. Error Detection in SLR Parsing

One major strength of LR parsers (including SLR) is
early error detection.
If at any point, the parser encounters a table entry that’s
empty (no Shift, Reduce, or Accept), it immediately
reports a syntax error.
For example:
 If input had been id + * id,
after reading +, the parser would see * next,
but there would be no valid entry in the ACTION
table for that combination,
hence it would report an error at the earliest
possible moment.
This makes LR parsing robust and precise for real
compiler syntax analysis.
8. Advantages of SLR Parsing
Feature Description
Handles all deterministic context-free
Powerful
grammars that are SLR(1).
No backtracking; always one correct
Deterministic
action per step.
Linear-time parsing (O(n)) — fast for
Efficient
programming languages.
Detects syntax errors as soon as an
Error Detection
invalid prefix is seen.
Table-driven approach makes
Systematic
implementation consistent.
SLR is the basis for Canonical LR
Foundation for
(LR(1)) and LALR parsers used in real
Advanced Parsers
compilers.

9. Limitations of SLR Parsing

Limitation Explanation
Cannot handle all context-free
Limited Grammar
grammars; fails on some ambiguous
Coverage
ones.
Shift/Reduce Some grammars produce conflicts in
Conflicts the ACTION table (like the dangling else
 Limitation Explanation
problem).
If multiple reductions are valid, the
Reduce/Reduce
parser becomes undecidable without
Conflicts
extra lookahead.
For complex grammars, even SLR tables
Large Tables can become very large to build by
hand.

10. Practical Use in Compiler Design

In actual compilers:
 SLR parsing is often too limited for entire
programming languages.
 However, it’s conceptually and educationally
important because it introduces the foundation of
LR parsing.
 Real-world compilers use more powerful LR
variants:
o LALR (Look-Ahead LR): Compact and

practical (used in YACC, Bison).

o Canonical LR (LR(1)): More powerful but with

larger tables.
Thus, understanding SLR is essential before learning
these advanced parsers.
11. Summary of Section 4.6 (All Parts)
Part Focus Key Learning
LR parsing is a deterministic bottom-up
Part parser that reads left-to-right and
Introduction
1 performs rightmost derivation in
reverse.
Each item represents parser progress;
Part
LR(0) Items canonical collection defines parser
2
states.
Part SLR Table ACTION and GOTO tables are built
3 Construction using item sets and FOLLOW sets.
Step-by-step parsing trace
Part Example
demonstrates how input is accepted
4 Parsing
using the table.

Structure Plan for Section 4.7 – More Powerful

LR Parsers
 4.7 (Part 1): Canonical LR(1) Parsing – Concepts
and Motivation
 4.7 (Part 2): Constructing Canonical LR(1) Parsing
Tables (with Example)
  4.7 (Part 3): LALR (Look-Ahead LR) Parsing –
Concepts and Table Merging
 4.7 (Part 4): Comparison of SLR, LR(1), and LALR
Parsers, Advantages, and Limitations

Let’s start with 4.7 (Part 1): Canonical LR(1) Parsing –

Concepts and Motivation

4.7 More Powerful LR Parsers (Part 1 –

Canonical LR(1) Parsing: Concepts and
Motivation)
1. Introduction
The SLR parser we studied earlier is efficient and easy to
build but cannot handle certain grammars — especially
those that require more precise lookahead information.
To overcome these limitations, we use a more powerful
version called the Canonical LR(1) parser.
The term LR(1) means:
 L → Input is scanned Left to right
 R → Parser produces a Rightmost derivation in
reverse
 1 → The parser uses 1 symbol of lookahead to make
decisions
This additional lookahead symbol gives LR(1) parsers
greater power to distinguish between similar grammar
situations, thus eliminating many conflicts found in SLR
parsing.

2. Why SLR Fails in Some Cases

SLR parsers decide when to reduce using only
FOLLOW sets of non-terminals.
But FOLLOW sets are sometimes too general — they
apply reductions even when they shouldn’t.
Example Grammar
S → Aa | bAc | dc | bda
A → d

This grammar cannot be parsed by SLR(1) because the

FOLLOW sets cause conflicts —
the parser cannot distinguish between whether A should
reduce or wait for more input like c.
An LR(1) parser, however, uses lookahead information
to know exactly when a reduction is valid, thus avoiding
the conflict.

3. Key Idea of LR(1) Parsing

An LR(1) item is similar to an LR(0) item but with one
extra piece of information —
a lookahead symbol that indicates which input symbols
can legally follow the production.
Definition of LR(1) Item

An LR(1) item is written as:

[A → α · β, a]

where:
 A → αβ is a production of the grammar
 The dot (·) marks the parser’s position in the
production
 a is a lookahead symbol — a terminal that may
follow A in a valid derivation

Example

For the production E → E + T, the corresponding LR(1)

items are:
[E → · E + T, +]
[E → E · + T, +]
[E → E + · T, +]
[E → E + T ·, +]

Each item carries a lookahead symbol (like +, $, ), etc.),

which helps decide when reductions are valid.

4. Difference Between LR(0) and LR(1) Items

Feature LR(0) Item LR(1) Item
Representation [A → α · β] [A → α · β, a]
 Feature LR(0) Item LR(1) Item
Lookahead Info None One lookahead symbol
Reduce based on Reduce only if
Reduction Rule
FOLLOW(A) lookahead matches a
Accuracy Coarse More precise
Conflicts May occur Fewer conflicts

The LR(1) item uses lookahead to avoid incorrect

reductions, giving it much greater precision.

5. Closure and GOTO for LR(1) Items

Just like LR(0), we define closure and goto operations —
but they now include lookahead information.
Closure for LR(1) Items

If we have [A → α · B β, a], and there is a

production B → γ,
then we add [B → · γ, b] for every terminal b in
FIRST(βa).
In other words:
 If the parser expects B next,
 The possible lookaheads are everything that could
begin βa.
This ensures that each new item carries context-sensitive
lookahead.

GOTO for LR(1) Items

If I is a set of LR(1) items, and X is a grammar symbol,

then:
GOTO(I, X)

is the closure of all items [A → α X · β, a]

for every [A → α · X β, a] in I.

6. Example of Closure with Lookahead

Given grammar:
S' → S
S → C C
C → c C | d

Start item:
[S' → · S, $]

Then closure includes:

[S' → · S, $]
[S → · C C, $]
[C → · c C, c/d]
[C → · d, c/d]
Lookahead symbols propagate using FIRST sets and the
suffix after the non-terminal.

7. How LR(1) Resolves Ambiguity

In LR(1), a reduction is only performed if the lookahead
symbol matches the one expected in the item.
Example:
[A → α ·, a]

means “reduce A → α only if the next input symbol is a”.

Thus, even if two items suggest different actions, their
lookaheads determine which one applies, removing
conflicts that caused errors in SLR.

8. Canonical LR(1) Collection

The Canonical Collection of LR(1) Items is built
similarly to LR(0):
 Start with the closure of the initial item [S' → · S,
$]
 Repeatedly apply GOTO on all grammar symbols
(terminals and non-terminals)
 Include lookahead symbols in every new item set
Each unique set of LR(1) items becomes one state of the
LR(1) automaton.
Because lookahead makes each item distinct, there may
be many more states than in SLR —
but they lead to perfect precision in parsing.

9. Advantages of Canonical LR(1) Parsing

1. Handles all deterministic context-free grammars.
2. Eliminates conflicts found in SLR (due to detailed
lookahead).
3. Accurate and precise — never performs an invalid
reduction.
4. Strong error detection — can pinpoint syntax issues
very early.
5. Foundation for LALR parsing, which combines
power with compactness.

10. Disadvantages
1. Complex table construction — large number of
states.
2. Memory-intensive — each LR(1) item carries its
own lookahead symbol.
3. Difficult to implement manually — used mainly
through parser generators.
Despite these challenges, it forms the most powerful
deterministic parsing technique available.
4.7 More Powerful LR Parsers (Part 2 –
Constructing Canonical LR(1) Parsing Tables)

1. Purpose of the LR(1) Parsing Table

The Canonical LR(1) Parsing Table guides the parser in
performing the correct actions —
Shift, Reduce, Goto, or Accept — based on both the
current state and the lookahead symbol.
It consists of two main parts:
Table Part Used For Contains
ACTION Shift, Reduce, Accept, or Error
Terminals
Table entries
Non-
GOTO Table Next state after a reduction
terminals

The difference from the SLR table is that each entry is

based on precise lookahead symbols, rather than general
FOLLOW sets.
This eliminates many conflicts.

2. Steps to Construct the Canonical LR(1)

Parsing Table
The process has five systematic steps.
Step 1 – Augment the Grammar
Add a new start production to mark the start of parsing.
If the original grammar start symbol is S, we add:
S' → S

The new start symbol is S', and $ (end-of-input) is the

lookahead symbol for it.

Step 2 – Construct LR(1) Items

Each LR(1) item has the form:
[A → α · β, a]

where:
 A → αβ is a production,
 The dot (·) marks the current parsing position,
 a is the lookahead terminal that can follow A.

Step 3 – Compute Closure of LR(1) Items

When the dot (·) is before a non-terminal, we must
include items for its productions with appropriate
lookaheads.

then for each production B → γ and each terminal b ∈

If [A → α · B β, a] is in the item set,

FIRST(βa) we add:
[B → · γ, b]

This allows lookahead symbols to propagate through

the grammar.

Step 4 – Compute Canonical Collection of LR(1)

Item Sets
1. Start with the initial item set:
2. I₀ = closure([S' → · S, $])

3. For every item set I and grammar symbol X (terminal

or non-terminal),
compute:
4. GOTO(I, X)

5. Add each new item set to the collection if it’s not

already present.
The result is a complete LR(1) Automaton, where:
 Each state corresponds to an item set,
 Transitions between states are labeled with grammar
symbols.

Step 5 – Construct ACTION and GOTO Tables

Once all item sets and transitions are known:
 Type Rule Meaning
If [A → α · a β, b] in state
Move input symbol
i and GOTO(Iᵢ, a) = Iⱼ,
Shift a to stack and go
then ACTION[i, a] =
to state j.
shift j.
If [A → α ·, a] in state i, Reduce production
Reduce then ACTION[i, a] = only if lookahead is
reduce A → α. a.
If [S' → S ·, $] in state i,
Parsing is
Accept then ACTION[i, $] =
complete.
accept.
If GOTO(Iᵢ, A) = Iⱼ for
Move to new state
Goto non-terminal A, then GOTO[i,
after reduction.
A] = j.

All other entries are marked as error.

3. Example: Constructing an LR(1) Parser

Let’s use a simple grammar:
S' → S
S → C C
C → c C | d

We’ll now walk through how to construct its LR(1)

collection and table.
Step 1 – Augment the Grammar
S' → S
S → C C
C → c C | d

Step 2 – Start Item and Closure

Start with:
[S' → · S, $]

Closure includes:
[S' → · S, $]
[S → · C C, $]
[C → · c C, c/d]
[C → · d, c/d]

Explanation:
 Because the dot precedes C, we add items for all C
productions.
 Lookaheads {c, d} come from FIRST of the next
symbols.

Step 3 – Compute GOTO Transitions

Let’s derive a few transitions:
From Item Set On Symbol To Item Set
I₀ S I₁
I₀ C I₂
I₀ c I₃
I₀ d I₄

and so on.

Step 4 – Example of New Item Set

For example, GOTO(I₀, C) gives:
[S → C · C, $]
[C → · c C, $]
[C → · d, $]

and GOTO(I₀, c) gives:

[C → c · C, c/d]
[C → · c C, c/d]
[C → · d, c/d]

You can see how lookahead symbols remain attached to

each item —
this makes LR(1) tables context-sensitive and accurate.

Step 5 – Build ACTION and GOTO Table

Finally, we build the table based on transitions and items.
ACTION Table (Simplified View)
State c d $ ACTION
0 S3 S4
1 Acc
2 S3 S4
3 S3 S4
4 R3 R3 R3 Reduce C → d
5 Reduce S → C C
GOTO Table
State S C
0 12
2 5
3 6
6 5

This table allows precise parsing with no conflicts, since

reductions are limited to exact lookahead symbols.

4. Difference from SLR Table Construction

Feature SLR Canonical LR(1)
Uses FOLLOW Uses exact lookahead
Lookahead
sets symbols
 Feature SLR Canonical LR(1)
Precision Coarse Very fine-grained
Conflicts Possible Rare
Table Size Small Very large
Complexity Easier Complex

The LR(1) method ensures no incorrect reductions, even

when FOLLOW sets overlap.

5. Parsing Example (Conceptual Overview)

Let’s parse the input:
c d d $

using the constructed LR(1) table.

1. Start in state 0 with stack [0].
2. Read first c → ACTION[0, c] = shift 3.
3. Process next symbol and use GOTO transitions as
reductions occur.
4. Continue until reaching [S' → S·, $].
5. ACTION = Accept.
Each step follows exactly one valid shift or reduction —
no ambiguity, no guessing, and no conflicts.
6. Strength of Canonical LR(1)
1. Can handle all deterministic context-free
grammars (DCFGs).
2. Ensures unambiguous parsing for all valid input
strings.
3. Detects syntax errors immediately upon
encountering invalid symbols.
4. Forms the basis for practical LALR parsers.

7. Limitations
1. Large number of states (can be hundreds for
medium grammars).
2. Not memory-efficient for implementation by hand.
3. Complex table generation, requiring automated
parser generators.

4.7 More Powerful LR Parsers (Part 3 – LALR

(Look-Ahead LR) Parsing: Concept and Table
Merging)
In the previous parts, we studied how Canonical LR(1)
parsing achieves very high precision using lookahead
symbols.
However, the problem with Canonical LR(1) parsers is
that they produce too many states, making the parsing
tables very large and difficult to handle in practice.
To solve this, a new technique called LALR (Look-
Ahead LR) parsing was introduced.
LALR parsers are smaller and faster, yet almost as
powerful as full LR(1) parsers — making them the most
widely used in real-world compiler design.

1. Introduction to LALR Parsing

LALR stands for Look-Ahead LR.
It combines the compactness of SLR parsing with the
power of LR(1) parsing.
In simple words:
“LALR parsers are obtained by merging similar states of
the Canonical LR(1) parser while preserving their
lookahead symbols.”
This technique gives the same number of states as an
SLR parser,
but retains most of the conflict-free accuracy of the
LR(1) parser.

2. Motivation for LALR Parsing

Let’s recall a key problem with Canonical LR(1):
 Each LR(1) item includes a lookahead symbol.
  Often, two item sets are identical except for their
lookahead symbols.
 This duplication creates many redundant states,
sometimes hundreds.
To fix this, LALR merges those similar states —
reducing the total number of states without losing
accuracy.

Example Situation
Suppose two LR(1) item sets differ only in lookaheads:
I₁: [A → α ·, a]
I₂: [A → α ·, b]

Since both represent the same core structure [A → α ·],

LALR merges them into a single state:
I₃: [A → α ·, {a, b}]

Now, one state handles both lookaheads.

3. Core Concept: “Core” of an Item Set

Before merging, we define the core of an item set.
 The core of an item set consists of all its items
without lookahead symbols.
For example:
I₁: [A → α · β, a]
I₂: [A → α · β, b]

Both have the same core [A → α · β].

LALR Merging Rule

If two LR(1) item sets have the same core,
we merge them into one by combining their lookahead
symbols.
This way:
 Duplicate states are removed.
 The table size shrinks dramatically.
 The parser remains almost as powerful.

4. Steps to Construct an LALR Parser

The construction is similar to Canonical LR(1) parsing,
but includes a merging step.

Step 1 – Start with Canonical LR(1) Collection

Build all LR(1) item sets and transitions using closure
and goto operations.

Step 2 – Identify Item Sets with Same Core

Find all item sets whose items differ only in lookahead
symbols.
Example:
I₄ = {[C → c · C, d], [C → c · C, $]}
I₅ = {[C → c · C, c]}

Both share the core [C → c · C].

Step 3 – Merge These Item Sets

Combine them into one set by uniting their lookahead
symbols:
Merged: [C → c · C, {c, d, $}]

Step 4 – Construct ACTION and GOTO Tables

After merging:
 Build the ACTION and GOTO tables exactly as
before.
 Each merged set becomes a state in the LALR
parser.

Step 5 – Resolve Conflicts (if any)

Sometimes merging can cause new shift/reduce or
reduce/reduce conflicts.
If so:
  Try refining lookahead sets.
 If unresolved, the grammar may not be LALR(1).
In most practical programming languages, such conflicts
are rare.

5. Example: LALR Merging Process

Let’s reuse our earlier grammar:
S' → S
S → C C
C → c C | d

The Canonical LR(1) version of this grammar has 12

states.
However, after merging equivalent cores, the LALR
version has only 7 states.

Example of Merged States

Canonical States Common Core Merged LALR State
I₃, I₄ [C → c · C] Merged into one
I₆, I₇ [S → C C ·] Merged into one

This merging process reduces table size almost by half,

while still recognizing exactly the same language.
6. LALR Parsing Table Construction
Once merged, we build the ACTION and GOTO tables
as usual.
State Input (c) Input (d) Input ($) ACTION
0 Shift 3 Shift 4
1 Accept
2 Shift 3 Shift 4
3 Shift 3 Shift 4
4 Reduce C → d Reduce C → d Reduce C → d
5 Reduce S → C C
State S C
0 12
2 5
3 6

The parsing actions remain deterministic, even though the

states are merged.

7. Comparison: LR(1) vs LALR vs SLR

Feature SLR Canonical LR(1) LALR
Lookahead FOLLOW Individual Merged
sets lookahead lookahead sets
 Feature SLR Canonical LR(1) LALR
symbols
Table Size Small Very large Moderate
Conflicts Possible None Very rare
Parsing
Moderate Highest Almost as high
Power
Practical (used in
Usage Educational Theoretical
real compilers)

8. Why LALR is Popular in Practice

Most real-world parser generators like YACC, Bison, and
ANTLR use LALR parsing.
Reasons include:
 Compact tables → fewer states, smaller memory
usage.
 Almost LR(1)-level power → handles almost all
real-world grammars.
 Efficient → O(n) time complexity for parsing.
 Simple implementation → merging process is
systematic.
Thus, LALR is the best compromise between accuracy
and efficiency.
9. Limitations of LALR Parsing
1. Some grammars that are valid LR(1) may not be
valid LALR(1) due to merging conflicts.
2. Merging can cause reduce/reduce conflicts if two
items with different lookaheads are merged
incorrectly.
3. Still complex to construct manually — usually
generated automatically by parser generators.
However, for most programming languages (like C, Java,
or Python), LALR parsers work perfectly.

4.7 More Powerful LR Parsers (Part 4 –

Comparison of SLR, LR(1), and LALR Parsers:
Advantages, Limitations, and Practical Use)
In the previous parts, we explored three important LR-
based parsing methods:
SLR, Canonical LR(1), and LALR.
Each of them uses the same fundamental bottom-up,
rightmost derivation in reverse approach but differs in
how precisely they use lookahead information and how
large or small their parsing tables are.
In this final part, we will clearly compare these three
parsers, understand their relative strengths, weaknesses,
and practical importance in compiler construction.
1. Recap of the Three LR Parsers
Let’s first recall what each parser is designed to achieve.
Parser Type Meaning Key Idea
SLR (Simple Simple, small, but less
Uses FOLLOW sets
LR) precise
Canonical Uses one lookahead Fully accurate, but large
LR(1) per item tables
LALR (Look- Merges LR(1) states Compact and powerful,
Ahead LR) with same core used in real compilers

All three belong to the LR family (Left-to-right scanning,

Rightmost derivation in reverse),
and all construct ACTION and GOTO tables for
deterministic, table-driven parsing.

2. Comparison Based on Construction

Canonical
Feature SLR Parser LALR Parser
LR(1)
LR(1) items
LR(1) items
Items Used LR(0) items with
(merged by core)
lookahead
Per-item Combined
Lookahead FOLLOW
lookahead lookaheads of
Basis sets
symbol merged items
 Canonical
Feature SLR Parser LALR Parser
LR(1)
Number of
Small Very large Similar to SLR
States
Construction
Easy Complex Moderate
Effort
Storage
Low High Medium
Requirement
Many No conflicts
Conflict Rare conflicts
conflicts for LR(1)
Resolution after merging
possible grammars

The Canonical LR(1) method is the most powerful but

also the heaviest to implement,
while LALR strikes an ideal balance between power and
practicality.

3. Comparison Based on Parsing Power

Aspect SLR LR(1) LALR
Subset of All deterministic Nearly all
Grammars
LR(1) context-free LR(1)
Accepted
grammars grammars grammars
Error Detection Moderate Strong Strong
 Aspect SLR LR(1) LALR
Handling Excellent in
Poor Excellent
Ambiguity most cases
Shift/Reduce
Common None Very few
Conflicts
Reduce/Reduce
Common None Rare
Conflicts

Hence:
 If a grammar is not SLR(1), it may still be LALR(1)
or LR(1).
 Almost every programming language grammar is
LALR(1), so LALR parsers are the practical choice.

4. Comparison Based on Parsing Table Size

Parser Memory
Table Size Number of States
Type Requirement
≈ 20–30 for simple
SLR Smallest Very low
grammars
Can exceed 200 for
LR(1) Largest Very high
medium grammars
LALR Moderate ≈ Same as SLR Balanced
Thus, LALR manages to achieve LR(1)-level accuracy
with SLR-level compactness —
making it both efficient and accurate.

5. Conceptual View: What’s Added in Each

Step
Evolution
What Changed Benefit
Step
Basic shift-reduce, no
LR(0) Foundation concept
lookahead
Simpler, but conflicts
SLR(1) Added FOLLOW sets
possible
Canonical Added one-symbol
Fully precise parsing
LR(1) lookahead per item
Merged identical LR(1) Compact, practical
LALR(1)
states power

So, the entire LR family can be seen as an evolution:

LR(0) → SLR(1) → LR(1) → LALR(1)

Each step adds lookahead awareness or table

optimization.
6. When to Use Which Parser
Situation Best Parser Reason
Educational purpose or Simple and easy to
SLR
concept learning understand
Research or theoretical Canonical Fully deterministic
parsing LR(1) and conflict-free
Real-world compiler Compact and
LALR
implementation sufficiently powerful

In practice, most parser generators (like YACC, Bison,

and ANTLR) use LALR(1) parsing for its balance of
power and efficiency.

7. Strengths and Weaknesses Summary

A. SLR (Simple LR)
Strengths:
 Simple to implement manually.
 Small parsing tables.
 Suitable for teaching and small grammars.
Weaknesses:
 Cannot handle many programming language
grammars.
 Frequent shift/reduce conflicts.
 Fails for ambiguous grammars.
B. Canonical LR(1)
Strengths:
 Most powerful deterministic parser.
 No conflicts for LR(1) grammars.
 Very accurate and robust.
 Excellent error detection.
Weaknesses:
 Generates hundreds of states (memory expensive).
 Difficult to construct by hand.
 Practically replaced by LALR for real compilers.

C. LALR (Look-Ahead LR)

Strengths:
 Combines the power of LR(1) with the compactness
of SLR.
 Widely used in real compiler generators.
 Efficient in both time and space.
 Handles most programming language grammars.
Weaknesses:
 Can still fail for some complex LR(1) grammars.
 Occasional reduce/reduce conflicts after merging.
8. Parsing Power Hierarchy
In terms of strength and expressiveness, the parsers are
related as follows:
LR(1)
↑
LALR(1)
↑
SLR(1)
↑
LR(0)

Every grammar that is SLR(1) is also LALR(1) and

LR(1),
but not every LR(1) grammar is SLR(1).
Thus, the LR(1) parser family forms a hierarchy of
increasing power.

9. Real-World Applications
Parser Example Tools or Uses
SLR Educational tools, theoretical examples
Canonical
Advanced research, grammar analyzers
LR(1)
Real compilers and parser generators (e.g.,
LALR
YACC, Bison, CUP)
Almost all industrial compilers (C, C++, Java, Pascal)
rely on LALR(1) parsing
because it efficiently supports large language grammars.

10. Summary of Section 4.7 (All Parts)

Part Focus Main Learning
Part Canonical LR(1) Each LR(1) item includes one
1 Concepts lookahead; more powerful than SLR.
Part Constructing Built using closure and goto with
2 LR(1) Tables lookahead propagation.
Part Merges LR(1) states with same core
LALR Parsing
3 to reduce size.
Part Comparison & Summarizes trade-offs and practical
4 Evaluation choices between the three parsers.

Excellent — now we move to Section 4.8 – Using

Ambiguous Grammars.
This section deals with an important practical issue:
sometimes grammars that describe real programming
languages are ambiguous — meaning they can generate
more than one parse tree for the same input string.
In compiler design, ambiguity is a serious problem
because a parser must always produce a single, unique
syntax tree for every valid program.
However, in some cases, ambiguous grammars are used
intentionally when the ambiguity can be controlled by
special precedence and associativity rules.
We’ll study these ideas step by step, and since this section
is conceptually rich, we’ll divide it into two parts for
clarity.

Section 4.8 – Using Ambiguous Grammars

 Part 1: Understanding Ambiguity in Grammars and
Its Problems
 Part 2: Handling Ambiguity with Precedence and
Associativity Rules

4.8 Using Ambiguous Grammars (Part 1 –

Understanding Ambiguity and Its Problems)
1. What is an Ambiguous Grammar?
A grammar is ambiguous if there exists at least one
string that can have two or more different parse trees
(or equivalently, two different leftmost or rightmost
derivations).
Formally:
A context-free grammar (CFG) is ambiguous if there
exists a string w such that:
w has two or more distinct parse trees.
2. Example of Ambiguity
Consider this simple arithmetic grammar:
E → E + E
E → E * E
E → id

Now take the input string:

id + id * id

There are two possible parse trees:

(a) Interpretation 1 – Addition first
E
/ | \
E + E
| /|\
id E * E
| |
id id

(b) Interpretation 2 – Multiplication first

E
/ | \
E * E
/|\ |
E + E id
| |
id id

Both parse trees represent the same string, but the order
of operations is different —
and this leads to different meanings (or results) in
computation.
Thus, this grammar is ambiguous.

3. Why Ambiguity is a Problem

Ambiguity creates uncertainty in syntax analysis because
the parser can’t decide which parse tree (or meaning) to
choose.
Problems caused by ambiguity:

1. Multiple parse trees → multiple interpretations.

o Example: id + id * id could mean (id +

id) * id or id + (id * id).

2. Compiler inconsistency.
o The syntax tree is the foundation for semantic

analysis and code generation.

Different trees lead to different compiled code.
3. Parser conflict.
o Ambiguity causes shift/reduce or

reduce/reduce conflicts in LR and LL parsing

tables.
4. Error-prone debugging.
o Developers can’t predict which structure the

compiler will interpret.

Because of these reasons, ambiguity must either be
removed or controlled.
4. Ambiguity in Programming Languages
Many programming language constructs are inherently
ambiguous if written directly as context-free rules.
Common examples:
 Operator precedence (e.g., * binds stronger than +)
 Associativity (e.g., a - b - c should mean (a -
b) - c, not a - (b - c))
 Dangling else (e.g., ambiguity in if-then-else
statements)

5. Example: Dangling Else Ambiguity

Consider this grammar fragment:
stmt → if expr then stmt
| if expr then stmt else stmt
| other

Now consider this code:

if E1 then if E2 then S1 else S2

The question is: does else S2 belong to the inner if or

the outer if?
Both interpretations are possible:
1. Interpretation 1 (else matches inner if):
2. if E1 then (if E2 then S1 else S2)
 3. Interpretation 2 (else matches outer if):
4. (if E1 then if E2 then S1) else S2

This makes the grammar ambiguous.

6. General Ways to Handle Ambiguity

There are two main approaches:
1. Rewrite the grammar to be unambiguous.
Modify the grammar rules to enforce clear structure
and eliminate multiple parse trees.
2. Keep the grammar ambiguous, but disambiguate
using rules.
Keep the simpler ambiguous grammar, but guide the
parser using operator precedence and associativity
specifications.
This is the preferred approach in many real
compilers.

7. Rewriting Example (Unambiguous Grammar)

To remove ambiguity from the arithmetic grammar:
Ambiguous grammar:
E → E + E | E * E | id

Unambiguous version:
E → E + T | T
T → T * F | F
F → id

Here:
 Multiplication (*) is separated into a lower-level
nonterminal (T),
ensuring that * has higher precedence than +.
 Addition (+) applies only at the outermost level (E).
So, for input id + id * id,
the only valid parse tree corresponds to id + (id *
id) —
multiplication takes precedence, as expected.

8. Key Observation
Ambiguity is not always evil — it’s sometimes a useful
simplification if the parser knows how to resolve it
consistently.
For example, operator precedence and associativity
declarations allow parser generators to automatically
choose the correct parse when conflicts arise.

4.8 Using Ambiguous Grammars (Part 2 –

Handling Ambiguity with Precedence and
Associativity Rules)
In Part 1, we understood what ambiguity in grammars is
and why it is problematic.
We also saw that while some grammars can be rewritten
to remove ambiguity, it is often simpler and more
practical to retain the ambiguous grammar and control
the ambiguity through carefully defined rules.
In this part, we will study how operator precedence and
associativity are used in compilers to resolve ambiguity
automatically — without changing the grammar structure.

1. The Practical Need for Controlled

Ambiguity
In programming languages, arithmetic and logical
expressions are frequent, and their grammar would
become very complex if we tried to rewrite it in a
completely unambiguous way.
For example, to handle all combinations of +, -, *, /, <,
>, ==, etc., an unambiguous grammar would have dozens
of nonterminals.
Hence, compilers and parser generators (like YACC,
Bison, and ANTLR) use simple ambiguous grammars
and rely on:
 Precedence rules (to decide which operator binds
tighter)
 Associativity rules (to decide grouping direction)
These rules let the parser automatically choose the correct
parse tree when conflicts arise.

2. Operator Precedence
Definition
Operator precedence defines which operator should be
applied first when several operators appear in an
expression without parentheses.
For example:
id + id * id

Multiplication (*) has higher precedence than addition

(+),
so the intended interpretation is:
id + (id * id)

Even though the grammar is ambiguous, this precedence

rule ensures only one parse tree is selected.

Common Precedence Hierarchy

From highest to lowest (typical in most languages):
Precedence
Operators Example Interpretation
Level
Highest *, /, % a + b * c → a + (b * c)
 Precedence
Operators Example Interpretation
Level
Medium +, - a - b - c → (a - b) - c
a + b > c → ((a + b) >
Low <, >, ==
c)

The parser uses this hierarchy to guide parsing decisions.

How Precedence Resolves Conflicts

In LR or LALR parsing tables, ambiguity often appears as
a shift/reduce conflict.
For instance, when both “shift” and “reduce” actions are
possible, the parser generator refers to the operator’s
precedence:
 If the incoming operator has higher precedence,
shift.
 If the operator on stack has higher precedence,
reduce.
Thus, precedence rules tell the parser which operation to
handle first.

Example
Grammar (ambiguous):
E → E + E | E * E | id
Input:
id + id * id

During parsing:
 Parser sees both shift and reduce options when *
appears.
 Because * has higher precedence than +, it shifts
instead of reducing.
 This automatically produces the intended parse tree:
id + (id * id).

3. Operator Associativity
Definition
When two operators of the same precedence appear
together, associativity determines which operator is
applied first.
For example:
a - b - c

Here both - operators have equal precedence.

If subtraction is left associative, this means:
(a - b) - c

If it were right associative, it would mean:

a - (b - c)
Types of Associativity
Associativity Example
Example Operators
Type Interpretation
a - b - c → (a -
Left Associative +, -, *, /, %, <, >
b) - c
Right a = b = c→a =
=, ^, **, ternary ?:
Associative (b = c)
Non- Relational
a < b < c is invalid
Associative operators like <, >

Thus, associativity defines the grouping direction for

operators of the same precedence.

How Associativity Resolves Conflicts

During parsing:
 If both operators have the same precedence,
associativity decides between shift and reduce.
 Left associative: the parser reduces before shifting
(evaluates left first).
 Right associative: the parser shifts before reducing
(evaluates right first).

Example 1: Left Associativity

E → E - E | id
Input: a - b - c
At a - b, the parser can either:
 Reduce E → E - E, or
 Shift and continue reading.
Because - is left associative, the parser chooses to
reduce,
resulting in (a - b) - c.

Example 2: Right Associativity

E → E = E | id

Input: a = b = c
Both = have equal precedence, but since = is right
associative,
the parser shifts to read more input, producing a = (b =
c).

4. Declaring Precedence and Associativity in

Parser Generators
In real compiler tools like YACC or Bison, precedence
and associativity can be declared directly.
Example (YACC syntax):
%left '+' '-'
%left '*' '/'
%right '='
%%
E : E '+' E
| E '-' E
| E '*' E
| E '/' E
| E '=' E
| id
;

Here:
 %left defines left associativity.
 %right defines right associativity.
 Operators listed later (*, /) have higher precedence
than earlier ones (+, -).
These declarations automatically resolve shift/reduce
conflicts during table construction.

5. The “Dangling Else” Problem Revisited

Ambiguity in if-then-else statements is another
classic example that’s handled using precedence rules
rather than rewriting the grammar.
Ambiguous grammar:
stmt → if expr then stmt
| if expr then stmt else stmt
| other
Rule used by most languages:
The else is associated with the nearest unmatched if.
This is implemented by assigning higher precedence to
the “else” keyword
than to “then”, ensuring the parser always attaches an
else to the innermost if.

Result
Input:
if E1 then if E2 then S1 else S2

is always interpreted as:

if E1 then (if E2 then S1 else S2)

and not as (if E1 then if E2 then S1) else S2.

Thus, ambiguity is resolved without changing the
grammar,
just by defining precedence between “then” and “else”.

6. Advantages of Using Precedence and

Associativity
1. Simpler grammar:
Reduces the number of nonterminals and
productions.
 2. Automatic disambiguation:
Parser generators resolve conflicts based on rules.
3. More readable grammar:
Developers can easily add new operators.
4. Practical for large languages:
Used by almost all programming language parsers.

7. Limitations
1. Not suitable for all ambiguities:
Some ambiguous constructs cannot be fixed using
precedence rules (e.g., nested typedefs or
grammar-level ambiguity).
2. Must be declared carefully:
Wrong precedence order can lead to wrong parse
trees.
3. Limited to operator-related conflicts:
Other structural ambiguities may still require
grammar rewriting.

8. Summary of Part 2
 Ambiguous grammars are often retained for
simplicity.
 Ambiguity is managed by defining operator
precedence and associativity rules.
 Precedence decides which operator binds first.
 Associativity decides direction when operators have
equal precedence.
  Tools like YACC/Bison use declarations (%left,
%right) to apply these rules.
 Ambiguities like dangling else are resolved using the
same concept.

4.9 Error Recovery in LR Parsing

In a real compiler, the parser must do more than just
accept or reject input; it must also detect syntax errors
and recover gracefully so that the remaining program can
still be analyzed.
A parser that simply stops at the first error is not very
helpful to the programmer.
Instead, a good parser should be able to:
1. Identify an error precisely,
2. Report it clearly, and
3. Continue parsing to find further errors.
This section explains how LR parsers (such as SLR,
LALR, and Canonical LR(1)) handle syntax errors and
perform error recovery using various strategies.

1. Introduction
LR parsers are table-driven and hence very good at
detecting errors as soon as possible — that is, at the point
where no valid shift or reduce action exists in the parsing
table.
When the parser consults the ACTION table for the
current state and next input symbol and finds that the
entry is empty, it immediately identifies a syntax error.
This early detection is one of the strongest advantages of
LR parsing.

Example
Suppose the input string is:
id + * id

During parsing, when the parser encounters + *, it

consults the table and finds no valid entry for that
combination of state and symbol.
At this exact moment, it detects a syntax error — before
reading the rest of the input.
Thus, LR parsers detect errors at the earliest possible
point, unlike some top-down parsers that might continue
too far before realizing something is wrong.

2. Goals of Error Recovery

When an error occurs, the parser must:
 1. Report the error meaningfully, so the programmer
understands the problem.
2. Skip or adjust part of the input to reach a point
where parsing can continue.
3. Avoid cascading errors — a single error should not
generate dozens of false error messages.
Hence, the process must be both accurate and robust.

3. Types of Errors Detected During Parsing

Error Type Description Example
Lexical Invalid tokens from the
@variable = 5;
Errors scanner
Syntax Violation of grammar if (a > b) else
Errors rules c = d;

Semantic Incorrect meaning,

x = true + 5;
Errors type, or usage
Logical Valid syntax but
while(1) { }
Errors incorrect logic

LR parsers mainly deal with syntax errors — errors that

violate the context-free grammar.

4. Common Syntax Errors

1. Missing operators or operands:
a b + c → missing operator between a and b.
 2. Unbalanced parentheses:
(a + b → missing closing parenthesis.
3. Unexpected token:
if x then else y → extra “else”.
4. Wrong operator order:
* a + b → operator * cannot start an expression.

These are the kinds of errors the LR parser can catch

immediately by consulting its table.

5. LR Error Recovery Techniques

There are several methods used by LR parsers to recover
from syntax errors.
They differ in complexity, accuracy, and how much input
they skip before continuing.

A. Panic-Mode Recovery
Idea:
Skip input symbols until a “safe” point (a synchronizing
token) is found.
This is the simplest and most commonly used recovery
technique in LR parsing.
Process

1. When an error is found (no entry in the ACTION

table),
 the parser pops states from the stack until it finds a
state that can handle a synchronizing token.
2. It then skips input tokens until such a token is
found.
3. Parsing resumes from that point.
Synchronizing Tokens

Typical synchronizing tokens are:

 Statement separators like ;
 Block delimiters like { or }
 End of statement keywords like end, else
Example

Input:
a + (b * c ; d + e)

The parser encounters an unexpected ; after c.

It skips symbols until it finds the next ), which is a
synchronizing token,
and then continues parsing.
Advantages

 Very simple and fast.

 Prevents long cascades of false errors.
 Works well for statement-based languages like C or
Java.
Disadvantages

 Some statements may be skipped entirely.

 The parser may miss the specific cause of the error.

B. Phrase-Level Recovery
Idea:
When an error is detected, the parser makes local
corrections to the input
so that parsing can continue immediately.
Techniques

 Insert missing symbols (e.g., insert ; or )).

 Delete extra symbols.
 Replace one token with another.
 Transpose adjacent symbols.
Example

If the input is:

if (x > y then z = 1;

The parser might automatically insert a missing ) after y.

Advantages

 Keeps parsing closer to the user’s intended meaning.

 Fewer skipped parts of input.
Disadvantages

 Harder to implement for LR parsers (since table-

driven).
 May produce misleading error messages if the
correction guess is wrong.

C. Error Productions
Idea:
Extend the grammar itself with special error rules to
handle common mistakes.
Example
stmt → error ';'
stmt → if expr then stmt
stmt → if expr then stmt else stmt

Here, the production stmt → error ';' handles

invalid statements that still end with ;.
The parser will detect the error, consume input until ;,
and then continue parsing.
Advantages

 Allows more specific error messages.

 Integrates naturally into parsing tables.
Disadvantages

 Grammar becomes more complex.

  Must be carefully designed to avoid introducing new
ambiguities.

D. Global Correction
Idea:
Find the smallest number of changes to transform an
incorrect input into a valid one.
Example changes: insert, delete, or replace tokens to
make input syntactically correct.
While theoretically elegant, this approach is too
expensive computationally (requires exploring many
possibilities), so it’s rarely used in real compilers.

6. Example of Panic-Mode Recovery in

Action
Let’s simulate a simple LR parser detecting and
recovering from an error.
Grammar:
stmt → id = expr ;
expr → expr + term | term
term → id

Input:
x = y + + z ;
Process:
 Parser reads x = y +, expects an operand but sees
another +.
 ACTION table has no valid entry → syntax error
detected.
 Panic-mode: skip extra + and resume from next valid
token z.
 Continue parsing until reaching ;.
Output Message:
Syntax error near '+': missing operand
before '+'.
Continuing after correction...

The parser continues parsing instead of terminating.

7. Typical Error Messages from LR Parsers

When an LR parser finds an error, it often reports:
 The unexpected token, and
 The expected symbols according to the grammar.
Example:
Error: Unexpected token '*', expected one
of {id, '('}

Such messages are helpful for debugging syntax issues

during compilation.
8. Summary of Error Recovery Methods
Method Description Usefulness Complexity
Skip input until
Panic-Mode synchronizing High Simple
token
Local fixes to
Phrase-Level Moderate Medium
continue parsing
Error Add rules for
High Medium
Productions common mistakes
Global Minimal edits to Low
High
Correction correct input (impractical)

9. Advantages of LR Error Recovery

1. Immediate detection: LR parsers detect errors as
soon as they occur.
2. Controlled continuation: Recovery methods allow
continued parsing.
3. Informative diagnostics: Expected-token messages
help users fix errors.
4. No backtracking: Ensures efficiency even in
presence of errors.

4.10 Summary of Chapter 4 – Syntax Analysis

Chapter 4 focused on Syntax Analysis, one of the most
important phases of a compiler.
The syntax analysis stage is also known as parsing, and
its main job is to check whether the given input program
(in the form of tokens) follows the grammatical structure
of the programming language.
This chapter explained the different types of parsers,
especially top-down and bottom-up parsers, and gave
detailed coverage of LR parsing techniques, which are
among the most powerful and widely used in compiler
construction.
The following summary reviews all the sections of
Chapter 4 step by step.

1. Introduction (Section 4.1)

 Purpose of Syntax Analysis:
The syntax analyzer (parser) checks whether the
sequence of tokens produced by the lexical analyzer
forms a valid sentence according to the grammar of
the language.
 Input and Output:
o Input: Stream of tokens from the lexical

analyzer.
o Output: A parse tree (or syntax tree)

representing grammatical structure.

 Functions of the Parser:
 1. Detect syntax errors.
2. Report errors accurately.

3. Produce a hierarchical structure (parse tree) for

further stages.
 Relation with Grammar:
The parser uses context-free grammars (CFGs),
which describe syntactic structure formally.

2. The Role of the Parser (Section 4.2)

 The parser acts as a bridge between lexical analysis
and semantic analysis.
 It organizes the flat stream of tokens into a tree
structure that shows how tokens combine into valid
language constructs (expressions, statements, etc.).
 It checks that each construct conforms to the
grammar’s rules.
 On detecting an error, it must report and recover so
that further parsing can continue.
 Two main strategies:
1. Top-down parsing – starts from the start
symbol and expands nonterminals.
2. Bottom-up parsing – starts from the input and
reduces it back to the start symbol.

3. Context-Free Grammars (Section 4.3)

 A context-free grammar (CFG) consists of:
o A set of nonterminals (variables).
 o A set of terminals (tokens).
o A start symbol.

o A set of production rules of the form A → α.

 Sentential forms and derivations define how

sentences of a language are generated.
 Parse trees show hierarchical structure of
derivations.
 Ambiguity:
A grammar is ambiguous if one string has two or
more parse trees.
Ambiguity must be removed or controlled in syntax
analysis.

4. Top-Down Parsing (Section 4.4)

 Top-down parsers build the parse tree from root to
leaves, predicting productions.
 They try to find a leftmost derivation for the input
string.
4.4.1 Recursive-Descent Parsing
 Consists of a set of mutually recursive functions —
one for each nonterminal.
 Each function processes a portion of input according
to grammar rules.
 Works only if the grammar is non-left-recursive and
unambiguous.
4.4.2 Predictive Parsing
  A special type of recursive-descent parsing that uses
lookahead tokens to predict the correct production.
 For each nonterminal, only one production is chosen
based on the next input symbol.
 Uses FIRST and FOLLOW sets to guide decisions.
 Implemented as LL(1) parsers — very efficient but
only for a restricted class of grammars.

5. Bottom-Up Parsing (Section 4.5)

 Bottom-up parsing starts from the input string and
gradually reduces it to the start symbol.
 It performs a rightmost derivation in reverse.
4.5.1 Reductions and Handles
 A handle is a substring that matches the right side of
a production and can be reduced to the left side.
 The parser repeatedly finds handles and performs
reductions until only the start symbol remains.
4.5.2 Shift-Reduce Parsing
 Operates with a stack:
o Shift: push the next input symbol on the stack.

o Reduce: replace a handle on the stack by its

corresponding nonterminal.
 Simple and effective but can face shift/reduce or
reduce/reduce conflicts in ambiguous grammars.
4.5.3 Operator-Precedence Parsing
  Special form of bottom-up parsing that uses operator-
precedence relations to guide parsing.
 Works for grammars where no two operators have
equal precedence and where precedence between
every pair is defined.
 Used mainly for arithmetic expressions.

6. Introduction to LR Parsing: Simple LR

(SLR) (Section 4.6)
 LR parsing stands for:
o L: Scans input from Left to right.

o R: Produces a Rightmost derivation in reverse.

 LR parsers are bottom-up, table-driven, and

deterministic.
4.6.1 LR(0) Items
 Items are grammar rules with a dot (·) indicating how
much of the production has been seen.
 Example: [A → α · β].
4.6.2 Canonical Collection of LR(0) Items
 Constructed using closure and goto functions.
 Each item set represents a state in the parser’s
automaton.
4.6.3 Constructing SLR Parsing Tables
 ACTION and GOTO tables guide the parser:
 o ACTION: For terminals — shift, reduce, accept,
or error.
o GOTO: For nonterminals — next state after

reduction.
 Uses FOLLOW sets to determine reduce actions.
 Example parsing process shows stack operations and
transitions.

7. More Powerful LR Parsers (Section 4.7)

4.7.1 Canonical LR(1) Parsing Tables
 Adds lookahead symbols to LR(0) items for better
precision.
 Each item becomes [A → α · β, a], where a is a
lookahead symbol.
 Eliminates most conflicts found in SLR parsing but
creates very large tables.
4.7.2 LALR Parsing Tables
 Merges LR(1) states with the same core (same items
ignoring lookaheads).
 Produces smaller tables almost as powerful as LR(1).
 Used in most practical parser generators (YACC,
Bison).
Comparison:
Parser Lookahead Table Size Power Practicality
SLR FOLLOW sets Small Limited Educational
LR(1) Exact lookahead Large Very high Theoretical
Merged Almost
LALR Moderate Practical use
lookahead high

8. Using Ambiguous Grammars (Section

4.8)
 Ambiguity: when a grammar allows multiple parse
trees for the same string.
 Examples: arithmetic expressions and “dangling else”
problem.
 Ambiguity can be:
1. Removed — by rewriting grammar rules.
2. Controlled — using precedence and
associativity rules.
Precedence Rules
 Decide which operator binds stronger.
 Example: * > +.
Associativity Rules
 Decide grouping direction when operators have equal
precedence.
 Example: - is left associative, so a - b - c means
(a - b) - c.
Dangling Else
 Resolved by giving higher precedence to else than
then.
 Ensures else always matches the nearest unmatched
if.

9. Error Recovery in LR Parsing (Section 4.9)

 LR parsers detect syntax errors immediately when
no valid table entry exists.
 Error recovery allows parsing to continue after an
error.
Common Techniques
Technique Description Example
Skip input until synchronizing Skip until ; or
Panic Mode
symbol found }
Local corrections like Insert missing
Phrase-Level
insertion/deletion )
Error stmt →
Add special rules to grammar error ';'
Productions
Global Find minimal edits
Too costly
Correction (theoretical only)

 Panic mode is most widely used in practice because

it is simple and effective.
10. Key Concepts of LR Parsing
 Shift: push next token onto stack.
 Reduce: replace handle on stack with left-hand side
of production.
 Accept: successful parse when start symbol
recognized.
 Error: no valid action — initiate recovery.
 Determinism: only one valid action for each (state,
symbol) pair in a valid grammar.

11. Overall Comparison of Parsing Methods

Category Top-Down (LL) Bottom-Up (LR)
Leftmost Rightmost derivation (in
Direction
derivation reverse)
Start Point Start symbol Input string
Grammar No left
Handles most grammars
Restrictions recursion
Sometimes
Backtracking Never needed
needed
Error Detection Later Immediate
More powerful,
Efficiency Simple, fast
complex
Usage Simpler Real-world languages
 Category Top-Down (LL) Bottom-Up (LR)
languages

12. Summary Points for Students

1. Parsing checks syntactic structure using CFGs.
2. Top-down parsers predict productions, suitable for
simple grammars.
3. Bottom-up parsers reduce input to the start symbol,
suitable for complex languages.
4. LR parsers are the most powerful deterministic
parsers.
5. SLR, Canonical LR(1), and LALR differ in
precision and table size.
6. Ambiguous grammars are controlled using
precedence and associativity rules.
7. Error recovery makes the parser robust and user-
friendly.
8. LALR parsing is the industry standard due to its
balance of power and efficiency.

Section 4.1 – Introduction: 40 Short

Questions and Answers
1. What is the main function of the syntax analysis phase?
Ans: To check whether the sequence of tokens follows
the grammatical rules of the programming language.
2. What is another name for syntax analysis?
Ans: Parsing.
3. What does the syntax analyzer take as input?
Ans: A stream of tokens produced by the lexical analyzer.
4. What is the output of the syntax analyzer?
Ans: A parse tree (or syntax tree).
5. What does a parse tree represent?
Ans: The grammatical structure of the source program
according to the language grammar.
6. What type of grammar does the parser use?
Ans: Context-Free Grammar (CFG).
7. What is the role of the syntax analyzer in the compiler?
Ans: It organizes tokens into a hierarchical structure and
checks grammatical correctness.
8. What comes before the syntax analyzer in compilation?
Ans: The lexical analyzer.
9. What comes after the syntax analyzer in compilation?
Ans: The semantic analyzer.
10. What is a “token”?
Ans: The smallest meaningful unit in source code, such as
a keyword, identifier, or symbol.
11. What is the difference between lexical analysis and
syntax analysis?
Ans: Lexical analysis deals with token formation; syntax
analysis deals with token arrangement according to
grammar.
12. What is the main job of parsing?
Ans: To ensure the source program is syntactically valid.
13. Why do we use context-free grammars in syntax
analysis?
Ans: Because they can express nested structures like
loops and conditionals easily.
14. What is the “start symbol” in a grammar?
Ans: The nonterminal symbol from which all valid
sentences of the language can be derived.
15. What is a production rule?
Ans: A rule that defines how a nonterminal can be
replaced by a combination of terminals and nonterminals.
16. What is an example of a production rule?
Ans: E → E + T | T
17. What is a terminal symbol?
Ans: A basic symbol that cannot be replaced further (e.g.,
actual tokens like +, id).
18. What is a nonterminal symbol?
Ans: A symbol that can be replaced by other symbols
according to production rules.
19. Why is syntax analysis important?
Ans: Because it detects structural errors early and ensures
correct interpretation by later stages.
20. What kind of errors does the parser detect?
Ans: Syntax errors.
21. What happens when a syntax error is detected?
Ans: The parser reports it and tries to recover to continue
parsing.
22. What are the two major types of parsers?
Ans: Top-down parsers and Bottom-up parsers.
23. What is the purpose of top-down parsing?
Ans: To start from the root (start symbol) and predict
productions to match the input.
24. What is the purpose of bottom-up parsing?
Ans: To start from the input and reduce it to the start
symbol.
25. Which type of parser is more powerful?
Ans: Bottom-up parsers.
26. What are the typical parsing techniques used in
compilers?
Ans: Recursive-descent, predictive, shift-reduce, and LR
parsing.
27. What is a “derivation”?
Ans: A sequence of production applications that
generates a string from the start symbol.
28. What is a “leftmost derivation”?
Ans: Derivation in which the leftmost nonterminal is
always replaced first.
29. What is a “rightmost derivation”?
Ans: Derivation in which the rightmost nonterminal is
replaced first.
30. Which derivation is used by top-down parsers?
Ans: Leftmost derivation.
31. Which derivation is used by bottom-up parsers?
Ans: Rightmost derivation in reverse.
32. What is a sentential form?
Ans: A string of terminals and nonterminals derived from
the start symbol.
33. What is meant by syntax error detection?
Ans: Identifying parts of code that do not follow the
grammar rules.
34. Can a syntactically correct program still have errors?
Ans: Yes, it may still have semantic or logical errors.
35. Why is syntax analysis performed before semantic
analysis?
Ans: Because semantics depend on the correct syntactic
structure.
36. What is the structure that represents hierarchical
relationships in a program?
Ans: The parse tree.
37. What is another name for a syntax tree?
Ans: Concrete syntax tree.
38. How is syntax analysis helpful to the compiler’s next
phase?
Ans: It provides a structured representation that semantic
analysis can use to assign meaning.
39. Can all grammars be parsed by simple parsers?
Ans: No, some grammars are too complex or ambiguous
for simple parsing methods.
40. What is the final goal of syntax analysis?
Ans: To construct a correct and complete parse tree for
the input program.

Section 4.2 – The Role of the Parser: 40

Short Questions and Answers
1. What is the main task of the parser?
Ans: The parser checks whether the input tokens follow
the grammar of the programming language.
2. What does the parser receive as input?
Ans: Tokens generated by the lexical analyzer.
3. What does the parser produce as output?
Ans: A parse tree or syntax tree.
4. What does the parse tree show?
Ans: The hierarchical structure of the source program
according to grammar rules.
5. What part of the compiler does the parser follow?
Ans: It follows the lexical analyzer.
6. What comes after the parser in the compilation
process?
Ans: The semantic analyzer.
7. What is the purpose of parsing in a compiler?
Ans: To verify that the source program is syntactically
correct.
8. What are the two main types of parsers?
Ans: Top-down parsers and bottom-up parsers.
9. What is a top-down parser?
Ans: A parser that starts from the start symbol and
predicts productions to match the input.
10. What is a bottom-up parser?
Ans: A parser that starts from the input and reduces it to
the start symbol.
11. What is the difference between syntax analysis and
semantic analysis?
Ans: Syntax analysis checks structure; semantic analysis
checks meaning.
12. What is the role of the parser in error detection?
Ans: It identifies syntax errors and reports them with
meaningful messages.
13. Why is error recovery important in parsing?
Ans: It allows the parser to continue checking the rest of
the program after an error.
14. What is the bridge between lexical and semantic
analysis?
Ans: The syntax analyzer (parser).
15. How does the parser use grammar rules?
Ans: It applies production rules to check the correct order
of tokens.
16. What is a grammatical structure in programming?
Ans: The correct arrangement of tokens that form valid
statements or expressions.
17. What kind of grammar is used by a parser?
Ans: Context-Free Grammar (CFG).
18. What is meant by "syntactic structure"?
Ans: The way in which language constructs are organized
hierarchically.
19. Why can’t the lexical analyzer perform parsing?
Ans: Because lexical analysis only identifies tokens, not
their hierarchical relationships.
20. What is a syntax error?
Ans: A violation of the grammatical rules of the
programming language.
21. Give an example of a syntax error.
Ans: Missing a semicolon, like int x = 5 instead of
int x = 5;.

22. What should a good parser do when it finds an error?

Ans: Report the error clearly and try to recover from it.
23. What is the role of the parser in code generation?
Ans: It provides a structured tree that helps later stages
generate machine code.
24. How does the parser help in semantic analysis?
Ans: It provides the structure needed to assign meaning to
expressions.
25. What is the start symbol in a grammar?
Ans: The main nonterminal symbol from which parsing
begins.
26. What is a production rule used for?
Ans: To define how nonterminals can be expanded into
terminals and other nonterminals.
27. What are terminals in grammar?
Ans: The basic symbols (tokens) of the language, such as
id, if, or +.

28. What are nonterminals in grammar?

Ans: Variables representing groups or patterns of tokens,
like expr or stmt.
29. How does the parser check correctness of a program?
Ans: By comparing input tokens with the grammar rules.
30. What are the two main strategies of parsing?
Ans: Predictive (top-down) and shift-reduce (bottom-up)
parsing.
31. What does “predictive parsing” mean?
Ans: Predicting which production to use based on the
next input symbol.
32. What does “shift-reduce parsing” mean?
Ans: Shifting input symbols onto a stack and reducing
them to grammar symbols.
33. What is the role of FIRST and FOLLOW sets?
Ans: They help the parser decide which production rule
to apply.
34. What is a parse tree used for in later stages of
compilation?
Ans: For semantic checking, intermediate code
generation, and optimization.
35. What should happen if the parser cannot match input
tokens with any production?
Ans: It should report a syntax error.
36. Why is syntax analysis essential for compiler
correctness?
Ans: It ensures the program follows the language’s
structure before meaning is interpreted.
37. What is meant by “syntactically valid” code?
Ans: Code that follows all the grammatical rules of the
language.
38. Why is parsing called “syntax-directed”?
Ans: Because it is guided by the grammar (syntax) rules
of the language.
39. What are the three possible outcomes of parsing?
Ans: Accept (valid), reject (invalid), or error recovery
(correctable).
40. In one sentence, summarize the role of the parser.
Ans: The parser checks grammar correctness, builds a
parse tree, and ensures structural validity for later
compiler phases.

Section 4.3 – Context-Free Grammars: 40

Short Questions and Answers
1. What is the full form of CFG?
Ans: Context-Free Grammar.
2. What is a Context-Free Grammar used for?
Ans: To describe the syntax (structure) of a programming
language.
3. Why is it called "context-free"?
Ans: Because each production rule can be applied
regardless of the surrounding symbols.
4. What are the main components of a CFG?
Ans: Terminals, nonterminals, a start symbol, and a set of
production rules.
5. What is a terminal in CFG?
Ans: A basic symbol of the language, such as an actual
token like id, +, or if.
6. What is a nonterminal in CFG?
Ans: A variable that represents a group or pattern of
symbols (e.g., E, T, stmt).
7. What is a production rule?
Ans: A rule showing how a nonterminal can be replaced
by a string of terminals and nonterminals.
8. Give an example of a production rule.
Ans: E → E + T | T
9. What does the symbol “→” mean in grammar?
Ans: It means “can be replaced by”.
10. What is a start symbol?
Ans: The nonterminal from which the derivation of all
valid strings begins.
11. What is a sentential form?
Ans: Any string of terminals and nonterminals derived
from the start symbol.
12. What is a derivation?
Ans: The process of repeatedly applying production rules
to generate a string.
13. What is a leftmost derivation?
Ans: A derivation in which the leftmost nonterminal is
always replaced first.
14. What is a rightmost derivation?
Ans: A derivation in which the rightmost nonterminal is
replaced first.
15. What is a parse tree?
Ans: A graphical representation of a derivation showing
how the start symbol expands into the input string.
16. How are parse trees and derivations related?
Ans: Each derivation corresponds to a parse tree that
represents the same structure.
17. What do the leaves of a parse tree represent?
Ans: Terminal symbols (tokens).
18. What do the interior nodes of a parse tree represent?
Ans: Nonterminal symbols.
19. What does the root of a parse tree represent?
Ans: The start symbol of the grammar.
20. What is a language generated by a CFG?
Ans: The set of all strings derivable from the start symbol
using production rules.
21. What is an ambiguous grammar?
Ans: A grammar that allows more than one parse tree for
the same input string.
22. Give an example of an ambiguous input.
Ans: id + id * id can be parsed in two different ways
if grammar rules are unclear.
23. Why is ambiguity undesirable in compilers?
Ans: Because it creates multiple possible meanings for
the same program.
24. Can all programming languages be defined by
unambiguous grammars?
Ans: Most can, but some constructs (like “dangling else”)
require careful design to avoid ambiguity.
25. What is a context-sensitive grammar?
Ans: A grammar where production rules depend on the
surrounding symbols (context).
26. How does CFG differ from context-sensitive
grammar?
Ans: CFG rules can be applied freely without considering
neighboring symbols.
27. Why are CFGs preferred in syntax analysis?
Ans: Because they are simple, powerful, and can be
efficiently parsed.
28. What is meant by grammar simplification?
Ans: Removing useless symbols, unit productions, and
epsilon-productions to make grammar cleaner.
29. What is a null (epsilon) production?
Ans: A rule that allows a nonterminal to produce an
empty string (ε).
30. What is a unit production?
Ans: A rule where one nonterminal produces another
nonterminal, e.g., A → B.
31. What is a useless symbol in grammar?
Ans: A symbol that cannot derive any terminal string or
cannot be reached from the start symbol.
32. What is the purpose of eliminating useless symbols?
Ans: To make the grammar efficient and reduce parsing
complexity.
33. What is derivation length?
Ans: The number of production steps required to produce
a given string.
34. What are recursive productions?
Ans: Rules where a nonterminal refers to itself, e.g., E →
E + T.

35. What problem does left recursion cause?

Ans: It leads to infinite recursion in top-down parsers.
36. How can left recursion be removed?
Ans: By rewriting grammar in a right-recursive or
iterative form.
37. What is a right-recursive grammar?
Ans: A grammar where recursive calls appear on the right
side of productions.
38. What is the use of grammar rewriting?
Ans: To make grammar suitable for a specific parsing
method like LL(1) or LR.
39. What is the role of CFG in compiler construction?
Ans: It defines the syntactic rules that guide the parser to
build the parse tree.
40. In one line, what is a CFG?
Ans: A formal system that defines how valid statements
and expressions of a language can be generated.

Section 4.4 – Top-Down Parsing: 40 Short

Questions and Answers
1. What is top-down parsing?
Ans: It is a parsing method that starts from the start
symbol and tries to derive the input string step by step.
2. Why is it called “top-down”?
Ans: Because the parser starts from the top (the start
symbol) and moves down toward the input symbols.
3. What kind of derivation does top-down parsing use?
Ans: Leftmost derivation.
4. What is the main goal of top-down parsing?
Ans: To find a leftmost derivation for the input string.
5. What is the starting point of a top-down parser?
Ans: The grammar’s start symbol.
6. What does the parser do at each step?
Ans: It replaces a nonterminal with one of its productions
that matches the next input tokens.
7. What are the main types of top-down parsers?
Ans: Recursive-Descent Parser and Predictive Parser.
8. What is a recursive-descent parser?
Ans: A parser made up of mutually recursive functions,
each corresponding to a grammar nonterminal.
9. What is predictive parsing?
Ans: A type of recursive-descent parsing that uses
lookahead to choose the correct production without
backtracking.
10. Why is backtracking inefficient?
Ans: Because the parser may need to undo previous
choices and reprocess input multiple times.
11. What is a major problem with recursive-descent
parsers?
Ans: They cannot handle left-recursive grammars.
12. What does left recursion mean?
Ans: When a nonterminal appears first on the right side of
its own production (e.g., E → E + T).
13. Why does left recursion cause problems?
Ans: Because it can lead to infinite recursion in a
recursive-descent parser.
14. What is right recursion?
Ans: When the recursive call appears on the right side,
e.g., E → T + E.
15. Can right recursion be handled safely in top-down
parsers?
Ans: Yes, it doesn’t cause infinite recursion.
16. How can left recursion be eliminated?
Ans: By rewriting the grammar into an equivalent right-
recursive or iterative form.
17. Give an example of removing left recursion.
Ans:
Original: E → E + T | T
Rewritten:

Section 4.5 – Bottom-Up Parsing: 40 Short

Questions and Answers
1. What is bottom-up parsing?
Ans: It is a parsing technique that starts from the input
string and reduces it step by step to the start symbol.
2. Why is it called bottom-up parsing?
Ans: Because it builds the parse tree from the leaves
(tokens) up to the root (start symbol).
3. What kind of derivation does bottom-up parsing
follow?
Ans: Rightmost derivation in reverse.
4. What is the main goal of bottom-up parsing?
Ans: To find the sequence of reductions that produce the
start symbol.
5. What are the two main actions in bottom-up parsing?
Ans: Shift and Reduce.
6. What is a “shift” operation?
Ans: Moving the next input symbol onto the parsing
stack.
7. What is a “reduce” operation?
Ans: Replacing a sequence of grammar symbols on the
stack (a handle) with a nonterminal.
8. What is a “handle”?
Ans: A substring that matches the right-hand side of a
production rule and can be reduced to its left-hand side.
9. What does “handle pruning” mean?
Ans: Repeatedly finding and reducing handles until the
start symbol is obtained.
10. What is the final goal of handle pruning?
Ans: To reduce the entire input to the start symbol of the
grammar.
11. What data structure is used in bottom-up parsing?
Ans: A stack.
12. What are the typical contents of the stack in shift-
reduce parsing?
Ans: Grammar symbols (terminals and nonterminals) and
parser states.
13. What are the four main actions a shift-reduce parser
can take?
Ans: Shift, Reduce, Accept, and Error.
14. What does the “Accept” action mean?
Ans: The input string has been successfully parsed and
matches the grammar.
15. What does the “Error” action mean?
Ans: The parser cannot continue because the input is
invalid according to the grammar.
16. What is a “conflict” in bottom-up parsing?
Ans: When the parser’s table allows more than one
possible action in a given situation.
17. What are the two types of conflicts in bottom-up
parsing?
Ans: Shift/Reduce conflict and Reduce/Reduce conflict.
18. What is a shift/reduce conflict?
Ans: When the parser cannot decide whether to shift the
next input symbol or reduce the current stack contents.
19. What is a reduce/reduce conflict?
Ans: When the parser cannot decide which of two
possible reductions to apply.
20. What kind of grammars cause conflicts?
Ans: Ambiguous grammars.
21. What is an example of a shift/reduce conflict?
Ans: The “dangling else” problem in if-then-else
statements.
22. How can conflicts be reduced?
Ans: By rewriting the grammar or defining precedence
and associativity rules.
23. What is operator-precedence parsing?
Ans: A type of bottom-up parsing that uses precedence
relations among operators to guide parsing.
24. When can operator-precedence parsing be used?
Ans: When no two operators have equal precedence and
no ambiguity exists between them.
25. What are the three operator-precedence relations?
Ans:
 Less than (<·)
 Equal to (=·)
 Greater than (>·)
26. What does a <· b mean in operator-precedence
parsing?
Ans: Operator a has lower precedence than operator b.
27. What does a >· b mean?
Ans: Operator a has higher precedence than operator b.
28. What does a =· b mean?
Ans: Operators a and b have the same precedence level.
29. What is a precedence table?
Ans: A table showing the precedence relationships among
operators.
30. What is the main advantage of operator-precedence
parsing?
Ans: It is simple and efficient for arithmetic and
expression-based grammars.
31. What is the main disadvantage of operator-precedence
parsing?
Ans: It cannot handle complex or nested language
structures.
32. What kind of grammar is suitable for operator-
precedence parsing?
Ans: Operator-precedence grammar — where precedence
relations are clearly defined.
33. What does “viable prefix” mean in bottom-up
parsing?
Ans: The portion of the input that can appear on the stack
of a shift-reduce parser at any point.
34. What is the significance of a viable prefix?
Ans: It helps the parser ensure reductions occur at correct
positions.
35. What is the relationship between bottom-up parsing
and LR parsing?
Ans: LR parsing is a form of bottom-up parsing that uses
deterministic tables for shifting and reducing.
36. What is the role of grammar in bottom-up parsing?
Ans: It defines how reductions should occur and which
sequences form valid handles.
37. Why is bottom-up parsing called “shift-reduce”
parsing?
Ans: Because it repeatedly shifts input symbols and
reduces handles until the parse is complete.
38. What are the strengths of bottom-up parsers?
Ans: They can handle a large class of grammars and
detect errors quickly.
39. What is the main difference between top-down and
bottom-up parsing?
Ans: Top-down starts from the start symbol, while
bottom-up starts from the input string.
40. In one line, what is the purpose of bottom-up parsing?
Ans: To construct the parse tree from the input tokens
upward by performing a series of shifts and reductions.

Section 4.6 – Introduction to LR Parsing:

Simple LR (SLR)
(Covers LR(0) items, canonical collection, and SLR
parsing tables)

1. What does LR stand for in LR parsing?

Ans: L stands for Left-to-right scanning, and R stands for
constructing a Rightmost derivation in reverse.
2. What kind of parsing method is LR parsing?
Ans: It is a bottom-up, table-driven parsing method.
3. Why is LR parsing called deterministic?
Ans: Because for each state and input symbol, there is at
most one valid action.
4. What is the main goal of LR parsing?
Ans: To parse a large class of context-free grammars
efficiently without backtracking.
5. Who introduced LR parsing?
Ans: Donald Knuth in 1965.
6. What is the main advantage of LR parsing?
Ans: It can handle all deterministic context-free
grammars.
7. What are the three common types of LR parsers?
Ans: SLR (Simple LR), Canonical LR(1), and LALR(1).
8. Which LR parser is simplest to construct?
Ans: SLR (Simple LR).
9. Which LR parser is most commonly used in practice?
Ans: LALR parser.
10. What is an LR(0) item?
Ans: A production with a dot (•) indicating how much of
the production has been seen so far.
11. Give an example of an LR(0) item.
Ans: For rule E → E + T, items are:
E → •E + T, E → E• + T, E → E + •T, and E → E +
T•.

12. What does the dot (•) represent in an LR(0) item?

Ans: The current position of the parser within the
production.
13. What are the two main operations in building LR
items?
Ans: Closure and Goto.
14. What is the Closure operation?
Ans: It adds new items to a state whenever a nonterminal
appears immediately after the dot.
15. What is the Goto operation?
Ans: It defines transitions between states when the parser
reads a particular symbol.
16. What is the purpose of constructing item sets?
Ans: Each set represents a possible state of the parser
during parsing.
17. What is the Canonical Collection of LR(0) items?
Ans: The complete set of all item sets (states) created
using closure and goto functions.
18. What is an augmented grammar?
Ans: A grammar with a new start rule added to mark the
beginning of parsing, e.g., S' → S.
19. Why do we add an augmented grammar?
Ans: To clearly define the point at which parsing should
accept the input.
20. What does the initial item set (I₀) contain?
Ans: The closure of the augmented start production S' →
•S.

21. How are states represented in the LR parser?

Ans: Each state corresponds to an item set.
22. What are the two tables used in an LR parser?
Ans: ACTION table and GOTO table.
23. What does the ACTION table specify?
Ans: Parser actions for terminals (Shift, Reduce, Accept,
or Error).
24. What does the GOTO table specify?
Ans: Next state transitions for nonterminals.
25. What does “Shift” mean in the ACTION table?
Ans: Push the input symbol and move to a new state.
26. What does “Reduce” mean in the ACTION table?
Ans: Replace the handle on the stack with the left-hand
side nonterminal.
27. What does “Accept” mean in LR parsing?
Ans: The input has been successfully parsed and matches
the grammar.
28. What does an “Error” entry in the table mean?
Ans: The parser cannot continue — syntax error detected.
29. How does SLR differ from LR(1)?
Ans: SLR uses FOLLOW sets for reductions instead of
explicit lookaheads.
30. What is the FOLLOW set used for in SLR parsing?
Ans: To determine where reduce actions should occur.
31. What does SLR stand for?
Ans: Simple LR parser.
32. Why is SLR called "Simple"?
Ans: Because it uses a simpler way (FOLLOW sets) to
decide reduce actions.
33. What is a typical structure of an LR parser?
Ans: It consists of an input buffer, stack, parsing tables
(ACTION and GOTO), and a driver program.
34. What is the driver program responsible for?
Ans: Controlling parsing steps and applying shift or
reduce actions as per tables.
35. What kind of errors does LR parsing detect?
Ans: Syntax errors — and it detects them as soon as
possible.
36. What is the complexity of constructing an SLR
parser?
Ans: It is less complex than LR(1) or LALR parsers.
37. What is the main limitation of SLR parsing?
Ans: It cannot handle some grammars that LR(1) can
because of conflicts.
38. What is a conflict in SLR parsing?
Ans: When both a shift and a reduce (or two reduces) are
possible for the same input.
39. What kind of grammar causes SLR conflicts?
Ans: Ambiguous or complex grammars.
40. In one line, what is SLR parsing?
Ans: A simple, bottom-up, table-driven parsing technique
using FOLLOW sets to guide reductions.
Section 4.7 – More Powerful LR Parsers
(Canonical LR(1) and LALR)
(Covers 4.7.1 Canonical LR(1) Parsing Tables and
4.7.2 LALR Parsing Tables)

1. What does LR(1) stand for?

Ans: Left-to-right scanning with one lookahead symbol
and rightmost derivation in reverse.
2. Why is LR(1) called more powerful than SLR?
Ans: Because it uses explicit lookahead symbols to make
parsing decisions, avoiding many conflicts.
3. What is the main weakness of SLR parsing?
Ans: It can cause shift/reduce or reduce/reduce conflicts
in certain grammars.
4. What does LR(1) parsing solve?
Ans: It resolves conflicts that occur in SLR parsing by
considering specific lookahead symbols.
5. What is an LR(1) item?
Ans: An LR(0) item combined with one lookahead
symbol, written as [A → α • β, a].
6. What does the lookahead symbol represent in LR(1)?
Ans: The terminal that can legally appear immediately
after the nonterminal A.
7. How does LR(1) improve accuracy?
Ans: By deciding reductions only when the lookahead
symbol matches expected terminals.
8. Give an example of an LR(1) item.
Ans: [E → E + •T, )] means the parser expects a T
next, followed by a ) after completion.
9. What is the Closure operation in LR(1)?
Ans: It adds items for nonterminals after the dot, with
appropriate lookahead symbols.
10. What is the GOTO operation in LR(1)?
Ans: It transitions between item sets based on the next
symbol after the dot.
11. What is a Canonical Collection of LR(1) items?
Ans: The complete set of item sets constructed using
closure and goto, considering lookaheads.
12. What is the structure of an LR(1) parser?
Ans: It consists of ACTION and GOTO tables, similar to
SLR, but built using LR(1) items.
13. What are the entries of the ACTION table in LR(1)?
Ans: Shift, Reduce, Accept, and Error.
14. What are the entries of the GOTO table?
Ans: Next states for nonterminals.
15. Why are LR(1) tables large?
Ans: Because each state includes unique lookahead
symbols, leading to many item sets.
16. How does LR(1) handle conflicts better than SLR?
Ans: It differentiates reductions based on specific
lookahead symbols rather than general FOLLOW sets.
17. What does Canonical LR(1) mean?
Ans: The most detailed LR parser, using all possible
LR(1) items without merging any states.
18. What is the main drawback of Canonical LR(1)?
Ans: It produces a very large number of states, making
the tables difficult to manage.
19. How many states can Canonical LR(1) generate
compared to SLR?
Ans: Many times more — sometimes hundreds instead of
tens.
20. What does LALR stand for?
Ans: LookAhead LR parser.
21. How does LALR differ from LR(1)?
Ans: LALR merges states in the LR(1) automaton that
have identical cores (same items without lookahead
symbols).
22. What is the “core” of an LR(1) item?
Ans: The part of the item without the lookahead symbol,
i.e., the LR(0) part.
23. What is the purpose of merging LR(1) states?
Ans: To reduce the size of the parsing table while
maintaining accuracy.
24. What is the main advantage of LALR parsing?
Ans: It has almost the same power as LR(1) but with
table sizes as small as SLR.
25. Why is LALR parsing widely used in practice?
Ans: Because it offers a good balance between power and
efficiency.
26. Which parser generator tools use LALR parsing?
Ans: YACC (Yet Another Compiler Compiler) and
Bison.
27. How does LALR handle lookahead symbols after
merging?
Ans: It unites the lookahead sets of merged states.
28. Can merging states cause new conflicts in LALR?
Ans: Yes, sometimes merging introduces new
shift/reduce or reduce/reduce conflicts.
29. Why are conflicts in LALR rare in real programming
grammars?
Ans: Because most language grammars are designed to be
LALR-compatible.
30. What is the relation between SLR, LALR, and LR(1)?
Ans: SLR < LALR < LR(1) in terms of power and
accuracy.
31. Which LR parser is smallest in size?
Ans: SLR parser.
32. Which LR parser is largest in size?
Ans: Canonical LR(1) parser.
33. Which LR parser provides the best trade-off between
power and size?
Ans: LALR parser.
34. What is the main characteristic of all LR parsers?
Ans: They use a deterministic table-driven approach and
never require backtracking.
35. What kind of derivation do LR parsers follow?
Ans: Rightmost derivation in reverse.
36. What is a parsing conflict?
Ans: When more than one action (shift/reduce or
reduce/reduce) is possible in a parser table.
37. What type of grammars are best suited for LR
parsing?
Ans: Deterministic context-free grammars.
38. Why is LALR often preferred over Canonical LR(1)?
Ans: Because it produces smaller tables without losing
much parsing power.
39. How does an LALR parser behave compared to an
LR(1) parser?
Ans: It behaves almost identically in parsing most real
programming languages.
40. In one line, what is the purpose of LALR and LR(1)
parsers?
Ans: To provide accurate, efficient, and deterministic
parsing for complex programming languages.

Section 4.8 – Using Ambiguous Grammars:

40 Short Questions and Answers

1. What is an ambiguous grammar?

Ans: A grammar is ambiguous if one string can have two
or more different parse trees.
2. Why is grammar ambiguity a problem?
Ans: Because the same input may produce different
meanings, making it unclear how to interpret the program.
3. What is a parse tree?
Ans: A tree that represents how a string is derived from a
grammar’s start symbol.
4. What happens when a grammar is ambiguous?
Ans: The parser can’t decide which parse tree or
derivation to choose.
5. Give an example of an ambiguous expression.
Ans: id + id * id — it can be parsed as either (id +
id) * id or id + (id * id).
6. What is the main source of ambiguity in arithmetic
expressions?
Ans: Operator precedence and associativity.
7. What is operator precedence?
Ans: It defines which operator should be evaluated first.
8. What is operator associativity?
Ans: It defines how operators of the same precedence are
grouped — left or right.
9. What does left associativity mean?
Ans: Operations are grouped from left to right (e.g., a -
b - c = (a - b) - c).

10. What does right associativity mean?

Ans: Operations are grouped from right to left (e.g., a =
b = c = a = (b = c)).

11. What kind of grammar causes ambiguity in arithmetic

expressions?
Ans: Grammars where operators are not assigned clear
precedence or associativity.
12. What is the most famous example of ambiguity in
programming languages?
Ans: The dangling else problem.
13. What is the dangling else problem?
Ans: It’s unclear which if statement an else clause
belongs to.
14. Write the grammar that causes dangling else
ambiguity.
Ans:
stmt → if expr then stmt
| if expr then stmt else stmt
| other

15. In the dangling else problem, which if gets the

else?
Ans: It can belong to either the inner or outer if, causing
ambiguity.
16. How is the dangling else ambiguity resolved?
Ans: By assigning the else to the nearest unmatched if.
17. How can ambiguity be removed from a grammar?
Ans: By rewriting the grammar to make choices explicit.
18. What are the two main ways to handle ambiguity?
Ans: (1) Rewrite the grammar to be unambiguous, or (2)
Control ambiguity using rules.
19. What kind of rules can control ambiguity?
Ans: Operator precedence and associativity rules.
20. What is an example of a rule-based solution?
Ans: Declaring * has higher precedence than +.
21. What is an unambiguous version of the grammar E →
E + E | E * E | id?
Ans:
E → E + T | T
T → T * F | F
F → id

22. In the above unambiguous grammar, which operator

has higher precedence?
Ans: Multiplication (*) has higher precedence than
addition (+).
23. How does rewriting a grammar remove ambiguity?
Ans: By restricting the order and structure in which rules
can be applied.
24. What is a practical benefit of keeping an ambiguous
grammar?
Ans: It can be simpler and easier to write if the parser can
handle the ambiguity.
25. How do parser generators handle ambiguous
grammars?
Ans: They use precedence and associativity declarations
to resolve conflicts automatically.
26. Which type of parser can use such rules easily?
Ans: LR parsers (especially LALR parsers like YACC).
27. What is a precedence rule in parser generators?
Ans: A rule specifying which operator should be
evaluated first in case of conflict.
28. What is an associativity rule in parser generators?
Ans: A rule defining how operators of the same
precedence are grouped.
29. Give an example of a precedence declaration.
Ans:
%left '+' '-'
%left '*' '/'

30. How do these declarations help in parsing?

Ans: They tell the parser which action (shift or reduce) to
choose during conflicts.
31. Can ambiguity always be removed?
Ans: Not always easily; sometimes it’s more practical to
manage it instead.
32. Why do real-world languages often allow controlled
ambiguity?
Ans: Because it simplifies the grammar and makes
parsing efficient.
33. What kind of ambiguity do parentheses eliminate?
Ans: Operator-precedence ambiguity in expressions.
34. What does if-then-else ambiguity teach about
parsing?
Ans: That language design and grammar rules must
match carefully to avoid confusion.
35. What is a shift/reduce conflict in ambiguous
grammars?
Ans: When the parser cannot decide whether to shift the
next symbol or reduce the current one.
36. What is a reduce/reduce conflict?
Ans: When two different reductions are possible for the
same input and state.
37. Which parsing method can still work with controlled
ambiguity?
Ans: LR parsing, with proper precedence and
associativity settings.
38. What is the advantage of using ambiguous grammars
with rules?
Ans: It allows concise grammars without losing control
over parsing behavior.
39. What is the main trade-off when using ambiguous
grammars?
Ans: Simplicity of grammar versus clarity of meaning.
40. In one line, what is the goal of handling ambiguous
grammars?
Ans: To allow simple grammars while ensuring unique
and correct parsing through precedence and associativity
rules.

Section 4.9 – Error Recovery in LR Parsing:

40 Short Questions and Answers
1. What is error recovery in parsing?
Ans: It is the process of detecting syntax errors and
continuing parsing to find more errors.
2. Why is error recovery important?
Ans: Because a good compiler should not stop after one
error; it should detect multiple errors in one run.
3. When does an LR parser detect a syntax error?
Ans: When it finds no valid action for the current state
and input symbol in the ACTION table.
4. What are the main goals of error recovery?
Ans: To report errors clearly, minimize false messages,
and continue parsing safely.
5. What is the best property of LR parsers in error
detection?
Ans: They detect errors as soon as possible — at the
exact point where the error occurs.
6. Give an example of a syntax error detected early.
Ans: In id + * id, the parser detects an error when it
sees + *.
7. What are the main types of program errors?
Ans: Lexical errors, syntax errors, semantic errors, and
logical errors.
8. Which kind of errors does the parser handle?
Ans: Syntax errors.
9. What is a lexical error?
Ans: An invalid token from the scanner, e.g., @name.
10. What is a semantic error?
Ans: A type or meaning error, e.g., true + 5.
11. What is a logical error?
Ans: An error in program logic, e.g., while(1){}
causing infinite loop.
12. What are common causes of syntax errors?
Ans: Missing operators, unbalanced parentheses, extra
symbols, or misplaced keywords.
13. What is an example of a missing operator error?
Ans: Writing a b + c instead of a + b + c.
14. What is an example of unbalanced parentheses?
Ans: Writing (a + b instead of (a + b).
15. What is the goal of a good error recovery strategy?
Ans: To fix or skip minimal input and continue parsing
properly.
16. What are the common methods of error recovery in
LR parsing?
Ans: Panic-mode recovery, phrase-level recovery, error
productions, and global correction.
17. What is panic-mode recovery?
Ans: It skips input symbols until a synchronizing token is
found.
18. What is a synchronizing token?
Ans: A symbol where parsing can safely restart, like ;, },
or end.
19. How does panic-mode work?
Ans: It pops states from the stack until a safe point and
skips input until a synchronizing symbol is seen.
20. What is the main advantage of panic-mode recovery?
Ans: It is simple, fast, and prevents long cascades of
errors.
21. What is the main drawback of panic-mode recovery?
Ans: It may skip large portions of input unnecessarily.
22. What is phrase-level recovery?
Ans: It performs local corrections, like inserting or
deleting small symbols to fix the input.
23. Give an example of phrase-level correction.
Ans: In if (x > y then z = 1;, inserting a missing
) after y.

24. What are the advantages of phrase-level recovery?

Ans: It fixes errors locally and avoids skipping large code
sections.
25. What are the disadvantages of phrase-level recovery?
Ans: It’s harder to implement and may guess wrong
corrections.
26. What are error productions?
Ans: Extra grammar rules added to handle common errors
gracefully.
27. Give an example of an error production.
Ans: stmt → error ';' handles invalid statements
ending with ;.
28. What is the advantage of error productions?
Ans: They allow customized error messages for specific
mistakes.
29. What is the disadvantage of error productions?
Ans: They make the grammar more complex.
30. What is global correction?
Ans: A theoretical method that finds the smallest number
of changes needed to make input valid.
31. Why isn’t global correction used in practice?
Ans: Because it’s computationally expensive and slow.
32. Which error recovery method is most widely used in
LR parsers?
Ans: Panic-mode recovery.
33. How does panic-mode avoid cascading errors?
Ans: By skipping to a safe point before continuing,
preventing multiple false errors.
34. What is meant by cascading errors?
Ans: Multiple error messages triggered by one actual
mistake.
35. What is an example of a cascading error?
Ans: Missing a semicolon causes the parser to
misinterpret several following lines as errors.
36. What does a good error message include?
Ans: The unexpected symbol and what was expected
instead.
37. Give an example of a helpful error message.
Ans: “Syntax Error: Unexpected ‘*’, expected identifier
or ‘(’.”
38. How does an LR parser handle errors internally?
Ans: By consulting the ACTION table, popping states,
and synchronizing input.
39. What is the benefit of error recovery for
programmers?
Ans: It helps them correct multiple syntax mistakes in
one compilation.
40. In one line, what is the goal of LR error recovery?
Ans: To detect syntax errors early, report them clearly,
and continue parsing safely.

…
Great — here are 10 simple, student-friendly assignments for a Compiler Construction
course, each followed by a clear solution (explanations + short traces or code/pseudocode where
helpful). Problems are kept small so students can complete them in a short lab session.

1. Assignment 1 — Token specification (lexer)

Problem: Write regular expressions for these tokens: identifier, integer literal,
whitespace, and the symbols +, *, (, ). Then show a tokenizer output for the input sum1
+ 23 * (var_2).

Solution:
Regular expressions (simple form)

 identifier: [A-Za-z_][A-Za-z0-9_]*
 integer literal: [0-9]+
 whitespace: [ \t\n\r]+ (skip)
 plus: \+
 star: \*
 left paren: \(
 right paren: \)

Tokenization of sum1 + 23 * (var_2) (ignoring whitespace)

1. identifier("sum1")
2. +
3. integer(23)
4. *
5. (
6. identifier("var_2")
7. )

Short note: lexer returns tokens to parser (token type + lexeme).

2. Assignment 2 — Build NFA from regex and show simple transition table
Problem: For regex a(b|c)*, draw (or describe) the NFA and give a small transition
table for states.

Solution (short): NFA conceptually

 Start state 0 → on a → state 1

 From 1 there is a loop via an intermediate branching: 1 → on b → 1; 1 → on c → 1 (so
(b|c)* means stay in 1 on b or c)
 Accepting state 1.
Transition table (state, input → next states)

(0, b) → ∅
 (0, a) → {1}

 (1, b) → {1}

(1, a) → ∅
 (1, c) → {1}


This NFA accepts strings starting with a followed by zero or more b or c (e.g., a, ab, accb).

3. Assignment 3 — Convert left-recursive grammar to non-left-recursive form

Problem: Given grammar E → E + T | T and T → T * F | F, transform it to an
equivalent grammar without left recursion.

Solution: Eliminate left recursion using standard technique

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

This grammar is suitable for top-down parsing (no left recursion).

4. Assignment 4 — Compute FIRST and FOLLOW sets

Problem: For the grammar in Assignment 3, compute FIRST and FOLLOW for E, E', T,
T', F.

Solution (concise)
FIRST:

 FIRST(F) = { id, ( }
 FIRST(T) = FIRST(F) = { id, ( }
 FIRST(T') = { *, ε }
 FIRST(E) = FIRST(T) = { id, ( }
 FIRST(E') = { +, ε }

FOLLOW:

 FOLLOW(E) includes $ and ) (start symbol E): FOLLOW(E) = { ), $ }

 From productions E → T E' and E' → + T E' so: FOLLOW(T) includes FIRST(E')
minus ε plus FOLLOW(E) if E' can be ε → FOLLOW(T) = { +, ), $ }
 FOLLOW(T') = { +, ), $ } (similar reasoning)
 FOLLOW(F) = { *, +, ), $ }

(Students should compute stepwise: use FIRST rules, then propagate to FOLLOW using
productions; above are final sets.)
 5. Assignment 5 — Build LL(1) parsing table (small)
Problem: Using the transformed grammar (Assignment 3) construct the LL(1) parsing
table (rows = nonterminals E,E',T,T',F; columns = terminals id,(,+,*,),$) and show the
table entries for E and E'.

Solution (key entries)

We only list relevant cells:

 For E and input id or (: E → T E'

 For E' and input +: E' → + T E'
 For E' and input ) or $: E' → ε

Full table would follow FIRST/FOLLOW details computed earlier. This is how the predictive
parser chooses productions.

6. Assignment 6 — Simulate LL(1) parse (trace)

Problem: Using the table entries above, show the stack/input trace to parse id + id.

Solution (trace)
Initial: Stack: [E, $] (here top-left), Input: id + id $

1. Top is E, input id → use E → T E'. Replace E by T E'. Stack: [T, E', $].
2. Top T, input id → use T → F T'. Stack: [F, T', E', $].
3. Top F, input id → F → id. Match id: pop id. Input advances to +. Stack: [T', E', $].
4. Top T', input + → T' → ε (since + in FOLLOW(T')). Pop T'. Stack: [E', $].
5. Top E', input + → E' → + T E'. Replace. Stack: ['+', T, E', $].
6. Match +, advance input to id. Stack: [T, E', $].
7. Repeat steps to match second id. Finally input $, stack $ → accept.
8. Assignment 7 — Write recursive-descent pseudocode for factor and term
Problem: For grammar F → id | ( E ), T → F T' and T' → * F T' | ε, write recursive-
descent functions parseF() and parseT() (pseudocode that uses nextToken() and
match()).

Solution (pseudocode)

function parseF():
if nextToken == 'id':
match('id')
else if nextToken == '(':
match('(')
parseE() // assume parseE exists
match(')')
else:
error("expected id or (")

function parseT():
parseF()
while nextToken == '*':
match('*')
parseF()
Note: parseT uses a loop to implement T' instead of recursion (iterative style), avoiding left
recursion.

8. Assignment 8 — Small shift-reduce parsing trace

Problem: Given grammar S → a A b, A → c | ε. Parse input a c b using shift-reduce
method; show stack and action sequence.

Solution (trace)
Input: a c b $, Stack initial $

1. Shift a: Stack: $ a (action: shift)

2. Now possible to reduce? Right-hand sides: A → c or ε; no reduce yet.
3. Shift c: Stack: $ a c (shift)
4. Reduce A → c: Replace c by A. Stack: $ a A (reduce)
5. Shift b: Stack: $ a A b (shift)
6. Reduce S → a A b: Replace a A b by S. Stack: $ S (reduce)
7. If input $ and stack $ S → accept.
8. Assignment 9 — Build tiny SLR ACTION/GOTO entries (conceptual)
Problem: For grammar S' → S, S → a S b | ε, draw item sets conceptually and state
that ACTION will allow shift on a and reduce on b when appropriate. Give short
explanation why SLR works here.

Solution (concise)

 This grammar produces balanced a...b pairs. The SLR automaton states will include
items like S → • a S b and S → ε •. ACTION for a state with S → • a S b will shift
on a. When a handle ε is at end, reductions occur on FOLLOW(S) which includes b and
$. So reduce on b or $. SLR works since grammar is not ambiguous; FOLLOW-based
reductions are safe here.

10. Assignment 10 — Simple semantic action: evaluate expression during parsing

Problem: Using grammar (transformed) E → T E', E' → + T E' | ε, T → F T', F → id (id
holds numbers), add semantic rules to compute the numeric value of expression 2 + 3
(assume id returns integer value).

Solution (annotated grammar with attributes)

 [Link] = (if id) then integer value of id

 T'. inherited: T'.inh = [Link] or accumulated value
Simpler approach using recursive evaluation:

Pseudocode (recursive-descent with evaluation):

function parseF():
if nextToken == 'id':
val = integerValue([Link])
match('id')
return val

function parseT():
val = parseF()
 while nextToken == '*':
match('*')
right = parseF()
val = val * right
return val

function parseE():
val = parseT()
while nextToken == '+':
match('+')
right = parseT()
val = val + right
return val

For input 2 + 3, parseE() returns 5.

Short note: This uses operator precedence embedded in grammar (T handles * before +), and
returns computed value as attribute val.