G
=
⟨
V
n
,
V
t
,
S
,
P
⟩
{\displaystyle G=\langle V_{n},V_{t},S,P\rangle }
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
⋗
Y
⟺
{
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
{\displaystyle {\begin{aligned}X\doteq 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 Y&\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}}\end{aligned}}}
Precedence relations computing algorithm
edit
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
{\displaystyle {\begin{aligned}\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}\end{aligned}}}
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 .
Head+ (X ) and Tail+ (X ) are ∅ if X is a terminal.
The pseudocode for computing relations is:
RelationTable := ∅
For each production
A
→
α
∈
P
{\displaystyle A\to \alpha \in P}
For each two adjacent symbols X Y in α
add(RelationTable,
X
≐
Y
{\displaystyle X\doteq Y}
)
add(RelationTable,
X
⋖
H
e
a
d
+
(
Y
)
{\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}
)
add(RelationTable,
T
a
i
l
+
(
X
)
⋗
H
e
a
d
∗
(
Y
)
{\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}
)
add(RelationTable,
$
⋖
H
e
a
d
+
(
S
)
{\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}
) where S is the initial non terminal of the grammar, and $ is a limit marker
add(RelationTable,
T
a
i
l
+
(
S
)
⋗
$
{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}
) where S is the initial non terminal of the grammar, and $ is a limit marker
⋖
{\displaystyle \lessdot }
and
⋗
{\displaystyle \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.
S
→
a
S
S
b
|
c
{\displaystyle S\to aSSb|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
{\displaystyle S\to aSSb}
a Next to S
a
≐
S
{\displaystyle a\doteq S}
a
⋖
H
e
a
d
+
(
S
)
{\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}
a
⋖
a
{\displaystyle a\lessdot a}
a
⋖
c
{\displaystyle a\lessdot c}
S Next to S
S
≐
S
{\displaystyle S\doteq S}
S
⋖
H
e
a
d
+
(
S
)
{\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}
S
⋖
a
{\displaystyle S\lessdot a}
S
⋖
c
{\displaystyle S\lessdot c}
T
a
i
l
+
(
S
)
⋗
H
e
a
d
∗
(
S
)
{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}
b
⋗
a
{\displaystyle b\gtrdot a}
b
⋗
c
{\displaystyle b\gtrdot c}
c
⋗
a
{\displaystyle c\gtrdot a}
c
⋗
c
{\displaystyle c\gtrdot c}
S Next to b
S
≐
b
{\displaystyle S\doteq b}
T
a
i
l
+
(
S
)
⋗
H
e
a
d
∗
(
b
)
{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}
b
⋗
b
{\displaystyle b\gtrdot b}
c
⋗
b
{\displaystyle c\gtrdot b}
S
→
c
{\displaystyle S\to c}
there is only one symbol, so no relation is added.
precedence table
S
a
b
c
$
S
≐
⋖
≐
⋖
a
≐
⋖
⋖
b
⋗
⋗
⋗
⋗
c
⋗
⋗
⋗
⋗
$
⋖
⋖
{\displaystyle {\begin{array}{c|ccccc}&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{array}}}
S
→
a
|
a
T
|
[
S
]
{\displaystyle S\to a|aT|[S]}
T
→
b
|
b
T
{\displaystyle T\to b|bT}
Head+ ( S ) = { a, [ }
Head+ ( a ) = ∅
Head+ ( T ) = { b }
Head+ ( [ ) = ∅
Head+ ( ] ) = ∅
Head+ ( b ) = ∅
Tail+ ( S ) = { a, T, ], b }
Tail+ ( a ) = ∅
Tail+ ( T ) = { b, T }
Tail+ ( [ ) = ∅
Tail+ ( ] ) = ∅
Tail+ ( b ) = ∅
Head* ( S ) = { a, [ }
Head* ( a ) = a
Head* ( T ) = { b }
Head* ( [ ) = [
Head* ( ] ) = ]
Head* ( b ) = b
S
→
a
T
{\displaystyle S\to aT}
a Next to T
a
≐
T
{\displaystyle a\doteq T}
a
⋖
H
e
a
d
+
(
T
)
{\displaystyle a\lessdot \mathrm {Head} ^{+}(T)}
a
⋖
b
{\displaystyle a\lessdot b}
S
→
[
S
]
{\displaystyle S\to [S]}
[ Next to S
[
≐
S
{\displaystyle [\doteq S}
[
⋖
H
e
a
d
+
(
S
)
{\displaystyle [\lessdot \mathrm {Head} ^{+}(S)}
[
⋖
a
{\displaystyle [\lessdot a}
[
⋖
[
{\displaystyle [\lessdot [}
S Next to ]
S
≐
]
{\displaystyle S\doteq ]}
T
a
i
l
+
(
S
)
⋗
H
e
a
d
∗
(
]
)
{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])}
a
⋗
]
{\displaystyle a\gtrdot ]}
T
⋗
]
{\displaystyle T\gtrdot ]}
]
⋗
]
{\displaystyle ]\gtrdot ]}
b
⋗
]
{\displaystyle b\gtrdot ]}
T
→
b
T
{\displaystyle T\to bT}
b Next to T
b
≐
T
{\displaystyle b\doteq T}
b
⋖
H
e
a
d
+
(
T
)
{\displaystyle b\lessdot \mathrm {Head} ^{+}(T)}
b
⋖
b
{\displaystyle b\lessdot b}
precedence table
S
T
a
b
[
]
$
S
≐
≐
T
⋗
⋗
a
≐
⋖
⋗
⋗
b
≐
⋖
⋗
⋗
[
≐
⋖
⋖
]
⋗
⋗
$
≐
⋖
⋖
{\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}}
Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling