第六章-自底向上优先分析课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第六章-自底向上优先分析课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 向上 优先 分析 课件
- 资源描述:
-
1、1盛威网:专业的计算机学习网站指导教师指导教师:杨建国杨建国二零零七年十一月二零零七年十一月2盛威网:专业的计算机学习网站第6章自底向上优先分析语法分析推导推导p自上而下的语法分析过程p预测分析程序,递归下降分析法(最左推导)p注:要求文法是LL(1)文法归约p自下而上的语法分析过程p简单优先分析法,算符优先分析法,LR分析法3盛威网:专业的计算机学习网站1.1.自底向上优先分析概述自底向上优先分析概述2.2.简单优先分析(简单优先分析(优先关系的理解优先关系的理解)3.3.算符优先分析算符优先分析 确定句型的短语、直接短语、句柄、确定句型的短语、直接短语、句柄、素短语、素短语、最左素短语最左
2、素短语 算符优先关系矩阵的构造及输入串的过程分析算符优先关系矩阵的构造及输入串的过程分析学习目标学习目标4盛威网:专业的计算机学习网站v第一节第一节 自底向上优先分析概述自底向上优先分析概述v第二节第二节 简单优先分析法简单优先分析法v第三节第三节 算符优先分析法算符优先分析法v第四节第四节 典型例题及解答典型例题及解答教学内容教学内容5盛威网:专业的计算机学习网站知识结构知识结构6盛威网:专业的计算机学习网站从输入串开始,逐步进行从输入串开始,逐步进行“归约归约”,直至,直至归约到文法开始符号;或者说,从语法树的末归约到文法开始符号;或者说,从语法树的末端开始,步步向上端开始,步步向上“归约
3、归约”,直到根结点。,直到根结点。7盛威网:专业的计算机学习网站u引言引言 1.1.基本思想基本思想自下而上的语法分析过程是一个自下而上的语法分析过程是一个最左归约最左归约的过程,的过程,从输入串开始,朝着文法的开始符号进行归约,从输入串开始,朝着文法的开始符号进行归约,直到到达文法的开始符号为止的过程。直到到达文法的开始符号为止的过程。从语法树角度看从语法树角度看,是以输入符号串作为语法树的,是以输入符号串作为语法树的末端结点符号串,自底向上地构造语法树,使文末端结点符号串,自底向上地构造语法树,使文法开始符号正好是该语法树的根。如果最终根结法开始符号正好是该语法树的根。如果最终根结点是开始
4、符号,则输入符号串是语言的一个句子,点是开始符号,则输入符号串是语言的一个句子,否则不是。否则不是。自底向上分析过程实际上是一个不断进行直接归自底向上分析过程实际上是一个不断进行直接归约的过程。约的过程。注意:输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列。 8盛威网:专业的计算机学习网站1、找出当前句型的句柄、找出当前句型的句柄 x (或句柄的变形)(或句柄的变形)2 2、找出以、找出以x x为右部的规则为右部的规则X Xx x 3 3、把、把x x规约为规约为X X,产生语法树的一枝产生语法树的一枝9盛威网:专业的计算机学习网站2.2.实现方式实现方式- -“移进归约移进
5、归约”方式方式 语法分析程序 语法表 a+b#输出带#p 自左至右把输入串的符号逐个自左至右把输入串的符号逐个移进移进栈栈【注注】初态时栈内仅有栈底符初态时栈内仅有栈底符“”,读头指在最左边的单词符号上。读头指在最左边的单词符号上。 p 若栈顶形成某个句型的句柄,就将此句柄用相应的若栈顶形成某个句型的句柄,就将此句柄用相应的产生式左部替换(产生式左部替换(归约归约),若再形成句柄,就继续替),若再形成句柄,就继续替换,直到栈顶不再形成句柄为止。换,直到栈顶不再形成句柄为止。p重复上面的过程直到栈顶只剩下重复上面的过程直到栈顶只剩下# #和文法的和文法的开始符号开始符号,同时输入串读完为止,这样
6、就认为识别了一个句子。同时输入串读完为止,这样就认为识别了一个句子。10盛威网:专业的计算机学习网站3.3.语法分析程序执行的动作语法分析程序执行的动作移进移进 读入下一个输入符号并压入栈内,读头后移;归约归约 检查栈顶若干个符号能否进行归约,若能,就以产生式左部替代该符号串,同时输出产生式;接受接受 移进归约的结局是栈内只剩下栈底符号和文法开始符号,读头也指向语句的结束符; 报错报错 当识别程序察觉一个错误,因此输入符号串不是句子而无法继续识别工作时,调用一个出错处理子程序进行处理或停止。11盛威网:专业的计算机学习网站例例1:文法:文法GS:(1) S aAcBe(2) A b(3) A
7、Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1) # abbcde# 移进移进 2) #a bbcde# 移进移进A 3) #ab bcde# 归约归约(Ab) 4) #aA bcde# 移进移进A 5) #aAb cde# 归约归约(AAb) 6) #aA cde# 移进移进 7) #aAc de# 移进移进B 8) #aAcd e# 归约归约(Bd) 9) #aAcB e# 移进移进11) #S # 接受接受S10) #aAcBe # 归约归约(S aAcBe)符号串符号串abbcdeabbcde是否是是否是GSGS的句子的句子对输入串对输入串a
8、bbcde#的移进的移进-归约分析过程归约分析过程SaAcBe aAcde aAbcde abbcde12盛威网:专业的计算机学习网站顺序扫描输入符号并依次移进栈栈顶部的符号串是否构成一句柄?YN进行一次归约输入串扫描完否?noY栈中仅有开始符号?noerror输入串合法,报告分析报告出口移进移进- -归约过程归约过程Y13盛威网:专业的计算机学习网站14盛威网:专业的计算机学习网站15盛威网:专业的计算机学习网站6.1自底向上优先分析概述1.1.优先分析器(优先分析器(Precedence ParserPrecedence Parser)简单优先分析法简单优先分析法算符优先分析法算符优先分析
9、法2.LR2.LR分析器分析器16盛威网:专业的计算机学习网站基本思想基本思想:按一定原则定义文法中所有符号:按一定原则定义文法中所有符号(终结符和非终结符)之间的优先关系,按照(终结符和非终结符)之间的优先关系,按照这种关系确定归约过程中的句柄并实行归约。这种关系确定归约过程中的句柄并实行归约。是一种规范归约。是一种规范归约。简单优先分析法准确、规范,但效率低,不实简单优先分析法准确、规范,但效率低,不实用,不流行。用,不流行。17盛威网:专业的计算机学习网站基本思想基本思想:只定义文法中终结符之间的优先:只定义文法中终结符之间的优先关系(关系(不考虑非终结符不考虑非终结符),并由这种关系指
10、),并由这种关系指导分析过程导分析过程不是规范归约不是规范归约算符优先分析法分析速度快,特别适用于表算符优先分析法分析速度快,特别适用于表达式的分析。缺点是不规范,常常要采用适达式的分析。缺点是不规范,常常要采用适当措施克服其缺点。当措施克服其缺点。 18盛威网:专业的计算机学习网站6.2简单优先分析法6.2.1 6.2.1 优先关系优先关系.+*.+(1 1) X XY Y当且仅当当且仅当G G中存在产生式规则中存在产生式规则 A AXYXY(2 2) X XY Y当且仅当当且仅当G G中存在产生式规则中存在产生式规则 A A XBXB,且,且B BY Y(3 3) X XY Y当且仅当当且
11、仅当G G中存在产生式规则中存在产生式规则 A ABDBD, ,且且B B X X和和D D Y Y20盛威网:专业的计算机学习网站 设设G G是已化简的文法是已化简的文法, ,s,ts,t V V, ,若若G G中存在规范句型中存在规范句型 = =stst, , 则则s,ts,t与与 的句柄之间的关系必有下述情况的句柄之间的关系必有下述情况之一之一: :1.1.s s在句柄在句柄中中, ,而而t t不不在句柄中在句柄中2.2.s s与与t t均均在句柄中在句柄中3.3.s s不在句柄不在句柄中中, ,而而t t在句在句柄中柄中对于上述情况对于上述情况, ,我们规定:我们规定:情况情况1 1:
12、 :stst; ;情况情况2 2: :s=ts=t; ;情况情况3 3: :ststA s t .A s t .A s t .21盛威网:专业的计算机学习网站 另外另外, ,还有一种情况还有一种情况, ,就是就是s s和和t t均不在句柄中均不在句柄中, ,那那么一定存在某句型使得它们进入上述三种情况之一。么一定存在某句型使得它们进入上述三种情况之一。 若若s s和和t t在任何句型中都不可能相邻出现在任何句型中都不可能相邻出现, ,则我们则我们规定二者规定二者。, ,这种优先关系是这种优先关系是的的! !22盛威网:专业的计算机学习网站在句型中,句柄内各相邻符号之间具有相同的优先级。u结论由
13、于句柄要先归约,所以规定句柄两端符号的优先级 要比位于句柄之外的相邻符号的优先级高。 句型中NiNj是句柄,则 N1Ni-1 N Ni i N Nj j Nj+1Nn .【注】优先分析法基本思想也可以表述为: 若句型中N Ni iN Nj j是句柄,语法分析程序可以 通过寻找Ni-1 Ni和Nj Nj+1 这两个关系来确定句 柄的头尾,从而确定句柄进行归约。 .23盛威网:专业的计算机学习网站p我们可以通过两个相邻符号我们可以通过两个相邻符号S Si iS Si i+1+1之间的关系之间的关系来找到句柄:来找到句柄:S Si iS Si i+1+1在句柄内:必然有规则在句柄内:必然有规则UUS
14、 Si iS Si i+1+1S Si i在句柄内部,但是在句柄内部,但是S Si i+1+1在句柄之后,必然有规则在句柄之后,必然有规则UUS Si i,且存在规范句型,且存在规范句型USUSi+1i+1。如果如果S Si i+1+1在句柄内,而在句柄内,而S Si i在句柄外,那么必然存在在句柄外,那么必然存在规范句型规范句型S Si iU U,且有,且有USUSi i+1+1。24盛威网:专业的计算机学习网站如何确定优先关系?如何确定优先关系?例例2文法文法GS:(1) S bAb(2) A (B|a(3) B Aa)1.1.求求= =关系:关系:由由(1)(1):b=Ab=A A=b
15、A=b由由(2)(2):(=B(=B由由(3)(3):A=aA=a a=) a=)注意:注意:行列与左右,空行列与左右,空4.#4.#3.3.求求 关系:关系:由由(1)(1):BbBb ab ab )b)b由由(3)(3):BaBa aa aa )a)a2.2.求求 关系:关系:由由(1)(2)(1)(2):b bab ba由由(2)(3)(2)(3):( ( A A ( (a( (.第二步:找句柄头第二步:找句柄头trjkiSk-1 Skkk-1 =SkSk+1Si 是句柄,用它查产生式表是句柄,用它查产生式表 与一产生式右部与一产生式右部相同相同Si=#且且trj=#结束结束ik,Si
16、UU是该产生是该产生式左部符号式左部符号errorii+1Si trjjj+1YNNYYNYYNerrorerrorN30盛威网:专业的计算机学习网站文法文法GS:(1) S bAb(2) A (B|a(3) B Aa)步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1) # b(aa)b# 2) #b (aa)b# 3) #b( aa)b# 4) #b(a a)b# 5) #b(A a)b# 6) #b(Aa )b# 7) #b(Aa) b# 8) #b(B b# 9) #bA b#10) #bAb #11) #S #对输入串对输入串b(aa)bb(aa)b# #的简单优先分析过程的简单优
17、先分析过程简单优先关系矩阵简单优先关系矩阵注意注意:何时移进,何时归约?:何时移进,何时归约?归约中如何确定句柄?归约中如何确定句柄?#b(a#b, ,移进移进b( , ,移进移进(a, ,用用Aa归约归约A=a , ,移进移进a=) , ,移进移进#b(Aa)b, ,用用BAa) )归约归约#b(BBb, ,用用A(B归约归约A=b, ,移进移进#bAbb#, ,用用SbAbSbAb归约归约接受接受31盛威网:专业的计算机学习网站6.2.4 6.2.4 简单优先分析法的优缺点简单优先分析法的优缺点优点:优点:技术简单 缺点:缺点:适用范围小,分析表尺寸太大。 32盛威网:专业的计算机学习网站
18、6.2.5 6.2.5 简单优先分析法的局限性简单优先分析法的局限性简单优先分析法是有局限性的,它只适应于简单优简单优先分析法是有局限性的,它只适应于简单优先文法,但是程序设计语言的文法一般都不是简单先文法,但是程序设计语言的文法一般都不是简单优先文法,即使是关于表达式的文法也不是简单优优先文法,即使是关于表达式的文法也不是简单优先文法。如果要使用简单优先文法,就必须修改相先文法。如果要使用简单优先文法,就必须修改相应语言的文法,使之成为简单优先文法。应语言的文法,使之成为简单优先文法。例例3 3 设文法设文法G G:E EE+T|TE+T|T T TT T* *F|FF|F E E(E E)
19、|i|i33盛威网:专业的计算机学习网站【解】因为有EE+T,所以有+=T,但由于T T*F,所以有+. + +( ( = = ) )40盛威网:专业的计算机学习网站注意:注意: 是三种有序关系,与数学中的是三种有序关系,与数学中的 不同,所以不同,所以a=ba=b不意味不意味b=ab=a,abab不意不意味味bab +) +,在在(E+T)(E+T)中得中得 + )+ )41盛威网:专业的计算机学习网站a1 a2 a3 ai an# 优先关系表优先关系表总控程序总控程序X1Xn-1Xn#分析器的逻辑结构:分析器的逻辑结构:优先关系表、分析栈、总控程序优先关系表、分析栈、总控程序文法符号文法符
20、号42盛威网:专业的计算机学习网站EE+E|E-E|EEE+E|E-E|E* *E|E/E|EE|E/E|E E|(E)|iE|(E)|i 二义性文法的句子往往有不同的规范推导,句子i+i*i的两种不同的规范归约过程如下:第一个规范归约过程第一个规范归约过程(1) i+i(1) i+i* *i i(2) E+i(2) E+i* *i i(3) E+E(3) E+E* *i i(4) E+E(4) E+E* *E E(5) E+E(5) E+E(6) E(6) E第二个规范归约过程第二个规范归约过程(1) i+i(1) i+i* *i i(2) E+i(2) E+i* *i i(3) E+E(3
21、) E+E* *i i(4) E(4) E* *i i(5) E(5) E* *E E(6) E(6) Ei i是句柄是句柄E+EE+E是句柄是句柄43盛威网:专业的计算机学习网站u按按传统的习惯规定传统的习惯规定优先级从优先级从高到低为高到低为:(0 0)i i的优先级最高的优先级最高(1 1) 优先级次于优先级次于i i,右结合,右结合(2 2)* *和和/ /优先级次之,左结合优先级次之,左结合(3 3)+ +和和- -优先级最低,左结合优先级最低,左结合(4 4)括号)括号( (, ,) )的优先级大的优先级大于括号外的运算符,小于括号于括号外的运算符,小于括号内的运算符,内括号的优先
22、性内的运算符,内括号的优先性大于外括号大于外括号(5 5)# #优先性低于与其相邻的优先性低于与其相邻的算符算符+-*/ ()i#+-*/ (=i#-*/ (=i#P-QRQR 例例GE: EEE|E*E |(E) |i GE: EEAE|(E)|i A|*注:算符文法保证了两个运算符之间只有一个操作数。注:算符文法保证了两个运算符之间只有一个操作数。 47盛威网:专业的计算机学习网站证明:用归纳法证明:用归纳法设设 是句子,是句子,S S,即,即S S 0 01 1.n-1n-1n n 1.1. 推导长度是推导长度是n n,归纳起点,归纳起点n n1 1时,时,S=S= 0 0 1 1 ,即
23、,即S S,必存在一个规则,必存在一个规则S S,而由算符文,而由算符文法的定义,文法的规则中无相邻的非终结符,满足性质法的定义,文法的规则中无相邻的非终结符,满足性质1 1。 2.2. 假设假设n1n1, n-1n-1满足性质满足性质1 1。若若 n-1n-1 A A ,A A为非终结符。由假设的为非终结符。由假设的 的尾符号和的尾符号和 的首符的首符号都不是非终结符,否则与假设矛盾。号都不是非终结符,否则与假设矛盾。又若又若A A是文法的规则,则有是文法的规则,则有 n-1n-1n n= = 而而A A是文法的规则,它不含两个相邻非终结符,所以是文法的规则,它不含两个相邻非终结符,所以 也
24、不含两个相邻的非终结符,满足性质也不含两个相邻的非终结符,满足性质1 1。* *性质性质1 1:在算符文法中,:在算符文法中,任意句型任意句型都不含两个相邻的非终结符。都不含两个相邻的非终结符。48盛威网:专业的计算机学习网站性质性质2 2:若:若AbAb或或bAbA出现在算符文法的句型出现在算符文法的句型 中,其中中,其中A A V VN N , ,b b V VT T, ,则则 中任何中任何含含b b的短语的短语必包含必包含A A。 证明:用反证法。证明:用反证法。由算符文法的性质由算符文法的性质1 1可知。可知。S S bAbA 若存在若存在B Bb b,( b b是仅含是仅含b b但不
25、含但不含A A的短语)的短语)这时这时b b和和A A不同不同时归约,分属于不同的短语,时归约,分属于不同的短语,则必有则必有S SBABA ,这样在句型,这样在句型BABA 中,存在相邻的非终结符,中,存在相邻的非终结符,所以所以与性质与性质1 1矛盾矛盾。故:故: 中任何含中任何含b b的短语必包含的短语必包含A A,证毕。证毕。* *注意:含注意:含b b的短语必含的短语必含A A,含,含A A的短语不一定含的短语不一定含b b。49盛威网:专业的计算机学习网站优先关系的定义优先关系的定义定义定义6.2 6.2 设设G G是一个不含是一个不含产生式的算符文法,产生式的算符文法,A A、B
展开阅读全文