《编译原理课件第5章》由会员分享，可在线阅读，更多相关《编译原理课件第5章（103页珍藏版）》请在金锄头文库上搜索。
1、2017/5/27,1,第5章自底向上的语法分析,5.1 自底向上的语法分析概述5.2 算符优先分析法5.3 LR分析法5.4 语法分析程序的自动生成工具Yacc5.5 本章小结,2017/5/27,2,5.1 自底向上的语法分析概述,思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。核心寻找句型中的当前归约对象“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法,2017/5/27,3,例5.1 一个简单的归约过程,设文法G为：SaABe AAbc|b Bd,句子分析： abbcdeaAbcdeaAde aABe S,语法
2、树的形成过程,2017/5/27,4,语法分析树的生成演示,a b b c d e,A,A,B,S,Ab,AAbc,Bd,SaAcBe,2017/5/27,5,5.1.1 移进-归约分析,系统框架采用表驱动的方式实现输入缓冲区：保存输入符号串分析栈：保存语法符号已经得到的那部分分析结果控制程序：控制分析过程，输出分析结果产生式序列格局：栈+输入缓冲区剩余内容=“句型”,2017/5/27,6,移进-归约语法分析器的总体结构,id + id id #,#,移进-归约控制程序,输出产生式序列,栈内容+输入缓冲区内容 # “当前句型 ” #,栈,输入缓冲区,分析表M,2017/5/27,7,与LL(
3、1)的体系结构比较,输入缓冲区(符号序列),栈,控制程序P132,预测分析表M,输出产生式序列,2017/5/27,8,移进-归约分析的工作过程,系统运行开始格局栈：#；输入缓冲区：w#存放已经分析出来的结果,并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈问题：系统如何发现句柄在栈顶形成？正常结束: 栈中为 #S，输入缓冲区只有 #,2017/5/27,9,输出结果表示：用产生式序列表示语法分析树,E id,id + id * id,E,E,E,E,E,E id,E id,E E * E,E E + E,例5.2 EE+E|E*E|(E)|id,2017/5/27
4、,10,动作 栈 输入缓冲区,1) # id1+id2*id3#,id + id * id,2) 移进 #id1 +id2*id3#,例5.2 分析过程,3) 归约 Eid #E +id2*id3#,4) 移进 #E+ id2*id3#,5) 移进 #E+id2 *id3#,6) 归约 Eid #E+E *id3#,7) 移进 #E+E* id3#,8) 移进 #E+E*id3 #,9) 归约 Eid #E+E*E #,10) 归约 EE*E #E+E #,11) 归约 EE+E #E #,12) 接受,2017/5/27,11,分析器的四种动作,1) 移进：将下一输入符号移入栈2) 归约：用
5、产生式左侧的非终结符替换栈顶的句柄（某产生式右部）3) 接受：分析成功4) 出错：出错处理？决定移进和归约的依据是什么回头看是否可以找到答案,2017/5/27,12,移进-归约分析中的问题,1) 移进归约冲突 例5.2中的 6)可以移进 * 或按产生式EE+E归约,2017/5/27,13,动作 栈 输入缓冲区,1) # id1+id2*id3#,id + id * id,2) 移进 #id1 +id2*id3#,例5.2分析过程,3) 归约 Eid #E +id2*id3#,4) 移进 #E+ id2*id3#,5) 移进 #E+id2 *id3#,6) 归约 Eid #E+E *id3#
6、,7) 移进 #E+E* id3#,8) 移进 #E+E*id3 #,9) 归约 Eid #E+E*E #,10) 归约 EE*E #E+E #,11) 归约 EE+E #E #,12) 接受,2017/5/27,14,移进-归约分析中的问题,1) 移进归约冲突 例5.2中的 6)可以移进 * 或按产生式EE+E归约 2) 归约归约冲突 存在两个可用的产生式各种分析方法处理冲突的方法不同如何识别句柄？如何保证找到的直接短语是最左的?利用栈如何确定句柄的开始处与结束处？,2017/5/27,15,5.1.2 优先法,根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同
7、优先的句柄两端符号的优先级要高于句柄外与之相邻的符号a1ai-1aiai+1aj-1ajaj+1an定义了这种优先关系之后，语法分析程序就可以通过ai-1ai和ajaj+1这两个关系来确定句柄的头和尾了,2017/5/27,16,5.1.3 状态法,根据句柄的识别状态（句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态例如： SbBB可分解为如下识别状态S.bBB 移进bSb.BB 等待归约出BSbB.B 等待归约出BSbBB. 归约采用这种方法，语法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约。,2017/
8、5/27,17,5.2 算符优先分析法,算术表达式分析的启示算符优先关系的直观意义+ * + 的优先级低于 *( ) ( 的优先级等于 )+ + + 的优先级高于 +方法将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄,2017/5/27,18,算术表达式文法的再分析,EE+EEE-EEE*EEE/E E(E) EidEE+T| E-T| T TT*F| T/F| F F(E)|id,从如何去掉二义性,看对算符优先级的利用,句型的特征：(E+E)*(E-E)/E/E+E*E*E没有两个语法变量直接相邻,2017/5/27,19,算符文法,如果文法G=（ V，T，P，S）中不存在
9、形如ABC 的产生式，则称之为算符文法(OG Operator Grammar)即：如果文法 中不存在具有相邻非终结符的产生式，则称为算符文法。每个产生式的右部都没有两个语法变量直接相邻。该文法不会产生如下形式的句型：E1E2其中，E1和E2是两个相邻的语法变量。,2017/5/27,20,5.2.1 算符优先文法,定义5.1 假设G是一个不含-产生式的文法，A、B和C均是G的语法变量，G的任何一对终结符a和b之间的优先关系定义为： ab，当且仅当文法G中含有形如Aab或AaBb的产生式； ab，当且仅当文法G中含有形如AaB的产生式，而且Bb或BCb； ab，当且仅当文法G中含有形如ABb的
10、产生式，而且Ba或BaC； a与b无关系，当且仅当a与b在G的任何句型中都不相邻。问题：什么是算符优先文法？,2017/5/27,21,5.2.1 算符优先文法,设G=（V，T，P，S）为OG，如果 a,bVT, ab, ab, ab 至多有一个成立，则称之为算符优先文法(OPG Operator Precedence Grammar) 在无产生式的算符文法中，如果任意两个终结符之间至多有一种优先关系，则称为算符优先文法。,2017/5/27,22,例：EE+E | E-E | E*E | E/E | (E) | id 证明不是OPG文法。因为：EE+E ， EE*E 则有 + *又因为：EE
11、*E, EE+E 则有 + *所以不是算符优先文法。,2017/5/27,23,5.2.2 算符优先矩阵的构造,优先关系的确定根据优先关系的定义ab AaBP且(Bb或者BCb)需要求出非终结符B派生出的第一个终结符集ab ABbP且(Ba或者BaC)需要求出非终结符B派生出的最后一个终结符集设G=（V，T，P，S）为OG，则定义FIRSTOP(A)=b|Ab或者ABb,bT,B VLASTOP(A)=b|Ab或者AbB,bT,B V,+,+,+,+,+,+,+,+,2017/5/27,24,算符优先关系矩阵的构造,Aab ; AaBb, 则abAaB,则对bFIRSTOP(B),abABb,
12、则对aLASTOP(B), abif ABP,then FIRSTOP(B) FIRSTOP(A)if ABP,then LASTOP(B) LASTOP(A)问题：编程求FIRSTOP、LASTOP,2017/5/27,25,构造FIRSTOP(B)和LASTOP(B)的算法,假设B、C为语法变量，b为终结符1) 若有产生式B b或B Cb ，则bFIRSTOP(B)2) 若有产生式B C，则FIRSTOP(C) FIRSTOP(B)3) 若有产生式B b或B bC ，则bLASTOP(B)4) 若有产生式B C，则LASTOP(C) LASTOP(B),2017/5/27,26,文法Ge：
13、(1) ET(2) EE+T(3) EE-T(4) TF(5) TT*F(6) TT/F(7) F(E) (8) Fid,FIRSTOP(E)=+,-,*,/,(,idFIRSTOP(T)=*,/,(,idFIRSTOP(F)=(,idLASTOP(E)=+,-,*,/,),idLASTOP(T)=*,/,),idLASTOP(F)=),id,1)关系由产生式(7),得（）2）关系找形如：AaB的产生式+T: 则+FIRSTOP(T) -T: 则-FIRSTOP(T)*F:则 *FIRSTOP(F)/F: 则 /FIRSTOP(F)(E: 则 (FIRSTOP(E),3)关系找形如：ABb的产生式E+ ,则 LASTOP(E)+E- ,则 LASTOP(E)- T* ,则 LASTOP(T)* T/ ,则 LASTOP(T)/ E) ,则 LASTOP(E),2017/5/27,27,例 5.6 表达式文法的算符优先关系, acc,+-*/()id#,+-*/（）id#, , , , ,
