Wirth–Weber precedence relationship

The 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, and in such case the simple precedence parser can be used.

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

Formal definition

$G=<V_{n},V_{t},S,P>$

$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}}$
$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}}$

Precedence relations computing algorithm

We will define three sets for a symbol:

$\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}$

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 $\empty$ if X is a terminal.

The pseudocode for computing relations is:

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

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

$S\to aSSb|c$

Head+(a) = $\empty$
Head+(S) = { a, c}
Head+(b) = $\empty$
Head+(c) = $\empty$
Tail+(a) = $\empty$
Tail+(S) = { b, c}
Tail+(b) = $\empty$
Tail+(c) = $\empty$
Head*(a) = a
Head*(S) = { a, c}
Head*(b) = b
Head*(c) = c
$S\to aSSb$
- a Next to S
  - a ${\dot {=}}$ S
  - a $\lessdot$ Head+(S)
    - a $\lessdot$ a
    - a $\lessdot$ c
- S Next to S
  - S ${\dot {=}}$ 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 ${\dot {=}}$ 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:

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

This article is issued from Wikipedia - version of the 3/17/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.