Finding Counterexamples from Parsing Conflicts
Chinawat Isradisaikul

Andrew C. Myers

Department of Computer Science
Cornell University
Ithaca, New York, United Stateschinawat@cs.cornell.edu

andru@cs.cornell.edu

Abstract

trying to understand how a grammar specification leads to the observed conflicts. The predictable result is that software developers
tend to hand-code parsers even for tasks to which parser generators
are ideally suited. Hand-coded parsers lead to code that is moreverbose, less maintainable, and more likely to create security vulnerabilities when applied to untrusted input [9, 10]. Developers may
also compromise the language syntax in order to simplify parsing,or avoid domain-specific languages and data formats altogether.
Despite the intrinsic limitations of LL grammars, top-downparser generators such as ANTLR [20, 21] are popular perhaps
because their error messages are less inscrutable. It is surprising that
there does not seem to have been much effort to improve debugging
of conflicts in the more powerful LR grammars. Generalized LR
parsers [28] enable programmers to resolve ambiguities programmatically, but even with GLR parsers, ambiguities could be better
understood and avoided. Moving towards this goal, Elkhound [17]reports parse trees but only when the user provides a counterexample
illustrating the ambiguity. Some LALR parser generators attempt toreport counterexamples [18, 30] but can produce misleading counterexamples because their algorithms fail to take lookahead symbols
into account. Existing tools that do construct correct counterexamples [8, 27] use a brute-force search over all possible grammar
derivations. This approach is impractically slow and does not help
diagnose unambiguous grammars that are not LALR.
We improve the standard error messages produced by LR parser
generators by giving short, illustrative counterexamples that identify
ambiguities in a grammar and show how conflicts arise. For ambiguous grammars, we seek a unifying counterexample, a string ofsymbols having two distinct parses. Determining whether a contextfree grammar is ambiguous is undecidable, however [13], so thesearch for a unifying counterexample cannot be guaranteed to terminate. When a unifying counterexample cannot be found in areasonable time, we seek a nonunifying counterexample, a pair ofderivable strings of symbols sharing a common prefix up to the pointof conflict. Nonunifying counterexamples are also reported when
the grammar is determined to be unambiguous but not LALR.
Our main contribution is a search algorithm that exploits theLR state machine to construct both kinds of counterexamples. Ourevaluation shows that the algorithm is efficient in practice. A key
insight behind this efficiency is to expand the search frontier fromthe conflict state instead of the start state.
The remainder of the paper is organized as follows. Section 2
reviews how LR parser generators work and how parsing conflicts
arise. Section 3 outlines properties of good counterexamples. Sections 4 and 5 explore algorithms for finding nonunifying and unifying counterexamples. An implementation of the algorithm thatworks well in practice is discussed in Section 6. Using various grammars, we evaluate the effectiveness, efficiency, and scalability of
the algorithm in Section 7. Section 8 discusses related work, andSection 9 concludes.

Writing a parser remains remarkably painful. Automatic parser generators offer a powerful and systematic way to parse complex grammars, but debugging conflicts in grammars can be time-consuming
even for experienced language designers. Better tools for diagnosing
parsing conflicts will alleviate this difficulty. This paper proposes apractical algorithm that generates compact, helpful counterexamples
for LALR grammars. For each parsing conflict in a grammar, acounterexample demonstrating the conflict is constructed. When thegrammar in question is ambiguous, the algorithm usually generates
a compact counterexample illustrating the ambiguity. This algorithm
has been implemented as an extension to the CUP parser generator.
The results from applying this implementation to a diverse collectionof faulty grammars show that the algorithm is practical, effective,
and suitable for inclusion in other LALR parser generators.
Categories and Subject Descriptors D.2.5 [Software Engineering]: Testing and Debugging—Debugging aids, Diagnostics; D.3.4[Programming Languages]: Processors—Parsing
General Terms Languages
Keywords Context-free grammar; shift-reduce parser; ambiguous
grammar; error diagnosis; lookahead-sensitive path; product parser

1.

Introduction

An early triumph of programming language research was thedevelopment of parser generators, tools that in principle provide a
concise, declarative way to solve the ubiquitous problem of parsing.
Although LALR parser generators are powerful and have been
available since the 1970s [15], they remain difficult to use, largely
because of the challenges that arise when debugging grammars toeliminate shift/reduce and reduce/reduce conflicts.
Currently, debugging LALR grammars requires a solid understanding of the internal mechanism of LR parsers, a topic that isoften but not always taught in undergraduate-level compiler courses.
Even with this understanding, language designers can spend hours

This is the author’s version of the work. It is posted here by permission of ACM for
your personal use. Not for redistribution.
PLDI’15, June 13–17, 2015, Portland, OR, USA© 2015 ACM. 978-1-4503-3468-6/15/06. . . $15.00
http://dx.doi.org/10.1145/2737924.2737961
1

2.

Backgroundstmt → if expr then stmt else stmt

We assume the reader has some familiarity with LR grammars andparser generators. This section briefly reviews the construction ofan LR parser and shows how LR parsing conflicts arise.
2.1

Parser State Machine|

expr ? stmt stmt|

arr [ expr ] := expr

num → hdigiti

expr + expr|

num hdigiti

Figure 1. An ambiguous CFG
State 0
→
→
→
→
→
→
→
→

stmt
stmt
stmt
stmt
expr
expr
num
num

stmt
stmt
expr
expr
num
num

→
→
→
→
→
→

Shift/Reduce Conflicts

→
→
→

→
→
→
→
...

u a shift item of the form A → X1 X2 · · · Xk • Xk+1 · · · Xm , where

stmt
stmt
stmt
stmt

u a reduce item of the form B → Y1 Y2 · · · Yn •, whose lookahead

State 10set contains t.

stmt
stmt

The example grammar has a shift/reduce conflict, because thetwo items in State 10 match the criteria above on lookahead else.
This is the classic dangling else problem. The grammar is ambiguous
because there are two ways to parse this statement:→→

State 11
stmt
stmt
stmt

if expr then if expr then stmt • else stmt
Even though the grammar is ambiguous, not every conflict must
contribute to the ambiguity. Conflicts may also occur even if thegrammar is not ambiguous. For instance, the grammar in Figure 3
has a shift/reduce conflict between shift action Y → a • a b andreduction X → a • under symbol a. Nevertheless, this grammar isLR(2) and hence unambiguous.

→
→
→
...

State 12stmt

if • expr then stmt else stmt
if • expr then stmt
• num
• expr + expr
• hdigiti• num hdigiti{$, else, . . . }{$, else, . . . }{then, +}{then, +}{then, +, hdigiti}{then, +, hdigiti}

if expr • then stmt else stmt
if expr • then stmt
expr • + expr{$, else, . . .}{$, else, . . .}{then, +}thenState 9

Xk+1 = t for some k ≥ 0 and m ≥ 1, and

{$
}
{$
}
{$
}
{$
}
{?, +
}
{?, +
}
{?, +, hdigiti}{?, +, hdigiti}

exprState 7
stmt
stmt
expr

• if expr then stmt else stmt
• if expr then stmt
• expr ? stmt stmt
• arr [ expr ] := expr
• num
• expr + expr
• hdigiti• num hdigiti
ifState 6

For LR(1) grammars, actions on parser state machines are deterministic: given a state and the next input symbol, either a shift action
or a reduction is executed. Otherwise, a state may contain a pair of
items that create a shift/reduce conflict on a terminal symbol t:

2.3

if expr then stmt

expr → num |Starting from a context-free grammar like the one in Figure 1, thefirst step in generating an LR(1) parser is the construction of a parser
state machine for the grammar. Each state contains a collection oftransitions on symbols and a collection of production items. Eachtransition is either a shift action on a terminal symbol or a goto on a
nonterminal symbol. A production item (abbreviated item) tracks
the progress on completing the right-hand side of a production. Each
item contains a dot (•) indicating transitions that have already been
made on symbols within the production, and a lookahead set of
possible terminals that can follow the production.
The items within a state include those that result from taking
transitions from a predecessor state, and also those generated by
the closure of all the productions of any nonterminal that follows adot. For the start state, the items include those of productions of thestart symbol and their closure1 . Figure 2 shows a partial parser state
diagram for the example grammar.
A parser maintains a stack of symbols during parsing. A shiftaction on the next input symbol t is performed when a transition
on t is available in the current state; t is pushed onto the stack. A
reduction is performed when the current state contains an item of
the form A → X1 X2 · · · Xm •, whose lookahead set contains thenext input symbol; m symbols are popped from the stack, and thenonterminal A is then pushed onto the stack. If neither a shift action
nor a reduction is possible, a syntax error occurs.
2.2

|

→

if expr then • stmt else stmt
if expr then • stmt
• if expr then stmt else stmt
• if expr then stmt{$, else, . . .}{$, else, . . .}{$, else, . . .}{$, else, . . .}

if

stmt
if expr then stmt • else stmt
if expr then stmt •{$, else, . . .}{$, else, . . .}ifelse
if expr then stmt else • stmt
• if expr then stmt else stmt
• if expr then stmt{$, else, . . .}{$, else, . . .}{$, else, . . .}stmt
if expr then stmt else stmt •{$, else, . . .}Figure 2. Selected parser states for the ambiguous CFG. Symbol $indicates the end of input.

Reduce/Reduce Conflicts

A state may also contain a pair of distinct reduce items that create areduce/reduce conflict because their lookahead sets intersect:

S → T

| S T

T → X

|

u A → X1 X2 · · · Xm •, with lookahead set LA , andX → au B → Y1 Y2 · · · Yn •, with lookahead set LB such that LA ∩L B , ∅.

Y → a a b

1 The actual parser construction adds a special start symbol and production,

Y

Figure 3. An unambiguous CFG with a shift/reduce conflict

which are omitted in this section.

2

2.4

Precedence

having two distinct parses. A unifying counterexample is a clear
demonstration that a grammar is ambiguous. The counterexample
given for the challenging conflict above is unifying, for example.
Good unifying counterexamples should be derivations of theinnermost nonterminal that causes the ambiguity, rather than full
sentential forms, to avoid distracting the user with extraneous
symbols. For instance, a good unifying counterexample for the
conflict in Section 2.4 is expr + expr • + expr, a derivation of thenonterminal expr, rather than expr + expr • + expr ? stmt stmt, aderivation of the start symbol.

To simplify grammar writing, precedence and associativity declarations can be used to resolve shift/reduce conflicts. For example, thegrammar in Figure 1 has a shift/reduce conflict between shift item
expr → expr • + expr and reduce item expr → expr + expr • undersymbol +, exhibited by the counterexample expr + expr • + expr.
Declaring operator + left-associative causes the reduction to win.

3.

Counterexamples

The familiar shift/reduce conflicts in the previous section are easily
diagnosed by experienced programming language designers. In
general, the source of conflicts can be more difficult to find.
3.1

Nonunifying counterexamples When a unifying counterexample
cannot be found, there is still value in a nonunifying counterexample:
a pair of derivable strings of symbols sharing a common prefix
up to the point of conflict but diverging thereafter. The common
prefix shows that the conflict state is reachable by deriving somenonterminal in the grammar. For example, the following is a possible
nonunifying counterexample for the challenging conflict, where eachbracket groups symbols derived from the nonterminal stmt:
stmt
stmt
expr ? arr [ expr ] := num • hdigiti ? stmt stmt
expr ? arr [ expr ] := num • hdigiti stmt
stmt
Like unifying counterexamples, good nonunifying counterexamples should be derivations of the innermost nonterminal that canreach the conflict state.
Nonunifying counterexamples are produced for unambiguous
grammars that are not LALR. Additionally, since ambiguity detection is undecidable, no algorithm can always provide a unifying
counterexample for every ambiguous grammar. In this case, providing a nonunifying counterexample is a suitable fallback strategy.

A Challenging Conflict

The example grammar in Figure 1 has another shift/reduce conflictin State 1 (not shown in Figure 2) between
u shift item num → num • hdigiti, andu reduce item expr → num •under terminal symbol hdigiti. It is probably not immediately clear
why this conflict is possible, let alone what counterexample explains
the conflict. In fact, an experienced language designer in our researchgroup spent some time to discover this counterexample by hand2 :expr ? arr [ expr ] := num • hdigiti hdigiti ? stmt stmt.
This statement can be derived in two ways from the production
stmt → expr ? stmt1 stmt2 . First, we can use the reduce item:
u stmt1 →∗ arr [ expr ] := numu stmt2 →∗ hdigiti hdigiti ? stmt stmt

Second, we use the shift item:

4.

u stmt1 →∗ arr [ expr ] := num hdigiti
u stmt2 →∗We first describe an algorithm for constructing nonunifying counterexamples that are derivations of the start symbol. The algorithm
for constructing unifying counterexamples, described in Section 5,
identifies the innermost nonterminal that can reach the conflict state.
Recall that certain terminals in a counterexample can be replacedwith a nonterminal without invalidating the counterexample. Suchterminals must have been part of a reduction. Therefore, a counterexample can be constructed from a walk along transition edges
in the parser state diagram from the start state to the conflict state.
Not all such walks constitute valid counterexamples, however. In
particular, the shortest path is often invalid. For example, the input
if expr then stmt forms the shortest path to State 10 in Figure 2,
but a conflict does not arise at this point. If the next input symbol iselse, the shift action is performed; if the end of input is reached, thereduction occurs. For a counterexample to be valid, the lookahead
sets of parser items must be considered as well.
Instead of finding the shortest path in the state diagram, our algorithm finds the shortest lookahead-sensitive path to the conflict state.
Intuitively, a lookahead-sensitive path is a sequence of transitions
and production steps3 between parser states that also keeps track ofterminals that actually can follow the current production.
To define lookahead-sensitive paths formally, we first define alookahead-sensitive graph, an extension of an LR(1) parser state
diagram in which production steps are represented explicitly. Eachvertex is a triple (s, itm, L), where s is a state number, itm is an item
within s, and L is a precise lookahead set. The edges in this graphare defined as follows:

hdigiti ? stmt stmt

This counterexample, along with its two possible derivations,
immediately clarifies why there is an ambiguity and helps guide thedesigner towards a better syntax, e.g., demarcating stmt1 and stmt2 .
Our goal is to generate such useful counterexamples automatically.
3.2

Constructing Nonunifying Counterexamples

Properties of Good Counterexamples

Useful counterexamples should be concise and simple enough to
help the user understand parsing conflicts effortlessly. This principle
leads us to prefer counterexamples that are no more concrete thannecessary. Although a sequence of terminal symbols that takes theparser from the start state to the conflict state through a series of shiftactions and reductions might be considered a good counterexample,
some of these terminals may distract the user from diagnosing thereal conflict. For example, the following input takes the parser fromState 0 to State 10 in Figure 2:
if 2 + 5 then arr[4] := 7
But the expression 2 + 5 could be replaced with any other expression, and the statement arr[4] := 7 with any other statement.
Good counterexamples should use nonterminal symbols wheneverthe corresponding terminals are not germane to the conflict.
As discussed earlier, LALR parsing conflicts may or may not
be associated with an ambiguity in a grammar. Counterexamples
should be tailored to each kind of conflict.
Unifying counterexamples When possible, we prefer a unifying
counterexample: a string of symbols (terminals or nonterminals)

3 A production step picks a specific production of a nonterminal to work on.
These steps are implicit in an LR closure.

2 This conflict was originally part of a larger grammar.

3

u transition (Figure 4(a)): For every transition in the parser, there is=(s, itm

A → X1 · · · Xk • Xk+1 Xk+2 · · · Xm , L)

an edge between appropriate parser states and items, preserving
the precise lookahead set between the vertices.

Xk+1(s , itm00

u production step (Figure 4(b)): For every item whose symbol after• is a nonterminal, there is an edge from this item to each item
associated with a production of the nonterminal within the samestate. The precise lookahead set changes to the set of terminals
that actually can follow the production. Denoted followL (itm), theprecise follow set for itm in L’s context is defined as follows:=

A → X1 · · · Xk Xk+1 • Xk+2 · · · Xm , L)(a) Transition(s, itm=

A → X1 · · · Xk • Xk+1 · · · Xm , L)
where Xk+1
is a nonterminal· · · Zm0 , followL (itm))[prod](s, itm0

followL (A → X1 · · · Xn−1 • Xn ) , L.

=

Xk+1 → • Z1

followL (A → X1 · · · Xk • Xk+1 Xk+2 · · · Xn ) , {Xk+2 } if Xk+2 isa terminal.

(b) Production step

followL (A → X1 · · · Xk • Xk+1 Xk+2 · · · Xn ) , FIRST(Xk+2 )if Xk+2 is a nonnullable nonterminal, i.e., a nonterminal thatcannot derive ε. FIRST(N) is the set of terminals that can begin
a derivation of N.

Figure 4. Edges of a lookahead-sensitive graphfollowL (A → X1 · · · Xk • Xk+1 Xk+2 · · · Xn ) , FIRST(Xk+2 ) ∪followL (A → X1 · · · Xk+1 • Xk+2 · · · Xn ) if Xk+2 is a nullable
nonterminal.
A shortest lookahead-sensitive path is a shortest path in thelookahead-sensitive graph. To construct a counterexample, thealgorithm starts by finding a shortest lookahead-sensitive path from(s0 , itm0 , {$}) to (s0 , itm0 , L0 ), where s0 is the start state, itm0 is thestart item, s0 is the conflict state, itm0 is the conflict reduce item4 ,and L0 contains the conflict symbol. The symbols associated withthe transition edges form the first part of a counterexample. For
instance, Figure 5(a) shows the shortest lookahead-sensitive path tothe conflict reduce item in State 10 of Figure 2. This path gives theprefix of the expected counterexample:(0, START → • stmt $, {$})

[prod]

1

if

2

expr

3

then

4

[prod]

5

if

6

expr

7

then

8

stmt

9

(0, stmt → • if expr then stmt else stmt, {$})
(6, stmt → if • expr then stmt else stmt, {$})
(7, stmt → if expr • then stmt else stmt, {$})
(9, stmt → if expr then • stmt else stmt, {$})
(9, stmt → • if expr then stmt, {else})(6, stmt → if • expr then stmt, {else})(7, stmt → if expr • then stmt, {else})(9, stmt → if expr then • stmt, {else})(10, stmt → if expr then stmt •, {else})(a) The shortest lookahead-sensitive path to the conflict reduce item
(10, stmt → if expr then stmt • else stmt)

if expr then if expr then stmt •stmt

To avoid excessive memory consumption, our algorithm does
not construct the lookahead-sensitive graph in its entirety. Rather,vertices and edges are created as they are discovered.
The partial counterexample constructed so far takes the parser
to the conflict state. Counterexamples can be constructed in fullby completing all the productions made on the shortest lookaheadsensitive path. Since the conflict terminal is a vital part of counterexamples, this terminal must immediately follow •. In the example
above, a production step was made in State 9 (step 5 in Figure 5(a)),
where the next symbol to be parsed is the conflict terminal else. In
this case, the production can be completed immediately, yielding
the counterexample

then
expr
if
[prod]
thenexpr
if[prod](9, stmt → if expr then • stmt else stmt)(7, stmt → if expr • then stmt else stmt)(6, stmt → if • expr then stmt else stmt)(9, stmt → • if expr then stmt else stmt)(9, stmt → if expr then • stmt)(7, stmt → if expr • then stmt)(6, stmt → if • expr then stmt)(0, stmt → • if expr then stmt)(0, START → • stmt $)(b) The path to the conflict shift item obtained from the shortest lookaheadsensitive pathif expr then if expr then stmt • else stmt
On the other hand, if the symbol immediately after • is a nonterminal,
a derivation of that nonterminal beginning with the conflict symbol
is required. Consider once again the conflict between expr → num •and num → num • hdigiti under lookahead hdigiti. The shortest
lookahead-sensitive path to the reduce item gives the prefix

Figure 5. Paths to the dangling-else shift/reduce conflictthe shortest lookahead-sensitive path as follows. Since transitions on
input symbols must be between the same states for both counterexamples, the only difference is that the derivation using the shift item
must take different production steps within such states. To determine these production steps, our algorithm starts at the conflict shift
item and explores backward all the productions that may be used in
the states along the shortest lookahead-sentitive path, until an item
used in the derivation using the reduce item is found. For example,
Figure 5(b) shows the reverse sequence leading to the shift item of
the dangling-else conflict. Observe that this sequence follows thesame states as in the shortest lookahead-sensitive path when making
transitions, namely, [0, 6, 7, 9, 6, 7, 9, 10]. Even though this sequence
yields the same counterexample as above, the derivation is different.

expr ? arr [ expr ] := num •but the next symbol to be parsed is stmt. In this case, we must find astatement that starts with a digit, e.g., hdigiti ? stmt stmt, yielding
the counterexample
expr ? arr [ expr ] := num • hdigiti ? stmt stmt
The shortest lookahead-sensitive path only reveals a counterexample that uses the conflict reduce item. A counterexample that uses
the conflict shift item can be discovered by exploring the states on
4 The conflict shift item cannot be used because we have no information

about the lookahead symbol after the completion of the shift item.

45.

State (itm1 , itm2 )Constructing Unifying Counterexamples

The algorithm for constructing nonunifying counterexamples does
not guarantee that the resulting counterexamples will be ambiguous
if the grammar is. To aid the diagnosis of an ambiguity, the symbols
beyond the conflict terminal must agree so that the entire string canbe parsed in two different ways using the two conflict items. Since
these conflict items force parser actions to diverge after the conflictstate, the algorithm must keep track of both parses simultaneously.
5.1

itm1
itm2

=
=

A → X1 · · · Xk • Xk+1 Xk+2 · · · Xm
B → Y1 · · · Y` • Y`+1 Y`+2 · · · Yn
Z, where Z = Xk+1 = Y`+1

State (itm01 , itm02 )
itm01
itm02

=
=

A → X1 · · · Xk Xk+1 • Xk+2 · · · Xm
B → Y1 · · · Y` Y`+1 • Y`+2 · · · Yn(a) Transition

Product Parser

State (itm1 , itm2 )The idea of keeping track of two parses is similar to the intuition
behind generalized LR parsing [28], but instead of running the parser
on actual inputs, our approach simulates possible parser actions andconstructs counterexamples at parser generation time. Two copies ofthe parser are simulated in parallel. One copy is required to take thereduction and the other to take the shift action of the conflict. If bothcopies accept an input at the same time, then this input is a unifying
counterexample. A distinct sequence of parser actions taken by eachcopy describes one possible derivation of the counterexample.
More formally, the parallel simulation can be represented by actions on a product parser, whose states are the Cartesian product of
the original parser items. Two stacks are used, one for each original
parser. This construction resembles that of a direct product of nondeterministic pushdown automata [1], but here the states are more
tightly coupled to make parser actions easier to understand. Like alookahead-sensitive graph, a product parser represents production
steps explicitly. Actions on a product parser are defined as follows:

=
=

itm1
itm2

A → X1 · · · Xk • Xk+1 · · · Xm...
where Xk+1
is a nonterminal

State (itm01 , itm2 ) [prod]
=
=

itm01
itm2

Xk+1 → • Z1 · · · Zm0...

(b) Production step on the first parser

Figure 6. Components of the state machine for a product parser
S → N

|

N c

N → n N d |

n N c

|

n A b

| n B

A → a
B → a b c

|

a b d

u transition: If both items in a state of the product parser have atransition on symbol Z in the original parser, there is a corresponding transition on Z in the product parser (Figure 6(a)). When thistransition is taken, Z is pushed onto both stacks.

Figure 7. An ambiguous grammar where the shortest lookaheadsensitive path does not yield a unifying counterexample

u production step: If an item in a state of the product parser has anonterminal after •, there is a production step on this nonterminalin the product parser (Figure 6(b)). Both stacks remain unchanged
when a production step is taken.
u reduction: If an item in a state of the product parser is a reduce

item, a reduction can be performed on the original parser associated with this item, respecting its loookahead set, while leaving
the other item and its associated stack unchanged.

I1 = [conflict-item1 ]D1 = []

I2 = [itm12 , . . . , itmm2 2 ]D2 = [d21 , . . . , d2n2 ]I2 = [conflict-item2 ]D2 = [](a) General form(b) Initial configuration

Figure 8. Configurations. Each itm is an item in the original parser,
and each d is a derivation associated with a transition between items.

For a conflict between items itm1 and itm2 , a string accepted by
the product parser that also takes the parser through state (itm1 , itm2 )is a unifying counterexample for the conflict. The remainder of thissection describes an algorithm that efficiently simulates the productparser without exploring irrelevant states.
5.2

I1 = [itm11 , . . . , itmm1 1 ]
D1 = [d11 , . . . , d1n1 ]steps in the original parser, and (2) partial derivations associatedwith transitions between items, as shown in Figure 8(a). The initialconfiguration contains (1) singleton sequences of the conflict itemsand (2) empty derivations, as shown in Figure 8(b). As partial
derivations are expanded, configurations progress through fourstages, which are illustrated in Figure 9 for the challenging conflictfrom Section 3.1. The four stages are as follows:

Outward Search from the Conflict State

The strategy of using shortest lookahead-sensitive paths to avoid
exploring too many states does not work in general, because symbols
required after • might be incompatible with the productions alreadymade on these paths. For example, the grammar in Figure 7 has
two shift/reduce conflicts in the same state, between reduce item
A → a • and two shift items B → a • b c and B → a • b d undersymbol b. The shortest lookahead-sensitive path gives prefix n a •,which is compatible with a unifying counterexample for the firstshift item, namely, n a • b c. Still, no unifying counterexamples
that use the second shift item can begin with n a •. An extra n isrequired before •, as in n n a • b d c. This example suggeststhat deciding on the productions to use before reaching the conflictstate is inimical to discovering unifying counterexamples.
To avoid making such decisions, our search algorithm starts fromthe conflict state and completes derivations outward. Each searchstate, denoted configuration henceforth, contains two pairs of (1)a sequence of items representing valid transitions and production

1. Completion of the conflict reduce item: the counterexample
must contain derivations of all symbols in the reduce item. All
reduce/reduce conflict items are completed in this stage.
2. Completion of the conflict shift item: the counterexample mustalso contain derivations of all symbols in the shift item. This
stage is not needed for reduce/reduce conflicts.
3. Discovery of the unifying nonterminal: the counterexample must
be a derivation of a single nonterminal. This stage also identifies
the innermost nonterminal for nonunifying counterexamples.
4. Completion of the entire unifying counterexample: the final
counterexample must complete all the unfinished productions.
This stage attempts to find the remaining symbols so that thederivation of the nonterminal found in Stage 3 can be completed
at the same time on both copies of the parser.

5Stage 1:

itmm1 1
itmm2 2expr
num •Stage 2:

Stage 3:

Z

...

...
stmt
...
stmt. . .
expr. . .
num. . .
stmt
expr numarr[ expr ]:= num • hdigiti
num

...

...
...
stmt. . .
expr. . .
num
stmt
expr numarr[ expr ]:= num • hdigiti
num
expr
stmt
stmt
...
...

itm01
itm02

D1 ++ [Z]I2 ++ [itm02 ]D2 ++ [Z]

itm01
itm02
Z

stmt

itm11
itm12

unifying
nonterminal

itm01
itmm2 2(b) Production step on the first parser
itm01
itm12

[itm01 ] ++ I1[Z] ++ D1[itm02 ] ++ I2[Z] ++ D2[itm01 ] ++ I1
D1
I2
D2

[prod]
itm11
itm12

where itmm1 1 is a reduce item
and itm01 , itm02 are in same state

where itmm1 1 is a reduce item of the form
A → X1 · · · X` •, and m1 = ` + 1(c) Reverse transition(d) Reverse production step on the first parser

itm11
itm02
[prod]
itm11
itm12

stmt
stmt
expr
num
expr num
expr ? arr[ expr ]:= num • hdigiti hdigiti ? stmt stmt
num
num
expr
expr
stmt
stmt
stmt

I1 ++ [itm01 ]
D1
I2
D2

[prod](a) Transition

Stage 4:

I1
D1
[itm02 ] ++ I2
D2

where itmm1 1 is a reduce item of the form
A → X1 · · · X` •, and m1 < ` + 1

stmt(e) Reverse production step on the second parser
itmm1 1 −`−1 = B → Y1 · · · Yk • A · · · Ym
[prod]

Figure 9. Counterexamples and derivations associated with configurations after finishing each stage for the challenging conflict. The
derivation above each counterexample uses the reduce item; the one
below uses the shift item. The gray portion of the configuration is
not required for completing the stage.
5.3

itmm1 1
itmm2 2I1 ++ [itm01 ]itm1m1 −` = A → • X1..
.

itmm1 1

Successor Configurations· · · X`A
itm01 = B → Y1

· · · Yk A • · · · Ym

I10 = [itm11 , . . . , itmm1 1 −`−1 , itm01 ]D01 = [d11 , . . . , d1n1 −` , (A → d1n1 −`+1 · · · d1n1 )]I2 = . . .
D2 = . . .

where itmm1 1 is a reduce item of the form
A → X1 · · · X` •, and m1 > ` + 1

We now present a strategy for computing successor configurations.
Figure 10 pictures some of the possible successor configurations
that can be reached from the configuration shown in Figure 8(a) via
various actions in the product parser:(f) Reduction on the first parser

Figure 10. Successor configurations. Each kind of edge in the
product parser corresponds to a particular successor configuration.
Operator ++ denotes list concatenation.

u transition (Figure 10(a)): If the product parser has a transition on

symbol Z from the last item in the current configuration, append
the current configuration with appropriate items and symbols.
u production step on the first parser (Figure 10(b)): If the productparser has a production step on the first parser from the last itemin the current configuration, append the item resulting from taking
the production step (itm01 ) to the sequence of items for the firstparser (I1 ). A production step on the second parser is symmetric.

and symbols. The prepended items must belong to the samestate in the original parser. Additionally, the lookahead set of
the item prepended to the first parser (itm01 ) must contain theconflict symbol if the current configuration is yet to complete
Stage 1.

u preparation of the first parser for a reduction: If the last item forthe first parser is a reduce item, but there are not enough items tosimulate a reduction moving forward, then more items must be
prepended to the configuration. That is, we must work backward
to ready the reduction. Preparing the second parser for a reduction
is symmetric. Successor configurations depend on the first itemin the current configuration:

reverse production step on the first parser (Figure 10(d)): If the
product parser has a production step on the first parser to thefirst item in the current configuration, prepend the item prior to
taking the production step (itm01 ) to I1 .
reverse production step on the second parser (Figure 10(e)):
Occasionally, the second parser will require a reverse production
step so that further reverse transitions can be made. In this case,prepend the item prior to taking the production step (itm02 ) to
the sequence of items for the second parser (I2 ).

reverse transition (Figure 10(c)): If the product parser has atransition on symbol Z to the first item in the current configuration, prepend the current configuration with appropriate items

6

Warning : *** Shift/Reduce conflict found in state #13
between reduction on expr ::= expr PLUS expr •and shift on
expr ::= expr • PLUS expr
under symbol PLUS
Ambiguity detected for nonterminal expr
Example: expr PLUS expr • PLUS expr
Derivation using reduction:
expr ::= [expr ::= [expr PLUS expr •] PLUS expr]
Derivation using shift:expr ::= [expr PLUS expr ::= [expr • PLUS expr]]

u reduction on the first parser (Figure 10(f)): If the last item for the

first parser is a reduce item of the form A → X1 · · · X` •, and theconfiguration has enough items, then the first parser is ready for a
reduction. A successor configuration is obtained by (1) removing
the last ` + 1 items that are part of the reduction from I1 , which
simulates popping the parser stack, (2) appending the result oftaking the goto on A (itm01 ) to I1 , and (3) rearranging the partial
derivations (D1 ) to complete the derivation for A. The second
parser remains unchanged throughout the reduction. A reduction
on the second parser is symmetric.
5.4

Figure 11. A sample error message reported by the implementation.
The first four lines are original to CUP.

Completing the Search

The search algorithm computes successor configurations until it
encounters a configuration C f that has completed Stages 1 and 2,
where both sequences of items in C f are of the form

Finding shortest lookahead-sensitive path Blindly searching forthe shortest path from the start state might explore all parser states.
As an optimization, only states that can reach the reduce conflict
item need be considered. These states can be found quickly using thelookup tables for reverse transitions and reverse production steps.

[? → · · · • A · · · , ? → · · · A • · · · ]for some nonterminal A. The partial derivations associated withthese sequences, which must be of the form [A → · · · ], show that
nonterminal A is ambiguous. The unifying counterexample is thesequence of the leaf symbols within these derivations.
Several observations can be made about the algorithm. First, thealgorithm maintains an invariant that the head of both sequences of
items in any configuration belong to the same parser state, as thesequence of states prior to the conflict must be identical for different
derivations of the unifying counterexample. Second, a configuration
generates multiple successor configurations only when a production
step (forward or backward) or a reverse transition is taken. Therefore,
the branching factor of the search is proportional to the ratio of thenumber of these actions to the number of items in the parser.
The third observation is that a production step may be taken
repeatedly within the same state, such as one for items of the form
A → • A · · · . To avoid infinite expansions on one configuration
without making progress on others, the search algorithm must
postpone such an expansion until other configurations have been
considered. The algorithm imposes different costs on different kindsof actions and considers configurations in order of increasing cost.
Finally, the algorithm is guaranteed to find a unifying counterexample for every ambiguous grammar, but the search will notterminate when infinite expansions are possible on unambiguous
grammars. In other words, this semi-decision procedure for determining ambiguity is sound and complete. Since a naive implementation of this algorithm is too slow for practical use, the next section
discusses techniques that speed up the search but still maintain thequality of counterexamples.

6.

Constructing unifying counterexamples The main search algorithm is also unguided. As a tradeoff, the algorithm only considers
states on the shortest lookahead-sensitive path when making reverse
transitions. This restriction makes the algorithm incomplete, causing
it to miss unifying counterexamples that use parser states outside
the shortest path. Nevertheless, a counterexample that follows theshortest lookahead-sensitive path will take the parser to the conflictstate as quickly as possible. These compact counterexamples seemas helpful as unifying ones, so our tool does report them. The option-extendedsearch can be used to force a full search.
Constructing nonunifying counterexamples The search for unifying counterexamples may fail in two cases: first, when eligible
configurations run out; second, when a production step in an unambiguous grammar is taken repeatedly, resulting in nontermination.
Therefore, our implementation imposes a 5-second time limit on
the main search algorithm. When the search fails, a nonunifying
counterexample is constructed and reported instead.
The implementation also imposes a 2-minute time limit on the
cumulative running time of the unifying counterexample finder.
After two minutes, at least 20 conflicts must have been accompaniedwith counterexamples, so the user is likely to prefer resolving themfirst. Our tool seeks only nonunifying counterexamples thereafter.
Exploiting precedence Precedence and associativity are not partof the parser state diagram, and hence are not part of the generated
lookup tables. Therefore, our implementation inspects precedence
declared with relevant terminals and productions during the search.

Implementation

7.

Our counterexample finder has been implemented in Java as a module extending the CUP LALR parser generator [14] version 0.11b
201503265 . The module contains 1478 non-comment, nonempty
lines of code. Figure 11 shows an error message reported by ourimplementation for the shift/reduce conflict in Section 2.4. One
interesting design choice was the tradeoff between finding unifying counterexamples when they exist, and avoiding long, possibly
fruitless searches when a nonunifying counterexample might suffice.

Evaluation

Our evaluation aims to answer three questions:u Is our implementation effective on different kinds of grammars?
u Is our implementation efficient compared to existing ambiguity

detection tools?
u Does our implementation scale to reasonably large grammars?

7.1

Data structures The search algorithm requires many queries on
possible parser actions, but parser generators usually do not provide
an infrastructure for fast lookups. In particular, reverse transitions
and production steps are not represented directly. Before working
on the first conflict within a grammar, our implementation generates
several lookup tables for these actions.

Grammar Examples

We have evaluated our implementation on a variety of grammars.
For each grammar, Table 1 lists the complexity (the numbers ofnonterminals and productions, and the number of states in theparser state machine) and the number of conflicts. The grammars
are partitioned into the following categories:
Our grammars All grammars shown in this paper are evaluated.
Other grammars that motivated the development of our tool, and a

5 Available at https://github.com/polyglot-compiler/polyglot/

tree/master/tools/java_cup.

7

ut
eo

#

3
1
2
1
3
1
6
1
2
1
3
1
1
4
1
1
1
2
3
8
1
19
1
1
1
1
1
3
5
1
1
1
1
1
4
1
1
1
1133
2
14
3

4
7
4
4
4
4
4
4
7
7
4
7
7
4
4
7
4
7
4
7
7
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

3
0
2
0
3
1
6
1
0
0
3
0
0
4
1
0
1
0
3
0
0
19
1
1
1
1
1
2
5
1
1
1
1
1
4
0
1
1
141
2
6
3

0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
1
0
2
0
8
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0

0
0
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
9 (983)0
60

few grammars in previous software projects that pose challenging
parsing conflicts are also part of the evaluation.

Time (seconds)
Total
Average
0.072
0.024
0.010
0.010
0.016
0.008
0.010
0.010
0.024
0.008
0.548
0.548
0.155
0.026
0.169
0.169
T/L
T/L
T/L
T/L
0.023
0.008
0.008
0.008
0.009
0.009
0.043
0.011
0.017
0.017
0.009
0.009
0.010
0.010
0.012
0.006
0.028
0.009
0.025
0.003
0.017
0.017
0.140
0.007
0.024
0.024 (1.8s)
0.060
0.060 (0.1s)
0.024
0.024 (0.1s)
0.031
0.031 (0.0s)
0.030
0.030 (0.4s)
0.196
0.098 (0.3s)
0.296
0.059 (0.1s)
0.070
0.070 (1.2s)
0.081
0.081 (0.3s)
0.113
0.113 (0.3s)
0.327
0.327 (1.3s)
0.219
0.219 (1.11h)
1.015
0.254 (0.5s)
T/L
T/L (1.3s)
0.212
0.212 (4.9s)
0.569
0.569 (32.4s)
35.3840.251 (0.4s)
0.435
0.218 (35.1s)
2.042
0.255 (6.5s)
0.526
0.175 (3.3s)

Amb?
Whether the grammar
is ambiguous.
# unifNumber of conflicts
for which unifying
counterexamples arefound within the time
limit.
# nonunif
Number of conflicts
for which nonunifying counterexamples
are found within thetime limit.
# time out
Number of conflicts
for which the tool
times out. Nonunifying counterexamples
are reported for theseconflicts.
Total time
Time used when counterexamples are foundwithin the time limit.
(Average of 15 runs,
with a standard deviation of at most 15%,so the margin of error
is at most 9% at 95%
confidence.)
Average time
Total time
# unif + # nonunif

counterexample exists, and for which our tool times out and hence
reports a nonunifying counterexample. For grammars requiring morethan two minutes of the main search algorithm, the number ofremaining conflicts is shown in parentheses. Our implementation
finishes within the time limit on 92% of the conflicts.
The main search algorithm may fail to find a unifying counterexample even if the grammar is ambiguous. One reason is thetradeoff used to reduce the number of configurations, as explained in
Section 6. Grammar ambfailed01 illustrates this problem. Anotherreason is that the configuration describing the unifying counterexample has a cost too high for the algorithm to reach within the time
limit. For instance, the ambiguous counterexample for grammar
C.4 requires a long sequence of production steps. For these failures,
nonunifying counterexamples are reported instead.
We also compare effectiveness against prior versions of the
Polyglot Parser Generator (PPG) [18], which attempt to report only
nonunifying counterexamples. PPG produces misleading results on
ten benchmark grammars: figure1, figure7, abcd, simp2, SQL.5,
Pascal.3, C.2, Java.1, Java.3, and Java.4. Incorrect counterexamples
are generated because PPG’s algorithm ignores conflict lookahead

Grammars from StackOverflow and StackExchange We evaluate our tool against grammars posted on StackOverflow and StackExchange by developers who had difficulty understanding the conflicts.
This section of Table 1 links to the corresponding web pages.
Grammars from existing tool To compare our implementation
with the state of the art, we run our tool against the grammars used
to evaluate the grammar filtering technique [5]. These grammars,
which we call the BV10 grammars hereafter, were constructed byinjecting conflicts into correct grammars for mainstream programming languages. In some grammars (e.g., Java.2), the addition of anullable production generates a large number of conflicts.
7.2

tim

nu
no
#

if
un
#

b?

ni

f

ic
ts
nfl

A
m

24
10
16
17
22
70
82
133
767
1255
13
15
9
9
10
13
14
15
17
21
27
53
46
151
149
151
151
323
324
321
322
322
369
368
368
369
370
607
606
608
608
607

co
#

at
e

s

s

9
7
10
10
11
41
41
67
445
599
7
11
5
5
6
9
10
10
12
13
12
20
23
81
81
81
81
177
177
177
177
177
214
214
214
214
214
351
351
351
351
351

st
#

pr
od

#

3
4
4
6
5
10
16
14
185
234
2
6
2
2
2
5
5
6
7
3
6
9
8
29
29
29
29
79
79
79
79
79
64
64
64
64
64
152
152
152
152
152

no

Grammarfigure1
figure3
figure7ambfailed01
abcd
simp2
xi
eqn
java-ext1
java-ext2
stackexc01
stackexc02
stackovf01
stackovf02
stackovf03
stackovf04
stackovf05
stackovf06
stackovf07
stackovf08
stackovf09
stackovf10
SQL.1
SQL.2
SQL.3
SQL.4
SQL.5
Pascal.1
Pascal.2
Pascal.3
Pascal.4
Pascal.5
C.1
C.2
C.3
C.4
C.5
Java.1
Java.2Java.3Java.4Java.5

#

nt

er
m

s

Table 1. Evaluation results. T/L indicates 5-second time limit exceeded on all conflicts. Times inparentheses indicate running time for the state-of-the-art ambiguity detector [2, 5].

EffectivenessOur tool always gives a counterexample for each conflict in every
grammar. Table 1 reports the numbers of conflicts for which ourtool successfully finds a unifying counterexample (if the grammar
is ambiguous), for which our tool determines that no unifying

8

symbols. For instance, PPG reports this invalid counterexample forthe dangling-else conflict:

Grammar filtering [5] combines this exhaustive approach with theapproximative approach from the NU test to speed up discovery of
ambiguities. AmbiDexter [4] uses parallel simulation similar to ourapproach, but on the state machine of an LR(0), grammar-filteredapproximation that accepts a superset of the actual language. This
allows false positives.
CFGAnalyzer [2] converts CFGs into constraints in propositional logic that are satisfiable if any nonterminal can derive an
ambiguous phrase whose length is within a given bound. This boundis incremented until a SAT solver finds the constraints satisfiable.
CFGAnalyzer does report counterexamples, but never terminates onunambiguous input grammars even if there is a parsing conflict.
Schmitz’s experimental ambiguity detection tool [26] for Bison
constructs a nondeterministic automaton (NFA) of pairs of parser
items similar to our product parser states. Its reports of detected
and potential ambiguities remain similar to parsing conflict reports
and hence difficult to interpret. Counterexample generation remains
future work for Schmitz’s tool. To obtain precise ambiguity reports
for LALR(1) construction, this tool must resort to constructing NFAs
for LR(1) item pairs.
SinBAD [29] randomly picks a production of a nonterminal toexpand when generating sentences, increasing the chance of discovering ambiguity without exhaustively exploring the grammar.
SinBAD’s search still begins at the start symbol, so reported counterexamples might not identify the ambiguous nonterminal.

if expr then stmt • else
if expr then stmt • else stmt
The unifying counterexamples given by our algorithm provide
a more accurate explanation of how parsing conflicts arise. Ouralgorithm has been integrated into a new version of PPG.
7.3

Efficiency

We have measured the running time of the algorithm on the conflicts
that our tool runs within the time limit. These measurements were
performed on an Intel Core2 Duo E8500 3.16GHz, 4GB RAM,
Windows 7 64-bit machine. The results are shown in the last twocolumns of Table 1. For the BV10 grammars, we also include inparentheses the time used on a similar machine by a grammarfiltering variant of CFGAnalyzer [2, 5], which is the fastest, on
average, among the ambiguity detection tools we have found.
This state-of-the-art ambiguity detector terminates as soon as it
finds one ambiguous counterexample, whereas our tool finds acounterexample for every conflict. Hence, the running time of thestate-of-the-art tool is compared against the average time taken perconflict in our implementation.
On average, when the time limit is not exceeded, the algorithm
spends 0.18 seconds per conflict to construct a counterexample.
For grammars taken from StackOverflow and StackExchange, theaverage is 8 milliseconds.
For the BV10 grammars, our algorithm outperforms the filtering
technique. Based on a geometric average, our tool is 10.7 times fasterthan the variant of CFGAnalyzer, which takes more than 30 seconds
to find a counterexample for certain grammars. (One grammar takes
0.0s for both tools and therefore dropped from the average.) For
most of these grammars, the time our implementation takes to findcounterexamples for all conflicts is less than that of the state-of-theart tool trying to find just one counterexample. For grammar C.4,
the CFGAnalyzer variant finds a unifying counterexample, but ourtool fails to do so within the time limit. This result suggests thatgrammar filtering would be a useful addition to our approach.
7.4

Counterexample generation Some additional attempts have been
made to generate counterexamples that illustrate ambiguities or
parsing conflicts in a grammar.
Methods for finding counterexamples for LALR grammars
can be traced back to the work of DeRemer and Pennello [11],who show how to generate nonunifying counterexamples using
relations used to compute LALR(1) lookahead sets. Unfortunately,
modern implementations of parser generators do not compute
these relations. Our method provides an alternative for finding
nonunifying counterexamples without requiring such relations, andoffers a bonus of finding unifying counterexamples when possible.
DMS [8] is a program analysis and transformation system whose
embedded parser generator allows users to write grammars directly
within the system. When a conflict is encountered, DMS uses aniterative-deepening [16] brute-force search on all grammar rules
to find an ambiguous sentence [7]. This strategy can only discover
counterexamples of limited length in an acceptably short time.
CUP2 [30] reports the shortest path to the conflict state, while
prior versions of PPG [18] attempt to report nonunifying counterexamples. These parser generators often produce invalid counterexamples because they fail to consider lookahead symbols.
While less powerful than LR grammars, LL grammars can also
produce conflicts. The ANTLR 3 parser generator [20] constructs
counterexamples, but they can be difficult to interpret. For instance,
ANTLR 3 provides the counterexample hdigitihdigiti for the thechallenging conflict in Section 3.16 . Our technique describes theambiguity more clearly.

Scalability

The evaluation results show that the running time of our algorithm
only increases marginally on larger grammars, such as those formainstream programming languages. The performance shown here
demonstrate that, unlike prior tools, our counterexample finder ispractical and suitable for inclusion in LALR parser generators.

8.

Related Work

Generating counterexamples is just one way to help address parsing
conflicts. In general, several lines of work address ways to deal withsuch problems. We discuss each of them in turn.
Ambiguity detection Several semi-decision procedures have beendevised to detect ambiguity. Pandey provides a survey [19] on thesemethods, some of which we discuss below.
One way to avoid undecidability is to approximate input CFGs.
The Noncanonical Unambiguity (NU) test [25] uses equivalence
relations to reduce the number of distinguishable derivations of agrammar, reducing the size of the search space but overapproximating the language. Its mutual accessibility relations are analogous toactions in our product parser. Basten extends the NU test to identify
a nonterminal that is the root cause of ambiguity [3]. One challengeof the NU test is choosing appropriate equivalence relations.
A brute-force way to test ambiguity is to enumerate all strings
derivable from a given grammar and check for duplicates. Thisapproach, used by AMBER [27], is accurate but prohibitively slow.

Conflict resolution Generalized LR parsing [28] keeps track ofall possible interpretations of the input seen so far by forking theparse stack. This technique avoids LR conflicts associated withhaving too few lookahead symbols but requires users to merge theoutcomes of ambiguous parses at parse time. Our approach, which
pinpoints ambiguities at parser construction time, is complementary
and applicable to GLR parsing.
The GLR parsing algorithm is asymptotically efficient for
typical grammars, but its constant factor is impractically high.
Elkhound [17] is a more practical hybrid between GLR and LALR
6 The example grammar was modified to eliminate left recursion.

9

parsing. It can display different derivations of ambiguous sentences,
but the user must provide these sentences.
The eyapp tool [24], a yacc-like parser generator for Perl, postpones conflict resolution until actual parsing. Users can write codethat inspects parser states and provides an appropriate resolution.
SAIDE [22, 23] is an LALR parser generator that automaticallyremoves conflicts arising from insufficient number of lookaheads,
and attempts to detect ambiguities by matching conflicts with predefined patterns of known cases. Although this approach guarantees
termination, conflicts could be miscategorized.
Dr. Ambiguity [6] provides diagnostics explaining causes ofambiguities as an Eclipse [12] plugin, but a collection of parse trees
demonstrating ambiguities must be provided as input.
ANTLR 4 [21] uses textual ordering of productions as precedence and abandons static detection of conflicts. Textual ordering
makes grammars less declarative, but ambiguous inputs can still
exist; any ambiguities are discovered only at parse time.

9.

[9] CVE. CVE-2013-0269. Common Vulnerabilities and Exposures,
February 2013. Retrieved November 13, 2014.
[10] CVE. CVE-2013-4547. Common Vulnerabilities and Exposures,
November 2013. Retrieved November 13, 2014.
[11] Frank DeRemer and Thomas Pennello. Efficient computation of
LALR(1) look-ahead sets. ACM Trans. on Programming Languages
and Systems, 4(4):615–649, October 1982.
[12] J. des Rivières and J. Wiegand. Eclipse: A platform for integrating
development tools. IBM Systems Journal, 43(2):371–383, 2004.
[13] John Hopcroft and Jeffrey Ullman. Introduction to Automata Theory,
Languages and Computation. Addison-Wesley, Reading, MA, 1979.
ISBN 978-0-201-02988-8.
[14] Scott E. Hudson, Frank Flannery, C. Scott Ananian, Dan Wang,
and Andrew Appel. CUP LALR parser generator for Java, 1996.
Software release. At http://www.cs.princeton.edu/˜appel/modern/java/CUP/.
[15] Stephen C. Johnson. Yacc: Yet another compiler-compiler. Computing
Science Technical Report 32, AT&T Bell Laboratories, Murray Hill,
NJ, July 1975.

Conclusion[16] Richard E. Korf. Depth-first iterative-deepening: an optimal admissible
tree search. Artificial Intelligence, 27(1):97–109, September 1985.
[17] Scott McPeak and George C. Necula. Elkhound: A fast, practical GLR
parser generator. In Proc. 13th Int’l Conf. on Compiler Construction(CC’04), pp. 73–88, 2004.
[18] Nathaniel Nystrom, Michael R. Clarkson, and Andrew C. Myers.
Polyglot: An extensible compiler framework for Java. In Proc. 12thInt’l Conf. on Compiler Construction (CC’03), pp. 138–152, April
2003.
[19] Hari Mohan Pandey. Advances in ambiguity detection methods
for formal grammars. Procedia Engineering, 24(0):700–707, 2011.
International Conference on Advances in Engineering 2011.
[20] Terence Parr and Kathleen Fisher. LL(*): The foundation of the ANTLR
parser generator. In Proc. 32nd ACM SIGPLAN Conf. on Programming
Language Design and Implementation (PLDI), pp. 425–436, 2011.
[21] Terence Parr, Sam Harwell, and Kathleen Fisher. Adaptive LL(*)
parsing: The power of dynamic analysis. In Proc. 2014 ACM SIGPLAN
Conf. on Object-Oriented Programming, Systems, Languages, andApplications, pp. 579–598, 2014.
[22] Leonardo Teixeira Passos, Mariza A. S. Bigonha, and Roberto S.
Bigonha. A methodology for removing LALR(k) conflicts. Journal of
Universal Computer Science, 13(6):737–752, June 2007.
[23] Leonardo Teixeira Passos, Mariza A. S. Bigonha, and Roberto S.
Bigonha. An LALR parser generator supporting conflict resolution.
Journal of Universal Computer Science, 14(21):3447–3464, December
2008.
[24] C. Rodriguez-Leon and L. Garcia-Forte. Solving difficult LR parsing
conflicts by postponing them. Comput. Sci. Inf. Syst., 8(2):517–531,
2011.
[25] Sylvain Schmitz. Conservative ambiguity detection in context-freegrammars. In Automata, Languages and Programming, volume 4596
of Lecture Notes in Computer Science, pp. 692–703. Springer Berlin
Heidelberg, 2007.
[26] Sylvain Schmitz. An experimental ambiguity detection tool. Scienceof Computer Programming, 75(1–2):71–84, 2010. Special Issue on
ETAPS 2006 and 2007 Workshops on Language Descriptions, Tools,
and Applications (LDTA ’06 and ’07).
[27] Friedrich Wilhelm Schröer. AMBER, an ambiguity checker for contextfree grammars. Technical report, Fraunhofer Institute for Computer
Architecture and Software Technology, 2001.
[28] Masaru Tomita, editor. Generalized LR Parsing. Springer US, 1991.
ISBN 978-1-4613-6804-5.
[29] Naveneetha Vasudevan and Laurence Tratt. Detecting ambiguity inprogramming language grammars. In Proc. 6th Int’l Conf. on Software
Language Engineering, pp. 157–176, October 2013.
[30] Andreas Wenger and Michael Petter. CUP2 LR parser generator for
Java, 2014. Software beta release. At http://www2.in.tum.de/cup2.

Better tools that help language designers quickly find potential flaws
within language syntax can accelerate the design and implementation of programming languages and promote the use of parser
generators for problems involving custom data formats. Our methodfinds useful counterexamples for faulty grammars, and evaluation of
the implementation shows that the method is effective and practical.
This paper suggests that the undecidability of ambiguity for contextfree grammars should not be an excuse for parser generators to givepoor feedback to their users.

Acknowledgments
Andrew Hirsch, Matthew Milano, Isaac Sheff, Owen Arden, Jed Liu,and Vivek Myers offered useful suggestions for the presentation.
Steve Blackburn and Ben Hardekopf helped with the review process.
This work was supported by Office of Naval Research grant
N00014-13-1-0089 and National Science Foundation grant 0964409.

References[1] Tadashi Ae. Direct or cascade product of pushdown automata. Journalof Computer and System Sciences, 14(2):257–263, 1977.
[2] Roland Axelsson, Keijo Heljanko, and Martin Lange. Analyzing
context-free grammars using an incremental SAT solver. In Automata,
Languages and Programming, volume 5126 of Lecture Notes in
Computer Science, pp. 410–422. Springer Berlin Heidelberg, 2008.
[3] H. J. S. Basten. Tracking down the origins of ambiguity in context-freegrammars. In Theoretical Aspects of Computing – ICTAC 2010, volume6255 of Lecture Notes in Computer Science, pp. 76–90. Springer Berlin
Heidelberg, 2010.
[4] H. J. S. Basten and T. van der Storm. AmbiDexter: Practical ambiguity
detection. In Proc. 10th IEEE Int’l Workshop on Source Code Analysis
and Manipulation (SCAM 2010), pp. 101–102, Sept 2010.
[5] H. J. S. Basten and J. J. Vinju. Faster ambiguity detection by grammar
filtering. In Proc. 10th Workshop on Language Descriptions, Tools andApplications, pp. 5:1–5:9, 2010.
[6] Hendrikus J. S. Basten and Jurgen J. Vinju. Parse forest diagnostics
with Dr. Ambiguity. In Software Language Engineering, volume 6940
of Lecture Notes in Computer Science, pp. 283–302. Springer Berlin
Heidelberg, 2012.
[7] Ira Baxter. What is the easiest way of telling whether a BNF grammar
is ambiguous or not? (answer). StackOverflow, July 2011. Retrieved
November 11, 2014.
[8] Ira D. Baxter, Christopher Pidgeon, and Michael Mehlich. DMS® :Program transformations for practical scalable software evolution. In
Proc. 26th Int’l Conf. on Software Engineering (ICSE), pp. 625–634,
May 2004.

10