[antlr-interest] Semantic Predicates Depending On Rule Results

Zachary Palmer zep_antlr at bahj.com
Sat Oct 23 19:01:08 PDT 2010


All,

I have a bit of a challenging problem at hand.  I've been using ANTLR 
quite successfully for a language development project on which I have 
been working for about a year now.  We are using an ANTLR grammar to 
build the AST for the language from source.  Due to the requirement that 
our AST nodes be heterogeneously typed and constructed via a particular 
factory, we are not using output=AST; we are instead having each rule 
return the type of AST node it generates a la the Java.g grammar found 
on the ANTLRv3 site.

We've recently introduced a new language construct with rather peculiar 
needs.  When the parser is created, it is provided with a typechecker.  
The new grammar rule for the language looks like the following (sans 
actions and predicates):

     '~:' expression ':~'

Whenever this rule (termed "splice") is invoked, it receives an expected 
type for the expression.  The ANTLR grammar rule should only match this 
production if it matches syntactically *and* the typechecker indicates 
that the expression has the type provided as input to the splice rule.  
The idea is that this rule can then be used as follows:

     ident returns [IdentNode ret]:
         splice[Type.IDENT] { $ret = factory.makeIdentNode($splice.ret); }
         | IDENTIFIER { $ret = factory.makeIdentNode($IDENTIFIER.text); }
         ;

     name returns [NameNode ret]:
         splice[Type.NAME] { $ret = factory.makeNameNode($splice.ret); }
         | a=ident { $ret = factory.makeNameNode($a.ret); }
         ('.' b=ident { $ret = factory.makeNameNode($b.ret, $ret); })*
         ;

This means that we can decide which AST to use based on the type of the 
provided expression.  For the code

     ~: stuff :~

we produce a different tree based on whether "stuff" typechecks as a 
NAME or an IDENT.

The following definition of the splice rule comes very close to what I want:

     splice[Type expectedType] returns [SpliceNode ret] :
         '~:' { this.spliceTypechecker != null }?
         expression
         ':~' { 
this.spliceTypechecker.typecheck($expression.ret).equals(expectedType) }
         { $ret = factory.makeSpliceNode($expression.ret); }
         ;

Sadly, I have to turn off the "memoize" option or the first try to parse 
splice will fail and the failure will be memoized.  I'd be okay with 
that for the time being (as I have an approaching deadline) except that 
it still doesn't work.  The problem appears to be that the backtracking 
step that determines whether or not splicing is viable here does not 
actually execute the actions I have attached to this grammar.  As a 
result, the "expression" nonterminal parses an expression but does not 
fill any values into $ret.  The typechecker is therefore asked to 
typecheck null, which always results in the semantic predicate failing.

The problem seems to lie with the fact that I have a semantic predicate 
that relies on the return value of a rule to function correctly.  I 
can't just hack this together by checking the predicate in an action of 
my own (thereby deferring the predicate until after backtracking 
analysis) because then backtracking will pick the wrong path.  I 
absolutely must predicate based on the AST node which is produced from 
the expression nonterminal.  Does anyone have any suggestions?

I've been quite impressed with ANTLR thus far and we've invested a fair 
amount of work in creating this grammar.  Between that and the 
aforementioned deadline, I'd really like to convince ANTLR to do this 
job for me.  And thanks for reading this far.  :)

My appreciations,

Zachary Palmer


More information about the antlr-interest mailing list