Wirth–Weber precedence relationship

The Wirth–Weber relationship between a pair of symbols ${\displaystyle (V_{t}\cup V_{n})}$ is necessary to determine if a formal grammar is a simple precedence grammar, and in such case the simple precedence parser can be used.

The goal is to identify when the viable prefixes have the pivot and must be reduced. A ${\displaystyle \gtrdot }$ means that the pivot is found, a ${\displaystyle \lessdot }$ means that a potential pivot is starting, and a ${\displaystyle \doteq }$ means that we are still in the same pivot.

Formal definition

${\displaystyle G=\langle V_{n},V_{t},S,P\rangle }$

${\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\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 XB\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 a&\iff {\begin{cases}A\to \alpha BY\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{aligned}}}$

Precedence relations computing algorithm

We will define three sets for a symbol:

${\displaystyle {\begin{aligned}\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{aligned}}}$

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 ${\displaystyle A\to \alpha \in P}$
  • For each two adjacent symbols X Y in α
    • add(RelationTable, ${\displaystyle X\doteq Y}$)
    • add(RelationTable, ${\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}$)
    • add(RelationTable, ${\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}$)
• add(RelationTable, ${\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}$) where S is the initial non terminal of the grammar, and $ is a limit marker
• add(RelationTable, ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}$) where S is the initial non terminal of the grammar, and $ is a limit marker

${\displaystyle \lessdot }$ and ${\displaystyle \gtrdot }$ 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

${\displaystyle S\to aSSb|c}$

• 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
• ${\displaystyle S\to aSSb}$
  • a Next to S
    • ${\displaystyle a\doteq S}$
    • ${\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle a\lessdot a}$
      • ${\displaystyle a\lessdot c}$
  • S Next to S
    • ${\displaystyle S\doteq S}$
    • ${\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}$
      • ${\displaystyle S\lessdot a}$
      • ${\displaystyle S\lessdot c}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}$
      • ${\displaystyle b\gtrdot a}$
      • ${\displaystyle b\gtrdot c}$
      • ${\displaystyle c\gtrdot a}$
      • ${\displaystyle c\gtrdot c}$
  • S Next to b
    • ${\displaystyle S\doteq b}$
    • ${\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}$
      • ${\displaystyle b\gtrdot b}$
      • ${\displaystyle c\gtrdot b}$
• ${\displaystyle S\to c}$
  • there is only one symbol, so no relation is added.

precedence table

${\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}$

Further reading

• Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling