自底向上优先分析法.PPT
《自底向上优先分析法.PPT》由会员分享,可在线阅读,更多相关《自底向上优先分析法.PPT(59页珍藏版)》请在三一文库上搜索。
1、1,自底向上优先分析法,掌握:构造算符优先关系表,进行算符优先分析,构造优先函数 理解:算符优先文法,最左素短语 了解:简单优先分析法,2,1 自底向上分析方法概述,基本思想 从输入符号串开始,利用文法的产生式逐步进行归约,试图归约到文法开始符 从语法树角度看,是以输入符号串作为语法树的末端结点符号串,自底向上的构造语法树,使文法开始符正好是该语法树的根。如果最终根结点是开始符,则输入符号串是语言的一个句子,否则不是。 自底向上分析过程实际上是一个不断进行直接归约的过程。,遇到的问题 如何找出进行直接归约的“可归约串”(句柄) 基本实现方法“移进归约”方法 引进一个先进后出的符号栈来存放符号
2、对输入符号串自左向右进行扫描,并把当前输入符号下推入栈中(移进), 边移进边分析,一旦栈顶符号串形成某个句型的句柄(为某产生式的右部)时,就用相应的非终结符(产生式的左部)替换它(归约)。 重复这一过程,直到输入符号串的末端,此时如果栈中只剩文法开始符号,则输入符号串是文法的句子,否则不是。,4,规范归约: 自底向上分析的移进归约过程是自顶向下最右推导的逆过程,因为最右推导为规范推导,所以自左向右的归约称为规范归约。,例 文法: (1) SaAcBe (2) Ab (3) AAb (4) Bd 输入串 abbcde#的最右推导的过程为: S=aAcBe=aAcde=aAbcde=abbcde
3、自底向上分析的过程为: abbcde|-aAbcde|-aAcde|-aAcBe|-S,例 文法: (1) SaAcBe (2) Ab (3) AAb (4) Bd 判断输入串 abbcde# 是否为该文法的句子,用符号栈对输入符号串自底向上的分析过程为:,6,关键问题:如何在分析的过程中确定句柄 何时移进?栈顶末形成句柄 何时归约?栈顶形成句柄 常用自底向上分析法: 算符优先分析法 LR类分析法,7,2 自底向上优先分析法概述,优先分析法两类: 简单优先分析法 基本思想:按一定原则定义文法中所有符号(终结符和非终结符)之间的优先关系,按照这种关系确定归约过程中的句柄并实行归约。 是一种规范归
4、约。 简单优先分析法准确、规范,但效率低,不实用。,8,算符优先分析法 基本思想:只定义文法中终结符之间的优先关系(不考虑非终结符),并由这种关系指导分析过程 不是规范归约 算符优先分析法分析速度快,特别适用于表达式的分析。缺点是不规范,常常要采用适当措施克服其缺点。,9,3 算符优先分析法,算符优先分析法特别适用于表达式的分析 从表达式得到的启发: 表达式的归约顺序与运算顺序是一样的 通常算术表达式的运算次序是先乘除后加减,同优先级时服从左结合,EE+T|T TTF|F F(E)|i,符号串E+T+TF的归约过程为: E+T+TF |- E+TF |- E+T |- E,10,运算次序只与运
5、算符(优先级,结合性)有关,与运算对象无关 可以根据运算符(终结符)的优先关系指导归约过程,与运算对象(非终结符)无关,11,3.1 优先关系,优先关系只存在于句型中相邻出现的符号 相邻:算符优先分析法只考虑终结符之间的优先关系,不考虑非终结符,所以两个终结符相邻指其中没有其他的终结符(但可以有非终结符) 如:E+Ti,和相邻,和i相邻, 但和i不相邻 终结符间优先关系表示: 终结符a和b之间的优先关系表示如下: ab 表示a的优先级高于b,优先关系定义的依据 在当前句柄中的符号优先于与其相邻的不在句柄中的符号被归约,其优先关系大 同一句柄中的相邻符号同时被归约,其优先关系相同,不可能相邻出现
6、在任何句型中的两个符号,无法比较其归约的先后,故它们之间无优先关系,EE+T|T TTF|F F(E)|i,E,E,+,T,T,F,(,E,),句型(E)+T的句柄是(E) , 所以) + ( = ),注意:是三种有序关系,与数学中的不同,所以a=b不意味b=a,ab不意味ba,E,E,+,T,T,F,(,E,),如:(=),但是)=(不成立,因为)和(不可能相邻出现在任何句型中,它们之间没有优先关系,EE+T|T TTF|F F(E)|i,E,T,F,(,E,),E,+,T,在句型(E)+T中得 ) +,在(E+T)中得 + ),按公认的计算顺序规定优先级和结合性,得到优先关系如下: ,/的
7、优先级高,遵循左结合,得, /, /, / +,-的优先级低,遵循左结合,得+, +-, -, + (, )规定括号的优先级大于括号外的运算符,小于括号内的运算符,如E + ( E + T ),有 + # 运算对象 i 的优先级最高 优先关系表如右图所示:,说明:表中为空的元素表示:在该文法的任何句型中都不会出现这两个终结符相邻,所以他们无优先关系,如不会有这样的表达式 ) i ,15,算符优先分析法 1 文法要满足一定的条件,即为算符优先文法 2 根据文法按一定规则计算算符之间的优先关系 3 按优先关系进行算符优先分析,16,3.2 算符优先文法的定义,1 算符文法 定义: 设有上下文无关文
8、法 G ,如果G中产生式的右部没有两个非终结符相连,则称G为算符文法(Operater Grammar),也称OG文法 例如: 表达式文法 EE+E|EE|(E)|i 是算符文法 性质: (1) 在算符文法中任何句型都不包含两个相连的非 终结符。,17,证明:用反证法。因为由算符文法的性质1知可有: S = =bA 若存在B = b,这时b和A不同时归约,则必有S = BA,这样在句型BA中存在相邻的非终结符B和A,所以与性质1矛盾,证毕。注意:含b的短语必含A,含A的短语不一定含b。,(2) 如果Ab或bA出现在算符文法的句型r中,其中A VN,b VT,则r中任何含b的短语必含有A(含A的
9、短语不一定含有b),句型E+T+TF 短语有: E+T TF E+T+TF,2 算符优先关系的定义 设G是一个不含产生式的算符文法,a和b是任意两个终结符,A,B,C是非终结符,算符优先关系定义如下: a = b 当且仅当G中有形如 Aab 或 AaBb 的产生式。,说明:为或B,a,b在用一句柄中同时归约所以优 先级相同,a,b,A,例如:有产生式F(E) 所以( = ),a + b 或 B=+ Cb,说明:为或C,a,b不在同一句柄中,b先归约, 所以a的优先级低于b,a,B,A,P,b,文法EE+T|T TTF|F F(E)|i 由EE+T T=+ TF 得+,a b 当且仅当G中有形如
10、 ABb 的产生式, 且 B=+ a 或 B=+ aC,说明: 为或C ,a,b不在同一句柄中,a先归约, 所以a的优先级大于b,b,B,A,P,a,文法EE+T|T TTF|F F(E)|i 由EE+T E=+ TF 得+,3 算符优先文法 定义: 设有一不含产生式的算符文法G,如果对任意两个终结符对a,b之间至多只有一种优先关系成立,则称G是一个算符优先文法(Operater Precedence Grammar),即OPG文法。 说明: 两个终结符之间的优先关系是有序的,算符优先文法允许ab,ba同时存在,而不允许有ab,a ) ,) +同时存 在,不允许 + ) 和 + ) 同时存在,
11、22,例 表达式文法 EE+E|EE|(E)|i 由EE+E且E=+ EE得+ E+E得 +和的优先关系不唯一,所以不是算符优先文法,包含优先级和结合性的表达式文法是算符优先文法 EE+T|T TTF|F F(E)|i,23,3.3 算符优先关系表的构造,最左终结符集FIRSTVT FIRSTVT(B)=b|B=+ b 或 B=+ Cb 其中bVT, B,CVN 直观上说FIRSTVT(B)是由B推导出的最左终结符(允许左边有一非终结符)的集合。 与FIRST() = a VT | * a 对照 文法符号串的开始符号集是由推导出的开头的终结符(包括)组成,24,例文法: EE+T|T TTF|
12、F F(E)|i,FIRSTVT(F)=(,i FIRSTVT(T)=,(,i FIRSTVT(E)=+,(,i,FIRST(F)=(,i FIRST(T)=(,i FIRST(E)=(,i,25,构造FIRSTVT(A)的算法 令每个非终结符的FIRSTVT集为空 依次扫描文法中的每条产生式,根据规则(a)(b),求各非终结符的FIRSTVT集 (a)若产生式Aa,或ABa, 则aFIRSTVT(A); (b)若有产生式AB,且aFIRSTVT(B), 则aFIRSTVT(A) 重复2),直到每个FIRSTVT集合都不发生变化为止,例 文法: EE+T|T TTF|F F(E)|i 求各非终
13、结符的FIRSTVT集,第三次,F,T,E,第二次,(,i,+,第一次,第四次迭代的时候,E、T、F 的FIRSTVT集都不再发生变换,算法终止, (,i, (,i,(a)若产生式Aa,或ABa,则aFIRSTVT(A); (b)若有产生式AB,且aFIRSTVT(B),则aFIRSTVT(A),27,最右终结符集LASTVT LASTVT(B)=a|B=a 或 B=aC 其中aVT, B,CVN 直观上说LASTVT(B)是由B推导出的最右终结符(允许右边有一非终结符)的集合。,例文法: EE+T|T TTF|F F(E)|i,LASTVT(F)=),i LASTVT(T)=,),i LAS
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 向上 优先 分析
链接地址:https://www.31doc.com/p-2762262.html