9. What is a partial derivation tree?
In the definition of derivation tree given, if every leaf has a label
from V T
∪ ∪ { }
λ then it is said to be a partial derivation tree.
10. What do you mean by Topdown Parsing?
The sequence of rules being applied in the leftmost derivation is
referred to as Topdown Parsing.
11. What is meant by bottomup Parsing?
Sequence of rules applied in a rightmost derivation is referred to as
bottom-up parsing.
12. What is an ambiguous grammar?
A CFG is said to be ambiguous if there exists at least one string in the
language of the CFG which is ambiguously derivable. Otherwise it is
unambiguous.
13. What is meant by a useless production?
A production which does not affect a language is called a useless
production.
14. What is an Unit Production?
Any production of a CFG of the form A B
→ where A B V
, ∈ is
called a Unit Production.
15. What do you mean by exhaustive search parsing?
To parse a string w, that generates all strings in L and check if w is
among them is called exhaustive search parsing.
16. Give the formal definition of an ambiguous CFG.
Let G
N T P S
= ( , , , ) be a CFG. A string w L G
∈ ( ) is said to be
“ambiguously derivable” if there are two or more different derivation
trees for that string in G.
17. What is an inherantly ambiguous language?
A language for which no unambiguous grammar exists, is called an
inherantly ambiguous language.
18. Give examples for ambiguous grammars.
(a) A CFG which has the production rules
S
SbS S
a
→
→
,
is ambig u ous.
(b) A CFG which has the production rules
S
a aAb abSb A aAAb bS
→
→
|
|
,
| is ambig u ous.
19. What do you mean by substitution rule?
A production A x Bx
→ 1 2 can be eliminated from a grammar if we
put in its place the set of productions in which B is replaced by all strings
it derives in one step. In this result, it is essential that A and B are
different variables.
Con text-free Grammars
155