The goal is to identify when the viable prefixes have the pivot and must be reduced. A [math]\displaystyle{ \gtrdot }[/math] means that the pivot is found, a [math]\displaystyle{ \lessdot }[/math] means that a potential pivot is starting, and a [math]\displaystyle{ \doteq }[/math] means that a relationship remains in the same pivot.
[math]\displaystyle{ G = \langle V_n, V_t, S, P \rangle }[/math]
[math]\displaystyle{ \begin{align}
X \doteq Y &\iff \begin{cases} A \to \alpha X Y \beta \in P \\ A \in V_n \\ \alpha , \beta \in (V_n \cup V_t)^* \\ X, Y \in (V_n \cup V_t) \end{cases} \\
X \lessdot Y &\iff \begin{cases} A \to \alpha X B \beta \in P \\ B \Rightarrow^+ Y \gamma \\ A, B \in V_n \\ \alpha , \beta, \gamma \in (V_n \cup V_t)^* \\ X, Y \in (V_n \cup V_t) \end{cases} \\
X \gtrdot Y &\iff \begin{cases} A \to \alpha B Y \beta \in P \\ B \Rightarrow^+ \gamma X \\ Y \Rightarrow^* a \delta \\ A, B \in V_n \\ \alpha , \beta, \gamma, \delta \in (V_n \cup V_t)^* \\ X, Y \in (V_n \cup V_t) \\ a \in V_t \end{cases}
\end{align} }[/math]
Precedence relations computing algorithm
We will define three sets for a symbol:
[math]\displaystyle{ \begin{align}
\mathrm{Head}^+(X) &= \{Y\mid X \Rightarrow^+ Y \alpha \}\\
\mathrm{Tail}^+(X) &= \{Y\mid X \Rightarrow^+ \alpha Y \}\\
\mathrm{Head}^*(X) &= (\mathrm{Head}^+(X) \cup \{ X \}) \cap V_t
\end{align} }[/math]
Head*(X) is X if X is a terminal, and if X is a non-terminal, Head*(X) is the set with only the terminals belonging to Head+(X). This set is equivalent to First-set or Fi(X) described in LL parser.:
Head+(X) and Tail+(X) are ∅ if X is a terminal.:
The pseudocode for computing relations is:
RelationTable := ∅
For each production [math]\displaystyle{ A \to \alpha \in P }[/math]
For each two adjacent symbols X Y in α
add(RelationTable, [math]\displaystyle{ X \doteq Y }[/math])
add(RelationTable, [math]\displaystyle{ X \lessdot \mathrm{Head}^+(Y) }[/math])
add(RelationTable, [math]\displaystyle{ \$ \lessdot \mathrm{Head}^+(S) }[/math]) where S is the initial non terminal of the grammar, and $ is a limit marker
add(RelationTable, [math]\displaystyle{ \mathrm{Tail}^+(S) \gtrdot \$ }[/math]) where S is the initial non terminal of the grammar, and $ is a limit marker
[math]\displaystyle{ \lessdot }[/math] and [math]\displaystyle{ \gtrdot }[/math] are used with sets instead of elements as they were defined, in this case you must add all the cartesian product between the sets/elements.:
Examples
[math]\displaystyle{ S \to aSSb | c }[/math]
Head+(a) = ∅
Head+(S) = {a, c}
Head+(b) = ∅
Head+(c) = ∅
Tail+(a) = ∅
Tail+(S) = {b, c}
Tail+(b) = ∅
Tail+(c) = ∅
Head*(a) = a
Head*(S) = {a, c}
Head*(b) = b
Head*(c) = c
[math]\displaystyle{ S \to aSSb }[/math]
a Next to S
[math]\displaystyle{ a \doteq S }[/math]
[math]\displaystyle{ a \lessdot \mathrm{Head}^+(S) }[/math]
[math]\displaystyle{ a \lessdot a }[/math]
[math]\displaystyle{ a \lessdot c }[/math]
S Next to S
[math]\displaystyle{ S \doteq S }[/math]
[math]\displaystyle{ S \lessdot \mathrm{Head}^+(S) }[/math]