编译原理自下而上语法分析.ppt

《编译原理自下而上语法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理自下而上语法分析.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院自下而上语法分析自下而上语法分析vv掌握自底相上分析的基本思想，基本概念掌握自底相上分析的基本思想，基本概念掌握自底相上分析的基本思想，基本概念掌握自底相上分析的基本思想，基本概念vv掌握算符优先关系的判定，求掌握算符优先关系的判定，求掌握算符优先关系的判定，求掌握算符优先关系的判定，求FIRSTVTFIRSTVTFIRSTVTFIRSTVT集集集集,LASTVT,LASTVT,LASTVT,LASTVT集集集集,构造算符优先关系表

2、，能运用算符优先分析方法进构造算符优先关系表，能运用算符优先分析方法进构造算符优先关系表，能运用算符优先分析方法进构造算符优先关系表，能运用算符优先分析方法进行表达式分析行表达式分析行表达式分析行表达式分析vv掌握最左素短语、句柄的定义与判定掌握最左素短语、句柄的定义与判定掌握最左素短语、句柄的定义与判定掌握最左素短语、句柄的定义与判定vv理解规范规约与算符优先归约的区别理解规范规约与算符优先归约的区别理解规范规约与算符优先归约的区别理解规范规约与算符优先归约的区别 vvLR(0)LR(0)和和和和SLRSLR文法的理解文法的理解文法的理解文法的理解 编译原理编译原理编译原理编译原理 长春工业

3、大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院自下而上的语法分析自下而上的语法分析vv实现思想实现思想实现思想实现思想从从从从输输输输入入入入符符符符号号号号串串串串开开开开始始始始，从从从从左左左左到到到到右右右右进进进进行行行行扫扫扫扫描描描描，将将将将输输输输入入入入符符符符号号号号逐逐逐逐个个个个移移移移入入入入一一一一个个个个栈栈栈栈中中中中，边边边边移移移移入入入入边边边边分分分分析析析析，一一一一旦旦旦旦栈栈栈栈顶顶顶顶符符符符号号号号串串串串形形形形成成成成某某某某个个个个产产产产生生生生式式式式的的的的

4、右右右右部部部部时时时时，就就就就用用用用该该该该产产产产生生生生式式式式的的的的左左左左部部部部非非非非终终终终结结结结符符符符代代代代替替替替，称称称称为为为为归归归归约约约约。重重重重复复复复这这这这一一一一过过过过程程程程，直直直直到到到到归归归归约约约约到到到到栈栈栈栈中中中中只只只只剩剩剩剩下下下下文文文文法法法法的的的的开开开开始始始始符符符符号号号号时时时时，则则则则分分分分析析析析成成成成功功功功，称称称称为为为为“移移移移进进进进-归归归归约约约约”方法方法方法方法。从从从从语语语语法法法法树树树树的的的的角角角角度度度度看看看看：从从从从语语语语法法法法树树树树的的的的树

5、树树树叶叶叶叶开开开开始始始始，逐逐逐逐步步步步向向向向上上上上归归归归约约约约构造分析树构造分析树构造分析树构造分析树，直到形成根结。是推导的逆过程，直到形成根结。是推导的逆过程，直到形成根结。是推导的逆过程，直到形成根结。是推导的逆过程。vv核心核心核心核心寻找可归约串寻找可归约串寻找可归约串寻找可归约串(这是关键这是关键这是关键这是关键)进行规约。进行规约。进行规约。进行规约。用不同的方法寻找用不同的方法寻找用不同的方法寻找用不同的方法寻找可归约串可归约串可归约串可归约串，就可获得不同的分析方法。，就可获得不同的分析方法。，就可获得不同的分析方法。，就可获得不同的分析方法。编译原理编译原

6、理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv最左推导最左推导最左推导最左推导(Left-most Derive)(Left-most Derive)每次推导都替换当前句型的最左边的非终结符。每次推导都替换当前句型的最左边的非终结符。每次推导都替换当前句型的最左边的非终结符。每次推导都替换当前句型的最左边的非终结符。与最右归约对应与最右归约对应与最右归约对应与最右归约对应vv最右推导最右推导最右推导最右推导(Right-most Derive)(Right-most Derive)每次推导

7、都替换当前句型的最右边的非终结符。每次推导都替换当前句型的最右边的非终结符。每次推导都替换当前句型的最右边的非终结符。每次推导都替换当前句型的最右边的非终结符。与最左归约与最左归约与最左归约与最左归约(规范归约规范归约规范归约规范归约)对应，得规范句型对应，得规范句型对应，得规范句型对应，得规范句型例：设有文法例：设有文法例：设有文法例：设有文法GSGS：(1)S (1)S aAcBe aAcBe (2)A (2)A b b (3)A (3)A Ab Ab (4)B (4)B d d 使用最右推导：使用最右推导：使用最右推导：使用最右推导：因为因为因为因为S=aAcBe=aAcde=aAbcd

8、e=abbcdeS=aAcBe=aAcde=aAbcde=abbcde，所以所以所以所以 abbcde abbcde是文法是文法是文法是文法GG的句子。的句子。的句子。的句子。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院步骤步骤动作动作(1)S aAcBe(2)A b(3)A Ab(4)B d最左归约过程是最右推导的逆过程，最左归约过程是最右推导的逆过程，最左归约过程是最右推导的逆过程，最左归约过程是最右推导的逆过程，对输入串对输入串对输入串对输入串abbcde的的的的归约过程

9、如下：归约过程如下：归约过程如下：归约过程如下：该分析过程反复执行该分析过程反复执行“移进移进”和和“归约归约”两个动作，直到栈中只有开始符号为止。两个动作，直到栈中只有开始符号为止。ab aA ab A aA ac A adc A aBc A aeBc A aS1 1移移移移进进进进a a2 2移移移移进进进进b b3 3归归归归约约约约2 24 4移移移移进进进进b b5 5归归归归约约约约3 36 6移移移移进进进进c c7 7移移移移进进进进d d8 8归归归归约约约约4 49 9移移移移进进进进e e1010归归归归约约约约1 1 编译原理编译原理编译原理编译原理 长春工业大学计算机

10、科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院语法分析树的生成演示语法分析树的生成演示a b b c d eAABSAbAbAAbAAbBdBdSaAcBeSaAcBe(1)S aAcBe(2)A b(3)A Ab(4)B d 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv这种分析过程具有如下特点：这种分析过程具有如下特点：这种分析过程具有如下特点：这种分析过程具有如下特点：从输入串的开始依次读入单词从输入串的开

11、始依次读入单词从输入串的开始依次读入单词从输入串的开始依次读入单词(移进栈中移进栈中移进栈中移进栈中)。一旦发现一旦发现一旦发现一旦发现可归约串可归约串可归约串可归约串(某个产生式的右端某个产生式的右端某个产生式的右端某个产生式的右端)就立即归约。就立即归约。就立即归约。就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约就是将栈顶的一串符号用文法产生式的左部代替，归约就是将栈顶的一串符号用文法产生式的左部代替，归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。归约可能重复多次，然后继续移进。归约可能重复多次，然后继续移进。归约可能重复多次，然后继续移

12、进。若最终能归约成文法的开始符号，则分析成功。若最终能归约成文法的开始符号，则分析成功。若最终能归约成文法的开始符号，则分析成功。若最终能归约成文法的开始符号，则分析成功。vv关键是如何判断可归约串？关键是如何判断可归约串？关键是如何判断可归约串？关键是如何判断可归约串？编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院问题的提出：问题的提出：问题的提出：问题的提出：在构造语法树的过程中，何时归约？在构造语法树的过程中，何时归约？在构造语法树的过程中，何时归约？在构造语法树的过程中，

13、何时归约？当可归约串出现在栈顶时就进行归约。当可归约串出现在栈顶时就进行归约。当可归约串出现在栈顶时就进行归约。当可归约串出现在栈顶时就进行归约。如何知道在栈顶符号串中已经形成可归约串？如何知道在栈顶符号串中已经形成可归约串？如何知道在栈顶符号串中已经形成可归约串？如何知道在栈顶符号串中已经形成可归约串？如何进行归约？如何进行归约？如何进行归约？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法通过不同的自底向上的分析算法来解释，不同的算法通过不同的自底向上的分析算法来解释，不同的算法通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的对可

14、归约串的定义是不同的，但分析过程都有一个共同的对可归约串的定义是不同的，但分析过程都有一个共同的对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。特点：边移进边归约。特点：边移进边归约。特点：边移进边归约。规范归约：使用句柄来定义可归约串。规范归约：使用句柄来定义可归约串。规范归约：使用句柄来定义可归约串。规范归约：使用句柄来定义可归约串。算符优先：使用最左素短语来定义可归约串算符优先：使用最左素短语来定义可归约串算符优先：使用最左素短语来定义可归约串算符优先：使用最左素短语来定义可归约串 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机

15、科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院规范归约概念规范归约概念vv有文法有文法有文法有文法G G G G，开始符号为，开始符号为，开始符号为，开始符号为S,S,S,S,如果有如果有如果有如果有S=xy,S=xy,S=xy,S=xy,则则则则xyxyxyxy是是是是文法文法文法文法G G G G的的的的句型句型句型句型，x,yx,yx,yx,y是任意的符号串是任意的符号串是任意的符号串是任意的符号串vv如果有如果有如果有如果有S=xAy,S=xAy,S=xAy,S=xAy,且有且有且有且有A=,A=,A=,A=,则则则则是句型是句型是句型是句型xyxyxy

16、xy相对于相对于相对于相对于非终结符非终结符非终结符非终结符A A A A的的的的短语短语短语短语vv如果有如果有如果有如果有S=xAy,S=xAy,S=xAy,S=xAy,且有且有且有且有A-,A-,A-,A-,则则则则是句型是句型是句型是句型xyxyxyxy相对于相对于相对于相对于A-A-A-A-的的的的直接短语直接短语直接短语直接短语vv位于位于位于位于一个一个句型最左边的直接短语称为句型最左边的直接短语称为句型最左边的直接短语称为句型最左边的直接短语称为句柄句柄句柄句柄。*+*注注注注:每次归约的部分必须是称之为每次归约的部分必须是称之为每次归约的部分必须是称之为每次归约的部分必须是称

17、之为句柄句柄句柄句柄的字符串的字符串的字符串的字符串(最右推导最右推导最右推导最右推导)。关键的问题是关键的问题是关键的问题是关键的问题是如何识别句柄如何识别句柄如何识别句柄如何识别句柄 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 例子例子下面的例子说明作为短语的两个条件缺一不可。下面的例子说明作为短语的两个条件缺一不可。下面的例子说明作为短语的两个条件缺一不可。下面的例子说明作为短语的两个条件缺一不可。例例例例 考虑表达式文法：考虑表达式文法：考虑表达式文法：考虑表达式文法

18、：E E T|E+T T|E+T T T F|T*FF|T*F F F i|(E)i|(E)对于句型对于句型对于句型对于句型i*i+i i*i+i 推导推导推导推导E E E+T E+T E+E+F F E+E+i i T+i T+i T*F+T T*F+T T*i+i T*i+i F*i+i F*i+i i*i+i i*i+i尽管有尽管有尽管有尽管有E E+i+i i+i 但是但是但是但是,i+i,i+i 并不是该句型的一个短语，并不是该句型的一个短语，并不是该句型的一个短语，并不是该句型的一个短语，因为不存在从因为不存在从因为不存在从因为不存在从E(E(文法开始符）到文法开始符）到文法开始

19、符）到文法开始符）到i*Ei*E的推导。的推导。的推导。的推导。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院句型的短语和句柄举例句型的短语和句柄举例 文法：文法：文法：文法：S(T)|TS|T,S|aS(T)|TS|T,S|avv 短语：短语：短语：短语：句型句型句型句型(a),S)S(a),S)S=*(T,S)T(T,S)T=+(a)(a)句型句型句型句型(T,S),S)S(T,S),S)S=*(T),S)T(T),S)T=+T,S T,S vv句型句型句型句型(a,(T),

20、(T,S)(a,(T),(T,S)直接短语以及句柄：直接短语以及句柄：直接短语以及句柄：直接短语以及句柄：S S=*(T,(T),(T,S)T(T,(T),(T,S)T=a aS S=*(a,S,(T,S)S(a,S,(T,S)S=(T)(T)S S=*(a,(T),(T)T(a,(T),(T)T=T,ST,S 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院短语与语法树的关系短语与语法树的关系vv短语：语法树子树的叶子结点组成的符号短语：语法树子树的叶子结点组成的符号串。串。vv

21、直接短语：语法树简单子树（只有父子两直接短语：语法树简单子树（只有父子两代）的叶子结点组成的符号串。代）的叶子结点组成的符号串。vv句柄：语法树最左边简单子树的叶子结点句柄：语法树最左边简单子树的叶子结点组成的符号串。组成的符号串。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院短语与语法树关系的例子短语与语法树关系的例子句型句型(a,(T),(T,S)的语法树：的语法树：S()TTS,T,S(T)a(T)T,S 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长

22、春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院用句柄对句子用句柄对句子abbcde进行归约进行归约vv用句柄对句子进行归约的过程与用移进用句柄对句子进行归约的过程与用移进用句柄对句子进行归约的过程与用移进用句柄对句子进行归约的过程与用移进-归约过程是一归约过程是一归约过程是一归约过程是一致的，使用归约的产生式及其顺序是一致的。致的，使用归约的产生式及其顺序是一致的。致的，使用归约的产生式及其顺序是一致的。致的，使用归约的产生式及其顺序是一致的。句型句型句型句型 归约规则归约规则归约规则归约规则abbcdeabbcde(1)S aAcBe(2)A

23、b(3)A Ab(4)B d(2)Ab(3)A AbaAbcdeaAcde(4)B d(1)S aAcBeaAcBeS 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院规范归约的定义规范归约的定义vv假定假定假定假定 是文法是文法是文法是文法GG的一个句子，如果序列：的一个句子，如果序列：的一个句子，如果序列：的一个句子，如果序列：n n,n-1n-1,0 0(=(=S S)满足如下条件，则序列满足如下条件，则序列满足如下条件，则序列满足如下条件，则序列 n n,n-1n-1,0

24、0是一个规范归约是一个规范归约是一个规范归约是一个规范归约:(1)(1)n n=是给定的句子是给定的句子是给定的句子是给定的句子(2)(2)0 0=S S 是文法的开始符号是文法的开始符号是文法的开始符号是文法的开始符号(3)(3)对任何对任何对任何对任何i,0ii,0E+T|TE-E+T|T(2)T-T*F|FT-T*F|F(3)F-(E)|iF-(E)|i对输入串对输入串对输入串对输入串 i1+i2*i3 i1+i2*i3 的规范归约过程：的规范归约过程：的规范归约过程：的规范归约过程：编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工

25、业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区1)1)准备准备#i#i1 1+i+i2 2*i*i3 3#2)2)移进移进#i#i1 1 +i +i2 2*i*i3 3#3)3)归约归约 Fi#F +i Fi#F +i2 2*i*i3 3#4)4)归约归约 TF#T +i TF#T +i2 2*i*i3 3#5)5)归约归约 ET#E +i ET#E +i2 2*i*i3 3#6)6)移进移进#E+i#E+i2 2*i*i3 3#7)7)移进移进#E+i#E+i2 2 *i *i3 3#8)8)归约归约 Fi#E

26、+F *i Fi#E+F *i3 3#9)9)归约归约 TF#E+T *i TF#E+T *i3 3#10)10)移进移进#E+T*i#E+T*i3 3#11)11)移进移进#E+T*i#E+T*i3 3#12)12)归约归约 Fi#E+T*F#Fi#E+T*F#13)13)归约归约 TT*F#E+T#TT*F#E+T#14)14)归约归约 EE+T#E#EE+T#E#15)15)接受接受所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树(1)E-E+T|T(2)T-T*F|F(3)F

27、-(E)|ii i1 1 +i +i2 2 *i *i3 3FTEFTFTE 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院算符优先分析算符优先分析vv算符优先分析法的思想源于表达式的分析，即利用相邻终算符优先分析法的思想源于表达式的分析，即利用相邻终算符优先分析法的思想源于表达式的分析，即利用相邻终算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。结符号之间的关系来寻找可归约串。结符号之间的关系来寻找可归约串。结符号之间的关系来寻找可归约串。vv

28、将句型中的终结符号当作将句型中的终结符号当作将句型中的终结符号当作将句型中的终结符号当作“算符算符算符算符”，借助于算符之间的优，借助于算符之间的优，借助于算符之间的优，借助于算符之间的优先关系确定先关系确定先关系确定先关系确定可归约串可归约串可归约串可归约串。vv显然，在一个符号串中，任意两个相邻终结符号显然，在一个符号串中，任意两个相邻终结符号显然，在一个符号串中，任意两个相邻终结符号显然，在一个符号串中，任意两个相邻终结符号a a和和和和b b之间，之间，之间，之间，只可能存在以下四种优先关系：只可能存在以下四种优先关系：只可能存在以下四种优先关系：只可能存在以下四种优先关系：(1)a,

29、b(1)a,b优先性相同，记作优先性相同，记作优先性相同，记作优先性相同，记作a ba b。(2)a(2)a优先性高于优先性高于优先性高于优先性高于b b，记作记作记作记作a a b b。(3)a(3)a优先性低于优先性低于优先性低于优先性低于b b，记作，记作，记作，记作a a b b。(4)a(4)a与与与与b b不可能相邻，即此符号串不是句型不可能相邻，即此符号串不是句型不可能相邻，即此符号串不是句型不可能相邻，即此符号串不是句型(出错出错出错出错)。如果以上四种关系中的任意两种都不会同时成立，则如果以上四种关系中的任意两种都不会同时成立，则如果以上四种关系中的任意两种都不会同时成立，则

30、如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。可以根据终结符号之间的归约关系进行语法分析。可以根据终结符号之间的归约关系进行语法分析。可以根据终结符号之间的归约关系进行语法分析。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv算符文法算符文法算符文法算符文法:一个上下无关文法一个上下无关文法一个上下无关文法一个上下无关文法G,G,G,G,如果没有如果没有如果没有如果没有P-P-P-P-,且没且没且没且没有有有有P-.QR.(P,Q,R

31、P-.QR.(P,Q,RP-.QR.(P,Q,RP-.QR.(P,Q,R属于非终结符属于非终结符属于非终结符属于非终结符),),),),则则则则G G G G是一个算是一个算是一个算是一个算符文法。符文法。符文法。符文法。vv算符优先关系算符优先关系算符优先关系算符优先关系的定义：的定义：的定义：的定义：a b,Ga b,G中有中有中有中有P-.ab.P-.ab.或或或或P-.aQb.(P-.aQb.(在同一产生式中在同一产生式中在同一产生式中在同一产生式中)a b,Ga b,G中有中有中有中有P-.aR.P-.aR.的产生式的产生式的产生式的产生式,且且且且R=b.R=b.或或或或R=Qb.

32、R=Qb.a b,Ga b,G中有中有中有中有P-.Rb.P-.Rb.的产生式的产生式的产生式的产生式,且且且且R=.aR=.a或或或或R=.aQ R=.aQ 算符优先文法（算符优先文法（OPG）的定义）的定义+编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例：例：EE+E|E*E|(E)|i 证明不是证明不是OPG文法。文法。因为：因为：EE+E，EE*E 则有则有+*又因为：又因为：EE*E,EE+E 则有则有+*所以不是算符优先文法。所以不是算符优先文法。vv算符优先文法算

33、符优先文法算符文法算符文法算符文法算符文法G G G G的任何终结符的任何终结符的任何终结符的任何终结符a,ba,ba,ba,b之间要么没有优先关之间要么没有优先关之间要么没有优先关之间要么没有优先关系，若有优先关系系，若有优先关系系，若有优先关系系，若有优先关系,至多有至多有至多有至多有 ,中的一种成中的一种成中的一种成中的一种成立立立立,则则则则G G G G为一算符优先文法。为一算符优先文法。为一算符优先文法。为一算符优先文法。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院

34、算符优先关系表的构造算符优先关系表的构造 vvFIRSTVTFIRSTVT集集定义：对每个非终结符定义：对每个非终结符定义：对每个非终结符定义：对每个非终结符P,P,P,P,FIRSTVT(P)=a|P=a.FIRSTVT(P)=a|P=a.FIRSTVT(P)=a|P=a.FIRSTVT(P)=a|P=a.或或或或P=Qa.,aP=Qa.,aP=Qa.,aP=Qa.,a为终结为终结为终结为终结符符符符,P,P,P,P，Q Q Q Q为非终结符为非终结符为非终结符为非终结符 +由优先性低于的定义和由优先性低于的定义和由优先性低于的定义和由优先性低于的定义和FIRSTVTFIRSTVTFIRST

35、VTFIRSTVT集合的定义可以得出：集合的定义可以得出：集合的定义可以得出：集合的定义可以得出：若存在某个产生式：若存在某个产生式：若存在某个产生式：若存在某个产生式：aPaPaPaP，对所有：，对所有：，对所有：，对所有：b b b bFIRSTVT FIRSTVT FIRSTVT FIRSTVT(P)(P)(P)(P)，都有：，都有：，都有：，都有：a ba ba ba b。按照下面两条规则来构造按照下面两条规则来构造按照下面两条规则来构造按照下面两条规则来构造FIRSTVTFIRSTVTFIRSTVTFIRSTVT集：集：集：集：若有产生式若有产生式若有产生式若有产生式P-a.P-a.

36、P-a.P-a.或或或或P-Qa.,P-Qa.,P-Qa.,P-Qa.,则则则则aFIRSTVT(P)aFIRSTVT(P)aFIRSTVT(P)aFIRSTVT(P)若有产生式若有产生式若有产生式若有产生式P-R.,P-R.,P-R.,P-R.,则则则则FIRSTVT(R)FIRSTVT(R)FIRSTVT(R)FIRSTVT(R)包含在包含在包含在包含在FIRSTVT(P)FIRSTVT(P)FIRSTVT(P)FIRSTVT(P)中中中中 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科

37、学与工程学院vvLASTVTLASTVT集集 定义：对每个非终结符定义：对每个非终结符定义：对每个非终结符定义：对每个非终结符P,P,P,P,LASTVT(P)=a|P=.a LASTVT(P)=a|P=.a LASTVT(P)=a|P=.a LASTVT(P)=a|P=.a或或或或P=.aQ,P=.aQ,P=.aQ,P=.aQ,a a a a为终结符为终结符为终结符为终结符,P,P,P,P，Q Q Q Q为非终结符为非终结符为非终结符为非终结符 +由优先性高于的定义和由优先性高于的定义和由优先性高于的定义和由优先性高于的定义和LASTVTLASTVTLASTVTLASTVT集合的定义可以得出

38、：集合的定义可以得出：集合的定义可以得出：集合的定义可以得出：若存在某个产生式：若存在某个产生式：若存在某个产生式：若存在某个产生式：PbPbPbPb，对所有：，对所有：，对所有：，对所有：a a a aLASTVT LASTVT LASTVT LASTVT(P)(P)(P)(P)，都有：，都有：，都有：，都有：a ba ba ba b。按照下面两条规则来构造按照下面两条规则来构造按照下面两条规则来构造按照下面两条规则来构造LASTVTLASTVTLASTVTLASTVT集：集：集：集：若有产生式若有产生式若有产生式若有产生式P-.aP-.aP-.aP-.a或或或或P-.aQ,P-.aQ,P-

39、.aQ,P-.aQ,则则则则aLASTVT(P)aLASTVT(P)aLASTVT(P)aLASTVT(P)若有产生式若有产生式若有产生式若有产生式P-.R,P-.R,P-.R,P-.R,则则则则LASTVT(R)LASTVT(R)LASTVT(R)LASTVT(R)包含在包含在包含在包含在LASTVT(P)LASTVT(P)LASTVT(P)LASTVT(P)中中中中 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv构造优先关系表构造优先关系表如果每个非终结符的如果每个非终结

40、符的如果每个非终结符的如果每个非终结符的FIRSTVTFIRSTVTFIRSTVTFIRSTVT和和和和LASTVTLASTVTLASTVTLASTVT集均已集均已集均已集均已知知知知,则可构造优先关系表。则可构造优先关系表。则可构造优先关系表。则可构造优先关系表。若产生式右部有若产生式右部有若产生式右部有若产生式右部有.aP.aP.aP.aP.的形式的形式的形式的形式,则对于每个则对于每个则对于每个则对于每个bFIRSTVT(P)bFIRSTVT(P)bFIRSTVT(P)bFIRSTVT(P)都有都有都有都有a ba ba ba b若产生式右部有若产生式右部有若产生式右部有若产生式右部有.

41、Pb.Pb.Pb.Pb的形式的形式的形式的形式,则对于每个则对于每个则对于每个则对于每个aLASTVT(P)aLASTVT(P)aLASTVT(P)aLASTVT(P)集集集集,都有都有都有都有a ba ba ba b 若产生是形如：若产生是形如：若产生是形如：若产生是形如：Aab Aab Aab Aab 或或或或 AaBb AaBb AaBb AaBb形式，则有形式，则有形式，则有形式，则有a ba ba ba bvv构造优先关系表的算法如下：构造优先关系表的算法如下：构造优先关系表的算法如下：构造优先关系表的算法如下：编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工

42、业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院For For 每条形如每条形如P PX X1 1X X2 2XXn n的的产生式产生式 do dofor i=1 to n-1 dofor i=1 to n-1 do if X if Xi i和和X Xi+1i+1都是终结符都是终结符 then then X Xi i =X =Xi+1i+1 if i=n-2 if i=n-2 且且 x xi i和和X Xi+2i+2都是终结符都是终结符,X,Xi+1i+1为非终结符为非终结符 then then X Xi i =X =Xi+2i+2 if X if X

43、i i为终结符为终结符,X,Xi+1i+1为非终结符为非终结符 then then for firstVT for firstVT中的每个元素中的每个元素a doa doX Xi i a Xa Xi+1i+1 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院算符优先分析算法算符优先分析算法vv通过比较终结符间的优先关系来实现通过比较终结符间的优先关系来实现通过比较终结符间的优先关系来实现通过比较终结符间的优先关系来实现vv根据优先分析的原理，语法分析程序的任务是：不根据优先分析的原

44、理，语法分析程序的任务是：不根据优先分析的原理，语法分析程序的任务是：不根据优先分析的原理，语法分析程序的任务是：不断移进输入符号，识别可归约串并进行归约。断移进输入符号，识别可归约串并进行归约。断移进输入符号，识别可归约串并进行归约。断移进输入符号，识别可归约串并进行归约。vv分析的方法：根据优先性分析的方法：根据优先性分析的方法：根据优先性分析的方法：根据优先性“高于高于高于高于”来识别可归约串来识别可归约串来识别可归约串来识别可归约串的头，根据优先性的头，根据优先性的头，根据优先性的头，根据优先性“低于低于低于低于”来识别可归约串的尾。来识别可归约串的尾。来识别可归约串的尾。来识别可归约

45、串的尾。各种优先关系已经存于优先关系表中。各种优先关系已经存于优先关系表中。各种优先关系已经存于优先关系表中。各种优先关系已经存于优先关系表中。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv不能识别只由一个非终结符组成的句柄。不不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约能保证每次对句柄进行归约,在算符优先分在算符优先分析过程中析过程中,每次归约的符号串每次归约的符号串,是当前句型的是当前句型的最左素短语。最左素短语。vv素短语：素短语：至少含有一个终结符至

46、少含有一个终结符,且除自身外且除自身外,不再包含任何其它更小的素短语。不再包含任何其它更小的素短语。vv最左素短语最左素短语(leftmost prime phrase)(leftmost prime phrase)：是是指位于句型最左边的那个素短语。指位于句型最左边的那个素短语。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例：下述文法的一个句型：例：下述文法的一个句型：例：下述文法的一个句型：例：下述文法的一个句型：T*F+iT*F+i 其短语、素短语、最左素短语分别是？其短

47、语、素短语、最左素短语分别是？其短语、素短语、最左素短语分别是？其短语、素短语、最左素短语分别是？ET|E+TTF|T*FFi|(E)EE +TFiTT *F短语有：短语有：短语有：短语有：i,T*F,T*F+ii,T*F,T*F+i素短语有：素短语有：素短语有：素短语有：i,T*F i,T*F最左素短语是：最左素短语是：最左素短语是：最左素短语是：T*FT*F 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例例例例:文法文法文法文法G G G G E-E+T|TE-E+T|TE

48、-E+T|TE-E+T|T T-T*F|FT-T*F|FT-T*F|FT-T*F|F F-(E)|i F-(E)|i F-(E)|i F-(E)|i句型句型句型句型T+T*F+iT+T*F+iT+T*F+iT+T*F+i的语法树如图：的语法树如图：的语法树如图：的语法树如图：EET+E+TFTT*FPi根据语法树可知：根据语法树可知：句型句型#T+T*F+i#的短语有：的短语有：T 相对非终结符相对非终结符E的短语的短语T*F 相对非终结符相对非终结符T的短语的短语T+T*F 相对非终结符相对非终结符E的短语的短语i 相对非终结符相对非终结符P、F、T的短语的短语T+T*F+i 相对非终结符相

49、对非终结符E的短语的短语根据素短语的定义可知：根据素短语的定义可知：i和和T*F为素短语。为素短语。其中：其中：T+T*F (含含T*F素短语素短语)、T+T*F+i(含含T*F素短语素短语)和和 T(不含终结符不含终结符)也不是素短语也不是素短语T*F为最左素短语。为最左素短语。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv一个算符文法一个算符文法一个算符文法一个算符文法GG的某个句型的最左素短语可描述：的某个句型的最左素短语可描述：的某个句型的最左素短语可描述：的某个句型

50、的最左素短语可描述：设句型的一般形式为设句型的一般形式为设句型的一般形式为设句型的一般形式为(N(Ni iVVN N,a ai i VVT T#N#N1 1a a1 1 N N2 2a a2 2 N Nn na an n N Nn+1n+1#它的它的它的它的最左素短语最左素短语最左素短语最左素短语是满足下列条件的最左子串：是满足下列条件的最左子串：是满足下列条件的最左子串：是满足下列条件的最左子串：N Ni ia ai i N Ni+1i+1a ai+1i+1 N Nj ja aj j N Nj+1j+1其中：其中：其中：其中：a ai-1i-1a ai,i,a ai ia ai+1i+1 .