I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been attempting to grasp the construction algorithm more intuitively. I believe I succeeded (this presentation was the source of the ah-ha moment), but a verification of correctness from someone either familiar with the technique or the terminology contained therein would be greatly appreciated.

I'm going to describe my take on the solution (if it's correct, I believe it could be of help to other people attempting to understand the technique) and ask additional questions afterwards. To ensure there's no misunderstanding, I'm going to use the following standard notation: $a, b, c, ... \in T$, $A, B, C, ... \in N$, $... X, Y, Z \in N \cup T$, $\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$ and, as in the paper, $A \xrightarrow{i} \omega$ to denote rule number $i$. However, I'll probably use different names for concepts than the original paper.

Also, throughout the description, the equivalence relation $\kappa_0$ is used.


There are two kinds of items inside the parsing automaton: simple LR(0) items of the form $A \xrightarrow{i} \alpha \bullet \beta$ which I call shift items and items of the form $A \xrightarrow{i} \alpha \bullet \beta, m, n$ which I call resolve items; these tell the parser to push $n$ symbols back the input stream and then reduce by rule number $m$ upon the first symbol of $\beta$.

The grammar is augmented with the rule $S' \xrightarrow{0} S \$$ and the construction starts with the shift item $S' \xrightarrow{0} \bullet S \$ $ in the initial state.

Now, to construct the automaton, decide between these alternatives for each item in a state $q$:

  1. If the item is a shift item $A \xrightarrow{i} \alpha \bullet \beta$, there will be a transition $q \xrightarrow{X} q'$ in the automaton, where $X$ is the first symbol of $\beta$.

  2. If the item is a finished shift item $A \xrightarrow{i} \omega \bullet$, add a resolve item $B \xrightarrow{j} \alpha A \bullet \beta, i, 0$ for each rule $B \xrightarrow{j} \alpha A \beta$.

  3. If the item is a resolve item $A \xrightarrow{i} \alpha \bullet \beta, m, n$, let $X$ be the first symbol of $\beta$. If $X \in N$, add a shift item $X \xrightarrow{j} \bullet \omega$ for each rule $X \xrightarrow{j} \omega$. If other items than $A \xrightarrow{i} \alpha \bullet \beta, m, n$ have $X$ as their dot lookahead, add a transition $q \xrightarrow{X} q'$ to the automaton. Every resolve item $C \xrightarrow{i} \alpha \bullet X \beta, m, n$ in $q$ will result in a resolve item $C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$ in $q'$.

  4. If the item is a resolve item $A \xrightarrow{i} \omega \bullet, m, n$ it won't contribute any lookahead information and can be discarded, but first add a resolve item $B \xrightarrow{j} \alpha A \bullet \beta, m, n$ for each rule $B \xrightarrow{j} \alpha A \beta$.

This is, of course, just a sketch; actually, a closure of the state must be calculated first and only then can we deal with transitions/shifts and resolutions.

Transforming the automaton into a shift-resolve parsing table is trivial afterwards; just, as a minor variation, the authors of the paper interpret a resolution $r_{0,0}$ as the accept action. Given the resulting automaton, I found it handier to simply treat a shift of $\$$ as the accept action.


The first one is, obviously, whether the process described above is correct.

The second one is about the equivalence relations. I can only guess that the equivalence relation $\kappa$ is what's responsible for deciding which resolve items are brought in when a finished shift item has been seen. $\kappa_0$ seems to result in lookahead strikingly similar to the $FOLLOW_{LM}$ sets of LSLR parsers. The paper describes a "finer equivalence relation" on page 11; is there a way to interpret this relation in intuitive terms? Are there other relations known?

And the final one is about conflict resolution. The paper describes well what constitutes an inadequacy in a shift-resolve automaton; is there a way of resolving these inadequacies, similar to ways of resolving conflicts in a traditional LR parser? Could something like yacc-style conflict resolution via precedence and associativity be implemented in a ShRe parser generator?

Thanks if you read all this and any answers will be greatly appreciated :)

  • $\begingroup$ suggest migrating this question to cstheory. as for the paper, it seems to be a very complex algorithm that "probably"(?) hasnt been implemented by anyone. the main idea seems to be to combine arbitrary lookahead but also with linear time parsing...? but how many applications would be ok with a simpler, more standard, superlinear algorithm? any idea, what application would work better with this approach? do you have one or know of one? $\endgroup$ – vzn Feb 28 '13 at 22:58
  • $\begingroup$ A very nice theoretical exercise (though I did not look at the technicalities). Given that the full power of LR(k) is often not even used, one may wonder about the practical impact. I see 2 problems with this kind of work: (1) since the algorithm gets more complex, is it still possible for the human mind to twiddle the grammar and understand the consequences, when it happens not to work. It is a frequent fact that highly sophisticated techniques are very rewarding when they work, but make things worse when they do not. (2) will it be linear in cases when general CF algorithms are not linear. $\endgroup$ – babou Apr 11 '14 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.