CODEWITHSUNDEEP
parsingcompiler-constructiongrammar
Stephen Hynes
Stephen Hynes

Reputation: 23389

Check grammar ambiguity

The following is the extract of a piece of grammar that I'm trying to see whether it is ambiguous or not. 

Y->b
Y->Z
Z->bW
W->d
W->ϵ

When I compute the first set of the grammar I stumble upon this irregularity for first of Y.

First(Y) = {b,First(Z)}
First of Z = b so I have the set First(Y)={b,b}.

What I want to know is that sufficient enough to prove that the grammar given this evidence is ambigious or not. Or should the set be First(Y) = {b}.

Upvotes: 1

Views: 4648

Answers (1)

Rubens
Rubens

Reputation: 14778

To prove a grammar is ambiguous, you simply need to prove that there's at least two different ways to reach a result.

Considering your example, and considering your edit, you do have an ambiguous grammar, since you're be able to derive the expression b by:

Y -> b
Y -> Z
Z -> bW
Y -> d
W -> ϵ

First way:

Y -> b

Second way:

Y -> Z
Y -> Z -> bW
Y -> Z -> bW -> bϵ
Y -> Z -> bW -> bϵ -> b

This is an ambiguous grammar.

Upvotes: 5

Related Questions