ambiguous grammar

In computer science, a grammar is an ambiguous grammar if some string in the language can be generated in more than one way (i.e., it has more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars. For programming languages, ambiguous grammars can lead to difficulties for some compilers.

Example

The context free grammar

A → A + A | A − A | a

is ambiguous since there are two leftmost derivations for the string a + a − a:

A	→ A + A	\|	A	→ A − A
	→ a + A	\|		→ A + A − A
	→ a + A − A	\|		→ a + A − A
	→ a + a − A	\|		→ a + a − A
	→ a + a − a	\|		→ a + a − a

Equivalently, it is ambiguous since there are two parse trees for the string a + a − a:

References

Programming Languages: Design and Implementation, T. Pratt, M. Zelkowitz. Prentice Hall, 2001

<< Previous

Word Browser

Next >>

asian brown flycatcher
hans werner henze
ricky j
allegheny portage railroad
cheng
robert reed (author)
jack watson
microbrowser
sherman adams
clean water act
middle binyang cave

kashmir flycatcher
yungang grottoes
delta 4
prince sattva
icebreaker lenin
marlon fletcher
slade gorton
fredro starr
hms poictiers
cathedral of st. george (saskatoon)
data general business basic

master of divinity
little juniata river
longmen
hms frolic
flesh and blood
henri cole
irving stone
kenitra
kirk jones
dragon: the bruce lee story
united states women's national soccer team

canadian association of journalists
hidden stream temple cave
richard simpkin
palmer's penstemon
mallet
suave sonny caeser
new york observer
tyler yates
shinzo maeda
roger trinquier
shirokiya