CHAPTER 4

Question 1

What does it mean for a grammar to be ambiguous?

Answer 1

A grammar is ambiguous if there exists at least one string in its language that has two or more different parse trees.

Question 2

What does it mean for two grammars to be equivalent?

Answer 2

Two grammars
𝐺
1
G
1
​
and
𝐺
2

​
are equivalent if they generate the same language
𝐿
(
𝐺
1
)
=
𝐿
(
𝐺
2
)
L(G
1
​
)=L(G
2
​
).

Question 3

11. What is “left factoring”?

Answer 3

A transformation used to eliminate common prefixes to make a grammar suitable for LL parsing.

Question 4

What is “left recursion”?

Answer 4

A grammar has left recursion if a nonterminal calls itself as the first symbol in its production.

Question 5

Can LL(k) parsing algorithms handle common prefixes and left recursion?

Answer 5

LL(k) cannot handle left recursion (must eliminate it).
LL(k) struggles with common prefixes, but left factoring fixes this.

Question 6

Can LR(k) parsing algorithms handle common prefixes and left recursion?

Answer 6

LR(k) parsers can handle left recursion naturally (no need for transformation).
LR(k) can also handle common prefixes without modification.