Chapter 3

Syntax Analysis
 Outline
• Introduction
• Role of the parser
• Context-Free Grammars (CFG)
• Parse trees and derivations
• Top-down parsing (LL)
• Bottom-up parsing (LR, SLR, LALR)
• Yacc/Bison tool

2
 Introduction
- Syntax Analysis, also known as parsing, is a
crucial phase in compiler construction.
- After lexical analysis produces tokens, the
parser takes these tokens and ensures that
they follow the grammatical rules of the
programming language.

3
 Role of the Parser
• Checking syntactic correctness
– The parser verifies that the sequence of tokens
from the lexer conforms to the language grammar.
– Example: if (x > 0) y = 1; is syntactically correct; if x > 0 y = 1;
is not.
• Constructing a parse tree or abstract syntax
tree (AST)
– Represents the hierarchical syntactic structure of
the program.
– Helps in later stages like semantic analysis and code
generation. 4
 Role of the Parser
• Error detection and recovery
– Identifies syntax errors and, where possible,
recovers to continue parsing.
– Example: missing semicolons, unmatched
parentheses.
• Guiding semantic analysis
– Provides structure for type checking, scope
management, and other semantic checks.

5
 Context-Free Grammars (CFG)
• A CFG defines the syntax of programming
languages formally.
• CFG consists of:
– Terminals (T)
• Basic symbols from which strings are formed (usually
tokens from lexical analysis).

• Example: id, +, *, (, ).
– Non-terminals (N)
• Abstract symbols representing language constructs.

• Example: Expression, Statement. 6

 Context-Free Grammars (CFG)
– Start symbol (S)
• A special non-terminal representing the entire
program.
– Production rules (P):
• Rules for replacing non-terminals with combinations of
terminals and non-terminals.
• Example:
– Expression → Expression + Term | Term
– Term → Term * Factor | Factor
– Factor → ( Expression ) | id
– CFG is powerful because it can describe most
programming language syntax, including nested structures
like parentheses and blocks. 7
 Example of CFG
A grammar for palindromic bit-strings:
G = (V, T, P, S), where:
– V = { S, B }
– T = {0, 1}
– P = { S  B,
S  ,
S  0 S 0,
S  1 S 1,
B  0,
B1
} 8
 Parse Trees and Derivations
• Parse Tree (Syntax Tree)
– A tree that represents the structure of a string according to
a grammar.
• Tree structure
– Root: start symbol.
– Internal nodes: non-terminals.
– Leaves: terminals (tokens).
• Derivations:
– Leftmost derivation: Replace the leftmost non-terminal
first.
– Rightmost derivation: Replace the rightmost non-terminal
9
first.
 Example
• For grammar:
S → aSb | ε
String: aabb
• Leftmost derivation:
S ⇒ aSb ⇒ aaSbb ⇒ aabb
• Parse Tree:
S
/|\
a S b
/|\
a S b
|
10
ε
 Ambiguity
Grammar rules: Input: 1+2*3
E  id
E  num
EE+E
EE*E
E(E)

Leftmost derivation Rightmost derivation

Derivation: Parse tree: Derivation: Parse tree:

E E
E E
E+E E*E
1+E E + E E*3 E * E
1+E+E E+E*3
1 * 3
1+2+E E E E+2*3 E + E
1+2*3 1+2*3
2 3 1 2

11
 Top-Down Parsing (LL Parsing)
• LL parsers construct the parse tree from root
(start symbol) to leaves (input tokens).
• Top-down parsing tries to predict which
production to use based on the next input
token.
• LL Parsers:
– LL(k) parser:
• L → Left-to-right scanning of input
• L → Leftmost derivation
• k → Number of lookahead tokens used 12
 Types of LL Parsers
• LL(1)
– Uses 1 token of lookahead to decide which
production to apply. Most commonly used in
predictive parsers.
• LL(k)
– Uses k tokens of lookahead. Useful for more
complex grammars, but less common.
• Features:
– Easy to implement with recursive descent parsers.
– Works best for predictive grammars (no left
recursion). 13
 Predictive Parsing
• Predictive parsing is a form of top-down
parsing that does not require backtracking.
• Uses a parsing table to decide which
production to apply based on:
– Current non-terminal
– Next input token

14
 Recursive Descent Parsing
• A common implementation of top-down
parsing.
• Each non-terminal corresponds to a recursive
function.
• Functions call each other according to the
grammar productions.
• Easy to implement for small grammars.

15
 Example of Recursive Descent
Parsing
– Grammar: def E():
T()
E → T E'
E_prime()
E' → + T E' | ε
T → id def E_prime():
– The parser uses if lookahead == '+':
functions for E, E', T match('+')
T()
and matches input
E_prime()
tokens accordingly. else:
pass # epsilon

def T():
match('id') 16
 Advantages and Disadvantages of
Top-Down Parsing
• Advantages
– Simple and easy to implement
– Good for predictive parsing of programming
languages
– Works well for hand-written parsers
• Disadvantages
– Cannot handle left-recursive grammars
– Not suitable for all context-free grammars
– Less powerful than LR parsers (bottom-up parsers)
17
 Bottom-Up Parsing
• These parsers build the parse tree from leaves to root
(input tokens upward).
• Recognizes handles (rightmost derivations in reverse)
and reduces them to non-terminals (shift-reducing).
• Concept:
– Goal: Find a rightmost derivation in reverse.
– Key idea:
• Identify handles (substrings that match the right side of a
production).
• Reduce the handle to its corresponding non-terminal.
– Uses a stack to keep track of partially parsed input.
18
 Types of LR Parsers
• LR Parsers:
– L → Left-to-right scanning of input
– R → Rightmost derivation in reverse
• Types of LR Parsers:
Parser Description Notes
LR(0) No lookahead Rarely used
Uses FOLLOW sets for
SLR (Simple LR) Simpler, less powerful
decisions
LALR (Lookahead Most commonly used in
Combines states of LR(1)
LR) practice
Powerful but generates larger
LR(1) Uses 1 lookahead
tables
19
 Shift-Reduce Parsing
• Use in bottom-up parsers
• How it works:

Action Description
Shift Push the next input symbol onto the stack.
Replace a handle on the stack with the
Reduce
corresponding non-terminal.
Accept Input is successfully parsed.
Error Input does not match any production.

20
 Shift-Reduce Parsing Example
• Example Grammar: E → E + id | id
• Input: id + id
• Shift-Reduce Steps:
Stack Input Action
$ id+id$ Shift id
$ id +id$ Reduce id → E
$E +id$ Shift +
$E+ id$ Shift id
$ E + id $ Reduce id → E
$E $ Accept
21
 Advantages and Disadvantages of
Bottom-Up Parsing
• Advantages
– Can handle a larger class of grammars than top-down
parsing (LL).
– Does not require left-factoring or removal of left recursion.
– Automatically handles operator precedence and
associativity.
• Disadvantages
– Parsing tables can be large and complex.
– More difficult to implement manually (compared to
recursive descent).
– Error messages can be less intuitive than top-down parsers.22
 Yacc/Bison Tool
• Yacc (Yet Another Compiler Compiler) and
Bison (GNU version of Yacc) are tools used to
automatically generate parsers for
programming languages.
• They are bottom-up parser generators,
usually producing LALR parsers.
• Features:
– Takes a CFG (in a specific syntax) and produces C code for
a parser.
– Usually used with Lex/Flex (lexer generator).
• Workflow: 23
 Purpose
• Automates parser generation based on
context-free grammars.
• Handles syntax analysis and shift-reduce
parsing automatically.
• Commonly used with Lex/Flex (lexer
generator) for complete compiler front-ends.

24
 How Yacc/Bison Works
• Input:
– A grammar file describing the language syntax.
– Grammar is written in Yacc/Bison syntax with semantic
actions (optional C/C++ code).
• Process:
– Generates C code implementing the parser.
– Builds parsing tables internally using LALR(1) algorithm.
• Output:
– Parser code that can:
• Read tokens from a lexer (Lex/Flex)
• Perform shift-reduce parsing
• Execute semantic actions when a production is reduced 25
 Grammar Rules and Actions
• Grammar rules - define how tokens combine
to form language constructs.
• Actions - are code snippets executed when a
rule is applied.

26
 Example (Simple Arithmetic Expressions)
%token ID NUMBER
%left '+' '-'

%%
expr: expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| NUMBER { $$ = $1; }
| ID { $$ = lookup($1); }
;
%%

• Explanation:
– $1, $3: Values of symbols on the right-hand side of the production.
– $$: Value assigned to the left-hand side non-terminal.
– %left: Declares operator precedence and associativity.
27
 Integration of Lex/Flex with Yacc
• Lex/Flex generates a lexer that produces
tokens (like ID, NUMBER).
• Yacc/Bison parser reads these tokens and
builds the parse tree or performs semantic
actions.
• Workflow:
– Source Code → Lex/Flex → Tokens → Yacc/Bison
→ Parse Tree / Actions → Intermediate Code

28
 Advantages of Using Lex with Yacc
• Separation of concerns:
– Lex handles low-level pattern matching (tokens).
– Yacc handles high-level syntax (grammar rules
and semantic actions).
• Efficiency:
– Lexer produces tokens fast.
– Parser efficiently applies LALR parsing tables.
• Ease of Maintenance:
– Easy to modify the grammar in Yacc or token
patterns in Lex independently. 29