编译原理电子课件教案-第6章-自底向上优先分析法.pptx

1
第六章自底向上优先分析法
2
本章内容
引子:自底向上分析的一般原理
自底向上优先分析概述
简单优先分析法(了解)
算符优先分析法
3
一、自底向上分析的基本思想
对输入串从左到右扫描,并逐个移入栈中。边移入边分析,一旦栈顶符号串形成某个句型的可归约串(它对应某产生式右部),就用该产生式左部的非终极符号代替它,完成进一步归约。
重复这一过程直到归约到栈中,只剩下开始符号和右边界符’#’,成功。否则,报错。
引子:自底向上分析的一般原理
4
例.(p94) (1) S aAcBe (2) A b (3) A  Ab (4) B d, 对输入串abbcde#语法分析走一遍动作。
符号栈输入串
0 # abbcde#
1 #a bbcde#
2 #ab bcde# 用Ab归约
3 #aA bcde#
4 #aAb cde# 用AAb归约
5 #aA cde#
6 #aAc de#
7 #aAcd e# 用Bd归约
8 #aAcB e#
9 #aAcBe # 用SaAcBe归约
10 #S #
5
二、自底向上分析的关键
如何精确定义可归约串并识别。
对可归约串(p23)的不同定义形成不同的自下而上分析方法:
,用句柄来刻画可归约串(LR, 简单优先)
,是用最左素短语来刻画可归约串。
根据识别可归约串的不同方法,也形成不同的自下而上分析法。
简单优先分析法和LR分析法都是规范归约分析法(句柄—可归约串),但它们识别句柄的方法不同:
、现实、展望三者信息来确定栈顶符号串是否形成句柄
。
6
自底向上优先分析法概述
:对一文法求出所有符号之间的优先关系,并据此确定句柄(规范归约)
:只考虑算符之间的优先关系,不考虑VN的优先关系。只要找到可归约串就归约,并不考虑归约到哪个非终极符。
7
简单优先分析法(了解)
优先关系
X=·Y iff A…XY…
X<·Y iff A…XB…且B Y…
X·>Y iff A…BD…且B …X和D Y…
SbAb, A(B | a, BAa)
(1)相等:b=·A,A=·b,(=·B,A=·a,a=·)
(2) <· : 由bA及A(B | a , BAa) ,可得
b <·( , b <· a,(<· A, (<·( , (<· a
(3) ·> : 由 S bAb , A(B | a 及 B Aa),可得
B ·> b , B ·> a
a ·> b , a ·> a
) ·> b , ) ·> a
+

+

+

8
简单优先文法的定义
一、定义
简单优先文法满足两个条件
(1)任意两个文法符号之间最多只有一种优先关系成立
(2)在G中任意两个产生式没有相同的右部(归约唯一)
分析:栈顶为ai
ai <· ai+1 移进
ai ·> ai+1 归约(已形成句柄)
9
二、简单优先分析法
步骤:构造文法的优先关系矩阵,将G规则保存,设置符号栈S
(1)将输入串a1,a2,…an #逐个移入符号栈S中,直到栈顶符号ai ·> ai+1为止。
(2)栈顶ai为句柄尾,由此向左在栈中找句柄开头符号ak(找到ak-1 <· ak为止)
(3)由句柄akak+1…ai在产生式中查找右部为ak…ai的产生式,若找到则用相应左部代替句柄(归约),否则出错,串不是合法句子。
简单优先文法的定义
10
算符优先分析法
特别适合于分析程序中各类表达式且宜于手工实现—简单、直观(仅适用于表达式的语法)
方法概述
算符优先文法的定义
算符优先关系表的构造(由定义)
算符优先分析算法
算符优先分析法的局限(p120)