CODEWITHSUNDEEP
grammarcontext-free-grammar
CnR
CnR

Reputation: 371

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.

Upvotes: 2

Views: 508

Answers (2)

Ghislain Fourny
Ghislain Fourny

Reputation: 7279

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)

Upvotes: 2

maxik
maxik

Reputation: 1123

Another approach could be the following (after edit, thanks @Peter):

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

Upvotes: 0

Related Questions