Package step2

Step 2: Precedence, Associativity, and Iterative Constructs.

See:
Description

Class Summary

dummy

fake class, triggers javadoc.

Package step2 Description

Step 2: Precedence, Associativity, and Iterative Constructs.

• Precedence and Associativity
• Inline Precedence Specification
• Optional and Iterative Constructs
• Summary

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 pj input file:

%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 directives enable 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

if.pj in 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 1

This 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 jay 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: ...

pj supports 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.

Summary

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 jay. This is very useful because pj can also insert rules for a very robust recovery from input errors within iterations.