# Wirth–Weber precedence relationship

The WirthWeber 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 {\dot {=}}}$ means that we are still in the same pivot.

## Formal definition

${\displaystyle G=}$

• ${\displaystyle X{\dot {=}}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}}}$
• ${\displaystyle 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}}}$
• ${\displaystyle 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}}}$

## Precedence relations computing algorithm

We will define three sets for a symbol:

• ${\displaystyle \mathrm {Head} ^{+}(X)=\{Y\mid X\Rightarrow ^{+}Y\alpha \}}$
• ${\displaystyle \mathrm {Tail} ^{+}(X)=\{Y\mid X\Rightarrow ^{+}\alpha Y\}}$
• ${\displaystyle \mathrm {Head} ^{*}(X)=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}}$

Note that 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

Note that Head+(X) and Tail+(X) are ${\displaystyle \emptyset }$ if X is a terminal.

The pseudocode for computing relations is:

• RelationTable := ${\displaystyle \emptyset }$
• For each production ${\displaystyle A\to \alpha \in P}$
• For each two adjacent symbols X Y in α
• add(RelationTable,${\displaystyle X{\dot {=}}Y}$)
• add(RelationTable,${\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}$)
• add(RelationTable,${\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}$)
• add(RelationTable,${\displaystyle \\lessdot Head^{+}(S)}$) where S is the initial non terminal of the grammar, and $is a limit marker • add(RelationTable,${\displaystyle \mathrm {Tai} l^{+}(S)\gtrdot \}$) where S is the initial non terminal of the grammar, and$ is a limit marker

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

precedence table:

 S a b c $S ${\displaystyle {\dot {=}}}$ ${\displaystyle \lessdot }$ ${\displaystyle {\dot {=}}}$ ${\displaystyle \lessdot }$ a ${\displaystyle {\dot {=}}}$ ${\displaystyle \lessdot }$ ${\displaystyle \lessdot }$ b ${\displaystyle \gtrdot }$ ${\displaystyle \gtrdot }$ ${\displaystyle \gtrdot }$ ${\displaystyle \gtrdot }$ c ${\displaystyle \gtrdot }$ ${\displaystyle \gtrdot }$ ${\displaystyle \gtrdot }$ ${\displaystyle \gtrdot }$$ ${\displaystyle \lessdot }$ ${\displaystyle \lessdot }$