第四章自下而上语法分析.ppt
《第四章自下而上语法分析.ppt》由会员分享,可在线阅读,更多相关《第四章自下而上语法分析.ppt(74页珍藏版)》请在三一文库上搜索。
1、自下而上语法分析方法,第四章(2),本章要求,主要内容:自下而上语法分析的概念,规范归约,算符优先分析方法及其相关概念。 重点掌握:掌握自下而上分析的基本思想,基本概念,算符优先文法、算符优先关系的判定,最左素短语、句柄、活前缀的定义与判定,求First VT集,Last VT集,构造算符优先关系表,能用算符优先分析法进行表达式分析,存在主要问题: 左递归问题 回溯问题,主要方法: 递归子程序法 LL分析法,自顶向下分析算法的基本思想为:,自底向上分析算法的基本思想为:,存在主要问题: 句柄的识别问题,主要方法: 算符优先分析法 LR分析法,G = (E, i, +, *, (, ) , P
2、, E) P: E E + E E E * E E ( E ) E i,使用最左推导:E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i,例:判定输入串(i+i)*i是否是下述文法的句子?,结论:自上而下语法分析采用最左推导,每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。 自下而上语法分析是最左推导的逆过程,由输入符号串反向推导到文法的开始符号。,自下而上的语法分析,实现思想:“移进-归约”方法 设置一个栈,将输入符号逐个移进栈中,栈顶形成某产生式的右部时,就用左部去代替,称为归约。重复这一过程,直到栈中只剩下文法
3、的开始符号,就确认输入串是文法的句子,分析成功,否则出错。 语法树:从树叶开始,逐步向上归约构造分析树,直到形成根结。是推导的逆过程。 核心 寻找句柄(这是关键) 进行规约。用不同的方法寻找句柄,就可获得不同的分析方法。,最左推导(Left-most Derive) 每次推导都替换当前句型的最左边的非终结符。与最右归约对应 最右推导(Right-most Derive) 每次推导都替换当前句型的最右边的非终结符。与最左归约(规范归约)对应,得规范句型,例:设有文法GS: (1) S aAcBe (2) A b (3) A Ab (4) B d 使用最右推导: 因为S aAcBe aAcde a
4、Abcde abbcde,所以 abbcde是文法G的句子。,步骤 动作,(1)S aAcBe (2)A b (3)A Ab (4)B d,最左归约过程是最右推导的逆过程, 对输入串abbcde的归约过程如下:,该分析过程反复执行“移进”和“归约”两个动作,直到栈中只有开始符号为止。,a,b,A,c,S,b,d,B,e,A,这种分析过程具有如下特点: 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串(某个产生式的右端)就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替,归约可能重复多次,然后继续移进。 若最终能归约成文法的开始符号,则分析成功。 由于总是将句型的最左边的可
5、归约串替换成非终结符,该方法与最右推导对应。 关键是如何判断可归约串?,语法分析树的生成演示,a b b c d e,A,A,B,S,Ab,AAb,Bd,SaAcBe,(1)S aAcBe (2)A b (3)A Ab (4)B d,这一方法简单明了,不断地进行移进归约, 关键是确定当前句型的句柄.,说明:例子的分析过程是一步步地归约当前句型的句柄,该句子输入串为bbcde的 语法树的构造过程为:,例:GS: SAcBe Ab AAb Bd,问题的提出: 在构造语法树的过程中,何时归约? 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串? 如何进行归约? 通过不同的自
6、底向上的分析算法来解释,不同的算法对可归约串的定义是不同的,但分析过程都有一个共同的特点:边移进边归约。,规范归约的概念,有文法G,开始符号为S, 如果有S=xy,则xy是文法G的句型,x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语 如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语 位于一个句型最左边的直接短语称为句柄.,注意: 每次归约的部分必须是句柄 (最右推导)。 关键的问题是如何识别句柄,例:考虑如下文法:,求句型 i1 * i2 + i3 的短语、直接短语和句柄。,ET | E+T TF | T*F Fi | (E),因此: 短语
7、有:i1, i2, i3, i1*i2, i1*i2+i3 直接短语有:i1, i2 , i3 句柄是: i1,E = F * i2 + i3 E = i1 * F + i3 E = i1 * i2 + F,E = T + i3 (T =T*F =i1 * i2) E = i1 * i2 + i3,Fi,从语法分析树来识别: 一棵子树是由树的某个结点连同它的所有子孙组成的。 子树的所有端末结点自左至右排列成一个相对子树根的短语。 直接短语:只有父子两代结点形成的短语。 句柄:最左子树的直接短语。,从语法树可以看出: i1, i2, i3, i1*i2, i1*i2+i3是句型i1*i2+i3的
8、短语 直接短语有:i1, i2 , i3 句柄是: i1,ET | E+T TF | T*F Fi | (E),句型i1*i2+i3的语法树如图:,对下述文法,求句型 E+T * F + i的短语、直接短语、句柄,ET | E+T TF | T*F Fi | (E),短语有:i, T * F, E+T * F, E + T * F + i 直接短语有: i, T * F 句柄是:T * F,练 习,给定右边的文法,用句柄对符号串abbcde进行归约,用句柄对句子进行归约的过程与用移进-归约过程是一致的,使用归约的产生式及其顺序是一致的。,(1)S aAcBe (2)A b (3)A Ab (4
9、)B d,(2)Ab,(3)A Ab,aAbcde,aAcde,(4)B d,(1)S aAcBe,aAcBe,S,规范归约的定义:,假定是文法G的一个句子,如果序列: n, n-1, ,0 (=S)满足如下条件,则序列n, n-1, , 0是一个规范归约: (1) n = 是给定的句子 (2) 0 =S 是文法的开始符号 (3) 对任何i, 0in,i-1是从i经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程,规范归约又称为最左归约。 最右推导又称规范推导,由规范推导所得到的句型称规范句型,规范推导的逆过程是规范归约。,(1)S aAcBe (2)A b (3)A
10、 Ab (4)B d,上述例子中句子abbcde的规范归约过程是: abbcde, aAbcde, aAcde, aAcBe,S,练 习,使用下述文法对句型i1*i2+i3进行规范规约:,ET | E+T TF | T*F Fi | (E),i1*i2+i3 , F*i2+i3 , T*i2+i3, T*F+i3 , T + i3 , E+i3 , E + F, E + T , E,使用修剪语法树的方法来进行归约:,规范归约分析中栈的使用,1、句型表示,符号栈内容 + 输入缓冲区内容 # 当前句型 #,2、分析器结构,能够到达终态,分析成功,不能到达终态,分析失败。,例2:有文法: E E+T
11、|T T T*F|F F (E)|i 对输入串 id1+id2*id3 的规范归约过程:,动作 栈 输入缓冲区 1) 准备 # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 Fid #F +id2*id3# 4) 归约 TF #T +id2*id3# 5) 归约 ET #E +id2*id3# 6) 移进 #E+ id2*id3# 7) 移进 #E+id2 *id3# 8) 归约 Fid #E+F *id3# 9) 归约 TF #E+T *id3# 10) 移进 #E+T* id3# 11) 移进 #E+T*id3 # 12) 归约 Fid #E+T*F #
12、13) 归约 TT*F #E+T # 14) 归约 EE+T #E # 15) 接受,所得的结果是:用产生式序列表示语法分析树,id1 + id2 * id3,F,T,E,F,T,F,T,E,(1) ET | E+T (2) TF | T*F (3) Fi | (E),练习,给出句型(a,(a,a)的 规范归约过程,给定文法GS:,S a | (T) T T,S | S,3. 过程描述: repeat repeat 将输入串最左边的符号移入栈内 until 在栈里符号串中找到一个可归约串; 归约可归约串 until 文法开始符号出现在栈顶或者发现错误。,分析成功的条件:栈顶为文法开始符号,输入
13、串为空。 注意:该过程并未涉及如何在栈里找可归约串。实际上,不同的找可归约串的方法,构成了不同的分析算法。 “移进-归约”分析法用栈实现的特点: 可归约串必定位于栈顶,即可归约串之后就是剩余的输入串。 栈内符号串与剩余输入串正好构成一个句型。,分析器的四种动作,1) 移进:将下一输入符号移入栈 2) 归约:当栈顶出现句柄,用产生式左侧的非终结符替换栈顶的句柄 3) 接受:分析成功,是归约的一种特殊情况 4) 出错:栈顶的内容与输入符号相悖,进行出错处理 ?决定移进和归约的依据是什么,移进归约分析中的问题,1) 移进-归约冲突 在分析到某一步时,既可以移进,又可以归约 上例第10)步可以移进*,
14、也可以按产生式EE+T进行归约。 2) 归约-归约冲突 存在两个可选的句柄,可对栈顶符号进行归约 例如上述第13)步,可以用TF进行归约,又可以按TT*F进行归约。 各种分析方法中处理冲突的技术不同,语法分析树的表示,具体实现时可以采用不同的数据结构 P89 介绍了一种“穿线表”方法来表示语法树,优先分析法有两种: 简单优先分析法(规范归约)文法按一定原则规定文法符号的优先关系 算符优先分析法(不规范归约)规定算符之间的优先关系,自底向上优先分析法概述,算符优先分析,算符优先分析法的思想源于表达式的分析,是利用相邻终结符号之间的关系来寻找可归约串。 将句型中的终结符号当作“算符”,借助于算符之
15、间的优先关系确定句柄,分析过程是自下而上的归约过程,不是一种严格的规范归约。,优先关系的定义:,在一个符号串中,任意两个相邻终结符号a和b之间,只可能存在三种优先关系: (1) a优先性等于b ,记作a b。 (2) a优先性高于b, 记作a b。 (3) a优先性低于b ,记作a b。,另一种情况是,a与b不可能相邻,即此符号串不是句型(出错)。 如果以上四种关系中的任意两种都不会同时成立,则可以根据终结符号之间的归约关系进行语法分析。,1.算符文法:如果文法G没有P.QR.(P,Q,R属于非终结符)的产生式,(主要是看产生式中是否包含两个非终结符相邻的情况) 2.算符优先关系的定义:文法G
16、是一个不含-产生式的算符文法,定义终结符a、b之间的优先关系 a b,G中有P.ab.或P.aQb. (在同一产生式中) a b,G中有P.aR.的产生式,且R=b.或R=Qb. (注意ab相邻) a b,G中有P.Rb.的产生式,且R=.a或R=.aQ (注意ab相邻),算符优先文法的定义,例:EE+E | E*E | (E) | i 证明不是算符优先文法。 因 为:EE+E ,EE*E 则有 + *(由规则2) 又因为:EE*E, EE+E 则有 + *(由规则3) 所以不是算符优先文法。,3.算符优先文法 算符文法G的任何终结符a,b之间要么没有优先关系,若有优先关系,至多有 = , 中
17、的一种成立,则G为一算符优先文法。,练 习,对右边的文法G,计算终结符+,*,和 )之间的优先关系:,EE + T TT * F FP F P(E),因为: EE + T ,T=T*F,所以:+ E + T ,所以:+ + (规则3) 因为: T T * F ,F = P F,所以:* T * F,所以:* * (规则3) 因为: P(E) , E = E + T ,所以:+ ) (规则3) 因为:FP F, P = (E),所以:) (规则3) 因为: FP F, F =P F,所以: (规则2) ,算符优先关系表的构造,用表格形式来表示各终结符号的优先关系,这种表称为优先表。 构造优先关系
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 自下而上 语法分析
链接地址:https://www.31doc.com/p-2262850.html