programming-languagesgrammarcontext-free-grammarlanguage-theory

Given grammar ambiguous or not?

Consider the grammar below...

bexp -> bterm | bterm ‘||’ bexp
bterm -> bfact | bfact ‘&&’ bterm
bfact -> true | false | id | ‘(‘ bexp ‘)’

Suppose we extend BEXP with the '!' operator for negation by changing the bfact rule as follows:-

bfact -> true | false | id | '(' bexp ')' | '!' bexp

Lets call this extended grammar BEXP2. How can I prove that it is ambiguous?

Solution

  • You can prove that it is ambiguous by finding a string with two parses :)

    In this case, try !id&&id. Is that (!id)&&id or !(id&&id)