Wirth-Weber precedence relationship
Encyclopedia
The Wirth
Niklaus Wirth
Niklaus Emil Wirth is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. In 1984 he won the Turing Award for developing a sequence of innovative computer languages.-Biography:Wirth...

-Weber relationship between a pair of symbols is necessary to determine if a formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 is a Simple precedence grammar
Simple precedence grammar
A simple precedence grammar is a context-free formal grammar that can be parsed with a simple precedence parser.-Formal definition:G = is a simple precedence grammar if all the production rules in P comply with the following constraints:* There are no erasing rules * There are no useless rules A...

, and in such case the Simple precedence parser
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....

 can be used.

The goal is to identify the when the viable prefix
Viable prefix
The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. An equivalent definition of a viable prefix is that it is a prefix of right sentential form that does not continue past the right end of the rightmost handle of that...

es 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 we are still in the same pivot.

Formal definition





Precedence Relations Computing Algorithm

We will define three Sets for a symbol:



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
LL parser
An LL parser is a top-down parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence...






Note that 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




Note that and are used with sets instead of elements as they were defined, in this case you must add all the cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...

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
      • 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
    • there is only one symbol, so no relation is added.


precedence table:
S a b c $
S
a
b
c
$
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK