《编译原理》总复习

1、编译原理编译原理复习复习西安电子科技大学西安电子科技大学 软件工程研究所软件工程研究所习题与试题习题与试题认真复习，重点是掌握基本概念。基本概念掌握了，相认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了当一部分试题的解就有了习题与试题的目的区别：习题的目的是通过反复的练习习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大时间内覆盖大量

2、内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的量时间的题是不可能出的自己要会辨别什么是主要的什么是次要的，抓什么丢什自己要会辨别什么是主要的什么是次要的，抓什么丢什么。么。“基本概念要严谨（清楚），基本方法要灵活基本概念要严谨（清楚），基本方法要灵活”总之一句话，学习方法的掌握是个人努力的结果，单纯总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的靠别人教是学不会的如果是我复习如果是我复习词法分析词法分析基本概念：正规式、正规集、有限自动机，词法分析基本概念：正规式、正规集、有限自动机，词法分析器的构造器的构造常见计算题类型：已知集合求正规式、常见计算题类型：已知集合

3、求正规式、DFADFA；已知正规；已知正规式求式求DFADFA、集合；已知、集合；已知FAFA求正规式、集合；求正规式、集合；FAFA的确定化、的确定化、最小化。最小化。语法分析语法分析基本概念：上下文无关文法、语言、下推自动机，基本概念：上下文无关文法、语言、下推自动机，LLLL分析与分析与LRLR分析；分析；一些必要的定义、公式、算法的核心思想等；一些必要的定义、公式、算法的核心思想等；常见的计算题类型：（自己思考）常见的计算题类型：（自己思考）基本解题方法与技巧等。基本解题方法与技巧等。3. 3. 语法制导翻译（略）（语法制导翻译（略）（哪些最重要？哪些最重要？）4关于考试关于考试 题目

4、类型：题目类型：简答题简答题(30(30分分) )、填空题、填空题(20(20分分) )、计算题、计算题(50(50分分) ) 内容分布内容分布(大概大概)：概述与词法分析概述与词法分析(30分分)、语法分析、语法分析(40分分)、语法制导翻译与运行环境语法制导翻译与运行环境(30分分) 考试范围：考试范围：14章讲过的内容章讲过的内容 侧重考察：侧重考察：基本概念与基本方法的掌握基本概念与基本方法的掌握易犯的错误易犯的错误不认真审题（题目的要求理解错误：意思理解错、难题想不认真审题（题目的要求理解错误：意思理解错、难题想容易、容易题想难。容易、容易题想难。关键问题是基本概念不清楚关键问题是基

5、本概念不清楚）所答非所问所答非所问( (例如：没有要求例如：没有要求LLLL分析却将文法改为分析却将文法改为LLLL的的) )画蛇添足画蛇添足( (例如：仅问有无冲突却将分析表先构造出来例如：仅问有无冲突却将分析表先构造出来) )1.1. 偷工减料偷工减料( (例如：有若干问，仅回答部分或问题仅答一半例如：有若干问，仅回答部分或问题仅答一半) )警示警示千万不要作弊！命运掌握在自己的手中！千万不要作弊！命运掌握在自己的手中！实际试题举例实际试题举例一、简答题一、简答题1.11.1（2 2分）有哪些方法可以去除文法的二义性。分）有哪些方法可以去除文法的二义性。1.21.2（2 2分）写出分）写出

6、 -(a+b)-(a+b)* *c)+d c)+d 的后缀式。的后缀式。1.51.5（4 4分）试证明正规式分）试证明正规式(ab)(ab)* *a a与与a(ba)a(ba)* *是等价的。是等价的。1.1 1.1 （1 1）改写文法）改写文法 （2 2）规定文法符号的优先级和结合性）规定文法符号的优先级和结合性1.2 1.2 ab+cab+c* *d+d+（或（或ab+cab+c* *-d+-d+）1.5 1.5 证明：证明： 考虑考虑L(ab)L(ab)* *a)a)中的任意一个串中的任意一个串ababab.abaababab.aba， 由串连接的结合性可得：由串连接的结合性可得：a(b

7、a)(ba)(b.a)(ba)a(ba)(ba)(b.a)(ba)，它恰好，它恰好是是L(a(ba)L(a(ba)* *) )， 即即L(ab)L(ab)* *a)= L(a(ba)a)= L(a(ba)* *) )。 也可以用归纳法证明（提示：以也可以用归纳法证明（提示：以abab重复重复0 0次、次、1 1次作为归纳次作为归纳基础，假设基础，假设abab重复重复n n次成立，证明次成立，证明abab重复重复n+1n+1次也成立）。次也成立）。二、填空题二、填空题2.22.2（6 6分）分）编译程序的基本组成有：词法分析、编译程序的基本组成有：词法分析、 、 、中、中间代码生成、间代码生成、

8、 、 、 和和 。2.32.3（1 1分）分）正规式正规式r r和和s s等价说明等价说明 相同。相同。2.42.4（2 2分）分）不含子串不含子串baabaa的所有的所有a a、b b符号串的正规式是符号串的正规式是 。2.92.9（4 4分）分） 已知文法已知文法G G定义如下：定义如下：SeT|RT TDR| RdR| Da|bdSeT|RT TDR| RdR| Da|bd则则FIRST(S)=FIRST(S)= ，FIRST(D)=FIRST(D)= ，FIRST(T)=FIRST(T)= ，FIRST(R)=FIRST(R)= 。 2.2 2.2 语法分析语法分析、语义分析语义分析、

9、代码优化代码优化、目标代码生成目标代码生成、 符号表管理符号表管理和和出错处理出错处理 2.3 2.3 r r和和s s表示的正规集表示的正规集 2.42.4 a a* *(b|ba)(b|ba)* * 2.92.9 FIRST(S)=FIRST(S)= e e，d d，a a，b b ，FIRST(D)=FIRST(D)= a a，b b ，FIRST(T)=FIRST(T)= ，a a，b b ，FIRST(R)=FIRST(R)= d d， 。三、计算题（三、计算题（3.33.3）3.33.3（1313分）分）已知一个已知一个NFANFA如图。如图。 (a)(4(a)(4分分) ) 用自

10、然语言简要叙述该自动机所识别的语言用自然语言简要叙述该自动机所识别的语言 的特点，列举两个它可识别的串。的特点，列举两个它可识别的串。 (b)(b)（3 3分）分）写出与该自动机等价的正规式写出与该自动机等价的正规式r r。 (c)(c)（6 6分）分）用子集法构造识别用子集法构造识别r r的最小的最小DFADFA。012bba,ba,b三、计算题（三、计算题（3.43.4）3.43.4（1515分）分）有文法有文法G G如下（注：如下（注：G G中终结符中终结符idid仅由单个英文字母仅由单个英文字母组成，如组成，如a, ba, b等）：等）：EEEE* *T|TT|TTT+F|FTT+F|

11、FF(E)|idF(E)|id和和G G的语法制导翻译如下：的语法制导翻译如下：EEEE1 1* *T TE.place=newtemp; emit(E.place=newtemp; emit(* *,E,E1 1.place,T.place,E.place;.place,T.place,E.place;| T| TE.place=T.place;E.place=T.place;TTTT1 1+F+FT.place=newtemp; emit(+,TT.place=newtemp; emit(+,T1 1.place,F.place,T.place;.place,F.place,T.place

12、;| F| FT.place=F.place;T.place=F.place;F(E)F(E)F.place=E.place;F.place=E.place;| id| idF.place=;F.place=;(a)(a)（4 4分）分）求句型求句型(T+F)(T+F)* *idid 的短语、直接短语以及句柄；的短语、直接短语以及句柄；(b)(b)（4 4分）分）根据语法制导翻译写出句子根据语法制导翻译写出句子a a* *b+cb+c* *d d的中间代码；的中间代码；(c)(c)（3 3分）分）若若a=3a=3，b=5b=5，c=7c=7，d=8d=8，请给出中间

13、代码计算结果；请给出中间代码计算结果；(d)(d)（4 4分）分）将文法将文法G G简化为：简化为：EEEE* *T|TT|T，TT+F|FTT+F|F，FidFid。给出。给出它的识别活前缀的它的识别活前缀的DFADFA。 习题习题2.42.4写出下述语言的正规式描述写出下述语言的正规式描述（1 1） 由偶数个由偶数个0 0和奇数个和奇数个1 1构成的所有构成的所有0101串串（2 2） 所有不含子串所有不含子串011011的的0101串串（3 3） 每个每个a a后面至少紧随两个后面至少紧随两个b b的的abab串串（4 4） C C的形如的形如/ /* * */ / 的注释。其中的注释。

14、其中代表不含代表不含* */ /的字符串的字符串问题：问题：拿到这类题该怎样思考，然后去解决？拿到这类题该怎样思考，然后去解决？( (特别是特别是(1)(1)思路：思路：分析题意，从最简单的例子考虑，然后找出统一规律分析题意，从最简单的例子考虑，然后找出统一规律步骤：步骤：1. 1. 最简单的符合要求的串：最简单的符合要求的串：1 1、010010（还有（还有100100或或001001）2. 2. 所有所有0101均为偶数的串：均为偶数的串： A=(00|11)|(01|10)(00|11)A=(00|11)|(01|10)(00|11)* *(10|01)(10|01)* *3. 3. 符

15、合要求的所有串：符合要求的所有串：A1AA1A、A0A1A0AA0A1A0A（为什么没有后两个？）（为什么没有后两个？）结果：结果：A1A | A0A1A0AA1A | A0A1A0A思考：思考：识别它的识别它的DFADFA又应该如何构造？又应该如何构造？（4 4） C C的形如的形如/ /* * */ / 的注释。其中的注释。其中代表不含代表不含* */ /的字符串的字符串思路：思路：注释中若遇到注释中若遇到* *：若后边是：若后边是/ /则结束注释否则仍然是注释则结束注释否则仍然是注释步骤：步骤：1. 1. 注释串是空；注释串是空；2. 2. 考虑没有考虑没有* *的注释；的注释；3. 3

16、. 考虑含考虑含* *的注释的注释结果：结果：(4) (4) /* * (* * | ( | (* *) )* * */)/)* * (* *) )* * * */习题习题2.92.9用自然语言给出下述正规式所描述的语言，并构造他们的最小用自然语言给出下述正规式所描述的语言，并构造他们的最小DFADFA1010* *1 1(0|1)(0|1)* *011(0|1)011(0|1)* *问题：问题：看得懂，但是不太会用自然语言较好的表达看得懂，但是不太会用自然语言较好的表达说明：说明：所谓用自然语言描述就是解释字符串的性质，一般情所谓用自然语言描述就是解释字符串的性质，一般情况下是已经有了形式化

17、描述。注意：这就是练习的目的。况下是已经有了形式化描述。注意：这就是练习的目的。解：解：1010* *1 1：首尾是首尾是1 1中间有零或若干个中间有零或若干个0 0的的0101串。串。(0|1)(0|1)* *011(0|1)011(0|1)* * ：至少含一个至少含一个011011的的0101串。串。注意：注意：绝对不允许用正规式形式表示，因为正规式已经给出绝对不允许用正规式形式表示，因为正规式已经给出习题习题2.102.10有一有一NFANFA的状态转换矩阵下表，其中的状态转换矩阵下表，其中S S为初态，为初态，D D为终态为终态a ab bc cS SA,BA,BC,DC,DD DA,

18、B.CA,B.CA AA AC CB BB BA AD DC CC CB BA AA AD DC CB BS S求出它的最小求出它的最小DFADFA用正规式描述用正规式描述DFADFA所所接受的语言接受的语言问题：问题：根据根据DFADFA写出对应的正规式，通常的考虑和步骤是什么？写出对应的正规式，通常的考虑和步骤是什么？ 再重复一遍：再重复一遍： 正规式、正规式、DFADFA是从两个不同的侧面表示一个集合是从两个不同的侧面表示一个集合( (即正规集即正规集) )。所。所以，根本的方法是把正规集作为桥梁，先分析清楚以，根本的方法是把正规集作为桥梁，先分析清楚DFADFA识别出的识别出的是一个什

19、么集合，然后再设计此集合的正规式。反之亦然。是一个什么集合，然后再设计此集合的正规式。反之亦然。习题习题2.102.10（2 2）的解的解 该该DFADFA从初态到终态有三条路径：从初态到终态有三条路径：b|c|a(a|c)b|c|a(a|c)* *b b，而且是，而且是这三条路径的至少一次重复，故正规式为：这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)(b|c|a(a|c)* *b)b)+ +习题习题3.23.2对所给文法：对所给文法：S(L)|a LL,S|SS(L)|a LL,S|S(3) (3) 用自然语言描述该文法所产生的语言用自然语言描述该文法所产生的语言问题：问题：

20、同样不理解同样不理解“用自然语言表达用自然语言表达”思路：思路：所谓用自然语言描述就是解释句子的性质，一般情况所谓用自然语言描述就是解释句子的性质，一般情况下是已经有了形式化描述（下是已经有了形式化描述（CFGCFG）。解题思路是先用所给）。解题思路是先用所给的产生式集合产生若干句子，然后分析句子的共性，从的产生式集合产生若干句子，然后分析句子的共性，从中找出规律。根据这一思想再看习题解答。中找出规律。根据这一思想再看习题解答。习题习题3.73.7设计一文法设计一文法G G，使得，使得L(G)=|L(G)=|是不以是不以0 0开始的正奇数开始的正奇数 问题：问题：不知怎样着手做设计题，通常步骤

21、是什么？不知怎样着手做设计题，通常步骤是什么？（看到这样的问题我要疯掉了，都是一样的思路吗）（看到这样的问题我要疯掉了，都是一样的思路吗）思路：思路：首先根据集合的描述设计几个句子，然后从句子中找首先根据集合的描述设计几个句子，然后从句子中找出规律（或共性），把它们的性质用产生式表示出来。出规律（或共性），把它们的性质用产生式表示出来。解：解：正规式：正规式：个位：个位：1357913579个位以上：个位以上：0-90-9* *最高位：最高位：1-91-9三段连起来：三段连起来：1-90-91-90-9* *1357913579产生式：产生式：SACB|BSACB|BA1|2|3|4|5|6|

22、7|8|9A1|2|3|4|5|6|7|8|9B1|3|5|7|9B1|3|5|7|9C|0C|ACC|0C|AC习题习题 3.173.17对于文法对于文法G3.4G3.4和它所产生的句子和它所产生的句子-id+id-id+id* *idid 和和 -(id+id)-(id+id)* *ididE E+T|TE E+T|TT TT T* *F|F (G3.4)F|F (G3.4)F (E) |-F|idF (E) |-F|id（1 1）构造基于）构造基于LR(0)LR(0)项目集的识别活前缀的项目集的识别活前缀的DFADFA（2 2）指出）指出DFADFA中所有含有冲突的项目集，并说明这些冲突

23、可以中所有含有冲突的项目集，并说明这些冲突可以用用SLR(1)SLR(1)方法解决；方法解决；（3 3）构造文法）构造文法G3.4G3.4的的SLR(1)SLR(1)分析表分析表（4 4）用分析表对句子）用分析表对句子-id+id-id+id* *idid 和和 -(id+id)-(id+id)* *idid进行分析（以进行分析（以格局变化的方式）格局变化的方式）（5 5）根据（）根据（4 4）的分析给出）的分析给出-id+id-id+id* *idid的分析树和剪句柄的过程的分析树和剪句柄的过程解：解：作为练习，本题的每一步都是必要的。相对来说分析表的作为练习，本题的每一步都是必要的。相对来

24、说分析表的构造并不重要。构造并不重要。（具体步骤有时间板书）（具体步骤有时间板书）构造构造SLRSLR（1 1）分析表的方法：分析表的方法：1 1可移进项直接从可移进项直接从DFADFA上看：上看：actionI,a:=sjactionI,a:=sjgotoI,A:=kgotoI,A:=k2 2可归约项分两步走：若在可归约项分两步走：若在I I状态中有状态中有A.A.，首先计算：首先计算：FOLLOW(A),FOLLOW(A),然后填写：然后填写：actionI,b:=RiactionI,b:=Ri其中：其中：bFOLLOW(A)bFOLLOW(A)且且AA是第是第i i个产生式。个产生式。

25、习题习题 4.44.4假定下述程序分别采用值调用，引用调用，复写假定下述程序分别采用值调用，引用调用，复写- -恢复和换名恢复和换名调用，请给出它们的打印结果。调用，请给出它们的打印结果。 program main(input output);program main(input output); procedure p(x,y,z); procedure p(x,y,z); begin y:=y+1; z:=z+x end; begin y:=y+1; z:=z+x end; begin a:=2; b:=3; p(a+b, a, a); print a end; begin a:=2; b

26、:=3; p(a+b, a, a); print a end;两种解题的思路：两种解题的思路：1. 1. 把自己当作计算机，按照参数传递的实现方式把自己当作计算机，按照参数传递的实现方式“运行运行”一一遍程序，得出结果；遍程序，得出结果；2. 2. 找台机子把程序敲进去试试（辅助手段）找台机子把程序敲进去试试（辅助手段）比较困惑的是：比较困惑的是：表达式表达式a+ba+b如何可以作为复写如何可以作为复写- -恢复的实参？恢复的实参？解决方案：解决方案：忽略返回值问题（因为复写忽略返回值问题（因为复写- -恢复一般要求形参要恢复一般要求形参要有左值）；其实这一思想可以推广到任何不支持某种方式有左

27、值）；其实这一思想可以推广到任何不支持某种方式的情况（放心，考试中不会有这种很困惑的问题）的情况（放心，考试中不会有这种很困惑的问题）具体结果（略）具体结果（略）19第一章第一章 引言引言 语言的翻译语言的翻译 不同的翻译形式：不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译汇编、编译、转换（预编译）、逆向翻译翻译方法：翻译方法： 20 编译器的基本组成编译器的基本组成 21 编译器的分析综合模式编译器的分析综合模式 编译器的扫描遍数与编译器的编写编译器的扫描遍数与编译器的编写 22第二章第二章 词法分析词法分析 构词规则与词法分析：构词规则与词法分析： 首先规定单词形成的规则，称为首先规

28、定单词形成的规则，称为构词规则构词规则；然后根据；然后根据构词规则识别输入序列，称为构词规则识别输入序列，称为词法分析词法分析。 主要内容：主要内容： 记号、模式与单词记号、模式与单词 记号的说明模式的形式化描述（正规式与正规集）记号的说明模式的形式化描述（正规式与正规集） 记号的识别有限自动机记号的识别有限自动机 从正规式到词法分析器从正规式到词法分析器 词法分析器的作用：词法分析器的作用：滤掉源程序中的无用成分；滤掉源程序中的无用成分；处理与具体操作系统或机器有关的输入；处理与具体操作系统或机器有关的输入；识别记号并交给语法分析器；识别记号并交给语法分析器；调用符号表管理器和出错处理器进行

29、相关处理。调用符号表管理器和出错处理器进行相关处理。 23 记号、模式与单词记号、模式与单词 模式（模式（patternpattern）：规定单词识别的规则）：规定单词识别的规则 记号（记号（tokentoken）：按照某模式识别出的一类单词（记号种类）：按照某模式识别出的一类单词（记号种类） 单词（单词（lexemelexeme）：被识别出的字符串本身）：被识别出的字符串本身 词法分析器的输出：记号词法分析器的输出：记号= =记号种类记号种类+ +记号属性记号属性 记号的说明模式的形式化描述记号的说明模式的形式化描述 正规式与正规集：正规式与正规集：正规式与正规集的定义正规式与正规集的定义(

30、 (基本正规式、三个运算基本正规式、三个运算) )正规式的等价正规式的等价( (描述相同的集合描述相同的集合) )利用正规式的等价对正规式进行化简利用正规式的等价对正规式进行化简( (正规式的代数性质正规式的代数性质) )用正规式对模式进行形式化描述：用正规式对模式进行形式化描述：如何用正规式描述程序设计语言中常见的记号，如标识如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等符、数字、运算符和分隔符等正规式的简化形式以及辅助定义与规则正规式的简化形式以及辅助定义与规则24 记号的识别有限自动机（记号的识别有限自动机（FAFA） NFANFA与与DFADFA的定义：的定

31、义：FA = (S, , move, s0, F)FA = (S, , move, s0, F)；NFANFA与与DFADFA的表示：定义表示、状态转换图、状态转换矩阵；的表示：定义表示、状态转换图、状态转换矩阵；NFANFA与与DFADFA的关键区别：的关键区别：NFANFA的不确定性（当前状态下，对同的不确定性（当前状态下，对同一字符可能有多于一个的下一状态转移）；一字符可能有多于一个的下一状态转移）；用用NFANFA识别输入序列的弱点：尝试所有路径才能确定一个输识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收、回溯带来的问题；入不被接收、回溯带来的问题；模拟模拟DFADFA的算法

32、（用的算法（用DFADFA识别记号）。识别记号）。 从正规式到词法分析器从正规式到词法分析器 构造构造NFANFA的的ThompsonThompson算法算法( (与与NFANFA定义的对应关系定义的对应关系) )； 模拟模拟NFANFA的的“并行并行”算法；算法； 从从NFANFA构造构造DFADFA子集法：子集法：smove(S, a)smove(S, a)与与-闭包闭包(T)(T)的计算；的计算； DFADFA的最小化可区分的概念：所有不可区分的状态看作的最小化可区分的概念：所有不可区分的状态看作是一个状态；是一个状态； 灵活运用各种方法构造灵活运用各种方法构造DFADFA( (正规式化

33、简、状态转换图等正规式化简、状态转换图等) )26第三章第三章 语法分析语法分析 语法分析是编译器中的重要阶段之一，可以认为是语法制语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即的规则构成语言的各种结构，即语法规则语法规则；根据语法规则识别；根据语法规则识别输入序列（记号流）中的语言结构，即输入序列（记号流）中的语言结构，即语法分析语法分析。 语法分析的分析对象是组成语言的句子，句子具有层次结语法分析的分析对象是组成语言的句子，句子具有层次结构的特征，表征

34、该结构的最好方法是树，从而使得对语法的分构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了析就有了从根到叶子从根到叶子和和从叶子到根从叶子到根两种分析方法。两种分析方法。 主要内容主要内容 程序设计语言与文法程序设计语言与文法 有关推导的基本概念有关推导的基本概念 自上而下分析自上而下分析 自下而上分析自下而上分析 27 程序设计语言与文法程序设计语言与文法 正规式与正规文法：正规式与正规文法用于描述线性结构，正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号如构成句子的记号( (终结符终结符) )；识别正规语言的自动机是有；识别正规语言的自动机是有限自动机，它们

35、的特征是没有记忆能力；限自动机，它们的特征是没有记忆能力； 上下文无关文法上下文无关文法( (CFG=(N, T, S, P)CFG=(N, T, S, P) )：CFGCFG用于描述层次结用于描述层次结构，如构成程序的句子；识别构，如构成程序的句子；识别CFLCFL的自动机是下推自动机，的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；简单的记忆能力； 文法的分类：文法的分类：0 0型、型、1 1型、型、2 2型和型和3 3型文法型文法 词法分析器与语法分析器词法分析器与语法分析器（FAFA与与PDAPD

36、A）28 有关推导的基本概念有关推导的基本概念 CFGCFG产生语言的基本方法推导：从文法的开始符号开始，产生语言的基本方法推导：从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。反复地用产生式的右部替换句型中的非终结符。 推导的基本概念：句子、直接推导、最左推导、左句型（最推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；右推导、右句型）； 分析树与语法树：分析树和语法树都反映了语言结构；分析分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程（树还记录了分析的过程（含有非终结符含有非终结符）；）； 文法的二义性：二义性的本质是在文法中缺

37、少对文法符号优文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。棵分析树。 二义性的消除：二义性的消除：改写二义文法为非二义文法；改写二义文法为非二义文法； 对文法符号施加优先级与结合性的限制，使得分析的每对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。一步有唯一选择。 29 自上而下分析自上而下分析 分析方法：推导，从上到下构造分析树，是一种预测的、分析方法：推导，从上到下构造分析树，是一种预测的、试探的方法；试探的方法； 对文法的要求：没有公共左因子和左递归；

38、对文法的要求：没有公共左因子和左递归； 递归下降子程序方法：匹配终结符，展开非终结符（递归下降子程序方法：匹配终结符，展开非终结符（子子程序调用程序调用） 预测分析表方法预测分析表方法: : 工作方式与过程：工作方式与过程：PDAPDA（DPDADPDA）、格局与改变格局的、格局与改变格局的动作；动作； 预测分析表的构造：预测分析表的构造：FIRSTFIRST集合与集合与FOLLOWFOLLOW集合，集合， FIRSTFIRST与与FOLLOWFOLLOW的计算；的计算； LL(1)LL(1)文法及其判别：预测分析表中没有多重定义条文法及其判别：预测分析表中没有多重定义条目（推论目（推论3.2

39、3.2）。）。30 自下而上分析自下而上分析 分析方法：归约分析方法：归约( (推导的逆过程推导的逆过程) )，从叶子到根构造分析树；，从叶子到根构造分析树；基本概念：短语、直接短语、句柄、归约、规范归约；基本概念：短语、直接短语、句柄、归约、规范归约； 采用的方法采用的方法: : 用移进用移进- -归约方法实现剪句柄。关键问题是如归约方法实现剪句柄。关键问题是如何确定栈顶已经形成句柄，当句柄形成时，如何判定采用何确定栈顶已经形成句柄，当句柄形成时，如何判定采用哪个产生式进行规约；哪个产生式进行规约； 识别活前缀的识别活前缀的DFADFA：活前缀活前缀与与LR(0)LR(0)项目项目( (NF

40、ANFA状态状态) )，拓广文，拓广文法与子集法构造法与子集法构造DFADFA；31 自下而上分析（续）自下而上分析（续）DFADFA分析输入序列：有效项目、可移进项、可规约项、移分析输入序列：有效项目、可移进项、可规约项、移进进/ /归约冲突、归约归约冲突、归约/ /归约冲突；解决冲突的方法归约冲突；解决冲突的方法SLR(1)SLR(1)：简单向前看一个终结符（：简单向前看一个终结符（计算归约项非终结符计算归约项非终结符的的FOLLOWFOLLOW，与可移进终结符比较，与可移进终结符比较）；）； 2.2. 移进移进- -归约分析表：动作表转移表；归约分析表：动作表转移表； 3. LR3. LR文法与文法与LRLR分析：分析：LR(0)LR(0)、SLR(1)SLR(1)、LALR(1)LALR(1)、LR(1)LR(1)。32第四章第四章 语法制导翻译生成中间代码语法制导翻译生成中间代码 本章讨论程序设计语言的静态语义分析，并且在语法分析本章讨论程序设计语言的静态语义分析，并且在语法分析的基础上生成中间