Chapt5语法分析-自下而上ppt.ppt

编译原理,第五章 语法分析自下而上分析,编译原理,编译原理,第五章 语法分析自下而上分析,自上而下分析法(Top-down)自下而上分析法(Bottom-up),编译原理,语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。,编译原理,语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约,编译原理,G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E,i,+,*,i,i,编译原理,5.1.1 归约,采用“移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。,编译原理,例：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d试对abbcde进行“移进归约”分析。,编译原理,编译原理,b,d,b,a,c,e,分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串,编译原理,5.1.2 规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,编译原理,考虑文法G(E)： E T | E+T T F | T*F F (E) | i和句型i1*i2+i3：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3短语： i1，i2，i3， i1*i2， i1*i2+i3直接短语： i1，i2，i3句柄： i1,编译原理,在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。,编译原理,可用句柄来对句子进行归约句型 归约规则abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe S,编译原理,定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,编译原理,把上例倒过来写，则得到：S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约 规范推导由规范推导推出的句型称为规范句型。,编译原理,编译原理,5.1.3 符号栈的使用和分析树的表示,栈是语法分析的一种基本数据结构。#作为栈底符号考虑文法G(E)： E T | E+T T F | T*F F (E) | i输入串为i1*i2+i3 ，分析步骤为：,编译原理,步骤 符号栈输入串动作0 #i1*i2+i3#预备1 #i1*i2+i3#进2 #F*i2+i3#归，用Fi3 #T*i2+i3#归，用TF4 #T*i2+i3#进,G(E)： E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作4 #T*i2+i3#进5 #T*i2+i3#进6 #T*F+i3#归，用Fi7 #T+i3#归，用TT*F8 #E+i3# 归，用ET9 #E+i3# 进,G(E)： E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作9 #E+ i3#进10#E+i3#进11#E+F#归，用Fi12#E+T#归，用TF13#E#归，用EE+T14#E#接受,G(E)： E T | E+T T F | T*F F (E) | i,编译原理,语法分析的方法：自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓 归约 ，是指根据文法的产生式规则，把产生式的右部替换成左部符号。,回顾,编译原理,归约,采用“移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。,编译原理,规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,编译原理,定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,编译原理,步骤 符号栈输入串动作0 #i1*i2+i3#预备1 #i1*i2+i3#进2 #F*i2+i3#归，用Fi3 #T*i2+i3#归，用TF4 #T*i2+i3#进,G(E)： E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作4 #T*i2+i3#进5 #T*i2+i3#进6 #T*F+i3#归，用Fi7 #T+i3#归，用TT*F8 #E+i3# 归，用ET9 #E+i3# 进,G(E)： E T | E+T T F | T*F F (E) | i,编译原理,步骤 符号栈输入串动作9 #E+ i3#进10#E+i3#进11#E+F#归，用Fi12#E+T#归，用TF13#E#归，用EE+T14#E#接受,G(E)： E T | E+T T F | T*F F (E) | i,编译原理,5.2 算符优先分析,四则运算的优先规则： 先乘除后加减，同级从左到右考虑二义文法文法G(E)：G(E)： E i| E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。,编译原理,例如：句子i+i-i*(i+i),编译原理,返回,编译原理,句子i+i-i*(i+i)的归约过程是：(1) i+i-i*(i+i)(2) E+i-i*(i+i)(3) E+E-i*(i+i)(4) E-i*(i+i)(5) E-E*(i+i)(6) E-E*(E+i)(7) E-E*(E+E)(8) E-E*(E)(9) E-E*E(10) E-E(11) E,编译原理,起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。,编译原理,首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系a b a的优先级低于ba b a的优先级等于ba b a的优先级高于b注意：与数学上的=不同 + + a b并不意味着b a，如 ( + 和 + (,编译原理,5.2.1 算符优先文法及优先表构造,一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。,编译原理,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1. ab当且仅当文法G中含有形如Pab或PaQb的产生式；,如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：ab，ab， ab 则称G是一个算符优先文法。,2. ab当且仅当G中含有形如PaR的产生式， 而R b或R Qb；,3. ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。,编译原理,例:考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i由第(4)条规则，有 ()；由规则EET和TT*F， 有 *；由(2) TT*F 和(3) FP F ，可得*；由(1)EET和E E+T，可得+；由(3)FPF和F PF，可得。由(4)P(E)和 EE+TT+TT*F+TF*F+TPF*F+TiF*F+T 有 (+、(*、(和(i。,编译原理,优先关系表,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。,确定满足关系和的所有终结符对：,1. ab当且仅当文法G中含有形如Pab或PaQb的产生式；,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,比较,比较,编译原理,有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。假定有个产生式的一个候选形为aP 那么，对任何bFIRSTVT(P)，有 ab。假定有个产生式的一个候选形为Pb 那么，对任何aLASTVT(P)，有 ab。,编译原理,首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1. 若有产生式Pa或PQa，则aFIRSTVT(P)；2. 若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。,编译原理,数据结构：布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。,编译原理,运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。,编译原理,如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDURE INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE； 把(P，a)下推进STACK栈 END；,编译原理,主程序：BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE； FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)； WHILE STACK 非空 DOBEGIN 把STACK的顶项，记为(Q，a)，上托出去； FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；END,编译原理,这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)a | FP，a=TRUE同理，可构造计算LASTVT的算法。,编译原理,构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1. 若有产生式P a或P aQ，则a LASTVT(P)；2. 若a LASTVT(Q)，且有产生式P Q ，则a LASTVT(P)。,编译原理,使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：,编译原理,FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2； IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xia； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END,编译原理,例: 考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i1. 计算文法G的FIRSTVT和LASTVT;2. 构造优先关系表;3. G是算符优先文法吗?,编译原理,编译原理,结论: G是算符优先文法,G的算符优先关系表,编译原理,回顾,定义任何两个可能相继出现的终结符a与b的优先关系 三种关系a b a的优先级低于ba b a的优先级等于ba b a的优先级高于b注意：与数学上的=不同，a b并不意味着b a,编译原理,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1. ab当且仅当文法G中含有形如Pab或PaQb的产生式；,如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：ab，ab， ab 则称G是一个算符优先文法。,2. ab当且仅当G中含有形如PaR的产生式， 而R b或R Qb；,3. ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。,编译原理,从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,比较,比较,编译原理,有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。假定有个产生式的一个候选形为aP 那么，对任何bFIRSTVT(P)，有 ab。假定有个产生式的一个候选形为Pb 那么，对任何aLASTVT(P)，有 ab。,编译原理,首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1. 若有产生式Pa或PQa，则aFIRSTVT(P)；2. 若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。,编译原理,构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1. 若有产生式P a或P aQ，则a LASTVT(P)；2. 若a LASTVT(Q)，且有产生式P Q ，则a LASTVT(P)。,编译原理,使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：,编译原理,FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2； IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xia； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END,编译原理,5.2.2 算符优先分析算法,可归约串，句型，短语，直接短语，句柄，规范归约。一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。,编译原理,考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i,句型：T+F*P+i,短语：直接短语：句柄：素短语：最左素短语：, T+F*P+i,T, F, P, F*P, i,T+F*P,T, F, P, i,T,F*P, i,F*P,编译原理,算符优先文法句型(括在两个之间)的一般形式写成： #N1a1N2a2NnanNn+1#其中，每个ai都是终结符，Ni是可有可无的非终结符。定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1， aj-1aj aj aj+1，ai-1ai aiai+1,编译原理,算符优先分析算法使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。,编译原理,k:=1;Sk:=#;REPEAT 把下一个输入符号读进a中； IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sja DOBEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL SjQ; 把Sj+1Sk归约为某个N； k:=j+1; Sk:=N END OF WHILE; IF Sja OR Sja THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*调用出错诊察程序*/ UNTIL a=#,自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。 N X1 X2 Xk-j Sj+1 Sj+2 Sk,编译原理,在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N #。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。,编译原理,算符优先分析一般并不等价于规范归约。,考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的句子i+i*i+i,编译原理,算符优先分析法特点：优点: 简单，快速缺点: 可能错误接受非法句子，能力有限.算符优先分析法是一种广为应用、行之有效的方法。用于分析各类表达式ALGOL 60,编译原理,5.2.3 优先函数,把每个终结符与两个自然数f()与g()相对应，使得若1 2，则f(1) g(2)f称为入栈优先函数，g称为比较优先函数。优点:便于比较，节省空间；缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。,编译原理,文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的优先函数如下表,编译原理,有许多优先关系表不存在优先函数，如：,不存在对应的优先函数f和g 假定存在f和g，则有 f(a)=g(a)，f(a)>g(b)， f(b)=g(a)，f(b)=g(b) 导致如下矛盾: f(a) > g(b) = f(b) = g(a) = f(a)如果优先函数存在，则不唯一(无穷多),编译原理,如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:1 对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。如果ab，则从fa画一条弧至gb，如果ab，则画一条弧从gb至fa 。2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。3 检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。,编译原理,现在必须证明：若ab，则f(a)g(b)；若ab，则f(a) g(b)。第一个关系可从函数的构造直接获得。因为，若ab，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同的。至于ab和ab的情形，只须证明其一。,1 对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。如果ab，则从fa画一条弧至gb，如果ab，则画一条弧从gb至fa 。,编译原理,如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a) g(b)。我们所需证明的是，在这种情况下，f(a)g(b)不应成立。我们将指出，如果f(a)g(b)，则根本不存在优先函数。假若f(a)g(b)，那么必有如下的回路：,编译原理,因此有ab, a1b, a1b1, , ambm, abm对任何优先函数f和g来说，必定有f(a)> g(b) f(a1) g(b1) f(am) g(bm) f(a)从而导致f(a)> f(a)，产生矛盾。因此，不存在优先函数f和g。,编译原理,例:取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的终结符+，*，i,编译原理,编译原理,语法分析的方法：自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。优先关系表的构造：FIRSTVT, LASTVT优先函数算符优先分析法,回顾,编译原理,规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,编译原理,定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,编译原理,5.3 LR分析法,LR分析法：1965年 由Knuth提出,分析表产生器,产生分析表,LR分析器工作,编译原理,主要介绍,1. 总控程序(LR分析器)的处理思想2. LR分析表的构造方法及原理,编译原理,5.3.1 LR分析器,规范归约的关键问题是寻找句柄.“历史”：已移入符号栈的内容“展望”：根据产生式推测未来可能遇到的输入符号“现实”：当前的输入符号,编译原理,LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作,LR分析程 序,编译原理,LR分析器的核心是一张分析表：ACTIONs，a：当状态s面临输入符号a时，应采取什么动作.GOTOs，X：状态s面对文法符号X时，下一状态是什么,编译原理,每一项ACTIONs，a所规定的四种动作:1. 移进 把(s，a)的下一状态s和输入符号a推进栈，下一输入符号变成现行输入符号.2. 归约 指用某产生式A进行归约. 假若的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s=GOTOsm-r, A和文法符号A推进栈.3. 接受 宣布分析成功，停止分析器工作.4. 报错,编译原理,分析开始时:状态 已归约串 输入串 (s0， #， a1a2 an #)以后每步的结果可以表示为:(s0 s1 sm ，# X1 Xm ，aiai+1 an #),编译原理,(s0 s1 sm ，# X1 Xm ，aiai+1 an #)分析器根据ACTION(sm , ai)确定下一步动作1. 若ACTION(sm , ai)为移进，且s=GOTO(sm, ai),，则三元式格局变为: (s0 s1 sms ，# X1 Xm ai，ai+1 an #)2. 若ACTION(sm , ai)为按A归约，三元式变为: (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #)此处, s=GOTO(sm-r, A), r为的长度, = Xm-r+1 Xm3. 若ACTION(sm , ai)为"接受"，则三元式不再变化，变化过程终止，宣布分析成功.4. 若ACTION(sm , ai)为"报错"，则三元式变化过程终止，报告错误.,(s0 s1 sm-r sm-r+1 sm ，# X1 Xm-r Xm-r+1 Xm ，aiai+1 an #)(s0 s1 sm-r ，# X1 Xm-r，aiai+1 an #)(s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #),编译原理,LR分析器示例：,文法G(E)： (1) EET(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi,编译原理,其LR分析表为:,编译原理,假定输入串为i*i+i， LR分析器的工作过程:步骤状态符号输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#,i,*,编译原理,假定输入串为i*i+i， LR分析器的工作过程:步骤状态符号输入串(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#(9)01#E+i#(10)016#E+i#,+,i,编译原理,步骤状态符号输入串(10)016#E+i#(11)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15) 接受,+,i,i,编译原理,定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法.非LR结构LR文法不是二义的，二义文法肯定不会是LR的。 S iCtS | iCtSeS 栈 输入 iCtS e#,编译原理,5.3.2 LR(0)项目集族和LR(0)分析表的构造,假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,编译原理,5.3.2 LR(0)项目集族和LR(0)分析表的构造,规范归约过程中栈内的符号串和扫描剩下的输入符号串构成了一个规范句型栈内的如果出现句柄，句柄一定在栈的顶部,栈内永远不会出现句柄之后的符号！,编译原理,5.3.2 LR(0)项目集族和LR(0)分析表的构造,字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u2ur，则符号串u1u2ui(1ir)是的活前缀。(必为终结符串)对于一个文法G, 可以构造一个DFA,它能识别G的所有活前缀.,编译原理,指导思想目标驱动,踢足球“如果你不知道怎样踢球，就往球门方向踢 ” 施拉普纳LR分析“如果你不知道怎样分析，就保证栈中总是活前缀”,一个语言都有哪些活前缀?那些字符串是活前缀?能不能构造一个DFA来识别活前缀?,编译原理,文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目如:AXYZ有四个项目：A.XYZ AX.YZ AXY.Z AXYZ. A . 称为"归约项目"归约项目 S . 称为"接受项目"A .a (aVT) 称为"移进项目" A .B (BVN) 称为"待约项目".,编译原理,文法G(S) SE EaA|bB AcA|d BcB|d 该文法的项目有：1. S·E2. SE·3. E·aA 4. Ea·A5. EaA·6. A·cA7. Ac·A8. AcA·9. A·d 10. Ad·11. E·bB12. Eb·B13. EbB·14. B·cB15. Bc·B 16. BcB·17. B·d18. Bd·,编译原理,构造识别文法所有活前缀的NFA方法 1. 若状态i为XX1 Xi-1.Xi Xn ， 状态j为XX1 Xi-1Xi .Xi+1 Xn ， 则从状态i画一条标志为Xi的有向边到状态j； 2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。把识别文法所有活前缀的NFA确定化。,