MENU

【编译原理】算符优先文法 OPG

June 2, 2020 • Read: 721 • 编程之路,编译原理

算符优先分析法(OPG):它只考虑算符(终结符)之间的优先关系,分析扫描每个归约式的算符间优先关系。

算符文法

即它的任意产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算符文法,那么只要它的任一对终结符都至多只满足 >, =, < 关系的其中一种,则称g是一个 算符优先文法 。

两个相继出现的终结符之间归约的优先关系有三种:

  • a 的优先级 高于 b 记为:a ●> b,
  • a 的优先级 等于 b 记为:a =● b,
  • a 的优先级 低于 b 记为:a <● b,

FIRSTVT集:FIRSTVT(P)={a|P=>a…,或P=>Qa…,a属于VT}

LASTVT集:LASTVT(P)={a|P=>...a,或P=>…aQ,a含于VT}

算符优先关系表的构造

文法案例:

E→E+T|T
T→T*F|F
F→(E)|i

终结符之间的优先关系

对算符文法G, a,b属于VT 定义

(1)a=b: G中有P→. . .ab. . .或P→. . .aQb. . .

(2)a<b: G中有P→. . .aQ. . .且Q=>b…或Q=>Rb...

(3)a>b: G中有P→. . .Qb. . . 且Q=>. ..a或Q=>…aR

算符优先关系表的构造

(1) 在文法中添加E→#E#

E→#E#
E→E+T|T
T→T*F|F
F→(E)|i

(2) 求出FIRSTVT和LASTVT集

(3) 找出所有终结符,并画出关系表的结构

(4) 从文法中找出形为aQb(终结符+非终结符+终结符)和ab(终结符+终结符)的部分,本例中为(E)和#E#,然后在(和)与#和#相应的表格填=。

(5) 从文法中找出形为aQ(终结符+非终结符)的部分,a与Q的FIRSTVT集合中每一个元素在表格中的交叉点填小于号。

i.找出形为aQ的部分

ii.填小于号(终结符为竖排,非终结符中的元素为横排,以横排为基准填符号)

(6) 从文法中找出形为Qa(非终结符+终结符)的部分, Q的LASTVT集合中每一个元素与a在表格中的交叉点填大于号。

i.找出形如Qa的部分

ii.填小于号(终结符为竖排,非终结符中的元素为横排,以横排为基准填符号)

(7) 合并后的结果为

从上表可知:

(1)相同终结符之间的优先关系未必是=

(2)有a<b,未必有b>a

(3)a、b之间未必一定有优先关系

故=、<、>不同于关系运算符“等于”、“小于”、“大于”

- - - 结束 - - -
  • 文章标题:【编译原理】算符优先文法 OPG
  • 文章链接:https://blog.canye365.cn/archives/319.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 10, 2021