April 2002 Draft
Tuesday, October 9, 2001
This proposal uses the following conventions to denote literal characters:
Printable ASCII literal characters (values 20 through 7E hexadecimal) are in a
blue monospaced font. Other
characters are denoted by enclosing their four-digit hexadecimal Unicode value between
». For example, the non-breakable space character would be denoted in this
«u00A0». A few of the common control characters are represented
A space character is denoted in this document either by a blank space where it’s obvious from the context or by
where the space might be confused with some other notation.
Each LR(1) syntactic grammar and lexical grammar rule consists of a nonterminal, a , and one or more expansions of the nonterminal separated by vertical bars (|). The expansions are usually listed on separate lines but may be listed on the same line if they are short. An empty expansion is denoted as «empty».
Consider the sample rule:
This rule states that the nonterminal SampleList can represent one of four kinds of sequences of input tokens:
...followed by some expansion of the nonterminal Identifier;
...and an expansion of the nonterminal Identifier.
Input tokens are characters (and the special End placeholder) in the lexical
grammar and lexer tokens in the syntactic grammar. Input tokens to be typed literally
are in a
bold blue monospaced font. Spaces separate input tokens and nonterminals from
each other. An input token that consists of a space character is denoted as
Other non-ASCII or non-printable characters are denoted by also using
as described in the character notation section.
If the phrase “[lookahead set]” appears in the expansion of a production, it indicates that the production may not be used if the immediately following input terminal is a member of the given set. That set can be written as a list of terminals enclosed in curly braces. For convenience, set can also be written as a nonterminal, in which case it represents the set of all terminals to which that nonterminal could expand.
For example, given the rules
matches either the letter
n followed by one or more decimal digits the first of which is even, or a decimal
digit not followed by another decimal digit.
These lookahead constraints do not make the grammars more theoretically powerful than LR(1), but they do allow these grammars to be written more simply. The semantic engine compiles grammars with lookahead constraints into parse tables that have the same format as those produced from ordinary LR(1) or LALR(1) grammars.
If the phrase “[no line break]” appears in the expansion of a production, it indicates that this production cannot be used if there is a line break following the last terminal matched by the grammar. Line break constraints are only present in the syntactic grammar.
Many rules in the grammars occur in groups of analogous rules. Rather than list them individually, these groups have been summarized using the shorthand illustrated by the example below:
Metadefinitions such as
introduce grammar arguments and . If these arguments later parametrize the nonterminal on the left side of a rule, that rule is implicitly replicated into a set of rules in each of which a grammar argument is consistently substituted by one of its variants. For example, the sample rule
expands into the following four rules:
AssignmentExpressionnormal,allowIn is now an unparametrized nonterminal and processed normally by the grammar.
Some of the expanded rules (such as the fourth one in the example above) may be unreachable from the grammar’s starting nonterminal; these are ignored.
A few lexical rules have too many expansions to be practically listed. These are specified by descriptive text instead of a list of expansions after the .
Some lexical rules contain the metaword except. These rules match any expansion that is listed before the except
but that does not match any expansion after the except. All of these rules ultimately expand into single characters.
For example, the rule below matches any single UnicodeCharacter except the
Last modified Tuesday, October 9, 2001