|PREV PACKAGE NEXT PACKAGE||FRAMES NO FRAMES|
|dummy||fake class, triggers javadoc.|
Step 2: Precedence, Associativity, and Iterative Constructs.
Precedence and Associativity
Separate rules were used in
step 1 to define
operator precedence, and left-recursive specifications arranged
for the operators to be left-associative. badexpr.pj illustrates what
happens if the rules are specified less carefully:
$ java -jar pj.jar -jay badexpr.pj >/dev/null
jay: 35 shift/reduce conflicts.
jay is completely confused because there is only a
single rule which is left- and right-recursive. However, in spite
of the multitude of conflicts, this grammar is actually preferable
because it allows
jay to generate a more compact recognition program.
Precedence and associativity can be specified through explicit
directives which precede the rules section of a
%left '+' '-' %left '*' '/' '%' %% expr: expr '+' expr | ...A directive starts with a special symbol at the beginning of a line. %left introduces one or more operators that are left-associative and have equal precedence. Similarly there is a directive %right for right-associative operators such as assignment or exponentiation, and %nonassoc for operators such as comparisons that may not be chained. Successive directives have increasing precedence.
Once the directives are included in expr.pj the conflicts are no longer reported:
$ java -jar pj.jar -jay expr.pj >/dev/null
It should be noted that the conflicts are still there. The
jay to deal with the grammar in a useful
fashion, but the grammar designer has to be quite sure that the
directives work as intended. Generally the directives are only
used in the context of expressions where a precedence and
associativity table has an intuitive meaning.
Inline Precedence Specification
step 1 demonstrated the shift/reduce conflict associated with the
dangling else problem:
$ java -jar pj.jar -jay -verbose if.pj >/dev/null
jay: 1 shift/reduce conflict.
betterif.pj shows how to hide this conflict with precedence directives:
$ java -jar pj.jar -jay -verbose betterif.pj >/dev/null
Searching y.output shows that the precedence directives arrange for the proper sequence of reductions:
state 7 statement : __if condition __then statement . (1) statement : __if condition __then statement . __else statement (2) __else shift 8 $end reduce 1This solution is possible because there are two input symbols, then and else which can be ordered by precedence directives:
%nonassoc "then" %nonassoc "else"Even if there are no convenient symbols, the technique can still be used because a precedence clause can be directly attached to a rule. precif.pj does not require then as an input symbol:
$ java -jar pj.jar -jay -verbose precif.pj >/dev/null
This time y.output contains the proper sequence of reductions in state 6. [Thanks to B. Alliet and P. Lorenz who inspired this example.]
Optional and Iterative Constructs
expr.pj is a typical grammar for lines with arithmetic expressions:
%% program: line*; line: expr? '\n'; expr: ...A program consists of zero or more lines. A line may or may not contain an expr and it is terminated with a newline character.
jay cannot deal with optional and iterative constructs
directly. The input file which
pj creates for
can be obtained:
$ java -jar pj.jar expr.pj
A closer look reveals that
pj adds additional rules
for these constructs:
%% program: lines; lines: // zero or more | lines line; line: opt_expr '\n'; opt_expr: // optional | expr; expr: ...
pjsupports one optional and three iterative constructs where in each case name can refer to a terminal or a non-terminal:
|name ?||specifies that name appears at most once.|
|name *||specifies that name appears zero or more times.|
|name +||specifies that name appears one or more times.|
|name / item||specifies that name appears one or more times, separated by a (non-iterative) item such as a literal symbol.|
These constructs have to be used with care. In particular, nesting optional items is likely to cause problems, as many.pj illustrates:
$ java -jar pj.jar -jay -verbose many.pj >/dev/null
jay: 1 shift/reduce conflict, 1 reduce/reduce conflict.
y.output documents that the conflicts are caused by nesting an optional item into a sequence of zero or more items:
%% no: "no" optId*; // causes 1 s/r and 1 r/r conflict optId: Id?;
many.pj also exercises several other iterative constructs.
Grammars can often be simplified by using a table of directives
to declare increasing precedence and associativity (left,
right, and nonassoc) and then specifying fewer and
more compact rules which
jay would otherwise consider
loaded with shift/reduce conflicts.
pj supports notations for optional and iterative constructs
and implicitly translates them into pure BNF rules for
This is very useful because
pj can also insert rules for
a very robust recovery from input errors within iterations.
|PREV PACKAGE NEXT PACKAGE||FRAMES NO FRAMES|