HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Grammar for describing boolean expressions with AND, OR and NOT

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
booleanwithexpressionsdescribinggrammarforandnot

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#10558, answer score: 4

Revisions (0)

No revisions yet.