Finding Counterexamples from Parsing Conflicts

How the CUP parser generator explains conflicts.

I found the abstract of [Isradisaikul, Myers, Finding Counterexamples from Parsing Conflicts, 2015] quite exciting. After reading the paper, I think it delivers what the title and the abstract promise: better errors for parser generators. If you ever worked with a LR parser generator, then you know that sometimes it reports shift/reduce or reduce/reduce conflicts. The error usually points to a couple of grammar rules and says ‘here is the problem’. I never feel like I understand what exactly the problem is until I have an example of what could go wrong. So, once I see the warning/error from the parser generator, I try to come up with examples. Well, according to this paper, the CUP parser generator gives you examples. How cool is that?

Still, I'm not completely enthusiastic about the paper. I think the algorithm could be better described. For example, I would have preferred to see pseudocode. I realize that it is not easy to add pseudocode, and I realize that the pseudocode could be too large to be useful. But. I think that adding pseudocode would've forced the presentation to be more precise, which is a good thing. I think that striving for small pseudocode would've forced isolating the core idea, which is a good thing. The heuristics that embellish the core idea could remain in prose, as they are now.

Now let's get technical, a bit. Recall that the ambiguity problem is in P for NFAs (nondeterministic finite automata), and undecidable for CFGs (context free grammars).

The ambiguity problem for NFAs asks whether there are two runs that accept the same word. To solve it, we explore pairs $(q_1,q_2)$ of states that can be reached by the same word. For pairs with $q_1=q_2$ we also care whether they were reached through distinct runs. Formally, we define a graph that has a transition $(q_1,q_2,b) \to (q'_1,q'_2,b')$ when the NFA has transitions $t_1 = \bigl(q_1 \stackrel{\ell}{\to} q'_1\bigr)$ and $t_2 = \bigl(q_2 \stackrel{\ell}{\to} q'_2\bigr)$ for some letter $\ell$ and $b'=b \lor (t_1 \ne t_2)$. The third component is a boolean that keeps track of whether the runs have diverged. We then ask if there is a path $(q,q,0) \leadsto (q',q',1)$ with $q$ initial and $q'$ final. We answer this question with BFS (breadth first search). If the NFA has $m$ transitions and $n$ states, then the graph we defined has $\le 2m^2$ edges and $2n^2$ vertices. Thus, the BFS takes $O(m^2+n^2)$ time. This, by the way, you can find in [Even, On Information Lossless Automata of Finite Order, 1965].

(I have posted this previously as a problem on my blog and on SPOJ. I believe my reference solution for SPOJ is slightly different from what I describe above, but I'm too lazy to check.)

The paper by Isradisaikul and Myers essentially uses the same trick, of running two copies of the machine in parallel. Except in their case, the machine is not an NFA but an LALR parser. If you wonder how could the problem be undecidable, the answer is simple: a LALR parser has an infinite number of configurations, because of the stack. Now, I should say that many other papers are based on the same trick of running two copies in parallel. What Isradisaikul and Myers do is that they exploit a bit the structure of a LALR parser to squeeze some efficiency.

One thing they do is that they distinguish nonunifying from unifying counterexamples. In the terminology from above, a nonunifying counterexample is a word that corresponds to a path $(q,q,0) \leadsto ({\cdot},{\cdot},1)$ with $q$ initial; a unifying counterexample is a word that corresponds to a path $(q,q,0) \leadsto (q',q',1)$ with $q$ initial and $q'$ final. The idea is that in some cases you can find where the paths diverge (the conflict) but it's difficult to find the continuation that gives two different parse trees. In fact, they give up after some timeout. (Another way to describe the difference is to say that a unifying counterexample remains a counterexample even for a GLR parser.)

There are other optimizations they propose. But, frankly, I didn't parse those carefully. So, if you want to add better error messages to your favorite parser generator, then you'll have to read the paper yourself, not just this post. :)