Operator Precedence Functions
The operator precedence parsers
never stores the table of precedence relations
Generally, this table is encoded
by two functions f and g, known as precedence functions which map terminal
symbols to integers
For any terminals a and b the two
functions f and g is defined as
f(a)
< g(b) whenever a <. b
f(a)
= g(b) whenever a $\overset{.}{\mathop{=}}\,$ b
f(a)
> g(b) whenever a .> b
After f and g are defined, the
precedence relation between a and b can be determined by a numerical comparison
between f(a) and g(b)
Computing Precedence Functions
- Create symbols fa and gb for each a that is a terminal or $
- Partition the created symbols into as many groups as possible, in such a way that if a $\overset{.}{\mathop{=}}\,$ b, then fa and gb are in the same group. Note that we may have to put symbols in the same group even if they are not related by $\overset{.}{\mathop{=}}\,$ . For example, if a $\overset{.}{\mathop{=}}\,$ b and c $\overset{.}{\mathop{=}}\,$ b, then fa and fc must be in the same group, since they are both in the same group as gb. If in addition c $\overset{.}{\mathop{=}}\,$ d may not hold
- Create a directed graph whose nodes are the groups found in (2). For any a and b, if a <.b, place an edge from the group of gb to the group of fa. If a .> b, place an edge from the group of fa to that gb. Note that an edge or path from fa to gb means that f(a) must exceed g(b); a path from gb to fa means that g(b) must exceed f(a)
- If the graph constructed in (3) has a cycle, then no precedence function exists. If there are no cycles, let f(a) be the length of the longest path beginning at the group of fa; let g(a) be the length of the longest path from the group of ga
Consider the grammar,
E →
E + E | E * E | id and its precedence relations table
id
|
+
|
*
|
$
|
|
id
|
.>
|
.>
|
.>
|
|
+
|
<.
|
.>
|
<.
|
.>
|
*
|
<.
|
.>
|
.>
|
.>
|
$
|
<.
|
<.
|
<.
|
Now the precedence and functions are
+
|
*
|
id
|
$
|
|
f
|
2
|
4
|
4
|
0
|
g
|
1
|
3
|
5
|
0
|
