Actually, even backtracking does not solve this. The problem is apparently as you noted Jim resolving standalone vs embedded expr2. In standalone expr2 following SUFFIX has to be consumed unconditionally whereas in embedded expr2 it has to be consumed only if followed by yet another SUFFIX. To resolve between the 2 cases though procedure for expr2 needs to look back, not forward, so it does not matter how far ahead it looks. I guess this is what ultimately makes the grammar not LL - with LL parser expr2 has to be handled in a context dependent way even though the grammar as such is context free. LALR should be able to solve this I think by shifting long enough to figure out what to do before making a reduction.
Regards Nikolay Jim Idle wrote: > David-Sarah Hopwood wrote: >>> >>> Because at the time it is in expr2, it is ambiguous as to whether it >>> should match PREFIX_2 and exit, or match PREFIX_2 SUFFIX and then exit. >>> >> >> Yes. >> >> >>> You only have 1 token of lookahead (by default). >>> >> >> That's not right. The value of k is normally determined automatically >> per rule (if not overridden). The problem here is that the grammar is >> ambiguous *as an LL(k) grammar* for any k. Although ANTLR supports >> backtracking (which makes it more powerful than LL(k)), that's not >> enabled by default, and so is not taken into account by the ambiguity >> warning. >> >> For example, consider input starting with "prefix_1 prefix_2 suffix". >> A non-backtracking LL(k) parser must predict and commit to a particular >> alternative of expr2 by looking only at tokens that would be part of that >> alternative, here either "prefix_2" or "prefix_2 suffix". It will never >> look further ahead than that, regardless of k. >> >> The default of not enabling backtracking is the right default, since the >> ambiguity warnings are more conservative and more likely to help in >> finding grammar errors. (To me this is more important than the loss >> of efficiency that can result from backtracking.) In this case, the >> left-factoring suggested by Jim Idle is a better solution than enabling >> backtracking, even though the latter would handle this particular >> grammar automatically. >> >> > But, you must remember that once you use backtracking, you lose the > inherent ability of LL parsers to pin-point the locale of errors > accurately. Hence backtracking is only good for prototypes, or > situations where you expect the input to be syntactically sound (you > are transforming otherwise good code and so on). > > Jim > > ------------------------------------------------------------------------ > > > List: http://www.antlr.org/mailman/listinfo/antlr-interest > Unsubscribe: > http://www.antlr.org/mailman/options/antlr-interest/your-email-address > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "il-antlr-interest" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/il-antlr-interest?hl=en -~----------~----~----~----~------~----~------~--~---
List: http://www.antlr.org/mailman/listinfo/antlr-interest Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
