Wirth–Weber precedence relationship

In computer science, a Wirth–Weber relationship between a pair of symbols (Vt∪Vn) 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.

## Contents

* 1 Formal definition
* 2 Precedence relations computing algorithm
* 3 Examples
* 4 Further reading

## Formal definition

G=⟨Vn,Vt,S,P⟩

X≐Y⟺{A->αXYβ∈PA∈Vnα,β∈(Vn∪Vt)*X,Y∈(Vn∪Vt)X⋖Y⟺{A->αXBβ∈PB⇒+YγA,B∈Vnα,β,γ∈(Vn∪Vt)*X,Y∈(Vn∪Vt)X⋗Y⟺{A->αBYβ∈PB⇒+γXY⇒*aδA,B∈Vnα,β,γ,δ∈(Vn∪Vt)*X,Y∈(Vn∪Vt)a∈Vt

## Precedence relations computing algorithm

We will define three sets for a symbol:

Head+(X)={Y∣X⇒+Yα}Tail+(X)={Y∣X⇒+αY}Head*(X)=(Head+(X)∪{X})∩Vt

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
* For each two adjacent symbols X Y in α
* add(RelationTable, X≐Y)
* add(RelationTable, X⋖Head+(Y))
* add(RelationTable, Tail+(X)⋗Head*(Y))
* add(RelationTable, $⋖Head+(S)) where S is the initial non terminal of the grammar, and $ is a limit marker
* add(RelationTable, Tail+(S)⋗$) 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

S->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->aSSb
* 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
Sabc$S≐⋖≐⋖a≐⋖⋖b⋗⋗⋗⋗c⋗⋗⋗⋗$⋖⋖

## Further reading

* Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling

* v
* t
* e

Niklaus Wirth

Software|

| Programming
languages|

* Active Oberon
* ALGOL W
* Euler
* Lola
* Pascal
* Modula
* Modula-2
* Oberon
* Oberon-2
* Oberon-07
* Object Pascal

Derivative works|

* Alma-0
* BlackBox Component Builder
* Component Pascal
* Delphi
* Modula-2+
* Modula-3
* Object Oberon
* Zonnon

Operating systems|

* Bluebottle OS
* Oberon System

Formalisms|

* Wirth's law
* Wirth syntax notation
* Wirth–Weber precedence relationship

Books|

* Algorithms + Data Structures = Programs

Hardware|

* Ceres
* Lilith

Workplaces|

* ETH Zurich
* Stanford University
* University of Zurich
* Xerox PARC

Collaborators|

* Luca Cardelli
* Jürg Gutknecht
* Tony Hoare
* Larry Tesler

Awards|

* Turing Award
* SIGPLAN Programming Languages Achievement Award
* Fellow of the Computer History Museum
* Marcel Benoist Prize

* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Wirth–Weber precedence relationship. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Wirth–Weber_precedence_relationship&oldid=308328"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template