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 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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.