3-Syntax Analyzer PDF

UNIT - III
Syntax Analyzer
Santanu Halder Compiler Design

1
Role of Parser

2
Role of Syntax Analyzer
if (b == 0) a = b;
Lexical Analysis or Scanner
if ( b == 0 ) a = b ;
Syntax Analysis or Parsing
if
abstract syntax tree
== = or parse tree
b 0 a b
3
Grammar
Definition:
Generally a grammar is represented as 4-tuples –
G = <V, T, P, S>
Where V = finite set of variables (or non-terminals)
T = finite set of terminal symbols
P = finite set of productions
S = Starting symbol
Example:
G = ({S}, {a, b}, {S→aSb, S→ab}, S)
What language does this grammar accept?

4
Grammar..
Definition:
Generally a grammar is represented as 4-tuples –
G = <V, T, P, S>
Where V = finite set of variables (or non-terminals)
T = finite set of terminal symbols
P = finite set of productions
S = Starting symbol
Example:
G = ({S}, {a, b}, {S→aSb, S→ab}, S)
What language does this grammar accept?
L(G) = {anbn | n≥1}

5
Chomsky Classification
Type 0 or Unrestricted grammar:
A grammar G = (V, T, P, S) is said to be unrestricted if all the
production rules are of the form –
A→α where A is in (VUT)+ and α is in (VUT)*

6
Chomsky Classification..
Example:
S→S1B
S1→aS1B
bB→bbbB
aS1b→aa
B→ϵ

7
Example:
S→S1B
S1→aS1B
bB→bbbB
aS1b→aa
B→ϵ
L(G) = {an+1bn+k | n≥1, k=-1,1,3….}

8
Type 1 or Context-Sensitive grammar:
A grammar G = (V, T, P, S) is said to be context-sensitive
grammar if all the production rules are of the form –
A→α where A, α is in (VUT)+ and |A| ≤ |α|

9
Example:
S→abc | aAbc
Ab→bA
Ac→Bbcc
bB→Bb
aB→aa | aaA

10
Example:
S→abc | aAbc
Ab→bA
Ac→Bbcc
bB→Bb
aB→aa | aaA
L(G) = {anbncn | n≥1}

11
Type 2 or Context-Free grammar:
A grammar G = (V, T, P, S) is said to be context-free grammar
if all the production rules are of the form –
A→α where A is in V and α is in (VUT)*

12
Example:
S→aSa
S→bSb
S→ϵ

13
Example:
S→aSa
S→bSb
S→ϵ
L(G) = {WWR | W is in {a, b}*}

14
Type 3 or Regular Grammar:
A grammar G = (V, T, P, S) is said to be right linear grammar
A→xB or A→x where A, B is in V and x is in T*
A grammar G = (V, T, P, S) is said to be left linear grammar if

all the production rules are of the form –
A→Bx or A→x where A, B is in V and x is in T*
A regular grammar is one that is either left linear or right

linear.

15
Example:
Right linear
S→abS | a L(G) = {(ab)*a}

16
Example:
Right linear
Left Linear
S→S1ab
S1→S1ab | S2 L(G) = {aab(ab)*}
S2→a

17
Example:
Right linear
Left Linear
S→S1ab
S1→S1ab | S2 L(G) = {aab(ab)*}
S2→a
Linear grammar
S→A
A→aB | ϵ L(G) = {anbn | n ≥ 0}
B→Ab

18
Context Free Grammar
1. Generate a CFG for L(G) = {anbn | n≥1}

19
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aSb, S→ab}

20
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aSb, S→ab}
2. Construct a CFG to generate the set of palindromes

over alphabet {a, b}.

21
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aSb, S→ab}
2. Construct a CFG to generate the set of palindromes

over alphabet {a, b}.
G = (V, T, P, S)
V = {S}, T = {a, b},
And for even palindrome –
P = {S→aSa, S→bSb, S→ ε}
And for odd palindrome –
P = {S→aSa, S→bSb, S→a, S→b}

22
3. Design a CFG for a given language L(G) = {aibi | i≥0}.

23
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aSb, S→ ε}
4. Design a CFG for L(G) = {aibicjdj | i,j≥0}.

24
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aSb, S→ ε}
4. Design a CFG for L(G) = {aibicjdj | i,j≥0}.

Let, L1 = {aibi | i ≥ 0} and L2 = {cjdj | j ≥ 0}
Hence L(G) = L1·L2
L1 can be expressed as {A→aAb | ε}
L2 can be expressed as {B→cBd | ε}
Finally, P = {S→AB, A→aAb | ε, B→cBd | ε}

25
5. Generate a CFG for L(G) = {0i1j0k | j>i+k and i,k≥0}.

26
L(G) = 0i1j0k for i, k ≥ 0 and j > i+k
= 0i1i1m1k0k for m > 0

27
This can be rewritten as –
L1 = {0i1i | i ≥ 0}
L2 = {1m | m >0}
L3 = {1k0k| k ≥ 0}
And hence –
L(G) = L1·L2·L3

28
This can be rewritten as –
L1 = {0i1i | i ≥ 0}
L2 = {1m | m >0}
L3 = {1k0k| k ≥ 0}
And hence –
L(G) = L1·L2·L3
L1 can be expressed as {A→0A1 | ε}
L2 can be expressed as {B→1B | 1}
L3 can be expressed as {C→1C0 | ε}
Finally, P = {S→ABC, A→0A1| ε, B→1B|1, C→1C0 | ε}

29
6. Design a CFG for L(G) = {e5aibjcjdi | i,j>0}.

30
G = (V, T, P, S)
V = {S, S1, S2, S3}, T = {a, b, c, d},
P = { S→e5aS1d,
S1→ aS2d | bc,
S2→aS2d | bS3c | bc,
S3→bS3c | bc}

31
G = (V, T, P, S)
V = {S, S1, S2, S3}, T = {a, b, c, d},
P = { S→e5aS1d,
S1→ aS2d | bc,
S3→bS3c | bc}
7. Design a CFG for L(G) = {WWR | W is a binary string}.

32
G = (V, T, P, S)
V = {S, S1, S2, S3}, T = {a, b, c, d},
P = { S→e5aS1d,
S1→ aS2d | bc,
S3→bS3c | bc}
7. Design a CFG for L(G) = {WWR | W is a binary string}.

G = (V, T, P, S)
V = {S}, T = {0, 1}, P = {S→0S0 | 1S1 | ε}

33
8. Design a CFG for L(G) = (a+b)*.

34
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aS | Sb | a | b | ε}

35
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aS | Sb | a | b | ε}
9. Design a CFG for L(G) = {anbm | n≠m}.

36
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aS | Sb | a | b | ε}

Case 1: n < m
L = {anbnbi | i > 0}
L1 = {anbn}
L2 = {bi | i > 0}

37
G = (V, T, P, S)
V = {S}, T = {a, b}, P = {S→aS | Sb | a | b | ε}

Case 1: n < m
L = {anbnbi | i > 0}
L1 = {anbn}
L2 = {bi | i > 0}
Hence,
L1 can be expressed as : {A→aAb | ε}
L2 can be expressed as : {B→bB | b}
So, P1 = {S1→AB, A→aAb | ε, B→bB | b}

38
Case 2: n > m
L = {aianbn | i > 0}
L1 = {ai | i > 0}
L2 = {anbn | i > 0}

39
Case 2: n > m
L1 = {ai | i > 0}
L2 = {anbn | i > 0}
Hence,
L1 can be expressed as : {C→aC | a}
L2 can be expressed as : {D→aDb | ε}
So, P2 = {S2→CD, C→aC | a, D→aDb | ε }

40
Case 2: n > m
L1 = {ai | i > 0}
L2 = {anbn | i > 0}
Hence,
L1 can be expressed as : {C→aC | a}
L2 can be expressed as : {D→aDb | ε}
So, P2 = {S2→CD, C→aC | a, D→aDb | ε }
Finally –
P = { S→S1 | S2,
S1→AB, A→aAb | ε, B→bB | b
S2→CD, C→aC | a, D→aDb | ε }

41
Leftmost Derivation
A derivation is said to be leftmost if in each step of the
derivation, the leftmost variable in the sentential form is
replaced.

42
Leftmost Derivation..
replaced.
Example: Consider the grammar with productions –
S→aAB A→bBb B→A | ϵ
Leftmost derivation for the string abbbb is –

43
replaced.
S => aAB S→aAB

44
replaced.
S => aAB S→aAB
=> abBbB A→bBb

45
replaced.
S => aAB S→aAB
=> abBbB A→bBb
=> abAbB B→A

46
replaced.
S => aAB S→aAB
=> abBbB A→bBb
=> abAbB B→A
=> abbBbbB A→bBb

47
replaced.
S => aAB S→aAB
=> abBbB A→bBb
=> abAbB B→A
=> abbBbbB A→bBb
=> abbbbB B→ ϵ

48
replaced.
S => aAB S→aAB
=> abBbB A→bBb
=> abAbB B→A
=> abbBbbB A→bBb
=> abbbbB B→ ϵ
=> abbbb B→ ϵ

49
Rightmost Derivation
A derivation is said to be rightmost if in each step of the
derivation, the rightmost variable in the sentential form is
replaced.

50
Rightmost Derivation..
replaced.
Rightmost derivation for the string abbbb is –

51
replaced.
S => aAB S→aAB

52
replaced.
S => aAB S→aAB
=> aAA B→A

53
replaced.
S => aAB S→aAB
=> aAA B→A
=> aAbBb A→bBb

54
replaced.
S => aAB S→aAB
=> aAA B→A
=> aAbBb A→bBb
=> aAbb B→ ϵ

55
replaced.
S => aAB S→aAB
=> aAA B→A
=> aAbBb A→bBb
=> aAbb B→ ϵ
=> abBbbb A→bBb

56
replaced.
S => aAB S→aAB
=> aAA B→A
=> aAbBb A→bBb
=> aAbb B→ ϵ
=> abBbbb A→bBb
=> abbbb B→ ϵ

57
Derivation Tree
Let G=(V, T, P, S) be a CFG. An ordered tree is a derivation
tree for G iff it has the following properties:
1. The root is labeled S.
2. Every leaf has a label from T U {ϵ}.
3. Every interior vertex has a label from V.
4. If a vertex has label A (which is in V), and its children
are labeled from left to right as a1, a2, …, an, then P
must contain a production of the form –
A→a1a2…an
5. A leaf labeled ϵ has no siblings.

58
Derivation Tree..
S
a A B
b B b ϵ

59
Simplification of CFG
Steps to simplify a grammar –
Step 1: Eliminate null production.
Step 2: Eliminate unit production.
Step 3: Eliminate production that contains useless variables.
Useless variables are of two types –

1. Variables which are not deriving terminal string.
2. Variables that can’t be reached from start symbol.

60
Simplification of CFG..
Elimination of null production:
Let G={V, T, P, S} and G′={V, T, P′, S}
Step 1: Say w1={A ϵ V | A→ ɛ is in P}
wi+1=wi U {A ϵ V | there exists a production
A→ x with x ϵ wi*}
Stop when wi = wi+1 and wi is the set of all null able variables.

61
Let G={V, T, P, S} and G′={V, T, P′, S}
Step 1: Say w1={A ϵ V | A→ ɛ is in P}
A→ x with x ϵ wi*}
Stop when wi = wi+1 and wi is the set of all null able variables.
Step 2:
a) Any productions, whose RHS does not have any nullable
variable, is included in P′.
b) If A→X1X2…Xk is in P, the productions of the form
A→α1α2…αk are included in P′, where αi = Xi if Xi is not in
wi. αi = Xi or ɛ if xi ϵ wi and α1α2…αk ≠ ɛ.

62
Example:
G = (V, T, P, S) V = {S, A, B, C, D} T = {a, b, d}
P = {S→ABaC, A→BC, B→b | ɛ, C→D | ɛ, D→d}

63
Example:
Solution:
w1 = {B, C} Since B→ɛ and C→ɛ

64
Example:
Solution:
w2 = w1 U {A} Since A→BC
= {A, B, C}

65
Example:
Solution:
w2 = w1 U {A} Since A→BC
= {A, B, C}
w3 = w2 U {Φ} Since no more such productions
= {A, B, C}

66
Example:
Solution:
Hence –
P′ = { S→ABaC|BaC|AaC|ABa|aC|Aa|Ba|a
A→BC|C|B
B→b
C→D
D→d}

67
Elimination of Unit Production:
Any production of a CFG of the form A→B where A, B ϵ V is
called an unit production.

68
Any production of a CFG of the form A→B where A, B ϵ V is
called an unit production.
For the following grammar,
S→Aa |B B→A|bb A→a|bc|B
The unit productions are:

S→B B→A A→B
The dependency graph for the unit productions is –
S A B

69
S A B
Hence, P′ contains:
Original non-unit productions:
S→Aa
A→a | bc
B→bb

70
S A B
S→Aa
A→a | bc
B→bb
The new rules:
S→a | bc | bb
A→bb
B→a | bc

71
S A B
S→Aa
A→a | bc
B→bb
The new rules: Altogether,
S→a | bc | bb S→Aa | a | bc | bb
A→bb A→a | bc | bb
B→a | bc B→bb | a | bc

72
Elimination of variables not deriving terminal string:
Let G={V, T, P, S} and G′={V′, T, P′, S}
Step 1: Say w1={A ϵ V | A→ x is in P where xϵT*}
A→ x with x ϵ {T U wi}*}
Stop when wi = wi+1 and then V′ = {wi}.
Step 2:
P′={A→x | A, x ϵ (V′UT)*}

73
Example:
G = (V, T, P, S) V = {S, A, B, C} T = {a, b, c} and
P = { S→AB, A→a, B→b, B→C, E→c }

74
Example:
P = { S→AB, A→a, B→b, B→C, E→c }
w1 = {A, B, E} Since A→a, B→b, E→c

75
Example:
P = { S→AB, A→a, B→b, B→C, E→c }
w2 = w1 U {S} Since S→AB
= {S, A, B, E}

76
Example:
P = { S→AB, A→a, B→b, B→C, E→c }
= {S, A, B, E}
w3 = w2 U {Φ} Since no more such productions.
= {S, A, B, E}

77
Example:
P = { S→AB, A→a, B→b, B→C, E→c }
= {S, A, B, E}
w3 = w2 U {Φ} Since no more such productions.
= {S, A, B, E}
Hence, V′ = {S, A, B, E}
So, P′ = { S→AB, A→a, B→b, E→c }

78
Elimination of variables not reachable from start symbol:
Let G={V, T, P, S} and G′={V′, T, P′, S}
Step 1: Draw dependency graph for the variables. A variable
is useful only if there is a path from the vertex labelled S.
V′ = {useful variables}
Step 2: P′={A→x | A, x ϵ (V′UT)*}

79
Example:
G = (V, T, P, S) V = {S, A, B} T={a}
P = { S→aS | A, A→a, B→aa }

80
Example:
G = (V, T, P, S) V = {S, A, B} T={a}
P = { S→aS | A, A→a, B→aa }
The dependency graph for V is:
S A B

81
Example:
G = (V, T, P, S) V = {S, A, B} T={a}
P = { S→aS | A, A→a, B→aa }
The dependency graph for V is:
S A B
Hence V′ = {S, A}
So, P′ = {{ S→aS | A, A→a}

82
Normal Forms for CFG
 In a context free grammar, then right hand side of a
production rule can be any string of terminals and variables.
When the production rules in a grammar satisfy certain
restrictions, then the grammar is said to be in a normal form.
 The normal forms for CFG are of two types:

1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)

83
Chomsky Normal Form (CNF)
Definition:
A context free grammar is in CNF, if all the production rules
are of the form:
A → BC
or, A → a
Where A, B, C ϵ V and a ϵ T.
Example:
S → AS | a
A → SA | b

84
Greibach Normal Form (GNF)
Definition:
A context free grammar is said to be in GNF, if all the
production rules are of the form:
A → ax
Where a ϵ T and x ϵ V*.
Example:
S → aAB | bBB | bB
A → aA | bB | b
B→b

85
S - Grammar
A context free grammar G = (V, T, P, S) is said to be a simple
grammar or S-Grammar if all its productions are of the form –
A→aX
Where A is in V, a is in T and X is in V*, and any pair (A, a)
occurs at most once in P.

86
S - Grammar..
A→aX
Example:
S→aS S→aS
S→bSS S→bSS
S→c S→aSS
S→c

87
S - Grammar..
A→aX
Example:
S→aS S→aS
S→bSS S→bSS
S→c S→aSS
S→c

88
Ambiguous Grammar
A context free grammar G = (V, T, P, S) is said to be
ambiguous if there exists some w (which is in L(G)) that has
at least two distinct derivation trees.

89
Ambiguous Grammar..
Example:
E→E+E | E*E | id
id + id + id

90
Ambiguous Grammar..
Example:
E→E+E | E*E | id
id + id + id
E + E
id E + E
id id

91
Ambiguous Grammar..
Example:
E→E+E | E*E | id
id + id + id
E E
E + E E + E
id E + E E + E id
id id id id

92
Ambiguous Grammar..
Example:
E→E+E | E*E | id
id + id * id

93
Ambiguous Grammar..
Example:
E→E+E | E*E | id
id + id * id
E + E
id E * E
id id

94
Ambiguous Grammar..
Example:
E→E+E | E*E | id
id + id * id
E E
E + E E * E
id E * E E + E id
id id id id

95
Ambiguous Grammar..
Solution: Associate precedence rules with the operators.
E→E+E | E*E | id
Rewrite the production rules as follows to make it

unambiguous –
E→E+T | T
T→T*F | F
F→id

96
Ambiguous Grammar..
E E
E + T E + T
E + T F T T * F
T F id F F id
F id id id
id

97
Ambiguous Grammar..
Example: Rewrite the following production rules to make the
grammar unambiguous.
bExp → bExp or bExp
→ bExp and bExp
→ not bExp
→ True | False

98
Ambiguous Grammar..
bExp → bExp or bExp
→ bExp and bExp
→ not bExp
→ True | False
Solution:
E → E or T | T
T → F and G | G
G → not H | True | False

99
Ambiguous Grammar..
stmt → if expr then stmt
stmt → if expr then stmt else stmt
stmt → other

100
Ambiguous Grammar..
stmt → if expr then stmt
stmt → if expr then stmt else stmt
stmt → other
Solution:
Idea: A statement appearing between a then and an else
must be matched
stmt → match_stmt | open_stmt
match_stmt → if expr then match_stmt else match_stmt
match_stmt → other
open_stmt → if expr then stmt
open_stmt → if expr then match_stmt else open_stmt

101
Right Recursive Grammar
A grammar G is said to be right recursive if it contains the
following type of production rules:
A→αA | β

102
Left Recursive Grammar
A grammar G is said to be left recursive if it contains the
following type of production rules:
A→Aα | β
In other words, a grammar G is left recursive if it has a non-

terminal A such that there is a derivation A+=> Aα for some
string α.
Top down parsing methods can not accept left recursive

grammar.

103
Elimination of Left Recursion
Replace the following production rules:
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ

104
Elimination of Left Recursion..
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
E→E+T | T

105
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
E→E+T | T
After elimination of left recursion –
E → TE’
E’→ +TE’ | ϵ

106
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
S→S0S1S | 01

107
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
S→S0S1S | 01
After elimination of left recursion –
S → 01S’
S’→ 0S1SS’ | ϵ

108
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
S → (L) | x
L → L,S | S

109
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
S → (L) | x not left recursive
L → L,S | S left recursive

110
A→Aα | β
By
A → βA’
A’→ αA’ | ϵ
Example:
S → (L) | x not left recursive
L → L,S | S left recursive
So, after elimination of left recursion from production rule 2 –
L → SL’
L’→ ,SL’ | ϵ

111
Left Factoring
 Left factoring is a grammar transformation that is useful for
producing a grammar suitable for predictive or top-down
parsing.
 When the choice between two alternative A-productions is
not clear, one may be able to rewrite the productions to defer
the decision until enough of the input, has been seen that
he/she can make the right choice.
 For example –
A → αβ1 | αβ2 | … | αβn
 As a solution, rewrite the production rules as –
A → αA’
A’→ β1 | β2 … | βn

112
Left Factoring..
A → aBcDE A → aBcDE
A → aBdEC B → aBdEC
B→b B→b
C→c C→c
D→d D→d
E→e E→e

113
Left Factoring..
B→b B→b
C→c C→c
D→d D→d
E→e E→e
Non-deterministic grammar Deterministic Grammar

114
Left Factoring..
B→b B→b
C→c C→c
D→d D→d
E→e E→e
Non-deterministic grammar Deterministic Grammar

Apply left factoring Does not require left factoring

115
Left Factoring..
Example:
S → iEtS | iEtSeS | a
E→b

116
Left Factoring..
Example:
S → iEtS | iEtSeS | a
E→b
Solution:
S → iEtSS’ | a
S’→ ϵ | eS
E→b

117
Left Factoring..
Example:
S → aSSbS | aSaSb | abb | b

118
Left Factoring..
Example:
Solution:
Step 1:
S → aS’ | b
S’→ SSbS | SaSb | bb

119
Left Factoring..
Example:
Solution:
Step 1:
S → aS’ | b
Step 2:
S’→ SS’’ | bb
S’’→ SbS | aSb

120
Left Factoring..
Example:
Solution:
Step 1:
S → aS’ | b
Step 2:
S’→ SS’’ | bb
Altogether:
S → aS’ | b
S’→ SS’’ | bb

121
Closure Properties of CFL and RL
1. If L1 be a context free language and L2 be a regular
language, then L1∩L2 is a context free language.
2. Regular sets are closed under transpose.
3. Regular sets are closed under complementation.
4. Regular sets are closed under intersection.
5. Context free languages are closed under union.
6. Context free languages are closed under concatenation.
7. Context free languages are closed under star closure.
8. Context free languages are not closed under intersection.
9. Context free languages are not closed under
complementation.

122
Type of Parser
Parsers
Top Down Bottom Up

Parsers Parsers
TDP with full TDP without

Backtracking Backtracking
Brute Force Recursive Non Recursive

Method Descent Descent (LL(1))

123
Type of Parser..
Parsers
Top Down Bottom Up

Parsers Parsers
Operator LR Parser
Precedence
Parser
LR(0) SLR(1) LALR(1) CLR(1)

124
Difference between TDP and BUP
S → aABe
A → Abc | b w = abbcde
B→d

125
S → aABe
B→d
Top down parser
S
a A B e

126
S → aABe
B→d
Top down parser
S
a A B e
A b c

127
S → aABe
B→d
Top down parser
S
a A B e
A b c

128
S → aABe
B→d
Top down parser
S
a A B e
A b c d

129
S → aABe
B→d
Top down parser Bottom up parser
S
a A B e
A b c d
b a b b c d e

130
S → aABe
B→d
S
a A B e
A b c d A
b a b b c d e

131
S → aABe
B→d
S
a A B e A
A b c d A
b a b b c d e

132
S → aABe
B→d
S
a A B e A B
A b c d A
b a b b c d e

133
S → aABe
B→d
S S
a A B e A B
A b c d A
b a b b c d e

134
S → aABe
B→d
(Left most derivation) (Right most derivation)

135
S → aABe
B→d
S => aABe S => aABe

136
S → aABe
B→d
S => aABe S => aABe
=> aAbcBe => aAde

137
S → aABe
B→d
S => aABe S => aABe
=> aAbcBe => aAde
=> abbcBe => aAbcde

138
S → aABe
B→d
(Left most derivation) (Reverse of Right most derivation)
S => aABe S => aABe
=> aAbcBe => aAde
=> abbcBe => aAbcde
=> abbcde => abbcde

139
S → aABe
B→d
(Left most derivation) (Reverse of Right most derivation)
S => aABe S => aABe
=> aAbcBe => aAde
=> abbcBe => aAbcde
=> abbcde => abbcde

140
Recursive Descent Parser
 Consists of a set of procedures, one for each non-
terminal.
 Execution begins with the procedure for start symbol.
 Recursive descent parsers cant be used for left-recursive

grammars.

141
Recursive Descent Parser..
E → iE’
E’→ +iE’ | ε

142
E → iE’
E’→ +iE’ | ε
E()
{
if(l == 'i')
{
match('i');
E’();
}
}

143
E → iE’
E’→ +iE’ | ε
E() E’()
{ {
if(l == 'i') if(l == '+')
{ {
match('i'); match(+);
E’(); match(i);
} E’();
} }
else
return();
}

144
E → iE’ match(char t)
E’→ +iE’ | ε {
E() E’() if(l == t)
{ { l = getchar();
if(l == 'i') if(l == '+') else
{ { printf(“error”);
match('i'); match('+'); }
E’(); match('i');
} E’();
} }
else
return();
}

145
E → iE’ match(char t)
E’→ +iE’ | ε {
E() E’() if(l == t)
{ { l = getchar();
if(l == 'i') if(l == '+') else
{ { printf(“error”);
match('i'); match('+'); }
E’(); match('i'); main()
} E’(); {
} } E();
else if(l=='$')
return(); printf(“accept”);
} }

146
FIRST and FOLLOW
To compute FIRST(X) for all symbols X in grammar G, apply
following rules until no more terminals or ɛ can be added to
any FIRST set:
1. If X is a terminal, then FIRST(X) = {X}.
2. If X is a non-terminal and X→Y1Y2…Yk is a production for

some k≥1, then place a in FIRST(X) if for some i, a is in
FIRST(Yi) and ɛ is in all of FIRST(Y1),…,FIRST(Yi-1). If ɛ is in
FIRST(Yj) for j=1…k then add ɛ to FIRST(X).
3.If X→ ɛ is a production, then add ɛ to FIRST(X).

147
FIRST and FOLLOW..
To compute FOLLOW(A) for all non-terminals A, apply the
following rules until nothing can be added to any FOLLOW
set.
1. Place $ in FOLLOW(S) , where S is the start symbol, and $
is the input right end marker .
2. If there is a production A → αBβ, then everything in
FIRST(β) except ɛ is in FOLLOW(B).
3. If there is a production A → αB, or a production A →αBβ,
where FIRST(β) contains ɛ, then everything in FOLLOW(A) is
in FOLLOW(B) .

148
FIRST and FOLLOW..
Example: Find FIRST and FOLLOW for the following
grammar.
S→ABCDE
A→a | ɛ
B→b | ɛ
C→c
D→d | ɛ
E→e | ɛ

149
FIRST and FOLLOW..
Solution:
FIRST FOLLOW
S→ABCDE S {a, b, c} {$}
A→a | ɛ A {a, ɛ} {b, c}
B→b | ɛ B {b, ɛ} {c}
C→c C {c} {d, e, $}
D→d | ɛ D {d, ɛ} {e, $}
E→e | ɛ E {e, ɛ} {$}

150
FIRST and FOLLOW..
grammar.
S→Bb | Cd
B→aB | ɛ
C→cC | ɛ

151
FIRST and FOLLOW..
Solution:
FIRST
S→Bb | Cd S {a, b, c, d}
B→aB | ɛ B {a, ɛ}
C→cC | ɛ C {c, ɛ}

152
FIRST and FOLLOW..
Solution:
FIRST FOLLOW
S→Bb | Cd S {a, b, c, d} {$}
B→aB | ɛ B {a, ɛ} {b}
C→cC | ɛ C {c, ɛ} {d}

153
FIRST and FOLLOW..
grammar.
E → TE’
E’→ +TE’ | ɛ
T → FT’
T’→ *FT’ | ɛ
F → id | (E)

154
FIRST and FOLLOW..
Solution:
FIRST
E → TE’ E {id, (}
E’→ +TE’ | ɛ E’ {+, ɛ}
T → FT’ T {id, (}
T’→ *FT’ | ɛ T’ {*, ɛ}
F → id | (E) F {id, (}

155
FIRST and FOLLOW..
Solution:
FIRST FOLLOW
E → TE’ E {id, (} {$, )}
E’→ +TE’ | ɛ E’ {+, ɛ} {$, )}
T → FT’ T {id, (} {+, $, )}
T’→ *FT’ | ɛ T’ {*, ɛ} {+, $, )}
F → id | (E) F {id, (} {*, +, $, )}

156
FIRST and FOLLOW..
grammar.
S → ACB | CbB | Ba
A → da | BC
B→g|ɛ
C→h|ɛ

157
FIRST and FOLLOW..
Solution:
FIRST
S → ACB | CbB | Ba S {d, g, h, ɛ, b, a}
A → da | BC │ ε A {d, g, h, ɛ}
B→g|ɛ B {g, ɛ}
C→h|ɛ C {h, ɛ}

158
FIRST and FOLLOW..
Solution:
FIRST FOLLOW
S → ACB | CbB | Ba S {d, g, h, ɛ, b, a} {$}
A → da | BC A {d, g, h, ɛ} {h, g, $}
B→g|ɛ B {g, ɛ} {$, a, h, g}
C→h|ɛ C {h, ɛ} {g, $, b, h}

159
LL(1) Grammar
Input buffer
$ LL(1)
Scan Left Size

input most of
LL(1) parser from deriva look
Left to tion ahead
$ right
Stack LL(1) parsing table

160
LL(1) Grammar
An unambiguous, non left recursive grammar G is LL(l) if and
only if whenever A →α | β are two distinct productions of G,
the following conditions hold:
1. For no terminal a, do both α and β derive strings beginning
with a.
2. At most one of α and β can derive the empty string.
3. If , then α does not derive any string beginning with
a terminal in FOLLOW(A) . Likewise, if then β does
not derive any string beginning with a terminal in
FOLLOW(A).

161
Parser table for LL(1)
Method:
For each production A→α in the grammar, do the following to
construct a parser table –
1.For each terminal a in FIRST(A), add A→α to M[A, a].
2.If ε is in FIRST(α), then for each terminal b in FOLLOW(A),

add A→α to M[A, b]. If ε is in FIRST(α), and $ is in
FOLLOW(A), then add A→α to M[A, $] as well.

162
Parser table for LL(1)..
FIRST FOLLOW
E → TE’ E {id, (} {$, )}
E’→ +TE’ | ɛ E’ {+, ɛ} {$, )}
T → FT’ T {id, (} {+, $, )}
T’→ *FT’ | ɛ T’ {*, ɛ} {+, $, )}
F → id | (E) F {id, (} {*, +, $, )}

163
FIRST FOLLOW
E → TE’ E {id, (} {$, )}
E’→ +TE’ | ɛ E’ {+, ɛ} {$, )}
T → FT’ T {id, (} {+, $, )}
T’→ *FT’ | ɛ T’ {*, ɛ} {+, $, )}
F → id | (E) F {id, (} {*, +, $, )}
id + * ( ) $
E E→TE’ E→TE’
E’ E’→+TE’ E’→ε E’→ε
T T→FT’ T→FT’
T’ T’→ε T’→*FT’ T’→ ε T’→ ε
F F→id F→(E)

164
FIRST FOLLOW
S → (S) | ɛ S {(, ɛ} {$, )}

165
FIRST FOLLOW
S → (S) | ɛ S {(, ɛ} {$, )}
( ) $
S S→(S) S→ε S→ε

166
Table driven LL(1) parsing Algo
INPUT: A string w and a parsing table M for grammar G.
OUTPUT: If w is in L(G) , a leftmost derivation of w; otherwise, an error indication.
METHOD:
set ip to point to the first symbol of w;
set X to the top stack symbol;
While(X≠$)
{
// a is current symbol of w.
if ( X is a ) {pop the stack and advance ip;}
elseif ( X is a terminal ) error();
elseif ( M [X, a] is an error entry ) {error() ;}
elseif ( M[X, a] = X→Y1Y2…Yk)
{
output the production X →Y1Y2…Yk;
pop the stack;
push Yk, Yk -l, ... , Y1 onto the stack, with Y1 on top;
}
set X to the top stack symbol;
}
167
Parsing for LL(1)
FIRST FOLLOW
S → (S) | ɛ S {(, ɛ} {$, )}
( ) $
Show the sequence of moves to parse the string (()) using the
above parse table.

168
Parsing for LL(1)..
( ) $
w= (())
Matched Stack Input Action
S$ (())$

169
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)

170
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)
( S)$ ())$ match '('

171
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)
( S)$ ())$ match '('
( (S))$ ())$ output S→(S)

172
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)
( S)$ ())$ match '('
( (S))$ ())$ output S→(S)
(( S))$ ))$ match '('

173
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)
( S)$ ())$ match '('
( (S))$ ())$ output S→(S)
(( S))$ ))$ match '(‘
(( ))$ ))$ output S→ε

174
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)
( S)$ ())$ match '('
( (S))$ ())$ output S→(S)
(( S))$ ))$ match '(‘
(( ))$ ))$ output S→ε
(() )$ )$ match ')'

175
Parsing for LL(1)..
( ) $
w= (())
S$ (())$
(S)$ (())$ output S→(S)
( S)$ ())$ match '('
( (S))$ ())$ output S→(S)
(( S))$ ))$ match '('
(( ))$ ))$ output S→ε
(() )$ )$ match ')'
(()) $ $ match ')'

176
Shift Reduce Parser
 The general idea is to shift some symbols of input to the
stack until a reduction can be applied.
 At each reduction step, a specific substring matching the
body of a production is replaced by the non-terminal at the
head of the production.
 The key decisions during bottom-up parsing are about
when to reduce and about what production to apply.
 A reduction is a reverse of a step in a derivation.
 The goal of a bottom-up parser is to construct a derivation
in reverse:
E=>T=>T*F=>T*id=>F*id=>id*id

177
Handle Pruning
A Handle is a substring that matches the body of a
production and whose reduction represents one step along
the reverse of a rightmost derivation.
Example:
Right Sentential Form Handle Reducing Production
id*id id F→id
F*id F T→F
T*id id F→id
T*F T*F E→T*F

178
Shift Reduce Parsing
 A stack is used to hold grammar symbols.
 Handle always appear on top of the stack.
 Initial configuration:
Stack Input
$ w$
 Acceptance configuration:
Stack Input
$S $

179
Operator Precedence Grammar
 An operator precedence grammar is a context-free
grammar that has the property that no production has either
an empty right-hand side or two adjacent nonterminals in its
right-hand side. Or a CFG which is used to define the
mathematical operators is called an operator precedence
grammar.
Example: E→E+E | E*E | id
 Rely on the following three precedence relations between
terminals:
Relation Meaning
a <· b a yields precedence to b
a =· b a has the same precedence as b
a ·> b a takes precedence over b

180
Operator Precedence Parser
 An operator precedence parser is a bottom-up parser
that interprets an operator-precedence grammar.
 Able to parse an ambiguous grammar.
 Simple enough to write by hand.
 Can be written to consult an operator table at run time.
 Not used often in practice.

181
Operator Precedence Parser..
 E→E+E | E*E | id
 Terminals are +, *, id, $.
 Operator precedence relation table:
1. id has the highest precedence.
2. $ has the lowest precedence.
3. Both + and * are left-associative (hence +·>+ and *·>*)
4. Need not compare between id and id because of two
adjacent non-terminals are not present in production
rules.

182
E→E+E | E*E | id
id + * $
id - ·> ·> ·>
+ <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -

183
Algorithm for parsing
Initialize: Set ip to point to the first symbol of w$.
Repeat:
If $ is on the top of the stack and ip points to $ then return
else
Let a be the top terminal on the stack, and b the symbol pointed to by ip;
if a <• b or a =• b then
push b onto the stack ;
advance ip to the next input symbol;
else if a •> b then
repeat
pop the stack;
until (the top stack terminal is related by <• to the terminal most recently
popped)
else
error() ;
end
end

184
Initially, the stack content is $.
Poping Sequence:
id+id*id$ id + * $
id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -
$ a id + id * id

185
As id ·> $, so push id.
Poping Sequence:
id+id*id$ id + * $
id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -
id a
$ id + id * id

186
As + <· id, so pop, or invoke production rule E→id.
Poping Sequence: id
id+id*id$ id + * $
id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -
E
+ a
$ id + id * id

187
As id ·> +, so push id.
Poping Sequence: id
id+id*id$ id + * $
id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -
id a E
+
$ id + id * id

188
As * <· id, so pop, or invoke production rule E→id.
Poping Sequence: id id
id+id*id$ id + * $
id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -
* a E E
+
$ id + id * id

189
As id ·> *, so push id.
Poping Sequence: id id
id+id*id$ id + * $
id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
id a $ <· <· <· -
* E E
+
$ id + id * id

190
As $ <· id, so pop, or invoke the production rule E→id.
Poping Sequence: id id id
id+id*id$ id + * $
Id - ·> ·> ·>
ip + <· ·> <· ·>
* <· ·> ·> ·>
$ <· <· <· -
* a E E E
+
$ id + id * id

191
As $ <· *, so pop, or invoke the production rule E→E*E.
Poping Sequence: id id id *
id+id*id$ id + * $
Id - ·> ·> ·>
ip + <· ·> <· ·>
E * <· ·> ·> ·>
$ <· <· <· -
E E E
+ a
$ id + id * id

192
As $ <· +, so pop, or invoke the production rule E→E+E.
Poping Sequence: id id id * +
id+id*id$ id + * $
E Id - ·> ·> ·>
ip + <· ·> <· ·>
E * <· ·> ·> ·>
$ <· <· <· -
E E E
$ a id + id * id

193
As a and ip both point to $, so end the parsing.
Poping Sequence: id id id * +
id+id*id$ id + * $
E Id - ·> ·> ·>
ip + <· ·> <· ·>
E * <· ·> ·> ·>
$ <· <· <· -
E E E
$ a id + id * id

194
LR Parser
Input buffer
$
LR(K)
Scan Right Size

LR parser input most of
from deriva look
Left to tion ahead
$ right
Stack LR parsing table

195
LR Parser..
LR Parser
LR(0) SLR(1) LALR(1) CLR(1)

Simple Look ahead Canonical
LR LR LR
Use canonical Use canonical

collection of LR(0) collection of LR(1)
items to build the items to build the
parsing table parsing table

196
LR Parser..
The most prevalent type of bottom-up parsers.
LR(k), mostly interested on parsers with k<=1.
Why LR parsers?
 Table driven.
 Can be constructed to recognize all programming
language constructs.
 Most general non-backtracking shift-reduce parsing
method.
 Can detect a syntactic error as soon as it is possible to
do so.
 Class of grammars for which we can construct LR
parsers are superset of those which we can construct
LL parsers.

197
States of a LR Parser
 States represent set of items
 An LR(0) item of G is a production of G with the dot at
some position of the body.
e.g. for A→XYZ we have following items
A→.XYZ
A→X.YZ
A→XY.Z
A→XYZ.
 In a state having A->.XYZ we hope to see a string
derivable from XYZ next on the input.

198
Canonical Collection of LR(0) item
 Augmented grammar:
G with addition of a production: S' → S
 Closure of item sets:
 If I is a set of items, then closure(I) is a set of items
which are constructed from I by the following rules:
 Add every item in I to closure(I)
 If A->α.Bβ is in closure(I) and B->γ is a production
then add the item B->.γ to clsoure(I).

199
Example:
E' → E
E→E+T|T
T→T*F|F
F → (E) | id
I0=closure{[E'→.E]}
E'→.E
E→.E+T
E→.T
T→.T*F
T→.F
F→.(E)
F→.id
200
Example:
S → AA
A → aA | b

201
Example:
S → AA
A → aA | b
Add one more production rule: S' → S
So, now the grammar is:
S'→ S
S → AA
A → aA | b

202
I1
S'→S.
S
I0
I2 I5
S'→.S
A S→A.A A
S→.AA S→AA.
A→.aA | .b A→.aA | .b
a a b
I3 I6
a A
A→a.A A→aA.
b A→.aA | .b
I4 b
A→b.

203
LR(0) Parsing Table
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0
1
2
3
4
5
6

204
LR(0) Parsing Table..
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1
2
3
4
5
6

205
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
2
3
4
5
6

206
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
2 s3 s4 5
3
4
5
6

207
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
2 s3 s4 5
3 s3 s4 6
4
5
6

208
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5
6

209
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6

210
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

211
LR Parsing Algorithm
Set ip to point to the first symbol of the input string and s0 on the stack;
repeat forever
begin
let s be the state on top of the stack and a the symbol pointed to by ip;
if (action[s, a] == shift s') then begin
push a and s' on top of the stack;
advance ip to the next symbol;
end
else if (action[s, a] == reduce A->b) then begin
pop 2*|b| symbols off the stack;
let s' be the state on top of the stack;
push A then goto[s', A] on top of the stack;
output the production A->b;
end
else if (action[s, a] = accept) then return
else error();
end

212
LR(0) Parsing
Line Stack Input Action Action Goto
States
1 0 aabb$ a b $ A S
0 s3 s4 2 1
1 acc
ept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

213
LR(0) Parsing
States
1 0 aabb$ Shift to 3 a b $ A S
2 0a3 abb$
0 s3 s4 2 1
1 acc
ept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

214
LR(0) Parsing
States
2 0a3 abb$ Shift to 3
0 s3 s4 2 1
3 0a3a3 bb$
1 acc
ept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

215
LR(0) Parsing
States
0 s3 s4 2 1
3 0a3a3 bb$ Shift to 4
1 acc
4 0a3a3b4 b$
ept
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

216
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
4 0a3a3b4 b$ Reduce by A→b
ept
5 0a3a3A6 b$ 2 s3 s4 5
3 s3 s4 6
Reduce by A→b means pop 2*|b|=2
symbols from stack which is here 4 and 4 r3 r3 r3
b. Then push A onto the stack and as 5 r1 r1 r1
the previous symbol is 3 in the stack,
then perform goto(3,A) which gives 6. 6 r2 r2 r2
Also push 6 onto the stack and don’t
forward the input pointer.

217
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
ept
5 0a3a3A6 b$ Reduce by A→aA 2 s3 s4 5
6 0a3A6 b$
3 s3 s4 6
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

218
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
ept
6 0a3A6 b$ Reduce by A→aA
3 s3 s4 6
7 0A2 b$
4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

219
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
ept
3 s3 s4 6
7 0A2 b$ Shift to 4
8 0A2b4 $ 4 r3 r3 r3
5 r1 r1 r1
6 r2 r2 r2

220
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
ept
3 s3 s4 6
7 0A2 b$ Shift to 4
8 0A2b4 $ Reduce by A→b 4 r3 r3 r3
9 0A2A5 $ 5 r1 r1 r1
6 r2 r2 r2

221
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
ept
3 s3 s4 6
7 0A2 b$ Shift to 4
9 0A2A5 $ Reduce by S→AA 5 r1 r1 r1

10 0S1 $ 6 r2 r2 r2

222
LR(0) Parsing
States
0 s3 s4 2 1
1 acc
ept
3 s3 s4 6
7 0A2 b$ Shift to 4
9 0A2A5 $ Reduce by S→AA 5 r1 r1 r1

10 0S1 $ Accept 6 r2 r2 r2

223
SLR(1) Parsing Table
1. Construct C = {I0 , I1 , . . . , In } , the collection of sets of LR(0) items for the
augmented grammar G' .
2. State i is constructed from Ii . The parsing actions for state i are determined as
follows:
a) If [A →α.Aβ] is in Ii and GOTO (Ii, a) = Ij , then set ACTION[i, a] to "shift j“.
Here a must be a terminal.
b) If [A→α.] is in Ii , then set ACTION[i, a] to "reduce A→α" for all a in
FOLLOW(A); here A may not be S' .
c) If [S'→S·] is in Ii , then set ACTION[i, $] to "accept“.
If any conflicting actions result from the above rules, we say the grammar
is not SLR(1) . The algorithm fails to produce a parser in this case.
3. The goto transitions for state i are constructed for all nonterminals A using the
rule: If GOTO (Ii, A) = Ij , then GOTo[i, A] = j .
4. All entries not defined by rules (2) and (3) are made "error″.
5. The initial state of the parser is the one constructed from the set of items
containing [S'→.S] .

224
SLR(1) Parsing Table..
S'→ S Action Goto
S → AA 1 States
a b $ A S
A → aA 2
A→b 3 0 s3 s4 2 1
1 accept
First Follow
2 s3 s4 5
S {a,b} {$}
A {a,b} {a,b,$} 3 s3 s4 6
4 r3 r3 r3
5 r1
6 r2 r2 r2

225
SLR(1) Grammar
Every SLR(1) grammar is unambiguous, but there are many
unambiguous grammars that are not SLR(1). Consider the
grammar with productions:
S → L=R | R
L → *R | id
R→L

226
Sets-of-LR(1)-items construction

227
Sets-of-LR(1)-items construction..

228
Example:
S → AA
A → aA | b

229
Example:
S → AA
A → aA | b
Add one more production rule: S' → S
So, now the grammar is:
S'→ S
S → AA
A → aA | b

230
I1 I5
S'→S.,$ S→AA.,$ I9
S
I0 I2 A I6 A A→aA.,$
S'→.S,$ A S→A.A,$ A→a.A,$
a A→.aA,$ a
S→.AA,$ A→.aA,$
A→.aA,a/b A→.b,$ A→.b,$
A→.b,a/b a b I7 b
I3
a A→a.A,a/b A→b.,$
b A→.aA,a/b A I8
A→.b,a/b A→aA.,a/b
I4 b
A→b.,a/b

231
I1 I5 The
S'→S.,$ S→AA.,$ I9 state
S
I0 I2 A I6 A A→aA.,$ pairs (I4,
S'→.S,$ S→A.A,$ A→a.A,$
I7), (I8,
A a A→.aA,$ a I9) and
S→.AA,$ A→.aA,$
A→.aA,a/b A→.b,$ A→.b,$ (I3,I6)
A→.b,a/b a I3 b I7 b have the
a A→b.,$ same
A→a.A,a/b
I LR(0)
b A→.aA,a/b A 8
with
A→.b,a/b A→aA.,a/b
different
I4 b Look-
A→b.,a/b ahead

232
Canonical LR(1) Parsing Table

233
Canonical LR(1) Parsing Table..
Action Goto
States
a b $ A S
0 s3 s4 2 1
1 accept
2 s6 s7 5
3 s3 s4 8
4 r3 r3
5 r1
6 s6 s7 9
7 r3
8 r2 r2
9 r2

234
Canonical LR(1) Parsing Table..
Action Goto As the state
States pairs (I4, I7),
a b $ A S
0 s3 s4 2 1 (I8, I9) and
1 accept (I3, I6) have
2 s6 s7 5
the same
LR(0), merge
3 s3 s4 8
the rows in
4 r3 r3
the parse
5 r1 table and get
6 s6 s7 9 the new
7 r3 parse table
8 r2 r2 as LALR(1)
9 r2 parsing table

235
LALR(1) Parsing Table
Action Goto Renaming
States State 3 and 6
a b $ A S
0 s36 s47 2 1 as (36), State
1 accept 4 and 7 as
2 s36 s47 5
(47), State 8
and 9 as (89).
36 s36 s47 89
47 r3 r3 r3
5 r1
89 r2 r2 r2

236
End of Unit III

237

3-Syntax Analyzer PDF

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

3-Syntax Analyzer PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

3-Syntax Analyzer PDF

Uploaded by

Copyright:

Available Formats

UNIT - III

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Lexical Analysis or Scanner

Syntax Analysis or Parsing

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

L(G) = {an+1bn+k | n≥1, k=-1,1,3….}

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

L(G) = {anbncn | n≥1}

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

L(G) = {WWR | W is in {a, b}*}

Santanu Halder Compiler Design

A grammar G = (V, T, P, S) is said to be left linear grammar if

A regular grammar is one that is either left linear or right

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

2. Construct a CFG to generate the set of palindromes

Santanu Halder Compiler Design

2. Construct a CFG to generate the set of palindromes

Santanu Halder Compiler Design

Santanu Halder Compiler Design

4. Design a CFG for L(G) = {aibicjdj | i,j≥0}.

Santanu Halder Compiler Design

4. Design a CFG for L(G) = {aibicjdj | i,j≥0}.

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

7. Design a CFG for L(G) = {WWR | W is a binary string}.

Santanu Halder Compiler Design

7. Design a CFG for L(G) = {WWR | W is a binary string}.

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

9. Design a CFG for L(G) = {anbm | n≠m}.

Santanu Halder Compiler Design

9. Design a CFG for L(G) = {anbm | n≠m}.

Santanu Halder Compiler Design

9. Design a CFG for L(G) = {anbm | n≠m}.

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design

Santanu Halder Compiler Design