In computer science, a Wirth–Weber relationship between a pair of symbols is necessary to determine if a formal grammar is a simple precedence grammar. In such a case, the simple precedence parser can be used. The relationship is named after computer scientists Niklaus Wirth and Helmut Weber.
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 a relationship remains in the same pivot.
Formal definition
Precedence relations computing algorithm
We will define three sets for a symbol:
The pseudocode for computing relations is:
RelationTable := ∅
For each production
For each two adjacent symbols in
add(RelationTable, ) add(RelationTable, ) add(RelationTable, ) add(RelationTable, ) where is the initial non terminal of the grammar, and $ is a limit marker add(RelationTable, ) where is the initial non terminal of the grammar, and $ is a limit marker
Examples
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
a Next to S
S Next to S
S Next to b
there is only one symbol, so no relation is added.