东北大学秦皇岛分校编译原理课件第六章.ppt

第6章 自底向上优先分析法,自底向上分析法的基本思想及主要方法,自底向上分析法也称移进-归约法。 自底向上分析法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。 从语法树的角度来看：自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。 自底向上分析法的关键在于：如何在每一步归约当中，找到当前句型的句柄，并判断句柄是否唯一。 主要的分析方法有：简单优先分析法、算符优先分析法、LR类分析法。,自底向上分析法中面临的问题及解决方法,采用自底向上分析法分析的每一步中，会遇到两个基本问题： （1）如何找出进行直接归约的简单短语？ （2）找出的简单短语应直接归约到哪一个非终结符号？ 解决方法：由于分析过程是从左往右扫描源程序，所以遇到的第一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，不同的自底向上分析法有不同的解决方法。 简单短语：只经过一次推导得到的短语叫简单短语； 句柄： 句型的最左简单短语。,自底向上分析法的基本实现方法,自底向上分析的基本实现方法是：移进-归约法。 引入“#”作为栈底标志符号。 在整个分析过程中，共有4类动作： （1）移入：读入下一个输入符号并把它下推进栈。 （2）归约：当栈顶的（部分）符号串形成一个句柄时，对此句柄进行归约，把形成句柄的符号串替换为相应的非终结符号。 （3）接受：当识别程序发现栈顶除了栈底标志符号#外仅有识别符号，而输入也以达到右端标志符号#时，便识别出输入符号串是一个句子，执行接受动作并结束本次识别。 （4）报错：发现输入符号串不是句子而无法继续识别。,自底向上优先分析法的基本思想,常见的自底向上的分析算法： （1）优先分析法 （2）LR类分析法 优先分析法分为： （1）简单优先分析法：采用规范归约，考虑所有文法符号（包括终结符号、非终结符号）之间的优先关系。 （2）算符优先分析法：不是规范归约，只考虑算符（即终结符号）之间的优先关系。 自底向上优先分析法的基本思想： 利用文法符号中相邻符号之间的优先关系找出句柄。,简单优先分析法及简单优先文法,简单优先分析法按照文法符号（终结符号和非终结符号）的优先关系确定句柄。 如何确定任意两个文法符号之间的优先关系？ 如何构造优先关系表,补充内容,FIRST关系：U FIRST S存在规则 US（注：S可以是终结符号，也可以是非终结符号。） FIRST关系的传递闭包： FIRST+= FIRST FIRST2 FIRST3 LAST关系： U LAST S存在规则 US（注：S可以是终结符号，也可以是非终结符号。） LAST关系的传递闭包： LAST += LAST LAST 2 LAST 3 ,例：求文法G的FIRST关系和LAST关系,GA：AAf|B BDdc|De Ce DBf, AAf AB BDdc BDe Ce DBf, A FIRST A A FIRST B B FIRST D B FIRST D C FIRST e D FIRST B,FIRST=（A，A），（A，B），（B，D），（C，e），（D，B）, A LAST f A LAST B B LAST c B LAST e C LAST e D LAST f,LAST=（A，f），（A，B），（B，c） ，（B，e） ，（C，e），（D，f）,FIRST=（A，A），（A，B），（B，D），（C，e），（D，B） FIRST2=（A，A），（A，B），（A，D），（B，B），（D，D） FIRST3=（A，A），（A，B），（A，D），（B，D），（D，B） FIRST4= FIRST2 FIRST+= FIRST FIRST2 FIRST3 = (A，A)，(A，B)，(A，D)，(B，D)， (C，e)，(D，B) ，(D，D),LAST=(A，f)，(A，B)，(B，c) ，(B，e) ，(C，e)，(D，f) LAST+=(A，f)，(A，B)，(A，c) ，(A，e) ，(B，c) ，(B，e) ，(C，e)，(D，f),优先关系的形式定义： （1）相等关系 X=Y：当且仅当G中存在规则 AXY （2）小于关系X Y） （3）大于关系XY：当且仅当G中存在规则 ABD，且 B LAST+ X （即B=X）和 D FIRST* Y（即D= Y）。在此限定S为终结符号。 简单优先文法满足条件： （1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。 （2）在文法中任意两个产生式没有相同的右部。 由简单优先文法的定义可知，简单优先文法是无二义性的。,+,+,*,构造优先关系,构造相等关系“=”很简单，只需要顺次考察文法的各规则即可。如：例6.2（1）。 构造大于和小于关系，可以使用如下两个公式：,其中，（FIRST*）为FIRST的自反传递闭包； （LAST+）T为LAST+的逆关系。,例：构造文法GZ的简单优先关系表,GS：SbAb， A（B|a， BAa）,首先构造相等（=）关系。根据文法规则： = = （b，M）, （M，b） ,（，L ），（A，a） ,（a，） ,构造小于（）关系： FIRST= （S，b）,（A，（ ）,（A，a）,（B，A） FIRST+= （S，b） ,（A，（ ） ,（A，a） ,（B，A） ,（B，（） ,（B，a） =（=）（ FIRST+）= （b，（ ）,（b，a）,（，A）,（，（）,（，a） ,构造大于（）关系： LAST=（S，b）,（A，B）,（A，a）,（B，） LAST+=（S，b）,（A，B）,（A，a）,（A，）,（B，） （LAST+）T=（b，S）,（B，A）,（a，A）,（），B）,（），A） = （LAST+）T（=）（FIRST *） = （B，b）,（B，a）,（a，b）,（a，a）,（ ），b）,（ ），a）,文法GZ的优先关系矩阵,课堂练习： 利用公式求出例6.2的三个优先关系，并给出其优先关系矩阵。,简单优先分析法算法,根据给定的简单优先文法构造出相应的简单优先关系表，并将文法的产生式保存，设置符号栈S，再根据如下算符步骤进行分析： （1）将输入符号串a1a2an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。 （2）栈顶当前符号ai尾句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1 ak，为止。 （3）由句柄akai在文法的产生式中查找右部尾akai的产生式，若找到则用相应左部代替句柄，若找不到则出错。 （4）重复上述三个步骤直到规约完输入符号串，栈中只剩文法的开始符号或出错为止。,算符优先分析法,算符优先分析法常用于高级语言的表达式的语法分析。 算符优先关系的形式定义： （1）相等关系 a=b：当且仅当G中存在 Aab 或 AaBb 的规则。 （2）小于关系a b 或 B= Cb （3）大于关系a b：当且仅当G中存在规则 ABb，且 B=a 或 B=aC 算符优先分析法的基本思想：根据算符（广义为终结符号）之间的优先关系来决定如何归约。,+,+,+,+,算符文法及其性质,算符文法的形式定义： 设有一文法G，如果G中没有形如ABC的规则，其中B和C为非终结符，则称G为算符文法，也称OG文法。 算符文法的性质： （1）在算符文法中任何句型都不包含两个相邻的非终结符。 （2）如果Ab（或bA）出现在算符文法的句型中，其中AVN，bVT，则中任何含b的短语必含有A。,算符优先文法及其性质,算符优先文法的形式定义： 设有一不含产生式的算符文法G，如果对任意两个终结符对a,b之间至多只有=、三种关系中的一种成立，则称G是一个算符优先文法。也称为OPG文法。 算符优先文法的性质： 如果aNb或ab出现在句型r中，则a和b之间有且仅有一种优先关系即： （1） 若a b 则 在r中必有含a而不含b的短语存在 （3）若a = b 则 在r中含有a的短语必含有b，反之亦然。,算符优先关系表的构造,由定义直接构造 （1）FIRSTVT集合：FIRSTVT（B）=b|B=b或B=Cb （2）LASTVT集合： LASTVT（B）=a|B=a或B=aC 由关系图法构造 （1）FIRST关系：A FIRST B 当且仅当存在形如 AB 的产生式。 （2）LAST关系： A LAST B 当且仅当存在形如 A B 的产生式。 （3）FIRSTTERM关系：B FIRSTTERM b 当且仅当存在形如 Bb 或 BCb的产生式。 （4）LASTTERM关系：B FIRSTTERM a 当且仅当存在形如 Ba 或 BaC的产生式。 （5）FOLLOWEDB关系：X FOLLOWEDB Y 当且仅当存在形如 AXY 的产生式（X、Y中必须是一个为终结符，另一个为非终结符）。 用公式法构造 （1） =（LAST*）（LASTTERM）T（=）,+,+,+,+,编译方法中对公式的证明： 注意：此处相等关系的符号为“”，与教材采用的符号不同。规则中连接左部与右部的符号也不同，为EBNF中的形式。,例：用公式构造文法GE的算符优先关系表,课堂练习：求该文法的优先关系“”,用程序构造算符优先关系的方法和步骤,教材6.3.3,算符优先分析法与最左素短语,引入最左素短语的目的： 解决在算符优先分析过程中如何寻找句柄的问题。 最左素短语的形式定义： 设有文法GS，其句型的素短语是一个短语，该短语至少包含一个终结符，并且除自身外不包含其他素短语，最左边的素短语称最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。 算符优先分析法的关键问题是寻找最左素短语。 算符优先分析法的局限性：算符优先分析法去掉了单个非终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得到正确的归约。,算符优先分析法算法,算符优先分析法的算法用到一个符号栈S和一个存放输入符号串的数组R，算法中的Q为一工作单元，用于存放待比较的终结符号： （1）将输入符串R1R2RK依次逐个存入符号栈S中，直至符号栈顶元素Sj与下一个待输入的符号Rk有关系Sj Rk为止； （2）最左素短语尾Sj已在符号栈S的栈顶，由此往前（左）在栈中找最左素短语的头