编译原理文法和语言与语法分析.ppt

1、2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 1,高级程序设计语言编译原理,主讲 周有顺 (适用于2008级计算机本科师范专业),2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 2,第四讲文法和语言与语法分析,上下文无关文法(LL文法和LR文法)与语法分析程序设计,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 3,回 忆,语法分析的任务是把词法分析的结果单词符号串进一步分解成各类语法单位 (语法范畴),并分析它们之间的层次关系输出语法树。 语法分析器 由单词符号(终结符)和语法范畴 单词符号串 (语法变量或称非终结符)

2、构成结点 组成的语法树 (词法分析) (创建) (语义分析的原始数据),2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 4,一、文法和形式语言的定义 二、上下文无关文法及其语法树 三、两种语法分析思想的形成 四、自上而下的语法分析方法 五、自下而上的语法分析方法*六、语法分析器的自动产生,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 5,一、文法和形式语言的定义, 回忆：程序语言的词法规则是可用表来描述的，而在词法分析器的讨论和自动产生中，词法是用正规式来描述定义的。 现在：程序语言的语法规则的定义和描述用什么呢？ -文法！,2020年8月16

3、日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 6, 文法与语言 文法是描述语言语法结构的一组形式规则。即是定义符号串（程序）集合（语言）的工具。它必须具备如下特点： 准确又易于理解； 由它定义形成的语言有利于句子分析和翻译； 通过它能自动产生有效的语法分析程序。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 7, 文法与语言 (形式)语言：若L*则称L是上的一个形式语言。其中,是基本符号集(有限集)， *是上基本符号串集(一般为无限集)， 例子： C语言是基本符号字母表上符号串集的子集合，每个C程序都是基本符号字母表上的符号串，是C语言中的一个元素。 假定=a

4、,b,c则L1=a,b,c,L2=a,aa,ab,L3=c,cc可表示字母表上的三个不同的形式语言。这里描述语言的方法是用枚举法。 若=a,b， 上的一个形式语言为上所有可能的符号串集。即L=a,b,ab,ba,aa,bb,此时用枚举法已经无法表示该语言了。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 8, 文法与语言 文法(形式)定义: 我们用四元式来作为描述一个语言L的工具(会发生什么),用G表示。即G(Vt,Vn,P,S)其中: Vt是终结符集合(有限集)-单词符号集合即组成语言的不可再分的基本符号。元素一般用小写英文字母表示。如常量、基本字等。 Vn是非终结

5、符集合(有限集)-用来表示语法范畴的语法变量。往往由它可以生成多个单词符号和其它非终结符等序列。元素一般用大写英文字母表示。如表达式、语句、分程序、过程等。VnVt= S是文法开始符号Vn -特殊非终结符号，它必须至少在某个产生式左端出现一次。它代表所定义语言中我们最终感兴趣语法范畴。 P是产生式(规则式)集合(有限集)-定义语法范畴的一种书写规则。形式：xAyxy A Vn, x,y,(VtVn)* 某即关于A的一条产生规则。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 9, 文法与语言 例子：定义一个语法范畴，有时需要好几个产生式，有时还需要含有递归的产生式。如

6、定义一个算术表达式的产生式如下： G: Ei EE+E EE*E E(E) 其中：i代表单词符号即变量或常数，另+、*、(、)也是单词符号。 + 可见，文法定义了一个语言。记为L(G)=|S=, Vt+, P,Vt = i,+,*,(,) , Vn = E S = E Vn P = 左边列出的产生规则序列,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 10, 文法是定义语言的好工具：只要定义它含哪些语法范畴(Vn),每个语法范畴所含语法单位之间的关系(P),还有基本单词符号集(Vt)，最大的语法范畴是谁(S)。这四元一定，则文法就定义了一个语言-由S和P所能产生出的终

7、结符串集。记为L(G)。即 + L(G)=|S=, Vt* P,? 假定=a,b,而上的一个形式语言L为上所有可能的非空符号串集，则该语言L用文法G怎样来描述。 答：G ( Vt = a,b, Vn = A, S A, P = Aa,Ab,AAa,AAb) 则，L = L(G) 证：A=a|b|Aa|Ab=(a|b)|A(a|b)=(a|b)(a|b)*,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 11, 文法性质类型与语言 一个文法G,若P中任一产生式形如 A ,有AVn, (VnVt)+(或(VnVt)*),则G为(扩充)上下文无关文法。(2型) 一个文法G，若

8、P中任一产生式形如 AB或A 有 A,BVn , Vt+ ，则G为正规文法。 (3型) 一个文法G，若P中任一产生式形如 A 有(VnVt)+,(VnVt)*,仅S例外,但此时S不得出现在任何产生式右部。则G为上下文有关文法。 (1型) 一个文法G，若P中任一产生式形如 B 有,(VnVt)* 且至少含一非终结符,则G为短语文法。(0型),2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 12, 文法性质类型与语言 1型文法G的另种等价定义:若P中任一产生式形如 有(VnVt)+,(VnVt)*, 且|,仅S例外,但此时S不得出现在任何产生式右部。则G为上下文有关文法。

9、可见，不同类型文法有如下关系： 3型文法 2型文法 2型文法 1型文法 0型文法 结论：上下文无关文法推导很自由，语法分析时一定较方便。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 13, 推导、句型、句子和语言 直接推导：x=y G 用一次规则式，替换一个非终结符 + 推导： x=y G 用若干次规则式，替换若干个非终结符 * 广义推导：x=y G 不用(x=y)或用若干次规则式 R 最右推导：x=y (规范推导) G 每次替换x中最右边的非终结符,如：E+E = E+i,如：E+E = i+i,如：E+E = E+E,如： E = E+E = E+i = i+i

10、,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 14, 句型：若有开始符 S=x 的广义推导，则x为G的句型。 G + 句子：若有开始符 S=x 且xVt*，则x为G的句子。 G + 语言：L(G)= x| S=x 且xVt*,则L为G描述的语言。 G 文法的等价：若 L(G1) = L(G2),则 G1 G2 。 正规文法与正规式的等价：若 L(G) = L(A),则 G A 。 正规文法与自动机的等价：若 L(G) = L(M),则 G M 。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 15,二、上下文无关文法及其语法树, 文法的递归

11、性、规范句型、短语与句柄 直接左(右)递归: G中有产生式形如 A A (A A) 左(右)递归、递归 + + A=A (A= A) 递归 + A=A 规范句型:由开始符号可用最右推导得到的句型。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 16, 规范句型:由开始符号可用最右推导得到的句型。 E=(E)=(E+E)=(i+E)=(i+i) 不是最右推导 E=(E)=(E+E)=(E+i)=(i+i) 是最右推导 后者每个句型均为规范句型。 短语: 设G,S且xuy是一句型，并有UVn,使得 * + S=xUy=xuy u(VnVt)+,x,y(VnVt)*, G

12、G 则称子串 u 是句型xuy的短语。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 17, 短语: 设G,S且xuy是一句型，并有UVn,使得 * + S=xUy=xuy u(VnVt)+,x,y(VnVt)*, G G 则称子串 u 是句型xuy的短语。 直接短语: 设G,S且xuy是一句型，并有UVn,使得 * S=xUy=xuy u(VnVt)+,x,y(VnVt)*, G G 则称子串 u 是句型xuy的直接短语(简单短语)。 句柄：一个句型中最左边的直接短语称为句柄。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 18,？ 给出文

13、法G中句子(i*i+i)*i的规范推导过程。并求句型P*(T+i)+i的所有简单短语和句柄。 G: EE+T|T TT*P|P Pi|(E),2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 19, 语义的二义性： 句子的二义性:若该句子有两个不同的规范推导，则称此句子为二义的。例如： (i+i*i) E=(E)=(E+E)=(E+E*E)=(E+E*i)=(E+i*i)=(i+i*i) E=(E)=(E*E)=(E*i)=(E+E*i)=(E+i*i)=(i+i*i) 文法的二义性：若该文法中有二义的句子，则称此文法为二义的。 语言的二义性：若所有描述该语言的文法都具有

14、二义，则称此语言是二义的。 注意：二义性是不可判别的。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 20, 语法树与寻找规范推导-研究分析可行性： 语法树:表示某一句型推导过程的树。(这里并不要求一定是最右推导过程)。 例子： G0: ABaD BbB|b DBaD|d (1)考虑一个推导；(不一定是规范推导) A=BaD=bBaD=bbaD=bbaBaD=bbaBad=bbabad (2)画出语法树。(每个句型的语法树) 语法树的性质和有关结论:,A=BaD=bBaD=bbaD=bbaBaD=bbaBad=bbabad 推导过程的语法树-生长树,| | | | |

15、 | | V,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 21, 语法树与寻找规范推导-研究分析可行性： 语法树:表示某一句型推导过程的树。(这里并不要求一定是最右推导过程)。 例子： G0: ABaD BbB|b DBaD|d (1)考虑一个推导；(不一定是规范推导) A=BaD=bBaD=bbaD=bbaBaD=bbaBad=bbabad (2)画出语法树。(每个句型的语法树) 语法树的性质和有关结论:,bbabad=bBabad=Babad=BaBad=BaBaD=BaD=A 剪枝法-归约过程的语法树-分析树, | | | | | | | |,2020年8月1

16、6日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 22, 语法树的性质和有关结论: 每个句型都有一棵语法树 每棵语法树的叶子组成一个句型 每棵子树的叶子组成一个短语。(如：baD是bbabad的短语) bB是bBabad的短语 每棵简单子树(只有单层分枝的子树)的叶子组成一个直接短语 最左简单子树的叶子组成一个句柄。(如：bB是bBabad的句柄) 用语法树可以证明每一个是句子必有一个规范推导。(用剪枝法)有二义的句子必有两棵以上不同的语法树。如(i+i*i) 用对语法树的剪枝法和语法树性质构造上述例子中句子bbabad的规范推导。,方 法 用语法树的剪枝法(保留树根且剪最左简单子树)得

17、出多个语法树； 用性质构造句型； 用规范推导的定义内容来验证。 得规范推导： A=BaD=BaBaD=BaBad=Babad =bBabad=bbabad,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 23,三、两种语法分析思想的形成, 从构造一个句子的规范推导的过程和生长一棵句子的语法树的过程可得对一个句子的语法分析方法。 自上而下的方法-试长语法树(规范推导)：从开始符号起，根据已知终结符号串，试着去选择产生式，用其右部代替最右边的非终结符号，最后得到的一个句子，若该句子与已知串相同，则合符语法，否则，我们“可以认为”不合语法。 自下而上的方法-归约句柄法(剪枝)

18、：假定一个终结符号串是一个句子，每次归约它的句柄，最终若为文法开始符号，则我们的假定是正确的。即该终结符号串合符语法，否则,我们“可以认为”不合语法。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 24, 几个结论 1. 自下而上语法分析法是规范推导的逆过程即规范归约(最左归约)，其关键是找每个句型的句柄。若找到即可归约成某个非终结符，再继续下去最后能归约到开始符号则句子正确。 自上而下语法分析是规范推导(最右推导)的过程，其关键是选择用来推导的产生式。最后能推导出所要分析的句子则该句子正确。 2. 一个语言可以有不同的文法描述 3. 为了对句子的语法结构进行确定的可

19、行性分析，只考虑也只需考虑规范推导或最左推导。 4. 对于一个程序语言来说，为了对每个语句的分析是唯一的，常希望描述它的文法是无二义的。但是二义文法并非坏事，在一定条件下，可以控制和驾驭。 5. 可以证明二义性问题是不可判定的。 6. O型语言1型语言2型语言3型语言，但文法： 短语文法上下文有关文法上下文无关文法正规文法 短语文法扩充上下文无关文法上下文无关文法 上下文有关文法不一定-扩充上下文无关文法,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 25,四、自上而下的语法分析方法, 递归下降子程序分析法 先对文法加以改造，使分析能正常进行。步骤： (I) 文法变换

20、之一-消除直接、间接左递归(P89有算法) (II) 文法变换之二-提取直接、间接左因子 Head()的概念定义： (VTVN)+ Head() =a |a aVT 想要发现G中的左因子，可以这样去考察： 若A1|2|3|n 则考察 Head(i ) Head(j )=？= ( i,j = 1,2,n 且 ij ) 只要不空就提取它(即进行文法变换)，直至新文法关于 非终结符A的产生式有 Head() Head()= 为止。 (III) -产生式的递归子程序问题-用 Follow(R) 来解决 Follow(R) 的概念定义： (RVn) Follow(R) = a | SRa，RVn ，aV

21、T ，S是文法开始符 或 Follow(R) = a | a是允许紧跟在R后面的终结符,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 26, 递归下降子程序分析法 递归子程序分析法的改进思想：(先举例看看) 例：ABc | DE | 这样的A含产生式所对应的子程序设计。 即从生长树上来看叶子A面临的输入符ch怎么办？ 处理方法： (算法) P(A)： begin if ch Head(Bc) then P(Bc) else /*选择ABc if ch Head(DE) then P(DE) else /*选择ADE if ch Follow(A) then ERROR

22、 /*选择A消失 end 下面只要解决Head()和Follow(R)集合的求法：,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 27, 递归下降子程序分析法 下面只要解决Head()和Follow(R)集合的求法： Head() = a |a aVT (VTVN)+ 的求法: I) 求每一个X VTVN 的 Head(X) 若XVT 则XHead(X) 若XVN且 X-a 则 a Head(X) 若X -Y Y VN 则把 Head(Y) 加入 Head(X) 若X -Y1Y2Y3Yn 且 Y1Y2Y3Yj * 则把 Head(Yj+1) 加入 Head(X) 。其

23、中 j=1n-1 特别地，Y1Y2Y3Yn * 则把 加入 Head(X) 重复第步。 II) 再求Head()： (VTVN)+ 若 a aVT 则 a Head () 若 Y YVN 则把 Head(Y) 加入 Head() 若 Y1Y2Y3Yn 且 Y1Y2Y3Yj * 则把 Head(Yj+1) 加入 Head()。其中 j=1n-1 特别地，Y1Y2Y3Yn * 则把加入Head(),2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 28, 递归下降子程序分析法 下面只要解决Head()和Follow(R)集合的求法： Follow(R) = a | SRa，R

24、Vn ，aVT ，S是开始符的求法： 若R是开始符号,则# Follow(R) (因为文法将扩展为S- #R# ) 若Q- R ,(VTVN)+ RVN且 *不成立。 则 Head() 加入Follow(R) 若Q-R 或 Q-R ,(VTVN)+ RVN且 *。 则应把 Follow(Q) 加入 Follow(R) 中 。 重复第步。 注意：求Follow(R) 要涉及求Head集合。 例：考虑文法G(E)： (注意扩充文法 S- #E# )-FH的求出 G: ETE G: EE+T | T E+TE| TT*F | F TFT F(E) | i T*FT| F(E) | i,2020年8月

25、16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 29, LL(1)文法的定义与递归子程序分析法的改进(构造预测分析表) - 预测分析程序(递归子程序分析法的升华) LL(1)文法的定义： 若文法G满足如下条件： 无左递归。 无公共左因子。即若A1|2|3|n 则 Head(i ) Head(j )= （i,j=1,2,n 且ij） 若A1|2|3|n |则 Head(i ) Follow(R)= （i=1,2,n） 递归子程序的一般结构 A1|2|3|n | 这样的产生式所对应的子程序设计。 算法处理方法： P(A)： begin if ch Head(1) then P(1) el

26、se if ch Head(2) then P(2) else if ch Head(n) then P(n) else if ch Follow(A) then ERROR end,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 30, 构造预测分析表算法 1. 对文法G的每个产生式执行第二步和第三步； 2. 对每个终结符 a Head()，把 加至 A,a中， 3. 若 Head()，则对任何 b Follow(A)把 加至 A,b中， 4. 把所有无定义的 A,a 标上“出错标志”。 可以证明,一个文法G的预测分析表不含多重入口,当且仅当该文法是LL(1)。 预测

27、分析算法及程序： (P94图5.11) LL(1)分析程序的自动构造 - 分析栈 + LL(k)分析表 + 预测分析算法-LL(k)分析法 分析栈 #E 输入符 i+i*i# top ch LL(1) 分析表 (LL分析表的演变和优化),2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 31, 预测分析算法： BEGIN 首先把#然后把文法开始符号推入栈；把第一个输入符号读进ch; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中； IF X Vt THEN IF X=ch THEN 把下一个输入符号读进ch ELSE ERROR

28、 ELSE IF X=# THEN IF X=ch THEN FLAG:=FALSE ELSE ERROR ELSE IF X,ch=XX1X2.XK THEN 把XK,X K-1,.,X1推进栈 ELSEERROR END OF WHILE; STOP /*分析成功，过程完毕* END,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 32,五、自下而上的语法分析方法,寻找句柄，无一般方法，因此很困难。 我们可以从描述语言的文法上考虑，用一些具有特殊性质（限制）的文法，它们既可描述该语言，而又好进行语法分析（如找句柄）。前面曾说过我们研究文法的目的有二：一是描述语言，二

29、是进行语法分析和翻译。 算符文法与算符优先文法： 当文法满足一定条件时，可用简单方法识别出句柄来，从而达到归约分析的目的，算符优先文法就是这样的一种文法。 算符文法：若一个文法G中，不含有如下形式的产生式： PRQ R,QVn 则称G为算符文法。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 33,算符文法的句型特点：算符文法的句型一定形如：（自证） N1a1N2a2N3Niaian-1Nn 其中 aiVT NiVN 算符优先文法：若一个不含-产生式（形如P）的算符文法G中，任意两a，bVT，至多只有下列关系中的一个： a=b ， ab ， abG中含有形如PRb产生

30、式， 而R+a或R+aQ ； abG中含有形如 PaR产生式， 而R+b或R+Qb ； R,Q,P VN 则称这个文法G为算符优先文法。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 34, 算符优先文法G中终结符之间有特定关系。如下表-算符优先关系表： 直观的算符优先关系表与算符优先分析法：（举例说明） 算术表达式文法G： E#E# EE+E|E*E|EE|(E)|i 其中E#E# 产生式是为了采用算符优先分析法而增加的一个约定产生式，“#”为特殊终结符，作为句子的括号。 根据日常算术运算的经验优先级，G的优先关系表如下: (表) ii , i( , (# , )i

31、 , )( ,#) 显然是不合法子串。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 35,直观算符优先分析法： 1) 两个工作栈和一个字符变量： OPTR栈： OPND栈： a字符变量： 2)算法：对于文法G，有 OPTR栈底:=# ;输入串尾:=# ; OPND栈:=空 ; START: READ(a) ; /读入当前符号进字符变量/ IF a=i THEN BEGIN PUSH(a,OPND);GOTO START END; DO WHILE a BEGIN IF OPND中操作数少于二个 THEN ERROR ; X:=POP(OPND); (*) PUSH(

32、POP(OPND) x,OPND); :=POP(OPTR) END; CASE OF =a: IF =( AND a=) THEN BEGIN POP(OPTR);GOTO START END; IF =# AND a=# THEN IF OPND中操作数有且只有一项 THEN WRITEN(OK) ELSE ERROR; a : PUSH(a,OPTR);GOTO START; OTHERWISE : ERROR ; ENDCASE,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 36, 下面的问题就是构造算符优先关系表： I) 求FirstVT(R) (算法书上P

33、112) II) 求LastVT(R) (算法书上P114) III) 造分析表： = 有形如Aab 或 AaRb 有形如ARb 则LastVT(R)b 算符优先关系表的查比效率：提高法-优先函数 优先函数如果存在将有无穷多组。 优先函数的叠代矩阵求法。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 37,寻找句柄的有效方法-LR(K)文法与识别活前缀的有限自动机 回忆： 最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换，最右推导被称为规范推导。由规范推导所得的句型称为规范句型。 GS： SE EE+T|T T(E)|int 推导S=E=T=(

34、E)=(E+T)=(E+int)=(T+int)=(int+int) 规范归约：假定是G的一个句子，称序列n ,n-1 ,0是 的一个规范归约。如果该序列满足： （1） n = （2） 0为文法的开始符号 （3）对任何j ，0j=n, j-1是从j 经把句柄替换为相应产生式的左部而得到的。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 38,活前缀：是规范句型（右句型）的前缀，但不超过句柄。移进归约分析的栈中（已被分析过并消化了的符号可以放入一个栈中记忆）出现的内容是规范句型（右句型）的活前缀，或者说它若加上余留输入将构成规范句型。 活前缀与句柄的关系：如 GS：若S

35、A r 是的前缀，则称 r 是G的一个活前缀。 1活前缀已含有句柄的全部符号，表明产生式A的右部已出现在栈顶； 2活前缀只含句柄的一部分符号表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号； 3活前缀不含有句柄的任何符号，此时期望A的右部所推出的符号串。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 39,活前缀和句柄与 LR(0)项目： 为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。 A 刻划产生式A的 右部已出现在栈顶。它是归约项目。 A12 刻划A12的右部子串1

36、已出现在栈顶，期待从输入串中看到2推出的符号 A 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串 A 表示对于A的LR(0)所有项目。 LR(0)项目分类： 根据圆点所在位置和圆点后是终结符还是非终结符或为空把项目分为以下几种： 移进项目，形如 A a a是终结符, , V* 以下同 待约项目，形如 A B 归约项目，形如 A 接受项目，形如 S S 注意： A的LR(0)项目只有一个即A 且是归约项目。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 40,LR(0)项目集规范族的构造与识别活前缀的有限自动机 （举例来说） G: EaA|bB AcA|d

37、 BcB|d 项目集：(0)S.E SE . E.aA Ea . A EaA . E.bB Eb . B EbB . A.cA Ac . A AcA . A.d Ad . B.cB Bc . B BcB . B.d Bd . LR(0)项目集规范族算法：设 C=I0 ，I1 , . In ,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 41,LR(0)项目集规范族算法：设 C=I0 ，I1 , . In Procedure itemsets(G); Begin C := CLOSURE (SS) Repeat For C 中每一项目集I和每一文法符号x Do if G

38、O(I,x) 非空且不属于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End; 识别活前缀的有限自动机: (黑板演示) 一次性构造识别活前缀的DFA。,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 42,LR(0)分析表的构造（动作ACTION与转换函数GOTO） 动作ACTION： 移进 记为 si 其中s表示移进，i表示移进后进入第i状态； 归约 记为 rj 其中r表示归约，j表示用第就j号产生式； 接受 记为 acc 报错 转换函数GOTO: sj=GOTO(si,a) 表示栈顶状态si面临符号a ，转入sj状态。,2020年8月16日

39、星期日,编译原理主讲：周有顺,版权所有 勿复制传播 43,SLR(1)分析表的构造 G(S): （0）SS (1) SrD (2) DDi (3) Di LR（0）项目集规范族 I0: SS I3: Sr D Sr D DDi I1: SS I4: Di I2: SrD I5: DDi DDi Di 其中I3中含有移进/归约冲突,故文法不是LR(0)的，如何解决？ 由于Follow(S)Head()=#i=，故SLR(1)分析表：,注：发现LR(0)项目冲突时(移进/归约、归约/归约)，若用考虑Follow(R)、Head()两两交均空时，则得到SLR(1)分析法。即此时的文法定是SLR(1)文法,2020年8月16日星期日,编译原理主讲：周有顺,版权所有 勿复制传播 44,LR(1)分析表的构造 先考虑如下文法：G(S)：(0) SS SBB BaB Bb 随然此文法是LR(0)文法因为LR(0)项目集中无冲突项目，但用做LR(1)、LALR(1) -LR(1)同心项目集合并分析表构造的例子很简单。 I0: S.S # I1: SS. # S.BB # I2: SB.B # B.aB a/b B.aB # B.b a/b B.b # I3: Ba.B a/b