Wirth–Weber precedence relationship
Lua error in package.lua at line 80: module 'strict' not found.
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.
The goal is to identify the when the viable prefixes have the pivot and must be reduced. A Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
means that the pivot is found, a Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot means that a potential pivot is starting, and a means that we are still in the same pivot.
Formal definition
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): X \lessdot Y \iff \begin{cases} A \to \alpha X B \beta \in P \\ B \Rightarrow^+ Y \gamma \\ A, B \in V_n \\ \alpha , \beta, \gamma \in (V_n \cup V_t)^* \\ X, Y \in (V_n \cup V_t) \end{cases}
- Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): X \gtrdot a \iff \begin{cases} A \to \alpha B Y \beta \in P \\ B \Rightarrow^+ \gamma X \\ Y \Rightarrow^* a \delta \\ A, B \in V_n \\ \alpha , \beta, \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:
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,Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): X \lessdot \mathrm{Head}^+(Y)
- For each two adjacent symbols X Y in α
)
-
-
- add(RelationTable,Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \mathrm{Tail}^+(X) \gtrdot \mathrm{Head}^*(Y)
-
)
- add(RelationTable,Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): $ \lessdot Head^+(S)
) where S is the initial non terminal of the grammar, and $ is a limit marker
- add(RelationTable,Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \mathrm{Tai}l^+(S) \gtrdot $
) where S is the initial non terminal of the grammar, and $ is a limit marker
Note that Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
and Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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
- 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 Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
- a Next to S
Head+(S)
-
-
-
- a Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
-
-
a
-
-
-
- a Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
-
-
c
-
- S Next to S
- S S
- S Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
- S Next to S
Head+(S)
-
-
-
- S Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
-
-
a
-
-
-
- S Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot
-
-
c
-
-
- Tail+(S) Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
Head*(S)
-
-
-
- b Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
-
a
-
-
-
- b Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
-
c
-
-
-
- c Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
-
a
-
-
-
- c Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
-
c
-
- S Next to b
- S b
- Tail+(S) Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
- S Next to b
Head*(b)
-
-
-
- b Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
-
b
-
-
-
- c Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot
-
-
b
-
- there is only one symbol, so no relation is added.
precedence table:
S | a | b | c | $ | |
S | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot | |||
a | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot | |||
b | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | |
c | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \gtrdot | |
$ | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot | Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \lessdot |