[antlr-interest] Trouble with nondeterminism

[John Gruenenfelder]

On Tue, Aug 29, 2006 at 01:21:08PM +0200, Ric Klaren wrote:
>>
>>Is that a "good" method for dealing with this problem?
>
>It works... but for every invocation of the constant rule it will for
>the first alternative read input untill ( ('0'..'9')+ '.') => .. is
>satisfied or failed. In the succes case it will rollback the input and
>enter the first alternative. In the failed case it will attempt to
>match the '.' for the 2nd alternative if that does not work it will
>try the predicate ( ('0'..'9')+ ('e' | 'E')) => .. read input untill
>the predicate fails or succeeds. If it succeeds it will roll back the
>input and enter the alternative. If it fails it will rollback the
>input and enter the last alternative.
>
>=> introduces a trial and error run of the input (or backtracking).
>E.g. it's very expensive in terms of efficiency. In terms of
>readability or speed of implementing it's pretty efficient ;)

Ohhh... it's like a bright light just went on in my head.  :)
This explanation really clears predicates up very nicely.  I definitely get it
now.

>The other solution to this problem is to left factor the rule:
>
>Constant:
>  { $setType(INT); /* int untill proven otherwise */ }
>  ('0' | ( '1'..'9' ('0'..'9')* ))
>  (
>        (  '.' ('0'..'9')* (Exponent)? )
>        { $setType(DOUBLE); }
>     |  Exponent
>        { $setType(DOUBLE); }
>  )?
>  |   '.' ('0'..'9')+ (Exponent)?
>     { $setType(DOUBLE); }
>  ;
>
>This should do the trick I think (unless I made a type/thinko)
>
>Left factoring usually leads to less readable code. But it's a lot
>faster. In a lexer you'd want to try to have no => constructs. But
>during prototyping it's quite handy.

And this example clears up the other half of my confusion.

Many thanks for taking the time to explain this.  It really has been a huge
help in my understanding of ANTLR and its method of operation.


-- 
--John Gruenenfelder    Research Assistant, UMass Amherst student
                        Systems Manager, MKS Imaging Technology, LLC.
Try Weasel Reader for PalmOS  --  http://gutenpalm.sf.net
"This is the most fun I've had without being drenched in the blood
of my enemies!"
        --Sam of Sam & Max