网络编程 第6章ppt课件.ppt

《网络编程 第6章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章自底向上分析【学习目标】算符优先分析法是自下而上（自底向上）语法分析的一种，尤其适应于表达式的语法分析，是学习其它自下而上语法分析的基础。通过本章学习应掌握：对给定的文法能够判断该文法是否是算符文法对给定的算符文法能构造算符优先关系表，并能利用算符优先关系表判断该文法是否是算符优先文法能应用算符优先分析算法对给定的输入串进行移进-归约分析，并能判断所给的输入串是否是该文法的句子了解算符优先分析法的优缺点和实际应用中的局限性【学习指南】算符优先分析法是自下而上语法分析的一种，它的算法简单、直观、

2、易于理解，故通常作为学习其它自下而上语法分析的基础。在学习前，应复习有关语法分析的知识，如：什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念【难重点】应该知道算符文法的形式对一个给定的算符文法能构造算符优先关系分析表，并能判别所给文法是否为算符优先文法分清规范句型的句柄和最左素短语，进而分清算符优先规约和规范规约算符优先分析的可归约串是句型的最左素短语，应掌握在分析过程中如何寻找可归约串是算符优先分析的关键问题能根据算符优先关系分析表判断所给输入串是否为文法的句子概论思

3、想自下而上的语法分析过程是最右推导的逆过程（最左归约），即从输入串开始，朝着文法开始符号进行归约，直至到达文法开始符号为止的过程。核心寻找句型中的“句柄”进行归约，用不同的方法寻找句柄，就可获得不同的分析方法一、规范归约归约G=(VT，VN，S，P)，α、β∈(VT∪VN)*，A→β∈P，αAwαβw归约的过程是:已知αβw和产生式A→β，用产生式A→β左部A替换αβw中的β，得到符号串αAw。规范推导(最右推导)右句型(最右推导可得的句型，规范句型)6.1自底向上分析规范归约规范归约是最右推导的

4、逆过程如果文法G是无二义的，那么，规范推导(最右推导)的逆过程必是规范归约(最左归约)，且唯一规范句型的特点：句柄后不会出现非终结符号例G[S],其产生式如下：    ①S→aAcBe②A→b③A→Ab④B→d对输入串abbcde#进行分析abbcdeAabbcdeAaAbcdeBSaAcdeaAcBe最右推导SabbcdeaAbcdeaAcdeaAcBebAbdaAcBe句型句柄句柄后不会出现非终结符号SaAcBeaAcdeaAbcdeabbcde输入串abbcdeaAbcdea

5、AcdeaAcBeSabbcdeAS→aAcBeAB→dBSA→AbA→b最右推导SaAcBeaAcdeaAbcdeabbcdeaAcBedAbb句型句柄归约用规则例G[S],其产生式如下：    ①S→aAcBe②A→b③A→Ab④B→d对输入串abbcde#进行分析A→bA→AbB→dS→aAcBe二义性文法存在规范归约不唯一的句子。例如，文法G[E]:E→E＋EE*E(E)id句子id＋id*id有二个不同的最右推导 :EE+EEE*EE＋E*EE*id3E＋E*id3E+

6、E*id3E+id2*id3E+id2*id3id1+id2*id3id1+id2*id3句型E＋E*id3中 ，句柄不唯一 。规范归约的中心问题是：如何寻找或确定一个句型的句柄二、自底向上分析方法从一个给定的输入符号串本身出发,试图逐步归约为文法的开始符号。从树叶(底)开始向上构造直到树根(顶)。从输入符号串出发，每次从被归约的句型中找到最左边的某个产生式的右部，用其左部替换之，得到新的句型，直至归约到文法的开始符号关键技术：在自底向上分析中，如何寻找或确定一个句型的句柄，是构造一个自左向

7、右扫描、自底向上分析方法必须要解决的一个关键问题自底向上分析方法——移进—归约“移进一归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为:栈        剩余输入符号串#       w#工作过程：自左至右把串w的符号一一移进栈里，边移进边归约。一旦栈顶形成句柄时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至分析器的终止状态为:栈        剩余输入符号串#S        #1##a23#ab4#aA5#aAb

8、6#aA78#aAc#aAcd9#aAcB10#S11#aAcBeabbcdeaAbcdeaAcdeaAcBeG[S]:SaAcBeAbAbBdabbcde#bbcde#bcde#bcde#cde#cde#de#e#e###移进移进归约Ab移进归约AAb移进移进归约Bd移进归约SaAcBe接受栈中符号串加上未扫描的输入串即是一个（右）句型S工作模型：堆栈的初始状态与终止状态；移进／归约／接受／出错，一共四种动作（暂不理会什么是可归约串）直观理解