编译原理:算符优先分析
·
1,算符优先文法
算符优先分析过程是自下而上的归约过程,但未必是严格的最左归约。也就是说,算符优先分析法不是一种规范归约法。所谓【算符优先分析法】就是定义算符之间的某种优先关系,借助于这种关系寻找“可归约串”进行归约的一种方法。
【算符文法】一个文法,如果它的任一产生式的右部都不含两个相继(并列)的非终结符,即不含如下形式的产生式右部: ,则我们称该文法为算符文法。
约定:
- 代表任意终结符。
- 代表任意非终结符号。
- 代表由终结符和非终结符组成的任意序列,包括空字。
假定 是一个不含 产生式的算符文法。对于任意一对终结符 ,我们说:
- ,当且仅当文法 中含有形如 或 的产生式。
- ,当且仅当文法 中含有形如 的产生式,而 或 。
- ,当且仅当文法 中含有形如 的产生式,而 或 。
如果一个算法文法 中的任何终结符对 至多满足下述三关系之一:
则称 是一个算符优先文法。
FIRSTVT推出的第一个终结符集合:
- 若产生式 或 ,则
- 若 ,且有产生式 ,则 。
LASTVT:
可用下面规则构造集合 :
- 若有产生式 ,则 ;
- 若 ,且有产生式 ,则 。
2,优先表构造
优先关系表的构造算法:
- 检查 的每个候选式,若有 或 的产生式,则置 。
- 若 中有形如 的候选项,则对于所有的 ,有 。
- 若 中有形如 的候选式,则对于所有的 ,有 。
先行后列
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 # #=# 接受
更多推荐
已为社区贡献6条内容
所有评论(0)