[antlr-interest] Re: another nondeterminism question

Adrian Sandor aditsu at yahoo.com
Wed Jul 23 19:21:53 PDT 2003


--- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> [...] 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);}
>    ;
>
> [...]
> Test it out and let me know if there are other inputs that fail.

this one works, thanks a lot :)

> [...] the following should work:
> 
> S: {LA(2)=='b'}?
>     ('a' | {LA(2)=='b'}?"bb")+ 
>    | 'b' {$setType(B);}
>    ;

sorry, this one doesn't work.. maybe I'll try to fix it

also see my next message

Adrian

> -----Original Message-----
> From: Adrian Sandor [mailto:aditsu at y...] 
> 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/


 

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




More information about the antlr-interest mailing list