ML-Yacc is a parser generator for Standard ML modeled after the
Yacc parser generator. It generates parsers for LALR languages, like Yacc,
and has a similar syntax. The generated parsers use a different algorithm
for recovering from syntax errors than parsers generated by Yacc.
The algorithm is a partial implementation of an algorithm described in [1].
A parser tries to recover from a syntax error
by making a single token insertion, deletion, or
substitution near the point in the input stream at which the error
was detected. The parsers delay the evaluation of semantic actions until
parses are completed successfully. This makes it possible for
parsers to recover from syntax errors that occur before the point
of error detection, but it does prevent the parsers from
affecting lexers in any significant way. The parsers
can insert tokens with values and substitute tokens with values
for other tokens. All symbols carry left and right position values
which are available to semantic actions and are used in
syntactic error messages.
ML-Yacc uses context-free grammars to specify the syntax of languages to
be parsed. See [2] for definitions and information on context-free
grammars and LR parsing. We briefly review some terminology here. A
context-free grammar is defined by a set of terminals T, a set of
nonterminals NT, a set of productions P, and a start
nonterminal S.
Terminals are interchangeably referred to as tokens. The terminal
and nonterminal sets are assumed to be disjoint. The set of symbols is the
union of the nonterminal and terminal sets. We use lower case
Greek letters to denote a string of symbols. We use upper case
Roman letters near the beginning of the alphabet to denote nonterminals.
Each production gives a
derivation of a string of symbols from a nonterminal, which we will
write as A ® a. We define a relation between strings of
symbols a and b, written a |- b and read
as a derives b, if and only if a = d A g,
b = d f g and
there exists some production A ® f. We write the
transitive closure of this relation as
|-*. We say that a string of terminals a is a valid sentence
of the language, i.e. it is derivable, if the start symbol
S |-* a. The sequence of derivations is often
visualized as a parse tree.
ML-Yacc uses an attribute grammar scheme with synthesized attributes.
Each symbol in the grammar may have a value (i.e. attribute) associated
with it. Each production has a semantic action associated with it.
A production with a semantic action is called a rule.
Parsers perform bottom-up, left-to-right evaluations of parse trees using semantic
actions to compute values as they do so. Given a production
P = A ® a, the corresponding semantic action is
used to compute a value for A from the values of the symbols in a.
If A has no value, the semantic action is still evaluated but the value is ignored.
Each parse returns the value associated with the start symbol S of the
grammar. A parse returns a nullary value if the start symbol does not carry a value.
The synthesized attribute scheme can be adapted easily to inherited
attributes. An inherited attribute is a value which propagates from
a nonterminal to the symbols produced by the nonterminal according to
some rule. Since functions are values in ML,
the semantic actions for the derived symbols
can return functions which takes the
inherited value as an argument.
1.2 Modules
ML-Yacc uses the ML modules facility to specify the interface between
a parser that it generates and a lexical analyzer that must be supplied
by you. It also uses the ML modules facility to factor out
a set of modules that are common to every generated parser.
These common modules include a parsing structure, which contains
an error-correcting LR parser1, an LR table structure, and a structure
which defines the representation of terminals. ML-Yacc produces
a functor for a particular parser parameterized by the LR table
structure and the representation of terminals. This functor
contains values specific to the parser, such as the
LR table for the parser2, the
semantic actions for the parser, and a structure containing
the terminals for the parser. ML-Yacc produces a signature
for the structure produced by applying this functor
and another signature for the structure containing the terminals for
the parser. You must
supply a functor for the lexing module parameterized this
structure.
Figure 1 is a dependency diagram of the modules that summarizes this
information. A module at the head of an arrow is dependent
on the module at the tail.
parsing structure
¾®
values for a particular parser
values for a particular parser
¾®
lexical analyzer
parsing structure,
¾®
particular parser
values for a particular parser,
lexical analyzer
Figure 1: Module Dependencies
1.3 Error Recovery
The error recovery algorithm is able to accurately recover from many
single token syntax errors. It tries to make a single token
correction at the token in the input stream at which the syntax error
was detected and any of the 15 tokens3 before that token. The algorithm checks corrections
before the point of error detection because a syntax error is often
not detected until several tokens beyond the token which caused the
error.4
The algorithm works by trying corrections at each
of the 16 tokens up to and including the token at which the
error was detected. At each token in the input stream, it
will try deleting the token, substituting other tokens for the
token, or inserting some other token before the token.
The algorithm uses a parse check to evaluate corrections. A parse
check is a check of how far a correction allows a parser to
parse without encountering a syntax error.
You pass an upper bound on how many tokens beyond the error
point a parser may read while doing a parse check as an argument to the
parser. This allows
you to control the amount of lookahead that a parser reads
for different kinds of systems. For an interactive system, you
should set the lookahead to zero. Otherwise, a parser may hang
waiting for input in the case of a syntax error. If the lookahead
is zero, no syntax errors will be corrected. For a batch system,
you should set the lookahead to 15.
The algorithm selects the set of corrections which allows the parse
to proceed the farthest
and parse through at least the error token. It then removes those
corrections involving keywords which do not meet a longer minimum
parse check. If there is more than one correction possible after this,
it uses a simple heuristic priority scheme to order the corrections,
and then arbitrarily chooses one of the corrections with the highest priority.
You have some control over the priority scheme by being able to
name a set of preferred insertions and a set of preferred substitutions.
The priorities for corrections, ordered from highest to lowest
priority, are
preferred insertions, preferred substitutions, insertions, deletions,
and substitutions.
The error recovery algorithm is guaranteed to terminate since it always
selects fixes which parse through the
error token.
The error-correcting LR parser implements the algorithm by keeping
a queue of its state stacks before shifting tokens and using
a lazy stream for the lexer.
This makes it possible to restart the
parse from before an error point and try various corrections. The
error-correcting LR parser does not defer semantic actions. Instead,
ML-Yacc creates semantic actions which are free of side-effects
and always terminate.
ML-Yacc uses higher-order functions to defer the
evaluation of all user semantic actions until the parse is successfully
completed without constructing an explicit parse tree.
You may declare whether your semantic actions are free of side-effects
and always terminate, in which case ML-Yacc does not need to defer
the evaluation of your semantic actions.
1.4 Precedence
ML-Yacc uses the same precedence scheme as Yacc for resolving
shift/reduce conflicts. Each terminal may be assigned a precedence and
associativity. Each rule is then assigned the precedence of its rightmost
terminal. If a shift/reduce conflict occurs, the conflict is resolved
silently if the terminal and the rule in the conflict have
precedences.
If the terminal has the higher precedence, the shift is chosen. If
the rule has the higher precedence, the reduction is chosen. If both
the terminal and the rule have the same precedence, then the associativity
of the terminal is used to resolve the conflict. If the terminal is
left associative, the reduction is chosen. If the terminal is
right associative, the shift is chosen. Terminals may be declared to
be nonassociative, also, in which case an error message is produced
if the associativity is need to resolve the parsing conflict.
If a terminal or a rule in a shift/reduce conflict does not have
a precedence, then an error message is produced and the shift
is chosen.
In reduce/reduce conflicts, an error message is always produced and
the first rule listed in the specification is chosen for reduction.
1.5 Notation
Text surrounded by brackets denotes meta-notation. If you see
something like {parser name}, you should substitute the actual
name of your parser for the meta-notation. Text in a bold-face
typewriter font (like this) denotes text in a specification
or ML code.
