工大编译原理课件-复习

1、复习LL(1)预测分析法1.工作原理 栈顶是终结符匹配 非终结符查表，候选式入栈核心分析表的构造 非空产生式：看FIRST集 空产生式：看FOLLOW集2022/9/921. 改造文法：消除二义性、消除左递归、提取左因子2. 求每个候选式的FIRST集和变量的FOLLOW集3. 检查是不是 LL(1) 文法 若不是 LL(1),说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”4. 构造预测分析表5. 实现预测分析器预测分析法的实现步骤复习递归下降分析法掌握其实现原理 终结符-匹配 非终结符递归调用由文法直接写由状态图，编写例：文法GA：ABBX|BAXXa|Xb|a|b构造其L

2、L（1）分析表消除左递归AB BXB B ABB XaX X bX X aXX bX|X a,b abab FIRSTFIRST(A)=FIRST(B)=a,bFIRST(B)=, FIRST(X)=a,bFIRST(X)=a,b, Follow(A)=,$Follow(B)=,$Follow(B)=,$Follow(X)=Follow(X)=是不是LL（1）文法？结论：不是LL（1）文法 a b $A AB B BXB BXB B B AB B B X XaX X bX X X aX X bX X LL（1）分析表所有的文法都能构造出LL（1）分析表，只有LL（1）文法的分析表不存在冲突Sc

3、hool of Computer Science & Technology Harbin Institute of Technology重点：自底向上分析的基本思想，算符优先分析法的基本思想，简单算符优先分析法。LR 分析器的基本构造思想，LR分析算法，规范句型活前缀及其识别器DFA，LR(0)分析表的构造，SLR(1)分析表的构造, LR(1)分析表的构造。第五章 自底向上的语法分析难点：规范句型活前缀，LR项目集闭包与项目集规范族。 2022/9/98第5章自底向上的语法分析 5.1 自底向上的语法分析概述5.2 算符优先分析法5.3 LR分析法5.4 语法分析程序的自动生成工具Yacc5

4、.5 本章小结2022/9/995.1 自底向上的语法分析概述思想自左向右逐个扫描输入串，一边把输入符号移入分析栈,一边检查位于栈顶的一串符号是否与某个产生式的右部相同.如果相同,就把栈顶的这串符号归约为左部的非终结符； 不同，则继续移入输入符号，进行判断。上述过程一直重复到输入串结束，栈内恰好为S。概括为：移入归约核心寻找句型中的当前归约对象“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法5.1 自底向上的语法分析概述2022/9/911例5.1 一个简单的归约过程设文法G为：SaABe AAb|b Bd语法树的形成过程句子分析： abbdeaAbdeaAde aABe S句子

5、abbde的归约过程(最左归约）a b b d eAAB S对应的最右推导:S=aABe=aAde=aAbde=abbde 栈 a b A b A d B e s存在的问题：在第 步归约时，有两种可能： AAb 和Ab分析栈的情况如图： b A a例5.1 一个简单的归约过程a b b d eAAB正确地选择归约的符号串很重要-句柄现在看看用Ab归约的情况2022/9/915EE*E+EEaaa关于语法树的几点结论短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。短语：a , a , a , a+a, a+a*a2022/9/916EE*E+EEaaa关于语法树的几点结论直接

6、短语：a , a , a , 直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。2022/9/917EE*E+EEaaa关于语法树的几点结论句柄：a 句柄：一个句型的分析树中最左面的直接短语例5.2：证明T/（E-T）*F+i是句型，并指出其所包含的短语、直接短语和句柄E=E+T=E+i=E+F=T+i=T*F+i=T/F*F+i=T/(E)*F+i=T/(E-T)*F+i （E-T），T/（E-T），T/（E-T）*F，i, T/（E-T）*F+i短语：E-T， 直接短语:E-T, i句柄：E-T2022/9/9195.1.1 移进-归约分析系统框架采用表驱动的方

7、式实现输入缓冲区：保存输入符号串分析栈：保存语法符号已经得到的那部分分析结果控制程序：控制分析过程，输出分析结果产生式序列格局：栈+输入缓冲区剩余内容=“句型”2022/9/920移进-归约语法分析器的总体结构 id + id id #移进-归约控制程序输出产生式序列栈内容+输入缓冲区内容 # “当前句型 ” #栈输入缓冲区 分析表M2022/9/921移进-归约分析的工作过程系统运行开始格局栈：#；输入缓冲区：w#存放已经分析出来的结果,并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈问题：系统如何发现句柄在栈顶形成？正常结束: 栈中为 #S，输入缓冲区只有 #例

8、5.3：考虑文法： EE+T|T TT*F|F F(E)|idid1*id2+id3的分析过程如下：移进-归约分析的工作过程步骤符号栈输入串动作0 #id1*id2+id3 # prepare1#id1*id2+id3 #移入 2#F*id2+id3 #归约Fid3#T *id2+id3 #归约TF4#T* id2+id3 # 移进5#T* id2 +id3 #移进6#T*F +id3 #归约Fid 7#T +id3 # 归约TT*F8#E +id3 # 归约ET9#E+ id3 #移入10 #E+id3#移入11#E+F#归约Fid12#E+T#归约TF13#E#归约EE+T14 #E#ac

9、cess2022/9/924分析器的四种动作1) 移进：将下一输入符号移入栈2) 归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）3) 接受：分析成功4) 出错：出错处理？决定移进和归约的依据是什么回头看是否可以找到答案2022/9/925移进-归约分析中的问题1) 移进归约冲突 例5.3中的 3)可以移进 * 或按产生式ET归约 2) 归约归约冲突 例5.3中的 6)可以按产生式ET*F归约,也可以按产生式TF归约存在两个可用的产生式各种分析方法处理冲突的方法不同如何识别句柄？如何保证找到的直接短语是最左的? 如何确定句柄的开始处与结束处？移进-归约分析中的问题 优先法状态法202

10、2/9/95.1.2 优先法根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同优先的句柄两端符号的优先级要高于句柄外与之相邻的符号a1ai-1aiai+1aj-1ajaj+1an定义了这种优先关系之后，语法分析程序就可以通过ai-1ai和ajaj+1这两个关系来确定句柄的头和尾了 2022/9/928根据句柄的识别状态（句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态例如： SbBB可分解为如下识别状态S.bBB 移进bSb.BB 等待归约出BSbB.B 等待归约出BSbBB. 归约采用这种方法，语

11、法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约。 5.1.3 状态法2022/9/9295.2 算符优先分析法算术表达式分析的启示算符优先关系的直观意义+ * + 的优先级低于 *( ) ( 的优先级等于 )+ + + 的优先级高于 +方法将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄2022/9/930算符文法如果文法G=（ V，T，P，S）中不存在形如ABC 的产生式，则称之为算符文法(OG Operator Grammar)即：如果文法 中不存在具有相邻非终结符的产生式，则称为算符文法。 相邻 若S= ab 或 S= aQb , 称a,b相邻例:E

12、E+T T+T F+T a +T a + T * Fa +F*F a + a *F a + a * a只有相邻的终结符之间才会有关系2022/9/932定义5.1 假设G是一个不含-产生式的文法，A、B和C均是G的语法变量，G的任何一对终结符a和b之间的优先关系定义为： ab，当且仅当文法G中含有形如Aab或AaBb的产生式； ab，当且仅当文法G中含有形如AaB的产生式，而且B=b或B=Cb； ab，当且仅当文法G中含有形如ABb的产生式，而且B=a或B=aC； a与b无关系，当且仅当a与b在G的任何句型中都不相邻。#后于所有的终结符归约5.2.1 算符优先文法2022/9/9335.2.1

13、 算符优先文法问题：什么是算符优先文法？设G=（V，T，P，S）为OG，如果 a,bVT, ab, ab, ab 至多有一个成立，则称之为算符优先文法(OPG Operator Precedence Grammar)。2022/9/9345.2.2 算符优先矩阵的构造优先关系的确定根据优先关系的定义ab AaBP且(B+b或者B+Cb)需要求出非终结符B派生出的第一个终结符集ab ABbP且(B+a或者B+aC)需要求出非终结符B派生出的最后一个终结符集设G=（V，T，P，S）为OG，则定义FIRSTOP(A)=b|A+b或者A+Bb,bT,B VLASTOP(A)=b|A+b或者A+bB,b

14、T,B V2022/9/935算符优先关系矩阵的构造Aab ; AaBb, 则abAaB,则对bFIRSTOP(B),abABb,则对aLASTOP(B), ab求FIRSTOP的算法1.若有产生式，Aa 或ABa，则 aFIRSTOP（A）2.if ABP,then FIRSTOP(B) FIRSTOP(A)同理，可构造LASTOP的算法FIRSTOP(E)=+，-，*，/，（，iFIRSTOP(T)=*，/，（，i FIRSTOP(F)=（，i LASTOP(E)=+，-，*，/，)，ILASTOP(T)=*，/，)，iLASTOP(F)=)，i文法G(E):EE+T|E-T|T TT*F

15、|T/F|F F (E)|i2022/9/937构造算符优先关系矩阵的算法AX1X2Xn如果XiXi+1TT则： XiXi+1如果XiXi+1Xi+2TVT则：XiXi+2如果XiXi+1TV则：aFIRSTOP(Xi+1)，Xia如果XiXi+1VT则：aLASTOP(Xi)， aXi+1例5.4：文法G（S）： S （A）|a AA+S|S求算符优先矩阵解：FIRSTOP（S）=a,( FIRSTOP（A）=+,a,( LASTOP(S)=a,) LASTOP(A)=+,a,) S （A） a + ( ) a + ( )（) S （A）=S （A） (=)AA+SAA+SLASTOP(A)

16、=a,+,).+.FIRSTOP(S)=a,(2022/9/940例 5.5 表达式文法的算符优先关系 acc+-*/()id#+-*/（）id# 2022/9/9415.2.3 算符优先分析算法 原理识别句柄并归约各种优先关系存放在算符优先分析表中利用识别句柄尾，利用识别句柄头，分析栈存放已识别部分，比较栈顶和下一输入符号的关系，如果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出句柄，归约为非终结符。例5.6句子id+id*id的识别过程句子id+id*id# ，分析过程如下 栈 关系 输入 动作 序号# +id*id# 归约 1 # F +id*id# 移进 2# F+ *id# 归约 4#

17、 F+F *id# 移进 5# F+F * # 归约 7# F+F * F # 归约 8# F+T # 归约 9# E # 接受 102022/9/943问题有时未归约真正的句柄（F）不是严格的最左归约归约的符号串有时与产生式右部不同仍能正确识别句子的原因OPG未定义非终结符之间的优先关系，不能识别由单非终结符组成的句柄定义算符优先分析过程识别的“句柄”为最左素短语LPP（Leftmost Prime Phase）2022/9/944素短语与最左素短语什么是素短语？当前我们要找什么样的短语？ 它首先是一个短语至少含有一个终结符除自身外，不再含有其它的素短语2022/9/945例EE+T|T T

18、T*F|F F(E)|id句型 T+T*F+i 的短语有T T*F i T+T*F T+T*F+i其中的素短语为T*F iT*F为最左素短语，是被归约的对象问题：按照文法EE+E|E*E|(E)|id，求i+E*i+i的短语和素短语 E E T TE FT + T * F + i2022/9/946文法：EE+E|E*E E(E)|id句型i+E*i+i的短语 E E EE E Ei + E * i + i问题：归约过程中如何发现“中间句型” 的最左素短语？i i E*i i i+E*i i+E*i+i其中的素短语为i i i2022/9/947素短语与最左素短语设句型的一般形式为#N1a1

19、N2a2 Nnan # (Ni V,ai VT）它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1 Njaj Nj+1其中：ai-1ai,， aiai+1aj-1aj ， ajaj+12022/9/948算符优先分析的实现系统组成移进归约分析器 + 优先关系表分析算法参照输入串、优先关系表，完成一系列归约，生成语法分析树输出产生式2022/9/949算符优先分析算法 算法5.3 算符优先分析算法。输入：文法G=(V, T, P, S)，输入字符串w和优先关系表;输出：如果w是一个句子则输出一个分析树架子，否则指出错误;步骤：beginS1:=#; i:=1;repeat 将下一输

20、入符号读入R; if SiT then j:=i else j:=i-1; while SjR do beginrepeat Q:=Sj;if Sj-1T then j:=j-1 else j:=j-2until SjQ;将Sj+1Si归约为N; i:=j+1;Si:=N end; if SjR or SjR then begin i:=i+1; Si:=R end else erroruntil i=2 and R=# end;2022/9/950id+id*id 的分析过程id + id * id #算符优先分析控制器E idE idE idE E * EE E + E算符优先关系表#id

21、#+#id+#+#*+#id*+#*+#+#2022/9/9515.2.4 优先函数为了节省存储空间（n2 2n）和便于执行比较运算，用两个优先函数f和g，它们是从终结符号到整数的映射。对于终结符号a和b选择f和g，使之满足： f(a)g(b)，如果a b。损失错误检测能力降低如：id id不存在，但f(id)g(id)可比较2022/9/952表5.2 对应的优先函数：1) 构造优先函数的算法不是唯一的。2) 存在一组优先函数，那就存在无穷组优先函数。3）就是说优先函数不唯一。+-*/()id#f22440440g113350502022/9/953优先函数的构造算法5.4 优先函数的构造。

22、输入：算符优先矩阵;输出：表示输入矩阵的优先函数，或指出其不存在;步骤：1. 对aT#，建立以fa和ga为标记的顶点；2. 对a, bT#，若ab或者ab，则从fa至gb画一条有向弧；若ab或者ab，则从gb至fa画一条有向弧；3. 如果构造的有向图中有环路，则说明不存在优先函数；如果没有环路，则对aT#，将f(a)设为从fa开始的最长路经的长度，将g(a)设为从ga开始的最长路经的长度。 gidfidf*g*g+f+f#g#根据Ges的优先矩阵建立的有向图和优先函数 2022/9/9555.2.5 算符优先分析的出错处理 栈顶的终结符号和当前输入符号之间不存在任何优先关系； 发现被“归约对象

23、”，但该“归约对象”不能满足归约要求。对于第种情况，为了进行错误恢复，必须修改栈、输入或两者都修改。对于优先矩阵中的每个空白项，必须指定一个出错处理程序，而且同一程序可用在多个地方。对于第种情况，由于找不到与“归约对象”匹配的产生式右部，分析器可以继续将这些符号弹出栈，而不执行任何语义动作。2022/9/956算符优先分析法小结优点简单、效率高能够处理部分二义性文法缺点文法书写限制大强调算符之间的优先关系的唯一性占用内存空间大不规范、存在查不到的语法错误算法在发现最左素短语的尾时，需要回头寻找对应的头2022/9/9575.3 LR分析法5.3.1 LR分析算法LR(k)分析法可分析LR(k)

24、文法产生的语言L ：从左到右扫描输入符号R ：最右推导对应的最左归约k ：超前读入k个符号，以便确定归约用的产生式使用语言的文法描述内涵解决句柄的识别问题，从语言的形式描述入手，为语法分析器的自动生成提供了前提和基础 LR分析器的工作方式：根据栈中的符号串和向右顺序查看输入串中的k(k0)个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。 LR分析方法是当前最广义的无回溯的“移进- 归约”方法。LR(k)分析技术knuth于1965年首先提出来的 优点：适用范围广；分析速度快；报错准确。5.3 LR分析法2022/9/959LR语法分析器的总体结构a1 ai an #L

25、R分析程序动作表action转移表goto产生式序列状态/符号栈输入缓冲区分析表SmSm-1S1S0XmXm-1X1#所有LR分析器的驱动程序都是一样的不同的语法分析器具有不同的分析表LR语法分析器的总体结构LR(0)分析器 = LR（0）分析表 SLR（1）分析器 = SLR（1）分析表LR（1）分析器 = LR（1）分析表LALR（1）分析器 = LALR（1）分析表分析表是LR分析法的核心例5.7文法 GE: (0) E E (1) E E +T (2) E T (3) T T*F (4) T F的分析表LR 分析表ACTION文法G（E）的SLR（1）分析表GOTOLR 分析表约定：s

26、n:将符号a、状态n压入栈rn:用第n个产生式进行归约LR(0)、SLR(1)、LR(1)、LALR(1)将以不同的原则构造这张分析表2022/9/964LR分析器的工作过程1. 初始化 s0 # a1a2an# 对应“句型” a1a2an2. 在一般情况下，假设分析器的格局如下： s0s1 sm #X1Xm aiai+1an# 对应“句型” X1Xmaiai+1an格局:(栈中符号序列，剩余输入符号串）LR分析器操作1.If actionsm,ai= sj then 格局变为s0s1 smj #X1Xmai ai+1an# 对应“句型” X1Xmaiai+1an2.If actionsm,a

27、i= ri then 表示用第i个产生式AXm-(k-1)Xm进行归约，格局变为:.归约前：s0s1. sm-k sm-(k-1) .sm #X1Xm-kXm-(k-1).Xm-k aiai+1an#2022/9/966.状态栈的变化查goto表，如果gotosm-k,A=i then 格局变为s0s1 sm-k i #X1Xm-kA aiai+1an#. 状态栈文法栈同时弹出后，栈内的情况：s0s1 sm-k #X1Xm-k aiai+1an#LR分析器的操作. 将归约后的非终结符A压入栈：s0s1 sm-k #X1Xm-kA aiai+1an#2022/9/9673.If actionsm

28、,ai=acc then 分析成功4.If actionsm,ai=err then 出现语法错LR分析器的操作2022/9/968LR分析算法 算法5.5 LR分析算法。输入：文法G的LR分析表和输入串w;输出：如果wL(G)，则输出w的自底向上分析，否则报错;步骤：1将#和初始状态S0压入栈，将w#放入输入缓冲区；2令输入指针ip指向w#的第一个符号；3令S是栈顶状态，a是ip所指向的符号;4repeat5if actionS,a=Si then /* Si表示移进a并转入状态i*/6 begin7 把符号a和状态i先后压入栈；8 令ip指向下一输入符号9 end2022/9/969 10

29、elseif actionS,a=rithen /* ri表示按第i个产生式A归约 */11 begin12 从栈顶弹出2*|个符号；13 令S是现在的栈顶状态；14 把A和gotoS,A先后压入栈中；15 输出产生式 A16 end17elseif actionS,a= acc then18 return19else20 error();例：id+id*id的识别过程id + id * id #0#S5 5 idr6 F-idgoto0,F=3 F 3 Tr4 T-Fgoto0,T=2r2 E-Tgoto0,E=12 S6 S5 6 + F E1 r6 F-id goto6,F=3 7 *

30、5 id F 10 5 id F 3 T r4 T-F goto6,T=9 S7 S5 r6 F-id goto4,F=10 r3 T-T*F goto6,T=9 r1 E-E*T goto0,E=19 T 9 E 1 栈 输入 动作0 # id+id*id# s5 05 #id +id*id# r6 Fid 0 #F +id*id# GOTO0,F=303 #F + id*id# r4 TF0 #T +id *id# GOTO0,T=302 #T +id *id# r2 ET0 #E +id*id# GOTO0,E=101 #E +id*id # S6016 #E+ id*id # S501

31、65 #E+id * id # r6 Fid 016 #E+ F * id # GOTO6,F=3 栈 输入 动作0163 #E+ F * id # r4 TF016 #E+ T * id # GOTO6,T=90169 #E+T * id # S7 01697 #E+ T* id # S501697 #E+ T* F # GOTO7,F=10016 #E+ T # GOTO6,T=90 #E # GOTO0,E=10169 #E+T # r1 EE+T 0169710 #E+ T* F # r3 TT*F 016975 #E+ T* id # r6 Fid 01 #E # accep2022

32、/9/973规范句型活前缀分析栈中内容+剩余输入符号=规范句型分析栈中内容为某一句型的前缀来自分析栈的活前缀(Active Prefix)不含句柄右侧任意符号的规范句型的前缀例：id + id * id 的分析中活前缀S *rmAw rm 12w 0165 #E+id * id # r6 Fid 2022/9/974对于文法G4.31.SvI:T2.II,i3.Ii4.TrealV i,i:real是该文法的一个句子S=vI:T=vI:real =vI,i:real =v i,i:real规范句型活前缀 V i , i : real $其活前缀是: $vi,ivI,ivivvI,vIvI:vI

33、:realvI:TS I IvIreal: T S2022/9/976规范句型活前缀规范归约所得到的规范句型(Canonical Sentential Form)的活前缀是出现在分析栈中的符号串，所以，不会出现句柄之后的任何字符，而且相应的后缀正是输入串中还未处理的终结符号串。活前缀与句柄的关系不含句柄的任何符号A.包含句柄 A.包含句柄的部分符号A1.2 识别句柄就可以转化为识别活前缀LR分析器如何识别各规范句型的活前缀?LR分析器使用有穷自动机DFA识别各规范句型的活前缀。DFA的定义：M=（Q,q0,Z)其中：Q-状态集 输入字母表 -Qx Q的映射函数确切说，就是找Q的过程规范句型活前

34、缀2022/9/9785.3.2 LR(0)分析表的构造LR(0)项目从产生式寻找归约方法右部某个位置标有园点的产生式称为相应文法的LR(0)项目（Item）例 S.bBB SbB.B Sb.BB SbBB.归约（Reduce）项目: SaBB.移进（Shift）项目：S.bBB待约项目：Sb.BB SbB.B2022/9/979拓广(Augmented)文法需要一个对“归约成S” 的表示（只有一个接受状态）文法 G= (V, T, P, S)的拓广文法 G：G=（V S，T，P SS，S）SV对应S.S（分析开始）和SS.（分析成功）例5.13 ，拓广后文法为：0) SS1) SBB2) B

35、aB3) Bb文法的项目1.S.S 2.SS.3.S.BB 4.SB.B 5.SBB.6.B.aB 7.Ba.B 8.BaB.9.B.b 10.Bb.其中：移入项目：6，9待约项目：3，4，7归约项目：5，8，10开始项目：1接收项目：2问题：这些项目有没有可合并的？合并的条件又是什么？有效项目集和转移函数定义:(识别活前缀的有效项目) 如果存在一个规范推导 S Aw 12w项目A12对识别活前缀=1是有效的。*rmrm有下面的结论：若项目AB对识别活前缀 =是有效的,且BP,则项目B 对识别活前缀 =也是有效的. 有效项目集和转移函数1.S.S 3.S.BB对活前缀有效SB.BS.BBB.a

36、BB.b对活前缀B有效推导如下：若项目AB对识别活前缀 =是有效，则存在一个规范推导 S Aw Bw设w x w , 则对任何BP ，有 S Aw Bw B x w x w *rmrm*rm*rmrm*rmrm有效项目集和转移函数2022/9/984例4-13S SSBBBaBBb的有效项目集I0:S.SS.BBB.aBB.bI1:SS.I2:SB.BB.aBB.bI4:Ba.BB.aBB.bI3:Bb.I5:SBB.I6:BaB.有效项目集和转移函数2022/9/985项目集 I 的闭包（Closure）CLOSURE(I)=I B.| A .BI, BP 算法 J:=I;repeat J=

37、JB.|A.BJ, BPuntil J不再扩大项目集闭包的计算2022/9/986闭包之间的转移后继项目（Successive Item）A.X的后继项目是AX.闭包之间的转移go(I,X)=CLOSURE(AX.| A.XI2022/9/987状态转移的计算确定在某状态遇到一个文法符号后的状态转移目标function GO(I, X);beginJ:=;for I中每个形如A.X的项目dobegin J:=JAX. end;return CLOSURE(J)end; 2022/9/988识别拓广文法所有规范句型活前缀的DFA识别文法G=（V，T，P，S）的拓广文法G的所有规范句型活前缀的DF

38、A :M=(C, VT, go, I0, C)I0=CLOSURE(S .SC=I0I|JC,XVT,I=go(J,X)称为G的LR(0)项目集规范族(Canonical Collection)2022/9/989计算LR(0)项目集规范族即：分析器状态集合beginC := closure( S.S); repeat for IC， X VT if go(I,X) & go(I,X)C then C=Cgo(I,X) until C不变化end.2022/9/990例4-13SBBBaBBbI0:S.SS.BBB.aBB.bI1:SS.SBI2:SB.BB.aBB.baI4:Ba.BB.aB

39、B.bbI3:Bb.BI5:SBB.abBI6:BaB.ab核心项目Kernel Item2022/9/991LR(0)分析表的构造算法算法5.6 LR(0)分析表的构造。输入：文法G=(V, T, P, S)的拓广文法G ;输出：G 的LR(0)分析表，即action表和goto表;步骤：1.令I0= CLOSURE(S .S)，构造G 的LR(0)项目集规范族C= I0,I1,In2让Ii对应状态i，I0对应状态0，0为初始状态。3for k=0 to n do begin if A.aIk & aT & GO(Ik, a)=Ij then actionk,a:=Sj; if A.BIk

40、& BV & GO(Ik, B)=Ij then gotok,B:=j; if A.Ik & A为G的第j个产生式then for aT# do actionk,a:=rj; if SS.Ik then actionk,#:=acc end;4上述到步未填入信息的表项均置为error。 2022/9/992LR(0)不是总有效的( S S ) 1) S A|B2) A aAc3) A a4) B bBd5) B b上下文无关文法不是都能用LR(0)方法进行分析的，也就是说，CFG不总是LR(0)文法.2022/9/993I0:S.S S.AS.BA.aAcA.aB.bBdB.bSI1:SS.A

41、I2:SA.BI3:SB.aI4:Aa.AcAa.A.aAcA.abI5:Bb.BdBb.B.bBdB.bAI6:AaA.cabBI7: BbB.dcI8:AaAc.dI7: BbBd.S S S A|BA aAcA aB bBdB b2022/9/994项目集 I 的相容如果 I 中至少含两个归约项目，则称 I 有归约归约冲突（Reduce/Reduce Conflict）如果 I 中既含归约项目，又含移进项目，则称 I 有移进归约冲突（Shift/Reduce Conflict）如果 I 既没有归约归约冲突，又没有移进归约冲突，则称 I 是相容的(Consistent)，否则称 I 是不相

42、容的对文法G，如果 IC,都是相容的，则称G为LR(0)文法2022/9/995I0:S.S S.AS.BA.aAcA.aB.bBdB.bSI1:SS.AI2:SA.BI3:SB.aI4:Aa.AcAa.A.aAcA.abI5:Bb.BdBb.B.bBdB.bAI6:AaA.cabBI7: BbB.dcI8:AaAc.dI7: BbBd.S S S A|BA aAcA aB bBdB b问题:如何构造其分析表?2022/9/9965.3.3 SLR(1)分析表的构造算法 算法5.6 LR(0)分析表的构造。输入：文法G=(V, T, P, S)的拓广文法G;输出：G的LR(0)分析表，即act

43、ion表和goto表;步骤：1.令I0= CLOSURE(S.S)，构造G的LR(0)项目集规范族C= I0,I1,In2让Ii对应状态i，I0对应状态0，0为初始状态。3for k=0 to n do begin if A.aIk & aT & GO(Ik, a)=Ij then actionk,a:=Sj; if A.BIk&BV&GO(Ik, B)=Ij then gotok,B:=j; if A.Ik & A为G的第j个产生式then for aFOLLOW(A) do actionk,a:=rj; if SS.Ik then actionk,#:=acc end;4上述到步未填入信息

44、的表项均置为error。 识别表达式文法的所有活前缀的DFA 拓广文法 0) 1) + 2) 3) * 4) 5) () 6) id2022/9/998I0:E.E E.E+TE.TT.T*FT.FF.(E)F.idEI1:EE. EE.+TTI2:ET.TT.*FFI3:TF.(I4:F(.E )E.E+TE.TT.T*FT.FF.(E)F.ididI5:Fid.+I6:EE+.TT.T*FT.FF.(E)F.id*I7:TT*.FF.(E)F.idEI8:F (E.)EE.+TTF(idTI9:EE+T.TT.*FF(idFI10:TT*F.()I11:F(E).+*id2022/9/99

45、9表达式文法的 LR(0)分析表含有冲突在状态 2、9 采用归约，出现移进归约冲突2022/9/9100表达式文法的SLR(1)分析表求非终结符的 FISRT 集和 FOLLOW 集FIRST( F ) = id, ( FIRST( T ) = id, ( FIRST( E ) = id, ( FOLLOW( E ) = ), +, # FOLLOW( T ) = ), +, #, * FOLLOW( F ) = ), +, #, * 1) + 2) 3) * 4) 5) () 6) id2022/9/9101 si 表示移进到状态i, ri 表示用i号产生式归约2022/9/9102SLR(

46、1) 分析的特点描述能力强于 LL(1) SLR(1)还考虑Follow集中的符号LL(1) 仅考虑产生式的首符号SLR(1) 文法：SLR(1)分析表无冲突的CFG2022/9/9103SLR(1)分析的局限性如果 SLR(1) 分析表仍有多重入口（移进归约冲突或归约归约冲突），则说明该文法不是 SLR(1) 文法；说明仅使用 LR(0) 项目集和 FOLLOW 集还不足以分析这种文法2022/9/9104I0:S.SS.L=RS.RL.*RL.idR.LI1:SS.I2:SL.=RRL.LI3:SR.RI4:L*.RR.LL.*RL.idI5:Lid .*idI6:SL=.RR.L L.*

47、RL.id=I7:L*R.RI8:RL.LI9:SL=R.R*LidS2022/9/9105SLR分析中的冲突需要更强的分析方法 I2 =S L.=R, R L. 输入符号为 = 时，出现了移进归约冲突： S L .=R I2 and go(I2,=)=I6 action2,= = Shift 6 R L . I2 and = FOLLOW(R)=,# action2,= = Reduce R L说明该文法不是SLR(1)文法，分析这种文法需要更多的信息。2022/9/9106SLR分析中存在冲突的原因SLR（1）只孤立地考察输入符号是否属于归约项目A.相关联的集合FOLLOW（A），而没有考

48、察符号串所在规范句型的“上下文”。所以试图用某一产生式A归约栈顶符号串时，不仅要向前扫描一个输入符号，还要查看栈中的符号串，只有当Aa的确构成文法某一规范句型的活前缀时才能用A归约。亦即要考虑归约的有效性：问题：怎样确定Aa是否是文法某一规范句型的活前缀2022/9/91075.3.4 LR(1)分析表的构造LR(0)不考虑后继符(搜索符)，SLR(1)仅在归约时考虑后继符(搜索符)，因此，对后继符(搜索符)所含信息量的利用有限，未考虑栈中内容。希望在构造状态时就考虑后继符(搜索符)的作用：考虑对于产生式 A的归约，不同使用位置的 A 会要求不同的后继符号2022/9/9108后继符(搜索符)

49、的概念EE + T( E )T * F 不同的归约中有不同的后继符。 特定位置的后继符是FOLLOW集的子集2022/9/9109LR(k) 项目定义5.11 A.,a1a2ak为LR（k）项目，根据圆点所处位置的不同又分为三类：归约项目: A.,a1a2ak移进项目：A.a,a1a2ak待约项目：A.B,a1a2ak利用LR(k)项目进行(构造)LR(k)分析(器)，当k=1时，为LR(1)项目，相应的分析叫LR(1)分析(器)2022/9/9110LR(1) 项目的有效性形式上 称LR(1)项目A.,a对活前缀=是有效的，如果存在规范推导S *Aw w其中a为w的首字符，如果w=，则a=#

50、与LR(0)文法类似，识别文法全部活前缀的DFA的每一状态也是用一个LR(1)项目集来表示，为保证分析时，每一步都在栈中得到规范句型的活前缀，应使每一个LR(1)项目集仅由若干个对相应活前缀有效的项目组成2022/9/9111识别文法全部活前缀的DFALR(1) 项目集族的求法CLOSURE（I）：求I的闭包，目的是为了合并某些状态，节省空间GO（I，X）：转移函数2022/9/9112闭包的计算CLOSURE(I)的计算(核心位置：A.B,a 扩展成闭包)同时考虑可能出现的后继符b FIRST( a ) 2022/9/9113闭包的计算如果A.B,a对=有效 /*即存在S*Aaxax*/假定

51、ax*by，则对任意的B有：B.，b对=也是有效的，其中bFIRST（a）2022/9/9114闭包的计算J:=I; repeat J=JB.,b|A.B,aJ, bFIRST(a)until J 不再扩大当+时，此时b=a叫继承的后继符，否则叫自生的后继符2022/9/9115状态 I 和文法符号 X 的转移函数go(I,X) = closure(AX.,a|A.X,aI)2022/9/9116计算LR(1)项目集规范族即：分析器状态集合C=I0I|JC，XVT，I=go(J,X)称为G的LR(1)项目集规范族（算法：P181) beginC:= closure( S.S,#); repea

52、t for IC， X VT if go(I,X) & go(I,X)C then C=Cgo(I,X) until C不变化end.2022/9/9117识别活前缀的关于LR(1) 的DFA识别文法G=（V，T，P，S）的拓广文法G的所有活前缀的DFA M=(C, VT, go, I0, C)I0=CLOSURE(S .S, #如果CFG G的LR(1)分析表无冲突则称G为LR(1)文法。2022/9/9118LR(1) 分析表的构造1令I0= CLOSURE(S.S)，构造C= I0, I1, , In，即G的LR(1)项目集规范族。2从Ii构造状态i，0为初始状态。for k=0 to

53、n dobegin if A.a, bIk & aT & GO(Ik, a)=Ij then actionk,a:=Sj; if GO(Ik, B)=Ij & BV then gotok,B:=j; if A., aIk & A为G的第j个产生式then actionk,a:=rj; if SS., #Ik then actionk,#:=acc;end上述到步未填入信息的表项均置为error。 2022/9/9119LR(1) 分析表的构造与LR(0)的不同点主要在归约动作的选择：LR(0) 分析考虑所有终结符SLR(1) 分析参考 FOLLOW 集LR(1) 分析仅考虑 LR(1)项目中的后继符2022/9/91202022/9/91215.3.