7.1.3.3 Alternatives ¶

Use ‘|’ to separate alternative expressions. On transferring control to a set of alternative expressions, a parser filters alternative expressions with FIRST sets containing a look-ahead terminal symbol and selects one of filtered expressions.

Example

S: [ "a" "b" ] .    // 1st
 | [ "b" "c" ] . .  // 2nd
 | "c" . . .        // 3rd
;

On the look-ahead terminal symbol "a", a parser selects the first expression. On the look-ahead terminal symbol "b", a parser selects the first or second expression. On the look-ahead terminal symbol "c", a parser selects the second or third expression. Processing every expression begins with consuming a just analyzed look-ahead terminal symbol.

In the above example, the selection of an alternative on the look-ahead terminal symbol "a" is deterministic, and the selection of an alternative on the look-ahead terminal symbol "b" or "c" is nondeterministic.

Note: in a bottom-up template grammar, the parser may select an alternative based on subsequent terminal symbols in a parse unit or training terminal symbol sequence rather than analyze the first look-ahead terminal symbol only.

As a result of iterative determinization, a parser removes terminal symbols from overlapping terminal symbol classes defining FIRST sets of the alternatives but preserves a set of terminal symbols in the union of the FIRST sets.

A parser can determinize the production from the above example in the following ways:

S: "a" .
 | "b" . .
 | "c" . . .
;

or

S: [ "a" "b" ] .
 | "c" . . .
;

or

S: "a" .
 | [ "b" "c" ] . .
;

On nondeterministic choice, a parser selects each applicable alternative with equal profile probability. Use a notation

[RelativeProbability]

at the beginning of an alternative to specify its custom relative profile probability. Examples: [2], [1.5], [0.25].

Note: in the general case, using precise default or custom profile probabilities requires calling a parser with the option --profile-tol=FLOAT where FLOAT is small enough.

If at least one alternative begins with a relative profile probability specification, all other alternatives must begin with relative profile probability specifications too.

Example

S: [0.50] [ "a" "b" ] .
 | [0.25] [ "b" "c" ] . .
 | [0.25] "c" . . .
;

An expression quantified by ‘?’

( EXPRESSION )?

is equivalent to

( | EXPRESSION )

If an expression is not inside ‘(’ … ‘)’, the quantifier ‘?’ after the expression relates to its last element. For example, in the expression ‘. . A B?’ the quantifier ‘?’ relates only to ‘B’.

Note: if the quantifier ‘?’ follows a sequence of input terminal symbols, terminal symbol placeholders, and terminal symbol classes, a quantified expression is the entire sequence rather than its last element. For example, the notation ‘. . [ "a" "Beta" ]?’ means that the quantified expression is ‘. . [ "a" "Beta" ]’. To relate ‘?’ only to [ "a" "Beta" ], use the notation ‘. . ([ "a" "Beta" ]?)’ or ‘. . ([ "a" "Beta" ])?’.

If the FIRST set of an EXPRESSION and the FIRST set of a location just after a construct ‘( EXPRESSION )?’ or ‘( | EXPRESSION )’ overlap, avoid using the construct to prevent unstable determinization. Instead, use the construct

( #su0 .~ | EXPRESSION )

See Switching Spur Update Mode, for the description of #su0 specifier.

Note: this construct (without #su0) has a different meaning in a bottom-up template grammar.