6.2. The Grammar

For some time now, we've been implementing BNF syntax equations for arithmetic expressions, without ever actually writing them down all in one place. It's time that we did so. They are:

<expression> ::= <unary op> <term> [<addop> <term>]*
<term>       ::= <factor> [<mulop> factor]*
<factor>     ::= <integer> | <variable> | ( <expression> )

Note

Remember, the nice thing about this grammar is that it enforces the operator precedence hierarchy that we normally expect for algebra.

Actually, while we're on the subject, I'd like to amend this grammar a bit right now. The way we've handled the unary minus is a bit awkward. I've found that it's better to write the grammar this way:

<expression>    ::= <term> [<addop> <term>]*
<term>          ::= <signed factor> [<mulop> factor]*
<signed factor> ::= [<addop>] <factor>
<factor>        ::= <integer> | <variable> | (<expression>)

This puts the job of handling the unary minus onto Factor, which is where it really belongs.

This doesn't mean that you have to go back and recode the programs you've already written, although you're free to do so if you like. But I will be using the new syntax from now on.

Now, it probably won't come as a shock to you to learn that we can define an analogous grammar for Boolean algebra. A typical set or rules is:

<b-expression>::= <b-term> [<orop> <b-term>]*
<b-term>      ::= <not-factor> [AND <not-factor>]*
<not-factor>  ::= [NOT] <b-factor>
<b-factor>    ::= <b-literal> | <b-variable> | (<b-expression>)

Notice that in this grammar, the operator AND is analogous to *, and OR (and exclusive OR) to +. The NOT operator is analogous to a unary minus. This hierarchy is not absolutely standard … some languages, notably Ada, treat all logical operators as having the same precedence level … but it seems natural.

Notice also the slight difference between the way the NOT and the unary minus are handled. In algebra, the unary minus is considered to go with the whole term, and so never appears but once in a given term. So an expression like

a * -b

or worse yet,

a - -b

is not allowed. In Boolean algebra, though, the expression

a AND NOT b

makes perfect sense, and the syntax shown allows for that.