第05章 算符优先分析法.ppt

文档介绍：自下而上分析法
思想
从输入串出发，反复利用产生式进行，如果最后能得到文法的开始符号，则输入串是合法句子，否则输入串有语法错误。
核心
寻找句型中的进行归约,用不同的方法寻找归约串，就可获得不同的分析方法
第05章_算符优先分析法
1、自下而上分析事例：设文法G为(1)SaAcBe (2)Ab (3)AAb (4)Bd试判断语句abbcde是否是该文法的合法句子？
怎样实现归约过程：借鉴LL(1)分析法的体系结构
步骤
栈内
输入串
动作
0
#
abbcde#
1
#a
bbcde#
移进
2
#ab
bcde#
移进
3
#aA
bcde#
归约
4
#aAb
cde#
移进
5
#aA
cde#
归约
6
#aAc
de#
移进
7
#aAcd
e#
移进
8
#aAcB
e#
归约
9
#aAcBe
#
移进
10
#S
#
归约
11
识别成功
第05章_算符优先分析法
2、自下而上分析法的核心问题：
1)存在移进--归约冲突;
2)存在归约--归约冲突;
核心问题是寻找句型中的归约串进行归约。
自下而上分析法
第05章_算符优先分析法
一、算符优先分析法：
1、算符优先分析法的思想：
对于文法G:EE+E|E-E|E*E|E/E|(E)|i，分析i+i-i*(i+i)
规范推导：
EE*EE*(E)E*(E+E)E*(E+i)E*(i+i) E+E*(i+i)E+E-E*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)
第5章 优先分析法
逆过程是规范归约
第05章_算符优先分析法
另外一种推导：
EE-EE-E*EE-E*(E)E-E*(E+E)E-E*(E+i) E-E*(i+i)E-i*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)
第5章 优先分析法
算符优先分析法的基本思想：
定义终结符之间的优先关系，借助终结符之间的优先关系确定归约对象，进行自下而上分析。
比较相邻的2个算符的优先级
2种推导过程对于8+7-5*(3+2)的计算结果
第05章_算符优先分析法
2、算符优先分析技术的引进：
必须给出文法中两个可能在句子中相继出现的终结符之间的优先关系。
(1)相继出现：在句子中若有“…ab…”或“…aQb…”.(a,b∈ＶT,Q∈ＶN),则称a，b相继出现。
(2)终结符号对优先关系的存储：
优先关系表是一个矩阵M(a,b),a∈ＶT,b∈ＶT,矩阵行数、列数都为|Σ|+1。
如:对于文法G:EE+E|E-E|E*E|E/E|(E)|i,对应的优先矩阵为：
①矩阵元素M(a,b)表示a在前,b在后时,a与b之间的优先关系。
②矩阵元素M(a,b)的取值:≮,≯,≡ 。
i+i-i*(i+i)
E+E-E
第05章_算符优先分析法
对文法E→E+E|E-E|E*E|E/E|(E)|i
+ - * / ( ) i #
+ ≯ ≯ ≮ ≮ ≮ ≯ ≮ ≯
- ≯ ≯ ≮ ≮ ≮ ≯ ≮ ≯
* ≯ ≯ ≯ ≯ ≮ ≯ ≮ ≯
/ ≯ ≯ ≯ ≯ ≮ ≯ ≮ ≯
( ≮ ≮ ≮ ≮ ≮ ≡ ≮
) ≯ ≯ ≯ ≯ ≯ ≯
i ≯ ≯ ≯ ≯ ≯ ≯
# ≮ ≮ ≮ ≮ ≮ ≮
如何获得一般的文法的优先分析表？
#优先级低于其右部符号
源程序中不会出现…)(…的情形
如何获得一般的文法的优先分析表？
第05章_算符优先分析法
3、优先表的构造方法：
算符文法：给定上下文无关文法G=（VN，VT，P，S）中不存在形如A…BC…的产生式，则称之为算符文法(OG—Operator Grammar)(其中A,B,C∈ＶN)
即：如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。
算符优先文法:设文法G是一个不包含有空串产生式的算符文法,如果该文法中的任何终结符号对a,b之间,在三种关系中最多只有一种成立,则称该文法为算符优先文法。
第05章_算符优先分析法
(1)求文法中每个非终结符P的首终结符集合FIRSTVT(P)
①定义：FIRSTVT(P)=