[antlr-interest] grammar for boolean expressions

[Kevin J. Cummings]

On 04/11/2011 06:47 PM, poroshpathor poroshpathor wrote:
> Hello,
> 
> I am trying to build  grammar rules for the following boolean expression.
> E1 AND E2 AND E3 AND ... AND En
> Here, E1, E2,...,En could consist boolean expressions of both OR and AND
> I have started with this 
> 
> 
> expression
> : or_relationalExpression ( AND^ or_relationalExpression)*
> ;
> 
> or_relationalExpression
> : relationalExpression (OR^ | AND^ relationalExpression )* 

I'm not sure about your intent here, did you mean to write:
  : relationExpression ((OR^ | AND^) relationalExpression )*
???

If so, you have a problem of the parser not knowing which rule to handle
when it sees an AND.  Is it a part of an or_relational expression?  Or
is it a part of an expression?  Your grammar is ambiguous.

If not, then your grammar allows an OR token with no rhs and a single
child (which doesn't seem useful to me).

Usually, the definition provides a precedence between AND and OR (with
AND bind more tightly than OR).  Most languages would parse:

	A AND B OR C AND D OR E

as
	(A AND B) OR (C AND D) OR E

Your definition (as I read it, and assuming no AND in the 2nd rule)
would parse as

	A AND (B OR C) AND (D OR E)

but the AND in your second rule is still your problem.  You have to
eliminate it if you want your parser to be deterministic.

> ;
> 
> But, as expected, it causes problems of following format
> Any idea to solve or rewrite the grammar rules??
> 
> Thanks in advance.
> 
> 
> [fatal] rule or_relationalExpression has non-LL(*) decision due to recursive 
> rule invocations reachable from alts 2,3.  Resolve by left-factoring or using 
> syntactic predicates or using backtrack=true option.
>  |---> : relationalExpression (OR^ | AND^ relationalExpression )*
> 
> warning(200): /CarFast/src/ConditionsGrammar.g:55:58: Decision can match input 
> *** using multiple alternatives: 2, 3 As a result, alternative(s) 3 were 
> disabled for that input
>  |---> : relationalExpression (OR^ | AND^ relationalExpression )*
> 
> 
> 
>       
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address


-- 
Kevin J. Cummings
kjchome at verizon.net
cummings at kjchome.homeip.net
cummings at kjc386.framingham.ma.us
Registered Linux User #1232 (http://counter.li.org)