Boolean Expression Grammar

Question

Write a grammar for Boolean expressions , assuming that we already have rules in our grammar for arithmetic expressions . Arithmetic expressions might be simple literals like 3 or 97 or may be more complex syntactic units like (3+x)/4. They evaluate to a number. You needn’t concern yourself with their structure; just that they can be used as below.

Boolean expressions include the literals TRUE and FALSE; they can be combined with the unary operator ! (meaning NOT) and binary operators && and || (meaning AND and OR). Also, arithmetic expressions can be combined with the following binary operators to form new Boolean expressions: ==, <, >, <=, >=, !=.

When your grammar is complete, you should be able to derive parse trees for expressions like the following:

• TRUE || FALSE

• FALSE && !TRUE

• 27<32 || x != 15

To get you started, here’s a preliminary rule: → TRUE | FALSE

Answer 1

I am assuming a non-terminal ArithmeticExpression,

and defining BooleanExpression.

Literal -> TRUE |

FALSE

Relation -> ArithmeticExpression == ArithmeticExpression |

ArithmeticExpression < ArithmeticExpression |

ArithmeticExpression > ArithmeticExpression |

ArithmeticExpression <= ArithmeticExpression |

ArithmeticExpression >= ArithmeticExpression |

ArithmeticExpression != ArithmeticExpression

Primary -> Literal |

Relation |

!Primary |

(BooleanExpression)

Term -> Primary |

Term && Primary

BooleanExpression -> Term |

BooleanExpression || Term

Note:

This grammar provides the usual precedence of Boolean operators.

This grammar is unusual in that it does not allow Boolean variables; the teacher did not mention them.