第五章 语法分析 自下而上 4.0

1、第五章第五章 语法分析语法分析自下而上分析自下而上分析本章内容本章内容l自下而上分析基本问题自下而上分析基本问题l直观算符优先分析法直观算符优先分析法l算符优先分析算符优先分析l LRLR分析法分析法- 核心问题：句型分析核心问题：句型分析 对任意对任意上下文无关文法上下文无关文法G G = ( = (V V ，T T ，P P，S S ) ) 和任意和任意w w T T * *，是否有，是否有w w L(G)L(G)？ 若成立，若成立， 则给出分析树或（最左）推导步骤；否则，则给出分析树或（最左）推导步骤；否则， 进行报错处理。进行报错处理。 语法分析语法分析自下而上分析法自下而上分析法从输

2、入串开始，逐步进行从输入串开始，逐步进行“归约归约”，直至，直至归约到文法的开始符号。归约到文法的开始符号。例例5.1 5.1 文法文法G2:G2:S-aAcBe S-aAcBe （1 1） A-b A-b （2 2） A-Ab A-Ab （3 3） B-d B-d （4 4）输入串：输入串：abbcdeabbcdel abbcde abbcde 数目数目=3=3，选择（，选择（2 2）l aAbcde aAbcde 数目数目=3=3，选择（，选择（3 3）l aAcde aAcde 数目数目=1=1， 选择（选择（4 4）l aAcBe aAcBe 数目数目=1=1， 选择（选择（1 1）l

3、 S S 得解得解l abbcde abbcde 数目数目=3=3，选择（，选择（4 4）l abbcBe abbcBe 数目数目=2=2，选择（，选择（2 2）l abAcBe abAcBe 数目数目=1=1， 选择（选择（2 2）l aAAcBe aAAcBe 数目数目=0=0，失败，失败自下而上，进行规约，自下而上，进行规约，如何进行？如何进行？自左向右扫描初始串或句型，根据产生式找到能自左向右扫描初始串或句型，根据产生式找到能规约的规约的候选串候选串如果候选串如果候选串数目数目=0=0，无法规约，无法规约如果候选串如果候选串数目数目=1=1，进行唯一规约，进行唯一规约如果候选串如果候选

4、串数目数目11，且只有一个最左候选串，选择该，且只有一个最左候选串，选择该串进行规约串进行规约如果候选串如果候选串数目数目11，且有多个最左候选串，选择较长，且有多个最左候选串，选择较长串进行规约串进行规约一、自下而上分析基本问题一、自下而上分析基本问题1 1 、归约、归约利用栈，输入符号移进栈，当栈顶形成利用栈，输入符号移进栈，当栈顶形成P P的的候选式时，就归约为它的左候选式时，就归约为它的左P P符号符号例例5.1 5.1 文法文法G2:G2:S-aAcBe A-bS-aAcBe A-bA-Ab B-dA-Ab B-d输入串：输入串：abbcdeabbcde自下而上法，即自下而上法，即“

5、移进移进- -归约归约”法法最右推导：最右推导：a aa ab ba aA Aa aA Ab ba aA Aa aA Ac ca aA Ac cd da aA Ac cB Ba aA Ac cB Be eS S1 12 23 34 45 56 67 78 89 91010栈栈S S= aAc= aAcB Be e = aAc= aAcd de e =a=aAbAbcdecde= a b b c d e= a b b c d eS-aAcBeS-aAcBe输入串：输入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-b注意注意b b及及AbAb都可以规约都可以规约SaAcBeAb

6、db分分 析析 树树最左归约：最左归约：= S= S= aAc= aAcB Be e= a= aA Acdecde= a= aA Abcdebcdea a b b b c d e b c d e S-aAcBeS-aAcBe输入串：输入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-b- 从所要分析的终结符串开始从所要分析的终结符串开始进行归约；进行归约；- 每一步归约每一步归约是在当前串中找到与某个产生式的右部相是在当前串中找到与某个产生式的右部相匹配的子串，然后将该子串用这一产生式的左部非终结匹配的子串，然后将该子串用这一产生式的左部非终结符进行替换；符进行替换；-如果找

7、不到这样的子串，则回退到上一步归约前的状如果找不到这样的子串，则回退到上一步归约前的状 态，选择不同的子串或不同的产生式重试；态，选择不同的子串或不同的产生式重试；- 重复上一步骤，直到重复上一步骤，直到归约至文法开始符号归约至文法开始符号；- 如果不存在任何一个这样的归约，则表明该终结符串如果不存在任何一个这样的归约，则表明该终结符串存在语法错误存在语法错误 自底向上分析的一般过程自底向上分析的一般过程u 在每一步归约中，选择哪一个产生式以及匹配在每一步归约中，选择哪一个产生式以及匹配 哪一个位置上的子串都可能是非确定的哪一个位置上的子串都可能是非确定的u这些非确定性导致分析过程会有很高的复

8、杂性这些非确定性导致分析过程会有很高的复杂性 自底向上分析中的非确定性？自底向上分析中的非确定性？ 改进的方法？改进的方法？- 选择选择“可归约串可归约串”进行归约进行归约 在实用的自底向上分析中，总是选择某个在实用的自底向上分析中，总是选择某个“可可 归约串归约串”进行归约，可大大减少回溯进行归约，可大大减少回溯 观 察v当前栈顶部分与多个产生式右部匹配；v移进归约冲突反映了文法有二义性；v通过消除文法二义性可以避免某些移进归约冲突；v通过向前查看一个Token可以避免某些移进归约冲突；2 2 规范归约规范归约短语短语: :令令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符

9、号，若号，若是文法是文法G G的一个句型，的一个句型，如果有如果有S S A A且且 A A ，则称，则称是句型是句型相对于相对于非终结符非终结符A A的的短语。短语。句柄：句柄：一个句型的一个句型的最左直接短语最左直接短语称为该句型称为该句型的句柄。的句柄。直接短语：直接短语：如果有如果有A A =，则称，则称是句型是句型相对于规则相对于规则A A 的的直接短语直接短语例例5.25.2 文法文法G G E T | E +T T F | T * F F i |（E）的一个句型的一个句型 i i1 1* *i i2 2+i+i3 3语语 法法 树树TFEEFF+T*iiiTTFEEFF+T*i1

10、i2i3T i i1 ,1 ,i i2 ,2 ,i i3 , 3 , i i1 1* *i i2 , 2 , i i1 1* *i i2 2+i+i3 3i i1 ,1 ,i i2 ,2 ,i i3 3 i i1 1 l短语短语: :l直接短语直接短语: :l句柄句柄: : i2+i3不是该句型的一个短语，为什么？不是该句型的一个短语，为什么？尽管有尽管有E推到出推到出i2+i3，但不存在从开始但不存在从开始符号符号E到到i1*E的推到的推到子树和短语：子树和短语： 语法树的某个结点连同它的所有后代组成了一棵子树，语法树的某个结点连同它的所有后代组成了一棵子树，只含有单层分支的子树称为只含有单

11、层分支的子树称为简单子树简单子树。 子树与短语的关系十分密切，根据子树的概念，句型的子树与短语的关系十分密切，根据子树的概念，句型的短语、直接短语、句柄的直观解释如下：短语、直接短语、句柄的直观解释如下：(1)短语：子树的末端结点短语：子树的末端结点(即树叶即树叶)组成的符号串是相对于组成的符号串是相对于子子树的根树的根的短语。的短语。(2)直接短语：简单子树的末端结点组成的符号串是相对于直接短语：简单子树的末端结点组成的符号串是相对于简简单子树的根单子树的根的直接短语。的直接短语。(3)句柄：最左简单子树的末端结点组成的符号串是句柄。句柄：最左简单子树的末端结点组成的符号串是句柄。 例：短语

12、、直接短语SEEE+T|ET|TTT*i|T/i|i-ESETT4*32T 2-3*42是句型是句型2-3*4相对于相对于T和和E的短语，是相对于的短语，是相对于Ti的直接短语的直接短语3是句型是句型2-3*4相对于相对于T的的短语，是相对于短语，是相对于Ti的的直接短语直接短语3*4是句型是句型2-3*4相对于相对于T的短语，不是直接短语的短语，不是直接短语2-3*4是句型是句型2-3*4相对于相对于E和和S的短语，不是直接的短语，不是直接短语短语SEEE+T|ET|TTT*i|T/i|i2*3+42是句型是句型2*3+4相对于相对于T的短语，是相对于的短语，是相对于Ti的直接短语的直接短语

13、4是句型是句型2*3+4相对于相对于T的短语，是相对于的短语，是相对于Ti的直接短语的直接短语2*3是句型是句型2*3+4相对于相对于T和和E的短语的短语,不是直接短语不是直接短语2-3*4是句型是句型2*3+4相对相对于于E和和S的短语，不是直的短语，不是直接短语接短语+ESTTT3*24E例：短语、直接短语例：SEEE+T|ET|TTT*i|T/i|i-ESETT4*32T句型句型: 2-3*42是句型是句型2-3*4相对于相对于T和和E的短语，是相对于的短语，是相对于Ti的直接短语，的直接短语，是句柄是句柄3是句型是句型2-3*4相对于相对于T的的短语，是相对于短语，是相对于Ti的的直接

14、短语直接短语3*4是句型是句型2-3*4相对于相对于T的短语，不是直接短语的短语，不是直接短语2-3*4是句型是句型2-3*4相对于相对于E和和S的短语，不是直接的短语，不是直接短语短语例：SEEE+T|ET|TTT*i|T/i|i+ESTTT3*24句型句型: 2*3+42是句型是句型2*3+4相对于相对于T的短语，是相对于的短语，是相对于Ti的直接短语，的直接短语，是句柄是句柄4是句型是句型2*3+4相对于相对于T的短语，是相对于的短语，是相对于Ti的直接短语的直接短语2*3是句型是句型2*3+4相对于相对于T和和E的短语的短语,不是直接短语不是直接短语2-3*4是句型是句型2*3+4相对

15、相对于于E和和S的短语，不是直的短语，不是直接短语接短语Ev定义：假定定义：假定 是文法是文法G G的一个句子，我们称序的一个句子，我们称序列列 n n， n-1n-1， ， 0 0 是的一个是的一个规范归约规范归约，如果此序列满足：，如果此序列满足： 1 1 n n= = 2 2 0 0为文法的开始符号，即为文法的开始符号，即 0 0=S=S 3 3 对任何对任何i i，0 0 i i n n， i-1i-1是从是从 i i经把句柄替换经把句柄替换成为相应产生式左部符号而得到的。成为相应产生式左部符号而得到的。句柄：句柄：可归约串可归约串规范推导：规范推导：即即最右推导最右推导；规范句型：规

16、范句型：由规范推导所得的句型称为规范由规范推导所得的句型称为规范句型；句型；规范归约：规范归约：是关于句型是关于句型的一个的一个最右推导最右推导的的逆过程，也称逆过程，也称最左归约最左归约。v可用句柄来对句子进行归约可用句柄来对句子进行归约句型句型 归约规则归约规则a ab bbcde bcde (2) A (2) A b ba aAbAbcde cde (3) A (3) A Ab AbaAcaAcd de e (4) B (4) B d daAcBeaAcBe (1) S (1) S aAcBe aAcBe S SbdbaceSABAdbaceSABAdaceSABaceSABSa ab

17、bbcde bcde a aAbAbcdecdeaAcaAcd de e aAcBeaAcBe 在一个句型对应的语法树在一个句型对应的语法树中，以某非终结符为根的中，以某非终结符为根的两代以上的子树的所有末两代以上的子树的所有末端结点从左到右排列就是端结点从左到右排列就是相对于该非终结符的一个相对于该非终结符的一个短语，如果子树只有两代，短语，如果子树只有两代，则该短语就是直接短语。则该短语就是直接短语。一个句型的最左直接短语一个句型的最左直接短语称为该句型的句柄。称为该句型的句柄。3 3 符号栈的使用符号栈的使用规范归约用来作语法分析需要解决的规范归约用来作语法分析需要解决的问题：问题：如何

18、在句型中找出句柄如何在句型中找出句柄? ?在相同的右部有不止一个产生式时在相同的右部有不止一个产生式时, ,选哪一个选哪一个? ?实现移进实现移进- -归约分析的一个方便途径是用一个栈和一个输归约分析的一个方便途径是用一个栈和一个输 入缓冲区入缓冲区, ,用用# #表示栈底和输入的结束表示栈底和输入的结束栈栈输输 入入#w# 分析程序的动作分析程序的动作l移进移进: : 下一输入符号移进栈顶下一输入符号移进栈顶l归约归约: : 把句柄按产生式的左部进行归约把句柄按产生式的左部进行归约l接收接收: : 分析程序报告成功分析程序报告成功l出错出错: : 发现了一个语法错发现了一个语法错, ,调用出

19、错处理程序调用出错处理程序注意注意: : 可归约的串在栈顶可归约的串在栈顶, ,不会在内部不会在内部文法文法G G E T | E +T T F | T * F F i |（E）在移进-规约过程中如何生成语法分析树？穿线表穿线表语法树的实际表示方法：穿线表语法树的实际表示方法：穿线表(1)(1) 从输入串移一个符号入栈时，建立代表端末结从输入串移一个符号入栈时，建立代表端末结a a（叶结点、（叶结点、终结符）的数据结构：终结符）的数据结构：(a.) (a.) 儿子的个数：儿子的个数：0 0 ；(b.) (b.) 关于关于a a自身信息（如单词内部值）；自身信息（如单词内部值）；将此数据结构地址

20、（指示器值）连同将此数据结构地址（指示器值）连同a a本身一起进栈。本身一起进栈。(2)(2)栈顶栈顶n n个符号如个符号如X X1 1X X2 2X Xn n归约为归约为A A时，建立新结时，建立新结A A的数据结构：的数据结构：(a.) (a.) 儿子个数：儿子个数：n n；(b.) (b.) 指向儿子结点的指向儿子结点的n n个指示器值；个指示器值；(c.) (c.) 关于关于A A自身信息（如语义信息）；自身信息（如语义信息）；将此数据结构地址连同将此数据结构地址连同A A本身一起进栈。本身一起进栈。二二 直观算符优先分析法直观算符优先分析法 1 1 定义定义: : 任二个相继出现的终

21、结符任二个相继出现的终结符a a与与b(b(可能中间有可能中间有V VNN), ),可能有以可能有以下优先关系下优先关系: :a b a的优先性的优先性低于低于ba b a的优先性的优先性等于等于ba b a的优先性的优先性高于高于b2 例例5.3 文法文法G:E E + E | E * E | EE | ( E ) | i的终结符的优先关系见下表。的终结符的优先关系见下表。 + * i （ ） # + * i（ ） #优优 先先 表表E E E+E | E E+E | E* *E | EE |( E )| iE | EE |( E )| i3 3 使用如上分析表，构造分析算法（直观算符使用如

22、上分析表，构造分析算法（直观算符优先分析法）优先分析法）记号使用说明：记号使用说明： #：语句括号（栈底：语句括号（栈底 w后）后）：现行栈顶符：现行栈顶符 a：刚读入字符：刚读入字符OPTR：运算符栈：运算符栈OPND：操作符栈：操作符栈分析算法步骤：分析算法步骤：下一个输入符号读至下一个输入符号读至a a中；中；若若a a为为i i，则，则a aOPNDOPND，转第一步；，转第一步；若若 a a，则调用关于，则调用关于的处理程序（语义程序），处理子的处理程序（语义程序），处理子表达式表达式 : : E E（1 1）EE（2 2） ；然后重新进入第；然后重新进入第3 3步；（其中，步；（其

23、中， E E（1 1） 、E E（2 2）分分别为别为OPNDOPND栈的次栈顶和栈顶）栈的次栈顶和栈顶）aOPTROPND#E （1） E （2）E（3）=若若 a a，则，则若若=( (,a=,a=) ), ,则逐出则逐出OPTROPTR栈顶的栈顶的( (, ,放弃放弃a a中的中的 ) ), ,转第转第 1 1步步; ;若若=a=a=# #, ,分析成功结束；分析成功结束；若若 a a，a aOPTROPTR栈，转第栈，转第1 1步；步；与与a a不存在优先关系不存在优先关系，则输入串错误，调出错处理，则输入串错误，调出错处理)OPTROPND#(E （1） E （2）a#成功！成功！2

24、 例例5.4 由文法由文法G: E E + E | E * E | EE | ( E ) | i的终结符的优先关系表及上述分析算法的终结符的优先关系表及上述分析算法分析算术表达式分析算术表达式 i1 + i2 i1 + i2 * * i3 # i3 # 的过程。的过程。OPTROPTROPNDOPND分析过程分析过程 OPND OPND栈为空，栈为空， # # -OPTR-OPTR栈栈 i1-OPND i1-OPND # # OPTROPTR i2-OPND i2-OPND# #+ +i1 i1i2i2i3i3* *t te e输入串输入串 : :i1 + i2 i1 + i2 * * i3

25、# i3 #+ + OPTR-OPTR i3-OPND i3-OPND* * # # ， * *弹出弹出OPTROPTR栈；栈； i2 i2 * * i3 = t -OPND i3 = t -OPND + + # # ， + +弹出弹出OPTROPTR栈；栈； t + i1 = e -OPNDt + i1 = e -OPND # # = =# # ， 分析成功；分析成功； e e 为整个表达式的结为整个表达式的结果果a a1 1 算符优先文法算符优先文法定义一定义一 如果一个文法的任何产生式右部都不含两如果一个文法的任何产生式右部都不含两个相继（并列）的非终结符，即不含有如下形式个相继（并列）

26、的非终结符，即不含有如下形式的产生式右部：的产生式右部：QRQR则我们称该文法为则我们称该文法为算符文法。算符文法。三三 算符优先分析算符优先分析定义二定义二 假定假定G G是一个不含是一个不含- -产生式的算符文法。对于任产生式的算符文法。对于任何一对终结符何一对终结符a a、b b，我们说：，我们说：la a b b， 当且仅当文法当且仅当文法G G中含有形如中含有形如P-P-abab 或或P-P-aQbaQb的产生式；的产生式； （如：（如：（E E），则（），则（ ）la ba b， 当且仅当当且仅当G G中含有形如中含有形如P-P-aRaR的产生的产生式，而式，而R bR b 或或

27、R QbR Qb；la ba b， 当且仅当当且仅当G G中含有形如中含有形如P-P-RbRb的产生的产生式，而式，而R R a a 或或 R R aQaQ。 定义三定义三 如果一个算符文法如果一个算符文法G G中的任何终结符对（中的任何终结符对（a a，b b）至多只满足下述三种关系之一：至多只满足下述三种关系之一：a ba b，a ba b，a ba b则称则称G G是一个是一个算符优先文法。算符优先文法。2 2 从算符优先文法构造优先关系表从算符优先文法构造优先关系表v例例: :考虑下面的文法考虑下面的文法G(E)G(E)： (1) EE+T | T(1) EE+T | T (2) TT

28、 (2) TT* *F | FF | F (3) FP (3) FP F | P F | P (4) P(E) | i (4) P(E) | iv由第由第(4)(4)条规则，有条规则，有 (=)(=)；v由规则由规则(1)EE(1)EET T和和(2)T(2)TT T* *F F， 有有 * *；v由由(2) (2) TTTT* *F F 和和(3) (3) FP FP F F ，可得，可得* *+；v由由(3)FP(3)FP F F和和F F P P F F，可得，可得。v由由(4)P(E)(4)P(E)和和 E EE+TE+TT+TT+TT T* *F+TF+TF F* *F+TF+TPF

29、PF* *F+TF+TiFiF* *F+TF+T 有有 (+(+、(* *、(和和(i(aP-a或或P-Qa,P-Qa,则则aFIRSTVT(P)aFIRSTVT(P)；若若aFIRSTVT(Q),aFIRSTVT(Q),且有产生式且有产生式P-QP-Q，则，则aFIRSTVT(P)aFIRSTVT(P)FIRSTVT Pa PaPQaaVQVTN() |,或而 3 3 构造集合构造集合FIRSTVT(P)FIRSTVT(P)的算法的算法v数据结构：数据结构：布尔数组布尔数组FPFP，aa，使得，使得FPFP，aa为真的条件是，当且仅为真的条件是，当且仅当当a a FIRSTVT(P)FIRS

30、TVT(P)。开始时，按上述的规则。开始时，按上述的规则(1)(1)对每个数对每个数组元素组元素FPFP，aa赋初值。赋初值。栈栈STACKSTACK，把所有初值为真的数组元素，把所有初值为真的数组元素FPFP，aa的符号的符号对对(P(P，a)a)全都放在全都放在STACKSTACK之中。之中。v运算：运算：如果栈如果栈STACKSTACK不空，就将顶项逐出，记此项为不空，就将顶项逐出，记此项为(Q(Q，a)a)。对于每个形如对于每个形如PQPQ 的产生式，若的产生式，若FPFP，aa为假，则变其值为真且将为假，则变其值为真且将(P(P，a)a)推推进进STACKSTACK栈。栈。上述过程必

31、须一直重复，直至栈上述过程必须一直重复，直至栈STACKSTACK拆空为止。拆空为止。lFIRSTVT(P)FIRSTVT(P)的自动构造的自动构造过程过程INSERTINSERT： PROCEDURE INSERT(P,a)PROCEDURE INSERT(P,a) IF NOT FP,a THEN IF NOT FP,a THENBEGIN BEGIN FP,a := TRUE FP,a := TRUE； 把把(P,a)(P,a)下推进下推进STACKSTACK栈栈 END;END;主程序：主程序：BEGINBEGIN FOR FOR 每个非终结符每个非终结符P P和终结符和终结符a DO

32、 FP,a := FALSE;a DO FP,a := FALSE; FOR FOR 每个形如每个形如P-a P-a 或或P-QaP-Qa的产生式的产生式 DO DO INSERT(P,a);INSERT(P,a); WHILE STACK WHILE STACK 非空非空 DODO BEGIN BEGIN把把STACKSTACK的顶项，记为的顶项，记为(Q,a)(Q,a)，弹出去，弹出去FOR FOR 每条形如每条形如P-QP-Q的产生式的产生式 DODO INSERT(P,a) INSERT(P,a) END OF WHILE; END OF WHILE;ENDEND这个算法的工作结果得到

33、一个二维数组这个算法的工作结果得到一个二维数组F F，从它可得任何非终结符，从它可得任何非终结符P P的的FIRSTVTFIRSTVT。 FIRSTVT(P) FIRSTVT(P)a | FPa | FP，a=TRUEa=TRUE4 4 构造集合构造集合LASTSTVT(P)LASTSTVT(P)的算法的算法,|)(NTVQVaaQPaPaPLASTVT而或 P-a P-a 或或 P-aQ,P-aQ,则则aLASTVT(P)aLASTVT(P)；若若aLASTVT(Q),aLASTVT(Q),且有产生式且有产生式P-QP-Q，则，则aLASTVT(P)aLASTVT(P)lLASTVT(P)L

34、ASTVT(P)的自动构造的自动构造过程过程INSERTINSERT： PROCEDURE INSERT(P,a)PROCEDURE INSERT(P,a)IF NOT LP,a THENIF NOT LP,a THEN BEGIN BEGIN LP,a := TRUELP,a := TRUE；把把(P,a)(P,a)下推进下推进STACKSTACK栈栈 END;END;主程序：主程序：BEGINBEGIN FOR FOR 每个非终结符每个非终结符P P和终结符和终结符a DO LP,a := FALSE;a DO LP,a := FALSE; FOR FOR 每个形如每个形如P- P- a

35、a 或或P- P- aQ aQ的产生式的产生式 DO DO INSERT(P,a);INSERT(P,a); WHILE STACK WHILE STACK 非空非空 DODO BEGIN BEGIN把把STACKSTACK的顶项，记为的顶项，记为(Q,a)(Q,a)，弹出去，弹出去FOR FOR 每条形如每条形如P- P- Q Q的产生式的产生式 DODO INSERT(P,a) INSERT(P,a) END OF WHILE; END OF WHILE;ENDEND5 5 构造优先表方法构造优先表方法 对文法适当改造（增广文法）之后：对文法适当改造（增广文法）之后： 对形如对形如 P-a

36、bP-ab和形如和形如P-aQbP-aQb，有，有a a b b；对形如对形如 P-aRP-aR，而，而bFIRSTVT(R)bFIRSTVT(R)，有，有a a b b；对形如对形如 P-RbP-Rb，而，而aLASTVT(R)aLASTVT(R)，有，有a a b b；优先表中对#的处理(增广文法)vS是文法G的开始符号，给G中添加一个产生式S#S#显然：M#,#:= ;foreach aFIRSTVT(S) M#, a:= ;foreach b LASTVT(S ) Mb, #:= ; MXi , a FOR FOR 每条产生式每条产生式P-X1X2P-X1X2Xn DOXn DO FO

37、R i := 1 TO n-1 DO FOR i := 1 TO n-1 DOBEGINBEGIN IF Xi IF Xi和和Xi+1Xi+1均为终结符均为终结符 THEN THEN 置置Xi Xi+1Xi Xi+1 IF in IF in2 2且且XiXi和和Xi+2Xi+2都为终结符都为终结符但但Xi+1Xi+1为非终结符为非终结符 THEN THEN 置置Xi Xi+2;Xi Xi+2; IF Xi IF Xi为终结符而为终结符而Xi+1Xi+1为非终结符为非终结符THENTHENFOR FIRSTVT(Xi+1)FOR FIRSTVT(Xi+1)中的每个中的每个a DOa DO置置 X

38、i a;Xi a; IF Xi IF Xi为非终结符而为非终结符而Xi+1Xi+1为终结符为终结符 THENTHENFOR LASTVT(Xi)FOR LASTVT(Xi)中的每个中的每个a DOa DO置置 a Xi+1a Xi+1ENDEND例1 设有表达式的文法GE：E E + T | TT T * F | FF (E) | id构造该文法的算符优先关系表。首先S#E#计算每个非终结符的FIRSTVT和LASTVT FIRSTVT LASTVT E *, +, (, id *, +, ), id T *, (, id *, ), id F (, id ), id P-aP-a或或P-Qa

39、,P-Qa,则则aFIRSTVT(P)aFIRSTVT(P)；若若aFIRSTVT(Q),aFIRSTVT(Q),且有产生式且有产生式P-QP-Q，则，则aFIRSTVT(P)aFIRSTVT(P) P-a P-a 或或 P-aQ,P-aQ,则则aLASTVT(P)aLASTVT(P)；若若aLASTVT(Q),aLASTVT(Q),且有产生式且有产生式P-QP-Q，则，则aLASTVT(P)aLASTVT(P)+ T 寻找终结符在左边，非终结符在右边的符号对有寻找终结符在左边，非终结符在右边的符号对有 则则+ FIRSTVT(T).* * F则则* * FIRSTVT(F)则则( FIRST

40、VT(E)( E * *, (, id (, id * *, +, (, id 逐条扫描文法规则，因有逐条扫描文法规则，因有E(E)的规则，则有的规则，则有( ) 寻找非终结符在左边，终结在右边的符号对有寻找非终结符在左边，终结在右边的符号对有 E +E +则则LASTVT(E) LASTVT(E) + +则则LASTVT(T) LASTVT(T) * *T T * *则则LASTVT(E) LASTVT(E) ) )E )E )补充：补充：# # # # # # FIRSTVT(E) LASTVT(E) FIRSTVT(E) LASTVT(E) # # * *, ), id , ), id

41、* *, +, ), id , +, ), id 例EE+T|T TT*F|F S#E#FPF|P P(E)|i+*i()#+ * i ( ) # a b 当且仅当当且仅当G中有中有Pab或或PaQba b 当且仅当当且仅当G中有中有PaR且且b FIRSTVT(R)a b 当且仅当当且仅当G中有中有PRb且且a LASTVT(R)6 6 算符优先分析算法的设计算符优先分析算法的设计l定义定义 1 1）文法文法G G，开始符号，开始符号S S，若，若S S ，如果，如果S S 且且 A A ，则称则称是句型是句型的一个的一个短语短语。2 2）所谓素短语是指这样一个短语所谓素短语是指这样一个短语

42、, ,它至少含有一个它至少含有一个终终结符结符, ,并且并且, ,除自身之外除自身之外, ,不再含任何更小的不再含任何更小的素短语素短语。3 3）句型最左边的那个素短语叫句型最左边的那个素短语叫最左素短语最左素短语。v考虑下面的文法考虑下面的文法G(E)G(E)： (1) EE+T | T(1) EE+T | T (2) TT (2) TT* *F | FF | F (3) FP (3) FP F | P F | P (4) P(E) | i (4) P(E) | iE EE EF F+ +* *T Ti iF FT TF FT TP P+ +E ET TP P句型：句型：T+FT+F* *P

43、+iP+i短语：短语：直接短语：直接短语：句柄：句柄：素短语：素短语：最左素短语：最左素短语：, T+F, T+F* *P+iP+iT T, F, F, P, P, F, F* *P,P, i, iT+FT+F* *P PT T, F, F, P, P, i, iT TF F* *P P , i, iF F* *P Pl定理定理: :一个算符优先文法一个算符优先文法G G的任何句型的最左素短语是满的任何句型的最左素短语是满足以下条件的最左子串足以下条件的最左子串 NNj ja aj j N Ni ia ai iNNi+1i+1， a aj-1j-1 a aj ja aj j a aj+1 j+

44、1 , , , a , ai-1 i-1 a ai i a ai i a ai+1i+1算符优先文法的句型一般形式：算符优先文法的句型一般形式：#N#N1 1a a1 1NN2 2a a2 2NNn na an nNNn+1n+1# # 其中，其中，a ai i V VT T，NNi i V VNN| | 任何两个终结符间任何两个终结符间顶多顶多只有一个非终结符只有一个非终结符.l也即：也即： a aj-1j-1 a ai+1i+1 NNj j a aj j a ai i NNi+1i+12 例例5.5 i1 i1 * *( i2 + i3) # ( i2 + i3) # # # i1 i1

45、* * ( ( i2 i2 + + i3i3 ) ) # #i1i1，i2i2，i3i3是素短语；是素短语；i1 i1是最左素短语。是最左素短语。对定理的解释句型 #N1a1N2a2NnanNn+1#记为 NjajNiaiNi+1由由a aj-1j-1 a aj j可知有规范推导（最右推导）：可知有规范推导（最右推导）： R R NNj ja aj jNNi ia ai iNNi+1i+1 由由a ai i a ai+1i+1 可知有规范推导：可知有规范推导： R R NNj ja aj jNNi ia ai iNNi+1i+1 由由 a aj j a aj+1 j+1 , a, ai-1i-

46、1 a ai i 可知可知NNj ja aj jNNi ia ai iNNi+1 i+1 是某个产生式规则是某个产生式规则( (其左部设为其左部设为R R）的候选式）的候选式; ;根据根据最左素短语最左素短语的定理，最左素短语中的终结符的定理，最左素短语中的终结符号具有相同的优先关系，并且，由于最左素短语号具有相同的优先关系，并且，由于最左素短语中的符号是当时中的符号是当时最先要归约的串最先要归约的串，其优先关系先，其优先关系先于最左素短语之外的符号，所以我们使用一个用于最左素短语之外的符号，所以我们使用一个用于存放文法符号的于存放文法符号的先进后出栈先进后出栈，并利用优先关系，并利用优先关系

47、表，可以确定最左素短语是否已形成来决定分析表，可以确定最左素短语是否已形成来决定分析器的动作。器的动作。 l算法分析：算法分析：# #t t1 1t t3 3t tj+1j+1t t2 2t tj jt ti+1i+1t tn n# #符号栈符号栈t ti i 尾尾头头最左素短语最左素短语算符优先分析程序的基本思想算符优先分析程序的基本思想: : . .S j a ? 或或 S j a ?N.=.YS j Q?.N说明说明:算法中算法中K为符号栈为符号栈S的指针，的指针，a用来存放当用来存放当前输入符号，前输入符号，j是栈的是栈的查找指针，查找指针，Q是工作是工作单元。单元。117算符优先分析

48、举例算符优先分析举例+ +* * i i( () )# #+ +* *i i( () )# # 步步骤骤分析栈分析栈剩余输入串剩余输入串所用产所用产生式生式/Q 1 #1 # i+i i+i* *ii #ii # 2 #i2 #i +i +i* *iiii # # Q=iQ=i 3 #P +i3 #P +i* *iiii # # 4 #P+4 #P+ i i* *iiii # # 5 #P+i5 #P+i * *iiii # # Q=iQ=i 6 #P+P6 #P+P * *iiii # # 7 #P+P7 #P+P* * ii ii # # 8 #P+P 8 #P+P* *i i i i #

49、 # Q=iQ=i 9 #P+P 9 #P+P* *P P i i # # G G：(1)E(1)EE+T|TE+T|T (2)T (2)TT T* *F|FF|F (3)F (3)FPF|PPF|P (4)P (4)P(E)|i(E)|i1185.2 5.2 算符优先分析算符优先分析+ +* * i i( () )# #+ +* *i i( () )# # 步骤分析栈剩余输入串所用产生式 9 #P+P9 #P+P* *P i #P i #Q=iQ=i 10 #P+P10 #P+P* *P P i # i # 11 #P+P11 #P+P* *P Pi #i # 12 #P+P12 #P+P*

50、 *P PP #P #Q=Q= 13 #P+P13 #P+P* *F F # #Q=Q=* * 14 #P+14 #P+T T # #Q=+ Q=+ 15 #15 #E E # #G G：(1)E(1)EE+T|TE+T|T (2)T (2)TT T* *F|FF|F (3)F (3)FPF|PPF|P (4)P (4)P(E)|i(E)|iv对于算符优先分析法，它虽然是一种自下对于算符优先分析法，它虽然是一种自下而上的语法分析方法，但它并不是一种而上的语法分析方法，但它并不是一种规规范归约范归约的分析方法。的分析方法。WHY?WHY?v这是因为在算符优先文法中，仅在终结符这是因为在算符优先文

51、法中，仅在终结符号之间定义优先关系而未对非终结符定义号之间定义优先关系而未对非终结符定义优先关系，从而无法使用优先关系表去识优先关系，从而无法使用优先关系表去识别由别由单个非终结符单个非终结符组成的组成的可归约串可归约串v算符优先分析法不是用算符优先分析法不是用句柄句柄来刻画可归约来刻画可归约串，而是用串，而是用最左素短语最左素短语来刻画可归约串的。来刻画可归约串的。v算符优先分析一般并不等价于规范归约。算符优先分析一般并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiPn考虑下面的文法考虑下面的文法G(E)G(E)： (1) EE+T | T(1) E

52、E+T | T (2) TT (2) TT* *F | FF | F (3) FP (3) FP F | P F | P (4) P(E) | I (4) P(E) | I 的句子的句子i+ii+i* *i+ii+iv算符优先分析法特点：算符优先分析法特点：优点优点: : 简单，快速简单，快速缺点缺点: : 可能错误接受非法句子，能力有限可能错误接受非法句子，能力有限. .v算符优先分析法是一种广为应用、行之算符优先分析法是一种广为应用、行之有效的方法。有效的方法。用于分析各类表达式用于分析各类表达式ALGOL 60ALGOL 607 7 优先函数优先函数 l定义：定义： 我们把每个终结符我们

53、把每个终结符与两个自然数与两个自然数f( f() ) 和和g(g() )相对相对应，使得：应，使得： 若若1 1 2 2，则，则f( f(1 1)g()g()g(2 2) )函数函数 f f 称为称为入栈优先函数入栈优先函数，g g 称为称为比较优先函数比较优先函数。l使用优先函数的优缺点：使用优先函数的优缺点：优：便于比较运算；节省存储空间。优：便于比较运算；节省存储空间。缺：对不存在优先关系的两个终结符，由于与自然数相缺：对不存在优先关系的两个终结符，由于与自然数相 对应，变成可比较对应，变成可比较。l优先函数的性质：优先函数的性质：1）正确性：）正确性：优先函数掩盖了矩阵中出错元素对，若

54、优先函数掩盖了矩阵中出错元素对，若f(id) g(b) f(a) g(b) f(b) = g(a) f(b) = g(a) f(b) = g(b) f(b) = g(b)那么，那么，f(a)g(b)=f(b)=g(a)=f(a)f(a)g(b)=f(b)=g(a)=f(a)，矛盾。，矛盾。baba g(x)f(x)3）唯一性：）唯一性：存在一个优先函数，就有无数多对，加一常数，不等存在一个优先函数，就有无数多对，加一常数，不等式也成立。式也成立。l构造优先函数的方法构造优先函数的方法（如果优先函数存在的话）（如果优先函数存在的话）构造优先函数的方法v已知优先关系表，构造一个有向图H=(V,E)

55、，foreach (aVT ) 置fa V;置ga V 结点为终结符a对应的符号fa和ga;if (a b)置(fa , gb)E 画结点fa到结点gb一条弧；if (a b)置(gb , fa)E 画结点gb到结点fa一条弧；v定义优先函数f和g,令f(a)为从fa出发所能达到的结点个数+1;令g(a)为从ga出发所能达到的结点个数+1;v检查f和g有无矛盾，若有则不存在优先函数否则成功v对每个对每个a a（包括）（包括）V VT T，对应两个符号，对应两个符号f fa a，g ga a。v把所建立的符号尽可能划分为许多组：把所建立的符号尽可能划分为许多组：若若a ba b，则，则f fa

56、a和和g gb b就在一组；就在一组；若若a ba b，c bc b，则，则f fa a和和f fc c同组；同组；v建立一个有向图，其结点是上一步中找出的组。建立一个有向图，其结点是上一步中找出的组。对于任何对于任何a a和和b b，若，若 a ba b，画，画 f fa aggb b 弧，意味着弧，意味着f(a)g(b)f(a)g(b)； 若若 a ba b，画，画 g gb bffa a 弧，意味着弧，意味着f(a)g(b)f(a) E+E | E*E | EE | ( E ) | i的终结符的优先关系表，构造优先函数。的终结符的优先关系表，构造优先函数。f+f*ff)f(g)g(gg*

57、g+由优先关系表，得：由优先关系表，得： + ) ( * + *其余类同其余类同4662935882算符优先-最左素短语规范归约-句柄自下而上(自动生成)递归下降-消除左递归预测分析法- 预测分析表 自上而下(手动，自动生成)语法分析4 4 LR LR分析法分析法lLRLR分析程序分析程序( (器器) )：自左向右自左向右扫描，识别句柄，扫描，识别句柄，自下而上自下而上归约的归约的 语法分析程序语法分析程序。lLRLR分析程序生成器：自动生成分析程序生成器：自动生成LRLR分析程序的程分析程序的程序。序。- “L”, “L”, 代表从代表从左左（LeftLeft）向右扫描输入单词序列）向右扫描

58、输入单词序列- “R R”, ,代表产生的是代表产生的是最右最右（RightmostRightmost）推导）推导 主要学习四种主要学习四种 LRLR 分析技术分析技术- LRLR（0 0）分析）分析 适用于适用于 LRLR（0 0）文法）文法- SLRSLR（1 1）分析）分析 适用于适用于 SLRSLR（1 1）文法）文法- LRLR（1 1）分析）分析 适用于适用于 LRLR（1 1）文法）文法- LALRLALR（1 1）分析）分析 适用于适用于 LALRLALR（1 1）文法）文法S Simpleimple LR(1) LR(1)L LookookA Aheadhead LR(1)

59、LR(1)“0” “0” - - 向前查看向前查看 0 0 个符号个符号“1” “1” - - 向前查看向前查看 1 1 个符号个符号分析表分析表产生器产生器文法文法分析表分析表总控总控程序程序输入输入输出输出分析表分析表l分析表的构造方法分析表的构造方法LR(0)表构造法SLR表构造法规范LR表构造法LALR（向前LR）表构造法分析表的构造方法最简单最简单, ,局限性大局限性大( (绝大多数高级语言绝大多数高级语言的语法分析器均不适用的语法分析器均不适用),),但却是建立但却是建立其它较一般的其它较一般的 LRLR分析法的基础分析法的基础. .一种较易实现又极有使用价值的方法一种较易实现又极

60、有使用价值的方法, ,对某些文法不适用对某些文法不适用. .能力最强能力最强, ,能适用一大类文法能适用一大类文法, ,但实现但实现代价过高代价过高( (分析表体积太大分析表体积太大).).能力介于能力介于SLRSLR和规范和规范LRLR之间之间, ,稍加努力稍加努力, ,即可高效实现即可高效实现. .l规范归约规范归约的关键问题是寻的关键问题是寻找找句柄句柄. .l“历史历史”：已移入符号栈的：已移入符号栈的内容内容l“展望展望”：根据产生式推测：根据产生式推测未来可能遇到的输入符号未来可能遇到的输入符号l“现实现实”：当前的输入符号：当前的输入符号l把把“历史历史”及及“展望展望”综合抽象