Operator Precedence Functions

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

1. Create symbols f_a and g_b for each a that is a terminal or $
2. Partition the created symbols into as many groups as possible, in such a way that if a $\overset{.}{\mathop{=}}\,$  b, then f_a and g_b 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 f_a and fc must be in the same group, since they are both in the same group as g_b. If in addition c $\overset{.}{\mathop{=}}\,$  d may not hold
3. 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 g_b to the group of f_a. If a .> b, place an edge from the group of f_a to that g_b. Note that an edge or path from f_a to g_b means that f(a) must exceed g(b); a path from g_b to f_a means that g(b) must exceed f(a)
4. 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 f_a; let g(a) be the length of the longest path from the group of g_a

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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.