算符优先分析法(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之间未必一定有优先关系
故=、<、>不同于关系运算符“等于”、“小于”、“大于”