Shift-resolve parsing - questions

Question

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.

Construction

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.

Questions

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 :)

Answer 1

Check if this is discussed in the encyclopaedic D. Grune, C. J. H. Jacobs, "Parsing Techniques: a Practical Guide" (Spinger, 2008). If not, perhaps it is similar enough to a technique discussed.