Wirth–Weber Precedence Relationship

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 $\doteq$ means that a relationship remains in the same ''pivot''.

Formal definition

: $G = \langle V_n, V_t, S, P \rangle$
:: $\begin X \doteq Y &\iff \begin 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 \\ X \lessdot Y &\iff \begin 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 \\ X \gtrdot Y &\iff \begin 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 \end$

Precedence relations computing algorithm

We will define three sets for a symbol:
: $\begin \mathrm^+(X) &= \\\ \mathrm^+(X) &= \\\ \mathrm^*(X) &= (\mathrm^+(X) \cup \) \cap V_t \end$
::
::

The pseudocode for computing relations is:

* RelationTable := ∅
* For each production $A \to \alpha \in P$
** For each two adjacent symbols in
*** add(RelationTable, $X \doteq Y$)
*** add(RelationTable, $X \lessdot \mathrm^+(Y)$)
*** add(RelationTable, $\mathrm^+(X) \gtrdot \mathrm^*(Y)$)
* add(RelationTable, $\$ \lessdot \mathrm^+(S)$) where is the initial non terminal of the grammar, and $ is a limit marker
* add(RelationTable, $\mathrm^+(S) \gtrdot \$$) where is the initial non terminal of the grammar, and $ is a limit marker

:

Examples

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

;precedence table: $\begin & 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$

Further reading

*

{{DEFAULTSORT:Wirth-Weber Precedence Relationship
Formal languages