编译原理 第5章 语法分析――自底向上分析

语法分析方法的分类（分类标准是按照识别句子时建立语法树的方法）：分析法分析法分析法分析法分析法算符优先分析法简单优先分析法优先分析法自底向上带回溯递归下降分析法分析法不带回溯自顶向下语法分析)1()1()1()0()(LALRLRSLRLRLRKLL第5章语法分析——自底向上分析自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输入串。即：开始符号输入符号串+自底向上的分析方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：开始符号输入符号串归约←第5章语法分析——自底向上分析第5章语法分析—自底向上分析(P78)5.1规范推导、规范句型和规范归纳5.2自底向上分析方法的一般过程5.3LR分析方法5.4LR(0)分析器5.5SLR(1)分析器5.6LR(1)分析器5.7LALR(1)分析器5.8语法分析程序的自动生成工具—YACC活前缀、识别活前缀的DFA的构造LR(0)项目、LR(1)项目LR(0)分析表、SLR(1)分析表、LR(1)分析表、LALR(1)分析表的构造LR(0)文法、LR(1)文法、SLR(1)文法和LALR(1)文法学习重点5.1规范推导、规范句型和规范归约规范推导就是最右推导。规范句型是通过规范推导能得到的句型。注意，并非所有句型都是规范句型。规范归约也称为最左归约，是规范推导的逆过程，即在分析的每一步，将当前句型的句柄归约成相应的非终结符号。例5-1(P78)有文法G[S]：S::=aAcBeA::=bA::=AbB::=d试分析符号串abbcde是否为该文法的句子。解：符号串abbcde的规范推导过程为：SaAcBeaAcdeaAbcdeabbcde符号串abbcde的规范归约过程为：5.2自底向上分析方法的一般过程自底向上分析方法是采用移进归约法来实现的。移进归约法的一般过程：设置一个符号栈。在分析进行时，把输入符号一个个地按扫描顺序移进栈里，当栈顶符号串形成一个句柄(即为某条规则的右部)时，就进行一次归约，即把栈顶构成句柄的那个符号串用相应规则左部的非终结符号来代替。接着再检查栈顶是否又出现了新的句柄，若出现新的句柄，就再进行归约；若没有形成新的句柄，则再从输入符号串移进新的符号，如此继续直到整个输入符号串处理完毕。最终如果栈里只有识别符号，则所分析的输入符号串为合法的句子，报告成功；否则，输入串是不合法的符号串，报告错误。界限符#进栈进栈进栈用A→b归约进栈用A→Ab归约进栈进栈用B→d归约进栈用S→aAcBe归约接受abbcde#bbcde#bcde#bcde#cde#cde#de#e#e######a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#S123456789101112动作输入符号串符号栈步骤例(P79)有输入串abbcde的分析过程(文法见例5-1,P78)通过上述分析可看出，每次归约的句柄都出现在符号栈的栈顶，不会出现在栈的中间，因为我们的算法是自左向右扫描输入符号串，进行的是最左归约。5.2自底向上分析方法的一般过程从自底向上分析的一般过程可看出，如何寻找或确定一个句型的句柄，是构造一个自左向右扫描、自底向上分析方法必须要解决的一个关键问题。上例中的第5步，栈内符号串为aAb，由于文法中同时有规则A::=Ab和A::=b，那么，符号串Ab和b都是某规则的右部，都可以作为句柄归约。如果我们选择b作为句柄归约成A，那么，最终就达不到归约到开始符号S的目的。事实上，我们不能因为规则A::=b就断定b是句柄，因为aAAcde并不是一个句型。对句型aAbcde来说，其简单短语是Ab和d，其中Ab是最左简单短语，所以是句柄。5.3LR分析方法LR(k)分析方法中各符号的含义：L表示从左到右扫描所给定的输入串。R表示以相反的方向构造该输入串的最右推导(即规范推导)。k表示为了做出分析决定需要向前看的输入符号的个数。k通常取0或1。LL(1)分析法LR分析器的模型5.3LR分析方法#在LR分析器的模型中，输入符号串就是等待分析的符号串。分析栈有两部分：一个是符号栈，另一个是状态栈。而控制系统包括一个分析表和一个总控程序。对于不同的文法来说，分析表各有不同，但总控程序都是一样的。5.3LR分析方法LR分析器的工作过程：在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的符号和状态以及当前的输入符号，查阅分析表并按分析表的指示完成相应的分析动作，直到符号栈中出现开始符号。LR分析表由ACTION表和GOTO表两部分组成（见下表）。表中S1、S2、…、Sn为分析器的各个状态；a1、a2、…、am为文法的全部终结符号及右界符（或输入结束符）#；X1、X2、…、Xk为文法的非终结符号。状态ACTION(动作表)GOTO(状态转换表)a1a2…#X1X2…XkS1S2...Sn5.3LR分析方法ACTION[Si，aj]表示当分析状态栈的栈顶为Si，输入符号为aj时应执行的动作；GOTO[Si，Xj]表示当前状态Si下而符号栈顶为非终结符号Xj后应移入状态栈的状态。分析表的动作(P81)：(1)移进(Sn)：将输入符号aj移进符号栈，将状态n移进状态栈，输入指针指向下一个输入符号。(2)归约(R)：当栈顶形成句柄时，按照相应的产生式U→W进行归约。若产生式右部W的长度为n，则将符号栈栈顶n个符号和状态栈栈顶n个状态出栈，然后将归约后的文法符号U移入符号栈，并根据此时状态栈顶的状态Si及符号栈顶的符号U，查GOTO表，将GOTO[Si，U]移入状态栈。5.3LR分析方法分析表的动作(续)：(3)接受(A)：当输入符号串到达右界符#时，且符号栈只有文法的开始符号时，则分析成功结束，接受输入符号串并结束分析。(4)报错(E)：在状态栈的栈顶状态为Si时，如果输入符号为不应该遇到的符号时，即ACTION[Si，aj]=空白，则报错，说明输入符号串有语法错误。5.3LR分析方法例(P81)已知文法G：(0)S→A(1)A→(A)(2)A→a其LR分析表如下表所示(见P81,表5-3)。状态ACTIONGOTO()a#A0S2S311ACCEPT2S2S343R2R2R2R24S55R1R1R1R1LR分析过程:分析开始时，栈内的初始状态为0，符号栈为#。当状态栈顶为某个状态p时，当前输入指针指向的符号是a时，查分析动作表的p行、a列。如果得到的动作指示ACTION[p,a]是移进Si，则将a压入符号栈，将状态i压入状态栈，然后将输入指针指向输入符号串的下一个符号；如果得到的动作指示是归约Ri，且归约产生式为B→β，则从符号栈内弹出|β|个符号，从状态栈内弹出|β|个状态，假设此时出栈后的状态栈栈顶为p，查状态转换表的p行、B列，得到下一个状态GOTO[p,B]=q，并将该后继状态q压入状态栈；如果得到的动作指示是接受，则接受输入的符号串，分析成功结束。5.3LR分析方法(P82)例5-2(P82)利用表5-3分析表(P81)分析符号串“(a)”。接受ACCEPT##A016用A→(A)归约，(A)出符号栈、A入符号栈，245出状态栈、0为栈顶，查GOTO[0，A]=1，1入状态栈1R1##(A)024555入状态栈，)入符号栈S5)##(A0244用A→a归约，a出符号栈、A入符号栈，3出状态栈、2为栈顶，查GOTO[2，A]=4，4入状态栈4R2)##(a02333入状态栈，a入符号栈S3a)##(0222入状态栈，(入符号栈S2(a)##01说明GOTOACTION输入符号串符号栈状态栈步骤解：符号串“(a)”的分析过程：5.4LR(0)分析方法LR(0)分析器是LR分析方法中最简单的一种，在确定分析动作时，不需要向前查看任何符号,它是构造其它更复杂的LR分析器的基础。对文法进行拓广，目的是使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。拓广后的文法称为拓广文法。5.4LR(0)分析方法解：引入一个新的开始符号S，使得文法的开始符号所在的规则唯一，这样得到拓广文法如下：S→EE→T|E+T|E－TT→i|(E)例5-3（P83）对文法G∶E→T|E+T|E－TT→i|(E)进行拓广。前缀指从任意符号串x的末尾删除0或多个符号后得到的符号串，如ε、u、un、uni、university都是university的前缀。活前缀：设λβt是一个规范句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么称ε和符号串u1u2…ui(其中1≤i≤r)是句型λβt的活前缀。活前缀不含句柄右边的任意符号，而可归前缀是含有句柄的活前缀。对一个规范句型来说，活前缀可有多个，可归前缀只有一个。可归前缀：含有句柄的活前缀。5.4LR(0)分析方法例5-4（P84）有文法G:E→T|E+T|E-T，T→i|(E)，找规范句型E+(i-i)的活前缀和可归前缀。ET+E）E（T-ETii解：首先画出E+(i-i)的语法树(如右图所示）。可找出左起第一个i是规范句型E+(i-i)的句柄。规范句型E+(i-i)的活前缀为：ε，E，E+，E+(，E+(i其中，E+(i是可归前缀。5.4LR(0)分析方法在LR分析过程中，如果输入符号串没有语法错误，则在分析的每一步，若将符号栈中的全部文法符号与剩余的输入符号串连接起来，得到的一定是所给文法的一个规范句型。也就是说，压入符号栈中的符号串一定是某一规范句型的活前缀。当符号栈形成句柄，即符号栈的内容为可归前缀时，就会立即被归约。所以说，LR分析就是逐步在符号栈中产生可归前缀，再进行归约的过程。5.4LR(0)分析方法项目：对某个文法G来说，如果A→α1α2为G的一条规则，那么，在规则的右部加上一个圆点“．”，就成为一个项目。特别地，空产生式A→只含有一个项目A→.。例（P85）有文法S→E，E→T|E+T|E-T，T→i|(E)，对于规则S→E右部有一个符号，因圆点位置不同，可有下面两个项目∶S→.ES→E.对于规则E→E－T，右部有三个符号，可有下面四个项目∶E→·E－TE→E.－TE→E－.TE→E－T．5.4LR(0)分析方法项目的分类(根据项目中圆点的位置和后继符号)：（1）移进项目：后继符号为终结符号。例如E→E.－T（2）待约项目：后继符号为非终结符号。例如E→E－.T和S→.E（3）归约项目：后继符号为空，即圆点在最后。例如E→E－T．和S→E.（4）接受项目：文法的开始符号S的归约项目。接受项目是一个特殊的归约项目，它表示该产生式归约后分析将结束。例如上例中的项目S→E.就是接受项目。5.4LR(0)分析方法后继符号：项目中圆点后面的符号。练习给定文法G[S]：S→(A)A→ABBA→BB→bB→c列出该文法的所有项目（又称为该文法的基本LR(0)项目集），并指出该项目集中的移进项目、待约项目、归约项目和接受项目。5.4LR(0)分析方法解：文法G的基本LR(0)项目集为：1S→.(A)2S→(.A)3S→(A.)4S→(A).5A→.ABB6A→A.BB7A→AB.B8A→ABB.9A→.B10A→B.11B→.b12B→b.13B→.c14B→c.其中，1、3、11、13是移进项目；4、8、10、12、14是归约项目；2、5、6、7、9是待约项目；4是接受项目。项目有效性：一个项目A→α1·α2对于某个活前缀λα1是有效的，当且仅当存在某个最右推导：S|λAt|λα1·α2t其中t是终结符号串。5.4LR(0)分析方法*在LR分析过程中，活前缀就是符号栈的内容，是已经读入的符号，它不包含句柄右边的任何符号。活前缀和句柄的关系:(1)如果活前缀包含句柄，表示符号栈顶形成句柄，则就可以归约。假设归约产生式为A→α，由