The Wirth–Weber relationship between a pair of symbols
(
V
t
∪
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
⋗
means that the pivot is found, a
⋖
means that a potential pivot is starting, and a
=
˙
means that we are still in the same pivot.
G
=<
V
n
,
V
t
,
S
,
P
>
X
=
˙
Y
⟺
{
A
→
α
X
Y
β
∈
P
A
∈
V
n
α
,
β
∈
(
V
n
∪
V
t
)
∗
X
,
Y
∈
(
V
n
∪
V
t
)
X
⋖
Y
⟺
{
A
→
α
X
B
β
∈
P
B
⇒
+
Y
γ
A
,
B
∈
V
n
α
,
β
,
γ
∈
(
V
n
∪
V
t
)
∗
X
,
Y
∈
(
V
n
∪
V
t
)
X
⋗
a
⟺
{
A
→
α
B
Y
β
∈
P
B
⇒
+
γ
X
Y
⇒
∗
a
δ
A
,
B
∈
V
n
α
,
β
,
γ
,
δ
∈
(
V
n
∪
V
t
)
∗
X
,
Y
∈
(
V
n
∪
V
t
)
a
∈
V
t
We will define three sets for a symbol:
H
e
a
d
+
(
X
)
=
{
Y
∣
X
⇒
+
Y
α
}
T
a
i
l
+
(
X
)
=
{
Y
∣
X
⇒
+
α
Y
}
H
e
a
d
∗
(
X
)
=
(
H
e
a
d
+
(
X
)
∪
{
X
}
)
∩
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
∅
if X is a terminal.
The pseudocode for computing relations is:
RelationTable :=
∅
For each production
A
→
α
∈
P
For each two adjacent symbols X Y in α
add(RelationTable,
X
=
˙
Y
)
add(RelationTable,
X
⋖
H
e
a
d
+
(
Y
)
)
add(RelationTable,
T
a
i
l
+
(
X
)
⋗
H
e
a
d
∗
(
Y
)
)
add(RelationTable,
$
⋖
H
e
a
d
+
(
S
)
) where S is the initial non terminal of the grammar, and $ is a limit marker
add(RelationTable,
T
a
i
l
+
(
S
)
⋗
$
) where S is the initial non terminal of the grammar, and $ is a limit marker
Note that
⋖
and
⋗
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
S
→
a
S
S
b
|
c
Head+(a) =
∅
Head+(S) = { a, c}
Head+(b) =
∅
Head+(c) =
∅
Tail+(a) =
∅
Tail+(S) = { b, c}
Tail+(b) =
∅
Tail+(c) =
∅
Head*(a) = a
Head*(S) = { a, c}
Head*(b) = b
Head*(c) = c
S
→
a
S
S
b
a Next to S
a
=
˙
S
a
⋖
Head+(S)
a
⋖
a
a
⋖
c
S Next to S
S
=
˙
S
S
⋖
Head+(S)
S
⋖
a
S
⋖
c
Tail+(S)
⋗
Head*(S)
b
⋗
a
b
⋗
c
c
⋗
a
c
⋗
c
S Next to b
S
=
˙
b
Tail+(S)
⋗
Head*(b)
b
⋗
b
c
⋗
b
S
→
c
there is only one symbol, so no relation is added.
precedence table:
