编译原理4语法分析.ppt

第四章 语法分析 4.1语法分析程序的功能 语法分析：逐一分析词法分析所得的属性字，检查其中的 语法错误，如果没有发现语法错误， 则给出正确的语法结 构。 语法分析常用方法： 1、自顶向下分析方法，2、自底向上分析方法。 所谓的自顶向下分析法就是从文法的开始符号出发，根据 文法规则正向推导出给定句子的方法；或者说，从树根开 始，往下构造语法树，直到建立每个树叶的分析方法。 自底向上分析方法是从给定的输入串开始，根据文法规则 逐步进行归约，直至归约到文法的开始符号；或者说，从 语法树的末端开始，步步向上归约，直至根结点的分析方 法。 4.2自顶向下分析法 4.2.1非确定的自顶向下分析法的思想 对任何输入串w试图用一切可能的办法，从文法的开始符号出发 ，自上向下地为它建立一棵语法树。或者说，为输入串寻找一个 最左推导。如果试探成功，则w为相应文法的一个句子，否则w就 不是文法的句子。这种分析过程本质上是一种穷举试探过程，是 反复使用不同规则，谋求匹配输入串的过程。 例：设有文法GS SaAb,A de|d,判断adb是否为该文法的句 子。 自顶向下分析的难点：对于形如:U x1|x2|xn 的规则,可能需要 对所有的规则都要试探，效率很低。故常使用确定的自顶向下分 析法，但确定的自顶向下分析法对文法有一定的限制，既是要求 文法无左递归和无回溯。 4.2.2文法的左递归和回溯的消除 1.左递归的消除 (1)引进一个新的非终结符，把含左递归的规则改写为右递归 一般地，对于含有左递归规则的文法GA: A A1|A 2|A m|1| 2| n 消除左递归规则后的文法为： A 1A| 2A| nA A 1A| 2A| mA| 例：E E+T|E-T|T T TF|T/F|F F (E)|i E TE E +TE|-TE| T FT T *FT|/FT| F (E)|i (2)扩充的BNF表示法 1）专用符号：扩充的BNF又引进了三对专用符号。 花括号：表示符号串可以重复出现任意次。 使用可以消除规则的左递归现象的出现。 例：N ND|D D 0|1|2|9 用扩充的BNF可以表示为： N DD D 0|1|2|9 方括号：表示符号串可有可无 圆括号（）：（）表示提因子。 例：A ax|ay|aw 改写为：A a(x|y|w)。 2）扩充的BNF表示法的用途 例：设有文法GE： E T|E+T T F|T*F F i|(E) 用扩充的BNF法可改写为： E T+T T FF F i|(E) 扩充的BNF表示法最大特点就是消除了文法的左递归问题。 E T+T|-T T FF|/F F i|(E) 例：设有文法A Ac|Aad|bd|e，用扩充的BNF表示法对其改写 A （bd|e） c|ad 2.回溯的消除 引起回溯的原因：在文法中某个非终结符A有多个 候选式，遇到用A去匹配当前输入符号时，无法确 定选用唯一的一个候选式，而只能逐一进行试探 ，从而引起回溯。 具体表现为两种情况： 第一种情况是相同左部的规则，其右部左端第一 个符号相同。 SaAb,A de|d,对于adb 第二种情况是相同左部的规则，其中某一右部能 推出。 ABx,B x| ,对于x 常用的符号集有三种：首符号集：FIRST；向前看集： FOLLOW；可选集：SELECT。 (1)设是文法G的任一符号串，定义符号串的首符号集为： FIRST()=a| a，a Vt 若 ，则规定 FIRST()，既FIRST()是从可以推导出的 所有首终结符或可能的。 (2)设文法G的开始符号为S，对于G的任何非终结符A，定义非 终结符A的向前看集FOLLOW(A)=a|S Aa，aVt 若有S A ，则规定$ FOLLOW(A) ，换句话说 FOLLOW(A) 是文法的所有句型中紧接在A之后出现的终结符 或$，$作为输入串的结束符。 (3)设有文法GS，并有规则A ，AVN, V*,则该规则的 可选集为： SELECT(A )= FIRST() 若 FIRST() FOLLOW(A)若 一个上下文无关文法G是LL(1)文法，并且仅当对G中每个非终 结符A的任何两个不同的规则A |，满足SELECT(A ) SELECT(A )= ，其中，中至多只有一个能推出 串。 例：判断下列文法是否为LL(1)文法 1.SaAb,A de|d 2.A aB|d,B bBA| 3. SaAB，A bB|dA| ，B a|e 4.2.3某些非LL(1)文法到LL(1)文法的改写 若文法中含有左递归或含有公共左因子，则该文法不是LL(1)文 法，因此对于某些非LL(1)文法来说，可以通过消除左递归 和反复提取公共左因子对文法进行等价变换，将其改造为 LL(1)文法。 提取公共因子： 当文法中含有形如A1| 2| n的规则，可将它改写成 AA A 1| 2| n 若在1，2，n中仍含有公共左因子，这时可再次提取，这 样反复进行提取，直到引进新的非终结符的有关规则再无公共 左因子为止。 例：将下例文法改写为LL(1)文法，并验证之。 1.SaAb,A de|d 2. Sad|Ae,A aS|bA 对于文法S Ae|Bd，A aAe|b，B aBd|b 4.2.4递归下降分析法 基本思想：对文法中的每个非终结符编写一个函数（或子程序） ，每个函数（或子程序）的功能是识别由该非终结符所表示的语 法成分。由于描述语言的文法常常是递归定义的，因此相应的这 组函数（或子程序）必然以相互递归的方式进行调用，所以将此 种分析法称为递归下降分析法。 构造递归下降分析程序时，每个函数名是相应的非终结符，函数 体则是根据规则右部符号串的结构编写。 1)当遇到终结符a时，则编写语句 if (当前读来的输入符号=a) 读下一个输入符号。 2)当遇到非终结符A时，则编写语句调用A()。 3)当遇到A 规则时，则编写语句 if (当前读来的输入符号FOLLOW(A) error()。 4)当某个非终结符的规则有多个候选式时，按LL(1)文法的条件 能唯一地选择一个候选式进行推导。 例：设有文法GS: S a|(T) T T,S|S 试构造一个识别该文法句子的递归下降分析程序。 设函数scaner()的功能是读进源程序的下一个单词符号并把它 放在全局变量sym中；函数error()是出错处理程序。 4.2.5 LL（1）分析方法（预测分析法） LL（1）分析方法也是一种自顶向下的分析技术。第一个L表示 采用从左到右扫描程序，第二个L表明采用最左推导，1表示分 析时每一步只需向前看一个符号即可决定所选用的规则，且这 种选择是准确无误的。采用这种方法进行语法分析要求描述语 言的文法是LL（1）文法。 预测分析器由一张预测分析表（也称LL（1）分析表 ）、一个 先进后出的分析栈和总控程序三部分组成。 a1 a2 a3 ai am $ 总控程序 分析表 x $ 栈顶 由具体的文法 规则构造 Sk Tj 预测分析表是一个MA，a形式的矩阵，其中A为非终结符，a 是终结符或$，分析表元素MA，a中的内容为一条关于A的规 则，表明当A面临输入符号a时，当前推导所应采用的候选式， 当元素的内容为出错标识时，则表明A不应该面临输入符号a。 预测分析器的总控程序在任何时候都是根据栈顶符号和当前符 号a来决定分析器的动作。 分析器工作流程可简单表示为： 1.初始化。分析开始时，首先将栈底符号$及文法的开始符号S推 入分析栈，并对各指示器置初值，此时分析栈与输入串有如下 格局： 之后反复执行下面的第二步。 2.设在分析的某一时刻，分析栈和余留的输入串处于如下的格 局： $Sa1 a2 an $ $ X1 X2 Xm-1 Xmai ai+1 an $ 时可视分析栈顶的文法符号Xm的不同情况，分别作如下处理： （1）若XmVT$，且Xm= ai，则表明栈顶符号已与当前正 扫视的输入符号（包括句尾符号$在内）相匹配，此时应将Xm从栈 中退出，并将输入串指示器向前推进一个位置，否则进行语法错误 处理； （2）若XmVn，则以符号对（ Xm，ai ）查分析表，设元素A Xm, ai为产生式Xm Y1 Y2 Yk，则将Xm从栈中退出，并将Y1 Y2 Yk按反序推入栈中，从而产生如下格局： 但若AXm, ai为“出错”，则进行语法错误处理。 $ X1X2 Xm-1 Yk Yk-1 Y1ai ai+1 an $ （3）若Xm=ai =$（即分析栈将被拆空） ，则表明输入串已完 全得到匹配，此时可宣告分析成功而结束工作。 $和文法的开始符号进S栈 第一个输入符号读进a S栈顶符号上托出去放X中 x=a?xVT? x=a? x=$? 查MX,a=x y1y2yn 将y1y2yn逆序 放入S栈中，若 右部符号串为 ,则不进栈 将下一个输 入符号读入a 出错 出错 YN stop Y Y Y N N N N 构造预测分析表的算法 (1)计算文法G的每一个非终结符的FIRST集和FOLLOW集。 1）对每一文法符号X(VNVT),计算FIRST(X): a.若X VT,则FIRST(X) =X; b.若XVN,且有规则Xa,a VT,则a FIRST(X); c.若XVN,且有规则X, FIRST(X); d.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元 素都加到FIRST(X)中；若有规则Xy1y2yn,对于任意的i(1i n),当y1y2yi-1都是非终结符，且y1y2yi-1 时，则将FIRST(yi) 中的所有非元素都加到FIRST(X)中,特别是，若y1y2yn ， 则 FIRST(X)。 e.反复使用a-d,直到FIRST集不再增大为止。 2）对每一文法符号AVN,计算FOLLOW(A): a.对文法的开始符号S，则将$加到FOLLOW(S)中； b.若A B是一条规则，则把FIRST()中的非元素加到 FOLLOW(B)中; c.若A B 或A B是一条规则且 ，则把 FOLLOW(A) 加到FOLLOW(B)中; d.反复使用b-c直到每个非终结符的FOLLOW集不再增大为止 。 (2)对文法的每个规则A ，若a FIRST(),则置MA,a= A 。 (3)若 FIRST(),则对任何b FOLLOW(A)，则MA,b= A 。 (4)把分析表中无定义的元素标上出错标识error(表中用空白表 示) P67 例4.10 4.3自下向上分析法的一般原理 自下向上分析法是按照移进归约法的原理建立起来的一种 语法分析方法，这种分析法的基本思想是：用一个寄存文法 符号的先进后出的栈，将输入符号一个一个地按从左到右扫 描顺序移入栈中，边移入边分析，当栈顶符号串形成某条规 则右部时就进行一次归约，即用该规则左部非终结符替换相 应规则右部符号串，我们把栈顶被归约的这一符号串称为可 归约串。重复这一过程直到整个输入串分析完毕。最终若栈 中剩下句子界符“$”和文法的开始符号，则所分析的输入符号 串是文法的正确句子，否则，就不是文法正确的句子，报告 错误。 例：设有文法GA: AaBcDe,B b,B Bb,D d 步骤骤符号栈栈输输入串 动动作 0$abbcde$ a进栈进栈 1$abbcde$ b进栈进栈 2$abbcde$ 用B b归约归约 3$aBbcde$ b进栈进栈 4$aBbcde$ 用B Bb归约归约 5$aBcde$ c进栈进栈 6$aBcde$ d进栈进栈 7$aBcde$ 用D d归约归约 8$aBcDe$ e进栈进栈 9$aBcDe$ 用AaBcDe归约归约 10$A$ 分析成功 实现自下而上分析法的关键问题是如何精确定义可归约串，以及 怎样识别可归约串 4.4算符优先分析法 4.4.1方法概述 所谓的算符优先分析法就是依照算术表达式的四则运算过程而 设计的一种语法分析方法，这种方法首先要规定运算符之间（ 确切的说是终结符之间）的优先关系和结合性质，然后借助这 种关系，比较相邻运算符的优先级来确定句型的可归约串，并 进行归约。 例：E E+E|E*E|(E)|i对于句子i+i*i有两种不同的规范归约。 第一种： i+i*i E+i*i E+E*i E+E*E E+E E 第二种： i+i*i E+i*i E+E*i E*i E*E E 问题原因：没有定义+和*的优先关系，在第一种规范归约中是 假定*优先于+，所以不能立即把E+E归约为E,而在第二种归约中 是假定+优先于*，因此必须把E+E归约为E。可见在归约过程中 起决定因素的是相邻两个终结符号的优先关系。 任意两个相邻终结符号a和b之间的优先关系有三种： ab a的优先级大于b 优先关系与出现的左右次序有关： a a 一个文法的终结符号之间的优先关系可用一个矩阵来表示，矩 阵的每一行每一列都是文法的终结符，矩阵元素是两个终结符 之间可能的优先关系。算符优先分析法并不是对所有的文法都 适合，他对文法有一定的要求，即要求文法是算符优先文法。 4.4.2算符优先文法的定义 1.算符文法的定义 设有文法G，若G中没有形如U VW的规则，其中V、 W为非终结符，则称G为算符文法，也称OG文法。也就是说 在算符文法中任何一个规则右部都不存在两个非终结符相邻 的情况。 算符文法有两个重要性质： 1）在算符文法中任何句型都不含有两个相邻的非终结符。 2）若Ab或bA出现在算符文法的句型中，其中AVN,b VT, 则中任何含有b的短语必含有A. 1）a b当且仅当G中含有形如P ab或P aQb的规则 2）a b当且仅当G中含有形如P Rb的规则,且R a 或R aQ。 3.算符优先文法的定义 设有一个不含规则的算符文法G,如果任意两个终结符号对(a,b) 在 、 三种关系中只有一种关系成立，则称G是算符优 先文法，也称OPG文法。 例： E E+E|E*E|(E)|i,判断是否为算符优先文法。 2.定义任意两个终结符号之间的优先关系 设G是一个算符文法，a和b是任意两个终结符，P、Q、R是非 终结符，算符优先关系、 定义如下： 4.4.3算符优先关系表的构造 首先对文法每个非终结符A定义两个集合： FIRSTVT(A)=b|A b或A Bb,bVT,B VN LASTVT(A)=a| A a或A aB,aVT,B VN 构造文法G的优先关系表算法如下： 1）为每个非终结符A计算FIRSTVT(A)和LASTVT(A)。 2）执行程序 for (每个产生式Ax1x2xn) for(i=1;i xi+1; 3)对FIRSTVT(S )中的所有b置$ $；置$ $，S为文法的开始符号 例：设有文法：GE E E+T|T T TF|F F (E)|i 4.4.4算符优先分析算法的设计 算术优先分析法并不是一种规范归约的分析法，它不是用句柄 来刻画可归约串，而是用最左素短语来刻画可归约串。 1.最左素短语 所谓句型的素短语是指这样一种短语，它至少包含一个终结符 ，并且除自身之外，不再包含其他的素短语。句型最左边的素 短语称为最左素短语。 如上例对句型T+T*F+i求其素短语和最左素短语。 2.识别句型最左素短语的方法 由算符文法的性质可知，算符优先文法的任何句型都没有相邻 的两个非终结符，其句型总可以表示成$N1a1N2a2NnanNn+1$ ，其中Ni为非终结符或空，ai为终结符（1i n ） 对算符优先文法有如下定理： 一个算符优先文法G的任何句型的最左素短语是满足下列条 件的最左子串NiaiNi+1ai+1ajNj+1 ai-1 aj+1 具体方法是：从左到右扫描句型中的各个符号，且在扫描过 程中，依次查看两相继终结符号间的优先关系，直至找出满 足关系aj aj+1的终结符aj为止，记下aj的位置，再从aj开始向 左扫描，直至找到满足关系ai-1 ，则表示 已找到最左素短语的尾，再从栈顶开始，按优先关系在栈内向 前寻找最左素短语的头，然后分析器将归约最左素短语，如果 出现两个终结符号之间不存在优先关系，则表示存在语法错误 ，分析器调用出错处理程序。 算法：设K为栈的使用深度，a用来存放当前输入符号，j是栈的 查找指针，Q是工作单元，则算法流程图如下： 栈置初值K1,SK$ jK SK是终结符或$？ Sj a？ jK-1 Sj+1SK是最左素短语，K j+1,SK N 当前输入符号读入a 结束 Y N N Y Y Y Q Sj,j j-1 K=2且a=$？ N Sj是终结符或$？ Sj b则令f(a)g(b) 我们把f和g分别称为栈内优先函数和栈外优先函数。这样a和b 之间的优先关系可以由比较f(a)和g(b)的大小来决定。 2.优先函数的构造方法 方法一：逐次加1法 1)确定初值，对所有的终结符(包括$)a，令f(a)=g(a)=0(可为其 它任意正数) 2)对所有终结符a和b 如果ab，而f(a)g(b)，则令f(a)=g(b)+1 如果a b = 方法二：Bell有向图法 1）对每个终结符a(包括$)，令其对应两个符号fa和ga，画一张 以所有符号fa和ga为结点的方向图，若ab或a b，就要画一 条从fa到gb的方向弧；若ab或a b，就要画一条从gb到fa的 方向弧。 2）对每个结点都赋予一个数，此数等于从该点出发所能到达的 结点（包括该结点自身在内）的个数，赋给结点fa的数等于fa的 值，赋给结点gb的数等于gb的值。 3）对构造出的优先函数f和g进行检查，看他们同原先的优先关 系表是否矛盾，若没有矛盾，则f和g既为所求优先函数，否则 不存在优先函数。 4.5 LR分析方法 所谓LR（K）方法：是指从左到右扫描和自底向上的语法分析方 法。L是指从左到右扫描输入符号串，R是指构造最右推导的逆过 程，K指最多向前看K个符号就可惟一确定是归约还是移进。 LR（K）理论证明：1)每个LR（K）文法都是无二义性文法2)一 个由LR（K）文法产生的语言也可由LR（1）文法产生。而且通 常的程序设计语言一般都能由LR（1）文法产生，因此对程序设 计语言的编译，我们仅需要考虑K1的情况即可。 4.5.1 LR分析器的原理和过程 LR分析法确定句柄的基本思想：在规范归约分析过程中，根据分 析栈中记录的已移进和归约的整个符号串（即历史）和使用的规 则推测未来可能遇到的输入符号（即展望），以及现实读到的输 入符号这三方面的信息来确定分析栈栈顶的符号串是否构成句柄 。 一个LR分析器的结构示意图如下： a1 a2 a3 ai an $ 分析表 总控程序 输入串 分析器 x1S1 $S0 xmSm 栈顶 分析栈 分析栈用来存放分析过程中的历史和展望信息。LR分析法将历 史和展望信息抽象成状态，并放在分析栈中，这就是说分析栈中 的每个状态概括了从分析开始到某一归约阶段的整个分析历史和 对未来进行的展望。 SmT + S1E S0$ LR分析表是LR分析法的核心，一张LR分析表由分析动作表（ ACTION）和状态转换表（GOTO）组成。 分析动作表 输输入符号 状态态 a1a2at S0ActionS0,a1ActionS0,a2ActionS0,at S1ActionS1,a1ActionS1,a2ActionS1,at SnActionSn,a1ActionSn,a2ActionSn,at 分析动作表元素ACTIONSi,a规定了当状态Si面临符号a（a为 文法的全部终结符和句子界符$）时应当执行的动作，有四种 可能的动作： 1）移进：把状态Sj=ACTIONSi,a和输入符号a移入分析栈。 2）归约：当栈顶符号串形成句柄，且文法中有A 的规则 ，其中| |=,则归约动作是从分析栈栈顶去掉个文法符号和 个状态，并把归约符A和GOTO Si- ,A= Sj移入分析栈。 3）接受（acc）:表示分析成功。此时，分析栈中只剩下文法开 始符号S和当前读到的输入符号$，即输入符号串已经结束。 4）报错：表示输入串含有错误，此时出现栈顶的某一状态遇到 了不该遇到的输入符号。 文法符号 状态态 x1x2xe S0GotoS0,x1GotoS0,x2GotoS0,xe S1GotoS1,x1GotoS0,x2GotoS1,xe SnGotoSn,x1GotoS0,x2GotoSn,xe 动作转换表 状态转换表GotoSi,x规定了当状态Si遇到文法符号x（x为文法的 全部符号）时应转移到的下一个状态。 为了节省存储空间，通常把两个表重叠，即把当前状态下面临终 结符的下一个状态与分析动作表的移进动作用数组元素表示。 状态态ACTION ab，$ S0SS S1acc S2Sr2 S3r3r3 S4r4r4 S5SS S6r1 状态态ACTIONGOTO ab，$LE S0S3S412 S1acc S2S5r2 S3r3r3 S4r4r4 S5S3S462 S6r1 总控程序也称为驱动程序，对所有的LR分析器总控程序是相同 的，其过程如下： 1.分析开始时，首先将初始状态S0及句子界符$推入分析栈。 2.设在分析的某一步，分析栈和余留输入符号串处于如下格局： 则用当前栈顶的状态Sm及正扫视的输入符号ai组成的符号对（ Sm， ai ）去查分析动作表，并根据分析表元素ACTIONSm， ai 的 指示采取相应的分析动作，每一分析表元素所指示的仅能是下 列动作之一： S0 S1 S2Sm $ X1 X2 Xm ai ai+1an$ 1）若ACTIONSm， ai =“移进”，则表明句柄尚未在栈顶部形 成，正期待继续移进输入符号以形成句柄，故将当前输入 符号ai推入栈中，即 然后，以符号对（ Sm， ai ）去查状态转移表，设相应的表元 素GOTOSm， ai = Sm+1，再将此新的状态Sm+1（即要转移到 的下一个状态）推入栈中，则有如下格局： S0 S1 S2Sm $ X1 X2 Xmai ai+1an$ S0 S1 S2Sm Sm+1 $ X1 X2 Xmai ai+1an$ 2）若ACTIONSm， ai =rj其中rj意指按文法的第j个产生式A Xm- r+1Xm-r+2 Xm进行规约。这表明栈顶的符号串Xm-r+1Xm-r+2 Xm已是 当前的句型的句柄，按第j个产生式进行规约，也就是将分析栈 从顶向下的r个符号和r个状态退出，然后将文法符号A进栈， 此时分析栈格局为 然后再以（ Sm-r， A）去查状态转移表，设GOTOSm-r， A = Sk，再 将此新的状态推入栈中，则有如下格局： S0 S1 S2Sm-r $ X1 X2 Xm-rA aiai+1an$ S0 S1 S2Sm-r Sk $ X1 X2 Xm-rA aiai+1an$ 3）若ACTIONSm， ai =“接受”，则表明当前的输入串已 被成功地分析完毕，应终止分析工作。 4）若ACTIONSm， ai =“ERROR”，则表明当前的输入 串中有语法错误，应该调用出错处理程序进行处理。 3.重复步骤2的工作，直到在分析的某一步，栈顶出现“接 受”状态为止。此时，分析栈的最终格局应为 其中Z为文法的开始符号， Sz为使ACTIONSz，$=“接受 ”的唯一状态。 S0 Sz $ Z $ 用稍微程序化的写法可描述为： 初始化(初始状态S0在分析栈栈顶，输入串的第一个符号读入a)； while(ACTIONS,a!=acc) if(ACTIONS,a=Si) 将状态Si和输入符号a进栈； 将下一个输入符号读入a; else if(ACTIONS,a=rj) 用第j条规则A 归约； 将| |个状态和| |个输入符号退栈： 当前栈顶状态为S,将A和GOTOS， A = S进栈； else if(ACTIONS,a=ERROR) error(); 例：设有文法 0.S S 1.S A 2.S B 3.A aAb 4.A c 5.B aBb 6.B d 状态态ACTIONGOTO abcd$SAB 0S4S5S6123 1acc 2r1r1r1r1r1 3r2r2r2r2r2 4S4S5S679 5r4r4r4r4r4 6r6r6r6r6r6 7S8 8r3r3r3r3r3 9S10 10r5r5r5r5r5 对aacbb$进行分析 4.5.2 LR（0）分析法 LR(0)根据当前分析栈顶状态确定应完成何种分析动作。 LR分析器的关键部分是分析表的构造。构造LR分析表的的基 本思想是从给定的上下文无关文法直接构造识别文法所有规范 句型活前缀的DFA，然后将DFA转换成一张LR分析表。 一、几个基本概念 1.文法规范句型的活前缀 1）字符串的前缀是指字符串的任意首部。例：字符串abc的前 缀有、a、ab、abc 2）规范句型的活前缀是指规范句型的前缀，这种前缀不包含句 柄右边的任何符号。若是含句柄的活前缀，并且每个句柄都是 的后端，则称是可归前缀或可规范前缀。 例：设有文法GS SS S CbBA A Aab A ab B c B Db C a D a 对于句子ababab有规范推导： S S CbBA CbBab CbDbab Cbabab ababab 规规范句型活前缀缀可归归前缀缀句柄 ababab 、a aa Cbabab 、C、Cb、Cba Cbaa CbDbab 、C、Cb、CbD、CbDb CbDbDb CbBab 、C、Cb、CbB、CbBa、 CbBab CbBabab CbBA 、C、Cb、CbB、 CbBA CbBACbBA 2.LR（0）项目 活前缀与句柄之间的关系有三种： 1）活前缀中已含有句柄的全部符号，表明此时某一规则 A的右部符号串已经出现在栈顶，其相应的分析 动作是用此规则规归约。 2）活前缀只含有句柄的一部分符号，此时意味着形如 A12规则的右部子串1已经出现在栈顶，正期待 着从剩余的输入串中进行归约得到2。 3）活前缀全然不含有句柄的任何符号，此时意味着期望 从剩余的输入串中能看到有某一规则A的右部所 推出的符号串。 为了刻画在分析过程中，文法的一个规则右部符号串已有 多大一部分被识别，我们可在文法中每个规则右部适当 位置加上一个圆点来表示。针对上面三种情况，标有圆 点的规则分别为： A A1 2 A 我们把文法G中右部标有圆点的规则称为G的一个项目。对 于空规则A仅有项目A。 一个LR（0）项目指明了对文法规范句型活前缀的不同识 别状态，文法G的全部LR（0）项目是构造识别文法所 有规范句型活前缀的DFA的基础。 由于不同的LR（0）项目反映了在分析过程中栈顶的不同情况 ，因此根据圆点的位置和圆点后是终结符还是非终结符，将 一个文法全部LR（0）项目进行分类： 1）规约项目，形如A，其中（VT VN ）*，既圆点 在最右端的项目，他表示一个规则的右部已分析完，句柄已 形成，应该按此规则进行归约。 2）移进项目，形如Aa，其中， （VT VN ）* ，a VT ，既圆点后为终结符的项目，他表示期待从输入串 中移进一个符号，以待形成句柄。 3）待约项目，形如AB，其中， （VT VN ）* ，B VN ，既圆点后为非终结符的项目，他表示期待从剩余 的输入串中进行归约而得到B，然后才能继续分析A的右部。 4）接受项目，形如SS，其中S为文法的开始符号，既文法 开始符号的归约项目。 S为左部的规则仅有一个，他是归约 项目的特殊情况，他表示整个句子已经分析完毕，可以接受 。 3.项目集： 构成识别文法规范句型活前缀的DFA的每一个状态是由若干个 LR（0）项目所组成的集合，称为LR（0）项目集。 4.项目集的相容性 定义：满足下列两个条件的项目集称为相容的项目集： ）无移进项目和归约项目并存 对于项目集： Aa ，B 对于栈顶元素，我 们无法确定是进行移进还是归约。 )无多个归约项目并存 对于项目集： A ，B 对于栈顶元素，我 们无法确定是把它归约到A还是B。 二、构造识别文法所有规范句型活前缀的DFA的方法 可以利用闭包函数（CLOSURE）来求DFA一个状态的项目集。 为了使“接受”项目唯一，我们可对文法G进行拓广。假定文法G的 开始符号为S，在文法G中引入一个新的开始符号S，并引进 规则S，S,从而得到文法G的拓广文法G，。 1）定义闭包函数 设I是拓广文法G，的一个LR（0）项目集，定义和构造I的闭包 CLOSURE（I）如下： I中的任何一个项目都属于CLOSURE（I） 若AB属于CLOSURE（I），则每一形如Br的项目也 属于CLOSURE（I） 重复直到CLOSURE（I）不在增大为止。 例：设有文法GS： 0、SS1、SA2、SB3、AaAb 4、Ac5、BaBa6、Bd 求SS的闭包函数。 2）定义状态转移函数GO 设I是拓广文法G，的一个LR（0）项目集，X为一文法符号， 定义状态转移函数GO（I，X）如下： GO（ I，X ）= CLOSURE（J） J=AX| AXI 3）构造识别文法规范句型活前缀的DFA的方法 求CLOSURE（S，S），得到初态项目集。 对初态项目集或其他已构造的项目集，应用转移函数GO（I ，X）求出新的项目集（后继状态）。 重复直到不再出现新的项目集（新状态）为止。 转移函数GO建立状态之间的连接关系。 构成识别一个文法活前缀的DFA的状态（项目集）的全体称为 这个文法的LR（0）项目集规范族。 4） LR（0）分析表的构造 若对于一个文法G的拓广文法G，的LR（0）项目集规范族的每个项 目集，不存在移进项目和规约项目同时并存或多个规约项同时共 存，则称G为LR（0）文法。对LR（0）文法构造LR（0）分析 表算法如下： 用整数0，1，2，n分别表示状态I0 ，I1 ，I2 ，In ，令包含S， S项目的集合Ik 的下标k为分析器的初态 若项目Ax属于Ik ，且转换函数GO（ Ik ，x） = Ij，当x为终结符时，则置ACTIONk，x= Sj 若项目A属于Ik ，则对任何终结符和$（统一记为a）置 ACTIONk，a= rj ，（假定A 为文法第j条规则） 若GO（ Ik ，A）= Ij，A为非终结符，则置 GOTOk，A= j 若项目S，S属于Ik ，则置ACTIONk， $= acc 分析表中凡不能用规则至填入信息的元素均置为“出错标志 ”,为了使分析表清晰，仅使用空白表示出错标志。 例：设有文法GS： 1、SA2、SB3、AaAb 4、Ac5、BaBb6、Bd 为了处理方便，我们给上述文法引入一个新的开始符号S ，且定义： SS 作为第0个产生式 从而得到原来的文法的拓广文法GS： 0、SS1、SA2、SB3、AaAb 4、Ac5、BaBb6、Bd SS S A S B A aAb B aBb A c B d Ba Bb S S S A S B Aa Ab Ba Bb A aAb B aBb A c B d a c AaA b BaB b AaA b B d I0 I1 I2 I3 I4 I5 I6 I7I8 I9I10 S A B a c d A B a b b d c 状态态ACTIONGOTO abcd$SAB 0S4S5S6123 1acc 2r1r1r1r1r1 3r2r2r2r2r2 4S4S5S679 5r4r4r4r4r4 6r6r6r6r6r6 7S8 8r3r3r3r3r3 9S10 10r5r5r5r5r5 4.5.3 SLR(1)分析法 例：文法GE E E+T| T T T*F| F F (E)| i 将文法进行拓广并编号： (0)SE(1)E E+T (2)E T(3)T T*F (4)T F(5)F (E)(6)F i 得到如下DFA和分析表 I0:SE E E+T E T T T*F T F F (E) F i I1:SE E E +T I3: TF I2: ET T T *F I4: F ( E) E E+T E T T T*F T F F (E) F i I5: Fi I6: EE+ T T T*F T F F (E) F i I7: TT* F F (E) F i I8: F(E ) EE +T I9: EE+T TT *F I10: TT*F I11: F(E) E F ( T F T ( i i i * + F ( E + ) * F T i ( 状态态ACTIONGOTO i+*()$ETF 0S5S4123 1S6acc 2r2r2S7 r2r2r2r2 3r4r4r4r4r4r4 4S5S4823 5r6r6r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1S7 r1r1r1r1 10r3r3r3r3r3r3 11r5r5r5r5r5r5 为了对句子进行确定性分析，需要解决移进归约或归约归约 冲突，我们采用对含有冲突的项目集向前查看一个输入符号的办 法来解决冲突，这种分析法称为简单的LR分析法，即SLR(1)分析 法。 出现问题的原因：LR分析表构造算法的第二条，即对于每个项目 集IK中的归约项目A ,不管当前输入符号是什么，都将 ACTION表中第K行的各个元素均置rj，其中j为规则A 的编号 ，因此假设有如下项目集： IK=X bB, A ,Br 在分析表第K行中遇到输入符号b时，必然会出现多重定义元素。 解决办法：向前查看一个输入符号以考察当前所处的环境，对归 约项目A 和Br，只需考察将句柄或 r归约为A或B时，直 接跟在A或B后的终结符的集合即FOLLOW(A)和FOLLOW(B)互 不相交且不包含移进符号b,即满足： FOLLOW(A)FOLLOW(B)= FOLLOW(A)b= FOLLOW(B)b= 那么当状态K面临输入符号aVT$时，可以按照以下规则解 决冲突： 1)a=b,则移进。 2) a FOLLOW(A)，则用规则A 进行归约。 3) a FOLLOW(B)，则用规则Br进行归约。 4)此外报错。 一般而言，若一个LR(0)项目集I中有m个移进项目和n个归约 项目时： I:A 1 a11, A 2 a22, , A m amm, B1r1, B2r2, Bnrn 对于所有的移进项目向前看一符号集合a1, a2, , am和 FOLLOW(B1), FOLLOW(B2), ,FOLLOW(Bn)两两相交为 时，则项目集I中冲突仍可用下述规则解决冲突。对当前输入 符号aVT$： 1)a a1, a2, , am,则移进。 2) a FOLLOW(Bi)，i=1,2,3则用规则Biri进行归约。 3)此外报错。 这种用来解决分析动作冲突的方法称为SLR(1)方法。如果对于 一个文法的某些LR(0)项目集或LR(0)分析表所含有的动作冲突 都能用SLR(1)方法解决，则称这个文法是SLR(1)文法。 状态态ACTIONGOTO i+*()$ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1S7r1r1 10r3r3r3r3 11r5r5r5r5 SLR(1)分析表的构造与LR(0)分析表的构造基本相同，仅对 LR(0)分析表的构造算法中的规则2进行如下修改： 若项目A属于Ik ，则对任何终结符a FOLLOW(A) , 置 ACTIONk，a= rj ，（假定A 为文法第j条规则） 4.5.4 LR（1）分析法 例：有拓广文法 0、SS1、SL=R 2、SR3、L*R 4、Li5、RL SS S L=R S R L *R L i R L RL S S S L =R R L S R L* R R L L *R L i S L=R SL= R R L L *R L i L*R L i I0 I1 I2 I3 I4 I5 I6 I9 I7 I8 S L R * i = R * R b i * L i L 一个事实：如果栈里的符号串为$，规约后变为$，当读到 的输入符号是a，若文法中不存在以a为前缀的规范句型，那 么这种归约无效。 对上例针对句型i=i的SLR（1）分析过程为： S S L=R L=L L=i i=i 状态栈 符号栈 输入串 0 $ i=i$ 05 $i =i$ 02 $L =i$ 03 $R =i$ 当状态2呈现于栈顶且面临的输入符号是=时,由于这个文法不含有 以R=为前缀的规范句型,因此用RL进行的归约是无效归约,也 就是说并不是FOLLOW(R)的每个元素在含R的所有句型中都会 出现在R的后面.解决这一问题的方法是采用LR(1)分析法. LR(1)分析法的思想是在分析过程中,当试图用某一规则A归约 栈顶的符号串时,不仅应该查看栈中符号串,还应向前扫 视一个输入符号a,只有当a的确构成文法某一规范句型的前 缀时,才能用此规则进行归约。为此可以考虑在原来LR（0）项 目集中增加更多的展望信息，这些信息有助于克服动作冲突和 排除无效归约。也就是需要重新定义称之为LR（1）的项目。 一个LR（1）项目是一个二元组A，a，其中A是 一个LR（0）项目，每个a是终结符且aFollow(A) ，称为展望 符或搜索符。当时，搜索符是无意义的；当=时，搜索 符a明确指出当A，a是栈顶状态的一个LR（1）项目时， 仅在输入符号是a时才能用A归约，而不是对FOLLOW（A） 中的所有符号都用A归约。 构造LR（1）项目集族的方法： （1）构造LR（1）项目集I的闭包函数 I的任何项目都属于CLOSURE（I） 若项目AB，a，属于CLOSURE（I）， Br是文法的一 条规则，bFIRST（ a），则Br，b也属于CLOSURE（I ） 重复直到CLOSURE（I）不在增大为止。 （2）构造转换函数 令I是一个LR（1）项目集，X是一个文法符号，函数 GO（ I，X ）= CLOSURE（J） J=AX，a| AX，aI （3）构造DFA同LR（0）分析法相同（注：构造初 态是从基本项目SS，$开始的） （4）构造LR（1）分析表的方法与构造LR（0）分 析表的方法基本相同，仅对归约项目作如下修改： 若归约项目A，a属于Ik，则对搜索符a置 ACTIONk，a= rj，（假定A 为文法第j条规 则） SS,$ S L=R, $ S R, $ L *R,=/ $ L i,=/ $ R L, $ I9 * L*R , $ RL , =/