All geek questions in one place

BNF Grammar Ambiguity

I recently thought about the next BNF

A -> x | yA | yAzA where x,y,z are terminals.

I am sure that this grammar is ambiguous, but how to make it unambiguous?

+4
source share
1 answer

Grammar is ambiguous if a particular line can have more than one parsing tree. In your language, the yyxzx string can have one of these two parsing trees:

  AA / \ /|\`\ y A y A z A /|\`\ / \ \ y A z A y A x | | | xxx

Therefore, the grammar is ambiguous.

This is actually equivalent to the notorious "if / then / else" ambiguity in languages ​​like C, where y=if , z=else and x=statement . http://en.wikipedia.org/wiki/Dangling_else . I would recommend checking this page for ideas on how to get around this problem.

+5
source

Source: https://habr.com/ru/post/1395986/

More articles:


All Articles