FULL STACK CODING PROGRAM

JOIN OUR PROGRAM AND BUILD YOUR CAREER IN TECH WITH EDULADDER.


NEW JOINEES WILL RECIVE CRYPTO WORTH OF RS 5000/-.


WHITE PAPER APPLY NOW HERE

Real Problems! Real Experts!

An unparalleled, New approach On creative thinking and problem solving.


The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions


You are here:Open notes-->VTU-->COMPAILER-DESIGN-10CS63-VTU-NOTES-UNIT-3

COMPAILER DESIGN 10CS63 VTU NOTES UNIT-3

UNIT III: SYNTAX ANALYSIS-2

Bottom-Up Parsing

 A bottom-up parser creates the parse tree of the given input starting from leaves
towards the root.
 A bottom-up parser tries to find the right-most derivation of the given input in the
reverse order.
S ?? ... ?? ?? (the right-most derivation of ??)
?? (the bottom-up parser finds the right-most derivation in the reverse
order)
 Bottom-up parsing is also known as shift-reduce parsing because its two main
actions are shift and reduce.
 At each shift action, the current symbol in the input string is pushed to a
stack.
 At each reduction step, the symbols at the top of the stack (this symbol
sequence is the right side of a production) will replaced by the non-
terminal at the left side of that production.
 There are also two more actions: accept and error.
Shift-Reduce Parsing
 A shift-reduce parser tries to reduce the given input string into the starting
symbol.
a string  the starting symbol
reduced to
 At each reduction step, a substring of the input matching to the right side of a
production rule is replaced by the non-terminal at the left side of that production
rule.
 If the substring is chosen correctly, the right most derivation of that string is
created in the reverse order.
Rightmost Derivation: S ?? ??
Shift-Reduce Parser finds: ?? ?? ... ?? S
Example
S ?? aABb input string: aaabb
A ?? aA | a aaAbb
B ?? bB | b aAbb ?? reduction
aABb
S

 53
S ?? aABb ?? aAbb ?? aaAbb ?? aaabb
Right Sentential Forms
 How do we know which substring to be replaced at each reduction step
Handle
 Informally, a handle of a string is a substring that matches the right side of a
production rule.
 But not every substring matches the right side of a production rule is
handle
 A handle of a right sentential form ???? (?? ??????) is
a production rule A ?? ?? and a position of ??
where the string ?? may be found and replaced by A to produce
the previous right-sentential form in a rightmost derivation of ??.
S ?? ??A?? ?? ??????
 If the grammar is unambiguous, then every right-sentential form of the grammar
has exactly one handle.
 We will see that ?? is a string of terminals.
Handle Pruning
?? Handle pruning help in finding handle which will be reduced to a non
terminal, that is the process of shift reduce parsing.
A Shift-Reduce Parser

A Stack Implementation of A Shift-Reduce Parser
 There are four possible actions of a shift-parser action:
1. Shift : The next input symbol is shifted onto the top of the stack.
2. Reduce: Replace the handle on the top of the stack by the non-terminal.
3. Accept: Successful completion of parsing.
4. Error: Parser discovers a syntax error, and calls an error recovery routine.
 Initial stack just contains only the end-marker $.
 The end of the input string is marked by the end-marker $.
Consider the following grams and parse the respective strings using shift-
reduce parser.
(1) E ?? E+T | T
T ?? T*F | F
F ?? (E) | id string is id + id * id
Here we follow 2 rules
1. If the incoming operator has more priority than in stack operator then
perform shift.
2. If in stack operator has same or less priority than the priority of incoming
operator then perform reduce.

A Stack Implementation of A Shift-Reduce Parser
Stack Input Action
$ id+id*id$ shift
$id +id*id$ reduce by F ?? id Parse Tree
$F +id*id$ reduce by T ?? F
$T +id*id$ reduce by E ?? T E 8
$E +id*id$ shift
$E+ id*id$ shift E 3 + T 7
$E+id *id$ reduce by F ?? id
$E+F *id$ reduce by T ?? F T 2 T 5 * F 6
$E+T *id$ shift
$E+T* id$ shift F 1 F 4 id
$E+T*id $ reduce by F ?? id
$E+T*F $ reduce by T ?? T*F id id
$E+T $ reduce by E ?? E+T
$E $ accept
(2) S TL;
T int | float
L  L, id | id
String is int id, id; do shift-reduce parser.
(3) S ?(L) |a
L  L,S | S
String (a,(a,a)) do shift-reduce parser.

Shift reduce parser problem
 Take the grammar:
 Sentence --> NounPhrase VerbPhrase NounPhrase --> Art Noun
VerbPhrase --> Verb | Adverb Verb Art --> the | a | ...
Verb --> jumps | sings | ... Noun --> dog | cat | ...
And the input: the dog jumps. Then the bottom up parsing is:
Stack Input Sequence ACTION
$ the dog jumps$ SHIFT word onto stack
$the dog jumps$ REDUCE using grammar rule
$Art dog jumps$ SHIFT..
$Art dog jumps$ REDUCE..
$Art Noun jumps$ REDUCE
$NounPhrase jumps$ SHIFT
$NounPhrase jumps $ REDUCE
$NounPhrase Verb $ REDUCE
$NounPhrase VerbPhrase $ REDUCE
$Sentence $ SUCCESS
Shift-Reduce Parsers
 There are two main categories of shift-reduce parsers
1. Operator-Precedence Parser
 Simple, but only a small class of grammars.
 LR-Parsers


 Covers wide range of grammars.
 SLR  simple LR parser
 LR  most general LR parser
 LALR  intermediate LR parser (lookhead LR parser)
SLR, LR and LALR work same, only their parsing tables are different
LR Parsers
 LR-Parsers
 covers wide range of grammars.
 SLR  simple LR parser
 LR  most general LR parser(canonical LR)
 LALR  intermediate LR parser (look-head LR parser)
 SLR, LR and LALR work same (they used the same algorithm), only their
parsing tables are different.
LR Parsing Algorithm
Sm
Xm
Sm-1
Xm-1
.
.
S1
X1
S0
a1 ... ai ... an $
Action Table
terminals and $
s
t four different
s n o i t c a at
es
Goto Table
non-terminal
s
t each item is
r e b m u n e t a t s a at
es
LR Parsing Algorithm
stack
input
output
A Configuration of LR Parsing Algorithm
 A configuration of a LR parsing is:
( So X1 S1 ... Xm Sm, ai ai+1 ... an $ )
Stack Rest of Input
 Sm and ai decides the parser action by consulting the parsing action
table. (Initial Stack contains just So )
 A configuration of a LR parsing represents the right sentential form:
X1 ... Xm ai ai+1 ... an $

Actions of A LR-Parser
1. shift s -- shifts the next input symbol and the state s onto the stack
( So X1 S1 ... Xm Sm, ai ai+1 ... an $ ) ?( So X1 S1 ... Xm Sm ai s, ai+1 ... an $ )
2. reduce A???? (or rn where n is a production number)
 pop 2|??| (=r) items from the stack;
 then push A and s where s=goto[sm-r,A]
( So X1 S1 ... Xm Sm, ai ai+1 ... an $ ) ?( So X1 S1 ... Xm-r Sm-r A s, ai ... an $ )
 Output is the reducing production reduce A????
3. Accept  Parsing successfully completed
4. Error -- Parser detected an error (an empty entry in the action table)
Reduce Action
 pop 2|??| (=r) items from the stack; let us assume that ?? = Y1Y2...Yr
 then push A and s where s=goto[sm-r,A]
( So X1 S1 ... Xm-r Sm-r Y1 Sm-r ...Yr Sm, ai ai+1 ... an $ )
 ( So X1 S1 ... Xm-r Sm-r A s, ai ... an $ )
 In fact, Y1Y2...Yr is a handle.
X1 ... Xm-r A ai ... an $ ?? X1 ... Xm Y1...Yr ai ai+1 ... an $
Constructing SLR Parsing Tables  LR(0) Item
 An LR(0) item of a grammar G is a production of G a dot at the some position of
the right side.
 Ex: A ?? aBb Possible LR(0) Items: A ?? .aBb
(four different possibility) A ?? a.Bb
A ?? aB.b
A ?? aBb.
 Sets of LR(0) items will be the states of action and goto table of the SLR parser.
 A collection of sets of LR(0) items (the canonical LR(0) collection) is the basis
for constructing SLR parsers.
 Augmented Grammar:
G is G with a new production rule S??S where S is the new starting symbol.
The Closure Operation
 If I is a set of LR(0) items for a grammar G, then closure(I) is the set of LR(0)
items constructed from I by the two rules:
1. Initially, every LR(0) item in I is added to closure(I).

 60
2. If A ?? ??.B?? is in closure(I) and B???? is a production rule of G; then
B??.?? will be in the closure(I). We will apply this rule until no more new
LR(0) items can be added to closure(I).
The Closure Operation -- Example
E ?? E closure({E ?? .E}) =
E ?? E+T { E ?? .E kernel items
E ?? T E ?? .E+T
T ?? T*F E ?? .T
T ?? F T ?? .T*F
F ?? (E) T ?? .F
F ?? id F ?? .(E)
F ?? .id }
Goto Operation
 If I is a set of LR(0) items and X is a grammar symbol (terminal or non-terminal),
then goto(I,X) is defined as follows:
 If A ?? ??.X?? in I then every item in closure({A ?? ??X.??}) will be
in goto(I,X).
Example:
I ={ E ?? .E, E ?? .E+T, E ?? .T,
T ?? .T*F, T ?? .F,
F ?? .(E), F ?? .id }
goto(I,E) = { E ?? E., E ?? E.+T }
goto(I,T) = { E ?? T., T ?? T.*F }
goto(I,F) = {T ?? F. }
goto(I,() = { F ?? (.E), E ?? .E+T, E ?? .T, T ?? .T*F, T ?? .F,
F ?? .(E), F ?? .id }
goto(I,id) = { F ?? id. }
Construction of The Canonical LR(0) Collection
 To create the SLR parsing tables for a grammar G, we will create the canonical
LR(0) collection of the grammar G.
 Algorithm:
C is { closure({S??.S}) }
repeat the followings until no more set of LR(0) items can be added to C.
for each I in C and each grammar symbol X
if goto(I,X) is not empty and not in C
add goto(I,X) to C
 goto function is a DFA on the sets in C.

 61
The Canonical LR(0) Collection  Example
I0: E ?? .E I1: E ?? E. I6: E ?? E+.T I9: E ?? E+T.
E ?? .E+T E ?? E.+T T ?? .T*F T ?? T.*F
E ?? .T T ?? .F
T ?? .T*F I2: E ?? T. F ?? .(E) I10: T ?? T*F.
T ?? .F T ?? T.*F F ?? .id
F ?? .(E)
F ?? .id I3: T ?? F. I7: T ?? T*.F I11: F ?? (E).
F ?? .(E)
I4: F ?? (.E) F ?? .id
E ?? .E+T
E ?? .T I8: F ?? (E.)
T ?? .T*F E ?? E.+T
T ?? .F
F ?? .(E)
F ?? .id
I5: F ?? id.
Transition Diagram (DFA) of Goto Function
I0 I1
I2
I3
I4
I5
I6
I7
I8
to I2
to I3
to I4
I9
to I3
to I4
to I5
I10
to I4
to I5
I11
to I6
to I7
id
(
F
*
E
E
+
T
T
T
)
F
F
F
(
id id
(
*
(
id

Constructing SLR Parsing Table
(of an augumented grammar G)
1. Construct the canonical collection of sets of LR(0) items for G.
C??{I0,...,In}
. 2 s w o l l o f s a e l b a t n o i t c a g n i s r a p e h t e t a e r C
 If a is a terminal, A????.a?? in Ii and goto(Ii,a)=Ij then action[i,a] is shift j.
 If A????. is in Ii , then action[i,a] is reduce A???? for all a in FOLLOW(A)
where A??S.
 If S??S. is in Ii , then action[i,$] is accept.
 If any conflicting actions generated by these rules, the grammar is not SLR(1).
. 3 e l b a t o t o g g n i s r a p e h t e t a e r C
 for all non-terminals A, if goto(Ii,A)=Ij then goto[i,A]=j
4. All entries not defined by (2) and (3) are errors.
5. Initial state of the parser contains S??.S
(SLR) Parsing Tables for Expression Grammar
state id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
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
Action Table Goto Table
1) E ?? E+T
2) E ??T
3) T ??T*F
4) T ??F
5) F ?? (E)
6) F ?? id
Actions of A (S)LR-Parser  Example
stack input action goto parsing
$0 id*id+id$ [0,id]=s5 shift 5
$0id5 *id+id$ [5,*]=r6 [0,F]=3 reduce by F??id (pop 2|id| no. of
symbols from stack and push F to the stack)
$0F3 *id+id$ [3,*]=r4 [0,T]=2 reduce by T??F (pop 2|F| no. of
symbols from stack and push T onto the stack)
$0T2 *id+id$ [2,*]=s7 shift 7
$0T2*7 id+id$ [7,id]=s5 shift 5
$0T2*7id5 +id$ [5,+]=r6 [7,F]=10 reduce by F??id(pop 2|id| no. of
symbols from stack and push F onto the stack)
$0T2*7F10 +id$ [10,+]=r3 [0,T]=2 reduce by T??T*F(pop 2 |T*F| no. of
symbols from stack and push F on the stack)
$0T2 +id$ [2,+]=r2 [0,E]=1 reduce by E??T (pop 2|T| no. of
symbols from stack and push E onto the stack)
$0E1 +id$ [1,+]=s6 shift 6
$0E1+6 id$ [6,id]=s5 shift 5
$0E1+6id5 $ [5,$]=r6 [6,F]=3 reduce by F??id (pop 2|id| no. of
symbols from stack and push F onto the stack)
$0E1+6F3 $ [3,$]=r4 [6,F]=3 reduce by T??F (pop 2|F| no. of
symbols from stack and push T onto the stack)
$0E1+6T9 $ [9,$]=r1 [0,E]=1 reduce by E??E+T (pop 2
|E+T| no. of symbols from stack and push F on the stack)
$0E1 $ accept
SLR(1) Grammar
 An LR parser using SLR(1) parsing tables for a grammar G is called as the
SLR(1) parser for G.
 If a grammar G has an SLR(1) parsing table, it is called SLR(1) grammar (or SLR
grammar in short).
 Every SLR grammar is unambiguous, but every unambiguous grammar is not a
SLR grammar.
shift/reduce and reduce/reduce conflicts
 If a state does not know whether it will make a shift operation or reduction for a
terminal, we say that there is a shift/reduce conflict.
 If a state does not know whether it will make a reduction operation using the
production rule i or j for a terminal, we say that there is a reduce/reduce conflict.
 If the SLR parsing table of a grammar G has a conflict, we say that that grammar
is not SLR grammar.
Problems on SLR
1. S  SS+ | SS* | a with the string aa+a* 6. S  +SS | *SS | a with the
string +*aaa
2. S  (L) | a, L  L,S | S 7. Show that following grammar is SLR(1)
but not LL(1)
S SA | A
A  a
3. S aSb | ab 8. X Xb |a parse the string abb
4. S aSbS | bSaS | ?? 9. Given the grammar A  (A) |a string ((a))
5. S ?? E#
E ?? E-T
E ?? T
T ?? F T
T ?? F
F ?? (E)
F ?? i
Construct parsing table for this. In this table there are 2 actions in one entry of the
table which is why It is not a SLR(1) grammar.
Another example for not SLR(1) grammar:
Conflict Example2
S ?? AaAb I0: S ??.S
S ?? BbBa S ?? .AaAb
A ?? ?? S ?? .BbBa
B ?? ?? A ?? .
B ?? .
Problem
FOLLOW(A)={a,b}
FOLLOW(B)={a,b}
a reduce by A ???? b reduce by A ????
reduce by B ???? reduce by B ????
reduce/reduce conflict reduce/reduce conflict
Problems : show that following grammars are not SLR(1) by constructing
parsing table.
1. Show that S  S(S)S | ?? not SLR(1)
2. Show that S  AaAb | BbBa
A ???

B ??? is not SLR(1) but is LL(1)

Editors




You might like this video:Watch more here

Watch more videos from this user Here

Learn how to upload a video over here