[antlr-interest] greedy vs nongreedy lexer rules

kferrio at gmail.com kferrio at gmail.com
Sun Apr 18 15:17:54 PDT 2010


I do not understand what I perceive between the lines as reticence toward lexer states.  Perhaps states seem "clunky" to some folks.  States are elegant -- or at least clean -- to me, provided the state stack frames are strictly scoped by design.   If communication across frames is allowed via anything but globals I can imagine chaos.  

 And although the non-greedy loop is an annoying use case, I think it is rare enough that your high standard for elegance could be relaxed a bit.

Kyle 

Sent from my Verizon Wireless BlackBerry

-----Original Message-----
From: Terence Parr <parrt at cs.usfca.edu>
Date: Sun, 18 Apr 2010 14:29:02 
To: antlr-interest interest<antlr-interest at antlr.org>
Subject: Re: [antlr-interest] greedy vs nongreedy lexer rules


On Apr 18, 2010, at 2:02 PM, Terence Parr wrote:
>  More importantly, I'm approximating recursive lexer rules with a DFA and then will invoke the recursive method at runtime after I've distinguished the input from other rules.  What I mean is that, I really kind of need to build a DFA :)

Hmm...if we allow a stack of lexical states ("modes") then we don't need recursive lexer rules, which I rarely use anyway.  Here's how we could do nested comments:

ID : ... ;
INT : ... ; // usual stuff 
CMT_START : '/*' {pushMode(COMMENTS);} ;

mode COMMENTS:

NESTED_CMT_START : '/*' {pushMode(COMMENTS);} ;
CMT_STOP : '*/' {popMode();} ;
ANY : . ;

That's not as "cool" as this though:

ID : ... ;
INT : ... ; // usual stuff 
CMT : '/*' (CMT | .)* '*/' ;

That said, my current thoughts on impl would match CMT approximately and then rewind to call the generated CMT method and exec it as if it were a parser rule.  Less efficient.  Worse, if approx predicted two recursive methods, I'd have to try both with backtracking...hmm...so maybe we really should avoid recursive lexer rules in favor of states, which handles nongreedy situations and recursion.

Ter



List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address


More information about the antlr-interest mailing list