“Right Parse” is the reversal of sequence of rules applied in a rightmost
derivation.
aababbb → Right parse of the string with the sequence 2221121.
This is known as “Bottom-up Parsing.”
2.3.4 Ambi gu ity
The grammar given by
G
S a b S S
aSb bSa SS
=
→
({ }, { , }, ,
|
|
| )
λ
generates strings having an equal number of a’s and b’s.
The string “abab” can be generated from this grammar in two distinct
ways, as shown in the following derivation trees:
Similarly, “abab” has two distinct leftmost derivations:
S
aSb abSab abab
S
SS
aSbS
abS
abaSb abab
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
.
Also, “abab” has two distinct rightmost derivations:
S
aSb abSab abab
S
SS
SaSb Sab aSbab abab
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
Each of the above derivation trees can be turned into a unique rightmost
derivation, or into a unique leftmost derivation. Each leftmost or rightmost
derivation can be turned into a unique derivation tree. These representations
are largely interchangeable.
Con text-free Grammars
129
S
S
S
b
S
a
a
a
b
b
b
S
S
S
Fig. Bot tom-up pars ing.
a
S
b
b
S
a
S
λ
S
S
S
a
b
S
λ
a
b
S
λ