27 March 2000 Release 2.22 Notes for New Users of PCCTS Version 1.33MR22
29
hoisting of the predicate in rule cb.
A first effort to solve this problem is to rewrite rule c so as to place "cb" on the left edge of the production:
c : () /* c1 */
| ca {cb} /* c2 */
| cb /* c3 */
; /* c4 */
The code generated for rule c now resembles:
if (LA(1)==ID) { /* d1 */
; /* d2 */
} else if (LA(1)==ID && pa(...)) { /* d3 */
... /* d4 */
It is clear that rules ca and cb are now unreachable because any ID will always match the test at line d1. In fact, this
will cause an error message because
PCCTS
is able to recognize the problem. The order of alternatives should be
changed to:
c : ca {cb} /* e1 */
| cb /* e2 */
| () /* e3 */
; /* e4 */
However our problems aren't over yet. The code generate for the "(...)*" test in rule "a" resembles:
while ( (LA(1)==X || LA(1)==Eol || LA(1)==ID) && /* f1 */
(pa(...) || pb(...))) { /* f2 */
... /* f3 */
If both pa and pb are false then the body of the rule is never entered even though it should match an X or and ID
using the rule on line a2 when rule c derives epsilon.
This can be fixed by using the
ANTLR
"-mrhoist on" option which suppresses the test for pa and pb in rule "a"
because ID is a viable alternative. See Item #140.
Contributed by Sigurdur Asgeirsson (sigurasg@menandmice.com).
#140. Example of predicate hoisting and suppression with the
ANTLR
option -mrhoist on
Consider the following grammar fragment:
a : bc /* 2 */
| d /* 3 */
; /* 4 */
bc : b /* 5 */
| c /* 6 */
; /* 7 */
b : <<pb(LT(1))>>? ID ; /* 8 */
c : ID ; /* 9 */
d : <<pd(LT(1))>>? ID ; /* 10 */
With no predicate context computation (-prc off) the generated code for rule "a" resembles:
if (LA(1)==ID && pb) {
bc();
} else if (LA(1)==ID && pd) {
d();
} ...
The code for the first alternative is incorrect because c (and therefore bc) is still a viable choice when pb is false.
With the default predicate context computation (-prc on) the generated code for rule "a" resembles:
if (LA(1)==ID && ((! LA(1)==ID) || pb)) {
bc();
} else if (LA(1)==ID && ((! LA(1)==ID) || pd)) {
d();
} ...
This is more complex, but a close look at the code shows that this is no better than the code generated by -prc off.