Implementation of a context-free grammar for logical operators with parentheses

Question

I'm trying to implement a context-free grammar for the language of logical operators with parentheses including operator precedence.

For example, the follows:

{1} or {2}
{1} and {2} or {3}
({1} or {2}) and {3}
not {1} and ({2} or {3})
...

I've started from the following grammar:

expr := control | expr and expr | expr or expr | not expr | (expr)
control := {d+}

To implement operator precedence and eliminate left recursion, I changed it in the following way:

S ::= expr
expr ::= control or expr1 | expr1
expr1 ::= control and expr2 | expr2
expr2 ::= not expr3 | expr3
expr3 ::= (expr) | expr | control
control := {d+}

But such grammar doesn't support examples like: ({1} or {2}) and {3} that contain 'and' / 'or' after parentheses.

For now, I have the following grammar:

S ::= expr
expr ::= control or expr1 | expr1
expr1 ::= control and expr2 | expr2
expr2 ::= not expr3 | expr3
expr3 ::= (expr) | (expr) expr4 | expr | control
expr4 :: = and expr | or expr
control := {d+}

Is this grammar correct? Can it be simplified in some way?

Thanks!

Answer 1

To implement your operator precedence, you want just:

S ::= expr
expr ::= expr or expr1 | expr1
expr1 ::= expr1 and expr2 | expr2
expr2 ::= not expr2 | expr3
expr3 ::= (expr) | control
control := {d+}

This is left-recursive in order to be left-associative, as that's generally what you want (both for correctness and most parser-generators), but if you need to avoid left recursion for some reason, you can use a right-recursive, right associative grammar:

S ::= expr
expr ::= expr1 or expr | expr1
expr1 ::= expr2 and expr1 | expr2
expr2 ::= not expr2 | expr3
expr3 ::= (expr) | control
control := {d+}

as both and and or are associative operators, so left-vs-right doesn't matter.

In both cases, you can "simplify" it by folding expr3 and control into expr2:

expr2 ::= not expr2 | ( expr ) | {d+}