This article has multiple issues. Please help or discuss these issues on the talk page. (Learn how and when to remove these template messages)
This article does not cite any sources. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: – ···scholar·JSTOR(December 2009) (Learn how and when to remove this template message)
This article provides insufficient context for those unfamiliar with the subject. Please help by providing more context for the reader.(October 2009) (Learn how and when to remove this template message)
This article may be too technical for most readers to understand. Please to make it understandable to non-experts, without removing the technical details.(July 2012) (Learn how and when to remove this template message)
(Learn how and when to remove this template message)
The Wirth–Weber relationship between a pair of symbols is necessary to determine if a formal grammar is a simple precedence grammar, and in such case the simple precedence parser can be used. It 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.
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
For each two adjacent symbols X Y in α
add(RelationTable, )
add(RelationTable, )
add(RelationTable, )
add(RelationTable, ) where S is the initial non terminal of the grammar, and $ is a limit marker
add(RelationTable, ) where S is the initial non terminal of the grammar, and $ is a limit marker
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.
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.
precedence table
Further reading[]
Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling