5 自下而上的语法分析——优先分析法
目录
一、自下而上语法分析概述
自下而上语法分析试图将一个字符串反向规约至开始符号。
自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少。
自下而上语法分析的策略
：
移进–规约分析
；
移进
就是将一个终结符推进栈
归约
就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈
移进-归约过程是自顶向下
最右推导的逆过程
（规范归约）
我们如何决定什么时候移进，什么时候规约？
考虑
i
n
t
∣
∗
i
n
t
+
i
n
t
int | * int + int
i
n
t
∣
∗
i
n
t
+
i
n
t
我们可以用 T →int进行归约，而得到
T
∣
∗
i
n
t
+
i
n
t
T | * int + int
T
∣
∗
i
n
t
+
i
n
t
致命错误: 无法规约到开始符号
E
E
E
一般的移进-归约策略：
若句柄在栈顶出现，则归约；否则移进
句柄
：句型的最左直接短语
冲突
实际应用中可能出现的冲突
- 移进与归约都合法，产生移进-归约冲突
- 归约时可以适用两个不同的产生式，产生归约-归约冲突
二义文法会导致‘冲突’，但应注意，许多的非二义文法同样会导致‘冲突’
Conflict Solutions：
改写文法；根据产生式出现的顺序来选择；根据算符的优先级；
二、自下而上的分析算法
自下而上的分析算法：
-
优先分析法
：
简单优先分析法、算符优先分析法
- LR分析
1、 简单优先分析
方法简洁、易接受、但是效率低
- 按照文法符号（包括终结符和非终结符）的优先关系确定句柄。
1）优先关系
2）简单优先文法的定义
满足以下条件的文法是简单优先文法
1）在文法符号集
V
V
V
中，
任意两个符号之间最多只有一种优先关系成立
2）在文法中
任意两个产生式没有相同的右部
3）
不含空产生式
2、算符优先分析
算符优先分析
1）如何确定算符优先关系？
-
ii
i
的优先级最高
-
↑ 优先级次于
ii
i
，右结合
-
∗*
∗
和
//
/
优先级次之，左结合
-
++
+
和
−–
−
优先级最低，左结合
-
括号‘
((
(
’,‘
))
)
’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号
-
#的优先性低于与其相邻的算符
2）算符(OG)文法的定义
算符文法两个条件：
①不含空产生式
②不含两个连续非终结符同时出现在产生式右部，即形如U→…VW…
3）算符优先关系的定义
4）算符优先文法的定义
在OG文法 G 中，若任意两个终结符间
至多有一种算符优先关系存在
，则称G 为算符优先文法(OPG)。
注意：允许b>c,c>b; 不允许b>c,b<c,b=c
结论 算符优先文法是无二义的。
算符优先文法的三个条件：
①不含空产生式
②不含两个连续非终结符同时出现在产生式右部，即形如U→…VW…
③任意两个终结符间至多有一种算符优先关系存在
5）算符优先关系表的构造及归约过程
①由定义直接构造 ②由关系图法构造算符优先关系表
求FIRSTVT、LASTVT集合：
如何计算算符优先关系
6）算符优先分析算法
归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的。
为解决在算符优先分析过程中如何寻找句柄，引进
最左素短语
的概念
7）优先函数
优先函数
（
2
(
n
+
1
)
）
（2(n+1)）
（
2
(
n
+
1
)
）
比优先矩阵
（
(
n
+
1
)
2
个
内
存
单
元
）
（(n+1)^2个内存单元）
（
(
n
+
1
)
2
个
内
存
单
元
）
节省空间
优先函数的构造：
- 1）由定义直接构造； 2）用关系图构造优先函数
算符优先分析法的局限性
一般语言的方法很难满足算符优先文法的条件
很难避免把错误的句子得到正确的归约
bingo~ ✨ Courage is resistance to fear,mastery of fear——not absence of fear. 勇敢并非没有恐惧，而是克服恐惧，战胜恐惧。