Question

I am trying to construct a CFG for a boolean operator NAND.. This is what I have so far:

boolexp --> boolexp NAND boolexp
boolexp --> (boolexp)
boolexp --> True | False

The problem is when the input is something like "False NAND False NAND (True NAND True)"

This is clearly ambiguous, since there can be 2 different parse trees depending on the derivation.

How do I remove this ambiguity and redesign my CFG??

I want the NAND operator to be left-associative.. That is, if the input is A nand B nand C, I want it to be (A nand B) nand C

No correct solution

OTHER TIPS

You can do the following

boolexp --> boolexp NAND boolterm
boolexp --> boolterm
boolterm --> (boolexp)
boolterm --> True | False

In case of a NAND b NAND c you get the only derivation

boolexp(a NAND b) NAND boolterm(c)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top