语法分析(二)

1、2021-10-12西北工业大学软件与微电子学院 machunyan1o 课程内容课程内容 第第1 1章章 概论概论 第第2 2章章 词法分析词法分析 第第3 3章上下文无关文法章上下文无关文法 第第4 4章语法分析章语法分析n 第第4 4章语义分析章语义分析n 第第6 6章运行时环境章运行时环境n 第第7 7章代码生成章代码生成machunyan西北工业大学软件与微电子学院2第四章 自下而上的语法分析 4.1 自下而上的语法分析概览 4.2 LR分析概览 4.3 LR(0)项目的有穷自动机与LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.

2、7 语法分析器自动生成工具YACC作业machunyan西北工业大学软件与微电子学院34.1 自下而上的语法分析概览自下而上的语法分析概览自下而上语法分析方法自下而上语法分析方法：从输入单词序列开始，自左至右逐步进行归约，试图将其归约为文法的开始符号。 从输入单词序列开始，以单词做为语法树的叶节点，自底向上地构造语法分析的结果-语法树。machunyan西北工业大学软件与微电子学院4例:文法G： S cAd A ab A a试采用自下而上的语法分析方法识别输入串cabd是否是该文法所定义的句子？4.1 自下而上的语法分析概览自下而上的语法分析概览(续续)machunyan西北工业大学软件与微电

3、子学院5 b d c a自左至右规约的过程： c aA b dSA c a b dcabd cAdcAd S4.1 自下而上的语法分析概览(续)自左至右规约是规范推导的逆过程, 所以称之为规范规约。machunyan西北工业大学软件与微电子学院6SraAcBeraAcde raAbcde rabbcde建立输入串abbcde的规范推导：规范归约是规范推导的逆过程：abbcde aAbcde aAcde aAcBeS对于文法GS:SaAcBe Ab AAb Bd4.1 自下而上的语法分析概览(续)machunyan西北工业大学软件与微电子学院74.1 自下而上的语法分析概览(续)o 在自下而上语

4、法分析工作的每一步，都是从在自下而上语法分析工作的每一步，都是从当前串中选择一个子串，将它归约到某个非当前串中选择一个子串，将它归约到某个非终结符号；终结符号；o 为了方便对自下而上的语法分析方法进行描为了方便对自下而上的语法分析方法进行描述，本章将每次述，本章将每次规约的子串规约的子串称为称为句柄句柄；machunyan西北工业大学软件与微电子学院8n句型的直接短语：若有S =*A ，、(VNVT)*则称是句型相对于非终结符A 的直接短语;文法GSn句型的句柄： 句型的最左直接短语（在规范推导中，最先被归约的子串），称为该句型的句柄;理解句柄machunyan西北工业大学软件与微电子学院9求

5、句型i*i+i 的直接短语和句柄例4.1:已知文法GE：EE+T|T TT*F|F F(E)|i直接短语： i1 ， i2 ， i3句柄： i1EE+TFi3T*TFi2Fi1machunyan西北工业大学软件与微电子学院10o 总结本节内容：总结本节内容：o 自下而上的语法分析算法通常采用自下而上的语法分析算法通常采用规范规范归约归约，即规范推导的逆过程；，即规范推导的逆过程；n 规范规约的每一步是从当前的规范句型中将句柄归约为相应的非终结符；4.1 自下而上的语法分析概览(续)machunyan西北工业大学软件与微电子学院11第4章 自下而上的语法分析 4.1 自下而上的语法分析概览 4.

6、2 LR分析概览 4.3 LR(0)项目的有穷自动机与LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 语法分析器自动生成工具YACC作业machunyan西北工业大学软件与微电子学院124.2 LR 分析概览o LR分析法分析法是一种有效的自下而上的语法分是一种有效的自下而上的语法分析技术，它能适用于大部分上下文无关文法析技术，它能适用于大部分上下文无关文法的分析，一般叫的分析，一般叫LR(k)分析方法，其中分析方法，其中n L是指自左(Left)向右分析输入单词序列，n R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)

7、，n 括号中的k是指在决定当前分析动作时向右看的单词个数。machunyan西北工业大学软件与微电子学院134.2 LR 分析概览(续)o 有以下原因使得有以下原因使得 LR分析法分析法与其它语法分析方法相与其它语法分析方法相比，应用更广泛，具有更强的吸引力。比，应用更广泛，具有更强的吸引力。n 应用面广：能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的语法结构；n 能有效实现：是无回溯的移进归约方法；n 容易查错：LR分析器能够及时发现语法错误和准确指出错误位置。machunyan西北工业大学软件与微电子学院14例4.2 考虑以下文法：abbcde对应的规范规约：构造规范规

8、约的语法分析程序要解决的问题？对于文法GS:SaAcBe Ab AAb Bdabbcde aAbcdeaAcde aAcBe Smachunyan西北工业大学软件与微电子学院15移进$abbcde$1下表给出了使用该文法对串acbc的LR分析。分析栈输入动作步骤$a bbcde$移进2$ab bcde$用Ab归约3$aA bcde$移进4$aAb cde$用AAb归约5$aA cde$移进6$aAc de$移进78$aAcd e$用Bd归约$aAcB e$移进9$aAcBe $用SaAcBe归约1011$ S $接受machunyan西北工业大学软件与微电子学院16分析栈输入动作步骤移进$ab

9、bcde$10$a bbcde$移进202$ab bcde$用Ab归约3025$aA bcde$移进4023$aAb cde$用AAb归约50236$aA cde$移进6023$aAc de$移进702348$aAcd e$用Bd归约02347$aAcB e$移进902348$aAcBe $用SaAcBe归约10 02348911$ S $接受01状态栈machunyan西北工业大学软件与微电子学院17o 为了描述何时移进，何时规约，现将为了描述何时移进，何时规约，现将分分析栈中存储的符号串称之为活前缀析栈中存储的符号串称之为活前缀；o 符号串前缀的定义符号串前缀的定义：符号串的前缀是指从符号

10、符号串的前缀是指从符号串的尾部删去若干串的尾部删去若干(包括包括0个个)个符号之后所余下个符号之后所余下的部分。的部分。n 若 x，y，z是字母表上的符号串，且z=xy,则x是符号串z的前缀，y是符号串z的后缀。4.2 LR 分析概览(续)machunyan西北工业大学软件与微电子学院18当前规范句型()的句柄是什么？o 活前缀和可归前缀活前缀和可归前缀：n 设有文法GS，若S =* A = 是文法G的一个规范推导，(， (VT VN)+，VT*，AVN)，o的一个前缀称为文法G的一个活前缀o称为文法G的可归前缀。n 包含句柄的活前缀是可归前缀？4.2 LR 分析概览(续)machunyan西

11、北工业大学软件与微电子学院19在对文法句型规范归约的过程中，自左向右分析输入串的任何时刻，在符号栈中的符号串均为规范句型的活前缀。如果符号栈的内容是当前句型的可归前缀，那么栈顶已经形成当前句型的句柄，进行归约，否则继续移进。machunyan西北工业大学软件与微电子学院20规范句型当前句柄可归前缀abbcdebabaAbcdeAbaAbaAcdedaAcdaAcBeaAcBeaAcBeSSS例，对于GS SaAcBe Ab AAb Bd 输入串:abbcdemachunyan西北工业大学软件与微电子学院21LR分析算法的关键技术：分析算法的关键技术：o 如何识别如何识别(符号栈符号栈)栈顶的符

12、号组成的符号串栈顶的符号组成的符号串是否是是否是可归前缀，是可归前缀就规约，否则可归前缀，是可归前缀就规约，否则移进移进o 分析表指导，分析表如何构造分析表指导，分析表如何构造n 求文法中的所有可归前缀n 识别可归前缀和活前缀分析表的构造123machunyan西北工业大学软件与微电子学院221.求文法中的所有可归前缀方法：对任一文法，若已知它有可归前缀xUy，UVN，且文法中有产生式Uu，则有xUy xuy,则xu也是文法的可归前缀。例：对文法 (1) SaAcBe (2) Ab (3) AAb (4) Bd例：对拓广文法 (0) SS (1) SaAcBe (2) Ab (3) AAb (

13、4) Bdmachunyan西北工业大学软件与微电子学院23据拓广文法有：S SrS为当前句型S的句柄，故S为可归前缀。因S为可归前缀，且有产生式SaAcBe，故 aAcBe是可归前缀因aAcBe 为可归前缀，且有产生式AAb，故aAb是可归前缀因aAcBe 为可归前缀，且有产生式Ab，故ab是可归前缀1.求文法中的所有可归前缀(续)machunyan西北工业大学软件与微电子学院24因aAb 为可归前缀，且有产生式AAb，故aAb是可归前缀(重复)因aAb 为可归前缀，且有产生式Ab，故ab是可归前缀(重复)因aAcBe 为可归前缀，且有产生式Bd，故aAcd是可归前缀1.求文法中的所有可归前

14、缀(续)machunyan西北工业大学软件与微电子学院25因aAcd 为可归前缀，且有产生式AAb，故aAb是可归前缀(重复)因aAcd 为可归前缀，且有产生式Ab，故ab是可归前缀(重复)所以文法的可归前缀有：S , aAcBe , aAb , ab , aAcd1.求文法中的所有可归前缀(续)machunyan西北工业大学软件与微电子学院262.识别可归前缀和活前缀o 可以证明一个文法可以证明一个文法G的所有可归前缀是一个的所有可归前缀是一个正规集，它可以由正规集，它可以由DFA加以识别。加以识别。每个终态都是可归前缀的识别态。234ab4678baA910111213aAcd141416

15、171819aAcBe01S*终结符和非终结符都看成是有限自动机的输入符号。machunyan西北工业大学软件与微电子学院27将以上有限自动机合并：234ab4678baA910111213aAcd141416171819aAcBe01S* x从初态到任一终态形成的符号串构成了文法的可归前缀o 可以指导可以指导移进移进-规约规约动作动作?machunyan西北工业大学软件与微电子学院2825bbAcdBe1*0Sa348679识别上述文法所有可归前缀的DFA输入串:abbcdemachunyan西北工业大学软件与微电子学院292.识别可归前缀和活前缀(续)o 上述有限自动机就是识别该文法所有活

16、前缀上述有限自动机就是识别该文法所有活前缀和可归前缀的有限自动机。和可归前缀的有限自动机。n 中间状态为活前缀识别态（移进）；n 所有终态都是可归前缀的识别态，此时分析栈中形成句柄（规约）；n 带星号（*）的状态为唯一的句子识别态，这次归约到开始符号；machunyan西北工业大学软件与微电子学院303.分析表的构造n 分析表分析表由由动作表动作表和和状态转换表组成状态转换表组成：n 动作表(Action)以一个二维数组表示，列代表识别活前缀的状态，行代表当前的输入符号，数组元素Actioni，a表示所执行的分析动作，即：当前识别活前缀的状态为i，而输入符号为a时所执行的动作。machunya

17、n西北工业大学软件与微电子学院313.分析表的构造(续) Action Actiona ab bc cd de e $ $ 0 0S S1 1成功成功2 2S S3 3S SS S4 4r rr rr rr rr r4 4S S6 6r rr rr rr rr r7 7r rr rr rr rr r8 8S S9 9r rr rr rr rr rmachunyan西北工业大学软件与微电子学院32o 共有共有4种动作：种动作：n 移进：输入符号进符号栈；n 归约：用相应的产生式进行归约；n 接受：当文法符号归约到只剩下开始符号，且输入串结束时(当前输入为$)，分析成功；n 报警：当状态栈顶为某一

18、状态下，出现了不该出现的文法符号时，报错。3.分析表的构造(续)machunyan西北工业大学软件与微电子学院33p 分析表分析表由由动作表动作表和和状态转换表组成状态转换表组成：n 状态转换表用一个二维数组表示，列代表识别活前缀的状态，行代表文法符号，数组元素表示当前识别活前缀的状态为i面对文法符号为X时，应转去的新状态Gotoi,X。3.分析表的构造(续)machunyan西北工业大学软件与微电子学院343.分析表的构造(续) Goto Gotoa ab bc cd de e $ $ S S A A B B0 02 21 11 12 25 53 33 36 64 44 47 75 58 8

19、6 67 78 89 99 9machunyan西北工业大学软件与微电子学院35ActionGotoab$S0S211acc2S44r2r2r2r2动作表和状态转换表的合并machunyan西北工业大学软件与微电子学院36LR分析算法的逻辑结构：总控程序a1a2aiai+1an$动作表状态转换表分析表输出Xm.X1$状态栈符号栈m.10识别活前缀的自动机状态machunyan西北工业大学软件与微电子学院37o 在总控程序的控制下，从左到右处理词法分析输入串，在总控程序的控制下，从左到右处理词法分析输入串，根据分析栈和输入符号的情况，查分析表确定分析动作；根据分析栈和输入符号的情况，查分析表确定

20、分析动作；n 分析栈包括文法符号栈Xi和相应的状态栈Si两部分(状态是指识别活前缀的自动机状态) 。n 分析表是LR分析器的核心，它包括动作表(Action)和状态转换表(Goto)两部分;n 根据识别文法所有活前缀和可归前缀的有限自动机，可以构造分析表来指导移进-规约动作；4.2 LR 分析概览(续)machunyan西北工业大学软件与微电子学院38第4章 自下而上的语法分析 4.1 自下而上的语法分析 4.2 LR分析概览 4.3 LR(0)项目的有穷自动机与LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 语法分析器自动生成工具YA

21、CC作业o 1. 构造识别活前缀的构造识别活前缀的NFAo 2. 构造识别活前缀的构造识别活前缀的DFAo 3. LR(0)分析表的构造分析表的构造o 4 . LR(0)分析算法分析算法o 4. 项目的分类项目的分类o 6. LR(0)文法的定义文法的定义machunyan西北工业大学软件与微电子学院394.3 LR(0)分析算法machunyan西北工业大学软件与微电子学院404.3 LR(0)分析算法分析算法o 为了由文法为了由文法G的产生式直接构造识别活前缀的的产生式直接构造识别活前缀的DFA，首先给出项目的定义。，首先给出项目的定义。o 定义：对于文法G，其产生式的右部添加一个特殊符号

22、“.”就构成文法的一个LR(0)项目，简称项目。n 若A是产生式，其中和是任意符号串（包括空串），那么A. 就是LR(0)项目。machunyan西北工业大学软件与微电子学院41例对于文法：SS S( S ) S | 有以下LR(0)项目：S.SSS.S.S. ( S ) SS( .S ) SS( S. )SS( S ) .SS( S )S.每个项目中圆点的左部表示在分析过程中，要用该产生式归约时，句柄已识别的部分(进入符号栈)，右部表示等待识别的部分。machunyan西北工业大学软件与微电子学院42o NFA的构造原则的构造原则:为了确保有唯一的接受项目，首为了确保有唯一的接受项目，首先拓

23、广文法先拓广文法G为为G,引进一新的产生式引进一新的产生式S S ， S是新是新增加的非终结符作为增加的非终结符作为G的开始符。的开始符。n NFA的状态集：每个项目对应一个NFA状态，所有项目对应的状态的集合；n 输入字符集合：包括终结符、非终结符和；n 初态：对于文法GS的拓广文法GS,有项目S . S ,由于S仅在第一个产生式的左部出现，规定它为初态； 终态：对于拓广文法GS，有项目Uu. (即圆点在最后的项目)，作为NFA的终态；1. 构造识别活前缀的NFAmachunyan西北工业大学软件与微电子学院43 转换函数f：若文法中有项目i为：Xx1xi-1.xixn 项目j为：Xx1xi

24、.xi+1xn1) 则有转换函数GO(i，xi)=j 2) 若xi为非终结符号，则还有转换函数GO (i, )=k 项目k为：xi . 1. 构造识别活前缀的NFA(续)machunyan西北工业大学软件与微电子学院44S(.S )SSS(S .)SS.S.(S)S例如：项目 S( .S ) S 的转换有：1. 构造识别活前缀的NFA(续)考虑文法： SS S( S ) S | 对应的LR(0)项目的NFA，见下页所示。machunyan西北工业大学软件与微电子学院45machunyan西北工业大学软件与微电子学院46machunyan西北工业大学软件与微电子学院47 例：对拓广文法(0) S

25、S(1) SaAcBe(2) Ab(3) AAb(4) Bd求出其对应的LR(0)项目的NFA1. 构造识别活前缀的NFA(续)machunyan西北工业大学软件与微电子学院48SaAc.BecS .SBSaAcB.eB.dSS S.S .aAcBeaS a .AcBeASaA .cBeA.bA.AbAb .Bd .SaAcBe .bdeAAA.bbAAb .machunyan西北工业大学软件与微电子学院49上述文法的可归前缀有：？machunyan西北工业大学软件与微电子学院502. 构造识别活前缀的DFAo 基于闭包函数基于闭包函数CLOSURE(I)以及转移函数以及转移函数GO(I，x)

26、构造识别活前缀的构造识别活前缀的DFA;nCLOSURE(I)的定义nGO(I，x)的定义n构造识别活前缀的DFA注：由上述定义知，CLOSURE(I)是一个LR(0)项目集合。machunyan西北工业大学软件与微电子学院51步骤1：令 CLOSURE(I)=I；步骤2：若项目A.B CLOSURE(I), BVN ,则 CLOSURE(I) = CLOSURE(I) B.；步骤3：重复步骤2直至CLOSURE(I) 不增加新的项 目为止。n 拓广文法G的一个LR(0)项目集合I的闭包函数CLOSURE(I)的定义如下：2. 构造识别活前缀的DFA(续)machunyan西北工业大学软件与微

27、电子学院52o I是一个项目集，是一个项目集， x VNVT，状态转移函数状态转移函数GO(I，x)的定义如下：的定义如下： n GO(I，x)= CLOSURE(J)，其中：o J是I识别输入符号x后所到达的项目集， J= Ax. | A.x I 2. 构造识别活前缀的DFA(续)machunyan西北工业大学软件与微电子学院532. 构造识别活前缀的DFA(续)o基于闭包函数基于闭包函数CLOSURE(I)和转移函数和转移函数GO(I，x)构构造识别文法活前缀的造识别文法活前缀的DFA的算法如下：的算法如下：n令项目集CLOSURE(S .S )为DFA的初态；n输入字符集合：包括终结符、

28、非终结符；n设I是DFA中一个已存在的状态(项目集)，若存在A.xI，则对xVNVT ，o 计算GO(I，x)= CLOSURE(J)，将项目集 CLOSURE(J) 作为DFA的一个新状态加入DFA的状态集；1. 同时将转移函数GO(I，x)= CLOSURE(J)作为DFA的转换函数。machunyan西北工业大学软件与微电子学院54o重复重复2直至的直至的DFA的状态集中不产生新的状态的状态集中不产生新的状态(项项目集目集)为止；为止；o含有项目含有项目Uu. 的项目集的项目集,作为作为DFA的终态。的终态。2. 构造识别活前缀的DFA(续)machunyan西北工业大学软件与微电子学院

29、55 例：对拓广文法(0) SS(1) SaAcBe(2) Ab(3) AAb(4) Bd求出其对应的LR(0)项目集合的DFACLOSURE(S .S ) ?machunyan西北工业大学软件与微电子学院56SS .SS .aAcBe0S S .1aAS a .AcBeA .bA .Ab 2S aA .cBeA A .b 3bA b .4bcAAb .6S aAc.BeB.d 4B d. 7BSaAcB.e8eS aAcBe.9dmachunyan西北工业大学软件与微电子学院57求文法:SS S(S) S | 对应的LR(0)项目集合的DFAmachunyan西北工业大学软件与微电子学院58

30、3. LR(0)分析表的构造设状态i、j，若有GO(i，x)=j ，对于状态i中的项目A.x,若xVN,则置Gotoi，x=j;则置Actioni，x=Sj;若xVT,由识别活前缀的DFA构造LR(0)分析表的方法：machunyan西北工业大学软件与微电子学院59(2) 对于终态对于终态i中的项目中的项目A. ，若，若A 是是G中中第第k个产生式，则个产生式，则对所有输入符号对所有输入符号x VT(包括包括$), 均置均置Actioni,x=rk ;(3)若终态若终态i中含中含项目项目SS. 则置则置Actioni,$=acc ($表示输入串结束符表示输入串结束符);(4) 其它情况均置错。

31、其它情况均置错。3. LR(0)分析表的构造(续)machunyan西北工业大学软件与微电子学院60例1：文法A(A)| a 对应的LR(0)项目集合的DFAmachunyan西北工业大学软件与微电子学院61文法A(A)|a 对应的LR(0)分析表ActionGotoa（）$A012344S2S31accr2r2r2r2S2S3S4r1r1r1r14machunyan西北工业大学软件与微电子学院624. LR(0)分析算法(1) 将输入串的左边界($)进符号栈和初始状态0进状态栈；(2) 根据状态栈栈顶状态i和当前输入符号a查Action表进行如下工作： 移进:若Actioni，a=Sj ，当

32、前输入符号a进符号栈，并将输入符号所对应的新的状态j进状态栈，继续处理下一个输入符号；machunyan西北工业大学软件与微电子学院63 归约:若Actioni，a=rj ，按指定产生式进行归约，假设产生式右部的符号串长度为n，则 符号栈栈顶的n个符号为句柄，所以符号栈栈顶n个符号出栈，同时，状态栈栈顶的n个元素也出栈； 归约后的文法符号A(非终结符)进符号栈； 假设当前符号栈栈顶为j，若Gotoj，A=k，则将文法符号A所对应的新状态k进状态栈。4. LR(0)分析算法(续)machunyan西北工业大学软件与微电子学院64 接受:若动作表中对应“acc”，则分析成功； 出错:若动作表中对应

33、空白，则报告错误信息。(3) 重复以上(2)的工作直到接受或出错为止。考虑文法A(A)|a的输入串(a)LR(0)分析算法对输入串(a)的分析步骤如下：4. LR(0)分析算法(续)machunyan西北工业大学软件与微电子学院65步骤 状态栈S符号栈X动作输入符号10$S3(a)$203$(S3(a)$3033$(S2a)$40332$(ar2(Aa)$40334$(AS4)$603344$(A)r1(A(A)$machunyan西北工业大学软件与微电子学院667034$(AS4)$80344$(A)r1(A(A)$901$A接受$machunyan西北工业大学软件与微电子学院674. 项目

34、的分类项目分类的原则是根据圆点所在位置和圆点之后是终结符还是非终结符进行的。移进项目：圆点之后为终结符的项目， A.a, ,V*, aVT,它对应的状态为移进状态；例如SaA.cBe待约项目：圆点之后为非终结符的项目， A.B ， ,V*,BVN ,它对应的状态为待约状态；例如 SaAc.Bemachunyan西北工业大学软件与微电子学院68归约项目：圆点之后没有符号(圆点在最后)的项目，A. V*,它对应的状态为归约状态；例如：SaAcBe.接受项目：对于拓广文法GS,有项目SS.它是一个特殊的归约项目，称它为接受项目，它所对应的状态为接受状态。4. 项目的分类(续)machunyan西北工

35、业大学软件与微电子学院696. LR(0)文法的定义 项目集的相容性：在一个项目集(对应DFA的一个状态)中，若能满足下述条件，则称该项目集是相容的项目集。(1)移进项目和归约项目不并存，否则是移进-规约冲突；(2)多个归约项目不并存，否则称规约-规约冲突；2）LR(0)文法：若一个文法G的任一项目集中的所有项目都是相容的（即LR(0)分析表表项的元素至多只有一个）， 则称文法G为LR(0)文法。machunyan西北工业大学软件与微电子学院70第4章 自下而上的语法分析 4.1 自下而上的语法分析 4.2 LR分析概览 4.3 LR(0)项目的有穷自动机与LR(0)分析 4.5 SLR(1)

36、 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 语法分析器自动生成工具YACC作业machunyan西北工业大学软件与微电子学院714.5 SLR(1)分析算法问题的提出：通常的程序设计语言一般不能满足LR(0)文法的要求。例如：文法：SS S(S)S| 对应的LR(0)项目集合的DFA如下图：machunyan西北工业大学软件与微电子学院72machunyan西北工业大学软件与微电子学院73若为上述文法构造LR(0)分析表，则：状态状态 Action Goto（）$S0S2 , r2r2r211acc2S2 , r2r2r233S44S2 , r2r2r244r1r1r

37、1machunyan西北工业大学软件与微电子学院744.4 SLR(1)分析算法(续)o 从分析表可以发现：表中从分析表可以发现：表中Action0 ,(出现了出现了多重定义的元素，即冲突。多重定义的元素，即冲突。o 对于状态对于状态0，当输入当输入“（”时，既要进行归时，既要进行归约又要进行移进，因而不能做唯一选择，从约又要进行移进，因而不能做唯一选择，从而发生冲突。而发生冲突。machunyan西北工业大学软件与微电子学院75对LR(0)分析的构造算法进行改造，以避免分析表中分析动作的冲突。当分析表出现冲突动作时，观察下一个输入符号是什么，从而确定该采用什么动作。问题的解决o 先求先求Fo

38、llow(S)= ),$，对于状态对于状态2 2，如果要做归如果要做归约动作，这时约动作，这时S S之后的下一个输入符号可以时之后的下一个输入符号可以时）或或$ $。( (即文法中含有即文法中含有S S的句型中，的句型中，S S之后只之后只能是能是) )或或$ $，而不能含有其他输入符号，而不能含有其他输入符号) )o 对于移进项对于移进项S S.(S)S,.(S)S,它所期待的移进符号为它所期待的移进符号为( (，而不是其它符号。，而不是其它符号。o 所以可以这样处理：当下一个输入符号所以可以这样处理：当下一个输入符号( (时时，做移进动作，当下一个输入符号，做移进动作，当下一个输入符号)

39、)和和$ $时做归约动作。时做归约动作。machunyan西北工业大学软件与微电子学院764.4 SLR(1)分析算法(续)machunyan西北工业大学软件与微电子学院77这样，消除冲突的分析表为(SLR(1)分析表)：状态状态 Action Goto（）$S0S2r2r211acc2S2r2r233S44S2r2r244r1r1r1o 在在SLR(1)SLR(1)文法中，向右看一个符号，所以属于文法中，向右看一个符号，所以属于LR(1)LR(1)方法。而它仅在发生冲突时才向右看一个方法。而它仅在发生冲突时才向右看一个符号，为了与普通的符号，为了与普通的LR(1)LR(1)方法区别，将其称为

40、方法区别，将其称为简单的简单的LR(1)LR(1)方法方法- -SLR(1)SLR(1)方法。方法。o SLR(1)SLR(1)文法与文法与LR(0)LR(0)文法识别其活前缀项目集合文法识别其活前缀项目集合的的DFADFA是一样的，是一样的，区别在于它们构造分析表的规区别在于它们构造分析表的规则不一样。则不一样。o SLR(1)SLR(1)分析与分析与LR(0)LR(0)分析的算法步骤一致分析的算法步骤一致。machunyan西北工业大学软件与微电子学院784.4 SLR(1)分析算法(续)machunyan西北工业大学软件与微电子学院79SLR(1)分析表的构造任意文法GS的SLR(1)分

41、析表的构造规则如下：设状态j是状态i输入符号x后到达的状态,即： GO(i,x)=j 对于状态i中的项目A.x,若xVN,则置Gotoi,x=j;则置Actioni,x=Sj;若xVT,machunyan西北工业大学软件与微电子学院803.若S.i,则置Actioni,$=acc(S为开始符号)；4.其他情况均置出错。对于给定的文法G,若按上述方法所构造的分析表不含多重定义的元素(无冲突动作)。则称文法G为SLR(1)文法。2.对于状态i中的归约项目：A.i 若A为文法的第j个产生式，则对于任意输入符号a,aFollow(A),则置Actioni,a=rjmachunyan西北工业大学软件与微

42、电子学院81EnSLR(1)分析算法考虑以下基本算术表达式的扩充文法：EEEE+n识别其活前缀项目集合的DFA如下图所示：machunyan西北工业大学软件与微电子学院82machunyan西北工业大学软件与微电子学院83状态状态 Action Goto+n$E0S211S3acc2r2r23S44r1r1构造SLR(1)分析表如下：Follow(E)=$ Follow(E)=$,+machunyan西北工业大学软件与微电子学院84用SLR(1)分析算法对输入串n+n+n的分析步骤：步骤 状态栈S符号栈X动作输入符号10$S2n+n+n$202$nr2(En)+n+n$301$ES3+n+n$

43、4013$ E+S4n+n$40134$ E+nr1(EE+n)+n$601$ES3+n$machunyan西北工业大学软件与微电子学院857013$E+S4n$80134$E+nr1(EE+n)$901$E接受$machunyan西北工业大学软件与微电子学院86第4章 自下而上的语法分析 4.1 自下而上的语法分析 4.2 LR分析概览 4.3 LR(0)项目的有穷自动机与LR(0)分析 4.4 SLR(1) 分析 4.4 一般的LR(1) 4.6 LALR(1)分析 4.7 语法分析器自动生成工具YACC作业machunyan西北工业大学软件与微电子学院874.5 LR（1）分析算法o 问

44、题的提出：问题的提出：例如：有文法GS (0)SS (3)Saec (1)SaAd (4)Sbed (2)SbAc (4)Aemachunyan西北工业大学软件与微电子学院88Sb.Ac Sb.ed A.e3SabSa.Ad Sa.ec A.eAeSaA.dSae.c Ae.AeSbA.cSbe.d Ae.dccdSaAd.Saec.SbAc.Sbed.S.S S.aAdS.bAc S.aec S.bed024891011467S1: SS.1移进归约冲突Follow(A)=c,dFirst(d)=d相交移进归约冲突Follow(A)=c,dFirst(c)=c相交结论：冲突不能用SLR(1)

45、方法解决！4.5 LR（1）分析算法(续)machunyan西北工业大学软件与微电子学院894.5 LR（1）分析算法(续)o LR(1)项目：项目：在在LR(0)项目中放置一个向右项目中放置一个向右搜索符号搜索符号a，成为成为LR(1)项目：项目：A. ，ao LR(1)分析过程中的每个状态，就是包含若分析过程中的每个状态，就是包含若干干LR(1)项目的一个项目的一个LR(1)项目集；项目集；o 构造构造 LR(1)项目集合的项目集合的DFA的算法的算法与与LR(0)类似，也需求两个函数类似，也需求两个函数CLOSURE和和GO。步骤3：重复步骤2直至CLOSURE(I) 不增加新项目为止。

46、machunyan西北工业大学软件与微电子学院90步骤1：CLOSURE(I)=I；步骤2：若存在A.B，a CLOSURE(I), BVN , 则CLOSURE(I) = CLOSURE(I) B., b ， 其中 bFirst(a)设I是拓广文法G的一个LR(1)项目集，定义和构造I的闭包函数CLOSURE(I)如下：4.5 LR(1)分析算法(续)machunyan西北工业大学软件与微电子学院91I是一个LR(1)项目集， xVNVT，状态转移函数GO(I,x)定义如下： GO(I，x)= CLOSURE(J) 其中J是I识别输入符号x后所到达的项目集，后跟符号不变。 J=Ax.，a |

47、 A.x, a I基于闭包函数和转移函数构造文法G的LR(1)项目集的识别文法活前缀的DFA，算法如下：4.4 LR(1)分析算法(续)machunyan西北工业大学软件与微电子学院92令DFA的初态为项目集CLOSURE(S .S, $ )设I是一个DFA中的状态(已存在的项目集)，对xVNVT ，产生新的项目集CLOSURE(J) 作为DFA的一个新状态加入DFA的状态集中： GO(I,x)= CLOSURE(J) 同时将转移函数GO(I,x)= CLOSURE(J)作为DFA的转换函数。重复2)直至DFA中不产生新的(项目集)为止；含有项目Uu. (即圆点在最后的项目)的项目集，作为DF

48、A的终态；4.5 LR(1)分析算法(续)machunyan西北工业大学软件与微电子学院93构造文法A(A)|a 的 LR(1)项目集合的DFA ;首先扩展该文法： AA A(A) A a CLOSURE( A . A，$ ) ?machunyan西北工业大学软件与微电子学院94A.A , $A.(A), $A.a, $0AA. , $1AAa. , $3aA(.A) , $A.(A), )A.a , )2(A(A.), $4A(A(.A) , )A.(A), )A.a , )4aAa. , )6a)A(A)., $7(A(A.), )8A)A(A)., )9machunyan西北工业大学软件

49、与微电子学院95LR(1)分析表构造规则：对于文法GS，其LR(1)分析表的构造规则为：1. 对于A.x, a状态i,且GO(i，x)=j.若xVT,则置Actioni，x=Sj 若xVN ,则置Gotoi，x=j2. 对于A. , a状态i，若A是文法的第j个产生式，则置 Actioni，a=rj3.对于S.，$状态i，则actioni，$=acc4.其它情况置错。machunyan西北工业大学软件与微电子学院96根据文法A(A)|a 的 LR(1)项目集合的DFA ，构造其对应的LR(1)分析表:给产生式编号：(0) AA(1) A(A)(2) A amachunyan西北工业大学软件与微

50、电子学院97A.A , $A.(A), $A.a, $0AA. , $1AAa. , $3aA(.A) , $A.(A), )A.a , )2(A(A.), $4A(A(.A) , )A.(A), )A.a , )4aAa. , )6a)A(A)., $7(A(A.), )8A)A(A)., )9machunyan西北工业大学软件与微电子学院98状态状态ActionGoto()a$A0S2S311acc2S4S643r24S74S4S686r2machunyan西北工业大学软件与微电子学院99用LR(1)分析算法对输入串(a)的分析步骤：步骤 状态栈S符号栈X动作输入符号10$S2(a)$20

51、2$(S6a)$3026$(ar2(Aa)$4024$(AS7)$40247$(A)r1(A(A)$601$Aacc$machunyan西北工业大学软件与微电子学院100(0)EE (1)E(L) (2)E a (3)LL,E (4)LE构造下面文法的LR(1)分析表：首先构造其LR(1)项目的DFAmachunyan西北工业大学软件与微电子学院101(0)EE (1)E(L) (2)E a (3)LL,E (4)LEE .E , $E .(L) , $E.a , $ 0EE E.,$1(2E a. , $ 3aLE(aE (.L) , $machunyan西北工业大学软件与微电子学院102E

52、 (.L) , $L .E ，)L .L,E , )E .(L) , )E. a , )L .L,E ，, L .E ，,E .(L) ， ,E. a ，, 2(0)EE (1)E(L) (2)E a (3)LL,E (4)LEE (.L) ， $L .L,E ， )/,L .E ，)/,E .(L)， )/,E. a ，)/,2machunyan西北工业大学软件与微电子学院103(0)EE (1)E(L) (2)E a (3)LL,E (4)LEE .E , $E .(L) , $E.a , $ 0EE E. , $1(E (.L) , $L .L,E , )/,L .E ,)/,E .(L

53、) , )/,E. a , )/, 2E a . , $ 3aLE (L.) , $L L.,E , )/, 4EL E.,)/, 4(E (.L) , )/,L .L,E , )/,L .E ,)/,E .(L) , )/,E. a , )/, 6aE a . , )/, 7)E (L)., $ 8,L L, .E , )/,E .(L) , )/,E. a , )/, 9LE (L.) , )/,L L.,E , )/, 10EL L, E . , )/, 11E (L)., )/, 12)E(a(a,machunyan西北工业大学软件与微电子学院104状态状态ActionGotoa（），

54、$EL0S3S211acc2S7S6443r24S8S94r4r46S7S64107r2r28r19S7S6 1110S12S911r3r312r1r1(0)EE (1)E(L) (2)E a (3)LL,E (4)LE基于DFA构造的LR(1)分析表machunyan西北工业大学软件与微电子学院105第4章 自下而上的语法分析 4.1 自下而上的语法分析 4.2 LR分析概览 4.3 LR(0)项目的有穷自动机与LR(0)分析 4.4 SLR(1) 分析 4.5 一般的LR(1) 4.6 LALR(1)分析 4.7 语法分析器自动生成工具YACC作业machunyan西北工业大学软件与微电子

55、学院1064.6 LALR（1）分析算法o LR(1)分析比分析比SLR(1)分析的能力有明显的提高，但是分析的能力有明显的提高，但是LR(1)也有缺点：分析表状态数过大，使分析的效率降也有缺点：分析表状态数过大，使分析的效率降低。为解决二者之间的能力与效率之间的矛盾，目前最低。为解决二者之间的能力与效率之间的矛盾，目前最流行的流行的LALR(1)分析是最佳方案。分析是最佳方案。n LALR(1)分析(Lookahead-LR)的基本思想是将LR(1)项目集中的同心集合并，将其压缩为较小的DFA，若压缩过程并未带来新的冲突，则分析表可大大地简化(状态数与SLR(1)，LR(0)的DFA相同)。

56、machunyan西北工业大学软件与微电子学院1074.6 LALR（1）分析算法(续)o LALR(1)项目集（状态）通过同心集合并构造项目集（状态）通过同心集合并构造: n 同心集：LR(1)的两个项目集的LR(0)项目全部相同，则称两个LR(1)项目集具有相同的心，具有相同心的项目集称为同心集。 n 同心集合并：o 相同的心(LR(0)项目)不变；o 合并后项目集的搜索符等于合并前LR(1)项目搜索符的并集。machunyan西北工业大学软件与微电子学院108A.A , $A.(A), $A.a, $0AA. , $1AAa. , $3aA(.A) , $A.(A), )A.a , )2

57、(A(A.), $4A(A(.A) , )A.(A), )A.a , )4aAa. , )6a)A(A)., $7(A(A.), )8A)A(A)., )9machunyan西北工业大学软件与微电子学院109合并上述DFA中的同心集：A(.A) , $A.(A), )A.a , )2A(.A) , )A.(A), )A.a , )4A(.A) , $/)A.(A), )A.a , )2/4machunyan西北工业大学软件与微电子学院110Aa. , $3Aa. , )6Aa. , $/)3/6A(A.), $4A(A.), )8A(A.), $/)4/8machunyan西北工业大学软件与微

58、电子学院111A(A)., $7A(A)., )9转换仅与项目集的LR(0)项目及文法符号X有关，与搜索符无关。所以，引入合并后的项目集后，由同心集导出的弧，改由合并后的项目集导出，弧上标记不变。A(A)., $/)7/9machunyan西北工业大学软件与微电子学院112A.A , $A.(A), $A.a, $0AA. , $1Aa(A)A(.A) , $/)A.(A), )A.a , )2/4Aa. , $/)3/6aA(A.), $/)4/8A(A)., $/)7/9LALR(1)分析表构造与LR(1)构造方法相同：LALR(1)项目集的DFAmachunyan西北工业大学软件与微电子学院113状态ActionGoto()a$A0S2/4S3/611acc2/4S2/4S3/64/83/6r2r24/8S7/97/9r1r1012347machunyan西北工业大学软件与微电子学院114用LALR(1)分析算法对输入串(a)的分析步骤：步骤 状态栈S