1、第四章 语法分析1/12414.6语法分析自下而上分析一、基本思想：从给定符号串出发，重复使用一、基本思想：从给定符号串出发，重复使用文法中相关产生式左部去替换当前符号串中对文法中相关产生式左部去替换当前符号串中对应子串，逐步归约成文法开始符号一个方法。应子串，逐步归约成文法开始符号一个方法。假如从语法树角度看，自下而上分析过程是输假如从语法树角度看，自下而上分析过程是输入符号串作为末端结点符号串，向着根结点方入符号串作为末端结点符号串，向着根结点方向往上结构语法树，使识别符号恰好是该语法向往上结构语法树，使识别符号恰好是该语法树根结点。树根结点。2/1242二、移进归约法自下而上分析法基本实
2、现方法是移进归约法。移进移进归约法：归约法：从左到右把输入串符号一一移进符号栈里，一旦发觉栈顶形成一个可归约串时，就把这个串用对应归约符号（在规范归约情况下用对应产生式左部符号）代替。重复这个过程，直至最终形成以下格局：符号栈输入串#S#这种格局表示分析成功；若达不到这种格局，意味着输入串含有语法错误。3/1243例：设文法例：设文法例：设文法例：设文法GS:GS:SaAcBeSaAcBeAb|AbAb|AbBdBd问问问问abbcdeabbcde是不是该文法句子？是不是该文法句子？是不是该文法句子？是不是该文法句子？步骤步骤步骤步骤符号栈符号栈符号栈符号栈输入流输入流输入流输入流动作动作动作
3、动作0 0#abbcde#abbcde#1 1#a#abbcde#bbcde#移进移进移进移进2 2#ab#abbcde#bcde#移进移进移进移进3 3#aA#aAbcde#bcde#归约，用归约，用归约，用归约，用AbAb4 4#a#aAbAbcde#cde#移进移进移进移进5 5#aA#aAcde#cde#归约，用归约，用归约，用归约，用AAbAAb6 6#aAc#aAcde#de#移进移进移进移进7 7#aAcd#aAcde#e#移进移进移进移进8 8#aAcB#aAcBe#e#归约，用归约，用归约，用归约，用BdBd9 9#aAcBe#aAcBe#移进移进移进移进1010#S#S#归
4、约，用归约，用归约，用归约，用S aAcBeS aAcBe1111#S#S#成功成功成功成功Sa A c B eA b d b 4/1244三、关键问题1 准确定义可归约串：不一样定义形式形成不一样归约法。在规范归约、LR分析法中，可归约串是句柄在算符优先分析法中，可归约串是最左素短语。2 怎样识别可归约串：=不一样分析法LR分析法中：历史，现实，展望。算符优先分析法中：符号之间优先关系。5/1245优先分析法有两种：简单优先分析法(规范归约)求出文法求出文法全部符号之间优先关系，以此确定归约过程中句全部符号之间优先关系，以此确定归约过程中句柄。柄。算符优先分析法(不规范归约)求出求出文法全部
5、终止符之间优先关系，以此确定归约过文法全部终止符之间优先关系，以此确定归约过程中程中可归约串。4.7优先分析法6/12464.7.1、简单优先分析法概述l基本思想l简单优先分析法基本思想是对一个文法按一定标准求出该文法全部符号之间优先关系，按照这种关系确定归约过程中句柄以进行归约。7/1247优先关系定义lXY 表示X与Y优先关系相等lXY 表示X优先级小于Y优先级lXY 表示X优先级大于Y优先级注意：这里、与数学中=、不一样。8/1248优先关系确定l定理定理lXY 当且仅当G中存在产生式AXYlXY 当且仅当G中存在产生式AXB，l 且BYlXY 当且仅当G中存在产生式ABD，l 且BX，
6、DY+*9/1249相邻文法符号之间优先关系l在句型中，句柄内各相邻符号之间含有相同优先级。相同优先级用“”。l因为句柄要先归约，所以要求句柄两端符号优先级要比位于句柄之外相邻符号优先级高。优先级低于表示为“”,优先级高于表示为：“”。l某句型中：N1Ni-1 Ni Nj N j+1Nn.10/12410优先关系例子l文法：文法：SbAb A(B|a/SbAb BAa)/A(Aa)|al语言：语言：bab,b(aa)b,b(aa)a)b,l能够从语法树里面导出能够从语法树里面导出部分部分优先关系。优先关系。bAbaSbbb A bS(Bbb11/12411优先关系矩阵l能够将优先能够将优先关系
7、填写到关系填写到一个矩阵，一个矩阵，得到优先矩得到优先矩阵。阵。(将矩阵将矩阵作为关系表作为关系表示形式）示形式）SbA(Ba)Sb=A=(=B)#=12/12412#b(a a)a)b#句柄句柄:a 归约为归约为A#b(A a)a)b#句柄句柄:A a)归约为归约为B#b(B a)b#句柄句柄:(B 归约为归约为A13/12413识别过程(例子续)#b(B b#句柄句柄:(B 归约为归约为A#b(A a)b#句柄句柄:Aa)归约为归约为B#b(A a)b#句柄句柄:Aa)归约为归约为B#b A b#句柄句柄:bAb 归约为归约为S#b(B b#句柄句柄:(B 归约为归约为A14/12414若
8、有文法若有文法GS：S bAb A(B|a B Aa)依据依据关系定义，由文法产生式可求得各个文法符号之间优先关系定义，由文法产生式可求得各个文法符号之间优先关系。关系。1.求关系：由求关系：由S bAb A(B|a B Aa)可知：可知：b=A，A=b，(=B，A=a，a=)。/A XY，X=Y2.求求关系：关系：由由S bAb，且，且A+(B，A+a 可知：可知：b(，ba。由由A (B 且且B+(B ，B+a ，B+A ，可知：，可知：(，(a，(A /A XB B+YX关系：关系：由由S bAb，且，且A+)，A+B，A+a，可知：可知：)b，ab，Bb；由由B Aa)且且A+)，A+
9、a，A+B，可知：，可知：)a，aa，Ba；/A BDB+XD*YXY15/12415简单优先文法l若一个文法是简单优先文法，必须满足以下条件：1)在文法符号集V中，任意两个符号之间最多只有一个优先关系成立；2)在文法中任意两个产生式没有相同右部。l简单优先分析法基本思想是找到形如lSj-1SjSj+1SiSi+1句柄。简单优先分析法算法思想是：在不停将输入符号移进分析栈过程中经过比较优先级，首先发觉句柄尾，然后再反向找到句柄头，从而找到句柄。之后寻找句柄以句柄为右部规则，如找到则进行规约，不然犯错16/124164.7.2算符优先分析法算符优先分析法算符优先分析法 是Floyd在1963年首
10、先提出来，Greis在1971年将它形式化。这是一个古典而又实用方法，用这种方法分析程序设计语言中各类表示式尤为有效。不少编译程序使用这种方法分析表示式，而使用其它方法分析其余语言部分。这种方法简单直观，尤其便于手工实现。17/124172 两个相邻终止符 a,b 之间优先关系：a b a优先级高于b1 算符优先分析法：就是仿照算术表示式四则运算过程而设计一个分析方法。这种方法首先要求运算符之间（终止符号之间）优先关系和结合性质，然后，利用这种关系用比较相邻运算符之间优先次序来确定句型可归约串并进行归约。一、概述.18/12418注意：优先关系与符号出现左右次序相关数学中：a b 能够 b b
11、 不能b a比如：EE+E|E*E|(E)|i(+不过+(3 逻辑结构图：.优先关系表优先关系表优先关系表优先关系表算符优先分析程序算符优先分析程序算符优先分析程序算符优先分析程序符符符符号号号号栈栈栈栈产产产产生生生生式式式式文文文文 法法法法词法分析后词法分析后词法分析后词法分析后单词串单词串单词串单词串语法树语法树语法树语法树19/12419二、算符优先文法和优先表结构1 算符优先文法（算符优先文法（OPG文法）文法）（1 1）算符文法（）算符文法（）算符文法（）算符文法（OGOG文法）：文法）：文法）：文法）：设有一文法设有一文法G，若，若G中没有形如中没有形如SQR产生式，（产生式，
12、（S,Q,RVN）则称文法）则称文法G为算符文为算符文法。法。（2 2）定义优先关系：）定义优先关系：）定义优先关系：）定义优先关系：设文法设文法G是一个是一个OG文法，令文法，令a,b是任意两是任意两个终止符号，个终止符号，P,G,R 是非终止符号，定义：是非终止符号，定义：a=b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb规则。规则。a b或或R=Qb。a b 当且仅当文法当且仅当文法G中含有形如中含有形如PRb规则，规则，其中：其中：R=a 或或 R=aQ。两个非终止符相邻两个非终止符相邻两个非终止符相邻两个非终止符相邻.20/12420l三种关系语法树：lab 其
13、中为或为B，这么a,b在同一句柄中同时归约所以优先级相同。la b 其中为或为C，a、b不在同一句柄中，a先归约，所以a优先性大于b。A a BP bA B bPa a bA21/12421（3）OPG文法：文法：设有一个OG文法，假如在任意两个终止符号之间，在 、E*有 +E 有 +*它是OG文法，但它不是OPG文法。改写：EE+T|TTT*F|FF(E)|i是 OPG文法.22/124222优先关系表结构方法（1 1）为每一个非终止符）为每一个非终止符）为每一个非终止符）为每一个非终止符P P定义二个集合：定义二个集合：定义二个集合：定义二个集合：l lFirstVT(P)=a|P=aFi
14、rstVT(P)=a|P=a或或或或 P=Qa,a P=Qa,aV VT T,Q,QV VN N 非终止符非终止符非终止符非终止符P P首终止符集合首终止符集合首终止符集合首终止符集合l lLastVT(P)=a|P=a LastVT(P)=a|P=a 或或或或 P=aQ,a P=aQ,aV VT T,Q,QV VN N 非终止符非终止符非终止符非终止符P P尾终止符集合尾终止符集合尾终止符集合尾终止符集合比如：表示式文法：比如：表示式文法：比如：表示式文法：比如：表示式文法：EE+T|TEE+T|TTT*F|FTT*F|FF(E)|iF(E)|il非终止符FirstVTFirstVTLast
15、VTLastVTE E(i +*(i +*i )+*i )+*T T(i *(i *i )*i )*F F(i (i i )i )+23/12423（2 2）结构优先关系表算法：）结构优先关系表算法：）结构优先关系表算法：）结构优先关系表算法：输入：输入：输入：输入：算符文法算符文法算符文法算符文法G G 输出：输出：输出：输出：关于关于关于关于GG优先关系表优先关系表优先关系表优先关系表 方法：方法：方法：方法：为每一个非终止符为每一个非终止符为每一个非终止符为每一个非终止符P P计算计算计算计算FirstVT(P)FirstVT(P)和和和和LastVT(P)LastVT(P)执行算法：执
16、行算法：执行算法：执行算法：for for 每个产生式每个产生式每个产生式每个产生式PxPx1 1x x2 2xxn n do do for i=1 to n-1 do for i=1 to n-1 do begin begin if xif xi i和和和和x xi-1i-1都为终止符都为终止符都为终止符都为终止符 then then 置置置置 x xi i=x=xi-1;i-1;if in-2 if in-2 且且且且x xi i和和和和x xi+2i+2都为都为都为都为V VT T,但但但但x xi+1i+1为为为为V VN N then then 置置置置 x xi i=x=xi+2;
17、i+2;if xif xi i为为为为V VT T 而而而而x xi+1i+1为为为为V VN N then then for FirstVT(xfor FirstVT(xi+1i+1)中每一个中每一个中每一个中每一个b dob do置置置置 x xi i b;x axi+1i+1;end;end;.24/12424比如：EE+T|TEE+T|TTT*F|FTT*F|FF(E)|iF(E)|i(3)对FirstVT(S)中全部b置#置#=#+*i()#+*i(#.25/12425例：结构下面文法算符优先表。S if Eb then E else E E E+T|T T T*F|F F i Eb
18、 b 解：1）求各非终止符首终止符集和尾终止符集。为了考虑语句开始和结束符号“”，对文法拓广，加一个产生式SS l FIRSTVT(S)=if LASTVT(S)=else,+,*,il FIRSTVT(E)=+,*,i LASTVT(E)=+,*,il FIRSTVT(T)=*,i LASTVT(T)=*,il FIRSTVT(F)=i LASTVT(F)=il FIRSTVT(Eb)=b LASTVT(Eb)=b 2)填写算符优先表26/12426 if thenelse+*i b#if=then=else+*i b#27/12427三、算符优先分析法1素短语素短语：素短语：素短语是一个短
19、语。l最少包含一个终止符。l除本身外不再包含其它素短语。比如：句型T+T*F+iE EE +TE +TE +T F E +T F T T *F i T T *F i 短语：短语：短语：短语：T+T*F+iT+T*F+iT+T*FT+T*FT*F T*F 最左素短语最左素短语最左素短语最左素短语T T 句柄句柄句柄句柄I I素短语素短语素短语素短语28/124282识别最左素短语方法对OG文法，任何句型都没有相邻两个非终止符，其句型总能够表示成：#N1a1N2a2 NnanNn+1#其中：NiVNaiVT定理：定理：一个OPG文法任何句型最左素短语是满足以下条件最左子串NiaiNi+1ai+1
20、ajNj+1ai-1 aiai=ai+1 aj-1=ajaj aj+1.29/12429比如：EE+T|TEE+T|TTT*F|FTT*F|FF(E)|iF(E)|i句型#T+T*F+i#有#+#所以，最左素短语是T*F。+*i()#+*i(=)#=.30/124303算符优先分析算法输入：输入符号串w和优先关系表输出：若w是正确句子，则接收，不然输犯错误信息。方法：依据最左素短语定理，利用符号栈来识别最左素短语（先找尾，后找头），然后归约。31/1243132/12432例：例：例：例：i*(i+i)i*(i+i)S S栈栈栈栈关系关系关系关系a a输入流输入流输入流输入流#i i*(i+i
21、)#*(i+i)#i#i#*#*(i+i)#(i+i)#F#F*(i+i)#(i+i)#F*#F*(i+i)#i+i)#F*(#F*(i i+i)#+i)#F*(i#F*(i (+(+i)#i)#F*(F#F*(F+i)#i)#F*(F+#F*(F+i i)#)#F*(F+i#F*(F+i +)+)#F*(F+F#F*(F+F()()#F*(E#F*(E=)#F*(E)#F*(E)*#*#F*F#F*F#E#E#33/12433算符优先分析优缺点lA、算符优先分析比规范归约要快得多，因为它跳过了许多单非终止符归约。不过，因为忽略了非终止符在归约中作用，它可能会把错误输入串误认为是句子。lB、算
22、符优先文法适用范围比简单优先文法大得多，许多程序设计语言都能够用它来分析。算符优先分析优先表结构简单，甚至能够用手工结构。lC、缺点在于有些文法不满足算符优先文法，必须先改写，有些甚至无法改写。若终止符数目多，优先表可能会占有太多空间。34/12434四、优先函数1、定义若若若若 1 1 2 2 则令则令则令则令 f(f(1 1)g()g()g(2 2)优点：节约内存空间n*n=2n 便于执行比较运算缺点：掩盖一些输入串错误说明：有些优先关系矩阵不存在对应优先函数。优先关系表优先函数不唯一。.=.其中：其中：其中：其中：f f 称为入栈（栈内）称为入栈（栈内）称为入栈（栈内）称为入栈（栈内）优
23、先函数。优先函数。优先函数。优先函数。g g 称为比较（栈称为比较（栈称为比较（栈称为比较（栈外）优先函数。外）优先函数。外）优先函数。外）优先函数。1 1 2 2之间优先关之间优先关之间优先关之间优先关系能够经过比较系能够经过比较系能够经过比较系能够经过比较f f(1 1)和和和和g(g(2 2)大小来大小来大小来大小来决定。决定。决定。决定。35/124352、优先表向优先函数转化l算法1：逐次加1法1）对全部终止符a（包含#），令f(a)g(a)=c，c为一任意常数。2）对全部终止符：l若a b 而f(a)=g(b),则取g(b)=f(a)+1；l若a b 而f(a)g(b),则取f(a
24、)=g(b)=max(f(a),g(b)；3）重复步骤2）直到f(a)，g(b)不再改变为止。若存在f(a)或g(b)值=2n+c而步骤2）还未结束，则优先函数不存在。36/12436例：优先表以下，结构优先函数表 +*()i#+*()i#37/12437l步骤1：置初值，设c=1+*()i#f111111 g111111步骤2：对第一步结果进行迭代，执行算法第二步+*()i#f241441 g23515138/12438l步骤3：对第2步结果进行迭代，执行算法第二步+*()i#f351551 g246161步骤4：对第3步结果进行迭代，执行算法第二步+*()i#f351551 g246161
25、步骤4与步骤3结果相同，迭代收敛，步骤5结果即为优先函数。39/124392、优先表向优先函数转化输入：输入：输入：输入：一张优先关系表。一张优先关系表。输出：输出：输出：输出：关于优先关系表优先函数。关于优先关系表优先函数。算法算法算法算法2 2：Bell有向图法。有向图法。对每一个终止符对每一个终止符a（包含（包含#）令其对应两个符号）令其对应两个符号fa和和ga，画一张以画一张以fa和和ga为结点方向图。为结点方向图。假如假如 a b,就画一条从就画一条从fa到到gb 方向弧。方向弧。假如假如 a b,就画一条从就画一条从gb 到到fa方向弧。方向弧。对每个结点都赋予一个数，此数等于从该
26、结点出发所能对每个结点都赋予一个数，此数等于从该结点出发所能抵达结点（包含结点本身）个数。赋给结点抵达结点（包含结点本身）个数。赋给结点fa数作为函数作为函数数fa值，赋给结点值，赋给结点gb数作为函数数作为函数gb值。值。检验优先函数检验优先函数f和和g，看是否有矛盾。若没有矛盾，则，看是否有矛盾。若没有矛盾，则f和和g就是所求优先函数；不然，不存在优先函数。就是所求优先函数；不然，不存在优先函数。.40/12440l例：优先表以下，结构优先函数 +*()i#+*()i#41/12441*()i#*()i#42/12442l注：用两种算法得到优先函数表不一样，说明了假如存在一对优先函数，就存
27、在无穷多对优先函数。+*()i#f682881 g47929143/124433、优先表与优先函数关系l1）优先函数并不等价于优先表，在优先表中没相关系终止符对也存在优先函数。优先表能发觉错误优先函数不能发觉。优先函数能力弱于优先表。l2）有些优先表不存在优先函数，比如l因为：f(a)=g(a),f(a)g(b),f(b)=g(a),f(b)=g(b)l造成结果f(a)g(b)f(b)=g(a)=f(a),出现矛盾a b a b44/124443、优先表与优先函数关系l3）假如存在一对优先函数，就存在无穷多对优先函数。l注：因为优先函数是在优先表基础上才能结构出来，能力又弱于优先表，唯一优点是
28、节约空间，所以最近优先函数用作语法分析已不多见了。45/12445l算符优先分析法不足算符优先分析法不足 l因为算符优先分析法去掉了单非终止符之间归约，尽管在分析过程中，当决定是否为句柄时采取一些检验办法，但仍难完全防止把错误句子得到正确归约。l比如，下述文法是一个算符优先文法，其产生式为：SS;D|DDD(T)|HHa|(S)TT+S|S其中VNS，D，T，H，VT；,(,),a,+，S为开始符号。46/12446l对应算符优先关系矩阵为;()a+#;(=a+#an(=tf#识别文法全部规范句型活前缀DFA=LR分析表1、规范句型活前缀前缀：指字符串任意首部。例：abc前缀为：,a,ab,a
29、bc规范句型活前缀：不包含句柄右部任何符号前缀。上例中：aaAbb活前缀为：,a,aa,aaA,aaAb一个LR分析器工作过程实质上是一个逐步识别所给文法规范句型活前缀过程。句柄句柄句柄句柄60/124602、LR(0)项目句柄与活前缀之间有三种关系：l活前缀中包含句柄全部符号l活前缀中只包含句柄一部分符号l活前缀中不包含句柄任何符号为了刻画在分析过程汉字法一个产生式右部符号串已经有多大一部分被识别，我们在产生式右部加上圆点来表示。A.A1.2A.把右部某位置上标有圆点产生式称为对应文法一个LR(0)项目。注意：对A仅有LR(0)项目 A.61/12461例：设有文法GS:SA|BAaAb|c
30、BaBb|d求该文法全部LR(0)项目。解：首先将文法拓广，使接收项目唯一(SS)(1)S.S(2)SS.(3)S.A(4)SA.(5)S.B(6)SB.(7)A.aAb(8)Aa.Ab(9)AaA.B(10)AaAb.(11)A.c(12)Ac.(13)B.aBb(14)Ba.Bb(15)BaB.B(16)BaBb.(17)B.d(18)Bd.62/12462项目分类：l l归约项目：归约项目：A.句柄已形成，按产生式归约。l l移进项目：移进项目：A.XXVT，期待从输入串中移进一个符号，以待形成句柄。l l待约项目：待约项目：A.XXVN，期待从剩下输入串中进行归约而得到X，然后才能继续
31、分析A右部。l l接收项目：接收项目：SS.,其中，S为文法开始符号，表示整个句子已经分析完成，能够接收。63/124633、结构识别文法活前缀DFADFA中每一个状态由若干个中每一个状态由若干个LR(0)项目组成。项目组成。定义闭包函数：定义闭包函数：定义闭包函数：定义闭包函数：设设I是文法是文法G任一项目集，任一项目集，Iclosure(I)定义定义为：为：lI中每一个项目都属于中每一个项目都属于closure(I)l若形如若形如 A.B 项目属于项目属于closure(I)，则文法中任何，则文法中任何B产产生式生式 B圆点在最左边项目圆点在最左边项目B.也属于也属于closure(I)l
32、重复上述过程，直到重复上述过程，直到closure(I)不再增大为止。不再增大为止。例：令例：令I=S.S则：则：closure(I)=S.S,S.A,S.B,A.aAb,A.c,B.aBb,B.d=I064/12464定义状态转移函数：定义状态转移函数：定义状态转移函数：定义状态转移函数：设 I 是文法G任一项目集，X为一文法符号，GO(I,X)=closure(J)J=A X.|A.XI 比如：GO(I0,S)=closure(SS.)=SS.=I1GO(I0,a)=closure(Aa.Ab,Ba.Bb)=Aa.Ab,Ba.Bb,A.aAb,A.c,B.aBb,B.d,=I465/124
33、65结构识别文法活前缀结构识别文法活前缀结构识别文法活前缀结构识别文法活前缀DFADFA方法：方法：方法：方法：(1)求识别文法活前缀求识别文法活前缀DFA状态集状态集（LR(0)LR(0)项目集规范族）项目集规范族）项目集规范族）项目集规范族）procedure item(G)beginc:=closure(S.S);得初态集得初态集repeat for c中每一个项目集中每一个项目集I和和G每一个符号每一个符号X doif GO(I,X)非空且不属于非空且不属于c then 把把GO(I,X)放入放入c 族中族中until c不再增大不再增大end;(2)状态转移函数状态转移函数GO把全部
34、项目集联成一张把全部项目集联成一张DFA66/12466比如：67/124674、LR(0)分析表结构若一个文法G拓广文法GLR(0)项目集规范族中每个项目集，不含有：移进归约冲突归约归约冲突则称G是一个LR(0)文法。输入：识别输入：识别LR(0)文法规范句型活前缀文法规范句型活前缀DFA输出：文法输出：文法GLR(0)分析表分析表68/12468方法：方法：用整数0,1,2 ,n 分别表示I0,I1,In；令包含S.S项目标集合Ik为分析表初始状态。若项目A.X属于Ik，且GO(Ik,X)=Ij，当x为终止符时，置ACTIONk,x=Sj；当X为非终止符时，则置GOTOk,X=j。若项目A
35、.属于Ik，设A为文法第j条产生式，则对任何终止符和结束符(记为a），置ACTIONk,a=rj 。若项目SS.属于Ik，则置ACTIONk,#=acc 分析表中不能用规则填入信息均置为犯错。69/12469S670/12470比如：文法GS:S(S)|a 拓广：(0)SS(1)S(S)(2)Sa71/12471比较比较比较比较返回返回返回返回72/12472三、SLR(1)分析法因为LR(0)文法要求每一个LR(0)项目集都不含有冲突项目，这个条件 比较苛刻。对于大多数程序设计语言来说，普通都不能满足LR(0)文法条件，即使简单算术表示式文法也不是LR(0)文法。无法处理冲突，向前查看一个输
36、入符号。比如：EE+T|TTT*F|FF(E)|id73/12473将文法拓广并对规则编号：将文法拓广并对规则编号：将文法拓广并对规则编号：将文法拓广并对规则编号：0.EE0.EE 1.EE+T 1.EE+T 2.ET 2.ET3.TT*F3.TT*F 4.TF 4.TF 5.F(E)5.F(E)6.Fid 6.Fid74/12474#75/12475普通，若I 中有m个移进项目和n个归约项目时：I =A1 1.a11,B11.,A2 2.a22,B22.,Am m.amm,Bnn.对全部移进项目向前查看一符号集合a1,a2,am和Follow(B1),Follow(B2),Follow(Bn
37、)两两不相交时，则项目集I 中冲突能够按以下标准处理。设a 是下一个输入符号：若a a1,a2,am,则移进。若aFollow(Bi),则用产生式Bii归约。其它报错。76/12476这种处理冲突方法称为SLR(1)方法。假如LR(0)项目集中全部冲突都能够用SLR(1)方法处理问题，此文法称为SLR(1)文法。结构结构SLR(1)分析表方法：分析表方法：同LR(0)分析表结构方法相同。若项目A.属于Ik，设A为文法第j条产生式，则对任何属于Follow(A)输入符号a ，置ACTIONk,a=rj 。当a1,a2,am Follow(Bi),表示不能用SLR(1)处理冲突。77/12477比
38、如：比如：I2=ET.,TT.*F 因为因为Follow(E)=+,),#+,),#*=，所以当面临输，所以当面临输入符号入符号+,),#时，用产生式时，用产生式ET 归约，而当面临输入符归约，而当面临输入符号号*时，则移进。时，则移进。I9=EE+T.,TT.*F 类似。类似。#78/12478例例1：对以下文法：对以下文法：(0)SS(1)SbRST(2)SbR(3)RdSa(4)Re(5)TfRa (6)Tf求各非终止符求各非终止符First和和Follow集合。集合。结构该文法结构该文法SLR(1)分析表。分析表。解：解：FirstFollow Sb#Sb a,f,#Rd,ea,b,f
39、,#Tfa,f,#79/1247980/12480ACTIONACTIONGOTOGOTOa ab bd de ef f#S SR RT T0 0S S3 31 11 1accacc2 2r r2 2S S3 3r r2 2r r2 25 53 3S S6 6S S4 42 24 4r r4 4r r4 4r r4 4r r4 45 5S S10109 96 6S S3 37 77 7S S8 88 8r r3 3r r3 3r r3 3r r3 39 9r r1 1r r1 1r r1 11010r r6 6S S6 6S S4 4r r6 6r r6 611111111S S1212121
40、2r r5 5r r5 5r r5 581/12481例例2.有文法有文法GA:AaABe|BaBdB|该文法是否是该文法是否是SLR(1)文法？证实之。文法？证实之。解：将文法拓广为解：将文法拓广为GS(0)SA(1)AaABe(2)ABa(3)BdB(4)B该文法该文法LR(0)项目有：项目有：S.A SA.A.aABe Aa.ABe AaA.Be AaAB.e AaABe.A.Ba AB.a ABa.B.dB Bd.B BdB.B.82/12482Follow(B)=a,eFollow(B)=a,e不是不是不是不是SLR(1)SLR(1)文法文法文法文法SASAAaABeAaABeABa
41、ABaBdBBdBBB 无法用无法用无法用无法用SLR(1)SLR(1)处处处处理冲突理冲突理冲突理冲突无法用无法用无法用无法用SLR(1)SLR(1)处处处处理冲突理冲突理冲突理冲突能够用能够用能够用能够用SLR(1)SLR(1)处理冲处理冲处理冲处理冲突突突突能够用能够用能够用能够用SLR(1)SLR(1)处理冲处理冲处理冲处理冲突突突突83/12483例例例例3.3.设有拓广文法设有拓广文法设有拓广文法设有拓广文法G:G:(0)SS(0)SS(1)SL=R(1)SL=R(2)SR(2)SR(3)L*R(3)L*R(4)Li(4)Li(5)RL(5)RLFollow(R)=Follow(R
42、)=,#=,#=，所以，所以，所以，所以，I I2 2冲突不能冲突不能冲突不能冲突不能 用用用用SLR(1)SLR(1)方法方法方法方法处理。需要功效更强处理。需要功效更强处理。需要功效更强处理。需要功效更强LRLR分析法，分析法，分析法，分析法，即即即即LR(1)LR(1)分析法来处理。分析法来处理。分析法来处理。分析法来处理。84/12484四、规范LR(1)分析法1、LR(1)项目集LR(1)分析法基本思想：分析法基本思想：向前查看一个输入符号，增加展望信息来处理冲突。LR(1)项目集：项目集：一个LR(1)项目集是一个二元组A.,a，当时，展望符（搜索符）a无意义。当=时，展望符 a明
43、确指出，当A.,a是栈顶状态一个LR(1)项目时，仅在输入符号是 a时才能用A 归约，而不是对Follow(A)中全部符号都用A 归约。85/124852、上下文无关文法、上下文无关文法=LR(1)项目集规范族项目集规范族定义闭包函数：定义闭包函数：设设I是一个是一个LR(1)项目集，项目集，Iclosure(I)定义为：定义为：lI中任何中任何LR(1)项目都属于项目都属于closure(I)l若项目若项目A.B，a属于属于closure(I)，B是一个产生式，那么，对于是一个产生式，那么，对于First(a)中每一中每一个终止符个终止符b，假如，假如B.，b不在不在 closure(I)中
44、，则把它加进去。中，则把它加进去。l重复上述过程，直到重复上述过程，直到closure(I)不再增大为止。不再增大为止。86/12486例：文法G为：(0)SS(1)SL=R(2)SR(3)L*R(4)Li(5)RLI=S.S,#Closure(I)=S.S,#,S.L=R,#,S.R,#,L.*R,=/#,L.i,=/#,R.L,#=I0First(#)=#First(#)=#First(=R#)=First(=R#)=First(#)=#First(#)=#First(#)=#First(#)=#87/12487定义状态转移函数：定义状态转移函数：设 I 是一个LR(1)项目集，X为一文法
45、符号，GO(I,X)=closure(J)J=A X.，a|A.X,a I 比如：求GO(I0,L)=closure(SL.=R,#,RL.,#)=SL.=R,#,RL.,#=I288/12488LR(1)项目集族结构方法：procedure item(G)beginc:=closure(S.S，#);得初态集得初态集repeat for c中每一个项目集中每一个项目集I和和G每一个符号每一个符号X doif GO(I,X)非空且不属于非空且不属于c then 把把GO(I,X)放入放入c 族中族中until c不再增大不再增大end;89/124893、规范LR(1)分析表结构方法输入：LR
46、(1)项目集族输出：规范LR(1)分析表90/12490方法：若项目A.X,a属于Ik，且GO(Ik,X)=Ij，当x为终止符a时，置ACTIONk,a=Sj；当X为非终止符时，则置GOTOk,X=j。若归约项目A.,a属于Ik，设A为文法第j条产生式，则置ACTIONk,a=rj 。若项目SS.,#属于Ik，则置ACTIONk,#=acc 分析表中不能用规则填入信息均置为犯错。91/12491(0)SS0)SS(1)SL=R(1)SL=R(2)SR(2)SR(3)L*R(3)L*R(4)Li(4)Li(5)RL(5)RL92/12492(0)SS(0)SS (1)SL=R (2)SR (1)
47、SL=R (2)SR(3)L*R(3)L*R (4)Li (4)Li (5)RL (5)RL*93/12493例：文法GS:S(S)|a 拓广：(0)SS(1)S(S)(2)Sa试结构它LR(1)项目集DFA和LR(1)分析表。解：(S).,$S).,$a.,a.,)94/12494比较比较比较比较a.,a.,)(S).S).$95/12495五、LALR分析法（LookaheadLR分析法）（介于SLR(1)和LR(1)分析法之间一个分析法）LR(1)分析法即使能够处理SLR(1)分析法难以处理移进归约或归约归约冲突，不过，对同一个文法来说，当搜索符不一样时，同一个项目集被分裂成多个项目集从
48、而引发状态数猛烈增加，造成时间和空间开销增加，应用也受到限制。能不能找到一个状态数少，又能处理SLR(1)冲突分析法呢？=LALR分析法。96/124961、LALR(1)分析法基本思想假如两个LR(1)项目集除搜索符不一样外，关键部分是相同，称这两个LR(1)项目集同心。LALR(1)分析法基本思想是将LR(1)项目集规范族中全部同心项目集合并为一。97/12497*合并：合并：合并：合并：I I4 4I I1111=I=I411411=I=I4 4I I5 5I I1212=I=I512512=Li.,=/$=Li.,=/$I I7 7I I1313=I=I713713=L*R.,=/$=
49、L*R.,=/$I I8 8I I1010=I=I810810=RL.,=/$=RL.,=/$(0)SS(0)SS (1)SL=R (1)SL=R (2)SR(2)SR(3)L*R(3)L*R (4)Li(4)Li (5)RL(5)RL=/$=/$98/12498怎样求合并后转移函数？并集转移就是各自转移并。怎样求合并后转移函数？并集转移就是各自转移并。怎样求合并后转移函数？并集转移就是各自转移并。怎样求合并后转移函数？并集转移就是各自转移并。若：Jk=I1I2 In则：GO(IGO(Ik k,x),x)=GO(I=GO(I1 1,x),x)GO(I GO(I2 2,x),x)GO(I GO(
50、In n,x),x)比如：GO(I411,i)=GO(I4,i)GO(I11,i)=I5I12=I512GO(I411,R)=GO(I4,R)GO(I11 R)=I7I13=I713GO(I411,*)=GO(I4,*)GO(I11,*)=I4I11=I41199/12499注意：注意：合并同心集可能产生新冲突，它不可能是移进归约冲突，它只可能是归约归约冲突。反证：假设反证：假设LR(1)文法合并同心集后产生移进文法合并同心集后产生移进归约冲突归约冲突Iij=A.,a/a B.a ,b/b 合并前：合并前：Ii=A.,a B.a ,b Ij=A.,a B.a ,b 合并前就存在移进合并前就存在
