[antlr-interest] Re: another nondeterminism question

Wed Jul 23 08:50:44 PDT 2003

I also couldn't figure out how to get this to work with syntactic predicates
because of ANTLR's linear approximation.  So, basically I had to do full
LL(k) analysis by hand and put it into semantic predicates.  For this simple
example it wasn't too hard.  

S: {LA(1)=='a'||(LA(1)=='b' && (LA(2)=='b'))}?
    ('a' | {LA(1)=='b' && (LA(2)=='b')}?"bb")+ 
   | 'b' {$setType(B);}
   ;

output:
S: a
B: b
S: a

Test it out and let me know if there are other inputs that fail.

Look at the generated code and note that semantic predicates are preceded by
the lookahead for that alternative.  Because of that the following should
work:

S: {LA(2)=='b'}?
    ('a' | {LA(2)=='b'}?"bb")+ 
   | 'b' {$setType(B);}
   ;

However I prefer the other as being more clear.  The compiler should be
optimizing the tests so there is no performance penalty.

Monty

-----Original Message-----
From: Adrian Sandor [mailto:aditsu at yahoo.com] 
Sent: Tuesday, July 22, 2003 3:10 PM
To: antlr-interest at yahoogroups.com
Subject: [antlr-interest] Re: another nondeterminism question

--- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> Argh.  Could you summarize your different attempts so I can try
them out and
> see what is happening?

I'll try, but maybe I can't remember them exactly

first, the common part (excluding the S, A, B rules):

---8<---
class l1 extends Lexer;
NL: '\r'|'\n';

class p1 extends Parser;
start: (s|b)+ NL;
s: x:S{System.out.println("S: "+x.getText());};
b: x:B{System.out.println("B: "+x.getText());};
--->8---

you can try them all with k=1 and k=2
also the input I tried is the same: aba

Attempt 1:

protected A: 'a' | "bb";
B: 'b';
S: (A)+;

results:
nondeterminism; exception: line 1:3: expecting 'b', found 'a'

Attempt 2:

protected A: 'a' | ("bb")=>"bb" | 'b'{$setType(B);};
S: (A)+;

results:
S: aba

Attempt 3:

protected A: 'a' | {LA(2)=='b'}? "bb" | {LA(2)!='b'}? 'b'{$setType (B);};
S: (A)+;

results:
S: aba

Attempt 4:

protected A: 'a' | {LA(2)=='b'}? "bb";
B: {LA(2)!='b'}? 'b';
S: (A)+;

results:
exception: line 1:2: unexpected char: 'b'

Attempt 5:

protected A: 'a' | "bb" | ('b' ~('b'))=>'b'{$setType(B);};
S: (A)+;

results:
nondeterminism; exception: line 1:3: expecting 'b', found 'a'

Attempt 6:

protected A: 'a' | BB;
B: ("bb")=>"bb"{$setType(BB);} | {LA(2)!='b'}? 'b';
protected BB: "bb";
S: (A)+;

results:
nondeterminism; exception: line 1:3: expecting 'b', found 'a'

Attempt 7:

S: ('a' | "bb")=>('a' | "bb")+ | 'b' {$setType(B);};

results:
exception: line 1:3: expecting 'b', found 'a'

Attempt 8:

S: ('a' | "bb")=>(('a')=>'a' | ("bb")=>"bb")+ | 'b' {$setType(B);};

results:
exception: line 1:3: expecting 'b', found 'a'

Attempt 9:

S: ('a'|("bb")=>"bb")+ | 'b'{$setType(B);};

results:
nondeterminism; exception: line 1:3: expecting 'b', found 'a'

Attempt 10:

S: ('a' | "bb")=>(('a')=>'a' | ("bb")=>"bb")+ | 'b' {$setType(B);};

results:
exception: line 1:3: expecting 'b', found 'a'

argh.. I'm tired, 10 should be enough
let me know if you find any solution

thanks
Adrian

> -----Original Message-----
> From: Adrian Sandor [mailto:aditsu at y...]
> Sent: Saturday, July 19, 2003 5:53 AM
> To: antlr-interest at yahoogroups.com
> Subject: [antlr-interest] Re: another nondeterminism question
> 
> 
> the problem is that the new syn preds make NO difference
> I compared the generated lexers (java source code) and besides a
renamed
> counter variable, they're identical
> 
> my initial approach was something like this:
> 
> class l1 extends Lexer;
> protected A: 'a' | ("bb")=>"bb" | 'b'{$setType(B);};
> S: (A)+;
> 
> but it also fails because when the lexer matches a single 'b'
inside the S,
> it doesn't care that it has a different type and continues the loop
> 
> I'm wondering if antlr is simply unable to generate a lexer for
this "too
> complicated" language
> 
> Adrian
> 
> --- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> > Ack.  Apparently we need a syn pred in the loop as well!  Try
some 
> > variations of this and inspect the generated code to make sure it
is
> working
> > correctly.  Ignore the warning about superfluous syn preds if one
> comes up.
> > 
> > class l1 extends Lexer;
> > S: ('a' | "bb")=>(('a')=>'a' | ("bb")=>"bb")+ | 'b' {$setType
(B);};
> > 
> > Monty
> > 
> > -----Original Message-----
> > From: Adrian Sandor [mailto:aditsu at y...]
> > Sent: Wednesday, July 16, 2003 10:14 PM
> > To: antlr-interest at yahoogroups.com
> > Subject: [antlr-interest] Re: another nondeterminism question
> > 
> > 
> > 
> > well, everything is ok... except that once the lexer starts 
> > recognizing an S, it fails to detect a B:
> > 
> > the grammar:
> > ---8<---
> > class l1 extends Lexer;
> > S: ('a' | "bb")=>('a' | "bb")+ | 'b' {$setType(B);};
> > 
> > class p1 extends Parser;
> > start: (S|B)+;
> > --->8---
> > 
> > input data: aba
> > result: exception: line 1:3: expecting 'b', found 'a'
> > 
> > this is still ok for the "//" comments in my grammar, but it's
not ok
> > in other cases, like Sanjiv's message
> > http://groups.yahoo.com/group/antlr-interest/message/8965
> > 
> > I'm going to read about that linear approximation thing...
> > 
> > Adrian
> > 
> > --- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> > > In fact you may need a syntactic predicate because of the linear 
> > > approximation issue:
> > > 
> > > 
> > > S: ('a'|"bb")=>('a' | "bb")+
> > >    | 'b' {$setType(B);}
> > >    ;
> > > 
> > > Let me know, I don't have time to try it out right now.
> > > 
> > > Monty
> > > -----Original Message-----
> > > From: mzukowski at y... [mailto:mzukowski at y...]
> > > Sent: Wednesday, July 16, 2003 11:46 AM
> > > To: antlr-interest at yahoogroups.com
> > > Subject: RE: [antlr-interest] Re: another nondeterminism
question
> > > 
> > > 
> > > OK, this is an linear approximation issue.  If you had A:"aa"
> > | "bb" things
> > > would work.  This example is very abstract.  I would code it
like
> > this:
> > > 
> > > S: ('a' | "bb")+
> > >    | 'b' {$setType(B);}
> > >    ;
> > > 
> > > Look up linear approximation in the FAQ & archives.
> > > 
> > > Monty
> > > -----Original Message-----
> > > From: Adrian Sandor [mailto:aditsu at y...]
> > > Sent: Wednesday, July 16, 2003 11:26 AM
> > > To: antlr-interest at yahoogroups.com
> > > Subject: [antlr-interest] Re: another nondeterminism question
> > > 
> > > 
> > > ok, I tried with the following grammar:
> > > 
> > > class l1 extends Lexer;
> > > options{k=2;}
> > > protected A: 'a' | "bb";
> > > B: 'b';
> > > S: (A)=>(A)+;
> > > 
> > > and I got:
> > > 
> > > ANTLR Parser Generator   Version 2.7.2   1989-2003 jGuru.com
> > > t1.g: warning:lexical nondeterminism between rules B and S upon
> > > t1.g:     k==1:'b'
> > > t1.g:     k==2:<end-of-token>
> > > t1.g:5: warning:Syntactic predicate ignored for single
alternative
> > > 
> > > 
> > > Adrian
> > > 
> > > --- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> > > > That's a weird bug you ran into, I think.  It should give
warnings
> > > in both
> > > > cases.  You could solve this with a syntactic predicate:
> > > > 
> > > > S: (A)=>(A)+;
> > > > 
> > > > -----Original Message-----
> > > > From: Adrian Sandor [mailto:aditsu at y...]
> > > > Sent: Friday, July 11, 2003 9:54 AM
> > > > To: antlr-interest at yahoogroups.com
> > > > Subject: [antlr-interest] another nondeterminism question
> > > > 
> > > > 
> > > > why do I get a nondeterminism warning for this grammar:
> > > > 
> > > > class l1 extends Lexer;
> > > > options{k=2;}
> > > > protected A: 'a' | "bb";
> > > > B: 'b';
> > > > S: (A)+;
> > > > 
> > > > but I don't get any warning when I change S to:
> > > > 
> > > > S: A (A)+;
> > > > 
> > > > and how can I solve it for the first case?
> > > > I tried many things but to no avail...
> > > > 
> > > > thanks
> > > > Adrian
> 
> 
>  
> 
> Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 