Search code examples
grammarcontext-free-grammar

Make a context free grammar not ambiguous

I have a test this week. There is the following grammar for Boolean statements:

B -> B and B | not B | (B) | id

B is a non terminal, and the terminals are: and, not, (, ), id

This grammar is ambiguous. I need to re-write it and create an equivalent grammar which is not ambiguous and without left recursion, such that not is in high precedence, 'and' is associative to the left.

I have tried to do it by myself: my beginning was: 

B -> not B' | ( B' | id B'

but I think this is wrong and I am really stuck for a long time.

Solution

  • Using more non-terminals allows setting precedence on all operators (I hope I'm getting the notation you're using right).

    This is to get right-to-left associativity for and: id and id and id is parsed as id and [id and id]

    B -> NotExpr | NotExpr and B
NotExpr -> PrimaryExpr | not NotExpr
PrimaryExpr -> id | (B)

    This is to get left-to-right associativity for and: id and id and id is parsed as [id and id] and id

    B -> NotExpr | B and NotExpr
NotExpr -> PrimaryExpr | not NotExpr
PrimaryExpr -> id | (B)