Ll(1) Parser in Compilers

This slide is prepared By these following Students of Dept. of CSE JnU, Dhaka. Thanks To: Nusrat Jahan, Arifatun Nesa, Fatema Akter, Maleka Khatun, Tamanna Tabassum.

1. LL(1)
PARSER

2. MODEL OF COMPILER FRONT END
2
Front End
Also called parsing , where
generates parse tree
Syntax analysis

3. PARSING 3
When the parser starts constructing the
parse tree from the start symbol and then
tries to transform the start symbol to the
input, it is called top-down parsing.
Where bottom-up parsing starts with
the input symbols and tries to construct
the parse tree up to the start symbol.

4. TOP DOWN PERSER 4
Predictive parser is a recursive descent
parser, which has the capability to predict
which production is to be used to replace
the input string. The predictive parser
does not suffer from backtracking.

5. PREDICTIVE PARSER 5
Predictiveparsingusesastackand
aparsingtabletoparsetheinput
andgenerateaparsetree.
Boththestackandtheinput
containsanendsymbol$todenote
thatthestackisemptyandtheinput
isconsumed.
Theparserreferstotheparsing
tabletotakeanydecisiononthe
inputand stackelement
combination.

6. LL(1) PARSER 6
AnLLparseriscalledanLL(k)parserif
itusesktokensoflookaheadwhen
parsingasentence.
LLgrammars,particularlyLL(1)
grammars,asparsersareeasyto
construct,and many computer
languagesaredesignedtobeLL(1)for
thisreason.
The1standsforusingoneinputsymbol
oflookaheadateachsteptomake
parsingactiondecision.

7. CONTINUE…
LL(k)parsersmustpredictwhichproductionreplaceanon-terminalwithassoonas
theyseethenon-terminal.ThebasicLLalgorithmstartswithastackcontaining[S,$]
(toptobottom)anddoeswhicheverofthefollowingisapplicableuntildone:
Ifthetopofthestackisanon-terminal,replacethetopofthestackwithoneof
theproductionsforthatnon-terminal,usingthenextkinputsymbolstodecide
whichone(withoutmovingtheinputcursor),andcontinue.
Ifthetopofthestackisaterminal,readthenextinputtoken.Ifitisthesame
terminal,popthestackandcontinue.Otherwise,theparsehasfailedandthe
algorithmfinishes.
Ifthestackisempty,theparsehassucceededandthealgorithmfinishes.(We
assumethatthereisauniqueEOF-marker$attheendoftheinput.)
Solookaheadmeaningis-lookingatinputtokenswithoutmovingtheinput
cursor.
7

8. PRIME REQUIREMENT OF LL(1)
The grammar must be -
 no left factoring
 no left recursion
FIRST() & FOLLOW()
Parsing Table
Stack Implementation
Parse Tree
8

9. STEP: LEFT FACTORING
9

10. LEFT FACTORING
A grammar is said to be left factored when it is of the form –
A -> αβ
1| αβ
2| αβ
3| …… | αβ
n| γ
The productions start with the same terminal (or set of terminals).
When the choice between two alternative A-productions is not clear, we
may be able to rewrite the productions to defer the decision until enough
of the input has been seen to make the right choice.
For the grammar
A -> αβ
1| αβ
2| αβ
3| …… | αβ
n| γ
The equivalent left factored grammar will be –
A -> αA’ | γ
A’ -> β
1| β
2| β
3| …… | β
n
10

11. CONTINUE…
For example :
the input string is -aab& grammar is
S ->aAb|aA|ab
A ->bAc|ab
After removing left factoring -
S ->aA’
A’ ->Ab|A|b
A ->ab|bAc
11

12. 12
STEP: LEFT RECURSION

13. RECURSION
RECURSION:
Theprocessinwhichafunctioncallsitselfdirectlyorindirectlyiscalledrecursion
andthecorrespondingfunctioniscalledasrecursivefunction.
TYPESOFRECURSION
LEFTRECURSION RIGHTRECURSION
13

14. Left Recursion Right Recursion
For grammar: For grammar:
A->A| β A-> A| β
A
A  A
A   A
A   A
β  A
β
This parse tree generate β * This parse tree generate *β
14

15. Right recursion-
 A production of grammar is said to have right recursion if
the right most variable RHS is same as
variable of its LHS. e.g. A -> A| β
 A grammar containing a production having right recursion is
called as a right recursive grammar.
 Right recursion does not create any problem for the top
down parsers.
 Therefore, there is no need of eliminating right recursion
from the grammar.
15

16. Left recursion-
 A production of grammar is said to have left
recursion if the leftmost variable of its RHS is same
as variable of its LHS. e.g. A -> A | β
 A grammar containing a production having left
recursion is called as aleft recursive grammar.
 Left recursion is eliminated because top down
parsing method can not handle left recursive
grammar.
16

17. Left Recursion
AgrammarisleftrecursiveifithasanonterminalAsuchthatthereisa
derivation
A->A|βforsomestring.
Immediate/directleftrecursion:
Aproductionisimmediatelyleftrecursiveifitslefthandsideandtheheadofits
righthandsidearethesamesymbol,e.g.A->A,whereαissequence
ofnonterminalsandterminals.
Indirectleftrecursion:
Indirectleftrecursionoccurswhenthedefinitionofleftrecursionissatisfiedvia
severalsubstitutions.Itentailsasetofrulesfollowingthepattern
. A→Br
B→Cs
C→At
Here,startingwitha,wecanderiveA->Atsr
17

18. Elimination of Left-Recursion
Suppose the grammar were
AA| 
How could the parser decide how many times to use the production A
Abefore using the production A -->?
Left recursion in a production may be removed by transforming the
grammar in the following way.
Replace
AA| 
With
AA'
A'A'| 
18

19. EXAMPLE OF IMMEDIATE LEFT RECURSION :
Consider the left recursive grammar
EE+ T| T
TT* F| F
F(E)|id
Apply the transformation to E:
ETE'
E'+ TE'| 
Then apply the transformation to T:
TF T'
T'* F T'| 
Now the grammar is
ET E'
E'+ T E'| 
TF T'
T'* F T'| 
F(E) | id
19

20. Continue…
The case of several immediate left recursive-productions. Assume
that the set of all-productions has the form
A → A1 | A2 | · · · | Am | β1 | β2| · · · | βn
Represents all the -productions of the grammar, and no βi begins
withA, then we can replace these -productions by
A →β1A′ | β2A′| · · · | βnA′
A′ → 1A′ | 2A′ | · · · | mA′ | 
20

21. Example:
Consider the left recursive grammar
S → SX | SSb| XS | a
X → Xb| Sa
Apply the transformation to S:
S → XSS′ | aS′
S′ → XS′ | SbS′ | ε
Apply the transformation to X:
X → SaX′
X′ → bX′ | ε
Now the grammar is
S → XSS′ | aS′
S′ → XS′ | SbS′ | ε
X → SaX′
X′ → bX′ | ε
21

22. Example of elimination indirect left
recursion:
S A A | 0
A S S | 1
Considering the ordering S, A, we get:
S A A | 0
A S | 0S | 1
And removing immediate left recursion, we get
S A A | 0
A0SA′| 1A′
A′ ε| ASA′
22

23. STEP:FIRST & FOLLOW
23

24. Why using FIRST and FOLLOW:
During parsing FIRST and FOLLOW help us to choose
which production to apply , based on the next input signal.
We know that we need of backtracking in syntax analysis, which is
really a complex process to implement. There can be easier way to
sort out this problem by using FIRST AND FOLLOW.
If the compiler would have come to know in advance, that what is the
“first character of the string produced when a production rule is
applied”, and comparing it to the current character or token in the input
string it sees, it can wisely take decision on which production rule to
apply .
FOLLOW is used only if the current non terminal can derive ε.
24

25. Rules of FIRST
FIRST always find out the terminal symbol from the grammar.
When we check out FIRST for any symbol then if we find any
terminal symbol in first place then we take it. And not to see the
next symbol.
If a grammar is
A → a then FIRST ( A )={ a }
If a grammar is
A → a B then FIRST ( A )={ a }
25

26. Rules of FIRST
If a grammar is
A → aBǀ εthen FIRST ( A )={ a,ε}
If a grammar is
A → BcDǀ ε
B → eDǀ ( A )
Here B is non terminal. So, we check the transition of B and
find the FIRST of A.
then FIRST ( A )={ e,( ,ε}
26

27. Rules of FOLLOW
For doing FOLLOW operation we need FIRST operation mostly. In FOLLOW
we use a $ sign for the start symbol. FOLLOW always check the right
portion of the symbol.
If a grammar is
A → BAc; A is start symbol.
Here firstly check if the selected symbol stays in right side of the grammar.
We see that c is right in A.
then FOLLOW (A) = {c , $ }
27

28. Rules of FOLLOW
If a grammar is
A → BA’
A' →*Bc
Here we see that there is nothing at the right side of A' . So
FOLLOW ( A' )= FOLLOW ( A )= { $ }
Because A' follows the start symbol.
28

29. Rules of FOLLOW
If a grammar is
A → BC
B → Td
C →*D ǀ ε
When we want to find FOLLOW (B),we see that B follows by C . Now
put the FIRST( C) in the there.
FIRST(C)={*,ε}.
But when the value is €it follows the parents symbol. So
FOLLOW(B)={*,$ }
29

30. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E
E’
T
T’
F
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
30

31. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id }
E'
T
T'
F
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
31

32. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id }
E' { + , ε}
T
T'
F
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
32

33. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id }
E' { + , ε}
T { id , ( }
T'
F
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
33

34. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id }
E' { + , ε}
T { id , ( }
T' { * , ε}
F
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
34

35. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id }
E' { + , ε}
T { id , ( }
T' { * ,ε}
F { id , ( }
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
35

36. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id } { $ , ) }
E' { + , ε}
T { id , ( }
T' { * ,ε}
F { id , ( }
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
36

37. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id } { $ , ) }
E' { + , ε} { $ , ) }
T { id , ( }
T' { * , ε}
F { id , ( }
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
37

38. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id } { $ , ) }
E' { + , ε} { $ , ) }
T { id , ( } { $ ,) ,+ }
T' { * , ε}
F { id , ( }
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
38

39. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id } { $ , ) }
E' { + , ε} { $ , ) }
T { id , ( } { $ ,) ,+ }
T' { * , ε} { $ , ) , + }
F { id , ( }
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
39

40. Example of FIRST and FOLLOW
Symbol FIRST FOLLOW
E { ( , id } { $ , ) }
E' { +,ε} { $ , ) }
T { id , ( } { $ ,) ,+ }
T' { * , ε} { $ , ) , + }
F { id , ( } { $, ) , + , * }
GRAMMAR:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id
40

41. STEP: PARSING TABLE
41

42. Example of LL(1) grammar
E -> TE’
E’ -> +TE’|ε
T -> FT’
T’ -> *FT’|ε
F -> (E)|id
42

43. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
43
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E
E’
T
T’
F

44. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
44
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’
E’
T
T’
F

45. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
45
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’
T
T’
F

46. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
46
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’ E’-> +TE’
T
T’
F

47. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
47
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’ E’-> +TE’ E’ -> εE’ -> ε
T
T’
F

48. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
48
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’ E’-> +TE’ E’ -> εE’ -> ε
T T -> FT’
T’
F

49. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
49
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’ E’-> +TE’ E’ -> ε E’ -> ε
T T -> FT’ T -> FT’
T’
F

50. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
50
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’ E’-> +TE’ E’ -> ε E’ -> ε
T T -> FT’ T -> FT’
T’ T’ -> *FT’
F

51. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
51
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
id + * ( ) $
E E -> TE’ E -> TE’
E’ E’-> +TE’ E’ -> ε E’ -> ε
T T -> FT’ T -> FT’
T’ T’ -> ε T’ -> *FT’ T’ -> ε T’ -> ε
F

52. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
52
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
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

53. TABLE:
PARSING
TABLE
TABLE:
FIRST & FOLLOW
53
Production Symbol FOLLOW
E -> TE’ { ( , id } { $ , ) }
E’ -> +TE’|ε { + ,ε} { $ , ) }
T -> FT’ { ( , id } { + , $ , ) }
T’ -> *FT’|ε { * , ε} { + , $ , ) }
F -> (E)|id { ( , id } { *, + , $ , ) }
Non
Terminal
INPUT SYMBOLS
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)

54. Continue…
54
TABLE: PARSING TABLE
Non
Terminal
INPUT SYMBOLS
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)
This grammar is LL(1).
So, the parse tree can be derived from the stack
implementation of the given parsing table.

55. There are grammars which may requite LL(1) parsing.
For e.g. Look at next grammar…..
55
Continue…

56. Continue…
GRAMMAR:
S iEtSS’ | a
S’ eS|ε
E b
SYMBOL FIRST FOLLOW
S a , i $ ,e
S’ e ,ε $ ,e
E b t
TABLE: FIRST & FOLLOW
56

57. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
57
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S
S’
E

58. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
58
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S Sa
S’
E

59. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
59
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S Sa
SiEtSS
’
S’
E

60. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
60
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S Sa
SiEtSS
’
S’ S’ eS
E

61. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
61
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S Sa
SiEtSS
’
S’
S’ eS
S’ε
S’ε
E

62. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
62
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S Sa
SiEtSS
’
S’
S’ eS
S’ε
S’ε
E E b

63. TABLE:
PARSING TABLE
TABLE:
FAST & FOLLOW
63
AMBIGUITY
SYMBOL FIRST FOLLOW
S iEtSS’ | a
a , i $ ,e
S’ eS|ε
e,ε $ ,e
E b
b t
Non
Terminal
INPUT SYMBOLS
a b e i t $
S Sa
SiEtSS
’
S’
S’ eS
S’ε
S’ε
E E b

64. Continue…
Thegrammarisambiguousanditisevidentbythefactthat
wehavetwoentriescorrespondingtoM[S’,e]containing
S’εandS’eS.
NotethattheambiguitywillbesolvedifweuseLL(2)parser,i.e.
Alwaysseeforthetwoinputsymbols.
LL(1)grammarshavedistinctproperties.
-Noambiguousgrammarorleftrecursivegrammar
canbeLL(1).
Thus,thegivengrammarisnotLL(1).
64

65. STEP: STACK IMPLEMENTATION
65

66. STACK Implementation
The predictive parser uses an explicit stackto keep track of pending
non-terminals. It can thus be implemented without recursion.
Note that productions output are tracing out a lefmost derivation
The grammar symbols on the stack make up left-sentential forms
66

67. LL(1) Stack
The input buffercontains the string to be parsed; $is the end-
of-input marker
The stackcontains a sequence of grammar symbols
Initially, the stackcontains the start symbol of the grammar on
the top of $.
67

68. LL(1) Stack
The parser is controlled by a program that behaves as follows:
The program considers X, the symbol on topof the stack, and a, the
current inputsymbol.
These two symbols, Xand adetermine the action of the parser.
There are threepossibilities.
68

69. LL(1) Stack
1.Xa $,
the parser halts and annouces successful completion.
2.Xa $
the parser pops xoff the stack and advances input pointer to next
input symbol
3.If X is a nonterminal, the program consults entry M[x,a] of parsing
table M.
If the entry is a production M[x,a] = {x →uvw } then the
parser replaces xon top of the stack by wvu(with uon top).
As output, the parser just prints the production used:
x →uvw .
69

70. LL(1) Stack
Example:
Let’s parse the input
string
id+idid
Using the nonrecursive
LL(1) parser
70
Grammar:
E -> TE'
E'-> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id

71. 71
id
E
+idid
$
$
stack
Parsing
Table

72. Parsing Table
72
id
+ * ( ) $
EE →TE' E →TE'
E' E' →
+TE'
E' →E' →
TT →FT' T →FT'
T' T' → 
T →*FT' T' →T' →
FF → id F →(E)

73. 73
id
E
+idid
$
$
stack
Parsing
Table
E→TE'

74. 74
id+idid
$
$
stack
Parsing
Table M
T→
T
E'
FT'
Non
Terminal
INPUT SYMBOLS
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)

75. 75
T'
id+idid
$
$
stack
Parsing
Table M
→
E'
F
Fid
Non
Terminal
INPUT SYMBOLS
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)

76. 76
T'
id+idid
$
$
stack
Parsing
Table M
E'
id
Non
Terminal
INPUT SYMBOLS
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)

77. 77
T'
+idid
$
$
stack
Parsing
Table M
→
E'
T'
id
Non
Terminal
INPUT SYMBOLS
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)

78. 78
+idid
$
$
stack
Parsing
Table M
→
E'
E'+
id
E'T
Non
Terminal
INPUT SYMBOLS
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)

79. 79
+idid
$
$
stack
Parsing
Table M
E'
+
id
T
Non
Terminal
INPUT SYMBOLS
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)

80. 80
MATCHED STACK INPUT ACTION
E$ id+id* id$
TE’$ id+id* id$ E->TE’
FT’E’$ id+id* id$ T->FT’
idT’E’$ id+id* id$ F->id
id T’E’$ +id * id$ Match id
id E’$ +id * id$ T’->Є
id +TE’$ +id* id$ E’-> +TE’
id+ TE’$ id* id$ Match +
id+ FT’E’$ id* id$ T-> FT’
id+ idT’E’$ id* id$ F-> id
id+id T’E’$ *id$ Match id
id+id * FT’E’$ *id$ T’-> *FT’
id+id* FT’E’$ id$ Match *
id+id* idT’E’$ id$ F->id
id+id* id T’E’$ $ Match id
id+id* id E’$ $ T’-> Є
id+id* id $ $ E’-> Є

81. STEP: LL(1) PARSE TREE
81

82. LL(1) Parse Tree
Top-down parsing expandsa parse tree from the start
symbolto the leaves
Always expand the leftmostnon-terminal
82

83. id+idid
83
E
T
E'
F
id
T'

E'
T+
F T'
id

* F T'
id 
DONE…