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.
Formal definition
Precedence relations computing algorithm
We will define three sets for a symbol:
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
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
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
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
S Next to S
S Next to b
there is only one symbol, so no relation is added.
precedence table
Further reading
Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling