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
S
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
c
However, the parse tree does not match 𝑎𝑏; the parser backtracks and tries the alternative 𝐴 → 𝑒 as shown
below:
S
a b A
e
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
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
S
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
c
However, the parse tree does not match 𝑎𝑏; the parser backtracks and tries the alternative 𝐴 → 𝑒 as shown
below:
S
a b A
e
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
