《第六章-自底向上优先分析课件》由会员分享，可在线阅读，更多相关《第六章-自底向上优先分析课件（111页珍藏版）》请在金锄头文库上搜索。
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，产生语法树的一枝产生语法树的一枝关键关键关键关键：找出当前句型的句柄：找出当前句型的句柄：找
5、出当前句型的句柄：找出当前句型的句柄x x x x( ( ( (或其变形），这不是很容易。或其变形），这不是很容易。或其变形），这不是很容易。或其变形），这不是很容易。9盛威网：专业的计算机学习网站2.2.实现方式实现方式- -“移进归约移进归约”方式方式 语法分析程序 语法表 a+b#输出带#p 自左至右把输入串的符号逐个自左至右把输入串的符号逐个移进移进栈栈【注注】初态时栈内仅有栈底符初态时栈内仅有栈底符“”，读头指在最左边的单词符号上。读头指在最左边的单词符号上。 p 若栈顶形成某个句型的句柄，就将此句柄用相应的若栈顶形成某个句型的句柄，就将此句柄用相应的产生式左部替换（产生式左部替换（
6、归约归约），若再形成句柄，就继续替），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止。换，直到栈顶不再形成句柄为止。p重复上面的过程直到栈顶只剩下重复上面的过程直到栈顶只剩下# #和文法的和文法的开始符号开始符号，同时输入串读完为止，这样就认为识别了一个句子。同时输入串读完为止，这样就认为识别了一个句子。10盛威网：专业的计算机学习网站3.3.语法分析程序执行的动作语法分析程序执行的动作移进移进 读入下一个输入符号并压入栈内，读头后移；归归约约 检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式；接接受受 移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头
7、也指向语句的结束符； 报报错错 当识别程序察觉一个错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。11盛威网：专业的计算机学习网站例例1：文法：文法GS：(1) S aAcBe(2) A b(3) A 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、 8） #aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约(S aAcBe)符号串符号串abbcdeabbcde是否是是否是GSGS的句子的句子对输入串对输入串abbcde#的移进的移进-归约分析过程归约分析过程SaAcBe aAcde aAbcde abbcde12盛威网：专业的计算机学习网站顺序扫描输入符号并依次移进栈栈顶部的符号串是否构成一句柄？YN进行一次归约输入串扫描完否？noY栈中仅有开始符号？noerror输入串合法，报告分析报告出口移进移进- -归约过程归约过程Y13盛威网：专业的计算机学习网站（1
9、 1）例子的分析过程是一步步地归约）例子的分析过程是一步步地归约）例子的分析过程是一步步地归约）例子的分析过程是一步步地归约当前句型当前句型当前句型当前句型的句柄的句柄的句柄的句柄该句子的唯一语法树为该句子的唯一语法树为该句子的唯一语法树为该句子的唯一语法树为: :a aA Ac cB Be eA Ab bb bd dS S注意两点：注意两点：注意两点：注意两点：（a a）栈内符号串）栈内符号串）栈内符号串）栈内符号串+未处理输入符号串未处理输入符号串未处理输入符号串未处理输入符号串 = = 当前句型当前句型当前句型当前句型（b b）句柄都在栈顶）句柄都在栈顶）句柄都在栈顶）句柄都在栈顶实际上
10、，以上分析过程并未真正解决句柄的识别问题实际上，以上分析过程并未真正解决句柄的识别问题实际上，以上分析过程并未真正解决句柄的识别问题实际上，以上分析过程并未真正解决句柄的识别问题说明说明:14盛威网：专业的计算机学习网站（2 2）未真正解决句柄的识别）未真正解决句柄的识别）未真正解决句柄的识别）未真正解决句柄的识别* *上述分析过程是怎样上述分析过程是怎样上述分析过程是怎样上述分析过程是怎样识别句柄识别句柄识别句柄识别句柄的，主要看栈顶符号串的，主要看栈顶符号串的，主要看栈顶符号串的，主要看栈顶符号串 是否形成规则的右部。是否形成规则的右部。是否形成规则的右部。是否形成规则的右部。这种做法形式
11、上是正确的，但在实际上不一定正确。这种做法形式上是正确的，但在实际上不一定正确。这种做法形式上是正确的，但在实际上不一定正确。这种做法形式上是正确的，但在实际上不一定正确。 举例的分析过程可以说是一种巧合。举例的分析过程可以说是一种巧合。举例的分析过程可以说是一种巧合。举例的分析过程可以说是一种巧合。 因为不能认为因为不能认为因为不能认为因为不能认为: : : :对句型对句型对句型对句型 xuyxuyxuyxuy 而言，若有而言，若有而言，若有而言，若有U U U Uuuuu，即，即，即，即U U U Uu u u u 就就就就断定断定断定断定u u u u是简单短语，是简单短语，是简单短语，
12、是简单短语，u u u u就是句柄，就是句柄，就是句柄，就是句柄，而是要同时满足而是要同时满足而是要同时满足而是要同时满足 Z Z Z Z xUyxUyxUyxUy15盛威网：专业的计算机学习网站一.优先分析法的类别6.1自底向上优先分析概述1.1.优先分析器（优先分析器（Precedence ParserPrecedence Parser）简单优先分析法简单优先分析法算符优先分析法算符优先分析法2.LR2.LR分析器分析器16盛威网：专业的计算机学习网站二.简单优先分析法基本思想基本思想：按一定原则定义文法中所有符号：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照（终结
13、符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。这种关系确定归约过程中的句柄并实行归约。是一种规范归约。是一种规范归约。简单优先分析法准确、规范，但效率低，不实简单优先分析法准确、规范，但效率低，不实用，不流行。用，不流行。17盛威网：专业的计算机学习网站三.算符优先分析法基本思想基本思想：只定义文法中终结符之间的优先：只定义文法中终结符之间的优先关系（关系（不考虑非终结符不考虑非终结符），并由这种关系指），并由这种关系指导分析过程导分析过程不是规范归约不是规范归约算符优先分析法分析速度快，特别适用于表算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常
14、常要采用适达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。当措施克服其缺点。 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 BYY（3 3） X XY Y当且仅当当且仅当G G中存在产生式规则中存在产生式规则 A ABD,BD,且且B B XX和和D D YY20盛威网：专业的计算机学习网站三.从语法树判别优先
15、性设设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: :stst; ;情况情况2 2: :s=ts=t; ;情况情况3 3: :ststA s t .A s t .A s t .21盛
16、威网：专业的计算机学习网站 另外另外, ,还有一种情况还有一种情况, ,就是就是s s和和t t均不在句柄中均不在句柄中, ,那么那么一定存在某句型使得它们进入上述三种情况之一。一定存在某句型使得它们进入上述三种情况之一。 若若s s和和t t在任何句型中都不可能相邻出现在任何句型中都不可能相邻出现, ,则我们规则我们规定二者定二者无关系无关系无关系无关系。 注意注意注意注意, ,这种优先关系是这种优先关系是不对称不对称不对称不对称的的! !22盛威网：专业的计算机学习网站在句型中，句柄内各相邻符号之间具有相同的优先级。u结论由于句柄要先归约，所以规定句柄两端符号的优先级 要比位于句柄之外的相邻符号的优先级高。 句型中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
