27 March 2000 Release 2.22 Notes for New Users of PCCTS Version 1.33MR22
10
IF e2 THEN IF e1 THEN s1 ELSE ...
where the underline identifies an inner if_stmt from item 1.
This is not terribly clear, so let's review the data and try to understand what the ambiguity aid is trying to say. When
we are ready to recognize the ELSE there must be two plausible derivations for the ELSE token. The first one is the
obvious one: the ELSE is part of the if_stmt being parsed. The second choice, the difficult one, arises when there is
no
ELSE clause for an if_stmt. Looking at
IF e2 THEN IF e1 THEN s1 ELSE ...
with this hint and some thought we should be able to recognize that the ELSE can be interpreted as part of the
underlined statement (choice 1) or as part of the non-underlined statement (choice 2).
I admit that this is far from ideal. However, I have found this an immense aid in trying to identify the source of an
ambiguity in large grammars which may require dozens of rules to be examined in order to discover that rule g can
follow rule f when rule f appears at the end of e, when e appears at the end of d, etc.
#55. Example with cast expression
This example illustrates the use of the -aad option which controls the number of lookahead tokens to match. The
ambiguity aid first reports on the choices which match just one token, then on the choices which match the second
token, and so on until the number of tokens specified by the -aad option is reached.
This ambiguity in this example is simple to diagnose without any aid, but I think it has educational value.
expr1 : expr2 { EQ_EQ expr2 } ; /* 1 */
expr2 : expr3 ( ADD_OP expr3 )* ; /* 2 */
expr3 : expr4 ( MUL_OP expr4 )* ; /* 3 */
expr4 : expr5 /* 4 */
| LP Id RP expr5 /* 5 */
; /* 6 */
expr5 : Id /* 7 */
| Number /* 8 */
| LP expr1 RP /* 9 */
; /* 10 */
When run with -ck 2
ANTLR
reports:
paren.g(4) : warning: alts 1 and 2 of the rule itself
ambiguous upon { LP }, { Id }
To diagnose this problem we use the command:
antlr paren.g -ck 2 -aa 4 -aad 2 #
ambiguity on line 4, match two tokens
The output is:
Ambiguity Aid (-ck 2 -aa 4 -aad 2)
Choice 1: expr4/1 line 4 file paren.g
Choice 2: expr4/2 line 5 file paren.g
The ambiguity is a choice between line 4 (expr5) and line 5 (LP Id RP ...)
Intersection of lookahead[1] sets:
LP
Intersection of lookahead[2] sets:
Id
Choice:1 Depth:1 Group:1 (LP)
The first choice at depth 1 starts at line 4 (item 1) and flows into expr5 (items 1 and
2). Once inside expr5 (item 2) we find the token LP (item 3).
1 to expr5 expr4/1 line 4 paren.g
2 expr5 expr5/1 line 7 paren.g
3 #token LP expr5/3 line 9 paren.g