# Grammar for describing boolean expressions with AND, OR and NOT

I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR an NOT only. This, as can be seen, also reflects the precedence of the operators (ie., 'AND' is done before 'OR', etc).

Is it correct?

    1.  E   ::=  T E’
2.  E’  ::= OR T E’
3.  E’  ::=  ε
4.  T   ::=  F T’
5.  T’  ::= AND F T’
6.  T’  ::= ε
7.  F   ::= NF'
8.  N   ::= NOT
9.  N   ::= ε
10.  F'  ::= (E)
11.  F'  ::= id

• Have you tried proving correctness? – Raphael Mar 17 '13 at 18:07
• what is NF' line 7? it seems not to be further defined or a typo? do you really mean N F'? what is id line 11? it would be helpful if you gave a verbal description/motivation/bkg/sketch of the logic... proving correctness is done via induction for these types of problems... – vzn Apr 20 '13 at 18:38

It is an almost copy of the grammar Wirth gives for arithmetic expressions in "Algorithms + data structures = programs" (as far as I can remember it; I might be wrong with the source, though). So I strongly believe it is correct.

Write the corresponding recursive descent parser, and try it on some correct strings, and some badly built ones. Get somebody else, without coaching on your part, come up with examples and broken cases. Also generate some random combinations to try.

Here is an EBNF grammar with precedence of operators enforced.

$\text{exp} \to \text{term } \{ \text{OR term}\};$

$\text{term} \to \text{factor } \{\text{AND factor}\};$

$\text{factor} \to \text{id};$

$\text{factor} \to \text{NOT factor};$

$\text{factor} \to \text{LPAREN exp RPAREN};$

TRUE and FALSE are id's. Try this online tool to check your grammar.

• +1 for online tool link – mvw Oct 12 '18 at 9:23