Wirth-Weber precedence relationship

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help Wikipedia by improving the introduction according to the guidelines laid out at Wikipedia:Guide to layout. You can discuss the issue on the talk page.

The Wirth-Webber relationship between a pair of symbols $(V_t \cup V_n)$ are necessary to determine if a formal grammar is a Simple precedence grammar, and in such case the Simple precedence parser can be used.

1 Formal definition
2 Precedence Relations Computing Algorithm
3 Examples

[edit] Formal definition

$G = < V n, V t, S, P >$

$X \dot = 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 \dot < 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 \dot > a \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}$

[edit] Precedence Relations Computing Algorithm

We will define three Sets for a symbol:

$Head^+(X) = \{Y|X \Rightarrow^+ Y \alpha \}$
$Tail^+(X) = \{Y|X \Rightarrow^+ \alpha Y \}$
$Head^*(X) = (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

The pseudocode for computing relations is:

RelationTable := $\empty$
For each production
- For each two adjacent symbols X Y in α
  - add(RelationTable, $X \dot = Y$ )
  - add(RelationTable, $X \dot < Head^+(Y)$ )
  - add(RelationTable, $Tail^+(X) \dot > Head^*(Y)$ )

Note that $\dot <$ and $\dot >$ 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