编译原理：算符优先分析

1，算符优先文法

算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约。也就是说，算符优先分析法不是一种规范归约法。所谓【算符优先分析法】就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”进行归约的一种方法。

【算符文法】一个文法，如果它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：...QR... ，则我们称该文法为算符文法。

约定：

  • a,b 代表任意终结符。
  • P,Q,R 代表任意非终结符号。
  • '...' 代表由终结符和非终结符组成的任意序列，包括空字。

假定 G 是一个不含 \varepsilon 产生式的算符文法。对于任意一对终结符 a,b，我们说：

  • a=b，当且仅当文法 G 中含有形如 P\rightarrow ...ab... 或 P\rightarrow ...aQb... 的产生式。
  • a<b，当且仅当文法 G 中含有形如 P\rightarrow ...aR... 的产生式，而 R\overset{+ }{\Rightarrow}b... 或 R\overset{+ }{\Rightarrow}Qb... 。
  • a>b，当且仅当文法 G 中含有形如 P\rightarrow ...Rb... 的产生式，而 R\overset{+ }{\Rightarrow}...a 或 R\overset{+ }{\Rightarrow}...aQ 。

如果一个算法文法 G 中的任何终结符对 (a,b) 至多满足下述三关系之一：

a<b,a=b,a>b

则称 G 是一个算符优先文法。

FIRSTVT推出的第一个终结符集合：

  • 若产生式 P\rightarrow a... 或 P\rightarrow Ra... ，则 a \in FIRSTVT(P)
  • 若 a\in FIRSTVT(R)，且有产生式 P\rightarrow R...，则 a\in FIRSTVT(P) 。

LASTVT：LASTVT(P)=\left \{ a|P\overset{+ }{\Rightarrow}...a\,\,or\,\,P\overset{+ }{\Rightarrow}...aQ,a\in V_T,Q\in V_N \right \} 

可用下面规则构造集合 LASTVT(P) ：

  • 若有产生式 P\rightarrow ...a\,\,or\,\,P\rightarrow ...aQ，则 a\in LASTVT(P) ；
  • 若 a\in LASTVT(Q)，且有产生式 P\rightarrow ...Q，则 a\in LASTVT(P) 。

2，优先表构造

优先关系表的构造算法：

  • 检查 G 的每个候选式，若有 P\rightarrow ...aQb... 或 P\rightarrow ...ab... 的产生式，则置 a=b 。
  • 若 G 中有形如 ...aP... 的候选项，则对于所有的 b\in FIRSTVT(P)，有 a<b 。
  • 若 G 中有形如 ...Pb... 的候选式，则对于所有的 a\in LASTVT(P)，有 a>b 。

先行后列

3，算符优先文法

素短语：至少含有一个终结符的短语（且不能拆分成最小）

  • 移进：当栈顶终结符 ＜ 或 ＝ 当前输入符号时。
  • 归约：当栈顶终结符 ＞ 当前输入符号时，在栈中寻找最左素短语进行归约。
  • 接受：当栈顶终结符 ＝ 当前输入符号＝‘#’  时，分析成功结束。
  • 出错：当栈顶终结符与当前输入符号没有优先关系时。

【例子】

分析：i1+i2*i3
顺序已分析未分析操作解释
1#i+i*i##<i移进i
2#i+i*i#i>+归约F→i
3#F+i*i##<+移进+
4#F+i*i#+<i移进i
5#F+i*i#i>*归约 F→i
6#F+F*i#+<*移进*
7#F+F*i#*<i移进i
8#F+F*i#i>#归约 F→i
9#F+F*F#*>#归约T→T*F
10#F+T#+>#归约 E→E+T
11#E##=#接受