UNIT –II SYNTAX ANALYSIS

1. Define Parser
A parsing or syntax analysis is a process which takes the input string w and produces either a
parse tree (syntactic structure) or generates the syntactic errors.
Example a:=b+c :=
a +

b c
2. Why lexical and syntax analyzer are separated out?
The lexical analyzer scans the input program and collects the tokens from it. On the other hand
parser builds a parser tree using these tokens. These are two important activities and these activities
are independently carried out by these two phases.
Separating out these two phases has tow advantages- Firstly it accelerates the process of
compilation and secondly the errors in the source input can be identified precisely.
3. Define Context free grammar?
The context free grammar G is a collection of following things
V is set of non-terminals
T is a set of terminals
S is a start symbol
P is a set of production rules
Thus G can be represented as G=(V,T,S,P)
The production rules are given in following form-
Non-terminal → (V U T)*
4. Define an ambiguous grammar
The ambiguous grammar is a grammar in which more then one parse trees can be generated for
the same input. For example the sting id*id +id can be represented

E E

E + E E * E

Id E * E E + E id

id id id id
5. What are the difference between top-down parser and bottom-up parser?

Top-down parser Bottom-Up Parser

[Link] tree can be built from root to leaves 1. Parse tree can be built from leaves to root
2. This is simple to implement [Link] is complex to implement
3. it is applicable to small class of languages 3. it is applicable to broad class of languages

[Link] is handle pruning?

In bottom up parsing the process of detecting handle and using them in reduction is called handle
pruning.
Example: Consider the grammar,
E->E+E
E->id
Now consider the string id+id+id and the rightmost derivation is
E=>E+E
E=>E+E+E
E=>E+E+id
E=>E+id+id
E=>id+id+id
The bold strings are called handles.
Right sentinel form handle Production
id+id+id id E->id
E+id+id id E->id
E+E+id Id E->id
E+E+E E+E E->E+E
E+E E+E E->E+E
E

7. What is the Left Recursion?

The rule to eliminate left recursion is
A->Aα / β
Then
A -> βA’
A’->αA’/Є.
 PART B

1. Explain the error recovery strategies in syntax analysis.

The different strategies that a parse uses to recover from a syntactic error are:
1. Panic mode
2. Phrase level
3. Error productions
4. Global correction
Panic mode recovery:
✓ On discovering an error, the parser discards input symbols one at a time until a synchronizing
token is found. The synchronizing tokens are usually delimiters, such as semicolon or end.
✓ It has the advantage of simplicity and does not go into an infinite loop. When multiple errors in
the same statement are rare, this method is quite useful.
Phrase level recovery:
✓ On discovering an error, the parser performs local correction on the remaining input that allows it
to continue. Example: Insert a missing semicolon or delete an extraneous semicolon etc.
Error productions:
✓ The parser is constructed using augmented grammar with error productions. If an error production
is used by the parser, appropriate error diagnostics can be generated to indicate the erroneous
constructs recognized by the input.
Global correction:
✓ Given an incorrect input string x and grammar G, certain algorithms can be used to find a parse
tree for a string y, such that the number of insertions, deletions and changes of tokens is as small
as possible.
✓ However, these methods are in general too costly in terms of time and space.

2. Write a algorithms for FIRST and FOLLOW functions of predictive LL(1) parser

The construction of predictive LL (1) parser is based on two very important functions and those are
FIRST and FOLLOW.
For construction of predictive LL (1) parser we have to follow the following steps-
1. Computation of FIRST and FOLLOW function.
2. Construct the predictive parsing table using FIRST and FOLLOW functions.
3. Parse the input string with the help of predictive parsing table.
FIRST function
FIRST(α) is a set of terminal symbols that are first symbols appearing at R.H.S in derivation of α.
if α=>ε then ε is also in FIRST(α).
Following are the rules used to compute the FIRST functions.
1. If the terminal symbol a then FIRST(a)={a}
2. If there is a rule X -> ε then FIRST(X)={ ε }
3. For the rule A-> X1 X2 X3…Xk FIRST (A) = (FIRST(X1) U FIRST(X2)U FIRST(X3)…U FIRST(XK))
Where k Xj≤n such that 1≤j≤k-1
FOLLOW function
FOLLOW (A) is defined as the set of terminal symbols that appear immediately to the right of A.
In other words
FOLLOW(A) = { a |S =>α Aa β where α and β are some grammar symbols may be terminal or non-
terminal}.
The rules for computing FOLLOW function are as given below-
1. For the start symbol S place $ in FOLLOW(S).
2. If there is a production A->α B β then everything in FIRST (β) without ε is to be placed in
FOLLOW(B).
[Link] there is a production A->α B β or A -> α B and FIRST(β)={ ε } then FOLLOW (A)=FOLLOW(B) or
FOLLOW (B)=FOLLOW(A). That means everything in FOLLOW (A) is in FOLLOW (B).

3. Construct non recursive predictive parsing table for the following grammar
E->E or E | E and E | not E | (E) | 0| 1.
Answer:
As the given grammar needs to be left factored. Also the ambiguity of this grammar needs to be
removed. The modified grammar will be as follows:
• Eliminating ambiguity
E ->E or T
E-> T
T->T and F
T->F
F->not G
F->G
G-> (E) |0|1
• Eliminating Left Recursion
E -> TE’
E’-> or TE’ | ε
T -> FT’
T’ -> and FT’ | ε
F -> not G
F -> G
G-> (E)|0|1

The FIRST & FOLLOW for above grammar is

FIRST (E)={not,(,0,1}
FIRST (E’)={or, ε }
FIRST (T)={not,(,0,1 }
FIRST (T’)={and, ε }
FIRST (F)={not, (,0,1 }
FIRST (G)={(,0,1 }
FOLLOW(E)={),$}
FOLLOW(E’)={),$}
FOLLOW(T)={or,),$}
FOLLOW(T’)={or,),$}
FOLLOW(F)={and,or,),$}
FOLLOW(G)={or,and,),$}

The Predictive Parsing Table:

or and not ( ) 0 1 $
E Error Error E->TE’ E->TE’ Error E->TE’ E->TE’ Error
E’ E’->orTE’ Error Error Error E’->ε Error Error E’->ε
T Error Error T->FT’ T->FT’ Error T->FT’ T->FT’ Error
T’ Error T->andFT’ Error Error T’->ε Error Error T’->ε
F Error Error F->not G F->G Error F->G F->G Error
G Error Error Error G->(E) Error G->0 G->1 Error
 Parsing String:
Stack Input buffering Action
$E 0 or 1 and 0 $
$E’T 0 or 1 and 0 $ E->TE’
$E’T’F 0 or 1 and 0 $ T->FT’
$E’T’G 0 or 1 and 0 $ F->G
$E’T’0 0or 1 and 0 $ G->0
$E’T’ or 1 and 0 $
$E’ or 1 and 0 $ T’->ε
$E’T or or 1 and 0 $ E’->orTE’
$E’T 1 and 0 $
$E’T’F 1 and 0 $ T->FT’
$E’T’G 1 and 0 $ F->G
$E’T’1 1 and 0 $ G->1
$E’T’ and 0 $
$E’T’F and and 0 $ T’->and FT’
$E’T’G 0$ F->G
$E’T’ 0 0$ G->0
$E’T’ $ T’->ε
$E’ $ E’->ε
$ $ Accepted

4. Construct the predictive parser for the following grammar:

S→ (L)/a
L→L, S/S
Solution:
As the given grammar is left recursive because of
L→L,S/S
We will first eliminate left recursion . as
A→Aα/β can be converted as
A→βA’
A’→αA’|Ɛ
We can write L→L,S/S
L→SL’
 L’→,SL’|Ɛ
Now the grammar taken for predictive parsing is
S→ (L)/a
L→SL’
L’→,SL’|Ɛ
Now we will compute FIRST and FOLLOW of non terminals
FIRST(S) = {( , a}
FIRST(L) = {( , a}
FIRST(L’) = {, , a}

FOLLOW(S) = {, , ) , $}
FOLLOW(L) = {)}
FOLLOW(L’)= {)}

The predictive parsing table can be constructed as

a ( ) ‘ $
S S→a S→(L) Error Error Error
L L→SL’ L→SL’ Error Error Error
L’ Error Error L’→€ L’→€ Error

As we have constructed a predictive parsing table in the string (a,a)

5. Consider the following grammar
S->TL;
T->int | float
L-> L , id | id
Parse the input string int id , id; using shift reduce parser
Answer:
Shift reduce parser:
Shift reduce parser attempts to construct parse tree from leaves to roots. Thus it works on the same
principle of bottom up parser.
A shift reduce parser requires following data structures
1. The input buffer storing the input string
2. A stack for storing and accessing the L.H.S and R.H.S of rules
Initial configuration of shift reduce parser is
Stack Input Buffer

$ $

The shift reduce parser performs following basic operations

1. Shift
2. Reduce
3. Accept
4. Errors

Stack Input buffer Action

$ int id , id;$ shift
$int id , id ; $ Reduce by T->int
$T id , id ; $ shift
$T id , id ; $ Reduce by L->id
$TL , id ; $ shift
$TL, id ; $ shift
$T L , id ; $ Reduce by L->L , id
$TL ; $ shift
$TL; $ Reduce by S->TL;
$S $ Accept
6. what is recursive descent parser? Construct a recursive descent parser for the following
grammar.? E->E+E/T
T->TF/F
F->F*/a/b
Answer:
Recursive Descent Paring
A parser that uses collection of recursive procedures for parsing the given input string is called
recursive descent parser. In this type of parser the CFG is used to build the recursive routines. The R.H.S
of the production rule is directly converted to a program code symbol by symbol For each non-terminal a
separate procedure is written and body of the procedure(code) is R.H.S of the corresponding non-
terminal.
Basic Types for Construction of RD parser
The R.H.S of the rule is directly converted into the program code symbol by symbol.
1. If the input symbol is non-terminal then a call to the procedure corresponding the non-terminal is
made.
2. If the input symbol is terminal then it is matched with the lookahead from input. The lookahead
pointer has to be advanced on matching of the input symbol.
3. If the production rule has many alternates then all these alternates has be combined into a single
body of procedure.
4. The parser should be activated by a procedure corresponding to the start symbol.
E->E+T/T
T->TF/F
F->F*/a/b.
The given grammar is a left recursive grammar. We will eliminate this left recursion before converting it
to recursive descent parser.
The rule to eliminate left recursion is
If A->Aα|β
then
A->βA’ and A’->αA’/Є.
E->TE’
E’->+TE’| ε
T->FT’
T’->FT’| ε
F->aF’|bF’
 F’->*F’|Є
Now the recursive desent parser is
Procedure E ( )
{
T ( );
Edash( );
}
If (lookahead=’$’)
{
Declare success;
}
Else Error;
Procedure Edash( )
{
If (lookhead = ‘+’)
{
Match (‘+’)
T ();
Edash( );
}
Else null;
}
Procedure T ( )
{
F ( );
Tdash( );
}
Procedure Tdash( )
{
If(true)
{
F ( );
Tdash( );
}
 Else null;
}
Procedure F ( )
{
If (lookhead=’a’ || lookahead=’b’)
Fdash( );
}
Procedure Fdash()
{
If(lookahead=’*’)
Match(`*’)
Fdash( );
}
Else null;
Procedure match (token t)
{
If(lookahead = t)
Lookahead =next_token ;
Else
Error
}
Procedure error
{
Print (“error!”);
}
7. Construct a SLR construction table for the following grammar or LR(0) Parser
E->E+T
E->T
T->T*F
T->F
F->(E)
F->id

Step 1 : Convert given grammar into augmented grammar.

Augmented grammar : GOTO (I0 , id )
E’ → E I5 : F → id .
E→E+T
E→T
T→T*F GOTO ( I1 , + )
T→F I6 : E → E + . T
F → (E) T→.T*F
F → id T→.F
Step 2 : Find LR (0) items. F → . (E)
I0 : E’ → . E F → . id
E→.E+T
E→.T GOTO ( I2 , * )
T→.T*F I7 : T → T * . F
T→.F F → . (E)
F → . (E) F → . id
F → . id
GOTO ( I0 , E) GOTO ( I4 , E )
I1 : E’ → E . I8 : F → ( E . )
E→E.+T E→E.+T

GOTO (I0 , T) GOTO ( I6 , T )

I2 : E → T . I9 : E → E + T.

T→T.*F T→T.*F

GOTO (I0 , F)
I3 : T → F . GOTO ( I7 , F )
I10 : T → T * F .

GOTO (I0 , ( ) GOTO ( I8 , ) )

I4 : F → ( . E) I11 : F → ( E ) .

E→.E+T FOLLOW(E’)= {$}

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

F → . (E)
F → . id
SLR parsing table:
State Action GOTO
id + * ( ) $ E T F
0 S5 S4 1 2 3
1 S6 ACCEPT
2 r2 S7 r2 r2
3 r4 r4 r4 r4
4 S5 S4 8 2 3
5 r6 r6 r6 r6
6 S5 S4 9 3
7 S5 S4 10
8 S6 S11
9 r1 S7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Blank entries are error entries.
8. Generate SLR parsing table for the following grammar
S->Aa|bAc|Bc|bBa
A->d
B->d
And parse the sentence “bdc” and “dd”
Solution: we will write the grammar using dot operator.
I₀:
S’->.S
S->.Aa
S->.bAc
S->.Bc
S->.bBa
A->.d
B->.d
Now we will apply goto on each symbol from I₀. Each goto (I) will generate new subsequent states
I₁: goto (I₀,S)
S’->S.
I₂: goto (I₀,A)
S->A .a
I₃: goto (I₀,b)
S->b .Ac
S->b .Ba
A -> .d
B->.d
I₄: goto (I₀,B)
S->B .c
I₅: goto (I₀,d)
A->d.
B -> d.
I₆: goto (I₂,a)
S->Aa.
I₇: goto (I₃,A)
S->bA .c
 I₈: goto (I₃,B)
S->bB .a
I₉: goto (I₄,c)
S ->Bc .
I₁₀: goto (I₇,c)
S -> b Ac.
I₁₁: goto (I₈,a)
S -> bBa .
Now we will compute FOLLOW of all non-terminal symbols
FOLLOW(S)={$}
FOLLOW(A)={a,c}
FOLLOW(B)={a,c}

The SLR parsing table will be

The given grammar is not SLR(1) as I5 entry in table shows reduce/reduce conflict
Exercises:

9). Consider the following grammar

S->L=R
S->R
L->*R
L->id
R->L Discuss the LALR parsing method for this grammar. List out Canonical Collections and also
construct a parsing table.

10). Construct CLR parsing table from

S->AA,
A->Aa/b