[antlr-interest] the nihilistic circle hoist

Ron Burk ronburk at gmail.com
Sun Jan 2 23:35:22 PST 2011

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

The predicate used in the previous examples is "{true}",
which I believe satisfies all possible constraints one
could imagine. :-) And yet the result is still absolutely
incorrect parsers.

There is an ANTLR slideshow that declares hoisted
predicates must only be executed in the correct syntactic
context. The second example was intended to demonstrate that
they may, in fact, execute completely outside the correct
syntactic context. I see no constraints that can be placed
on predicates that will avoid the bugs that behavior can

Previously, I said:
> The previous observation suggests that "hoisting"
> should only be extended to nonterminals that can
> actually derive a string that starts with the nonterminal
> containing the predicate being hoisted.

Which I can now see is not a complete characterization
of the problem.

Working through an LL(1) example implementing
predicates on the classic Yacc-is-LR(2) problem
(treat IDENT ':' different than IDENT) makes me understand
why the downward hoisting is motivated. The problem is
being able to reach those downward-hoisted predicates
via a path that does not involve the nonterminal that
contained the predicate. I don't yet see any reason that
should be defined as correct behavior for hoisting
(how to explain to the hapless user that syntactic
behavior has been altered by a predicate that exists
nowhere in the syntax being altered?), and
suspect it is fixable.

It's an interesting problem.

More information about the antlr-interest mailing list