第7章 LR语法分析

7.2 LR(0)分析表的构造4．构造LR(0)分析表——举例G[S′]：[0] S′→S [1] S→S(S)[2] S→εG[S]：[1] S→S(S)[2] S→εG[S]：[0] S′→SS′→.SS→.S(S)S→S.(S)S→.S(S) S→.7.3 SLR(1)分析表的构造1．LR(0)方法的不足LR(0)分析表的构造方法实际上隐含了这样一个要求：构造出的识别规范句型活前缀的有穷自动机中，每个状态均不能有冲突项目，这显然对文法的要求太高，也限制了该方法的应用。

7.3 SLR(1)分析表的构造1．LR(0)方法的不足例如，对文法G[S]：0S→E1 E→E+T2 E→T3 T→T*F4 T→F5 F→（E）6 F→i1I S→E.E→E.+TT→.T*F T→.FFT E #)(*+i G[S]：7.3 SLR(1)分析表的构造2．LR(0)方法的问题分析状态{ E→T.，T→T.*F}该状态含有移进-归约冲突，在分析表中表现为重定义。

7.3 SLR(1)分析表的构造2．LR(0)方法的问题①若U→x.ay ∈Ii ，且GO(Ii，a)=Ij，a∈VT，则ACTION[i，a]=“Sj”。

②若S′→S. ∈Ii，则置ACTION[i，＄]=“acc”。

③若U→x. ∈Ii ，则对任意终结符a和＄，均置ACTION[i，a]=“rj”或ACTION[i，＄]=“rj”。

④若GOTO(Ii ，U)=Ij，其中U∈VN，则置GOTO[i，U]=“j”。

⑤除上述方法得到的分析表元素外，其余元素均置“报错标志”。

7.3 SLR(1)分析表的构造3．解决问题的方法所以在状态{ E→T.，T→T.*F}中，只需要向前看下一输入符号是*，还是FOLLOW（E）中的符号，便可解决冲突了。

7.3 SLR(1)分析表的构造3．解决问题的方法假设一个状态Ii中含有冲突项目I i ={ U1→x.b1y1，U2→x.b2y2，…，Um→x.bmym，V1→x.，V 2→x.，…，Vn→x.}若{b1，b2，…，bm}和FOLLOW(V1)、FOLLOW(V2)、…、FOLLOW(Vn)两两互不相交，就可以采用向前看一个输入符号的方法来解决状态中的冲突。

编译原理教案说明：一、参考书：1、陈意云、张昱：《编译原理》，高等教育出版社，2003年。

2、陈意云、张昱：《编译原理习题精选》，中国科技大学出版社，2003年。

3、吕映芝、张素琴、蒋维杜：《编译原理》，清华大学出版社，1998年第二版。

4、王生原、吕映芝、张素琴：《编译原理课程辅导》，清华大学出版社，2007年。

5、伍春香：《编译原理习题与解析》，清华大学出版社，2001年。

6、Andrew W.Appel：《现代编译原理—C语言描述》，人民邮电出版社，2005年。

7、Noam Nison等：《计算机系统要素》，电子工业出版社，2007年。

8、Randall Hyde：《编程卓越之道（第二卷）》，电子工业出版社，2007年。

二、教学目的：通过学习形式语言与自动机理论、词法分析、语法分析、语义分析、代码优化和生成等内容使学生掌握构造编译程序的基本原理和基本方法，并通过上机实习使学生进一步掌握开发应用程序的基本方法，为深入理解计算机系统、程序设计语言与开发大型应用程序打下良好的基础。

三、教学时数：课堂教学51学时，上机实验30学时。

四、授课内容：第一章编译程序概述第二章 PL/0编译程序的实现第三章文法和语言第四章词法分析第五章自顶向下语法分析方法第六章自底向上优先分析方法第七章 LR分析方法第八章语法制导翻译和中间代码生成第九章符号表第一○章目标程序运行时的存储组织第一一章代码优化第一二章代码生成第一章概述一、说明：1、教学目的与要求：了解编译程序的概念、结构以及工作流程。

2、主要内容：什么是编译程序、编译过程概述、编译程序的结构、编译阶段的组合、编译技术和软件工具以及实例分析。

3、教学重点：编译程序的结构以及每一阶段的任务。

4、教学难点：理解编译程序各模块的判错功能、编译方式和解释方式执行速度上的不同。

二、教学内容第一节编译程序1、机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。

第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。

A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。

A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。

第7章LR分析第7章 LR分析练习 P1651、已知⽂法A->aAd| aAb|ε判断该⽂法是否是SLR（1）⽂法，若是构造相应分析表，并对输⼊串ab#给出分析过程。

【解】 (1)拓⼴⽂法 (0)S->A (1) A->aAd (2)A-> aAb (3)A->ε(2)构造识别活前缀的DFAFOLLOW(A)={d,b,#}对于状态I0：FOLLOW(A)∩{a}=Ф，对于状态I2：FOLLOW(A)∩{a}=Ф因为，在项⽬集规范族中⽆冲突的现象，所以该⽂法是SLR(1)⽂法。

(3)SLR(1)(4)输⼊串ab#的分析过程3、考虑⽂法S→A S | bA → S A | a(1)列出这个⽂法的所有LR(0)项⽬(3)这个⽂法是SLR（1）吗？若是，构造这个⽂法的SLR分析表。

【解】[1]令拓⼴⽂法G’为[0]S’ → S[1]S → A S[2]S → b[3]A → S A[4A → a其LR(0)项⽬集规范族及识别该⽂法活前缀的DFA如下图所⽰：FOLLOW(S)={#,a,b} FOLLOW(A)={a,b}(3) 因为I5中：FOLLOW（A）∩{a，b}≠Ф或I7中：FOLLOW（B）∩{a，b}≠Ф所以，该⽂法不是SLR（1）⽂法。

7、证明下⾯⽂法是SLR（1）但不是LR（0）的。

S->AA->Ab|bBaB->aAc|a|aAb【解】（⼀）拓⼴⽂法为：0）S’->S1） S->A 2） A->Ab 3）A->bBa 4） B->aAc5) B->a 6) B->aAb（⼆）构造其LR(0)项⽬集规范族及识别该⽂法活前缀的DFA如下图：【证明】因为I2、I5中存在移进-归约冲突，所以不是LR（0）I2中FOLLOW（S）={ #}，{#}∩{b}=ФI5中FOLLOW（B）={a} {a}∩{b}=Ф因为I2、I5中的移进-归约冲突可以⽤SLR（1）解决，所以该⽂法是SLR（1）。

《编译原理》总复习-07级第一章编译程序的概述（一）内容本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。

（二）本章重点编译（程序），解释（程序），编译程序的逻辑结构。

（三）本章难点编译程序的生成。

（四）本章考点全部基本概念。

编译程序的逻辑结构。

（五）学习指导引论部分主要是解释什么是编译程序以及编译的总体过程。

因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。

第三章文法和语言课外训练（一）内容本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。

（二）本章重点上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。

（三）本章难点上下文无关文法，语法分析树，文法的分类。

（四）本章考点上下文无关文法的定义。

符号串的推导。

语法分析树的构造。

（五）学习指导要构造编译程序，就要把源语言用某种方式进行定义和描述。

学习高级语言的语法描述是学习编译原理的基础。

上下文无关文法及语法树是本章学习的重点。

语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。