0513《编译原理》作业

《编译原理》习题解答：

第一次作业：

P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？

答：被翻译的程序称为源程序；

翻译出来的程序称为目标程序或目标代码；

将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；

把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；

解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；

编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。

P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。

P14 4、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法

编译原理作业集

1 第二章 词法分析

1. C或Java语言的标示符是字母和数字组成的序列，第一个字符必须是字母，下划线视为字母，且大小写字母不同。请写出匹配C或Java语言标示符的正规表达式。 2. 为下边所描述的串写正规式，字母表是 {0, 1}. a) 以11 结尾的所有串 b) 只包含一个1的所有串

2 第三章 上下文无关文法

1. ________是描述程序设计语言语法结构的形式工具。 2. 设G=(VN，VT，P，S)是一文法，且 V= VN∪VT，若S =>*α，α∈V，则称α为文法G的 ，若S=>*α，α∈VT，则称α为文法G的 。

3. 给出语言L={ab|j>i>=1}的上下文无关文法。 4. 文法G[S]的产生式如下： S?SaS | SbS | cS | Sd | t 对于输入串 tbctat: (1) 给出一个推导；

(2) 画出(1)中推导对应的分析树；

ij

*

*

(3) 文法G是否是二义性的，请证明你的结论。

3 第四章 语法分析

1. 考虑文法G[S]:

S-> A︱B A->

《编译原理》习题解答：

第一次作业：

P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？

答：被翻译的程序称为源程序；

翻译出来的程序称为目标程序或目标代码；

将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；

把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；

解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；

编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。

P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。

P14 4、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法

软件学院 2012秋季学期

《编译原理》第七次作业参考答案

一、 证明下列文法

S ? Aa | bAc | dc | bda A ? d

是LALR(1)文法但不是SLR(1)文法.

构造LR(1)自动机（没有需要合并的状态）：

没有状态存在冲突，因而是LALR(1)文法.

构造LR(0)自动机：

1

在状态I6，由于’a’∈FOLLOW(A)，因而对于SLR(1)分析而言，存在移进-归约，所以这一文法不是SLR(1)文法. 二、 证明下列文法

S ? Aa | bAc | Bc | bBa A ? d B ? d

是LR(1)文法但不是LALR(1)文法. 略.

三、 （附加题，选做）类似LL(1)文法，我们很容易给出LL(k)文法的定义. 对于一个上下文无关文法，如果

递归下降分析器（recursive-descent parser）每次都可以通过向前看k个符号来确定选用哪一个产生式而不需要回溯，这一文法便称为LL(k)文法. 试构造一个无左递归且无二义的文法，使得对任意固定的k，这一文法都不是LL(k)文法.

S ? A | B A ? aA | a B

作业题:

2.1(a,c,d), 2.8(a,c,d), 2.12, 3.3, 3.4, 4.8, 4.12

5.8(a,b,c), 5.12, 6.7, 6.8, 6.13 7.4, 7.15

第二章作业： 2．1 (a) a | a[a-z]*a

(c) [1-9][0-9]* (d) [0-9]*[02468]

2.8（a）

Start a a [b-z] [b-z]

a

正则表达式中丢了单独a的情况的比较多，另外有些同学在有NFA到DFA的转化过程

中，不能够正确的确定最终的状态，造成有两个终结状态的情况。 （c）

Start [0-9]

[1-9]

（d）

问题比较多，建议同学画出DFA图生成的全部过程。

2.12

3．4

a a a b a bb b a a b b b a （c）.rewrite this grammar to establish the correct precedences for the operator.

rexp -> rexp “|” rexp1 | rexp1 rexp1 -> rexp1 r

第一次作业答案： 3.12 词法单元描述

text 标签间的文本 Here is a photo of , my house, ; , See , More Pictures , if you liked that one. Start_tag End_tag attrbute value 开始标签 结束标签 标签内的参数 ,

,,
, , SRC,HREF 标签内的参数“house.gif” , “morePix.html” 值 assign_op 赋值号 = 3.3.5 b)a*b*……z* c) /\\*([^*”]|\\*[^/]|\\”([^”]*)\\”)*\\*/ h)b*(a|ab)* 3.7.3d

F转G错误，F跳转后的状态子集应包含9

第二次作业答案：

4.2.2 最左推导 S->SS S->S*S S->(S)*S S->(S+S)*S S->(a+S)*S S->(a+a)*S S->(a+a)*a Parse tree:

SSS*Sa(S)S+S 最右推导： S->SS S->S*a S->(S)*a

aa S->(S+S)*a S->(S+a)*a S->(a+a)*a

无二义

第一次作业答案： 3.12 词法单元描述

text 标签间的文本 Here is a photo of , my house, ; , See , More Pictures , if you liked that one. Start_tag End_tag attrbute value 开始标签 结束标签 标签内的参数 ,

,,
, , SRC,HREF 标签内的参数“house.gif” , “morePix.html” 值 assign_op 赋值号 = 3.3.5 b)a*b*……z* c) /\\*([^*”]|\\*[^/]|\\”([^”]*)\\”)*\\*/ h)b*(a|ab)* 3.7.3d

F转G错误，F跳转后的状态子集应包含9

第二次作业答案：

4.2.2 最左推导 S->SS S->S*S S->(S)*S S->(S+S)*S S->(a+S)*S S->(a+a)*S S->(a+a)*a Parse tree:

SSS*Sa(S)S+S 最右推导： S->SS S->S*a S->(S)*a

aa S->(S+S)*a S->(S+a)*a S->(a+a)*a

无二义

第一章

习题1.6.3：对于图1-14中的块结构代码，假设使用常见的声明的静态作用域规则，给出其中12个声明中的每一个的作用域？ { int w, x ,y ,z; /*块B1 */ { int x, z; /*块B2 */ { int w, x; } /*块B3 */ } { int w, x; /*块B4 */ { int y, z;} /*块B5 */ } } 答： 声 明 块 变 作 用 域 量 W X Y Z B1 B2 B3 B4 B5 B1-B3-B4 / B3 B4 / B1-B2-B4 B2-B3 B3 B4 / B1-B5 / / / B5 B1-B2-B5 B2 / / B5

习题1.6.4：下面C代码的打印结果是什么？ #define a (x+1) Int x=2; Void b(){ x=a;printf(“%d\\n”,x);} Void b(){ x=1;printf(“%d\\n”,a);} Void main(){b();c();} 答：输出结果是 3 2

调用函数b()时，a=x+1此

1. 编译程序的功能（P1，图1.1）

1) 高级语言程序（源程序）→编译程序→低级语言程序（目标程序） 2)

2. 编译过程和编译程序的结构（P2）

1) 编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化、目

标代码生成六个阶段 2) 编译程序结构框图

3)

3. 解释程序（P7）

1) 不需要在运行前把源程序翻译成目标代码，也可以让我们实现在某台机器上运行程

序并生成结果 2)

4. 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程

序的总体结构图。 （P11，习题2） 答：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。

词法分析程序：从左到右扫描源程序，识别单词及其相关属性

语法分析程序：分析源程序的结构，判别它是否为相应程序设计语言中的一个合法程序

语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息 中间代码生成程序：将源程序变成一种内部 表示形式。

代码优化程序：对中间代码进行变换或改造，使生成的代码更为高效

目标代码生

精品文档

精品文档第1章引言

1、解释下列各词

源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。

源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。

目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序

（结果程序）一般可由计算机直接执行。

低级语言：机器语言和汇编语言。

高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。

翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。

编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），

然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。

解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。

2、什么叫“遍”？

指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加