Wirth–Weber precedence relationship explained

In computer science, a Wirth–Weber relationship between a pair of symbols

(V _{t} \cup V _{n)} is necessary to determine if a formal grammar is a simple precedence grammar. In such a case, the simple precedence parser can be used. The relationship is named after computer scientists Niklaus Wirth and Helmut Weber.

The goal is to identify when the viable prefixes have the pivot and must be reduced. A

\gtrdot means that the pivot is found, a \lessdot means that a potential pivot is starting, and a • eq means that a relationship remains in the same pivot.

Formal definition

G = \langle V _{n,} V _{t,} S, P \rangle \begin{align} X • eq 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 ⇒ ^{+} 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 ⇒ ^{+} \gamma X \ Y ⇒ ^{*} 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}

Precedence relations computing algorithm

We will define three sets for a symbol:

\begin{align} Head ^{+(X)} & = \{Y\mid X ⇒ ^{+} Y \alpha \}\\ Tail ^{+(X)} & = \{Y\mid X ⇒ ^{+} \alpha Y \}\\ Head ^{*(X)} & = ( Head ^{+(X)} \cup \{ X \}) \cap V _{t \end{align}}

The pseudocode for computing relations is:

• RelationTable := ∅
• For each production

A \to \alpha \in P

• • For each two adjacent symbols in
    • add(RelationTable,

X • eq Y )

• • • add(RelationTable,

X \lessdot Head ^{+(Y)} )

• • • add(RelationTable,

Tail ^{+(X)} \gtrdot Head ^{*(Y)} )

• add(RelationTable,

\$ \lessdot Head ^{+(S)} ) where is the initial non terminal of the grammar, and $ is a limit marker

• add(RelationTable,

Tail ^{+(S)} \gtrdot \$ ) where is the initial non terminal of the grammar, and $ is a limit marker

Examples

Example 1

S \to aSSb | c

• Head(a) = ∅
• Head(S) =
• Head(b) = ∅
• Head(c) = ∅
• Tail(a) = ∅
• Tail(S) =
• Tail(b) = ∅
• Tail(c) = ∅
• Head(a) = a
• Head(S) =
• Head(b) = b
• Head(c) = c

S \to aSSb

• • a Next to S

a • eq S a \lessdot Head ^{+(S)} a \lessdot a a \lessdot c

• • S Next to S

S • eq S S \lessdot Head ^{+(S)} S \lessdot a S \lessdot c Tail ^{+(S)} \gtrdot Head ^{*(S)} b \gtrdot a b \gtrdot c c \gtrdot a c \gtrdot c

• • S Next to b

S • eq b Tail ^{+(S)} \gtrdot Head ^{*(b)} b \gtrdot b c \gtrdot b S \to c

• • there is only one symbol, so no relation is added.

precedence table:

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

Example 2

S \to a | aT | [S] T \to b | bT

• Head(S) =
• Tail(a) = ∅
• Tail(T) =
• Tail(['') = ∅ * Tail{{sup|+}}('']) = ∅
• Tail(b) = ∅
• Head(S) =