TYPES OF PARSING

There are two types of parsing:

i). Top-down parsing
ii). Bottom-up parsing
I). TOP-DOWN PARSING
Top-down parsing is a parsing strategy that finds the derivation of the input string from the start symbol of
the grammar.
There are two main approaches for top-down parsing:
a) Recursive descent parsing
b) Predictive parsing
a) Recursive Descent Parsing
It is a common form of top-down parsing that uses a parsing technique, which recursively parses the input to
make a parse tree from the top and the input is read from left to right. It is called recursive, as it uses
recursive procedures to process the input. The central idea is that each nonterminal in the grammar is
implemented by a procedure in the program.
Generally, these parsers consist of a set of mutually recursive routines that may require back-tracking to
create the parse tree.

Backtracking: It means, if one derivation of a production fails, the syntax analyser restarts the process using
different rules of same production. This technique may process the input string more than once to determine
the right production.

Example
Consider the following grammar
𝑆 → 𝑎𝑏𝐴
𝐴 → 𝑐𝑑|𝑐|𝑒

For the input stream 𝑎𝑏, the recursive descent parser starts by constructing a parse tree representing
𝑆 → 𝑎𝑏𝐴 as shown below:
S

a b A

The stream is then expanded with the production 𝐴 → 𝑐𝑑 as shown below

a b A

c d

Since it does not match 𝑎𝑏, it backtracks and tries the alternative 𝐴 → 𝑐 as shown below:

Compiler Construction ~ Wainaina Page 1 of 9

 S

a b A

However, the parse tree does not match 𝑎𝑏; the parser backtracks and tries the alternative 𝐴 → 𝑒 as shown
below:

a b A

With this, it finds a match and thus pursing is completely successful.

In general, using recursive descent parsing, one can write a procedure for each non-terminal in the language
definition:
i). Where the right hand side contains alternatives, the next symbol to input provides the selector for a
switch statement, each branch of which represents one alternative.
ii). If 𝑒 is an alternative, it becomes the default of the switch.
iii). Where a repetition occurs, it can be implemented iteratively.
iv). The sequence of actions within each branch, possibly one, consists of an inspection of the lexical
token for each terminal, and a procedure will be assigned to a local or global variable as required by
semantics of the language.
Example
The following is a recursive descent parser for the grammar shown below:
T’ →T$
T→R
T → aTc
R→ɛ
R → bR

parseT’() =
if next = ’a’ or next = ’b’ or next = ’$’ then
parseT() ; match(’$’)
else reportError()

parseT() =
if next = ’b’ or next = ’c’ or next = ’$’ then
parseR()
else if next = ’a’ then
match(’a’) ; parseT() ; match(’c’)

Compiler Construction ~ Wainaina Page 2 of 9

 else reportError()

parseR() =
if next = ’c’ or next = ’$’ then
(* do nothing *)
else if next = ’b’ then
match(’b’) ; parseR()
else reportError()

b) Predictive Parsing
Predictive parsing is a special form of recursive descent parsing in which the current input token
unambiguously determines the production to be applied at each step i.e. they are backtrack free.
Non-recursive Predictive – 𝐋𝐋(𝐤) Parsing
This is a parsing strategy which involves building tables instead of writing code. It is also possible to
automatically create tables. These parsers scan over the input stream using a prefix of tokens so as to
identify production to be applied. The language accepted by these parsers is called
𝐿𝐿(𝑘),
where 𝑘 is the length of the prefix. 𝐿𝐿 Stands for: Left to right scan; left most derivation.

The length of the prefix to be considered will be 𝑘 = 1. The construction of an 𝐿𝐿(1) parser for the
grammar < 𝑉𝑁 , 𝑉𝑇 , 𝑃, 𝑆 > requires first computing the following properties:

𝐅𝐈𝐑𝐒𝐓(𝐀) = {𝑢|𝑢 ∈ 𝑉𝑇 𝑎𝑛𝑑 𝐴 𝑐𝑎𝑛 𝑑𝑒𝑟𝑖𝑣𝑒 𝑎 𝑠𝑡𝑟𝑖𝑛𝑔 𝑠𝑡𝑎𝑟𝑡𝑖𝑛𝑔 𝑤𝑖𝑡ℎ 𝑢}

𝐅𝐎𝐋𝐋𝐎𝐖(𝐀) = {𝑢|𝑢 ∈ 𝑉𝑇 𝑎𝑛𝑑 𝑆 𝑐𝑎𝑛 𝑑𝑒𝑟𝑖𝑣𝑒 𝑎 𝑠𝑡𝑟𝑖𝑛𝑔 𝑙𝑖𝑘𝑒 𝛼𝐴𝑢β}
𝐅𝐈𝐑𝐒𝐓(𝛂) = {𝑢|𝑢 ∈ 𝑉𝑇 𝑎𝑛𝑑 𝛼𝑐𝑎𝑛 𝑑𝑒𝑟𝑖𝑣𝑒 𝑎 𝑠𝑡𝑟𝑖𝑛𝑔 𝑙𝑖𝑘𝑒 𝑢𝛽}

Generally, FIRST (A) is the set of terminals that can start a string derivable from A; FOLLOW (A) is the
set of terminals that can follow an occurrence of A, FIRST (𝛼) is the set of terminals that can start a string
derivable from 𝛼.
To compute these sets of grammar, it is necessary to define another property:

true, If A can derive e in zero(0) or more steps

nullable (A) = false, Otherwise

Notice that a non-terminal A is nullable if 𝑛𝑢𝑙𝑙𝑎𝑏𝑙𝑒(𝐴) = 𝑡𝑟𝑢𝑒, and a terminal is never nullable.
The following is the algorithm for computing first and follow sets of a grammar:

Compiler Construction ~ Wainaina Page 3 of 9

 for all 𝐴 ∈ 𝑁 𝑑𝑜
𝐹𝐼𝑅𝑆𝑇(𝐴) = 𝜙;
𝐹𝑂𝐿𝐿𝑂𝑊(𝐴) = 𝜙;
𝑓𝑜𝑟 𝑎𝑙𝑙 𝑢 ∈ 𝑇 𝑑𝑜
𝐹𝐼𝑅𝑆𝑇(𝑢) = {𝑢};
𝑑𝑜
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝐴 → 𝑋1 … 𝑋𝑛 ∈ 𝑃 𝑑𝑜
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑖 ∈ 1 … , 𝑛 𝑑𝑜
𝑖𝑓 𝑋1 … 𝑋𝑖−1 𝑎𝑟𝑒 𝑎𝑙𝑙 𝑛𝑢𝑙𝑙𝑎𝑏𝑙𝑒 𝑡ℎ𝑒𝑛
𝐹𝐼𝑅𝑆𝑇(𝐴) = 𝐹𝐼𝑅𝑆𝑇(𝐴) ∪ 𝐹𝐼𝑅𝑆𝑇(𝑋𝑖 )
𝑖𝑓 𝑋𝑖+1 , … , 𝑋𝑛 𝑎𝑟𝑒 𝑎𝑙𝑙 𝑛𝑢𝑙𝑙𝑎𝑏𝑙𝑒 𝑡ℎ𝑒𝑛
𝐹𝑂𝐿𝐿𝑂𝑊(𝑋𝑖 ) = 𝐹𝑂𝐿𝐿𝑂𝑊(𝑋𝑖 ) ∪ 𝐹𝑂𝐿𝐿𝑂𝑊(𝐴)
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑗 ∈ 𝑖 + 1, … , 𝑛 𝑑𝑜
𝑖𝑓 𝑋𝑖+1 , … , 𝑋𝑗−1 𝑎𝑟𝑒 𝑎𝑙𝑙 𝑛𝑢𝑙𝑙𝑎𝑏𝑙𝑒 𝑡ℎ𝑒𝑛
𝐹𝑂𝐿𝐿𝑂𝑊(𝑋𝑖 ) = 𝐹𝑂𝐿𝐿𝑂𝑊(𝑋𝑖 ) ∪ 𝐹𝑂𝐿𝐿𝑂𝑊(𝑋𝑗 );
𝑖𝑓 𝑎𝑙𝑙 𝑋𝑖′ 𝑠
𝑎𝑟𝑒 𝑎𝑙𝑙 𝑛𝑢𝑙𝑙𝑎𝑏𝑙𝑒 𝑡ℎ𝑒𝑛
𝑁𝑈𝐿𝐿𝐴𝐵𝐸𝐿(𝐴) = 𝑡𝑟𝑢𝑒
𝑢𝑛𝑡𝑖𝑙 𝐹𝐼𝑅𝑆𝑇, 𝐹𝑂𝐿𝐿𝑂𝑊 𝑎𝑛𝑑 𝑁𝑈𝐿𝐿𝐴𝐵𝐿𝐸 𝑠𝑒𝑡𝑠 𝑑𝑜 𝑛𝑜𝑡 𝑐ℎ𝑎𝑛𝑔𝑒

We can extend the notation of FIRST set to include 𝑒 and define them for strings as follows:

𝐹𝐼𝑅𝑆𝑇(𝑒) = {𝑒}

𝑋 𝑖𝑓 𝑋 ∈ 𝑇

𝐹𝐼𝑅𝑆𝑇(𝑋𝛼) = 𝐹𝐼𝑅𝑆𝑇(𝑋) 𝑖𝑓 𝑁𝑈𝐿𝐿𝐴𝐵𝐿𝐸(𝑋) = 𝑓𝑎𝑙𝑠𝑒

{ 𝐹𝐼𝑅𝑆𝑇(𝑋) ∪ 𝐹𝐼𝑅𝑆𝑇(𝛼) 𝑖𝑓 𝑁𝑈𝐿𝐿𝐴𝐵𝐿𝐸(𝑋) = 𝑡𝑟𝑢𝑒

Compiler Construction ~ Wainaina Page 4 of 9

LOOKAHEAD
For a production rule, 𝐴 → 𝛼, 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼) is defined as the set of terminals which can appear
next in the input when recognizing a production rule 𝐴 → 𝛼. Thus, a production rule’s LOOKAHEAD set
specifies the tokens which should appear next in the input before a production is applied.

To build 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼):

i). Put 𝐹𝐼𝑅𝑆𝑇(𝛼) − {𝑒} in 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼)

ii). If 𝑒 ∈ 𝐹𝐼𝑅𝑆𝑇(𝛼)
then put 𝐹𝑂𝐿𝐿𝑂𝑊(𝐴) in 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼)

A grammar 𝐺 is 𝐿𝐿(1) iff, for each set of production, 𝐴 → 𝛼1 |𝛼2 | … |𝛼𝑛

𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼1 ), 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼2 ) … 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝛼𝑛 ) are all pairwise disjoint

The following are facts about 𝐿𝐿(1) grammar:
i). No left recursive grammar is 𝐿𝐿(1).
ii). No ambiguous grammar is 𝐿𝐿(1).
iii). Some languages have no 𝐿𝐿(1) grammar.
iv). An 𝑒-free grammar where each alternative expansion for 𝐴 begins with a distinct terminal is a
simple 𝐿𝐿(1) grammar.

Example 1
Given the grammar
𝑆 → 𝑎𝑆|𝑎

Find whether it is 𝐿𝐿(1) grammar.

Solution:
𝐹𝐼𝑅𝑆𝑇(𝑆) = {𝑎}
Therefore, 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑆 → 𝑎𝑆) =
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑆 → 𝑎) = {𝑎}
Hence it is not 𝐿𝐿(1)grammar
Note: FOLLOW sets are not required since empty sets are not required in the grammar.

Example 2
Consider the grammar
𝐸 → 𝑇|𝐸 + 𝑇
𝑇 → 𝐹|𝑇 ∗ 𝐹
𝐹 → 𝑎|(𝐸)
Find whether the grammar is 𝐿𝐿(1).

Solution:
Calculate the FIRST sets:
𝐹𝐼𝑅𝑆𝑇(𝐹) = {𝑎, ( }
𝐹𝐼𝑅𝑆𝑇(𝑇) = {𝑎, ( }
𝐹𝐼𝑅𝑆𝑇(𝐸) = {𝑎, ( }
Calculate the LOOKAHEAD sets:
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐸 → 𝑇) = {𝑎, (}

Compiler Construction ~ Wainaina Page 5 of 9

 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐸 → 𝐸 + 𝑇) = {𝑎, ( }
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑇 → 𝐹) = {𝑎, ( }
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑇 → 𝑇 ∗ 𝐹) = {𝑎, ( }
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐹 → 𝑎) = {𝑎}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐹 → (𝐸)) = {( }
Hence the grammar is not 𝐿𝐿(1).

Example 3
Verify whether or not the following grammar is 𝐿𝐿(1):
𝑆 → 𝐴𝐵𝑎
𝐴 → 𝑏𝐴
𝐴→𝑒
𝐵 → 𝑎𝐵
𝐵→𝑒
Solution
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑆 → 𝐴𝐵𝑎) = (𝐹𝐼𝑅𝑆𝑇(𝐴) − {𝑒}) ∪ (𝐹𝐼𝑅𝑆𝑇(𝐵) − {𝑒}) ∪ 𝐹𝐼𝑅𝑆𝑇(𝑎)
= {𝑏} ∪ {𝑎} = {𝑎, 𝑏}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝑏𝐴) = 𝐹𝐼𝑅𝑆𝑇(𝑏) = {𝑏}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝑒) = (𝐹𝐼𝑅𝑆𝑇(𝑒) − {𝑒}) ∪ 𝐹𝑂𝐿𝐿𝑂𝑊(𝐴) = { } ∪ {𝑎} = {𝑎}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐵 → 𝑎𝐵) = 𝐹𝐼𝑅𝑆𝑇(𝑎) = {𝑎}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐵 → 𝑒) = (𝐹𝐼𝑅𝑆𝑇(𝑒) − {𝑒}) ∪ 𝐹𝑂𝐿𝐿𝑂𝑊(𝐵) = { } ∪ {𝑎} = {𝑎}
Hence the grammar is not 𝐿𝐿(1) since 𝑎 predicts 𝐵 → 𝑎𝐵 and 𝐵 → 𝑒.

Example 4
Consider the following grammar:
𝑆 → 𝑎𝐴𝑎
𝑆→𝑏
𝐴 → 𝑎𝑏
𝐴→𝑒
Verify whether the grammar is 𝐿𝐿(1) or not.
Solution:
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑆 → 𝑎𝐴𝑎) = 𝐹𝐼𝑅𝑆𝑇(𝑎) = {𝑎}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝑆 → 𝑏) = 𝐹𝐼𝑅𝑆𝑇(𝑏) = {𝑏}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝑎𝑏) = 𝐹𝐼𝑅𝑆𝑇(𝑎) = {𝑎}
𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷(𝐴 → 𝑒) = 𝐹𝑂𝐿𝐿𝑂𝑊(𝐴) = {𝑎}
Therefore the grammar is not 𝐿𝐿(1) since 𝑎 is in both 𝐴 → 𝑎𝑏 and 𝐴 → 𝑒.

Compiler Construction ~ Wainaina Page 6 of 9

LL (1) Parse Table Construction

Method - 1:
Once the first and follow states have been computed, it is possible to construct 𝐿𝐿(1) parse table 𝑀 that
maps pairs of non-terminals and terminals to production using the following method:

Input: Grammar 𝐺
Output: Parsing table 𝑀
Method:
1. ∀ 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝐴 → 𝛼
∀𝑎 ∈ 𝐿𝑂𝑂𝐾𝐴𝐻𝐸𝐴𝐷 𝐴 → 𝛼
𝑎𝑑𝑑 𝐴 → 𝛼 𝑡𝑜 𝑀 𝐴, 𝑎
2. Set each unidentified entry of 𝑀 to error

If ∃𝑀 𝐴, 𝑎 with multiple entries then the grammar is not 𝐿𝐿(1).

Example
Consider the following grammar:
𝑆→𝐸
𝐸 → 𝑇𝐸′
𝐸′ → +𝐸|−𝐸|𝑒
𝑇 → 𝐹𝑇′
𝑇′ →∗ 𝑇|/𝑇|𝑒
𝐹 → 𝑖𝑑|𝑛𝑢𝑚

The following is the table of FIRST and FOLLOW sets:

Symbol FIRST FOLLOW

S {num , id} {$}
E {num , id} {$}
E‘ {+,-,e} {$}
T {num, id} {+,-,$}
T’ {*,/,e} {+,-,$}
F {num, id} {+,-,*,/,$}
id {id}
num {num}
* {*}
/ {/}
+ {+}
- {-}

The following is the table of LOOKAHEAD sets:

Production LOOKAHEAD
S→E {num, id}
E→TE’ {num, id}
E’→+E {+}
E’→-E {-}
E’→e {$}
T→FT’ {num, id}
T’→*T {*}

Compiler Construction ~ Wainaina Page 7 of 9

 T’→/T {/}
T’→e {+,-,$}
F→id {id}
F→num {num}

Note: The $ sign is a special symbol for ‘end of input’.

The following is the parsing table:

Symbol Id num + - * / $
S S→E S→E
E E→TE’ E→TE’
E’ E’→+E E’→-E E’→e
T T→FT’ T→FT’
T’ T’→e T’→e T’→*T T’→/T T’→e
F F→id F→num

Method - 2:
Alternatively, once the FIRST and FOLLOW sets have been computed, LL(1) parse table M, that maps pairs
of non-terminals and terminals to productions can be constructed by using the following algorithm.

𝐹𝑜𝑟 𝑒𝑎𝑐ℎ 𝐴 → 𝛼 ∈ 𝑃 𝑑𝑜
𝑖𝑓 𝑒 ∈ 𝐹𝑖𝑟𝑠𝑡(𝛼) 𝑡ℎ𝑒𝑛
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑢 ∈ 𝑓𝑜𝑙𝑙𝑜𝑤(𝐴) 𝑑𝑜
𝑎𝑑𝑑 𝐴 → 𝛼 𝑡𝑜 𝑀 𝐴, 𝑢
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑢 ∈ 𝐹𝑖𝑟𝑠𝑡 (𝛼) 𝑑𝑜
𝑎𝑑𝑑 𝐴 → 𝛼 𝑡𝑜 𝑀 𝐴, 𝑢

If the resulting table has at most one production per (𝐴, 𝑢) pair then the grammar is 𝐿𝐿(1):

Example
Consider the following grammar:

𝐸 → 𝑀𝐸’
𝐸’ → 𝑒
𝐸’ → +𝑀𝐸’
𝑀 → 𝐴𝑀’
𝑀’ → 𝑒
𝑀’ →∗ 𝐴𝑀’
𝐴 → 𝑛𝑢𝑚
𝐴 → (𝐸)
The following is the table of the first and follow sets:

Symbol First Follow

E {num,( } { ),$}
E’ {+,e} { ),$}
M {num,( } { ),+,$}
M’ {*,e } { ),+,$}
A {num,(} { ),+,*,$}
The following is the parsing table M for the grammar:
Compiler Construction ~ Wainaina Page 8 of 9
 num + * ( ) $
E E→ME’ E→ME’
E’ E’→+ME’ E’→e E’→e
M M→AM’ M→AM’
M’ M’→e M’→*AM’ M’→e M’→e
A A→num A→(E)

The table driven parser for 𝐿𝐿(1) grammar works using a parsing table and an auxiliary stack of grammar
symbols. The table driven parser uses the following algorithm:

𝑊ℎ𝑖𝑙𝑒 𝑠𝑡𝑎𝑐𝑘 𝑖𝑠 𝑛𝑜𝑡 𝑒𝑚𝑝𝑡𝑦 𝑑𝑜

𝐿𝑒𝑡 𝑋 𝑏𝑒 𝑡ℎ𝑒 𝑡𝑜𝑝 𝑠𝑦𝑚𝑏𝑜𝑙 𝑜𝑛 𝑡ℎ𝑒 𝑠𝑡𝑎𝑐𝑘
𝐿𝑒𝑡 𝑈 𝑏𝑒 𝑡ℎ𝑒 𝑛𝑒𝑥𝑡 𝑖𝑛𝑝𝑢𝑡 𝑠𝑦𝑚𝑏𝑜𝑙
𝐼𝑓 𝑋 ∈ 𝑇 𝑡ℎ𝑒𝑛
𝐼𝑓 𝑋 = 𝑈 𝑡ℎ𝑒𝑛
𝑃𝑜𝑝 𝑋 𝑜𝑓𝑓 𝑡ℎ𝑒 𝑠𝑡𝑎𝑐𝑘 𝑎𝑛𝑑 𝑎𝑑𝑣𝑎𝑛𝑐𝑒 𝑡ℎ𝑒 𝑖𝑛𝑝𝑢𝑡
𝐸𝑙𝑠𝑒
𝑃𝑎𝑟𝑠𝑖𝑛𝑔 𝑒𝑟𝑟𝑜𝑟
𝐸𝑙𝑠𝑒 𝑖𝑓 𝑀 𝑋, 𝑈 = 𝐴 → 𝑌1 , … 𝑌n 𝑡ℎ𝑒𝑛
𝑃𝑜𝑝 𝑋 𝑎𝑛𝑑 𝑝𝑢𝑠ℎ 𝑌n , … 𝑌1 𝑜𝑛𝑡𝑜 𝑡ℎ𝑒 𝑠𝑡𝑎𝑐𝑘
𝐸𝑙𝑠𝑒
𝑃𝑎𝑟𝑠𝑖𝑛𝑔 𝑒𝑟𝑟𝑜𝑟

The following is the trace of learning the algorithm on the string “1 + 2 ∗ 3” using the above parsing table:

Stack Input Action

E 1+2*3$ Parse E→ME’
E’M 1+2*3$ Parse M→AM’
E’M’A 1+2*3$ Parse A→num
E’M’num 1+2*3$ Advance input
E’M’ +2*3$ Parse M’→e
E’ +2*3$ Parse E’→+ME’
E’M+ +2*3$ Advance input
E’M 2*3$ Parse M→AM’
E’M’A 2*3$ Parse A→num
E’M’num 2*3$ Advance input
E’M’ *3$ Parse M’→*AM’
E’M’A* *3$ Advance input
E’M’A 3$ Parse A→num
E’M’num 3$ Advance input
E’M’ $ Parse M’→e
E’ $ Parse E’→e
$ Accept

Note: Both the stack and the input contains an end symbol $ to denote that the stack is empty and the input is
consumed

Compiler Construction ~ Wainaina Page 9 of 9