编译器设计中的优先级函数是什么？

优先级表中任意两个运算符或符号之间的优先级关系可以转换为两个将终结符映射到整数的优先级函数 f 和 g。

• 如果 a <. b，则 f (a) <. g (b)
• 如果 a = b，则 f (a) =. g (b)
• 如果 a .> b，则 f (a) .> g (b)

这里 a、b 表示终结符。f (a) 和 g (b) 表示具有整数值的优先级函数。

优先级函数的计算

• 对于每个终结符 a，创建符号 f_a 和 g_a。
• 为每个符号创建一个节点。

               如果 a =. b，则 fa 和 gb 在同一组或节点中。

               如果 a =. b 和 c =. b，则 fa 和 fc 必须在同一组或节点中。

• (a) 如果 a <. b，则从 g_b 到 f_a 画一条边。

             (b) 如果 a .>b，则从 f_a 到 g_b 画一条边。

• 如果构造的图具有循环，则不存在优先级函数。
• 如果没有循环。

        (a) f_a = 从 f_a 组开始的最长路径的长度。

        (b) g_a = 从 g_a 组开始的最长路径的长度。

示例 1 - 为下表构建优先级图和优先级函数。

解决方案

步骤 1 - 创建符号

步骤 2 - 从给定表中可以看出，没有符号具有相同的优先级；因此，每个符号将保留在不同的节点中。

步骤 3 - 如果 a <. b，则从 f_a → g_a 创建一条边

              如果 a .>b，则从 g_b → f_a 创建一条边

由于 $ <. +,*, id。因此，从 g₊、g_*、g_id 到 f_s 画一条边

类似地 + <. ,∗, id。∴ 从 g_*、g_id 到 f₊ 画一条边

类似地 * <. id。因此，从 g_id 到 f_* 画一条边。

由于 +,*, id . > $ 因此，从 f₊、f_*、f_id 到 g_s 画一条边。

类似地 +,*, id . > +。从 f₊、f_*、f_id 到 g₊ 画一条边。

类似地 *, id . > *。从 f_*、f_id 到 g 画一条边。

组合所有边，我们得到

步骤 4 - 计算每个节点路径的最大长度，我们得到以下优先级函数

示例 2 - 为下表构建优先级图和优先级函数。

解决方案

由于我们有 (=.)。因此 f 和 g 将在同一组中。

优先级图的计算

优先级函数表的计算

由于 f_$ 和 g_$ 没有输出边，因此 f($ ) = g($ ) = 0。

由于 f 和 g 没有输出边，因此 f(( ) = g( )) = 0。

对于所有其他情况，计算从其开始的最长路径。

例如 -

取 f₊，

它有三条输出边并追踪其路径。

f₊ → g_$

f₊ → f₍

f₊ → g₊ → f₍ 和 f₊ → g₊ → f_$

选择最大长度的路径，长度为 2。

因此，f₊ = 2。计算 f 和 g 的所有路径，我们得到优先级表

Ginni

更新于： 2021 年 10 月 30 日

4K+ 次查看

开启您的 职业生涯

通过完成课程获得认证

开始