[antlr-interest] Predicate hoisting pain

[Sam Barnett-Cormack]

Sam Harwell wrote:
> 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!
>  ;

The problem here is that the usage of the two isn't distinguishable at a
useful point. elementSetSpecs and objectSetSpec know which they want,
but then converge for a whole series of rules (handling set arithmetic)
and diverge again at elements.

> High speed solution B, recommended if you can disambiguate the first
> two rules with short lookahead.

Which two rules? Short lookahead isn't usually doable in this language, 
as most constructions allow arbitrary nesting.

> 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! ;

I'm not sure how a well-crafted AST would be possible if the treewalker 
has to cope with potentially seeing a valueSet where it's expecting an 
objectSet - especially as they can look pretty similar. Without 
predicating, that elements declaration is ambiguous in a big way (this 
is presumably the "first two" you spoke of above). Either of them can 
potentially contain more valueSets, and objectSetElements can contain 
other objectSets - like I said, arbitrary nesting.

> 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! ;

And that's just horrible and leads to a horribly structured parser. *sigh*

I guess the question really is, for me, why does it get hoisted in one 
case and not another? I'm assuming it's because of the choice in the 
objectSetSpec rule, and I can't see any way to refactor that to lose the 
choice. Of course, there's probably a kludgy solution of setting a 
variable os to true and passing it...

Sam

> -----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