(c) S
SaSaSaSbS
S
SaSaSbSaS
S
SaSbSaSaS
S
SbSaSaSaS
S
→
→
→
→
→ ∈
Ì Exam ple 2.2.11: Given a grammar G with production rules
S
aB
S
bA
A aS
A bAA
A a
B
bS
B
aBB
B
b
→
→
→
→
→
→
→
→
Obtain the (i) leftmost derivation, and (ii) rightmost derivation for the
string “aaabbabbba”.
Solu tion
(i) Leftmost derivation:
S
aB
aaBB
aaaBBB
aaabBB
aaabbB
aaabbabB
aaabbabbB
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒ aaabbabbbS
aaabbabbba
aaabbabb
⇒
⇒
(ii) Rightmost der i va tion:
S
aB
aaBB
aaBbS
aaBbbA aaaBBbba
aaabBbba aaabbSbba
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
aaabbaBbba aaabbabbba
2.3 PARSING AND AMBIGUITY
2.3.1 Parsing
A grammar can be used in two ways:
(a) Using the grammar to generate strings of the language.
(b) Using the grammar to recognize the strings.
“Parsing” a string is finding a derivation (or a derivation tree) for that
string.
Parsing a string is like recognizing a string. The only realistic way to
recognize a string of a context-free grammar is to parse it.
Con text-free Grammars
127