2.3.2 Exhaus tive Search Parsing
The basic idea of the “Exhaustive Search Parsing” is to parse a string w,
generate all strings in L and check if w is among them.
Problem arises when L is an infinite language. Therefore a systematic
approach is needed to achieve this, as it is required to know that no strings are
overlooked. And also it is necessary so as to stop after a finite number of steps.
The idea of exhaustive search parsing for a string is to generate all strings
of length no greater than | w |, and see if w is among them.
The restrictions that are placed on the grammar will allow us to generate
any string w L
∈ in at most 2 | w | – 1 derivation steps.
Exhaustive search parsing is inefficient. It requires time exponential in | |
w.
There are ways to further restrict context free grammar so that strings may
be parsed in linear or non-linear time (which methods are beyond the scope of
this book).
There is no known linear or non-linear algorithm for parsing strings of a
general context free grammar.
2.3.3 Top down/Bottomup Parsing
Sequence of rules are applied in a leftmost derivation in Topdown parsing.
(Refer to section 2.2.4.)
Sequence of rules are applied in a rightmost derivation in Bottomup
parsing.
This is illustrated below.
Consider the grammar G with production
1
2
.
.
.
S
aSS
S
b
→
→
The parse trees are as follows.
aababbb → Left parse of the string with the sequence 1121222.
This is known as “Topdown Parsing.”
128
Theory of Automata, Formal Languages and Computation
a
S
S
S
a
S
S
b
a
S
S
b
b
b
Fig. Top down pars ing.
The basic idea of the “Exhaustive Search Parsing” is to parse a string w,
generate all strings in L and check if w is among them.
Problem arises when L is an infinite language. Therefore a systematic
approach is needed to achieve this, as it is required to know that no strings are
overlooked. And also it is necessary so as to stop after a finite number of steps.
The idea of exhaustive search parsing for a string is to generate all strings
of length no greater than | w |, and see if w is among them.
The restrictions that are placed on the grammar will allow us to generate
any string w L
∈ in at most 2 | w | – 1 derivation steps.
Exhaustive search parsing is inefficient. It requires time exponential in | |
w.
There are ways to further restrict context free grammar so that strings may
be parsed in linear or non-linear time (which methods are beyond the scope of
this book).
There is no known linear or non-linear algorithm for parsing strings of a
general context free grammar.
2.3.3 Top down/Bottomup Parsing
Sequence of rules are applied in a leftmost derivation in Topdown parsing.
(Refer to section 2.2.4.)
Sequence of rules are applied in a rightmost derivation in Bottomup
parsing.
This is illustrated below.
Consider the grammar G with production
1
2
.
.
.
S
aSS
S
b
→
→
The parse trees are as follows.
aababbb → Left parse of the string with the sequence 1121222.
This is known as “Topdown Parsing.”
128
Theory of Automata, Formal Languages and Computation
a
S
S
S
a
S
S
b
a
S
S
b
b
b
Fig. Top down pars ing.