Backus–Naur form with boolean algebra. Problem with brackets and parse tree

Question

boolean algebra

I want to write those boolean expression in Backus-Naur-Form.

What I have got is:

< variable > ::= < signal > | < operator> | < bracket >< variable>

< signal> ::= <p> | <q> | <r>| <s>

< operator> ::= <AND> | <OR> | <implication>| <equivalence>| <NOT>

< bracket> ::= < ( > | < ) >

I made a rekursion with < bracket >< variable>, so that whenever there is a bracket it starts a new instance, but I still do not know when to close the brackets. With this you are able to set a closing bracket and make a new instance, but I only want that for opening brackets.

Can I seperate < bracket> in < open bracket> and < closing bracket>? Is my Backus-Naur form even correct? There isn't much information about Backus-Naur form with boolean algebra on the internet. How does the parse tree of this look like?

Answer 1

I assume that you want to define a grammar for boolean expressions using the Backus-Naur form, and that your examples are concrete instances of such expressions. There are multiple problems with your grammar:

First of all, you want your grammar to only generate correct boolean expressions. With your grammar, you could generate a simple operator ∨ as valid expression using the path <variable> -> <operator> -> <OR>, which is clearly wrong since the operator is missing its operands. In other words, ∨ on its own cannot be a correct boolean expression. Various other incorrect expressions can be derived with your grammar. For the same reason, the opening and closing brackets should appear together somewhere within a production rule, since you want to ensure that every opening bracket has a closing bracket. Putting them in separate production rules might destroy that guarantee, depending on the overall structure of your grammar.

Secondly, you want to differentiate between non-terminal symbols (the ones that are refined by production rules, i.e. the ones written between < and >) and terminal symbols (atomic symbols like your variables p, q, r and s). Hence, your non-terminal symbols <p>, <q>, <r> and <s> should be terminal symbols p, q, r and s. Same goes for other symbols like brackets and operators.

Thirdly, in order to get an unambiguous parse tree, you want to get your precedence and associativity of your operators correct, i.e., you want to make sure that, for example, negation is evaluated before implication, since it has a higher precedence (similar to arithmetic expressions where multiplication must be evaluated before addition). In other words, we want operators with higher precedence to appear closer to the leaf nodes of the parse tree, and operators with lower precedence to appear closer to the root node of the tree, since the leaves of the tree are evaluated first. We can achieve that by defining our grammar in a way that reflects the precedences of the operators in a decreasing manner:

<expression>  ::= <expression>  ↔ <implication> | <implication>
<implication> ::= <implication> → <disjunction> | <disjunction>
<disjunction> ::= <disjunction> ∨ <conjunction> | <conjunction>
<conjunction> ::= <conjunction> ∧ <negation>    | <negation>
<negation>    ::= ¬ <negation> | <variable> | ( <expression> )
<variable>    ::= p | q | r | s

Starting with <expression>, we can see that a valid boolean expression starts with chaining all the ↔ operators together, then all the → operators , then all the ∨ operators, and so on, according to their precedence. Hence, operators with lower precedence (e.g., ↔) are located near the root of the tree, where operators with higher precedence (e.g., ¬) are located near the leaves of the tree.

Note that the grammar above is left-recursive, which might cause some problems with software tools that cannot handle them (e.g., parser generators).