Unit II: Syntax Analysis - Comprehensive

Guide
Overview
Syntax analysis, also known as parsing, is a critical phase in the compilation process that
follows lexical analysis. It involves checking whether a sequence of tokens produced by the
lexical analyzer follows the grammatical rules defined by the programming language's
grammar. This comprehensive module covers fundamental concepts, techniques,
algorithms, and practical implementations used in modern syntax analysis.

1. Introduction to Syntax Analysis

Definition and Purpose
Syntax analysis is the process of analyzing a string of symbols (tokens) conforming to the
rules of a formal grammar. It transforms a linear sequence of tokens into a tree structure
(parse tree or Abstract Syntax Tree) that represents the syntactic structure of the source
code. The primary goal is to verify that the token stream is valid according to the language's
grammar and to identify any syntax errors.

Role in Compilation Pipeline

The syntax analyzer (parser) is positioned strategically between the lexical analyzer and
the semantic analyzer in the compilation pipeline:
1. Input Source: Stream of tokens from the lexical analyzer (not individual characters)
2. Processing Stage: Validating token sequence against predefined grammar rules
3. Output Generation: Parse tree, Abstract Syntax Tree (AST), or intermediate code
4. Error Management: Detection, reporting, and recovery from syntax errors

Key Objectives of Syntax Analysis

Grammar Verification: Verify that the token stream conforms precisely to the
language grammar
Parse Tree Construction: Build a structured representation for further compilation
phases
Error Detection: Identify and report syntax errors with location, context, and
suggestions
Recovery Mechanism: Continue parsing after errors to report multiple issues in one
pass
Semantic Preparation: Create structures suitable for semantic analysis and code
generation
2. Error Handling and Recovery in Depth
Understanding Syntax Errors
Syntax errors occur when the token sequence violates the grammatical rules of the
language. These are distinct from semantic errors (which occur during semantic analysis)
and logical errors (which occur during execution).

Common Syntax Error Categories

1. Missing Tokens
Missing operators (e.g., a + b c instead of a + b + c)
Missing semicolons in statement-oriented languages
Missing parentheses or brackets
Missing operands in expressions
2. Unexpected Tokens
Extra operators or symbols
Tokens in wrong positions
Type mismatches in declarations
3. Structural Errors
Unmatched parentheses, braces, or brackets
Incorrect statement nesting
Invalid block structure
4. Invalid Token Sequences
Two operators in succession without operand
Operator without required operands

Error Recovery Strategies

Error recovery is essential to enable the parser to continue after detecting an error,
allowing it to report multiple errors in a single compilation pass rather than stopping at the
first error.

1. Panic Mode Recovery (Simple but Coarse)

Mechanism:
When an error is detected, the parser enters "panic mode"
It discards tokens from the input until it reaches a synchronization point (also
called a sync token)
Common synchronization points: semicolon (;), right brace (}), statement keywords
(if, while, for)

Algorithm:
If error detected:
While input token not in SYNC_SET:
Discard current token
Advance to next token
Resume parsing from synchronization point
Example:
Input: int x = ; y = 5;
↑ Error: missing value

Panic Mode:

1. Detect error at semicolon

2. Discard semicolon (synchronization point)
3. Continue parsing from y = 5;
Advantages:
Simple to implement
Fast error detection
Prevents cascading errors

Disadvantages:
May skip valid code portions
Loss of context information
Limited error correction capability

2. Phrase Level Recovery (Context-Aware)

Mechanism:
The parser performs local corrections on the remaining input
Identifies the minimal edit needed to continue parsing
Common corrections: inserting missing tokens, deleting extra tokens

Correction Operations:
1. Token Insertion: Add missing token and continue
2. Token Deletion: Skip unexpected token and continue
3. Token Replacement: Replace incorrect token with expected one
4. Combination: Apply multiple corrections
Algorithm:

If error detected at token 'a':

Check if 'a' can be corrected by:
1. Inserting a token before 'a'
2. Deleting 'a'
3. Replacing 'a' with correct token
Choose correction with lowest cost
Continue parsing with corrected input
Example:
Input: if (x > y print(x);
↑ Missing ')'

Correction: Insert ')' before 'print'

Result: if (x > y) print(x);
Continue parsing
Advantages:
More context-aware than panic mode
Preserves more valid code
Better error messages with suggestions

Disadvantages:
More complex to implement
Risk of masking deeper errors
Correction may be ambiguous

3. Error Productions (Grammar-Based)

Mechanism:
Include special error productions in the grammar to recognize and handle common
mistakes
These productions explicitly model typical user errors
Parser can recognize error patterns and suggest corrections

Grammar Extension:
Original:
expr → expr '+' term | term
Extended with error productions:
expr → expr '+' term
| expr '+' error
| term

error → /* empty */ // Recognizes missing operand

Example:
Grammar with error productions:
statement → assignment
| if_stmt
| error ';'

if_stmt → 'if' '(' expr ')' statement

| 'if' error statement // Handles missing condition
This allows parser to recover from missing conditions in if statements
Implementation Steps:

1. Identify common error patterns in the language

2. Add error productions to grammar
3. Associate error recovery actions with error productions
4. Generate parser with extended grammar
Advantages:
Systematic approach to error handling
 Enables specific error messages
Provides targeted recovery
Disadvantages:

Grammar becomes more complex

Requires careful design of error productions
May conflict with legitimate grammar rules

4. Global Correction (Optimal but Expensive)

Mechanism:
Attempts to find the minimum edit distance between the current input and a valid
string
Uses dynamic programming (similar to spell-checking algorithms)
Counts minimum number of insertions, deletions, and substitutions needed
Edit Distance Calculation:

edit_distance(input_string, valid_string) =
minimum number of single-character edits (insert, delete, substitute)
required to transform input_string into valid_string
Algorithm (Wagner-Fischer):
Let s be the input string
Let t be a valid string from the grammar
d[i,j] = edit distance between s[1..i] and t[1..j]

d[0,j] = j // j insertions
d[i,0] = i // i deletions
For i from 1 to len(s):
For j from 1 to len(t):
If s[i] = t[j]:
d[i,j] = d[i-1,j-1]
Else:
d[i,j] = 1 + min(
d[i-1,j], // deletion
d[i,j-1], // insertion
d[i-1,j-1] // substitution
)
Return d[len(s), len(t)]

Example:
Input: "int x 5;" (missing '=')
Valid: "int x = 5;"
Edit distance = 1 (one substitution or one insertion)
Correction: Insert '=' at position 8

Advantages:
 Theoretically optimal recovery
Can handle complex error patterns
Finds minimal corrections
Disadvantages:

Computationally expensive (O(n²) or worse)

Requires knowledge of all valid strings
Rarely used in practice for full programs
May choose unexpected corrections

Error Reporting and User Communication

Effective error messages are crucial for programmer productivity. A good error message
should provide:

Components of Effective Error Messages

1. Error Type/Classification
Clear description of what kind of error occurred
Examples: "Missing operand", "Unexpected token", "Mismatched parenthesis"
2. Location Information
Line number: Which line contains the error
Column number: Position in the line
Token pointer: Visual indication of error location
Context: Lines before and after for reference
3. Context Display
Line 15: int x = 5 + ;
↑
Error: Expected expression, found ';'
4. Helpful Suggestions
Possible corrections
Expected tokens at error location
Reference to grammar rules if applicable
Common fixes for this error type
5. Severity Levels
Fatal: Cannot continue compilation
Error: Prevents code generation but compilation continues
Warning: Compilation succeeds but behavior may be unexpected
Note: Informational message

Error Message Examples

Poor Message:
Syntax error at line 5
Good Message:
Line 5, Column 18: Error - Unexpected token ';'
int x = 5 + ;
^
Expected: expression (identifier, number, or '(')
Possible fix: Remove ';' or add operand before ';'
3. Detailed Definitions and Fundamental Concepts
Formal Grammar Definition
A formal grammar is a mathematical system for describing the syntax of a language. It
provides precise rules for what constitutes a valid program.
Formal Definition: A grammar G = (N, T, P, S) consists of:
N (Non-terminals): Set of abstract symbols representing language constructs
Example: {expression, statement, declaration}
Also called "variables" or "syntactic categories"
T (Terminals): Set of basic symbols (tokens) that cannot be further subdivided
Example: {int, float, +, -, *, /, ;, =}
These are the actual tokens from the lexical analyzer
P (Productions): Set of rewriting rules
Format: A → α where A ∈ N and α ∈ (N ∪ T)*
Example: expr → expr '+' term
S (Start Symbol): Distinguished non-terminal from which all valid programs can be
derived
Example: program, statement, expression

Context-Free Grammar (CFG)

Context-free grammars are the mathematical formalism most commonly used for
describing programming language syntax because they balance expressiveness with
computational tractability.

Definition
A context-free grammar is a grammar where every production has exactly one non-
terminal on the left side:
A → α where A ∈ N and α ∈ (N ∪ T)*
The term "context-free" means that A can be replaced by α regardless of context
(surrounding symbols).

Comparison with Other Grammar Classes

Exampl
Type Left Side Use
e
Single terminal/non-
Regular A→a Lexical analysis
terminal
Context-Free Single non-terminal E → E+T Syntax analysis
Context- αAβ → Not used in
String of symbols
Sensitive αγβ compilers
Unrestricted Any string α→β Theory only
Why CFG for Programming Languages?
1. Sufficient Expressiveness: Can describe most language constructs (control flow,
declarations, etc.)
2. Computational Feasibility: Efficient parsing algorithms exist (polynomial time)
3. Human Readability: Production rules are intuitive and resemble formal language
specifications
4. Tool Support: Automatic parser generators (YACC, Bison, ANTLR) support CFGs

Grammar Rule Notation

Extended Backus-Naur Form (EBNF)
Modern grammar specifications often use EBNF notation for conciseness:

Notation Meaning Example

[x] Optional (0 or 1) [sign] digit
{x} Repetition (0 or more) digit {digit}
x\|y Alternation int \| float
(x) Grouping ('+'\|'-') number
'x' Terminal (quoted) 'if', '('
x Non-terminal statement

Conversion to Standard BNF

EBNF can always be converted to standard BNF:

EBNF: A → B {C}
Equivalent BNF:
A→B
| B C_list
C_list → C
| C_list C
EBNF: A → [B] C
Equivalent BNF:
A→BC
|C

Derivations: Formal String Generation

A derivation is a sequence of production applications showing how a string can be
generated from the start symbol. Each step replaces one non-terminal with the right-hand
side of a production.
Formal Definition
A direct derivation is written as: α ⇒ β
This means β can be obtained from α by replacing one occurrence of a non-terminal with
the right-hand side of a production.
A derivation (or derivation sequence) is: w₀ ⇒ w₁ ⇒ w₂ ⇒ ... ⇒ wₙ

Where each wᵢ ⇒ wᵢ₊₁ is a direct derivation.

Types of Derivations
Leftmost Derivation (LM):
Always replaces the leftmost non-terminal at each step
Natural for top-down parsing
Notation: ⇒ₗₘ
Example:

Grammar:
E→E+T|T
T→T* F|F
F → (E) | id
Leftmost derivation of "id + id * id":
E ⇒ₗₘ E + T
⇒ₗₘ T + T
⇒ₗₘ F + T
⇒ₗₘ id + T
⇒ₗₘ id + T * F
⇒ₗₘ id + F * F
⇒ₗₘ id + id * F
⇒ₗₘ id + id * id

Rightmost Derivation (RM):

Always replaces the rightmost non-terminal at each step

Natural for bottom-up parsing (reversed)
Notation: ⇒ᵣₘ
Example:
Rightmost derivation of "id + id * id":
E ⇒ᵣₘ E + T
⇒ᵣₘ E + T * F
⇒ᵣₘ E + T * id
⇒ᵣₘ E + F * id
⇒ᵣₘ E + id * id
⇒ᵣₘ T + id * id
⇒ᵣₘ F + id * id
⇒ᵣₘ id + id * id
Sentential Forms
A sentential form is any intermediate string in a derivation that may contain both
terminals and non-terminals.
id + T * id is a sentential form
A sentential form using a leftmost derivation is a left sentential form
A sentential form using a rightmost derivation is a right sentential form

Parse Tree (Concrete Syntax Tree)

A parse tree is a graphical representation of a derivation. It shows the structure of the string
according to the grammar.

Structure and Components

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

Parse tree for: id + id * id

Construction Rules
1. Root: Labeled with the start symbol (S)
2. Interior Nodes: Non-terminals from the grammar
3. Leaf Nodes: Terminals (tokens) in the order they appear
4. Parent-Child Relationship: If production A → X₁X₂...Xₙ is applied, node A has
children X₁, X₂, ..., Xₙ
5. Yield: Reading leaves left to right gives the original terminal string

Parse Trees vs Derivations

Relationship:

Each derivation corresponds to a unique parse tree

Different derivations can yield the same parse tree (if grammar is ambiguous,
multiple parse trees can exist for one string)
For unambiguous grammars, each valid string has exactly one parse tree
Advantages of Parse Trees:
 Visual representation easier to understand
Shows structure clearly
Directly usable for semantic analysis
Independent of derivation order

Ambiguity in Grammars
An ambiguous grammar is one where a single input string can have more than one parse
tree (or equivalently, more than one rightmost/leftmost derivation).

Problems with Ambiguity

Ambiguity is a serious problem because:
1. Multiple Interpretations: One expression can be parsed in multiple ways
2. Semantic Uncertainty: Different parse trees lead to different meanings
3. Code Generation Issues: Compiler cannot generate unique code
4. Evaluation Order Uncertainty: Operator evaluation order becomes undefined

Classic Example: Dangling Else

Grammar:
stmt → 'if' expr 'then' stmt
| 'if' expr 'then' stmt 'else' stmt
| other_stmt

Input: if x > 0 then if y < 0 then a = 1; else b = 2;

Two Possible Parse Trees:
Tree 1 (else matched with inner if):
if x > 0 then
if y < 0 then
a = 1;
else
b = 2;

Tree 2 (else matched with outer if):

if x > 0 then
if y < 0 then
a = 1;
else
b = 2;
Resolution: Most languages adopt "else matches nearest if" convention

Another Classic Example: Arithmetic Expressions

Ambiguous Grammar:
E → E + E | E * E | id
Expression: 2 + 3 * 4

Parse Tree 1 : (2 + 3) * 4 = 20
*
/
+4
/
23
Parse Tree 2 : 2 + (3 * 4) = 14
+
/
2*
/
34

Resolving Ambiguity
Method 1: Grammar Rewriting

Replace ambiguous grammar with unambiguous version that enforces precedence and
associativity:
Unambiguous Grammar:
E→E+T|T
T→T* F|F
F → (E) | id
This grammar enforces:

has higher precedence than +

Both are left-associative
Method 2: Precedence and Associativity Declarations
Many parser generators allow declarative specification:

%left '+'
%left '*'
%right '^' // Right-associative for exponentiation
E → E '+' E | E '*' E | E '^' E | id
The declarations disambiguate the grammar without rewriting it.

Method 3: Add Parentheses to Grammar

Explicitly include parenthesization:
E → E '+' E | E '*' E | 'id' | '(' E ')'

This makes operator precedence explicit and allows users to override it

Associativity and Precedence in Grammar
Precedence (Operator Binding)
Precedence determines which operator binds more tightly in expressions without
parentheses.

Precedence Levels (highest to lowest):

1. Parentheses and function calls
2. Exponentiation (^)
3. Unary operators (-, not)
4. Multiplication, division (*, /)
5. Addition, subtraction (+, -)
6. Comparison operators (<, >, ==)
7. Logical AND
8. Logical OR
9. Assignment (=, +=, etc.)
Effect of Precedence:

Higher precedence operators are evaluated first

In expression 2 + 3 * 4, multiplication (higher precedence) is done before addition
Grammar Encoding of Precedence:
Expression: 2 + 3 * 4

Ambiguous grammar would allow both interpretations.

Unambiguous grammar uses production hierarchy:
E → E + T (lowest precedence)
T → T * F (higher precedence)
F → id (highest precedence - atomic)
This structure ensures * binds before +

Associativity (Grouping)
Associativity determines how operators of the same precedence are grouped (left-to-right
or right-to-left).

Left-Associative: Operators associate to the left

5 - 3 - 2 = (5 - 3) - 2 = 0 ✓
2 ^ 3 ^ 4 = (2 ^ 3) ^ 4 = 4096 (if left-associative, unusual)
Right-Associative: Operators associate to the right

2 ^ 3 ^ 4 = 2 ^ (3 ^ 4) = 2 ^ 81 = huge (standard for exponentiation)

a = b = 5 means a = (b = 5) (assignment is right-associative)
Grammar Encoding:
For left-associative operators:
E → E '+' T | T
This grammar produces left-associative trees:
a + b + c is parsed as (a + b) + c
For right-associative operators:
E → T '^' E | T

This grammar produces right-associative trees:

a ^ b ^ c is parsed as a ^ (b ^ c)
Standard Associativities:
Left-associative: +, -, *, /, <, >, <=, >=, ==, !=, &&, ||
Right-associative: ^, =, +=, -=, etc.
Non-associative: Comparisons in some languages (prevents chaining)

4. Parsing Techniques: Comprehensive Analysis

4.1 Top-Down Parsing
Fundamental Approach: Begin with the start symbol and derive the input string by
repeatedly applying grammar rules until either success or failure.

Conceptual Overview
Top-down parsing simulates a leftmost derivation. The parser constructs the parse tree
from root to leaves.
Analogy: Like expanding an outline from the top-level heading down to specific details.

Detailed Parsing Process

1. Initialize: Place start symbol (S) on parse stack
2. Main Loop: Repeat until stack empty or error:
If top of stack is non-terminal A:
Look at current input token
Consult grammar for productions A → ...
Choose appropriate production
Replace A with right-hand side on stack
(May require backtracking if choice wrong)
If top of stack is terminal t:
Match t with current input token
If match: pop stack, advance input
If no match: error or backtrack
3. Success Condition: Stack empty AND all input consumed

Advantages of Top-Down Parsing

1. Intuitive: Directly simulates how humans read and parse
2. Hand-Implementable: Easy to write manually without tools
3. Early Error Detection: Can detect errors while reading input left-to-right
4. Semantic Actions: Easy to interleave semantic code with parsing
5. Suitable for DSLs: Good for designing domain-specific language parsers
Disadvantages of Top-Down Parsing
1. Backtracking: May need to try multiple production rules (inefficient)
2. Left Recursion: Cannot handle left-recursive productions directly
3. Grammar Restrictions: Not all grammars are suitable (must be LL(k) class)
4. Limited Lookahead: Typically uses only 1 or 2 lookahead tokens
5. Memory Overhead: Maintains parse stack and backtrack information

Recursive Descent Parsing - Detailed Implementation

Recursive descent parsing is a top-down parsing technique implemented using recursive
functions, with one function for each non-terminal.

Function Structure
For each non-terminal A with productions:
A → α₁ | α₂ | ... | αₙ
Create function parseA():
function parseA():
if current_token in First(α₁):
parse α₁
else if current_token in First(α₂):
parse α₂
...
else if current_token in First(αₙ):
parse αₙ
else:
error("Unexpected token")

Complete Example: Expression Parser

Grammar (left-recursion eliminated):
E → T E'
E' → '+' T E' | ε
T → F T'
T' → '*' F T' | ε
F → '(' E ')' | id
First Sets:

First(T) = First(F) = {(, id}

First(E') = {+, ε}
First(T') = {*, ε}
Pseudocode Implementation:
var currentToken;

function parseE():
parseT()
parseE_prime()
function parseE_prime():
if currentToken == '+':
consume('+')
parseT()
parseE_prime()
else if currentToken == ε or ')' or $:
return // ε production
else:
error("Expected '+' or end of expression")
function parseT():
parseF()
parseT_prime()

function parseT_prime():
if currentToken == '':
consume('')
parseF()
parseT_prime()
else if currentToken == '+' or ')' or $ or ε:
return // ε production
else:
error("Expected '*' or end of term")
function parseF():
if currentToken == 'id':
consume('id')
else if currentToken == '(':
consume('(')
parseE()
consume(')')
else:
error("Expected identifier or '('")
function consume(expected):
if currentToken == expected:
currentToken = nextToken()
else:
error("Expected " + expected + " but got " + currentToken)

Execution Example: Parsing "id + id"

Input: id + id $
↑

parseE() calls parseT()

parseT() calls parseF()
parseF() matches 'id', consumes it
currentToken = '+'
parseT() calls parseT_prime()
parseT_prime() sees '+', returns (ε)
parseT() returns
parseE() calls parseE_prime()
parseE_prime() sees '+', consumes it
currentToken = 'id'
parseE_prime() calls parseT()
parseT() calls parseF()
parseF() matches 'id', consumes it
currentToken = ' ', returns
parseT() returns
parseE_prime() calls parseE_prime() [recursive]
parseE_prime() sees '$', returns
parseE_prime() returns
parseE() returns
Success: parse tree constructed

Advantages of Recursive Descent

1. Simple Implementation: Just write functions matching grammar
2. Flexible: Easy to add semantic actions at any point
3. Debugging: Stack traces directly show parse structure
4. No Parser Generation Tool Needed: Can write by hand

Limitations of Recursive Descent

1. No Backtracking Variant: Standard version doesn't backtrack
2. Requires LL(1) Grammar: Each position needs unique lookahead
3. Left Recursion Problem: Causes infinite recursion
4. Lookahead Limited: Generally restricted to 1 token
5. Grammar Rewriting Needed: Often must eliminate left recursion

4.2 Bottom-Up Parsing

Fundamental Approach: Start from input tokens and work backward toward the start
symbol by recognizing substrings that match production right-hand sides and replacing
them with left-hand sides (reductions).

Conceptual Overview
Bottom-up parsing simulates a rightmost derivation in reverse. The parser constructs the
parse tree from leaves to root.
Analogy: Like solving a jigsaw puzzle by identifying larger components from smaller
pieces.

Detailed Parsing Process

1. Initialize: Create empty stack, mark input end with $
2. Main Loop: Repeat until accept or error:
Shift Action: Move next input token onto stack
Reduce Action: Identify a substring on top of stack matching RHS of
production
Pop RHS from stack
Push LHS (non-terminal) onto stack
Accept Action: Successfully parsed all input
 3. State Information: Parser maintains state indicating possible actions

Advantages of Bottom-Up Parsing

1. Powerful: Handles larger grammar class than LL (including left recursion)
2. Efficient: No backtracking needed (deterministic table-driven)
3. Automatic Generation: Parser generators (YACC, Bison) create these parsers
4. Less Lookahead: Can use limited lookahead effectively
5. Error Detection: Good error detection points in real code
6. Better for Left Recursion: Naturally handles left-recursive grammars

Disadvantages of Bottom-Up Parsing

1. Complex: More difficult to understand and implement manually
2. Semantic Actions: Harder to incorporate semantic code during parsing
3. Large Tables: Requires parsing tables (can be memory-intensive)
4. Shift-Reduce Conflicts: Some ambiguities appear as parsing conflicts
5. Debug Difficulty: Stack traces less intuitive

Shift-Reduce Parsing - Detailed Mechanism

Shift-reduce parsing is the core bottom-up parsing technique using two actions:
Shift: Move next input token to stack
Reduce: Replace top of stack matching RHS with corresponding LHS

Parsing Stack and Symbols

The parser maintains:

Parsing Stack: Contains terminals and non-terminals being processed

Input Buffer: Remaining tokens to process
Parse State: Number indicating parser state (for table-driven versions)
Visualization:
Parsing Stack | Input Buffer
[...] | token token ... token $
[T, +] | T2 T3 ... $
[T] | + T2 T3 ... $
[E] | + T2 T3 ... $

Shift and Reduce Operations Detailed

Shift Operation:
Before: Stack: [... symbols] | Input: [a, b, ...]
Shift action

After: Stack: [... symbols, a] | Input: [b, ...]

Move one symbol from input to stack
Reduce Operation (for production A → X₁X₂...Xₙ):
Before: Stack: [... symbols, X₁, X₂, ..., Xₙ] | Input: [a, b, ...]
Reduce by A → X₁X₂...Xₙ
After: Stack: [... symbols, A] | Input: [a, b, ...]
Pop n symbols from stack matching RHS
Push LHS non-terminal on stack
(Input unchanged)

Conflict Resolution in Shift-Reduce Parsing

Shift-Reduce Conflict:

Parser sees stack that could be immediately reduced

But next input token suggests shifting more
Example: a + b * c at + b with lookahead *
Reduce a + b? Or shift * first?
Reduce-Reduce Conflict:
Multiple productions match top of stack
Cannot determine which reduction to apply
Generally indicates grammar ambiguity

Resolution Methods:
1. Precedence Rules: Operator precedence resolves shift-reduce conflicts
2. Associativity Rules: Determines shift vs. reduce with same-precedence operators
3. Conflict Resolution Directives: Parser generator declarations override default

Full Shift-Reduce Example: Parsing "2 + 3 * 4"

Grammar:
E→E+T|T
T→T* F|F
F → num
Parsing Trace:
 Step Stack Input Action
0 $ 2+3*4$ Shift 2
1 $2 +3*4$ Reduce F → 2
2 $F +3*4$ Reduce T → F
3 $T +3*4$ Reduce E → T
4 $E +3*4$ Shift +
5 $E+ 3*4$ Shift 3
6 $E+3 *4$ Reduce F → 3
7 $E+F *4$ Reduce T → F
8 $E+T *4$ Shift *
9 $E+T* 4$ Shift 4
10 $E+T*4 $ Reduce F → 4
11 $E+T*F $ Reduce T → T * F
12 $E+T $ Reduce E → E + T
13 $E $ Accept

Key Points:
Step 8: Shift * instead of reducing T → T immediately (precedence decision)
This ensures * is applied before + (correct precedence)
Result: 2 + (3 * 4) = 14 (correct evaluation order)

5. First(β) and Follow(β) Sets - Complete Analysis

First(β) Set - Formal Definition and Theory
Definition: The First(β) set is the set of all terminals that can appear as the first symbol of
some string derivable from β:

Additionally, if β can derive the empty string (ε):

Computing First(β) - Comprehensive Algorithm
Rules for First Set Computation
Rule 1 : If X is a terminal, First(X) = {X}

Rule 2 : If X is a non-terminal with production X → ε, then ε ∈ First(X)

Rule 3 : For production X → Y₁Y₂...Yₖ:
Add First(Y₁) - {ε} to First(X)
If ε ∈ First(Y₁), then add First(Y₂) - {ε} to First(X)
Continue this pattern until:
A symbol's First set doesn't contain ε, OR
All symbols can derive ε (then add ε to First(X))

Rule 4 : For a string β = X₁X₂...Xₙ:

First(β) = First(X₁) - {ε}
Plus First(X₂) - {ε} if ε ∈ First(X₁)
Continue pattern...
Plus ε if ε in all First(Xᵢ)

Formal Algorithm
Algorithm: Compute First Sets
Input: Grammar G = (N, T, P, S)
Output: First(X) for all X ∈ N ∪ T

Initialization:
For each terminal a ∈ T:
First(a) = {a}
For each non-terminal A ∈ N:
First(A) = ∅
Iteration (Repeat until no changes):
For each production A → X₁X₂...Xₖ:
i=1
While i ≤ k:
Add First(Xᵢ) - {ε} to First(A)
If ε ∉ First(Xᵢ):
Break
i=i+1
If i > k (all symbols can derive ε):
Add ε to First(A)

Detailed Example: Computing First Sets

Grammar:
S→ABc
A→Ba |ε
B→b|ε
Iteration 0 (Initialization):
First(S) = ∅
First(A) = ∅
First(B) = ∅
First(a) = {a}
First(b) = {b}
First(c) = {c}
Iteration 1 :
For S → A B c:
First(A) is empty, add nothing... wait, A hasn't been processed yet

For A → B a:
First(B) is empty, so nothing added yet
For A → ε:
ε ∉ First(A) yet, so add it: First(A) = {ε}
For B → b:
First(b) = {b}, so First(B) = First(B) ∪ {b} = {b}

For B → ε:
ε ∉ First(B) yet, so add it: First(B) = {b, ε}
After Iteration 1:
First(S) = ∅
First(A) = {ε}
First(B) = {b, ε}
First(a) = {a}
First(b) = {b}
First(c) = {c}
Iteration 2 :
For S → A B c:
ε ∈ First(A), so add First(B) - {ε} = {b}
ε ∈ First(B), so add First(c) = {c}
Result: First(S) = {b, c}

For A → B a:
ε ∈ First(B), so add First(a) = {a}
Result: First(A) = First(A) ∪ {a} = {ε, a}
For A → ε: (no change)
For B → b: (no change)

For B → ε: (no change)

After Iteration 2:
First(S) = {b, c}
First(A) = {ε, a}
First(B) = {b, ε}
Iteration 3 :
For S → A B c:
ε ∈ First(A), so add First(B) - {ε} = {b}
Result: First(S) = {b, c} ∪ {b} = {b, c} (no change)
For A → B a:
ε ∈ First(B), so add First(a) = {a}
Result: First(A) = {ε, a} (no change)

No more changes, algorithm terminates.

Final First Sets:
First(S) = {b, c}
First(A) = {a, ε}
First(B) = {b, ε}

Follow(A) Set - Formal Definition and Theory

Definition: The Follow(A) set is the set of all terminals that can immediately follow a non-
terminal A in some valid derivation (sentential form):

Where S is the start symbol, α and β are arbitrary strings.

Special Case: If A can appear at the end of a sentential form:

Computing Follow(A) - Comprehensive Algorithm

Rules for Follow Set Computation
Rule 1 : $ ∈ Follow(S) where S is start symbol
Rule 2 : If production is A → X₁X₂...Xₙ and B appears as Xᵢ:
Add First(Xᵢ₊₁...Xₙ) - {ε} to Follow(B)

Rule 3 : If production is A → X₁X₂...Xₙ B and:

Either n = i (B is last symbol), OR
ε ∈ First(Xᵢ₊₁...Xₙ) (all following symbols derive ε)
Then add Follow(A) to Follow(B)

Formal Algorithm
Algorithm: Compute Follow Sets
Input: Grammar G = (N, T, P, S)
Output: Follow(A) for all A ∈ N
Initialization:
For each non-terminal A ∈ N:
Follow(A) = ∅
Follow(S) = {$} // $ represents end-of-input
Iteration (Repeat until no changes):
For each production A → X₁X₂...Xₖ:
For each position i from 1 to k where Xᵢ is non-terminal:
// X_{i+1} X_{i+2} ... X_k is the rest of RHS
beta = X_{i+1} X_{i+2} ... X_k
Add First(beta) - {ε} to Follow(Xᵢ)
If ε ∈ First(beta):
Add Follow(A) to Follow(Xᵢ)

Detailed Example: Computing Follow Sets

Grammar:
S→ABc
A→Ba |ε
B→b|ε
First Sets (computed above):
First(S) = {b, c}
First(A) = {a, ε}
First(B) = {b, ε}

Initialization:
Follow(S) = {$}
Follow(A) = ∅
Follow(B) = ∅
Iteration 1 :
For S → A B c:
Position 1, X₁ = A (non-terminal):
β =Bc
First(B c) = {b, c} (since b ∈ First(B), and if ε∈First(B) we add First(c)={c})
Add {b, c} to Follow(A): Follow(A) = {b, c}
ε ∉ First(B c), so don't add Follow(S)

Position 2, X₂ = B (non-terminal):
β =c
First(c) = {c}
Add {c} to Follow(B): Follow(B) = {c}
ε ∉ First(c), so stop
For A → B a:
Position 1, X₁ = B (non-terminal):
β =a
First(a) = {a}
Add {a} to Follow(B): Follow(B) = {c, a}
ε ∉ First(a), so stop
For A → ε: (no symbols)

For B → b: (no non-terminals)

For B → ε: (no symbols)
After Iteration 1:
Follow(S) = {$}
Follow(A) = {b, c}
Follow(B) = {a, c}
Iteration 2 :

For S → A B c:
Position 1, X₁ = A:
First(B c) = {b, c}, already in Follow(A)
ε ∉ First(B c)
Position 2, X₂ = B:
First(c) = {c}, already in Follow(B)
ε ∉ First(c)
For A → B a:
Position 1, X₁ = B:
First(a) = {a}, already in Follow(B)
ε ∉ First(a)

No changes, algorithm terminates.

Final Follow Sets:
Follow(S) = {$}
Follow(A) = {b, c}
Follow(B) = {a, c}

Interpretation of First/Follow Sets

First(A) tells us: "What tokens can START a production for A?"
Used in LL(1) parsing to choose which production rule to apply
If current token is in First(A), we can use production for A

Follow(A) tells us: "What tokens can FOLLOW a production for A?"
Used in LL(1) parsing when A can derive ε
If current token is in Follow(A) and A → ε, we can use the empty production

6. LL(1) Parsing - Detailed Theory and Practice

LL(1) Parser Definition and Properties
LL(1) is an acronym for:
L: Left-to-right scanning of input
L: Leftmost derivation generation
(1): One token of lookahead
Formal Definition
An LL(1) parser is a table-driven top-down parser that:
1. Scans input left-to-right
2. Constructs leftmost derivations
3. Uses exactly one lookahead token to determine parsing action
4. Is deterministic (no backtracking or conflicts)

Implementation Components
An LL(1) parser consists of:
1. Input: Token stream with end-of-input marker $
2. Parsing Stack: Initialized with [S, $]
3. Parsing Table: M[A, a] giving action for non-terminal A with lookahead token a
4. Parsing Program: Deterministic algorithm using table

LL(1) Grammar Condition

A grammar is LL(1) if and only if for each non-terminal A with productions:

The following conditions hold:

Condition 1: Non-overlapping First Sets

This ensures that each lookahead token uniquely determines which production to use.

Condition 2: Nullable Productions

If any production can derive ε, then:

This prevents conflict between nullable and non-nullable alternatives.

Checking LL(1) Condition - Example

Grammar:
E → T E'
E' → '+' T E' | ε
T → F T'
T' → '*' F T' | ε
F → '(' E ')' | id
First and Follow Sets:
First(T) = {(, id}
First(E') = {+, ε}
First(T') = {, ε}
First(F) = {(, id}
First('(')={(}, First(')')={)}, First('+')={+}, First('')={*}, First(id)={id}
Follow(E) = {), $}
Follow(E') = {), $}
Follow(T) = {+, ), $}
Follow(T') = {+, ), $}
Follow(F) = {*, +, ), $}
Checking LL(1) Condition for E':

Productions: E' → '+' T E' | ε

First('+' T E') = {+}
First(ε) = {ε}
First('+' T E') ∩ First(ε) = {+} ∩ {ε} = ∅ ✓ (Condition 1 satisfied)
Since ε ∈ First(ε), check Condition 2:

First(ε) ∩ Follow(E') = {ε} ∩ {), $} = ∅ ✓ (Condition 2 satisfied)

Conclusion: Grammar is LL(1)

LL(1) Parsing Table Construction

The LL(1) parsing table M[A, a] specifies exactly what action to take when:
Non-terminal A is on top of the parsing stack
Current input token is a (or $ for end-of-input)

The table entry is either:

A production rule A → α to use (push A's right-hand side)
error (syntax error - no valid parse)
Empty cell (depends on implementation)

Algorithm for Table Construction

Algorithm: Construct LL(1) Parsing Table
Input: LL(1) Grammar G, First and Follow sets
Output: Parsing table M[A, a]

Initialization:
For all M[A, a]:
M[A, a] = error
Filling:
For each production A → α:
For each terminal a ∈ First(α):
M[A, a] = A → α
If ε ∈ First(α):
For each terminal b ∈ Follow(A):
M[A, b] = A → α
If $ ∈ Follow(A):
M[A, $] = A → α
Table Construction Example
Grammar:
E → T E'
E' → '+' T E' | ε
T → F T'
T' → '*' F T' | ε
F → '(' E ')' | id
Production Rules Numbered:
1. E → T E'
2. E' → '+' T E'
3. E' → ε
4. T → F T'
5. T' → '*' F T'
6. T' → ε
7. F → '(' E ')'
8. F → id

LL(1) Parsing Table:

NT ( id + * ) $
E 1 1
E' 2 3 3
T 4 4
T' 6 5 6 6
F 7 8

Explanation:
M[E, (] = 1: When expecting E and seeing (, use E → T E'
M[E', +] = 2: When expecting E' and seeing +, use E' → '+' T E'
M[E', )] = 3: When expecting E' and seeing ) (not in First(E')), use E' → ε
M[T', *] = 5: When expecting T' and seeing , use T' → '' F T'
M[T', +] = 6: When expecting T' and seeing + (not in First(T')), use T' → ε

LL(1) Parser Algorithm - Comprehensive

Algorithm: LL(1) Predictive Parsing

Input: Input string w and parsing table M for grammar G

Output: If w ∈ L(G), produce derivation; otherwise, error report
Initialization:
stack = [S, $] // S is start symbol, $ is end marker
input = w + $
ip = 1 // input pointer (current position)
Parsing Loop:
While stack is not empty:
X = top(stack)
a = input[ip]

If X is terminal or $:
If X == a:
Pop stack
ip++
Else:
error("Unexpected token")
// Panic mode recovery: skip to sync point

Else if X is non-terminal:
If M[X, a] is A → Y₁Y₂...Yₖ:
Pop stack
Push Yₖ, Yₖ₋₁, ..., Y₁ (rightmost first, so Y₁ on top)
// Print production for leftmost derivation
Else if M[X, a] is ε production (A → ε):
Pop stack
// Print production
Else if M[X, a] is "error" or empty:
error("No matching production")
// Error recovery action
Else:
error("Unknown table entry")

Completion:
If stack empty and ip at end of input:
return "Accept"
Else if stack empty and ip not at end:
error("Unexpected tokens remaining")
Else if stack not empty and ip at end:
error("Unexpected end of input")
Execution Example: Parsing "( id )" with Grammar F
Grammar:
F → '(' E ')' | id
E → T E'
...
Parsing Table (relevant entries):
M[F, (] = F → '(' E ')'
M[E, id] = E → T E'
M[T, id] = T → F T'
M[T', )] = T' → ε
M[F, id] = F → id
Execution Trace:
Step Stack Input Action
0 F$ ( id ) $ ip points to '('
M[F, (] = F → '(' E ')'
1 )E($ ( id ) $ Pop F, push ) E ( (reverse order)
ip=1, a='('
2 )E( ( id ) $ Top is '(', match '('
(consumes) Pop '(', ip++
3 )E id ) $ Top is E, a=id
M[E, id] = E → T E'
Pop E, push E' T
4 ) E' T id ) $ Top is T, a=id
M[T, id] = T → F T'
Pop T, push T' F
5 ) E' T' F id ) $ Top is F, a=id
M[F, id] = F → id
Pop F, push id
6 ) E' T' id id ) $ Top is id, match id
Pop id, ip++
7 ) E' T' )$ Top is T', a=')'
M[T', )] = T' → ε
Pop T' (epsilon, so just pop)
8 ) E' )$ Top is E', a=')'
M[E', )] = E' → ε
Pop E'
9 ) )$ Top is ')', match ')'
Pop ')', ip++
 Step Stack Input Action
10 $ $ Top is
Match, pop
11 (empty) (empty) Accept!

Advantages and Disadvantages of LL(1)

Advantages
1. Simplicity: Easy to understand and implement
2. Efficiency: O(n) parsing time where n is input length
3. Minimal Lookahead: Only one token needed
4. Tool Support: Parser generators (ANTLR) support LL(1) well
5. Suitable for Manual Implementation: Can write recursive descent by hand
6. Good for DSLs: Appropriate for domain-specific languages
7. Error Detection: Can report errors at specific locations

Disadvantages
1. Limited Grammar Class: Cannot parse left-recursive grammars
2. Grammar Modification Required: Often must rewrite grammar (eliminate left
recursion, factor productions)
3. Large Parse Tables: For large grammars, M[A, a] table can be substantial
4. Cannot Handle Some Natural Grammars: Some languages require rewriting to
LL(1) form
5. Lookahead Limitation: One token insufficient for some language constructs

LL(k) vs LL(1)
LL(k) parsers use k tokens of lookahead instead of just 1. While more powerful, they also:
Have larger parsing tables (exponentially grow with k)
Are more complex to implement
Have longer parse time due to lookahead scanning
In practice, LL(1) suffices for most modern languages (though some use LL(k) with k>1).

7. LR(1) Parsing - Detailed Theory and Implementation

Why LR Parsing?
LR parsing is more powerful than LL parsing and handles many languages that LL cannot:
Left-recursive grammars (common in language definitions)
Shift-reduce conflicts can be resolved with operator precedence
Larger grammar class: Includes LR(0), SLR(1), LALR(1), CLR (LR(1))
LR Parsing Family Hierarchy
LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1)
⊂ LR(k) for k>1

(LR(0) subset of SLR, which is subset of LALR and LR(1), etc.)

LR(0) Items - Foundation

An LR(0) item (or "item" for short) is a production with a dot (•) positioned at a point in the
right-hand side, indicating how much input has been recognized:

Interpretation:
The part before the dot has been seen (recognized/reduced)
The part after the dot is expected next
This item is "active" when its production is a candidate for reduction

Item Examples
For production E → E + T, possible items are:

1. E → • E + T (dot at start - haven't recognized anything yet)

2. E → E • + T (recognized E, expect + T next)
3. E → E + • T (recognized E +, expect T next)
4. E → E + T • (recognized entire RHS, ready to reduce)

Kernel vs Non-Kernel Items

Kernel item: Initial item (I₀ = {S' → • S}) or item with dot moved
Non-kernel item: Generated by closure operations

Closure Function - Building Complete Item Sets

The closure of a set of items I is obtained by:
1. Starting with I
2. For each item A → α • B β in closure(I) where B is non-terminal:
Add all productions B → γ as items B → • γ
3. Repeat until no new items added

Intuition: If we're about to process non-terminal B, we need to know ALL ways B can be
recognized.

Closure Algorithm
Algorithm: Closure(I)
Input: Set of items I
Output: Closure of I
closure(I) = I
Repeat:
For each item [A → α • B β] in closure(I):
If B is non-terminal:
For each production B → γ:
If [B → • γ] not in closure(I):
Add [B → • γ] to closure(I)
Until no new items added
Return closure(I)

Closure Example
Grammar:
S' → E
E→E+T|T
T→T* F|F
F → ( E ) | id

Item Set:
I = {[S' → • E]}
Closure(I):
Step 1: I = {[S' → • E]}

Item [S' → • E] has non-terminal E after dot

Add items for all E productions:
[E → • E + T]
[E → • T]
Step 2: New items added, process them
Item [E → • E + T] has non-terminal E after dot
But E productions already in set
Item [E → • T] has non-terminal T after dot
Add items for all T productions:
[T → • T * F]
[T → • F]

Step 3: New items added, process them

Item [T → • T * F] has non-terminal T after dot
But T productions already in set
Item [T → • F] has non-terminal F after dot
Add items for all F productions:
[F → • ( E )]
[F → • id]
Step 4: No new non-terminals to process

Final Closure(I):
{[S' → • E],
[E → • E + T],
[E → • T],
[T → • T * F],
[T → • F],
[F → • ( E )],
[F → • id]}

Goto Function - State Transitions

The goto function computes the next state when parsing symbol X:

Process:
1. Find all items in I with • before X
2. Move • past X
3. Take closure of result

Goto Example
From previous closure I₀:
I₀ = closure({[S' → • E]})
= {[S' → • E],
[E → • E + T],
[E → • T],
[T → • T * F],
[T → • F],
[F → • ( E )],
[F → • id]}

Computing goto(I₀, E):

Find items with • before E:
[S' → • E]
[E → • E + T]

Move • past E:
[S' → E •]
[E → E • + T]
Closure (no new non-terminals after •):

No additional items needed

goto(I₀, E) = I₁:
{[S' → E •],
[E → E • + T]}
Computing goto(I₀, T):

Find items with • before T:

[E → • T]
[T → • T * F]
Move • past T:
 [E → T •]
[T → T • * F]
Closure: No new non-terminals

goto(I₀, T) = I₂:
{[E → T •],
[T → T • * F]}

LR(0) Automaton Construction - Full Algorithm

Algorithm: Construct LR(0) Automaton
Input: Augmented Grammar G' = (N, T, P, S') where S' → S is added
Output: Set of LR(0) item sets (states), transitions (goto function)
States = ∅
Unmarked = ∅

I₀ = closure({[S' → • S]})
Add I₀ to States
Add I₀ to Unmarked
While Unmarked not empty:
I = Remove(Unmarked)
Mark I as processed
For each symbol X ∈ N ∪ T:
J = goto(I, X)

If J is non-empty and J ∉ States:

Add J to States
Add J to Unmarked

If J is non-empty:
Create transition: I →ˣ J

Return (States, Initial State I₀)

Complete LR(0) Automaton Example

Let's construct the automaton for the grammar:
E' → E
E→E+T|T
T→T* F|F
F → ( E ) | id
(Full construction produces multiple states I₀ through I₁₀ or similar, showing transitions)
LR(1) Items - Adding Lookahead
An LR(1) item augments LR(0) items with a lookahead terminal:

Where:
A → X₁X₂•X₃X₄ is the LR(0) item part
a is a lookahead terminal (or $ for end-of-input)
Meaning: This item is valid when:

Parser has recognized X₁X₂

Next input token is from the lookahead set
Parser expects X₃X₄ to follow

Lookahead Computation in Closure

When computing closure with lookahead:
For item [A → α • B β, a]:
Add all items [B → • γ, b] where b ∈ First(βa)

If ε ∈ First(βa), then b includes all terminals in Follow(B).

LR(1) Closure with Lookahead Example

Item: [S' → • E, $]
Closure:
S' → • E with lookahead $ (must compute what can follow E)
E can appear at end (in S' → E), so lookahead includes $
Add [E → • E + T, {+, $}] (if E appears directly, + can follow after +T)
Add [E → • T, {+, $}]

And so on...

LR(1) vs SLR(1) Distinction

SLR(1) (Simple LR):
Uses LR(0) items
Applies global Follow(A) sets in reduce actions
Simpler, smaller tables
Problem: Uses same lookahead set for all states
Result: May have reduce-reduce conflicts
LR(1) (Canonical LR):

Uses LR(1) items with state-specific lookaheads

More precise about what can follow in each state
Advantage: Fewer conflicts, can parse more grammars
Disadvantage: Much larger tables
 Size: Can be 10x or more larger than SLR
LALR(1) (LookAhead LR):

Merges LR(1) states with same LR(0) core

Combines lookahead sets from merged states
Balance: Between SLR and LR(1) in power and table size
Practical: Most automatic parser generators use LALR

SLR(1) Parsing Table Construction

Action Table Rules for SLR(1)
For each state I and lookahead terminal a:

1. Shift action: If [A → α • a β] ∈ I and goto(I, a) = J:

Set Action[I, a] = "shift J" (sJ)
2. Reduce action: If [A → α •, a] ∈ I and A ≠ S':
Set Action[I, a] = "reduce A → α" (r#)
Where # is the production number
3. Accept action: If [S' → S •, $] ∈ I:
Set Action[I, $] = "accept"
4. Error: If no rule applies:
Set Action[I, a] = "error"

Goto Table Rules

For each state I and non-terminal A:
If goto(I, A) = J:
Set Goto[I, A] = J
Otherwise, leave blank (implicit error).

LALR(1) Parsing Table Construction

LALR(1) tables are built by:
1. Computing all LR(1) states
2. Merging states with identical LR(0) cores (same items before lookahead)
3. Combining lookahead sets from merged states
4. Building tables from merged states
Efficiency:

Significantly smaller than LR(1) tables

Only slightly larger than SLR(1)
Very practical for real compilers
Shift-Reduce and Reduce-Reduce Conflicts in LR Parsing
Shift-Reduce Conflict
Occurs when a state has both shift and reduce actions for same lookahead:

Example:
State I contains:
[E → E + T •, +] (reduce after E+T)
[E → E • + T, +] (shift the second +)
Both with lookahead +
Resolution Methods:
1. Shift bias: Prefer shift (associativity: left-associative favors this)
2. Reduce bias: Prefer reduce
3. Precedence directives: Use operator precedence rules

Reduce-Reduce Conflict
Occurs when a state has multiple reduce actions for same lookahead:

Example:
State I contains:
[A → α •, a] (reduce by production 1)
[B → β •, a] (reduce by production 2)
Both with lookahead a
Problem: Indicates grammar is ambiguous or not LR(k)
Resolution: Rewrite grammar to be unambiguous (avoid this conflict)

Complete SLR(1) Parsing Example

Grammar:
1. S' → S
2. S → L = R
3. S → R
4. L → * R
5. L → id
6. R → L
After constructing LR(0) automaton (states I₀...I₁₀ or similar):

Action/Goto Table:
 State * id = $ S L R
0 s3 s5 1 2
1 acc
2 s6 r3 4
3 s5 7
...

Parsing "id = id":

State Stack Input Action

0 0 id=id$ shift id (state 5)
5 0 id 5 =id$ reduce L → id (prod 5)
2 0L2 =id$ shift = (state 6)
6 0L2=6 id$ shift id (state 5)
5 0 L 2 = 6 id 5 $ reduce L → id
... ... ... ...
1 0S1 $ accept

8. Operator Precedence Parsing - Simplified Approach

Overview and Motivation
Operator precedence parsing is a bottom-up parsing technique specifically designed for
expressions with infix binary operators. It's simpler than full LR parsing but less general.

Applicability
Suitable for:
Arithmetic expressions
Boolean expressions
Assignment expressions
Simple operator-based constructs

Not suitable for:

Complex language constructs
Statements with structure
 Declarations and definitions

Precedence Relations
Three binary relations define the structure:
1. <g (yield, lower precedence):
Shift when current operator has lower precedence than next
Example: + <g * means + has lower precedence
2. =g (equal precedence):
Operators have equal precedence
Associativity rules determine shift vs reduce
Example: + =g + for same precedence operators
3. >g (reduce, higher precedence):
Reduce (apply current operator) when current has higher precedence
Example: * >g + means * binds tighter than +

Precedence Table Construction

For a grammar with operators: +, -, *, /, ^
Standard mathematical precedence and associativity:

: precedence 1, left-associative

/ : precedence 2, left-associative
^ : precedence 3, right-associative
Precedence Table:

+ - * / ^ id $
+ >g >g <g <g <g <g >g
- >g >g <g <g <g <g >g
* >g >g >g >g <g <g >g
/ >g >g >g >g <g <g >g
^ >g >g >g >g >g <g >g
id >g >g >g >g >g >g
$ <g <g <g <g <g <g

Interpretation:

M[+, *] = <g: If current is +, next is *, shift (+ has lower precedence)

M[*, +] = >g: If current is , next is +, reduce ( has higher precedence)
M[+, +] = >g: If current is +, next is +, reduce (left-associative)
M[^, ^] = <g: If current is ^, next is ^, shift (right-associative)
Operator Precedence Parsing Algorithm
Algorithm: Operator Precedence Parsing
Input: Expression with operators, operands, and parentheses
Precedence table M
Output: Parsed expression / parse tree

Initialize:
stack = [$]
input = expression + $
ip = 1
While true:
a = currentOperator(stack) // Top operator on stack
b = nextOperator(input) // Next operator in input
relation = M[a, b]

If relation == <g or a == $ and b != $:

Push b onto stack
Advance input
Else if relation == =g:
Pop matching parenthesis
or shift next operator
Else if relation == >g:
Reduce top operand and two operators
Create tree node
Continue without advancing input

Else if a == $ and b == $:
Break (success)
Else:
Error("Invalid expression")

Example: Parsing "2 + 3 * 4" with Operator Precedence

Grammar: E → E + E | E * E | num

Precedence Relation: + <g * (addition has lower precedence)

Trace:
 Ste Top Next Relatio
Stack Input Action
p Op Op n
2+3*4
1 $ $ + <g shift +
$
2+3*4
2 $+ + 2 <g push 2
$
3 $+2 +3*4$ 2 + >g reduce
4 $E +3*4$ E + >g ?
5 $+ 3*4$ + * <g push 3
6 $+3 *4$ 3 * >g reduce
7 $+E *4$ E * <g shift *
8 $+E* 4$ * 4 <g push 4
$+E*
9 $ 4 $ >g reduce
4
$+E*
10 $ * $ >g reduce (*E)
E
11 $+E $ E $ >g reduce (+E)
Parse
12 $E $ E $ Accept
complete

Limitations of Operator Precedence Parsing

1. Limited to Expressions: Cannot handle full language syntax
2. Parenthesis Handling: Requires explicit treatment
3. Unary Operators: Difficult to incorporate
4. Error Recovery: Limited error handling capabilities
5. Grammar Class: Much smaller than LL or LR

9. LR Parsing with Complete Examples

Comprehensive SLR(1) Parsing Example
Grammar:
S → id := E
E→E+T|T
T→F* T|F
F → ( E ) | id | num
States and Parsing Table Construction
(Detailed construction of all states I₀ through I₁₅, showing items, transitions)
[Due to length constraints, providing key states and table]

Complete Parsing Example: "x := 2 + 3 * 4"

Token Sequence: id, :=, num, +, num, *, num, $

Parsing Trace (detailed):

Ste
State Stack Symbol Stack Input Action
p
id := 2 + 3 *
0 0 $ shift (state 3)
4$
:= 2 + 3 * 4 shift := (state
1 03 $ id
$ 5)
shift num
2 035 $ id := 2+3*4$
(state 8)
reduce
3 0358 $ id := num +3*4$
F→num
4 0357 $ id := F +3*4$ reduce T→F
shift + (state
5 0356 $ id := T +3*4$
10)
shift num
6 0 3 5 6 10 $ id := T + 3*4$
(state 8)
$ id := T + reduce
7 0 3 5 6 10 8 *4$
num F→num
8 0 3 5 6 10 11 $ id := T + F *4$ reduce T→F
shift * (state
9 0 3 5 6 10 12 $ id := T + T *4$
15)
0 3 5 6 10 12 shift num
10 $ id := T + T * 4$
15 (state 8)
0 3 5 6 10 12 $ id := T + T * reduce
11 $
15 8 num F→num
0 3 5 6 10 12 $ id := T + T * reduce
12 $
15 16 F T→F*T
0 3 5 6 10 12 reduce
13 $ id := T + T $
17 E→E+T
reduce
14 0356 $ id := E $
S→id:=E
15 01 $S $ accept
10. Relationship Between Parsing Techniques
Grammar Classes and Parsing Techniques
Type 3 (Regular) ← Regex, Lexical Analysis
↓
Type 2 (Context-Free) ← LL(1), LR(0), SLR, LALR, LR(k)
↓
Type 1 (Context-Sensitive) ← Not used in compilers

LL vs LR Comparison

Aspect LL LR
Derivation Leftmost Rightmost
Parse Direction Top-down Bottom-up
Grammar Class LL(k) LR(k)
Left Recursion Not allowed Allowed
Table Size Smaller Larger
Lookahead Limited More effective
Implementation Easier manually Needs generator
Error Detection Earlier Later (more input read)
Shift-Reduce Conflicts N/A Handled by precedence

11. Practical Implementation and Tools

Automatic Parser Generators
YACC (Yet Another Compiler Compiler):
Creates LR(1) parser from grammar specification
Input: Grammar with semantic actions
Output: C parser code

Bison (GNU version of YACC):

Modern replacement for YACC
Better error handling
Supports LALR, GLR parsing
ANTLR (ANother Tool for Language Recognition):

Generates LL(*) parsers

 Supports multiple target languages
Predicated parsing for context
Strong community support
Flex/Lex (Lexical analyzer):

Generates lexical analyzer

Works with Bison/YACC
Defines tokens using regular expressions

Grammar Specification Example (YACC Format)

%{
#include <stdio.h>
int yylex();
void yyerror(char *s);
%}
%token NUMBER
%token PLUS MINUS TIMES DIVIDE
%token LPAREN RPAREN
%%

expr : NUMBER
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIVIDE expr
| LPAREN expr RPAREN
;
%%
void yyerror(char *s) {
fprintf(stderr, "Error: %s\n", s);
}

int main() {
return yyparse();
}

Summary and Key Concepts

Syntax Analysis Overview
Key Responsibilities:
1. Validate token stream against grammar
2. Construct parse tree for semantic analysis
3. Detect and report syntax errors
4. Recover from errors to continue compilation
Grammar Fundamentals
Context-free grammars specify language syntax
Derivations show how strings are generated
Parse trees represent syntactic structure
Ambiguity must be resolved for deterministic parsing

Parsing Strategies
Top-Down:
Recursive descent, LL parsing
Intuitive but limited
Suitable for hand-written parsers

Bottom-Up:
LR parsing family (SLR, LALR, LR)
Powerful and general
Suitable for automatic generation

Important Techniques
First/Follow sets for predictive parsing
LR items for bottom-up parsing
Closure/Goto for automaton construction
Operator precedence for expression parsing

Practical Considerations
Parser generators automate table-driven parser creation
LALR provides best balance of power and table size
Modern compilers use automatic parser generators
Grammar design critical for parser efficiency and error handling

References
[1] Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques,
and Tools (2nd ed.). Pearson Education. ISBN 978-0321486813.
[2] Appel, A. W., & Palsberg, J. (2002). Modern Compiler Implementation in Java (2nd ed.).
Cambridge University Press. ISBN 978-0521820608.

[3] Fischer, C. N., Cytron, R. K., & LeBlanc, R. J. (2009). Crafting a Compiler. Pearson Education.
ISBN 978-0136067052.
[4] Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.).
Springer-Verlag. ISBN 978-0387202488.
[5] Johnson, S. C. (1975). Yacc - a parser generator. Bell Laboratories, Computing Science
Technical Report No. 32.
[6] Parr, T. (2013). Language Implementation Patterns: Create Your Own Domain-Specific and
General Programming Languages. Pragmatic Bookshelf. ISBN 978-1934356456.
[7] Louden, K. C. (2011). Compiler Construction: Principles and Practice (1st ed.). Cengage
Learning. ISBN 978-0534499860.

[8] Wilhelm, R., & Maurer, D. (1995). Compiler Design (1st ed.). Addison-Wesley. ISBN 978-
0201422619.
[9] Holub, A. I. (1990). Compiler Design in C (1st ed.). Prentice Hall. ISBN 978-0131550888.
[10] Pittman, T., & Peters, J. (1992). The Art of Compiler Design: Theory and Practice. Prentice
Hall. ISBN 978-0137043292.