[antlr-interest] the nihilistic circle hoist

[Sam Harwell]

When a semantic predicate is involved with decision making in a grammar, the
following rules should be considered absolute:

1. The predicate cannot access any argument to any rule.
2. The predicate cannot access any variables declared within an @init{}
block of any rule.
3. The predicate cannot access any member of any attribute scope in the
grammar.

In addition, semantic predicates should be pure in the sense that they do
not introduce changes to the program state under any circumstance.

Semantic predicates may safely do the following:

1. Access immutable variables declared within the @members{} section of the
grammar. If the rule foo is the entry point to your grammar, then any
variable "x" which is used by a semantic predicate should be initialized
before foo() is entered, and should remain unchanged until foo() completes.
2. Call input.la(n) and input.lt(n).

Finally, like the "backtrack" grammar option, you should do whatever is
necessary to remove semantic predicates from a production grammar as they
introduce a significant performance penalty. As an example, consider the
following example from a grammar I wrote. My language allows function
declarations of the form "function modifier* returnType? functionName",
where modifiers are effectively user-configured keywords in this context.
Originally, I had the following:

functionDefinition : 'function' ({IsFunctionModifier(input.LT(1))}? =>
mods+=IDENTIFIER)* retType=IDENTIFIER? functionBody
    -> ^('function' ^(MODS $mods*) retType? functionBody);

I now use the following:

functionDefinition : 'function' mods+=IDENTIFIER* functionBody
    -> ^('function' ^(MODS {ExtractFunctionModifiers($mods)})
{ExtractFunctionReturnType($mods)} functionBody);

The methods ExtractFunctionModifiers and ExtractFunctionReturnType each
return a CommonTree. ExtractFunctionModifiers returns a tree with a nil()
root and any number of children which are the actual modifiers. If
ExtractFunctionReturnType returns null, the node is not included in the
rewrite tree, so this works for cases where the return type is omitted.

Sam

-----Original Message-----
From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Ron Burk
Sent: Friday, December 31, 2010 11:14 PM
To: antlr-interest at antlr.org
Subject: Re: [antlr-interest] the nihilistic circle hoist

More fun with predicate hoisting:

grammar Simple;

FOO : 'foo' ;

section : element* unrelated EOF ;
element : {P1}?=> pre;
pre : FOO post ;
post : FOO*;
unrelated : ':' post;

In this grammar, the generated code invokes P1 (completely outside its
intended syntactic context) while trying to recognize an "unrelated"
(because P1 was "hoisted downward" into "post", and "post" is reachable via
a nonterminal unrelated to "element").

List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe:
http://www.antlr.org/mailman/options/antlr-interest/your-email-address