Wirth–Weber precedence relationship

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The WirthWeber 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.

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

Formal definition[edit]

Precedence relations computing algorithm[edit]

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

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 between the sets/elements

Examples[edit]

  • 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
$