[antlr-interest] Grammar does not match a valid sentence

[Harald M. Müller]

Edson - 
 
I looked into your grammar and played with it a little ... that language is
more or less a horror story.
 
Essentially, you can say things like
    a == 5 && c != 6
but also
    a == 5 && != 6
(without the c) and then there are operators that may be names, so you can
say
    a == 5 && c 6
(meaning probably a == 5 && a c 6, where c is some user-defined operator);
and then you can have those brackets as in
    a[3] == 5 && b[3] == 6
but an operator can ALSO have brackets, so you can have
    a[3] == 5 && b[3] 6
(meaning probably a[3] == 5 && a b[3] 6 - whatever the operator b[3] is
meant to be ...) as well as
    a[3] == 5 && b[3] c[2] 6
where now the b[3] is a path and c[2] is the operator.
 
The grammar tries to find a way thru this by having { backtracking=true; }
options in it - but I fear that hte graphs of the LL(*) analysis and the {
backtracking=true; } don't always work the way they are supposed to: Either
because ANTLR simply won't be able to do everything, or because there is
some tiny flaw in the grammar so that there's really no way to parse some of
the constructs.
When you remove the { backtracking=true; } around line 85 (I edited the file
a few times, so that number may be off), ANTLR tells you
 
    error(211): DRL2.g:88:3: [fatal] rule and_restr_connective has non-LL(*)
decision due to recursive rule invocations reachable from alts 1,2.  Resolve
by left-factoring or using syntactic predicates or using backtrack=true
option.
    warning(200): DRL2.g:88:3: Decision can match input such as
"DOUBLE_AMPER LEFT_PAREN {LEFT_PAREN, NOT, '=='..'!='}" using multiple
alternatives: 1, 2
    As a result, alternative(s) 2 were disabled for that input
 
Now, this definitely is a horrible thing - a grammar that is "not at all
LL(*)." ...
 
I would argue that the only way to "repiar" this machinery is to have only
one level of nested expressions, so that eg. DOUBLE_AMPER is only at one
place in the grammar. The core rule for a simple expression might be
something like
 
    simpleexpression:    path? operator value
 
where path is defined in some LL(k) (or LL(*) way) so that it is possible to
decide whether there is path. One step further, one could try
 
    simpleexpression
        : (path)=> path operator value
        | operator value
        ;
 
But I may also be wrong with these suggestions ... only having the full
thing set up will show what's going on.
 
Regards & good luck
Harald


  _____  

From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Edson Tirelli
Sent: Monday, December 03, 2007 1:53 PM
To: antlr-interest at antlr.org
Cc: Mark Proctor; Michael Neale
Subject: [antlr-interest] Grammar does not match a valid sentence



     All,

     I have a grammar that is not matching a valid sentence and I don't
understand exactly why. If anyone can shed some light, I would really
appreciate.
     To see the problem:

Using: antlr v3.0 and antlrworks 1.1.4:

1. Load the attached grammar in antlrworks 
2. Select the interpreter tab and paste the following sentence:

Address( street[1] == "Low" && street[2] == "High" ) 

3. Use the rule "fact" as an entry point to parse the sentence above.

     The above sentence is a valid sentence, but it is raising a
NoViableAltException in the "and_restr_connective" rule, while the expected
behavior is not to match "and_restr_connective", but go back in the call
hierarchy and to match the "and_constr" rule. 
     If you remove the square brackets, the sentence will work fine
(matching the "and_constr" rule):

Address( street1 == "Low" && street2 == "High" )

     Any idea how can I fix that?
     Thanks in advance,

     []s
     Edson

-- 
  Edson Tirelli
  JBoss Drools Core Development
  Office: +55 11 3529-6000
  Mobile: +55 11 9287-5646
  JBoss, a division of Red Hat @ www.jboss.com 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20071203/43d5f1fb/attachment.html