Chapter 4

Syntax Analysis
 An Overview of Parsing
Why are Grammars to formally describe Languages Important ?
1. Precise, easy-to-understand representations
2. Compiler-writing tools can take grammar and generate a
compiler
3. Allow language to be evolved (new statements, changes to
statements, etc.) Languages are not static, but are constantly
upgraded to add new features or fix “old” ones

How do grammars relate to parsing process ?

 Parsing During Compilation
regular
expressions errors

lexical token rest of intermediate

source parser parse
program analyzer get next tree front end repres
token

symbol
table 1. Also technically part or
parsing
• uses a grammar to check structure of tokens 2. Includes augmenting
• produces a parse tree info on tokens in source,
• syntactic errors and recovery type checking, semantic
• recognize correct syntax analysis
• report errors
 Parsing Responsibilities
Syntax Error Identification / Handling
Recall typical error types:
Lexical : Misspellings
Syntactic : Omission, wrong order of tokens
Semantic : Incompatible types
Logical : Infinite loop / recursive call
Majority of error processing occurs during syntax analysis
NOTE: Not all errors are identifiable !!
 Key Issues – Error Processing

1. Detecting errors
2. Finding position at which they occur
3. Clear / accurate presentation
4. Recover (pass over) to continue and find later errors
5. Don’t impact compilation of “correct” programs
 What are some Typical Errors ?
#include<stdio.h>
int f1(int v)
{ int i,j=0;
for (i=1;i<5;i++) As reported by MS VC++
{ j=v+f2(i) }
'f2' undefined;
return j; } syntax error : missing ';' before '}‘
int f2(int u) syntax error : missing ';' before identifier 'printf'
{ int j;
j=u+f1(u*u);
return j; } Which are “easy” to recover
int main() from? Which are “hard” ?
{ int i,j=0;
for (i=1;i<10;i++)
{ j=j+i*i printf(“%d\n”,i); }
printf("%d\n",f1(j));
return 0;
}
 Error Recovery Strategies
Panic Mode – Discard tokens until a “synchronous” token is
found ( end, “;”, “}”, etc. )
-- Decision of designer
-- Problems:
skip input miss declaration – causing more errors
miss errors in skipped material
-- Advantages:
simple suited to 1 error per statement

Phrase Level – Local correction on input

-- “,” ”;” – Delete “,” – insert “;”
-- Also decision of designer
-- Not suited to all situations
-- Used in conjunction with panic mode to allow less input
to be skipped
 Error Recovery Strategies – (2)
Error Productions:
--Augment grammar with rules
-- Augment grammar used for parser
construction / generation
-- example: add a rule for
:= in C assignment statements
Report error but continue compile
-- Self correction + diagnostic messages

Global Correction:
-- Adding / deleting / replacing symbols
may do many changes !
-- Algorithms available to minimize changes
costly - key issues
 Motivating Grammars
• Regular Expressions
→ Basis of lexical analysis
→ Represent regular languages
• Context Free Grammars
→ Basis of parsing
→ Represent language constructs

Reg. Lang. CFLs

 Context Free Grammars :
Concepts & Terminology
Definition: A Context Free Grammar, CFG, is described by T, NT,
S, PR, where:
T: Terminals / tokens of the language
NT: Non-terminals to denote sets of strings generated by the
grammar & in the language
S: Start symbol, SNT, which defines all strings of the
language
PR: Production rules to indicate how T and NT are combined to
generate valid strings of the language.
PR: NT → (T | NT)*
Like a Regular Expression / DFA / NFA, a Context Free Grammar
is a mathematical model
 Context Free Grammars : A First Look
assign_stmt → id := expr ;
expr → expr operator term
expr → term
term → id
term → real
term → integer
operator → +
operator → -

Derivation: A sequence of grammar rule applications and

substitutions that transform a starting non-term into a sequence of
terminals / tokens.
Simply stated: Grammars / production rules allow us to “rewrite”
and “identify” correct syntax.
 Derivation
Let’s derive: id := id + real – integer ; using production:
assign_stmt assign_stmt → id := expr ;
→ id := expr ; expr → expr operator term
→id := expr operator term; expr → expr operator term
→id := expr operator term operator term; expr → term
→ id := term operator term operator term; term → id
→ id := id operator term operator term; operator → +
→ id := id + term operator term; term → real
→ id := id + real operator term; operator → -
→ id := id + real - term; term → integer
→ id := id + real - integer;
 Example Grammar
expr → expr op expr
expr → ( expr )
expr → - expr
expr → id
op → + 9 Production rules
op → -
op → *
op → /
op → 

To simplify / standardize notation, we offer a

synopsis of terminology.
 Example Grammar - Terminology
Terminals: a,b,c,+,-,punc,0,1,…,9
Non Terminals: A,B,C,S
T or NT: X,Y,Z
Strings of Terminals: u,v,…,z in T*
Strings of T / NT:  ,  in ( T  NT)*
Alternatives of production rules:
A→ 1; A→ 2; …; A→ k;  A → 1 | 2 | … | 1
First NT on LHS of 1st production rule is designated as start
symbol !

E → E A E | ( E ) | -E | id
A→+|-|*| / |
 Grammar Concepts
A step in a derivation is zero or one action that replaces a NT
with the RHS of a production rule.
EXAMPLE: E  -E (the  means “derives” in one step) using
the production rule: E → -E
EXAMPLE: E  E A E  E * E  E * ( E )

DEFINITION:  derives in one step

+
 derives in  one step

* derives in  zero steps

EXAMPLES:  A      if A→  is a production rule

*
1  2 …  n → 1  n ;    for all 
*

If  
*  and  →  then  
* 
 How does this relate to Languages?
+
Let G be a CFG with start symbol S. Then S W (where W has no
non-terminals) represents the language generated by G, denoted
L(G). So WL(G)  S W. +

W : is a sentence of G
When S  (and  may have NTs) it is called a
sentential form of G.

EXAMPLE: id * id is a sentence
Here’s the derivation:
E  E A E E * E  id * E  id * id
Sentential forms
E
*
id * id
 Other Derivation Concepts
Leftmost: Replace the leftmost non-terminal symbol
E  E A E  id A E  id * E  id * id
lm lm lm lm

Rightmost: Replace the leftmost non-terminal symbol

 EAE 
E rm rm
E A id 
rm
E * id 
rm
id * id

Important Notes: A→

If A lm
   , what’s true about  ?
If A     , what’s true about  ?
rm
Derivations: Actions to parse input can be represented
pictorially in a parse tree.
Examples of LM / RM Derivations

E → E A E | ( E ) | -E | id
A→+|-|*| / |

A leftmost derivation of : id + id * id

A rightmost derivation of : id + id * id
Derivations & Parse Tree
E
E EAE E A E
E
E*E E A E

*
E

 id * E E A E

id *
E

 id * id E A E

id * id
 Parse Trees and Derivations
Consider the expression grammar:
E → E+E | E*E | (E) | -E | id
Leftmost derivations of id + id * id
E
E
EE+E E + E  id + E E + E
E + E
id

id + E  id + E * E E + E

id E * E
Parse Tree & Derivations - continued
E

id + E * E  id + id * E E + E

id E * E

id

id + id * E  id + id * id E + E

id E * E

id id
Alternative Parse Tree & Derivation
EE*E
E
E+E*E
E * E
 id + E * E E + E id
 id + id * E id id
 id + id * id

WHAT’S THE ISSUE HERE ?

Two distinct leftmost derivations!
 Resolving Grammar Problems/Difficulties

Regular Expressions : Basis of Lexical Analysis

Reg. Expr. → generate/represent regular languages
Reg. Languages → smallest, most well defined class of languages
Context Free Grammars: Basis of Parsing
CFGs → represent context free languages
CFLs → contain more powerful languages

Reg. Lang. CFLs

23
Resolving Problems/Difficulties – (2)
Since Reg. Lang.  Context Free Lang., it is possible
to go from reg. expr. to CFGs via NFA.

Recall: (a | b)*abb

a
start a b b
0 1 2 3

24
 Resolving Problems/Difficulties – (3)
Construct CFG as follows:
1. Each State I has non-terminal Ai : A0, A1, A2, A3

2. If i a j then Ai →a Aj

3. If i b j then Ai →bAj

4. If I is an accepting state, Ai → : A3 → 

5. If I is a starting state, Ai is the start symbol : A0

T={a,b}, NT={A0, A1, A2, A3}, S = A0

PR ={ A0→ aA0 | aA1 | bA0 ;
A1 → bA2 ; a
A2 → bA3 ; start
0 a 1 b 2 b 3
A3 →  } 25
b
How Does This CFG Derive Strings ?
a
start a b b
0 1 2 3

b
vs.
A0→ aA0, A0→ aA1
A0→ bA0, A1→ bA2
A2→ bA3, A3→ 

How is abaabb derived in each ?

26
 Regular Expressions vs. CFGs
Regular expressions for lexical syntax
1. CFGs are overkill, lexical rules are quite simple and
straightforward
2. REs – concise / easy to understand
3. More efficient lexical analyzer can be constructed
4. RE for lexical analysis and CFGs for parsing
promotes modularity, low coupling & high cohesion.

CFGs : Match tokens “(“ “)”, begin / end, if-then-else, whiles,

proc/func calls, …
Intended for structural associations between tokens !

27
Are tokens in correct order ?
 Resolving Grammar Difficulties :
Motivation
1. Humans write / develop grammars
2. Different parsing approaches have different needs

Top-Down vs. Bottom-Up

• For: 1 → remove “errors”
• For: 2 → put / redesign grammar

- ambiguity
- -moves
Grammar
- cycles
Problems
- left recursion
- left factoring 28
 Resolving Problems: Ambiguous
Grammars
Consider the following grammar segment:
stmt → if expr then stmt Else must match
| if expr then stmt else stmt
to previous then.
| other (any other statement)
Structure indicates
What’s problem here ? parse sub-tree for
expression.
Let’s consider a simple parse tree:

stmt

if expr then stmt else stmt

E1 S1 expr then stmt else stmt

if

E2 S2 S3
29
Example : What Happens with this
string?
If E1 then if E2 then S1 else S2
How is this parsed ?

if E1 then if E1 then
if E2 then if E2 then
S1 vs. S1
else else
S2 S2

What’s the issue here ?

30
 Parse Trees for Example
Form 1: stmt

if expr then stmt

E1 then stmt else stmt

if expr

E2 S1 S2

Form 2:
stmt

if expr then stmt else stmt

E1 expr then stmt S2

if

What’s the issue here ? E2 S1

31
 Removing Ambiguity
Take Original Grammar:
stmt → if expr then stmt
| if expr then stmt else stmt
| other (any other statement)

Rule: Match each else with the closest previous

unmatched then.
Revise to remove ambiguity:
stmt → matched_stmt | unmatched_stmt
matched_stmt → if expr then matched_stmt else matched_stmt | other
unmatched_stmt → if expr then stmt
| if expr then matched_stmt else unmatched_stmt
32
 Resolving Difficulties : Left Recursion
A left recursive grammar has rules that support the
derivation : A  +
A, for some .

Top-Down parsing can’t reconcile this type of grammar,

since it could consistently make choice which wouldn’t
allow termination.
A  A  A  A … etc. A→ A | 
Take left recursive grammar:
A → A | 
To the following:
A → A’
A’ → A’ |  33
 Why is Left Recursion a Problem ?
Consider: Derive : id + id + id
E→E+T | T EE+T
T→T*F | F
F → ( E ) | id

How can left recursion be removed ?

E→E+T | T What does this generate?
EE+TT+T
EE+TE+T+TT+T+T

How does this build strings ?
What does each string have to start with ? 34
Resolving Difficulties : Left Recursion (2)
Informal Discussion:

Take all productions for A and order as:

A → A1 | A2 | … | Am | 1 | 2 | … | n
Where no i begins with A.
Now apply concepts of previous slide:
A → 1A’ | 2A’ | … | nA’
A’ → 1A’ | 2A’| … | m A’ | 
For our example:
E → TE’
E→E+T | T E’ → + TE’ | 
T→T*F | F T → FT’
T’ → * FT’ | 
F → ( E ) | id F → ( E ) | id
35
 Resolving Difficulties : Left Recursion (3)
Problem: If left recursion is two-or-more levels deep,
this isn’t enough
S → Aa | b
S  Aa  Sda
A → Ac | Sd | 
Algorithm:
Input: Grammar G with ordered Non-Terminals A1, ..., An
Output: An equivalent grammar with no left recursion
1. Arrange the non-terminals in some order A1=start NT,A2,…An
2. for i := 1 to n do begin
for j := 1 to i – 1 do begin
replace each production of the form Ai → Aj
by the productions Ai → 1 | 2 | … | k
where Aj → 1|2|…|k are all current Aj productions;
end
eliminate the immediate left recursion among Ai productions 36
end
 Using the Algorithm
Apply the algorithm to: A1 → A2a | b| 
A2 → A2c | A1d
i=1
For A1 there is no left recursion

i=2
for j=1 to 1 do
Take productions: A2 → A1 and replace with
A2 → 1  | 2  | … | k |
where A1→ 1 | 2 | … | k are A1 productions
in our case A2 → A1d becomes A2 → A2ad | bd | d
What’s left: A1→ A2a | b | 
Are we done ?
A2 → A2 c | A2 ad | bd | d 37
 Using the Algorithm (2)
No ! We must still remove A2 left recursion !
A1→ A2a | b | 
A2 → A2 c | A2 ad | bd | d
Recall: A1→ A2a | b | 
A → A1 | A2 | … | Am | 1 | 2 | … | n
A2 → bdA2’ | dA2’

A → 1A’ | 2A’ | … | nA’

A2’ → c A2’ | adA2’ | 
A’ → 1A’ | 2A’| … | m A’ | 

Apply to above case. What do you get ?

38
Removing Difficulties : Left Factoring
Problem : Uncertain which of 2 rules to choose:
stmt → if expr then stmt else stmt
| if expr then stmt
When do you know which one is valid ?
What’s the general form of stmt ?
A → 1 | 2  : if expr then stmt
1: else stmt 2 : 

Transform to: EXAMPLE:

A →  A’ stmt → if expr then stmt rest
A’ → 1 | 2 rest → else stmt |  39
The End