0

I have made a grammar for boolean and arithmetic expressions. I want to handle arithmetic expressions like:

(1+5)+(-3)

I'm done with that work: I can handle all the expressions I want.

My problem is that a boolean expression can be something like:

( ( (2+2==4) or (3>2) ) and 2==2)

so at some point my boolean rules have to refer to my arithmetic expression rules. I can't use parentheses () in my boolean rules because it'll cause my grammar to be ambiguous. I understand why but I can't figure out a solution for this problem.

Anderson Green
  • 30,230
  • 67
  • 195
  • 328
Jorge Silva
  • 225
  • 1
  • 3
  • 10
  • What have you tried so far? Show your code and provide details of the conflicts that yacc identifies. – David Gorsline Mar 25 '13 at 14:33
  • There is nothing inherently ambiguous in having parenthesis in both boolean and arithmetic expressions (the simple ways of doing it will make the grammar not-LL, but are just fine with LR). What have you tried? – Chris Dodd Jun 17 '14 at 04:45
  • possible duplicate of [Simple ambiguous grammer with reduce-reduce conflict](http://stackoverflow.com/questions/12887072/simple-ambiguous-grammer-with-reduce-reduce-conflict) – Chris Dodd Jun 17 '14 at 06:01

1 Answers1

1

This LALR grammar written for GOLD should get you started:

<Formula>     ::= <BoolConcat> <Formula> | <BoolConcat> 

<BoolConcat> ::= <BoolConcat> 'and' <Comparison> | <Comparison>

<Comparison> ::=  <Comparison> '>' <Expression> | <Expression> 

<Expression> ::= <Expression> '+' <Term> | <Term>

<Term> ::= <Term> '*' <Fact> | <Fact>

<Fact> ::= Integer | '(' <BoolConcat> ')'

For the bool part the typical concepts for arithmetic grammar are reused. Nothing new, only new levels of precedence for the different kinds of bool operators.

Just add '==' to Comparison, 'or' to BoolConcat and so on.

user764754
  • 3,865
  • 2
  • 39
  • 55