Controlled grammatic ambiguity.
A new approach to ambiguity of context-free grammars is presented, and within this approach the LL and LR techniques are generalized to solve the following problems for large classes of ambiguous grammars: Construction of a parser that accepts all sentences generated by the grammar, and which always terminates in linear time. Identification of the structural ambiguity: a finite set of pairs of partial parse trees is constructed; if for each pair the two partial parse trees are semantically equivalent, the ambiguity of the grammar is semantically irrelevant. The user may control the parser generation so as to get a parser which finds some specific parse trees for the sentences. The generalized LL and LR techniques will still guarantee that the resulting parser accepts all sentences and terminates in linear time on all input.
INTRODUCTION
For unambiguous grammars we have the powerful LL and LR techniques that
for large classes can verify their unambiguity and construct complete linear time
parsers, i.e. parsers that accept the full languages and terminate in linear time
on all inputs. With a new approach to ambiguity we generalize the LL and LR
techniques to deal with large classes of ambiguous grammars as well; thus characterizing
the ambiguity and constructing complete linear time parsers.
This homemade reprent is typeset using the L A T E X document style acmtrans. It shows
how the published version was intended: the page references are still intact, figures
and text are with the same fonts, and theoretically important material has not been
deferred to an electronic appendix.
Most of this work was done while the author was at Oxford University and DIMACS supported,
mainly, by a NATO grant from the Danish Research Council, partly, by the Danish Research
Academy.
Author's address: University of Copenhagen, Department of Computer Science, Univer-
sitetsparken 1, 2100 Kbenhavn , Denmark; e-mail: mthorup@diku.dk.
Permission to copy without fee all or part of this material is granted provided that the copies are
not made or distributed for direct commercial advantage, the ACM copyright notice and the title
of the publication and its date appear, and notice is given that copying is by permission of the
Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or
specific permission.
c
Ambiguous grammars have long been considered relevant in connection with programming
languages, for as noticed in Aho, Johnson, and Ullman [1975] ambiguous
grammars are often simpler and more natural than their unambiguous counterparts.
Moreover, they can often be parsed more efficiently due to their having smaller parse
trees. In Aho, Johnson, and Ullman [1975], and independently in Earley [1975], the
now standard approach was developed for construction of linear time parsers for
ambiguous grammars. The approach starts by applying an LL or LR technique.
As the grammar is ambiguous the resulting parser will be non-deterministic due to
conflicts in the action table. A deterministic LL or LR parser is then obtained by
resolving these conflicts, possibly in a semi-automatic way using some disambiguating
rules. As stated in Aho, Johnson, and Ullman [1975], the problem with this
approach is that the resolved parser might not be complete. In fact, as noticed in
Soisalon-Soininen and Tarhio [1988], it might not even terminate on some input.
A simple example of a problematic grammar is
(1) L!LL; L!l; L!lll.
The idea behind the last production is to reduce the number of productions in
large parse trees roughly by a factor of five. Applying any LR(1) technique to the
above grammar we get the following non-deterministic LR(1) parser:
State ACTION GOTO
l
Suppose we resolve the conflicts using the heuristic from the classic parser generator
Yacc [Johnson 1975] of choosing shifts over reductions. When presented with a
sentence like ll, the resolved parser will make two shifts arriving at state 4 with
input $, and then it is stuck. Thus the resulting parser is not complete.
In this paper we present some very general techniques for resolving the conflicts
in a non-deterministic LL or LR parser so that the resulting deterministic parser
is guaranteed to be complete and work in linear time. Even for our problematic
grammar (1), our techniques will find such a "good" LR(1) parser. For example this
could be the parser P (1) that for each entry selects the first action. An alternative
good resolution is if instead of shifting in state 2 on input l, we choose to reduce
L!LL. Despite the fact that the grammar (1) is left-recursive, it is possible for us
to find a good LL parser for it, but a lookahead of length 2 is needed. Given the non-deterministic
parser constructed by the canonical LL(2) technique for the grammar
(1), our techniques can find a good resolution which, in fact, selects exactly the
same parse tree as our LR(1) parser P (1) .
The basic idea for testing if a resolved parser is good is to see if there is a set
of simple parse tree rewriting rules that rewrite any parse tree into a parse tree
for the same sentence but found by the parser. Trivially, the existence of such
rewriting rules implies that the resolved LL or LR parser is complete. Moreover it
turns out that in this case the resolved parser will always terminate in linear time.
Controlled Grammatic Ambiguity \Delta 3
The simple rewriting rules are pairs (u; v) of partial parse trees where u and v have
the same root and the same frontier. A parse tree t is rewritten by replacing an
occurrence of v in t with u; if v does not occur in t then (u; v) does not rewrite
t. Loosely speaking, we will show that it is decidable if there exists a finite set of
rewriting rules whose embedding in the original non-deterministic parser implies
that they can rewrite any parse tree into a parse tree for the same sentence found
by the parser. In this case the parser is not only complete, it always terminates in
linear time.
Continuing our example (1), in connection with the resolved parser P (1) , our
techniques will construct the following set of rewriting rules:
@
ll
A
@
A A
Using these rewriting rules, the techniques will prove that P (1) is complete and
works in linear time.
It should be mentioned that other more specialized techniques have been presented
for recognition of resolved LL or LR parsers that are complete and work in
linear time. In Aho, Johnson, and Ullman [1975] is found a simple combinatorial
test which works for classes of LL parsers, and Demers [1974] contains a test based
on merging nonterminals and removing trivial productions. Neither of these techniques
apply to our grammar (1).
By our test for good resolutions we have generalized the LL and LR techniques
to construct not only complete linear time parsers for large classes of ambiguous
grammars, but also finite sets of rewriting rules characterizing the structural am-
biguity. When Knuth in 1965 presented the canonical LR technique [Knuth 1965],
he described it as the most general known technique for testing unambiguity of
grammars. Similarly, our techniques are the most general known for characterizing
finitely generated ambiguity.
An obvious application is as follows. Suppose we want to use an ambiguous
grammar in the semantic definition of a formal language, as, for example, a programming
language or a specification language. If we do not want to refer to some
specific parser, we need to ensure that the ambiguity of the grammar is semantically
irrelevant, i.e. that all parse trees for the same sentence are semantically equivalent.
For example, we need to avoid ambiguity based on a dangling else while ambiguity
based on algebraic identities like associativity is perfectly okay. So far, proving that
the ambiguity of an ambiguous grammar is semantically irrelevant has been done
by hand [Blikle 1989]. However, with the above rewriting rules, we only need to
verify for each of them that the two partial parse trees are semantically equivalent.
Then the rewriting preserves semantics, and hence all the parse trees for any sentence
must be semantically equivalent. The advantages of semantically irrelevant
ambiguity are not only theoretical. Semantically irrelevant ambiguity exhibits real
freedom in parsing. This freedom is not exploited in the current paper where only
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
the construction of deterministic parsers is considered. However, in the technical
report Thorup [1992], based on the results in this paper, a theory is developed for
the construction of non-deterministic complete linear time parsers. The parsing
freedom of these parsers can be used, for example, in connection with incremental
parsing and evaluation.
The set of rewriting rules provides an exact description of the "canonical" parse
trees selected by the parser for the sentences. Firstly, the canonical parse trees are
exactly the parse trees that cannot be rewritten, i.e. the set of parse trees that for
no rewriting rule (u; v) contains an occurrences of v. Secondly, and more construc-
tively, given any parse tree for a sentence, the corresponding canonical parse tree
can be found by repeated rewriting with the rewriting rules. Thus from E (1) we can
read both that P (1) is right associative and that it does not use L!lll.
Our techniques allow the user to state his "priorities" by supplying his own
rewriting rules, thereby controlling the parser generation towards any desired set
of canonical parse trees. As always, our techniques guarantee that the generated
parser is complete and works in linear time.
When comparing our ambiguity resolution based on priorities with the traditional
disambiguating rules facilitated by Yacc [Aho, Sethi, and Ullman 1986; Johnson
1975], one difference is, of course, the already mentioned guarantees of completeness
and termination given by our techniques. On the other hand, there are grammars
for which our techniques report failure despite the existence of good resolutions.
This would never happen to Yacc, for Yacc takes no responsibility for the generated
parsers. Another difference is that our rewriting rules are independent of the actual
parsing technique. For example, our set E (1) can be used both with the LR(1)
and the LL(2) techniques. This independence makes our rewriting rules resemble
more ambiguity resolutions like those given in the syntactic metalanguage SDF
[Heering, Hendriks, Klint, and Rekers 1990]. There ambiguity resolution is achieved
by discarding parse trees that are non-minimal with respect to a fixed priority
ordering on parse trees parameterized, not by rewriting rules, but by a user-supplied
partial ordering of the productions. However, SDF doesn't guarantee that there is
a unique minimal parse. Also, besides the ordering of the productions, there is a
mechanism in SDF that allows certain parses to be disallowed outright ("priority
conflicts"). Consequently, the disambiguated "parser" may be both incomplete and
nondeterministic. Moreover, there are only exponential bounds on its complexity.
This paper is basically theoretical. The classes of grammars we can deal with will
be defined mathematically, but only future experience can tell how well they cover
practical applications. The examples are all very simple, just showing that our
techniques have enriched the class of grammars that can be handled automatically
with several nice ambiguous constructs. For each of these examples it would be
easy by hand to identify the ambiguity and to construct a complete linear time
parser, and, in fact, the same might be the case for any single naturally occurring
ambiguity. The problem in dealing with ambiguous grammars does not lie in the
deliberate use of ambiguous constructs by the designer of the grammar. Rather,
the problem is to ensure that there is no hidden ambiguity. In real life, the problem
could occur if, say, a grammar was so big that it had to be written in parts by
several different authors. Even if the compiler experts claim that they can deal
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 5
with all grammars occurring in practice, the problem is still relevant for more
dynamic systems like OBJ [Futatsugi, Goguen, Jouannaud, and Meseguer 1985]
where compiler tyros may define their own languages. The problem is solved by
the LL and LR techniques for large classes of unambiguous grammars, and with
our generalization it is solved for large classes of ambiguous grammars as well.
In order to keep the presentation short the paper will be focussed around the
canonical LR(1) technique [Knuth 1965] which is theoretically the most beautiful
of the LL and LR techniques. It is, however, not difficult to translate our results
to any of the other techniques. Moreover, we will only touch the semantic aspects
peripherally.
A key to our handling of ambiguity is to generalize the focus from sentences
to derived productions (if X is a grammar symbol deriving a string ff of grammar
symbols, then X!   ff is a derived production). Now, the paper is divided as follows:
Section 2 describes the basic notion of grammars in terms of derived productions,
and Section 3 reviews parsing, modified to deal with derived productions. After
these two preliminary sections, Section 4 formalizes the idea of rewriting rules
rewriting all parse trees into the canonical parse trees found by a parser. Section 5
contains the exact statement of the main result. This includes a precise definition
of what is meant by embedding rewriting into the finite non-deterministic parsers
constructed by the LL and LR techniques. Section 6 discusses the relation between
traditional disambiguating rules and priorities, and Section 7 discusses the problems
with a dangling else. Section 8 gives a general outline of the generalizations of the
LL and LR techniques. Moreover, it gives an overview of the appendices of this
paper. These appendices contain the details of the generalization of the canonical
The paper is self-contained, but the preliminary definitions are rather dense, so
the reader is referred to Aho, Sethi, and Ullman [1986] or Sippu [1988] and Sippu
and Soisalon-Soininen [1990] for a standard text on grammars and parsing. The
paper is a shortened version of Thorup [1993, Part I], to which the reader is referred
for more examples and discussions.
2. GRAMMARS IN TERMS OF DERIVED PRODUCTIONS
As was first noticed algebraically in Blikle and Thorup [1990] and Blikle, Tarlecki,
and Thorup [1991] a key to working formally with the ambiguity of grammars is
to focus on "derived productions" which are natural generalizations of sentential
forms (which in turn are generalizations of sentences). Below, we will review the
basic concepts of context-free grammars, but in terms of derived productions.
A grammar G consists of a finite set V of symbols together with a finite set P of
pairs (X; ff) where X belongs to V and ff is a, possibly empty, string of symbols
from V . We refer to the symbols in V as grammar symbols and to the pairs in P
as productions. A production (X; ff) is written X!ff. We refer to X as the leftside
and to ff the rightside of the production. The grammar symbols are divided into
terminals and nonterminals. One of the latter is distinguished as the start symbol.
A grammar is well-formed only if all the leftside symbols of the productions are
nonterminals.
We will always understand an underlying grammar when we talk about grammar
symbols, productions, etc. Moreover, we adopt the following notational convention
from Aho, Sethi, and Ullman [1986]: A; B; C stand for nonterminals, X;Y; Z for
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
grammar symbols, and ff; fi; fl for possibly empty strings of grammar symbols. The
generally reserved to denote an empty string. Thus, for
The following is a simple example of a grammar:
As in all later examples, only the productions of a grammar are given explicitly.
The grammar symbols are understood to be all symbols used in the productions, the
start symbol is the leftside of the first production, and the terminals are the grammar
symbols in typewriter font. Thus in the grammar (2) we have nonterminals
the start symbol, and we have terminals b; c.
Definition 1. Derived productions are pairs (X; ff) where X is a grammar symbol
and ff is a string of grammar symbols. A derived production (X; ff) is written
X!   ff. The set of derived productions is defined recursively as follows:
-If X is a grammar symbol then X!   X is a derived production.
-If X!   ffY fl is a derived production and Y !fi is a production then X!   fffifl is
a derived production.
For example, we have that A!   bC is a derived production for grammar (2). Notice
that for derived productions, it is not required that the leftside is a nonterminal
(as for productions, the leftside and the rightside refers to the first and the second
coordinate, respectively). This dropping of the distinction between terminals and
non-terminals turns out to be very convenient for the following definitions, algo-
rithms, and proofs. Besides having been used algebraically in Blikle and Thorup
[1990] and Blikle, Tarlecki, and Thorup [1991], the concept of derived productions
has been used in Ballance, Butcher, and Graham [1988] in connection with "gram-
matical abstraction". Often we will ignore the notational difference between derived
productions and productions when writing statements like "all productions are derived
productions" where formally we should have written something like "for all
productions X!ff, we have that X!   ff is a derived production".
In terms of derived productions, a sentential form is a string ff of grammar
symbols such that with S denoting the start symbol, we have that S!   ff is a
derived production. A sentence is then a sentential form consisting of terminals
only. Thus, as claimed, derived productions are more general than both sentential
forms and sentences.
As with sentences, we are interested in the way a derived production is generated
from its recursive definition. This is done in terms of parse trees. Parse trees for
derived productions form the base for all reasoning in the remainder of this paper.
They are therefore introduced with more care and terminology than usual. A parse
tree is an ordered rooted tree where each node is labeled either with a grammar
symbol or with ". Since our parse tree is ordered, the sons of a non-leaf node n are
given as an ordered sequence. Nodes labeled " play a special role, allowing us to
have internal nodes with an empty sequences of sons. More precisely, only a leaf
may be labeled ", and only if it is the single son of some node. If n has a single
son labeled ", we interpret this as its sequence of sons being empty. Concerning
the general labeling, it is required that if an internal node labeled X has its sons
labeled is a production. By the root
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 7
symbol of a parse tree we refer to the label of the root, and by the frontier we refer
to the sequence of labels of the non-" leaves. Parse trees are depicted with the root
in the top and the sons ordered from the left to the right. Thus, for grammar (2)
we have the following parse trees with root symbol A and frontier B:
A
A A
A
Clearly, X!   ff is a derived production if and only if there is a parse tree t with
root symbol X and frontier ff. In this case, we say that t is a parse tree for X!   ff,
or that X!   ff is the derived production generated by t. For example, t (2) and u (2)
both generate A!   B. Correspondingly, parse trees for sentential forms are parse
trees where the root symbol is the start symbol, and parse trees for sentences are
parse trees where, moreover, the frontier consists of terminals.
If we have two parse trees, like t (2) and u (2) , generating the same derived produc-
tion, we say that they are equivalent, and then the underlying grammar is said to
be ambiguous. Thus grammar (2) is ambiguous. Traditionally, one only says that
a grammar is ambiguous if the grammar has two parse trees for the same sentence.
Clearly, our grammar (2) is ambiguous also with respect to this notion of ambiguity.
Notice, however, that the traditional notion of ambiguity is strictly weaker; for it
is possible for a grammar to be ambiguous with respect to derived productions but
not with respect to sentences if there are grammar symbols that are not used in a
parse tree for any sentence.
The study of parse trees plays a major role in this paper, so we need some precise
definitions of a few more parse tree related concepts. A parse tree is said to be trivial
if it contains only one node. A sub-parse tree relation on parse trees is defined to
be the least partial ordering, i.e. the least reflexive and transitive relation, with the
following property: Let t be a parse tree and n be a non-" node of t. Moreover, let
1 be the sub-tree of t excluding all nodes strictly descending from n, and let t 2 be
the sub-tree of t containing all nodes descending from n including n itself. Then t 1
and t 2 are sub-parse trees of t. The construction is illustrated below with X being
the label of the common node n of t 1 and t 2 .
A
A
A
A
A
A
A
A
Notice, that if n is a leaf of t, then t 2 is trivial, and then t t. Similarly t
if n is the root of t. With t, n, we say that t is obtained by
rooting t 2 in the leaf n of t 1 .
It is important to notice that the sub-parse tree relation, in contrast to the normal
sub-tree relation, respects the production structure of parse trees. For example, u (2)
is a sub-tree but not a sub-parse tree of t (2) . According to the definition of the sub-
parse tree relation, we say a parse tree t is minimal in a set T of parse trees if t,
but no proper sub-parse tree of t, is in T . Hence, for example, if T is the set of all
parse trees, then the minimal parse trees in T are the trivial parse trees.
Finally, it is convenient to introduce a constructor pt for parse trees. If X is a
grammar symbol, by pt(X) we denote the trivial parse tree whose single node is
labeled by X . Now, let be a production and t be parse trees
with root symbols we denote the parse tree
with root symbol X and with t being the sub-parse trees descending from
the sons of the root. Thus, continuing our example with grammar (2), we have
3. PARSERS
In this section we review the concepts of parsing, but modified to deal with derived
productions. The modification itself is straightforward, using ideas from incremental
parsing and error recovery [Ghezzi and Mandrioli 1979; Pennello and DeRemer
1979]. However, knowing the exact way the modification is done is crucial to the
understanding of the rest of the paper. Thus parsing is the process of recognizing
derived productions (not just sentences) and selecting parse trees that generate
them.
A parser is an automaton which takes as input an input production meaning a
pair (X; ff), sometimes written X! ? ff, where X is a grammar symbol and ff is a
sequence of grammar symbols. There are now three possibilities:
(1) The parser successfully accepts the input production as a derived production,
and return some parse tree generating X!   ff.
(2) The parser terminates unsuccessfully. This might be the case even if the input
production is a derived production.
(3) The parser does not even terminate.
A parser is a linear time parser if it terminates for all inputs in a time linear in
the length of the input production. Moreover, a parser is complete if it successfully
finds a canonical parse tree for each derived production. We always want parsers
to be complete linear time parsers, and we refer to such parsers as implementations
of a grammar.
Given some parser P , we will refer to the parse trees it can return successfully
as P-canonical parse trees, possibly dropping the 'P ' if some specific parser is un-
derstood. Thus completeness of P means that any derived production is generated
by some P-canonical parse tree.
The traditional LL and LR parsers can easily be modified to parse derived productions
instead of just sentences. In this paper we focus on LR(1) parsers. Below,
we review the definition of LR(1) parsers modified for derived productions.
An parser P for a grammar is characterized by the following components:
-A finite set of states.
-A table INIT from grammar symbols to states.
-A partial table GOTO from states and grammar symbols to states.
-An action table ACTION from states and input symbols to actions.
Controlled Grammatic Ambiguity \Delta 9
Here, by the input symbols we mean all grammar symbols plus an extra symbol $,
and by actions we mean members of the set
is a productiong:
Notice, that relative to traditional LR(1) parsers for sentences we have introduced
the table INIT to take care of the leftside which is no longer fixed to some specific
start symbol. Moreover, the tables GOTO and ACTION are now defined for all
grammar symbols regardless of whether they are terminals or non-terminals.
A parsing with P proceeds through a series of configurations of the form
are grammar symbols, where are
states. The first component of the configuration is called the stack , and the second
component is called the input buffer. The last state, I m , in the stack is referred to
as the state and first input symbol, Xm+1 , in the input buffer is referred to as the
input symbol. By the action we refer to ACTION(Im ; Xm+1 ), i.e. the entry in the
action table given by the state and the input symbol.
ff be the input production. Then the initial configuration or configuration
0 is ( INIT(X) ;ff$). The next configurations are determined by the action of
the current configuration. The effects of the different actions are as follows:
-Accept is only valid if we have that the current configuration is of the form
$). The parsing is then completed suc-
cessfully, accepting the input production as a derived production. The parse tree
for the input production constructed by the parsing is described later.
-Shift is only valid if the current configuration is of the form (ff I ; Xfi), where
X is a grammar symbol and GOTO(I ; X) is defined. The next configuration
becomes (ff I X GOTO(I ; X) fi).
-Reduce is only valid if the current configuration is of the form
the subsequent
configuration becomes (ff I X GOTO(I
-Error simply means that we terminate unsuccessfully, giving up the input production

The parser P is only well-formed if there is no input production for which it will ever
try an invalid action. Notice that if in the parsing of an input production with left-side
X , we encounter a configuration with state I and the sequence X
grammar symbols in the stack, then I
In order to define the parse tree constructed by an accepting parsing, we associate
a parse tree with each grammar symbol in the stack. If the grammar symbol is
X , the parse tree will always have X as root symbol. Recall that in the initial
configuration we have no grammar symbols in the stack. When the parsing shifts
a symbol X from the input buffer to the stack, we associate pt(X) with X . The
interesting case is when the parser reduces some production X!X 1
the reduction, we have as a final segment of the sequence of grammar
symbols in the stack, and the reduction will replace them by X . If t are
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
the parse trees associated with before the reduction, then after the
reduction the parse tree associated with X . When a parsing
accepts, it returns the parse tree associated with the single grammar symbol on the
stack.
The definition of LR(1) parsers for derived productions is illustrated by an example
based on the grammar
Consider the following LR(1) parser for the grammar in (3): (a, s, and r stands
for accept, shift, and reduce, respectively)
INIT State ACTION GOTO
Given the input production B! ? 1\LambdaB \LambdaB it will carry out the following parsing:
Stack Inp-Buf Action
Thus the following parse tree is the P (3) -canonical parse tree for B!
The traditional techniques for construction of LL and LR parsers only work for
classes of unambiguous grammars. However, in Section 8 and the appendices they
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 11
will be generalized so that they construct complete linear time LL and LR parsers
for large classes of ambiguous grammars as well.
Notice that our generalization of parsers to work for derived productions rather
than just for sentences rightly can be viewed as a simplification. For example, in his
seminal paper [Knuth 1965] Knuth showed that if a grammar is unambiguous and
all grammar symbols are used in parse trees for sentences, then a complete linear
time LR(1) parser for sentences can be constructed if it exists. In the context of
derived production, the statement simplifies to: if a grammar is unambiguous, then
a complete linear time LR(1) parser for derived productions can be constructed if
it exists. In other words we get rid of the "no-junk" requirement in the original
formulation.
4. PRIORITIZED PARSING
We are now done with the prelimary sections, ready to introduce "prioritized pars-
ing" which is a key concept for our automatic verification of the completeness of
parsers. It formalizes the rewritings discussed in the introduction. A parse tree
pair is an ordered pair of equivalent parse trees, i.e. parse trees with the same
root and the same frontier. Loosely speaking, a parse tree pair (t 0
substitution from a parse tree pair (t
0 results from t 0
1 by replacing with t 0
an occurrence of t 1 in t 0
1 . Formally speaking this is the case if and only if there
exists numbers k; p, and parse trees u; such that for the parse
tree t 0
- results from t - by first for rooting u i in the ith non-" leaf of
subsequently rooting the obtained parse tree in the kth non-" leaf of u.
The figure below illustrates the construction. In the figure, X!   is the
derived production generated by t 0 and t 1 , and Y !   is the derived
production generated by t 0
1 .
Y
A
A
A
A


Given a set E of parse tree pairs, by E OE we denote the closure of E under substitution
and transitivity.
Definition 2. A set E of parse tree pairs is prioritizing if E OE is a well-founded (no
infinite descending sequence, i.e. no infinite sequence t 0 parse trees with
strict partial ordering, and no two E OE -minimal parse trees
are equivalent. If, moreover, P is a parser and the P-canonical parse trees coincide
with the E OE -minimal parse trees, then E prioritizes P .
Thus, if we say that a parse tree t has higher priority than a parse tree u whenever
then the P-canonical parse trees are exactly those with the highest
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
priority. The term is chosen because later the user will be allowed to manipulate
the set E , thereby showing his priorities for the parser P .
Proposition 4.1. If a set E of parse tree pairs prioritizes a parser P, then P
is complete.
Proof. Let X!   ff be a derived production. By definition, X!   ff is generated
by at least one parse tree u. Since E OE is well-founded, there is an E OE -minimal,
hence P-canonical, parse tree t with (t; u) 2 E OE . But E OE only relates equivalent
parse trees, so t is a P-canonical parse tree for X!   ff.
Sometimes, we will think about the definition of prioritized parsers in terms of
rewriting. We say that the parse tree pair (t; u) rewrites the parse tree u 0 to the
parse tree t 0 if substitution. Notice, that u 0 is not
uniquely defined in terms of t, u, and t 0 , for u might occur at different positions
in u 0 . Now, let E be a set of parse tree pairs prioritizing a parser P . Then, the
definition of prioritizing says that given any parse tree, if, as long as possible, we
rewrite with the parse tree pairs from E , then eventually we will arrive at a P-
canonical equivalent to t. At the moment it might seem most natural to think
of 'prioritizing' in this way. However, our more algebraic description in terms of
orderings forms a better base for the rest of the paper where, typically, we will
be interested in expansions of E OE to orderings that are not expressible in terms of
rewriting.
The techniques that will be presented in Section 8 and the appendices can find
prioritizing sets for large classes of grammars. For the grammar (3), page 10, they
could return
J J@ @
which prioritizes the parser P (3) that we found at page 10. Below are shown two
different maximal rewriting sequences with E (3) , starting in the same parse tree.
(The indices indicate the sub-parse trees being replaced)
A AS S
A AS S
A AS S
A AS S
J J@ @
A AS S A AS S
A AS S
A AS S
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 13
Notice that the number of rewritings needed to transform a parse tree into its
canonical equivalent is not unique.
Observe that any prioritizing set characterizes the ambiguity completely. Sup-
pose, for example, that we want to show that the ambiguity of a grammar is irrelevant
with respect to some semantics. If a prioritizing set E is given, it is sufficient
to check for each parse tree pair in E , that the two parse trees are semantically
equivalent, i.e. that rewriting with the pair preserves semantics. This follows, for
consider any two equivalent parse trees t and u. By the definition of prioritizing,
they can both be rewritten into their common P-canonical equivalent v. Hence they
are both semantically equivalent to v, and hence to each other. In connection with
our grammar (3), we have the prioriting set E (3) , so its ambiguity is irrelevant with
respect to some semantics if and only if these semantics associate an associative
operation with the production E!E   E. This characterization of the ambiguity
of a grammar is somewhat related to the work in Tomita [1986], Rekers [1991] and
Billot and Lang [1989]. There they operate with the concepts of "shared forests"
and "local ambiguity", both of which are subsumed by the concept of substitution.
as in the definition of substitution, shared forests corresponds to
the case where u is trivial, i.e. where local ambiguity corresponds
to the case where u are trivial. In Tomita [1986], Rekers [1991] and Billot
and Lang [1989] these concepts are used for a compact (cubic) representation of
the different parse trees for a given sentence whilst our prioritizing sets once and
for all characterizes the ambiguity for the whole grammar. On the other hand, our
techniques only works for restricted classes of grammars, for which finite prioritzing
sets can be found.
If a set of parse tree pairs prioritizes a parser, it implies that the set of canonical
parse trees is exactly the set of parse trees that does not have sub-parse trees
amongst the second coordinates in the prioritizing set. Thus, from the fact that
that the set of P (3) -canonical parse trees is exactly
the set of parse trees not containing
J J@ @
as a sub-parse tree. Notice that such a concise characterization of right-associative
parsing has not appeared previously in literature! However, a somewhat related
characterization has been proposed independently by Maddox (personal communi-
cation, 1993). Our characterization is only possible due to our change in focus from
sentences to derived productions.
By prioritizing the parsing of a grammar we mean finding a finite set E of parse
tree pairs and a parser P such that E prioritizes P . Thus by prioritizing the parsing
of a grammar we both identify the ambiguity and characterize a complete parser.
In the next section we will state precisely to what extent the techniques to be
presented in Section 8 and the appendices can help us prioritizing the parsing of
grammars. In Section 7, we shall see that there are grammars, like those containing
a dangling-else, which have no finite prioritizing set. It is not claimed that
our techniques can deal successfully with all natural grammars. The LL and LR
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
techniques deal with limited but important classes of unambiguous grammars, i.e.
grammars with empty prioritizing sets of parse tree pairs. The result of this paper
is that these techniques can be generalized to deal safely with correspondingly limited
but important classes of ambiguous grammars with finite prioritizing sets of
parse tree pairs. The relevance of these new classes is indicated simply by showing
some concrete natural ambiguous grammars, like the one in (3), with which they
can deal.
5. THE MAIN RESULT
In the following we assume that the LL and LR techniques have been modified to
work with derived productions instead of sentences. We will be focussing on the
modified version of the canonical LR(1) technique [Knuth 1965], henceforth referred
to as the CLR(1) technique (We change name from "canonical LR" to "CLR" not
as much for brevity, as to avoid confusion stemming from overloading of the term
"canonical"). The CLR(1) technique is formally described in Appendix B.
Given a grammar, the traditional LL and LR techniques (modified to deal with
derived productions) will try to construct a complete linear time LL or LR parser.
Unfortunately they can never be successful if the grammar is ambiguous. The techniques
will always succeed in generating a generally non-deterministic LL or LR
parser, and they are successful exactly when this parser is deterministic. Thus failure
shows up as conflicts in the generated action table, i.e. as entries containing more
than one action. The generated non-deterministic parser always has the property
that, with an appropriate parsing, it can construct any parse tree for any sentence.
To emphasize this property we will refer to the non-deterministic parsers generated
by the LL and LR techniques as universal parsers. Notice that universality implies
completeness in the case where the universal parser is deterministic.
Consider, for example, the grammar
Such a grammar could be relevant in connection with change in representation, i.e.
if we wanted to use equations like x \Theta
However, it is chosen here because of its richness on ambiguity. Applying the
technique, we get the following non-deterministic LR(1) parser:
INIT State ACTIONS GOTO
By a determinization of a universal LL or LR parser U we mean a deterministic LL
or LR parser P obtained by resolving the conflicts in the action table, i.e. for each
entry e in the action table of U , we select a canonical action
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 15
denotes the set of actions in the entry e of the action table of U . For our example
(4), we let P (4) denote the determinization of U (4) derived by selecting the first
action in each entry. Then P (4) is a complete linear time parser. The universal
parsers generated by most of the LL and LR techniques, including the LL(k), the
LALR(k), and the CLR(k) technique, satisfy the no-junk property that all actions
in each entry of the action table are used in the parsing corresponding to some
parse tree. Hence, whenever we resolve a conflict in the action table, we exclude
some parse trees. Thus, if for an unambiguous grammar, we get conflicts in the
action table, there is no hope of finding a complete determinization.
Let U be a universal LL or LR parser. Moreover, let (t; u) be a parse tree pair
with t 6= u. Consider the unique parsings constructing t and u. Let c be the
first configuration from which the two parsings carry out different actions a and
b, respectively. Let e be the entry in the action table corresponding to c; then
. Now, the triple (e; a; b) is called the projection on U of the parse tree
pair (t; u). For parse tree pairs with two identical parse trees, the projection is
undefined, denoted ?. Take for example, the following parse tree pair for grammar
a
F
F
F
FF
The parse trees in a (4) are constructed by following parsings with U
Stack Buffer Action Stack Buffer Action
Thus, the projection of a (4) in U (4) is ((7; F ); shift; reduce E!F )).
An ordering O of a universal LL or LR parser U is represented by associating
with each entry e in the action table a strict partial ordering O e of U e . Thereby
O defines a strict partial ordering on parse trees. Fix two equivalent but different
parse trees t and u, and let (e; a; b) be the projection of (t; u) in U . Then (t; u) 2 O
if and only if (a; b) 2 O e . Notice that because it is required that all the O e s are
strict partial orderings, the definition guarantees that in fact O is a strict partial
ordering. Also notice that if E is a set of parse tree pairs and there is an ordering
of U that contains E , then there is a unique least such ordering O; namely, the
"entry-wise" transitive closure of the projection of E in U . In this case we say
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
that O is the universal parser ordering spanned by does not span a
universal parser ordering.
Given a universal LL or LR parser U with an ordering O and a determinization
P , we say that P is minimal in O if for each entry e, we have that P e is minimal
in O e . Thus, if P is minimal in O, then all P-canonical parse trees are O-minimal.
Definition 3. Let E be a set of parse tree pairs, U be a universal LL or LR parser,
and P be a determinization of U . Then
spans an ordering of U in which P is minimal.
This definition is extremely important for the following. Loosely speaking, it says
that given a set E of parse tree pairs prioritizing a parser P , then E U-prioritizes
P if the finite universal parser U can "see" that the rewritings never loop and that
no canonical parse tree can be rewritten. Continuing our example with grammar
(4), set
@
F
A
@
F
A
@
F
FF
FF
F
Moreover, denote by O (4) the ordering of U (4) obtained by ordering the actions
in the entries of the action table of U (4) in the order that they are already listed.
Notice, that the pair a (4) is in O (4) but not in E OE
. The techniques from Section 8
and the appendices can ascertain that E (4) prioritizes P (4) and that E (4) spans O (4) .
Moreover, it is clear that P (4) is minimal in O (4) . Thus it follows that E (4) U (4) -
prioritizes P (4) . Also the techniques can verify that P (4) works in linear time, so
P (4) is a complete linear time parser. Finding such a parser for grammar (4) is not
completely trivial. Suppose, for example, we apply Warton's heuristic [Wharton
1976] for conflict resolution to U (4) . It prefers reductions over shifts, so in state
will choose to reduce E!F instead of
shifting. Hence the resulting parser will never terminate for an input production
like F! ? FF , which in fact is a derived production.
Main Theorem 5.1. Given a grammar G, a finite set E in of parse tree pairs,
and the universal parser U obtained by any one of the various LL or LR techniques,
we can decide if there exists a determinization P of U , and a finite set E out of parse
tree pairs such that (E in [ E out ) U-prioritizes P. In this case we can find such a P
and E out , where P is a linear time parser, and E out is minimal given P.
The role of E in is to allow the user to impose his own priorities on the parser
construction. Continuing our example with grammar (4), if we set E in to be the set
of the first two parse tree pairs in E (4) , we specify that the generated parser should
be "cycle-free", but leave it open whether it should be left or right associative.
Admittedly, in order to keep down the size of the presentation, we will only prove
Main Theorem 5.1 in detail for the CLR(1) technique. This is done constructively in
Section 8 together with the appendices. In the following, when we talk unspecified
about our technique, it is understood that we are talking about the generalization
of the CLR(1) technique.
Controlled Grammatic Ambiguity \Delta 17
6. DISAMBIGUATING WITH PRIORITIES
In this section we will discuss in some more detail how the priorities from E in in
Main Theorem 5.1 can be used like traditional rewriting rules. The discussion will
be based on an example stemming from Aho, Sethi, and Ullman [1986, pp. 251-
254], and which is taken from a real world grammar for the equation typesetting
language EQN [Kernighan and Cherry 1975]. We consider the grammar
Our aim is to construct a (complete linear time) parser that uses the "special case"
production E!E subE supE in connection with any substring c sub c sup c of
the input, but in no other cases. This is specified by setting
A A Z Z
A A Z Z
A A Z Z
A A Z Z
A A @ @
A A Z Z
A A Z Z
A A Z Z
A A Z Z
@
A A Z Z XXXX X
A A Z Z
The last three pairs are  -priorities. The idea behind them is to set the technique
choosing the first coordinates. Hence the effect of a  -priority is to exclude its
second coordinates from the canonical parse trees. Our technique will successfully
find a complete linear time parser prioritized by some superset of E in (with some
adequate first coordinates in place of the \Lambdas). By looking at the priorities returned
together with the parser, we can see exactly how the technique resolved the various
associativity and precedence questions.
With Yacc [Johnson 1975], which is based on the LALR(1) technique, it is in
some sense easier to construct a parser for grammar (5) satisfying the specification.
Yacc has a general heuristic which prefers shifts over reductions-the very same
heuristic that lead to an incomplete parser for grammar (1) in the introduction.
Thus, all we need to get a correct parser is to add a disambiguating rule saying
that we prefer to reduce with E!E subE supE rather than with E!E supE.
Technically this is told to Yacc, by listing the production E!E subE supE first
in the declaration of the grammar-as we already did.
It seems that one needs to be quite familar with Yacc and the LR(1) techniques,
in order to feel confortable with the above conflict resolution. A more serious
complaint is if there is a risk that somebody else could have worked on the gram-
mar, adding some disambiguating rules. Suppose, for example, that somebody had
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
worked on the grammar before the special case production E!E subE supE was
introduced. It would have made perfect sense for her/him to decide that both sub
and sup should be left associative and that they should beof the same precedence.
Technically this is told to Yacc via the declaration %left 'sub' `sup'. Such a
declaration overrules the heuristic about prefering shifts over reductions. Without
going into details, when applied to the full grammar (5), this declaration implies
that any conflict between shifting and reducing will be settled in favor of reducing.
This does not contradict our preference of reducing with E!E subE supE rather
than with E!E supE, but it implies that we will never get to a state from which it
is possible to reduce E!E subE supE. Consequently, our special case production
will never be used.
7. THE DANGLING ELSE
Unfortunately there are grammars for which our approach cannot be successful.
The most prominent example is the dangling else construction which is commonly
used despite it being semantically problematic (in order to get the correct semantics
of a sentence with a dangling else, one applies the ad-hoc rule that the "else"
belongs to the nearest preceding "then"). The following grammar represents the
classic dangling else construction:
Our techniques cannot handle this grammar, for it can be shown that it has no
finite prioritizing set. However, our techniques can offer to start listing the following
infinite prioritizing set of parse tree pairs:
@
tSSS
A
The universal CLR(1) parser for grammar (6) contains only one conflict, and it
turns out that any resolution of this conflict gives a complete linear time parser
(choosing shifting over reducing gives the parser with the intended semantics).
Unfortunately, our techniques cannot verify this completeness due the lack of a
finite prioritizing set. Hence, if we want the safety of our techniques, we have to
disambiguate grammar (6). Using the technique from Thorup [1994], this can be
done automatically, the result being the grammar
An even better solution would be to avoid the problem completely by changing the
language to something more readable, as is done in Modula-2 [Wirth 1985].
Of course, the lack of safety is not a problem in connection with a single small
like (6). As indicated in the last section, the problem arises if we start
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 19
using grammars like (6) in a larger context, say, where several language designers
are collaborating on the same grammar, or just with a large grammar where
checking against hidden ambiguity and incompleteness of the generated parsers is
cumbersome by hand.
In

Appendix

J we shall return to the possibility of generalizing our techniques to
deal directly with a dangling else construction.
8. ALGORITHMIC OUTLINE
In this section we will give a general outline of the computation described in Main
Theorem 5.1. Also, we will give an introduction to the appendices which, relative
to the CLR(1) technique, contain all the details of the computation. Initially, we
assume that we have none of the  -priorities that we discussed in Section 6. Thus,
we are given a grammar G, some universal LL or LR parser U for G, and a finite set
E in of parse tree pairs. Our goal is to find a determinization P of U , and a finite
set E out of parse tree pairs such that P and E out match each other in the sense
that . If such a matching pair exists we want E out to be
minimal given P , and P to be a linear time parser. The latter condition will be
shown always to be satisfied when P is matched. If there is no such matching pair,
we want to be able to report this.
Our key to searching matching pairs is to construct first a catalyst set R of parse
tree pairs defined as follows: The second coordinates in R are the minimal parse
trees amongst the non-trivial parse trees having the root symbol as a single symbol
in the frontier. Let t be any second coordinate in R, and let X!   X be the derived
production generated by t, then the corresponding first coordinate is pt(X). For
grammar (3), pare 10, the set R is empty, but for grammar (4), page 14, we have
R equal to
R
@
F
A
@
F
It is straighforward to see that R is always finite, and to construct R. The very
special properties of R are described in the following theorem, the proof of which
is deferred to the appendices:
Theorem 8.1. Let P be a determinization of a universal LL or LR parser U ,
and let E be a set of parse tree pairs. Then E U-prioritizes P if and only if the
following conditions are satisfied:
parse trees are P-canonical.
spans an ordering of U in which P is minimal.
From the theorem it follows that a determinization P of our universal parser U and
a finite set E out of parse tree pairs match each other if and only if the following
conditions are satisfied:
(i) All parse trees are P-canonical.
(ii) spans an ordering of U in which P is minimal.
Notice that we have no explicit test for the well-foundedness of (E in [E out ) OE which
is required for E in [ E out to be prioritizing. From spanning a
universal parser ordering it follows directly that (E in [E out [R) OE is irreflexive. The
strength of Theorem 8.1 is that this irreflixivety implies the desired well-foundedness
of
Trivially (ii) can only be satisfied if P is minimal in an ordering of U spanned by
in [ R) OE . This restriction on the number of relevant determinizations is crucial
for the running time. Generally this number is exponential, but if the user works
modularly, introducing only a little new ambiguity in each step, then the set E in
will largely determine the parsing, keeping the number of relevant determinizations
small. Thus we check that (E in [ R) OE spans an ordering O of U . If not, we report
that there cannot be a matching pair.
choose some O-minimal determinization P . We are going to decide if P
is matched by a set E out , and, if so, construct a minimal such set to be returned
together with P . If not, we will have to try another O-minimal determinization. If
no O-minimal determinization P is matched, we will have to report that there is
no matching pair.
Denote by M the set of minimal non-canonical parse trees. By definition, if
the (E in [ E out )-minimal parse trees coincide with the
P-canonical parse trees, but this can only be the case if all parse trees from M are
second coordinates in either E in or E out . Suppose M is infinite. Since E in is finite,
there cannot be a finite set E out matching P . Thus, if M is infinite, we have to try
another O-minimal determinization.
Denote by M \Gamma the set M without the the parse trees occurring as second coordinates
in E in . Check that each parse tree in M \Gamma has a P-canonical equivalent. If
not, P cannot be complete, so we have to try another O-minimal determinization.
Construct E out such that M \Gamma coincides with the second coordinates, and the first
coordinates are their P-canonical equivalents. Clearly we thereby satisfy (i). Also
it is clear that if (ii) is satisfied, then E out is a minimal set matching P , since all the
second coordinates are forced. We claim that (ii) is satisfied if P is matched at all.
Suppose that some set E 0
out matches P . Then
out prioritizes P , so any parse
tree pair with a canonical first coordinate is contained in (E in [
out ) OE . Hence, in
particular, we have E out '
out ) OE . Thus, from the fact that E 0
out satisfies
the condition that (E in [
out [R) OE spans an ordering of U in which P is minimal,
we may conclude that also E out satisfies this condition. Hence (ii) is satisfied, as
claimed. Thus, our final step in the processing of P is to check if (ii) is satisfied. If
so, we return P and E out successfully; otherwise, P cannot be matched, so we have
try another O-minimal determinization.
The above outlines an algorithm for the computation described in Main Theorem
5.1. In case our input contained some  -priorities, all we need to do is to
avoid determinizations in which some second coordinate is canonical. Then as first
coordinates, in place of the \Lambdas, we can just use their canonical equivalents. Unfor-
tunately,  -priorities do not speed up the search for an adequate determinization as
much as did the normal priorities. Essentially, the problem is that we do not know
in advance which is the first non-canonical action in a given second coordinate.
Our algorithmic outline assumes that we can solve the following problems:
Given a finite set E of parse tree pairs how do we check that E OE spans an
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
Controlled Grammatic Ambiguity \Delta 21
ordering of U? If it does, how do we construct this ordering? The problem is
to construct the projections in U of the possibly infinite set of parse tree pairs
in E OE .
Given a determinization P ; how do we construct the set M of minimal non-canonical
parse trees which constituted the necessary second coordinates in
In particular, how do we decide if M is infinite, implying that P
cannot be matched?
Given a determinization P and a parse tree t, how do we check that there is a
P-canonical equivalent to t? The problem is that P might not be terminating
for all input.
How do we prove that all matched determinizations are linear time parsers?
The essential problem is that they might be non-terminating.
All these problems are sorted out in the appendices relative to the CLR(1) technique
(Knuth's canonical LR(1) technique [Knuth 1965] modified to deal with derived
productions). Not all of them are solved exactly as stated. In connection
with problems 2 and 3 we will not give an exact solution if for some other reason
we can infer that P cannot be prioritized. Now, the appendices are divided as
follows. Appendix A proves Theorem 8.1. In Appendix B we formally describe the
construction of universal CLR(1) parsers, and in Appendix C we introduce some
convenient notions concerning such parsers. With the framework set up, Appendix
D solves problem 1, Appendix E addresses problem 2, Appendix F addresses problem
3, and Appendix G deals with problem 4. After having addressed all the above
problems, Appendix H puts everything together in an exact algorithm for the computation
described in Main Theorem 5.1 for the CLR(1) technique. The algorithm
is followed by some examples in Appendix I. Finally, Appendix J contains some
technical remarks about efficiency and possible generalizations.
9. CONCLUSION
The theoretical result of this paper is that the various LL and LR techniques can
be generalized to deal with classes of ambiguous grammars, characterizing their
ambiguity and generating complete linear time parsers.
The practical result is the guaranteed completeness and correctness of the generated
parsers with respect to explicitly declared user intent (the input priorities).
Unintentional ambiguity arising from grammar evolution or the combination of
reused grammar fragments originally developed in other contexts will not slip by
unnoticed. This contrasts the traditional approach based on disambiguating rules
which do not in general give warnings against incompleteness or incorrectness.
Unfortunately there are interesting grammars like those based on a dangling
else for which the techniques presented in this paper will report failure. In that
connection, it would be a significant improvement of our techniques to generalize
them to deal with parsers prioritized by no finite but by infinite sets of parse tree
pairs.

ACKNOWLEDGMENTS

Special thanks to William Maddox, Mark-Jan Nederhof, and Eljas Soisalon-Soini-
nen, all for having put a very large effort into helping me with the presentation
ACM Transactions on Programming Languages and Systems Vol. 16, No. 3, May 1994, Pages 1024-1050.
22 \Delta Mikkel Thorup
of this work. Many others have been helpful with suggestions, comments, and
encouragement during the years I have been working on the theory and algorithms
just presented. Among these are Andrew Appel, Dines Bjrner, Andrezej Blikle,
Alan Demers, Martin Farach, Tony Hoare, Neil Jones, Bernard Lang, Bill McColl,
Colin McDiarmid, Hans Rischel, Sren Riis, Mary Ryan, Barbara Ryder, Vincent
Sgro, Anders Thorup, and various anonymous referees.



--R

Deterministic parsing of ambiguous grammars.
Compilers: Principles
Grammatical abstraction and incremental syntax analysis in a language-based editor
The structure of shared forests in ambiguous parsing.
Denotational engineering.
On conservative extensions of syntax in system development.
On conservative extensions of syntax in the process of system development.
Skeletal LR parsing.

Ambiguity and precedence in syntax description.
Principles of OBJ2.
Incremental parsing.
Incremental generation of parsers.

A system for typesetting mathematics.
On translation of languages from left to right.


A forward move algorithm for LR error recovery.
Generalized LR parsing for general context-free grammars
Technical Report Technical Report CS R9153
Parsing Theory
Parsing Theory
Looping LR parsers.
Ambiguity for incremental parsing and evaluation.
Topics in Computation.
Disambiguating grammars by exclusion of sub-parse trees
Technical Report DIKU-94/11
Efficient parsing for natural language: a fast algorithm for practical systems.
Resolution of ambiguity in parsing.
Programming in Modula-2
revised July
--TR
Programming in MODULA-2 (3rd corrected ed.)
Compilers: principles, techniques, and tools
Looping LR parsers
Parsing theory. Vol. 1: languages and parsing
Grammatical abstraction and incremental syntax analysis in a language-based editor
Denotational engineering
Parsing theory volume 2: LR(K) and LL(K) parsing
Incremental Generation of Parsers
Principles of OBJ2
Incremental Parsing
A system for typesetting mathematics
Deterministic parsing of ambiguous grammars
A forward move algorithm for LR error recovery
Efficient Parsing for Natural Language
On Conservative Extensions of Syntax in the Process of System Development

--CTR
A. Wagner , Susan L. Graham, Efficient and flexible incremental parsing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.5, p.980-1013, Sept. 1998
grammatic ambiguity;semantic unambiguity