[antlr-interest] Predicate hoisting pain
Sam Barnett-Cormack
s.barnett-cormack at lancaster.ac.uk
Mon Apr 13 05:48:27 PDT 2009
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
More information about the antlr-interest
mailing list