《东北大学秦皇岛分校编译原理课件第六章.ppt》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校编译原理课件第六章.ppt（30页珍藏版）》请在金锄头文库上搜索。
1、第第6章章 自底向上优先分析法自底向上优先分析法自底向上分析法的基本思想及主要方法自底向上分析法的基本思想及主要方法v 自底向上分析法也称移进自底向上分析法也称移进-归约法。归约法。v 自底向上分析法的基本思想是：自底向上分析法的基本思想是：从待输入的符号串开始，从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。利用文法的规则步步向上归约，试图归约到文法的识别符号。v 从语法树的角度来看：从语法树的角度来看：自底向上分析的过程是以输入符号串作自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正为末端结点符号串，向着根结点的方
2、向往上构造语法树，使识别符号正好是该语法树的根结点。好是该语法树的根结点。v 自底向上分析法的关键在于：自底向上分析法的关键在于：如何在每一步归约当中，找如何在每一步归约当中，找到当前句型的句柄，并判断句柄是否唯一。到当前句型的句柄，并判断句柄是否唯一。v 主要的分析方法有：主要的分析方法有：简单优先分析法、算符优先分析法、简单优先分析法、算符优先分析法、LR类类分析法。分析法。自底向上分析法中面临的问题及解决方法自底向上分析法中面临的问题及解决方法vv 采用自底向上分析法分析的每一步中，会遇到两个采用自底向上分析法分析的每一步中，会遇到两个采用自底向上分析法分析的每一步中，会遇到两个采用自底
3、向上分析法分析的每一步中，会遇到两个基本问题：基本问题：基本问题：基本问题：（1 1）如何找出进行直接归约的简单短语？）如何找出进行直接归约的简单短语？）如何找出进行直接归约的简单短语？）如何找出进行直接归约的简单短语？（2 2）找出的简单短语应直接归约到哪一个非终结符号？）找出的简单短语应直接归约到哪一个非终结符号？）找出的简单短语应直接归约到哪一个非终结符号？）找出的简单短语应直接归约到哪一个非终结符号？vv 解决方法：解决方法：解决方法：解决方法：由于分析过程是从左往右扫描源程序，所以遇到的第由于分析过程是从左往右扫描源程序，所以遇到的第由于分析过程是从左往右扫描源程序，所以遇到的第由于
4、分析过程是从左往右扫描源程序，所以遇到的第一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，不同的自底向上分析法有不同的解决方法不同的自底向上分析法有不同
5、的解决方法不同的自底向上分析法有不同的解决方法不同的自底向上分析法有不同的解决方法。vv 简单短语：简单短语：简单短语：简单短语：只经过一次推导得到的短语叫简单短语；只经过一次推导得到的短语叫简单短语；只经过一次推导得到的短语叫简单短语；只经过一次推导得到的短语叫简单短语；vv 句柄：句柄：句柄：句柄： 句型的最左简单短语。句型的最左简单短语。句型的最左简单短语。句型的最左简单短语。自底向上分析法的基本实现方法自底向上分析法的基本实现方法v 自底向上分析的基本实现方法是：自底向上分析的基本实现方法是：自底向上分析的基本实现方法是：自底向上分析的基本实现方法是：移进移进移进移进- -归约法。归约
6、法。归约法。归约法。vv 引入引入引入引入“ “# #” ”作为栈底标志符号。作为栈底标志符号。作为栈底标志符号。作为栈底标志符号。vv 在整个分析过程中，共有在整个分析过程中，共有在整个分析过程中，共有在整个分析过程中，共有4 4类动作：类动作：类动作：类动作：（1 1）移入：）移入：）移入：）移入：读入下一个输入符号并把它下推进栈。读入下一个输入符号并把它下推进栈。读入下一个输入符号并把它下推进栈。读入下一个输入符号并把它下推进栈。（2 2）归约：）归约：）归约：）归约：当栈顶的（部分）符号串形成一个句柄时，对当栈顶的（部分）符号串形成一个句柄时，对当栈顶的（部分）符号串形成一个句柄时，对
7、当栈顶的（部分）符号串形成一个句柄时，对此句柄进行归约，把形成句柄的符号串替换为相应的非终结此句柄进行归约，把形成句柄的符号串替换为相应的非终结此句柄进行归约，把形成句柄的符号串替换为相应的非终结此句柄进行归约，把形成句柄的符号串替换为相应的非终结符号。符号。符号。符号。（3 3）接受：）接受：）接受：）接受：当识别程序发现栈顶除了栈底标志符号当识别程序发现栈顶除了栈底标志符号当识别程序发现栈顶除了栈底标志符号当识别程序发现栈顶除了栈底标志符号# #外仅外仅外仅外仅有识别符号，而输入也以达到右端标志符号有识别符号，而输入也以达到右端标志符号有识别符号，而输入也以达到右端标志符号有识别符号，而输
8、入也以达到右端标志符号# #时，便识别出输时，便识别出输时，便识别出输时，便识别出输入符号串是一个句子，执行接受动作并结束本次识别。入符号串是一个句子，执行接受动作并结束本次识别。入符号串是一个句子，执行接受动作并结束本次识别。入符号串是一个句子，执行接受动作并结束本次识别。（4 4）报错：）报错：）报错：）报错：发现输入符号串不是句子而无法继续识别。发现输入符号串不是句子而无法继续识别。发现输入符号串不是句子而无法继续识别。发现输入符号串不是句子而无法继续识别。自底向上优先分析法的基本思想自底向上优先分析法的基本思想 v 常见的自底向上的分析算法：常见的自底向上的分析算法：常见的自底向上的分
9、析算法：常见的自底向上的分析算法：（1 1）优先分析法）优先分析法）优先分析法）优先分析法（2 2）LRLR类分析法类分析法类分析法类分析法vv 优先分析法分为：优先分析法分为：优先分析法分为：优先分析法分为：（1 1）简单优先分析法）简单优先分析法）简单优先分析法）简单优先分析法：采用规范归约，考虑所有文法符号（包括采用规范归约，考虑所有文法符号（包括采用规范归约，考虑所有文法符号（包括采用规范归约，考虑所有文法符号（包括终结符号、非终结符号）之间的优先关系。终结符号、非终结符号）之间的优先关系。终结符号、非终结符号）之间的优先关系。终结符号、非终结符号）之间的优先关系。（2 2）算符优先分
10、析法）算符优先分析法）算符优先分析法）算符优先分析法：不是规范归约，只考虑算符（即终结符号）不是规范归约，只考虑算符（即终结符号）不是规范归约，只考虑算符（即终结符号）不是规范归约，只考虑算符（即终结符号）之间的优先关系。之间的优先关系。之间的优先关系。之间的优先关系。vv 自底向上优先分析法的基本思想：自底向上优先分析法的基本思想：自底向上优先分析法的基本思想：自底向上优先分析法的基本思想：利用文法符号中相邻符号之间的优先关系找出句柄。利用文法符号中相邻符号之间的优先关系找出句柄。利用文法符号中相邻符号之间的优先关系找出句柄。利用文法符号中相邻符号之间的优先关系找出句柄。简单优先分析法及简单
11、优先文法简单优先分析法及简单优先文法vv 简单优先分析法按照文法符号（终结符号和非终简单优先分析法按照文法符号（终结符号和非终简单优先分析法按照文法符号（终结符号和非终简单优先分析法按照文法符号（终结符号和非终结符号）的优先关系确定句柄。结符号）的优先关系确定句柄。结符号）的优先关系确定句柄。结符号）的优先关系确定句柄。vv如何确定任意两个文法符号之间的优先关系？如何确定任意两个文法符号之间的优先关系？如何确定任意两个文法符号之间的优先关系？如何确定任意两个文法符号之间的优先关系？vv如何构造优先关系表如何构造优先关系表如何构造优先关系表如何构造优先关系表补充内容补充内容n nFIRST关系：
12、关系：U U FIRSTFIRST S S存在规则存在规则存在规则存在规则 U USS（注：（注：（注：（注：S S可可可可以是以是以是以是终结终结符号，也可以是非符号，也可以是非符号，也可以是非符号，也可以是非终结终结符号。）符号。）符号。）符号。）FIRSTFIRST关系的关系的关系的关系的传递闭传递闭包：包：包：包：FIRSTFIRST+ += = FIRST FIRST FIRSTFIRST2 2 FIRSTFIRST3 3 n nLAST关系：关系： U U LASTLAST S S存在规则存在规则存在规则存在规则 U USS（注：（注：（注：（注：S S可可可可以是以是以是以是终结
13、终结符号，也可以是非符号，也可以是非符号，也可以是非符号，也可以是非终结终结符号。）符号。）符号。）符号。） LASTLAST关系的关系的关系的关系的传递闭传递闭包：包：包：包： LASTLAST + += = LAST LAST LAST LAST 2 2 LAST LAST 3 3 例：求文法例：求文法G的的FIRST关系和关系和LAST关系关系GA：AAf|BBDdc|DeCeDBf AAfAAf ABAB BDdcBDdc BDeBDe CeCe DBfDBf A FIRST A A FIRST A A FIRST B A FIRST B B FIRST D B FIRST D B F
14、IRST D B FIRST D C FIRST e C FIRST e D FIRST B D FIRST BFIRST=FIRST=（A A，A A），（），（），（），（A A，B B），（），（），（），（B B，D D），（），（），（），（C C，e e），（），（），（），（D D，B B） A LAST f A LAST f A LAST B A LAST B B LAST c B LAST c B LAST e B LAST e C LAST e C LAST e D LAST f D LAST fLAST=LAST=（A A，f f），（），（），（），（A A，B B），
15、（），（），（），（B B，c c） ，（，（，（，（B B，e e） ，（，（，（，（C C，e e），（），（），（），（D D，f f） FIRST= FIRST=（A A，A A），（），（），（），（A A，B B），（），（），（），（B B，D D），（），（），（），（C C，e e），（），（），（），（D D，B B） FIRST FIRST2 2=（A A，A A），（），（），（），（A A，B B），（），（），（），（A A，D D），（），（），（），（B B，B B），（），（），（），（D D，D D） FIRST FIRST3 3=（A A，A A），（），
16、（），（），（A A，B B），（），（），（），（A A，D D），（），（），（），（B B，D D），（），（），（），（D D，B B） FIRST FIRST4 4= FIRST= FIRST2 2 FIRSTFIRST+ += = FIRSTFIRST FIRSTFIRST2 2 FIRST FIRST3 3 = (A= (A，A)A)，(A(A，B)B)，(A(A，D)D)，(B(B，D)D)， (C(C，e)e)，(D(D，B)B) ，(D(D，D)D)LAST=(ALAST=(A，f) f)，(A(A，B)B)，(B(B，c)c) ，(B(B，e)e) ，(C(C，e)e)，
17、(D(D，f)f)LASTLAST+ +=(A=(A，f) f)，(A(A，B)B)，(A(A，c) c) ，(A(A，e) e) ，(B(B，c)c) ，(B(B，e)e) ，(C(C，e)e)，(D(D，f)f)vv 优先关系的形式定义：优先关系的形式定义：优先关系的形式定义：优先关系的形式定义：（1 1）相等关系）相等关系）相等关系）相等关系 X X=Y=Y：当且仅当当且仅当当且仅当当且仅当GG中存在规则中存在规则中存在规则中存在规则 A AXYXY（2 2）小于关系小于关系小于关系小于关系X XY YB= Y）（3 3）大于关系大于关系大于关系大于关系X XYY：当且仅当当且仅当当且仅
18、当当且仅当GG中存在规则中存在规则中存在规则中存在规则 A ABDBD，且且且且 B LASTB LAST+ + X X （即即即即B=XB=X）和和和和 D FIRST* YD FIRST* Y（即即即即D= YD= Y）。在此限定。在此限定。在此限定。在此限定S S为终结符号。为终结符号。为终结符号。为终结符号。vv 简单优先文法满足条件：简单优先文法满足条件：简单优先文法满足条件：简单优先文法满足条件：（1 1）在文法符号集在文法符号集在文法符号集在文法符号集V V中，任意两个符号之间最多只有一种优先关系成立。中，任意两个符号之间最多只有一种优先关系成立。中，任意两个符号之间最多只有一种
19、优先关系成立。中，任意两个符号之间最多只有一种优先关系成立。（2 2）在文法中任意两个产生式没有相同的右部。在文法中任意两个产生式没有相同的右部。在文法中任意两个产生式没有相同的右部。在文法中任意两个产生式没有相同的右部。vv 由简单优先文法的定义可知，简单优先文法是无二义性的。由简单优先文法的定义可知，简单优先文法是无二义性的。由简单优先文法的定义可知，简单优先文法是无二义性的。由简单优先文法的定义可知，简单优先文法是无二义性的。+* *构造优先关系构造优先关系n n构造相等关系构造相等关系构造相等关系构造相等关系“ “=”=”很简单，只需要顺次考察文法很简单，只需要顺次考察文法很简单，只需
20、要顺次考察文法很简单，只需要顺次考察文法的各规则即可。如：例的各规则即可。如：例的各规则即可。如：例的各规则即可。如：例6.26.2（1 1）。）。）。）。n n构造大于和小于关系，可以使用如下两个公式：构造大于和小于关系，可以使用如下两个公式：构造大于和小于关系，可以使用如下两个公式：构造大于和小于关系，可以使用如下两个公式：其中，（其中，（其中，（其中，（FIRSTFIRST* *）为）为）为）为FIRSTFIRST的自反传递闭包；的自反传递闭包；的自反传递闭包；的自反传递闭包； （LASTLAST+ +）T T为为为为LASTLAST+ +的逆关系。的逆关系。的逆关系。的逆关系。例：构造
21、文法例：构造文法GZ的简单优先关系表的简单优先关系表GSGS：S SbAbbAb， AA（B|aB|a， BAaBAa）首先构造相等（首先构造相等（首先构造相等（首先构造相等（= =）关系。根据文法规则：）关系。根据文法规则：）关系。根据文法规则：）关系。根据文法规则：= = = = （b b，MM）, , （MM，b b） , ,（，（，（，（，L L ），（），（），（），（A A，a a） , ,（a a，），），），） 构造小于（构造小于（构造小于（构造小于（ ）关系：）关系：）关系：）关系：FIRST= FIRST= （S S，b b）, ,（A A，（，（，（，（ ）, ,（A A
22、，a a）, ,（B B，A A） FIRSTFIRST+ += = （S S，b b） , ,（A A，（，（，（，（ ） , ,（A A，a a） , ,（B B，A A） , ,（B B，（），（），（），（） , ,（B B，a a） = ）关系：）关系：）关系：）关系：LAST=LAST=（S S，b b）, ,（A A，B B）, ,（A A，a a）, ,（B B，），），），） LASTLAST+ +=（S S，b b）, ,（A A，B B）, ,（A A，a a）, ,（A A，），），），）, ,（B B，），），），） （LASTLAST+ +）T T=（b b，S S
23、）, ,（B B，A A）, ,（a a，A A）, ,（），（），（），（），B B）, ,（），（），（），（），A A） = = （LASTLAST+ +）T T（= =）（）（）（）（FIRST *FIRST *） = = （B B，b b）, ,（B B，a a）, ,（a a，b b）, ,（a a，a a）, ,（ ），），），），b b）, ,（ ），），），），a a） SbABa（）Sb=a=（=文法文法文法文法GZGZ的优先关系矩阵的优先关系矩阵的优先关系矩阵的优先关系矩阵课堂练习：课堂练习：利用公式求出例利用公式求出例6.2的三个优先关系，的三个优先关系，并给出其优先关
24、系矩阵。并给出其优先关系矩阵。简单优先分析法算法简单优先分析法算法根据给定的简单优先文法构造出相应的简单优先关根据给定的简单优先文法构造出相应的简单优先关根据给定的简单优先文法构造出相应的简单优先关根据给定的简单优先文法构造出相应的简单优先关系表，并将文法的产生式保存，设置符号栈系表，并将文法的产生式保存，设置符号栈系表，并将文法的产生式保存，设置符号栈系表，并将文法的产生式保存，设置符号栈S S，再再再再根据如下算符步骤进行分析：根据如下算符步骤进行分析：根据如下算符步骤进行分析：根据如下算符步骤进行分析：（1 1）将输入符号串将输入符号串将输入符号串将输入符号串a a1 1a a2 2aa
25、n n# #依次逐个存入符号栈依次逐个存入符号栈依次逐个存入符号栈依次逐个存入符号栈S S中，直到遇到栈顶符中，直到遇到栈顶符中，直到遇到栈顶符中，直到遇到栈顶符号号号号a ai i的优先性的优先性的优先性的优先性 下一个待输入符号下一个待输入符号下一个待输入符号下一个待输入符号a aj j时为止。时为止。时为止。时为止。（2 2）栈顶当前符号栈顶当前符号栈顶当前符号栈顶当前符号aiai尾句柄尾，由此向左在栈中找句柄的头符号尾句柄尾，由此向左在栈中找句柄的头符号尾句柄尾，由此向左在栈中找句柄的头符号尾句柄尾，由此向左在栈中找句柄的头符号a ak k，即即即即找到找到找到找到a ak-1k-1
26、aak k，为止。为止。为止。为止。（3 3）由句柄由句柄由句柄由句柄a ak kaai i在文法的产生式中查找右部尾在文法的产生式中查找右部尾在文法的产生式中查找右部尾在文法的产生式中查找右部尾a ak kaai i的产生式，若找的产生式，若找的产生式，若找的产生式，若找到则用相应左部代替句柄，若找不到则出错。到则用相应左部代替句柄，若找不到则出错。到则用相应左部代替句柄，若找不到则出错。到则用相应左部代替句柄，若找不到则出错。（4 4）重复上述三个步骤直到规约完输入符号串，栈中只剩文法的开始符重复上述三个步骤直到规约完输入符号串，栈中只剩文法的开始符重复上述三个步骤直到规约完输入符号串，栈
27、中只剩文法的开始符重复上述三个步骤直到规约完输入符号串，栈中只剩文法的开始符号或出错为止。号或出错为止。号或出错为止。号或出错为止。算符优先分析法算符优先分析法vv算符优先分析法常用于高级语言的算符优先分析法常用于高级语言的算符优先分析法常用于高级语言的算符优先分析法常用于高级语言的表达式表达式的语法分析。的语法分析。的语法分析。的语法分析。vv算符优先关系的形式定义：算符优先关系的形式定义：算符优先关系的形式定义：算符优先关系的形式定义：（1 1）相等关系）相等关系）相等关系）相等关系 a a=b=b：当且仅当当且仅当当且仅当当且仅当GG中存在中存在中存在中存在 A Aab ab 或或或或
28、A AaBb aBb 的规则。的规则。的规则。的规则。（2 2）小于关系小于关系小于关系小于关系a ab b B= b 或或或或 B= CbB= Cb（3 3）大于关系大于关系大于关系大于关系a a bb：当且仅当当且仅当当且仅当当且仅当GG中存在规则中存在规则中存在规则中存在规则 A ABbBb，且且且且B=a B=a 或或或或 B=aCB=aCvv 算符优先分析法的基本思想：算符优先分析法的基本思想：算符优先分析法的基本思想：算符优先分析法的基本思想：根据算符（广义为终结符号）之间的优根据算符（广义为终结符号）之间的优根据算符（广义为终结符号）之间的优根据算符（广义为终结符号）之间的优先关
29、系来决定如何归约。先关系来决定如何归约。先关系来决定如何归约。先关系来决定如何归约。+算符文法及其性质算符文法及其性质vv算符文法的形式定义：算符文法的形式定义：算符文法的形式定义：算符文法的形式定义：设有一文法设有一文法设有一文法设有一文法GG，如果如果如果如果GG中中中中没有没有形如形如形如形如A ABCBC的规则，其的规则，其的规则，其的规则，其中中中中B B和和和和C C为非终结符，则称为非终结符，则称为非终结符，则称为非终结符，则称GG为算符文法，也称为算符文法，也称为算符文法，也称为算符文法，也称OGOG文法。文法。文法。文法。vv 算符文法的性质：算符文法的性质：算符文法的性质：
30、算符文法的性质：（1 1）在算符文法中任何句型都不包含两个相邻的非终结符。）在算符文法中任何句型都不包含两个相邻的非终结符。）在算符文法中任何句型都不包含两个相邻的非终结符。）在算符文法中任何句型都不包含两个相邻的非终结符。（2 2）如果）如果）如果）如果AbAb（或或或或bAbA）出现在算符文法的句型出现在算符文法的句型出现在算符文法的句型出现在算符文法的句型 中，其中中，其中中，其中中，其中A A V VN N，b b V VT T，则则则则 中任何含中任何含中任何含中任何含b b的短语必含有的短语必含有的短语必含有的短语必含有A A。算符优先文法及其性质算符优先文法及其性质vv算符优先文
31、法的形式定义：算符优先文法的形式定义：算符优先文法的形式定义：算符优先文法的形式定义：设有一设有一设有一设有一不含不含不含不含产生式产生式产生式产生式的算符文法的算符文法的算符文法的算符文法GG，如果对任意两个终结符对如果对任意两个终结符对如果对任意两个终结符对如果对任意两个终结符对a,ba,b之间之间之间之间至多只有至多只有至多只有至多只有= =、 三种关系中的一种成立，则称三种关系中的一种成立，则称三种关系中的一种成立，则称三种关系中的一种成立，则称GG是一个算符优先文法。是一个算符优先文法。是一个算符优先文法。是一个算符优先文法。也称为也称为也称为也称为OPGOPG文法。文法。文法。文法
32、。vv 算符优先文法的性质：算符优先文法的性质：算符优先文法的性质：算符优先文法的性质：如果如果如果如果aNbaNb或或或或abab出现在句型出现在句型出现在句型出现在句型r r中，则中，则中，则中，则a a和和和和b b之间有且仅有一种优之间有且仅有一种优之间有且仅有一种优之间有且仅有一种优先关系即：先关系即：先关系即：先关系即：（1 1） 若若若若a a b b 则则则则 在在在在r r中必有含中必有含中必有含中必有含a a而不含而不含而不含而不含b b的短语存在的短语存在的短语存在的短语存在（3 3）若）若）若）若a a = = b b 则则则则 在在在在r r中含有中含有中含有中含有a
33、 a的短语必含有的短语必含有的短语必含有的短语必含有b b，反之亦然。反之亦然。反之亦然。反之亦然。算符优先关系表的构造算符优先关系表的构造vv由定义直接构造由定义直接构造由定义直接构造由定义直接构造（1 1）FIRSTVTFIRSTVT集合：集合：集合：集合：FIRSTVTFIRSTVT（B B）=b|B=b=b|B=b或或或或B=CbB=Cb（2 2）LASTVTLASTVT集合：集合：集合：集合： LASTVTLASTVT（B B）=a|Ba|B=a=a或或或或B=aCB=aCvv 由关系图法构造由关系图法构造由关系图法构造由关系图法构造（1 1）FIRSTFIRST关系：关系：关系：关
34、系：A FIRST B A FIRST B 当且仅当存在形如当且仅当存在形如当且仅当存在形如当且仅当存在形如 A AB B 的产生式。的产生式。的产生式。的产生式。（2 2）LASTLAST关系：关系：关系：关系： A LAST B A LAST B 当且仅当存在形如当且仅当存在形如当且仅当存在形如当且仅当存在形如 A A B B 的产生式。的产生式。的产生式。的产生式。（3 3）FIRSTTERMFIRSTTERM关系：关系：关系：关系：B FIRSTTERM b B FIRSTTERM b 当且仅当存在形如当且仅当存在形如当且仅当存在形如当且仅当存在形如 B Bb b 或或或或 B BCb
35、Cb的产生式。的产生式。的产生式。的产生式。（4 4）LASTTERMLASTTERM关系：关系：关系：关系：B FIRSTTERM a B FIRSTTERM a 当且仅当存在形如当且仅当存在形如当且仅当存在形如当且仅当存在形如 B Ba a 或或或或 B BaCaC的的的的产生式。产生式。产生式。产生式。（5 5）FOLLOWEDBFOLLOWEDB关系：关系：关系：关系：X FOLLOWEDB Y X FOLLOWEDB Y 当且仅当存在形如当且仅当存在形如当且仅当存在形如当且仅当存在形如 A AXY XY 的产的产的产的产生式（生式（生式（生式（X X、Y Y中必须是一个为终结符，另一
36、个为非终结符）。中必须是一个为终结符，另一个为非终结符）。中必须是一个为终结符，另一个为非终结符）。中必须是一个为终结符，另一个为非终结符）。vv 用公式法构造用公式法构造用公式法构造用公式法构造（1 1） =（LAST*LAST*）（LASTTERMLASTTERM）T T（= =）+编译方法编译方法编译方法编译方法中对公式的证明：中对公式的证明：中对公式的证明：中对公式的证明：注意：此处相等关系的符号为注意：此处相等关系的符号为注意：此处相等关系的符号为注意：此处相等关系的符号为“ “”，与教材采用的符号不同。规则中连，与教材采用的符号不同。规则中连，与教材采用的符号不同。规则中连，与教材
37、采用的符号不同。规则中连接左部与右部的符号也不同，为接左部与右部的符号也不同，为接左部与右部的符号也不同，为接左部与右部的符号也不同，为EBNFEBNFEBNFEBNF中的形式。中的形式。中的形式。中的形式。例：用公式构造文法例：用公式构造文法GE的算符优先关系表的算符优先关系表课堂练习：求该文法的优先关系课堂练习：求该文法的优先关系“”用程序构造算符优先关系的方法和步骤用程序构造算符优先关系的方法和步骤n教材6.3.3算符优先分析法与最左素短语算符优先分析法与最左素短语vv引入最左素短语的目的：引入最左素短语的目的：引入最左素短语的目的：引入最左素短语的目的：解决在算符优先分析过程中如何寻找
38、句柄的问题。解决在算符优先分析过程中如何寻找句柄的问题。解决在算符优先分析过程中如何寻找句柄的问题。解决在算符优先分析过程中如何寻找句柄的问题。vv 最左素短语的形式定义：最左素短语的形式定义：最左素短语的形式定义：最左素短语的形式定义：设有文法设有文法设有文法设有文法GSGS，其句型的素短语是一个短语，该短语至少包含一个终结其句型的素短语是一个短语，该短语至少包含一个终结其句型的素短语是一个短语，该短语至少包含一个终结其句型的素短语是一个短语，该短语至少包含一个终结符，并且除自身外不包含其他素短语，最左边的素短语称最左素短语。符，并且除自身外不包含其他素短语，最左边的素短语称最左素短语。符，
39、并且除自身外不包含其他素短语，最左边的素短语称最左素短语。符，并且除自身外不包含其他素短语，最左边的素短语称最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。vv 算符优先分析法的关键问题是算符优先分析法的关键问题是算符优先分析法的关键问题是算符优先分析法的关键问题是寻找最左素短语寻找最左素短语寻找最左素短语寻找最左素短语。vv 算符优先分析法的局限性：算符优先分析法的局限性：算符优先分析法的局限性：算符优先分
40、析法的局限性：算符优先分析法去掉了单个非算符优先分析法去掉了单个非算符优先分析法去掉了单个非算符优先分析法去掉了单个非终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得到正确的归约。到正确的归约。到正确的归约。到正确的归约。算符优先分析法算法算符优先分析法算法算符优先分析法的算法用到一个符号栈算符优先分析法的算法用到一个符号栈算符优先分析法的算法用到一个符号栈算符优先分析法的算法用到一个符号栈S S
41、和一个存放输入符和一个存放输入符和一个存放输入符和一个存放输入符号串的数组号串的数组号串的数组号串的数组R R，算法中的算法中的算法中的算法中的QQ为一工作单元，用于存放待比较为一工作单元，用于存放待比较为一工作单元，用于存放待比较为一工作单元，用于存放待比较的终结符号：的终结符号：的终结符号：的终结符号：（1 1）将输入符串）将输入符串）将输入符串）将输入符串R R1 1R R2 2RRK K依次逐个存入符号栈依次逐个存入符号栈依次逐个存入符号栈依次逐个存入符号栈S S中，直至符号栈顶元素中，直至符号栈顶元素中，直至符号栈顶元素中，直至符号栈顶元素S Sj j与下一个待输入的符号与下一个待输
42、入的符号与下一个待输入的符号与下一个待输入的符号R Rk k有关系有关系有关系有关系S Sj j R Rk k为止；为止；为止；为止；（2 2）最左素短语尾）最左素短语尾）最左素短语尾）最左素短语尾S Sj j已在符号栈已在符号栈已在符号栈已在符号栈S S的栈顶，由此往前（左）在栈中找最左的栈顶，由此往前（左）在栈中找最左的栈顶，由此往前（左）在栈中找最左的栈顶，由此往前（左）在栈中找最左素短语的头符号素短语的头符号素短语的头符号素短语的头符号S Si i，直至找到第一个直至找到第一个直至找到第一个直至找到第一个 S Si i QQ（Q=Q=SjSj ）为止；）为止；）为止；）为止；（3 3）
43、已找到最左素短语）已找到最左素短语）已找到最左素短语）已找到最左素短语S Si iS Sj j，将其归约到任意一个非终结符。将其归约到任意一个非终结符。将其归约到任意一个非终结符。将其归约到任意一个非终结符。 重复上述过程，直至重复上述过程，直至重复上述过程，直至重复上述过程，直至j=2j=2且且且且RK= #RK= #为止。为止。为止。为止。优先函数优先函数v 优先关系表是以矩阵的形式在计算机内存储的，优先关系表是以矩阵的形式在计算机内存储的，优先关系表是以矩阵的形式在计算机内存储的，优先关系表是以矩阵的形式在计算机内存储的，占用的空间相对较大。占用的空间相对较大。占用的空间相对较大。占用的
44、空间相对较大。vv 引入优先函数是为了减少存储优先关系的存储空引入优先函数是为了减少存储优先关系的存储空引入优先函数是为了减少存储优先关系的存储空引入优先函数是为了减少存储优先关系的存储空间。间。间。间。vv 现在计算机的存储资源已经非常可观，由于优先现在计算机的存储资源已经非常可观，由于优先现在计算机的存储资源已经非常可观，由于优先现在计算机的存储资源已经非常可观，由于优先函数虽然能节省一定的存储空间，但由于其某些情函数虽然能节省一定的存储空间，但由于其某些情函数虽然能节省一定的存储空间，但由于其某些情函数虽然能节省一定的存储空间，但由于其某些情况下不能准确地提供出错位置等信息，因此现在已况下不能准确地提供出错位置等信息，因此现在已况下不能准确地提供出错位置等信息，因此现在已况下不能准确地提供出错位置等信息，因此现在已不再使用优先函数的形式来存储优先关系。不再使用优先函数的形式来存储优先关系。不再使用优先函数的形式来存储优先关系。不再使用优先函数的形式来存储优先关系。
