《自底向上分析》PPT课件

《《自底向上分析》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6自底向上分析116.1移进-归约分析(自底向上分析的一般过程)6.2算符优先分析法6.1自底向上分析22若采用自左向右的描述和分析输入串,那么自底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的句柄(最左简单短语)，并利用有关规则进行规约，若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。基本算法思想:33分析过程是重复一下步骤：1、找出当前句型的句柄x（或句柄的变形）2、找出以x为右部的规则X::=x3、把x规约为X，产生语法树的一枝关键：找出当前句型的句柄x(或其变形），这不是

2、很容易。6.1移进—规约分析（Shift-reduceparsing)44#S.R.P#符号栈输入串要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。55分析过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有

3、左界符号和识别符号，则表示分析成功，否则失败。#S.R.P#符号栈输入串66例：G[S]:S→aAcBeA→bA→AbB→d输入串为abbcde，检查是否是该文法的合法句子。若采用自底向上分析，即能否一步步规约当前句型的句柄，最终规约到识别符号S。先设立一个符号栈，我们统一符号“#”作为待分析的符号串的左右分界符。作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。分析过程如下表:77步骤符号栈输入符号串动作123456789101112##a#ab#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#S#aAabb

4、cde#bbcde#bcde#bcde#cde#cde#de#e#e####准备.初始化移进移进规约(A→b)移进规约(A→Ab)移进移进规约(B→d)移进规约(S→aAcBe)成功例：G[S]:S→aAcBeA→bA→AbB→d88这一方法简单明了,不断地进行移进规约,关键是确定当前句型的句柄.说明:(1)例子的分析过程是一步步地规约当前句型的句柄该句子的唯一语法树为:aAcBeAbbdS注意两点：（a）栈内符号串+未处理输入符号串=当前句型（b）句柄都在栈顶实际上，以上分析过程并未真正解决句柄的识别问题99(2)未真正解决句

5、柄的识别.上述分析过程的怎样识别句柄的，主要看栈顶符号串是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。因为不能认为:对句型xuY而言若有A→u，即Au就断定u是简单短语，u就是句柄，而是要同时满足SxAY*6.2简单优先分析例:G[S]S→bAbA→(B

6、aB→Aa)(1)先确定符号之间的优先关系优先关系的定义:设X,Y为可能相邻的符号定义:X=YX的优先级等于YXYX的优先级大于Y...1)X=Yif文法中有形如A→·¨XY·¨2)X

7、有形如A→·¨XB·¨的规则，其中BY·¨。3)X>Yif文法中有形如A→·¨BD·¨的规则,其中B·¨X或DY。+...+*+例:G[S]S→bAbb=A,A=b,b<(,bb,a>b,B>bA→(B

8、a(=B,(a,a>a,)>aS→bAbb=A,A=b,b<(,bb,a>b,B>bA→(B

9、a(=B,(a,a>a,)>aSbA(Ba)#S>b=<<>A==(<<=>a>>=)>>#<<=6

10、.3算符优先分析(Operator-PrecedenceParsing)13131)这是一种经典的自底向上分析法，简单直观，并被广泛使用。运算法则:1.乘除的优先大于加减2.同优先级的运算符左大于右3.括号内的优先级大于括号外于是：4+8-6/2*3运算过程和结果唯一。2)称为算符优先分析是因为这种方法是仿效算术式的四则运算而建立起来的，作算术式的四则运算时，为了保证计算结果和过程的唯一性，规定了一个统一的四则运算法则，规定运算符之间的优先关系。6.3.1直观算符优先文法1414例:G[E]E→E+E

11、E*E

12、(E)

13、iVt={

14、+,*,(,),i}这是一个二义文法，要用算符优先法分析有该文法所确定的语言句子。如：i+i*i(1)先确定终结符之间的优先关系优先关系的定义:设a,b为可能相邻的终结符定义:a=ba的优先级等于baba的优先级大于b...15152)例