Wirth-Weber precedence relationship

Wirth-Weber precedence relationship

The Wirth-Weber relationship between a pair of symbols (V_t cup 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 the when the viable prefixes have the pivot and must be reduced. A gtrdot means that the pivot is found, a lessdot means that a potential pivot is starting, and a dot = means that we are still in the same pivot.

__TOC__

=Formal definition= G =

* X dot = Y iff egin{cases} A o alpha X Y eta in P \ A in V_n \ alpha , eta in (V_n cup V_t)^* \ X, Y in (V_n cup V_t) end{cases}

* X lessdot Y iff egin{cases} A o alpha X B eta in P \ B Rightarrow^+ Y gamma \ A, B in V_n \ alpha , eta, gamma in (V_n cup V_t)^* \ X, Y in (V_n cup V_t) end{cases}

* X gtrdot a iff egin{cases} A o alpha B Y eta in P \ B Rightarrow^+ gamma X \ Y Rightarrow^* a delta \ A, B in V_n \ alpha , eta, gamma, delta in (V_n cup V_t)^* \ X, Y in (V_n cup V_t) \ a in V_t end{cases}

=Precedence Relations Computing Algorithm=

We will define three Sets for a symbol:

* Head^+(X) = {Y|X Rightarrow^+ Y alpha }
* Tail^+(X) = {Y|X Rightarrow^+ alpha Y }
* Head^*(X) = (Head^+(X) cup { X }) cap 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"

The pseudocode for computing relations is:

* RelationTable := empty
* For each production A o alpha in P
** For each two adjacent symbols X Y in α
*** add(RelationTable,X dot = Y)
*** add(RelationTable,X lessdot Head^+(Y))
*** add(RelationTable,Tail^+(X) gtrdot Head^*(Y))
* add(RelationTable,$ lessdot Head^+(S)) where S is the initial non terminal of the grammar, and $ is a limit marker
* add(RelationTable,Tail^+(S) gtrdot $ ) where S is the initial non terminal of the grammar, and $ is a limit marker

"Note that lessdot and 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"

=Examples=

S o aSSb | c

precedence table:


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Simple precedence parser — In computer science, a Simple precedence parser is a type of bottom up parser for context free grammars that can be used only by Simple precedence grammars.The implementation of the parser is quite similar to the generic bottom up parser. A stack …   Wikipedia

  • Niklaus Wirth — Niklaus E. Wirth Born February 15, 1934 (1934 02 15) (age 77) …   Wikipedia

  • international relations — a branch of political science dealing with the relations between nations. [1970 75] * * * Study of the relations of states with each other and with international organizations and certain subnational entities (e.g., bureaucracies and political… …   Universalium

  • UNITED STATES OF AMERICA — UNITED STATES OF AMERICA, country in N. America. This article is arranged according to the following outline: introduction Colonial Era, 1654–1776 Early National Period, 1776–1820 German Jewish Period, 1820–1880 East European Jewish Period,… …   Encyclopedia of Judaism

  • List of community topics — This List of community topics is intended to be a comprehensive listing of topics, categories and other resources related to community in the broadest sense possible. Community types Community, the human community: * World community, the global… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”