编译原理算符优先分析法.ppt

文档介绍：该【编译原理算符优先分析法 】是由【huanmouyo】上传分享，文档一共【28】页，该文档可以免费在线阅读，需要了解更多关于【编译原理算符优先分析法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。基本思想：用一个寄存文法符号的栈，将一个输入串反向归约至文法的开始符号。
01
特点：效率高、文法限制少。
02
自下而上语法分析概述
自下而上分析法的一般原理
1 自下而上语法分析概述
移进－归约过程实例。
设有文法G[A]：
(1)A aBcDe
(2)B b
(3)B Bb
(4)D d
对输入串abbcde$的移进－归约分析过程
对输入串abbcde$移进－归约分析过程：
步骤
符号栈
输入串
动作
0
1
2
3
4
5
6
7
8
9
10
$
$a
$ab
$aB
$aBb
$aB
$aBc
$aBcd
$aBcD
$aBcDe
$A
abbcde$
bbcde$
bcde$
bcde$
cde$
cde$
de$
e$
e$
$
$
a进栈
b进栈
用B b归约
b进栈
用B Bb归约
c进栈
d进栈
用D d归约
e进栈
用A aBcDe归约
分析成功
2 移进－归约的基本思想
用一个栈寄存文法符号，移进将一个终结符推进栈;
归约是将0个或多个符号从栈中弹出，用相应产生式的左部一个非终结符压入栈;
01
把栈顶被归约的一串符号称为可归约串;
重复这一过程直至整个输入串分析完毕;
最终栈中只剩下左界符$和开始符号S，则所分析的输入串是文法的正确句子;否则，出错。
02
可归约串
01
02
03
04
05
06
07
08
算符优先分析法
规范归约分析法
简单优先分析法
LR分析法
用 最左素短语
用 句柄
刻画可归约串
刻画可归约串
3 分类
算符优先分析法
方法概述
特点
适合分析各类表达式;
宜于手工实现;
规定运算符之间的优先顺序(优先关系，结合性质)。
通过比较算符之间的优先关系确定可归约串。
方法概述
2 优先关系
例 文法G[E]：
E E+E|E*E|(E)|id
对输入串id+id*id的规范归约过程。
(1)id+id*id
(2)E+id*id
(3)E+E*id
(4)E+E*E
(5)E+E
(6)E
(1)id+id*id
(2)E+id*id
(3)E+E*id
(4)E*id
(5)E*E
(6)E
*优先于＋：
＋优先于*：
优先关系种类
任何两个相邻的终结符a和b可能的优先关系有3种：
a b: a的优先级低于b
a b: a的优先级等于b
a b: a的优先级高于b
注：优先关系与出现的左右次序有关，不同于数学符号<,=,>。
方法概述
矩阵的行和列都是文法的终结符;
矩阵元素是两终结符间的优先关系。
算符优先分析法借助优先关系表寻找句型的可归约串。
优先关系矩阵(表)
方法概述
算符优先关系表实例
+
*
id
(
)
$
+
*
id
(
)
$
栈顶第一个终结符
当前输入串首字符