UNIT –III

Bottom-up Parsing

Bottom-up parsing corresponds to the construction of a parse tree for an input string
beginning at the leaves (the bottom nodes) and working up towards the root (the top node). It
involves “reducing an input string ‘w’ to the Start Symbol of the grammar. in each reduction
step, a perticular substring matching the right side of the production is replaced by symbol on the
left of that production and it is the Right most derivation. For example consider the following
Grammar:

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

Bottom up parsing of the input string “id * id “is as follows:

Input String Sub String Reducing production

id*id id F->id
F*id F->T
T*id id F->id
T*F * T->T*F
T E->T
Start symbol. Hence, the input
E
String is accepted

Parse Tree representation is as follows:

Fig: A Bottom-up Parse tree for the input String “id*id”

Bottom up parsing is classified in to

1. Shift-Reduce Parsing
2. Operator precedence parsing
3. Table Driven L R Parsing
i. LR ( 1 )
ii. SLR( 1 )
iii. CLR ( 1 )
iv. LALR( 1 )

Shift-Reduce Parsing

Shift-reduce parsing is a form of bottom-up parsing in which a stack holds grammar

symbols and an input buffer holds the rest of the string to be parsed, We use $ to mark the
bottom of the stack and also the right end of the input. And it makes use of the process of shift
and reduce actions to accept the input string. Here, the parse tree is Constructed bottom up from
the leaf nodes towards the root node.

When we are parsing the given input string, if the match occurs the parser takes the
reduce action otherwise it will goes for shift action. And it can accept ambiguous grammars also.

Ex; consider the below grammar to accept the input string “id * id “using S-R parser

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

Actions of the Shift-reduce parser using Stack implementation

STACK INPUT ACTION

$ Id*id$ Shift
$id *id$ Reduce with F d
$F *id$ Reduce with T F
$T *id$ Shift
$T* id$ Shift
$T*id $ Reduce with F id
$T*F $ Reduce with T T*F
$T $ Reduce with E T
$E $ Accept
Consider the following grammar:

S aAcBe
A Ab|b
B d

Let the input string is “abbcde”. The series of shift and reductions to the start symbol are
as follows.
abbcde aAbcde aAcde aAcBe S

Note: in the above example there are two actions possible in the second Step, these are as
follows:
1. Shift action going to 3rd Step
2. Reduce action, that is A->b
If the parser is taking the 1st action then it can successfully accepts the given input string,
if it is going for second action then it can’t accept given input string. This is called shift reduce
conflict. Where, S-R parser is not able take proper decision, so it not recommended for parsing.

Operator Precedence Parsing

Operator precedence grammar is kinds of shift reduce parsing method that can be applied
to a small class of operator grammars. And it can process ambiguous grammars also.
An operator grammar has two important characteristics:
1. There are no € productions.
2. No production would have two adjacent non terminals.
The operator grammar for to accept expressions is give below:
E E+E
E E-E
E E*E
E E/E
E E^E
E -E
E (E)
E id

Two main Challenges in the operator precedence parsing are:

1. Identification of Correct handles in the reduction step, such that the given input should be
reduced to starting symbol of the grammar.
2. Identification of which production to use for reducing in the reduction steps, such that we
should correctly reduce the given input to the starting symbol of the grammar.
Operator precedence parser consists of:

1. An input buffer that contains string to be parsed followed by a$, a symbol used to
indicate the ending of input.
2. A stack containing a sequence of grammar symbols with a $ at the bottom of the stack.

3. An operator precedence relation table O, containing the precedence ralations between the
pair of terminal. There are three kinds of precedence relations will exist between the pair
of terminal pair ‘a’ and ‘b’ as follows:

1. The relation a<•b implies that he terminal ‘a’ has lower precedence than terminal
‘b’.

2. The relation a•>b implies that he terminal ‘a’ has higher precedence than terminal
‘b’.

3. The relation a=•b implies that he terminal ‘a’ has lower precedence than terminal
‘b’.

4. An operator precedence parsing program takes an input string and determines whether it
conforms to the grammar specifications. It uses an operator precedence parse table and
stack to arrive at the decision.

a1 a2 a3 ……….. $ Input Buffer

Operator precedence
algorithm Parsing Output
Algorithm
$

Stack

Operator Precedence Table

Fig: Components of operator precedence parser

Ex: if the grammar is

E E+E
E E-E
E E*E
E E/E
E E^E
E -E
E (E)
E id construct operator precedence table and accept input string “
id+id*id”

The precedence relations between the operators are

( id ) > ( ^ ) > ( * / ) > ( + - ) > $ , ‘^’ operator is Right Associative and reaming all
operators are Left Associative

+ - * / ^ id ( ) $
+ •> •> <• <• <• <• <• •> •>
- •> •> <• <• <• <• <• •> •>
* •> •> •> •> <• <• <• •> •>
/ •> •> •> •> <• <• <• •> •>
^ •> •> •> •> <• <• <• •> •>
Id •> •> •> •> •> Err Err •> •>
( <• <• <• <• <• <• <• = Err
) •> •> •> •> •> Err Err •> •>
$ <• <• <• <• <• <• <• Err Err

The intention of the precedence relations is to delimit the handle of the given input String
with <• marking the left end of the Handle and •> marking the right end of the handle.

Parsing Action

To locate the handle following steps are followed:

1. Add $ symbol at the both ends of the given input string.
2. Scan the input string from left to right until the right most •> is encountered.
3. Scan towards left over all the equal precedence’s until the first <• precedence is
encountered.
4. Every thing between <• and •> is a handle.
5. $ on S means parsing is success.
Ex: if the input string is “id*id” and the grammar is

E E+E
E E*E Explain the parsing Actions?
E id

1. $ <• id •> *<• id•> $

The first handle is ‘id’ and match for the ‘id ‘in the grammar is E id .
So, id is replaced with the Non terminal E. the given input string can be
written as
2. $ <• E •> *<• id•> $
The parser will not consider the Non terminal as an input. So, they are not
considered in the input string. So , the string becomes
3. $ <• *<• id•> $

The next handle is ‘id’ and match for the ‘id ‘in the grammar is E id .
So, id is replaced with the Non terminal E. the given input string can be
written as
4. $ <• *<• E•> $
The parser will not consider the Non terminal as an input. So, they are not
considered in the input string. So, the string becomes
5. $ <• * •> $

The next handle is ‘*’ and match for the ‘ ‘in the grammar is E E*E.
So, id is replaced with the Non terminal E. the given input string can be
written as
6. $ E $
The parser will not consider the Non terminal as an input. So, they are not
considered in the input string. So, the string becomes
7. $ $
$ On $ means parsing successful.

Operator Parsing Algorithm

The operator precedence Parser parsing program determines the action of the parser
depending on

1. ‘a’ is top most symbol on the Stack

2. ‘b’ is the current input symbol
There are 3 conditions of ‘a’ and ‘b’ that are important for the parsing program

1. a=b=$ , the parsing is successful

2. a <• b or a = b, the parser shifts the input symbol on to the stack and advances
the input pointer to the next input symbol.
3. a •> b, parser performs the reduce action. The parser pops out elements one by
one from the stack until we find the current top of the stack element has lower
precedence than the most recently popped out terminal.

Ex: the sequence of actions taken by the parser using the stack for the input string “id * id “

Stack Input operations

$ id * id $ $ <• id, shift ‘id’ in to stack
$ id *id $ id •> *, reduce ‘id’ using E-> id
$E *id $ $ <• *, shift ‘*’ in to stack
$E* id$ * <• id , shift ‘id’ in to Stack
$E*id $ id •> $, reduce ‘id’ using E->id
$E*E $ *•> $, reduce ‘*’ using E->E*E
$E $ $=$=$, so parsing is successful

E * E

id id

Fig: parse tree for “id * id” using operator precedence parser

Advantages and Disadvantages of Operator Precedence Parsing

The following are the advantages of operator precedence parsing

1. It is simple and easy to implement parsing technique.

 2. The operator precedence parser can be constructed by hand after understanding the
grammar. It is simple to debug.

The following are the disadvantages of operator precedence parsing:

1. It is difficult to handle the operator like ‘-‘which can be either unary or binary and hence
different precedence’s and associativities.

2. It can parse only a small class of grammar.

3. New addition or deletion of the rules requires the parser to be re written.

4. Too many error entries in the parsing tables.

LR Parsing

Most prevalent type of bottom up parsing is LR (k) parsing. Where, L is left to right scan
of the given input string, R is Right Most derivation in reverse and K is no of input symbols as
the Look ahead.

 It is the most general non back tracking shift reduce parsing method

 The class of grammars that can be parsed using the LR methods is a proper superset of
the class of grammars that can be parsed with predictive parsers.

 An LR parser can detect a syntactic error as soon as it is possible to do so, on a left to

right scan of the input.

a1 a2 a3 ………. $ Input Buffer

OUTPUT
LR PARSING ALGORTHM

Shift GOTO
Stack LR Parsing Table

Fig: Components of LR Parsing

LR Parser Consists of

 An input buffer that contains the string to be parsed followed by a $ Symbol, used to
indicate end of input.

 A stack containing a sequence of grammar symbols with a $ at the bottom of the stack,
which initially contains the Initial state of the parsing table on top of $.

 A parsing table (M), it is a two dimensional array M[ state, terminal or Non terminal] and
it contains two parts

1. Action part
The ACTION part of the table is a two dimensional array indexed by state and the
input symbol, i.e. action [state][input], An action table entry can have one of
following four kinds of values in it. They are:
1. Shift X, where X is a State number.

2. Reduce X, where X is a Production number.

3. Accept, signifying the completion of a successful parse.

4. Error entry.

2. GO TO Part
The GO TO part of the table is a two dimensional array indexed by state and a
Non terminal, i.e. GO TO [state][Non terminal]. A GO TO entry has a state
number in the table.

 A parsing Algorithm uses the current State X, the next input symbol ‘a’ to consult the
entry at action[X][a]. it makes one of the four following actions as given below:

1. If the action[X][a]=shift Y, the parser executes a shift of Y on to the top of the stack
and advances the input pointer.

2. If the action[X][a]= reduce Y (Y is the production number reduced in the State X), if
the production is Y->β, then the parser pops 2*β symbols from the stack and push Y
on to the Stack.

3. If the action[X][a]= accept, then the parsing is successful and the input string is
accepted.

4. If the action[X][a]= error, then the parser has discovered an error and calls the error
routine.
The parsing is classified in to

1. LR ( 1 )

2. Simple LR ( 1 )

3. Canonical LR ( 1 )

4. Look ahead LR ( 1 )

LR (1) Parsing

Various steps involved in the LR (1) Parsing:

1. Write the Context free Grammar for the given input string

2. Check for the Ambiguity

3. Add Augment production

4. Create Canonical collection of LR ( 0 ) items

5. Draw DFA

6. Construct the LR ( 1 ) Parsing table

7. Based on the information from the Table, with help of Stack and Parsing algorithm
generate the output.

Augment Grammar

The Augment Grammar G`, is G with a new starting symbol S` an additional production
S` S. this helps the parser to identify when to stop the parsing and announce the acceptance of
the input. The input string is accepted if and only if the parser is about to reduce by S` S. For
example let us consider the Grammar below:

E E+T|T
T T*F
F (E) | id the Augment grammar G` is Represented by

E` E
E E+T|T
T T*F
F (E) | id
NOTE: Augment Grammar is simply adding one extra production by preserving the actual
meaning of the given Grammar G.
Canonical collection of LR (0) items

LR (0) items
An LR (0) item of a Grammar is a production G with dot at some position on the right
side of the production. An item indicates how much of the input has been scanned up to a given
point in the process of parsing. For example, if the Production is X YZ then, The LR (0)
items are:

1. X •AB, indicates that the parser expects a string derivable from AB.
2. X A•B, indicates that the parser has scanned the string derivable from the A and
expecting the string from Y.
3. X AB•, indicates that he parser has scanned the string derivable from AB.

If the grammar is X € the, the LR (0) item is

X •, indicating that the production is reduced one.

Canonical collection
This is the process of grouping the LR (0) items together based on the closure and Go to
operations

Closure operation
If I is an initial State, then the Closure (I) is constructed as follows:
1. Initially, add Augment Production to the state and check for the • symbol in the Right
hand side production, if the • is followed by a Non terminal then Add Productions
which are Stating with that Non Terminal in the State I.
2. If a production X α•Aβ is in I, then add Production which are starting with X in the
State I. Rule 2 is applied until no more productions added to the State I( meaning that
the • is followed by a Terminal symbol).

Ex:
0. E` E E` •E
1. E E+T LR (0) items for the Grammar is E •E+T
2. T F T •F
3. T T*F T •T*F
4. F (E) F • (E)
5. F id F • id
Closure (I0) State
Add E ` • E in I0 State
Since, the ‘•’ symbol in the Right hand side production is followed by A Non
terminal E. So, add productions starting with E in to Io state. So, the state
becomes

0. E ` •E
1. E •E+T
2. T •F
The 1st and 2nd productions are satisfies the 2nd rule. So, add productions
which are starting with E and T in I0
Note: once productions are added in the state the same production should
not added for the 2nd time in the same state. So, the state becomes
0. E` •E
1. E •E+T
2. T •F
3. T •T*F
4. F •(E)
5. F • id

Go to Operation
Go to (I0, X), where I0 is set of items and X is the grammar Symbol on which we
are moving the ‘•’ symbol. It is like finding the next state of the NFA for a give State I0 and the
input symbol is X. For example, if the production is E •E+T

Go to (I0, E) is E` •E, E E•+T

Note: Once we complete the Go to operation, we need to compute closure operation for the
output production

Go to (I0, E) is E E•+T,E` E. = Closure ({E` E•, E E•+T})

E`->.E E E`-> E.
E->.E+T
E-> E.+T
T-> .T*F
Construction of LR (1) parsing Table:

Once we have Created the canonical collection of LR (0) items, need to follow the steps
mentioned below:

If there is a transaction from one state (Ii ) to another state(Ij ) on a terminal value then,
we should write the shift entry in the action part as shown below:

A->α•aβ a A->αa•β States ACTION GO TO

a $ A

Ii Sj
Ii Ij
Ij

If there is a transaction from one state (Ii ) to another state (Ij ) on a Non terminal value
then, we should write the subscript value of Ii in the GO TO part as shown below: part as shown
below:

A->α•Aβ A A->αA•β States ACTION GO TO

a $ A

Ii j
Ii Ij
Ij

If there is one state (Ii), where there is one production which has no transitions. Then, the
production is said to be a reduced production. These productions should have reduced entry in
the Action part along with their production numbers. If the Augment production is reducing then,
write accept in the Action part.
 States ACTION GO TO
1 A->αβ• a $ A

Ii r1 r1
Ii
Ii

Ex: Construct the LR (1) parsing Table for the given Grammar (G)

S aB
B bB | b

Sol: 1. Add Augment Production and insert ‘•’ symbol at the first position for every
production in G

0. S` •S
1. S •aB
2. B •bB
3. B •b

I0 State:
1. Add Augment production to the I0 State and Compute the Closure

I0 = Closure ( S` •S)
Since ‘•’ is followed by the Non terminal, add all productions starting with
S in to I0 State. So, the I0 State becomes
I0 = S` •S
S •aB

Here, in the S production ‘.’ Symbol is following terminal

value so close the state.
I1= Go to (I0, S)
S` S•
Closure( S` S•) = S` S•
Here, The Production is reduced so close the State.

I1= S` S•
I2= Go to ( I0, a) = closure (S a•B)
Here, the ‘•’ symbol is followed by The Non terminal B. So, add
the productions which are Starting B.

I2 = B •bB
B •b
Here, the ‘•’ symbol in the B production is followed by he terminal value. So,
Close the State.

I2= S a•B
B •bB
B •b

I3= Go to ( I2 ,B) = Closure ( S aB• ) = S aB•

I4= Go to ( I2 , b) = closure ({B b•B, B b•})

Add productions starting with B in I4.

B •bB
B •b
The Dot Symbol is followed by the terminal value. So, close the State.

I4= B b•B
B •bB
B •b
B b•

I5= Go to (I2, b) = Closure (B b• ) = B b•

I6= Go to (I4, B) = Closure (B bB• ) = B bB•

I7 = Go to ( I4 , b) = I4
 Drawing DFA:

S->aB•

S`->S•
S I3
I1 B
S->•S

S->•aB
B->b•B
B
a b B->•bB
S->a•B
B->bB•
I0 B->•bB B->•b

B->•b B->b•
b
I5
I4
I2 I4

LR Table:

ACTION GOTO
States
a B $ S B
I0 S2 1
I1 ACCEPT
I2 S4 3
I3 R1 R1 R1
I4 R3 S4/R3 R3 5
I5 R2 R2 R2

Note: if there are multiple entries in the LR (1) parsing table, then it will not accepted by the
LR(1) parser. In the above table I3 row is giving two entries for the single terminal value ‘b’ and
it is called as Shift- Reduce conflict.
Shift-Reduce Conflict in LR (1) Parsing

Shift Reduce Conflict in the LR (1) parsing occurs when a state has
1. A Reduced item of the form A α• and
2. An incomplete item of the form A β•aα as shown below:

1 A-> β•a α States Action GOTO

a
2 B->b• Ij a $ A B

Ii Sj/r2 r2

Ii
Ij

Reduce - Reduce Conflict in LR (1) Parsing

Reduce- Reduce Conflict in the LR (1) parsing occurs when a state has two or more
reduced items of the form
1. A α•
2. B β• as shown below:

States Action GOTO

1 A-> α•
a $ A B
2 B->β•
Ii r1/r2 r1/ r2

Ii Ij

SLR (1) Parsing

Various steps involved in the SLR (1) Parsing:

1. Write the Context free Grammar for the given input string

2. Check for the Ambiguity

 3. Add Augment production

4. Create Canonical collection of LR ( 0 ) items

5. Draw DFA

6. Construct the SLR ( 1 ) Parsing table

7. Based on the information from the Table, with help of Stack and Parsing algorithm
generate the output.

SLR (1) Table Construction

Once we have Created the canonical collection of LR (0) items, need to follow the steps
mentioned below:

If there is a transaction from one state (Ii ) to another state(Ij ) on a terminal value then,
we should write the shift entry in the action part as shown below:

A->α•aβ a A->αa•β States ACTION GO TO

a $ A

Ii Sj
Ii Ij
Ij

If there is a transaction from one state (Ii ) to another state (Ij ) on a Non terminal value
then, we should write the subscript value of Ii in the GO TO part as shown below: part as shown
below:

A States ACTION GO TO

A->α•Aβ A->αA•β a $ A

Ii j
Ii Ij
Ij
 1 If there is one state (Ii), where there is one production (A->αβ•) which has no transitions
to the next State. Then, the production is said to be a reduced production. For all
terminals X in FOLLOW (A), write the reduce entry along with their production
numbers. If the Augment production is reducing then write accept.

1 S -> •aAb
2 A->αβ•
Follow(S) = {$}
Follow (A) = (b}

States ACTION GO TO

2 A->αβ• a b $ S A

Ii r2
Ii
Ii

SLR ( 1 ) table for the Grammar

S aB
B bB | b

Follow (S) = {$}

Follow (B) = {$}

ACTION GOTO
States
a B $ S B
I0 S2 1
I1 ACCEPT
I2 S4 3
I3 R1
I4 S4 R3 5
I5 R2

Note: When Multiple Entries occurs in the SLR table. Then, the grammar is not accepted by
SLR(1) Parser.
Conflicts in the SLR (1) Parsing

When multiple entries occur in the table. Then, the situation is said to be a Conflict.

Shift-Reduce Conflict in SLR (1) Parsing

Shift Reduce Conflict in the LR (1) parsing occurs when a state has
1. A Reduced item of the form A α• and Follow(A) includes the terminal value
‘a’.
2. An incomplete item of the form A β•aα as shown below:

1 A-> β•a α
States Action GOTO
a
2 B->b• Ij a $ A B

Ii Sj/r2
Ii

Reduce - Reduce Conflict in SLR (1) Parsing Ij

Reduce- Reduce Conflict in the LR (1) parsing occurs when a state has two or more
reduced items of the form
1. A α•
2. B β• and Follow (A) ∩ Follow(B) ≠ null as shown below:
If The Grammar is
S-> αAaBa
A-> α
B-> β
Follow(S)= {$}
Follow(A)={a} and Follow(B)= {a}

1 A-> α• States Action GOTO

2 B->β• a $ A B

Ii r1/r2

Ii
Ij
Canonical LR (1) Parsing

Various steps involved in the CLR (1) Parsing:

1. Write the Context free Grammar for the given input string

2. Check for the Ambiguity

3. Add Augment production

4. Create Canonical collection of LR ( 1 ) items

5. Draw DFA

6. Construct the CLR ( 1 ) Parsing table

7. Based on the information from the Table, with help of Stack and Parsing
algorithm generate the output.

LR (1) item
The LR (1) item is defined by production, position of data and a terminal symbol. The
terminal is called as look ahead symbol.

General form of LR (1) item is S->α•Aβ , $

A-> •γ, FIRST(β,$)

Rules to create canonical collection:

1. Every element of I is added to closure of I
2. If an LR (1) item [X-> A•BC, a] exists in I, and there exists a production B->b1b2…..,
then add item [B->• b1b2, z] where z is a terminal in FIRST(Ca), if it is not already
in Closure(I).keep applying this rule until there are no more elements adde.

Ex: if the Grammar is

S->CC
C->cC
C->d
Canonical collection of LR (1) items can be created as follows:
0 S`->•S (Augment Production)
1 S->•CC
2 C->•cC
3 C->•d

I0 State:

Add Augment production and compute the Closure, the look ahead symbol for the Augment
Production is $.

S`->•S, $= Closure(S`->•S, $)

The dot symbol is followed by a Non terminal S. So, add

productions starting with S in I0 State.

S->•CC, FIRST ($), using 2nd rule

S->•CC, $

The dot symbol is followed by a Non terminal C. So, add

productions starting with C in I0 State.

C->•cC, FIRST(C, $)
C->•d, FIRST(C, $)

FIRST(C) = {c, d} so, the items are

C->•cC, c/d
C->•d, c/d

The dot symbol is followed by a terminal value. So, close the I0 State. So, the
productions in the I0 are

S`->•S , $
S->•CC , $
C->•cC, c/d
C->•d , c/d

I1 = Goto ( I0, S)= S`->S•,$

I2 = Go to (I0 , C)= Closure( S-> C•C, $)

S-> C->•cC , $
C->•d,$ So, the I2 State is
 S->C•C,$
C->•cC , $
C->•d,$

I3= Goto(I0,c)= Closure( C->c•C, c/d)

C->•cC, c/d
C->•d , c/d So, the I3 State is

C->c•C, c/d
C->•cC, c/d
C->•d , c/d

I4= Goto( I0, d)= Colsure( C->d•, c/d) = C->d•, c/d

I5 = Goto ( I2, C)= closure(S->CC•,$)= S->CC•, $

I6= Goto ( I2, c)= closure(C->c•C , $)=

C->•cC, $
C->•d , $ S0, the I6 State is

C->c•C , $
C->•cC , $
C->•d,$

I7 = Go to (I2 , d)= Closure(C->d•,$ ) = C->d•, $

Goto(I3, c)= closure(C->•cC, c/d)= I3.

I8= Go to (I3 , C)= Closure(C->cC•, c/d) = C->cC•, c/d

Go to (I3 , c)= Closure(C->c•C, c/d) = I3

Go to (I3 , d)= Closure(C->d•, c/d) = I4

I9= Go to (I6 , C)= Closure(C->cC• , $) = C->cC• , $

Go to (I6 , c)= Closure(C->c•C , $) = I6

Go to (I6 , d)= Closure(C->d•,$ ) = I7

Drawing DFA for the above LR (1) items

S`->S•,$
S->CC•, $

S I1 C I5 C->cC• , $

0 S`->•S , $ S->C•C,$ C->c•C , $ I9

1 S->•CC , $ C->•cC , $ C->•cC , $
C c c
2C- C->•d,$ C->•d,$
>•cC,c/d d I6
3 C->•d
I2 I6 I7
,c/d
I0 c d

d
C->c•C, c/d C->d•, $
C->d•, C->•cC, c/d
c/d C->•d , c/d
C I7
I4
d I3 c
C->cC•,

I4 I3 c/d

I8
Construction of CLR (1) Table

Rule1: if there is an item [A->α•Xβ,b] in Ii and goto(Ii,X) is in Ij then action [Ii][X]= Shift
j, Where X is Terminal.
Rule2: if there is an item [A->α•, b] in Ii and (A≠S`) set action [Ii][b]= reduce along with
the production number.
Rule3: if there is an item [S`->S•, $] in Ii then set action [Ii][$]= Accept.
Rule4: if there is an item [A->α•Xβ,b] in Ii and go to(Ii,X) is in Ij then goto [Ii][X]= j,
Where X is Non Terminal.

ACTION GOTO
States
c D $ S C
I0 S3 S4 1 2
I1 ACCEPT
I2 S6 S7 5
I3 S3 S4 8
I4 R3 R3 5
I5 R1
I6 S6 S7 9
I7 R3
I8 R2 R2
I9 R2

Tab: LR (1) Table

LALR (1) Parsing

The CLR Parser avoids the conflicts in the parse table. But it produces more number of
States when compared to SLR parser. Hence more space is occupied by the table in the memory.
So LALR parsing can be used. Here, the tables obtained are smaller than CLR parse table. But it
also as efficient as CLR parser. Here LR (1) items that have same productions but different look-
aheads are combined to form a single set of items.
 For example, consider the grammar in the previous example. Consider the states I4 and I7
as given below:
I4= Goto( I0, d)= Colsure( C->d•, c/d) = C->d•, c/d

I7 = Go to (I2 , d)= Closure(C->d•,$ ) = C->d•, $

These states are differing only in the look-aheads. They have the same productions.
Hence these states are combined to form a single state called as I47.

Similarly the states I3 and I6 differing only in their look-aheads as given below:
I3= Goto(I0,c)=
C->c•C, c/d
C->•cC, c/d
C->•d , c/d

I6= Goto ( I2, c)=

C->c•C , $
C->•cC , $
C->•d,$

These states are differing only in the look-aheads. They have the same productions.
Hence these states are combined to form a single state called as I36.

Similarly the States I8 and I9 differing only in look-aheads. Hence they combined to form
the state I89.

ACTION GOTO
States
c D $ S C
I0 S36 S47 1 2
I1 ACCEPT
I2 S36 S47 5
I36 S36 S47 89
I47 R3 R3 R3 5
I5 R1
I89 R2 R2 R2

Tab: LALR Table

Conflicts in the CLR (1) Parsing

When multiple entries occur in the table. Then, the situation is said to be a Conflict.

Shift-Reduce Conflict in CLR (1) Parsing

Shift Reduce Conflict in the CLR (1) parsing occurs when a state has
3. A Reduced item of the form A α•, a and
4. An incomplete item of the form A β•aα as shown below:

1 A-> β•a α ,
States Action GOTO
$ a
Ij a $ A B
2 B->b• ,a
Ii Sj/r2
Ii

Ij
Reduce - Reduce Conflict in CLR (1) Parsing

Reduce- Reduce Conflict in the CLR (1) parsing occurs when a state has two or more
reduced items of the form
3. A α•
4. B β• If two productions in a state (I) reducing on same look ahead symbol
as shown below:

1 A-> α• ,a
States Action GOTO
2 B->β•,a
a $ A B

Ii r1/r2

Ii
Ij
String Acceptance using LR Parsing:
Consider the above example, if the input String is cdd
ACTION GOTO
States
c D $ S C
I0 S3 S4 1 2
I1 ACCEPT
I2 S6 S7 5
I3 S3 S4 8
I4 R3 R3 5
I5 R1
I6 S6 S7 9
I7 R3
I8 R2 R2
I9 R2

0 S`->•S (Augment Production)

1 S->•CC
2 C->•cC
3 C->•d

STACK INPUT ACTION

$0 cdd$ Shift S3
$0c3 dd$ Shift S4
$0c3d4 d$ Reduce with R3,C->d, pop
2*β symbols from the stack
$0c3C d$ Goto ( I3, C)=8Shift S6
$0c3C8 d$ Reduce with R2 ,C->cC, pop
2*β symbols from the stack
$0C d$ Goto ( I0, C)=2
$0C2 d$ Shift S7
$0C2d7 $ Reduce with R3,C->d, pop
2*β symbols from the stack
$0C2C $ Goto ( I2, C)=5
$0C2C5 $ Reduce with R1,S->CC, pop
2*β symbols from the stack
$0S $ Goto ( I0, S)=1
$0S1 $ Accept
Handing Ambiguous grammar

Ambiguity

. A Grammar can have more than one parse tree for a string

Consider grammar

string string + string

| string - string

|0|1|.|9

. String 9-5+2 has two parse trees

A grammar is said to be an ambiguous grammar if there is some string that it can generate in
more than one way (i.e., the string has more than one parse tree or more than one leftmost
derivation). A language is inherently ambiguous if it can only be generated by ambiguous
grammars.

For example, consider the following grammar:

string string + string

| string - string

|0|1|.|9

In this grammar, the string 9-5+2 has two possible parse trees as shown in the next slide.

Consider the parse trees for string 9-5+2, expression like this has more than one parse tree. The
two trees for 9-5+2 correspond to the two ways of parenthesizing the expression: (9-5)+2 and 9-
(5+2). The second parenthesization gives the expression the value 2 instead of 6.
Ambiguity is problematic because meaning of the programs can be incorrect

. Ambiguity can be handled in several ways

- Enforce associativity and precedence

- Rewrite the grammar (cleanest way)

There are no general techniques for handling ambiguity

. It is impossible to convert automatically an ambiguous grammar to an unambiguous one

Ambiguity is harmful to the intent of the program. The input might be deciphered in a way which
was not really the intention of the programmer, as shown above in the 9-5+2 example. Though
there is no general technique to handle ambiguity i.e., it is not possible to develop some feature
which automatically identifies and removes ambiguity from any grammar. However, it can be
removed, broadly speaking, in the following possible ways:-

1) Rewriting the whole grammar unambiguously.

2) Implementing precedence and associatively rules in the grammar. We shall discuss this
technique in the later slides.

If an operand has operator on both the sides, the side on which operator takes this operand is the
associativity of that operator

. In a+b+c b is taken by left +

. +, -, *, / are left associative

. ^, = are right associative

. Grammar to generate strings with right associative operators right à letter = right | letter letter
a| b |.| z

A binary operation * on a set S that does not satisfy the associative law is called non-
associative. A left-associative operation is a non-associative operation that is conventionally
evaluated from left to right i.e., operand is taken by the operator on the left side.

For example,

6*5*4 = (6*5)*4 and not 6*(5*4)

6/5/4 = (6/5)/4 and not 6/(5/4)

A right-associative operation is a non-associative operation that is conventionally evaluated from
right to left i.e., operand is taken by the operator on the right side.

For example,

6^5^4 => 6^(5^4) and not (6^5)^4)

x=y=z=5 => x=(y=(z=5))

Following is the grammar to generate strings with left associative operators. (Note that this is left
recursive and may go into infinite loop. But we will handle this problem later on by making it
right recursive)

left left + letter | letter

letter a | b | .... | z

Important Questions:
1. Explain the Operator precedence parsing?
2. Explain the LR (1) Parsing?
3. Write the differences between canonical collection of LR (0) items and LR (1) items?
4. Write the Difference between CLR (1) and LALR(1) parsing?
5. Explain YACC Parser?

Assignment Questions:

1. Explain the conflicts in the Shift reduce Parsing with an example?

2. E E+T|T
T T*F
F (E)|id , construct the LR(1) Parsing table? And explain the Conflicts?
3. E E+T|T
T T*F
F (E)|id , construct the SLR(1) Parsing table? And explain the Conflicts?
4. E E+T|T
T T*F
F (E)|id, construct the CLR(1) Parsing table? And explain the Conflicts?
5. E E+T|T
T T*F
F (E) |id, construct the LALR (1) Parsing table? And explain the Conflicts?

Multiple choices:

1. Not a bottom up parser is _________________.

a. LALR
b. Predictive parser
c. Canonical LR
d. SLR

2. BNF stands for_________________.

a. Backus Norm Form
b. Binary normal form
c. Backus naus form
d. Binary naus form

3. The total number of phases in compiler design is______________.

a. 4
b. 5
c. 3
d. 6

4. Shift reduce parsers are___________________.

A. May be top down or bottom up
B. Top down parsers
C. Predictive parsers
D. Bottom up parsers

5. A collection of semantic rules is called a______________________.

A. Grammar
B. NFA
C. Sentence
D. Language
6. ____________ is an LR(1) item
A. [SAa,b,D]
B. [SAa,b]
C. [SAab,]
D. [S,Aab]

7. A grammr will be meaningless if _____________________.

A. If the left hand side of a production is a single terminal
B. If terminal set and non terminal se are disjoint
C. If the left hand side of a production has more than two non terminals
D. If the left hand side of a production has non terminal

8. The minimum value for k in LR(k) is_____________________.

A. 1
B. 0
C. 2
D. 3

9. In bottom up parsing shift operation performs ___________________.

A. Only push
B. Either push or pop
C. Neither push or pop
D. Only pop

10. Which one of the following is True

A. LALR(1) requires less space compare with CLR(1)
B. LALR(1) is more powerful than CLR(1)
C. LALR(1) requires more space compare with LR(1)
D. LALR(1) is as powerful as an LR(1)

11. YACC specification consists_______________sections.

A. 0
B. 1
C. 3
D. 5
12. A grammar will be meaningless if __________________________.
A. If terminal set and non terminal se are disjoint
B. If the left hand side of a production has non terminal
C. If the left hand side of the production has more than two non terminals
D. If the left hand side of a production is a single terminal
13. Which of the following is an LR(0) item
A. [S.Aab]>
B. [SAa,b,D]>
C. [SAab,]
D. [SAa,b]>
14. Which of the following is true
A. LALR(1) requires more space compare with CLR(1)
B. LALR(1) requires less space compare with LR(1)
C. LARL(1) is as powerful as an LR(1)
D. LALR(1) is more powerful than LR(1)

15. Pick the odd man out

A. Syntax tree
B. Triple
C. Quadruples
D. Indirect triples

16. In bottom up parsing shift always____________

A. Pushes a token and also advances the input
B. Does pop operation
C. Advances the input
D. Pushes a token

17. YACC builds up ______________________parsing table

A. Canonical LR
B. LL
C. SLR
D. LALR
18. __________________ is a way of showing how an input sentence can be recognized
with a grammar.
A. Language
B. Derivation
C. DFA
D. CFG
19. In bottom up parsing reduce operation performs_________________.
A. Only push
B. Only pop
C. Either push or pop
D. Neither push or pop
20. In LR(1) ____________________ means the input is read from left to right.
A. LR
B. L
C. LR(1)
D. R

21. Which of the following is the most general phase structured grammar
A. Context free
B. Right linear
C. Left linear
D. Context sensitive

22. Which of the following is the most powerful parser_________________

A. SLR
B. Operator precedence
C. LALR
D. Canonical LR
23. The input to syntax analysis is__________________.
A. A sequence of lexemes
B. A sequence of tokens
C. A sequence of characters
D. A sequence of patterns
24. The input to _______________________ is a source program.
A. Loader link editor
B. Preprocessor
C. Assembler
D. compiler
25. Which of the following is an LR(1) item
A. [SAa.b,D]
B. S .Aab]
C. [SAa.b]
D. [SAab.]
26. _______________ is the process of replacing a right hand side on the stack with the
matching left hand side.
A. Handle
B. Shift
C. Viable prefix
D. Reduce
 27. In LR(1)___________ means the right most derivation is used to construct the parse
tree

A. R B. LR C.LR(1) D.L

Fill in the blanks:

1. Not a bottom up parser is _________________.

2. BNF stands for_________________.
3. The total number of phases in compiler design is______________.
4. Shift reduce parsers are___________________.
5. A collection of semantic rules is called a______________________.
6. ____________ is an LR(1) item
7. A grammar will be meaningless if _____________________.
8. The minimum value for k in LR(k) is_____________________.
9. In bottom up parsing shift operation performs ___________________.
10. YACC stands for _____________.
11. YACC specification consists of _______________sections.
12. A grammar will be meaningless if __________________________.
13. LR(0) item is____________.
14. YACC builds up ______________________parsing table
15. In bottom up parsing shift operation performs___________________
16. __________________ is a way of showing how an input sentence can be recognized
with a grammar.
17. In bottom up parsing reduce operation performs_________________.
18. In LR (1) ____________________ means the input is read from left to right.
19. ________ is the most general phase structured grammar.
20. ________ is the most powerful parser.
21. The input to syntax analysis is__________________.
22. The input to _______________________ is a source program.
23. _______ is an LR(1) item.
24. _________ is the process of replacing a right hand side on the stack with the matching
left hand side.

25. In LR(1)___________ means the right most derivation is used to construct the parse
tree.

26. The three representatives of LR family ___________,___________,___________

Answers:

1.B 2.C 3.D 4. D 5. A 6. A 7. A 8. B 9. A 10. A 11. B 12. D

13.A 14.A 15. A 16. A 17. A 18. B 19. C 20. B 21. A 22. D 23. B 24. D
25.A 26. A 27. A

1. Predictive parser
2. Backus naus form
3. 6
4. Bottom up parsers
5. Grammar
6. [SAa,b,D]
7. If the left hand side of a production is a single terminal
8. 0
9. Only push
10. Yet Another Compiler Compiler
11. 3
12. If the left hand side of a production is a single terminal
13. [S.Aab]>
14. Canonical LR
15. Pushes a token and also advances the input
16. Derivation
17. Either push or pop
18. L
19. Context free
20. Canonical LR
21. A sequence of tokens
22. compiler
23. [SAa.b,D]
24. Handle
25. R
26. SLR, CLR, LALR