[antlr-interest] Predicate hoisting pain

Sam Harwell sharwell at pixelminegames.com
Mon Apr 13 04:57:40 PDT 2009


Hoisting is a very difficult problem. Until I finish my new spec for
implementing reliable hoisting, I suggest one of the following:

High speed solution A, used as appropriate:

elementsTrue
   : objectSetElements
   | LPAREN! elementSetSpecTrue RPAREN!
   ;

elementsFalse
   : subtypeElements
   | LPAREN! elementSetSpecFalse RPAREN!
   ;

High speed solution B, recommended if you can disambiguate the first two
rules with short lookahead. For this method, you build the AST based on
whatever the user entered, and provide an error message during
post-parse semantic analysis if the user entered the wrong item for a
given context. Relaxing the parser/deferring semantic checks to the tree
walker(s) often leads to a grammar with shorter lookahead, fewer DFA
tables, improved ability to provide meaningful error messages, and
significantly improved performance. Remember that a carefully crafted
AST will allow an LL(1) tree walker without predicates.

elements
   : subtypeElements
   | objectSetElements
   | LPAREN! elementSetSpec RPAREN!
   ;

Low speed solution, using full synpreds wherever you use 'elements'
((elements[true])? => elements[true]):

elements[boolean os]
   : subtypeElements {!$os}?
   | objectSetElements {$os}?
   | LPAREN! elementSetSpec[$os] RPAREN!
   ;

-----Original Message-----
From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Sam
Barnett-Cormack
Sent: Monday, April 13, 2009 6:33 AM
To: ANTLR Interest Mailing List
Subject: [antlr-interest] Predicate hoisting pain

Hi all,

So, in my grammar I have need to re-use rules so they ultimately refer 
to a different rule (so I don't have to duplicate 
intersection/union/exception rules). I use a parameter and gated 
predicates, like so:

elements[boolean os]
   : {!$os}?=>subtypeElements
   | {$os}?=>objectSetElements
   | LPAREN! elementSetSpec[$os] RPAREN!
   ;

This is ultimately referred to from two places. The first, which 
generates code that's just fine, is:

elementSetSpecs
   : rootElementSetSpec[false] (COMMA EXTMARK (COMMA 
additionalElementSetSpec[false])?)?
   -> ^(ELEMENTSET rootElementSetSpec EXTMARK?
additionalElementSetSpec?)
   ;

However, in the *slightly* more complex case:

objectSetSpec
   : rootElementSetSpec[true] (COMMA EXTMARK 
additionalElementSetSpec[true]?)?
   | EXTMARK (COMMA additionalElementSetSpec[true])?
   ;

The predicates get hoisted in the generated code, and then there's 
compile errors with undefined variable 'os'.

I'm not sure why it happens in one case and not the other, and I'm even 
less clear on how to fix it. Can anyone help?

Sam

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