西邮编译原理期中试题

⑴ 帮我看看下面 编译原理 的题目: 谢谢!

23. D

24. D

25. A

26. D

27. C

28. B

29. D

30. A

31. A

32. B

33. A

34. 不太确定，蒙D

35. A

36. 不太确定，蒙A

37. D

38. C

39. D

40. 不知道

二、

1. A,B

2. A,D

3. C,D

4. A,C

5. A,B,D

6. A,B,C,D
   

⑵ 编译原理试题·

Lex和Yacc应用方法(一).初识Lex
草木瓜 20070301
Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler
编译器代码生成器)是Unix下十分重要的词法分析，语法分析的工具。经常用于语言分
析，公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，
入门参考意义并不大。本文通过循序渐进的例子，从0开始了解掌握Lex和Yacc的用法。

一.Lex(Lexical Analyzar) 初步示例
先看简单的例子(注：本文所有实例皆在RetHat linux下完成):
一个简单的Lex文件 exfirst.l 内容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下执行命令flex解析，会自动生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
进行编译生成parser可执行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll链结选项，cc编译时会出现以下错误，后面会进一步说明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status

创建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通过已生成的可执行程序，进行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法会有个直观的了解：
1.定义Lex描述文件
2.通过lex，flex工具解析成lex.yy.c文件
3.使用cc编译lex.yy.c生成可执行程序

再来看一个比较完整的Lex描述文件 exsec.l ：

%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
进行解析编译：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
这里就没有加-ll选项，但是可以编译通过。下面开始着重整理下Lex描述文件.l。

二.Lex(Lexical Analyzar) 描述文件的结构介绍
Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识
别程序，由该程序识别出输入文本中的各个单词。一般可以分为<定义部分><规则部
分><用户子程序部分>。其中规则部分是必须的，定义和用户子程序部分是任选的。

(1)定义部分
定义部分起始于 %{ 符号，终止于 %} 符号，其间可以是包括include语句、声明语句
在内的C语句。这部分跟普通C程序开头没什么区别。
%{
#include "stdio.h"
int linenum;
%}
(2) 规则部分
规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则。词法规则由模式和
动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组
成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单
词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。
类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多
行执行语句，也可以用{}括起来。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.规则部分的正则表达式
规则部分是Lex描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字
符含义：
A-Z, 0-9, a-z 构成模式部分的字符和数字。
- 指定范围。例如：a-z 指从 a 到 z 之间的所有字符。
\ 转义元字符。用来覆盖字符在此表达式中定义的特殊意义，
只取字符的本身。

[] 表示一个字符集合。匹配括号内的任意字符。如果第一个字
符是^那么它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一个。

^ 表示否定。
* 匹配0个或者多个上述模式。
+ 匹配1个或者多个上述模式。
? 匹配0个或1个上述模式。
$ 作为模式的最后一个字符时匹配一行的结尾。
{ } 表示一个模式可能出现的次数。 例如: A{1,3} 表示 A 可
能出现1次或3次。[a-z]{5} 表示长度为5的，由a-z组成的
字符。此外，还可以表示预定义的变量。

. 匹配任意字符，除了 \n。
( ) 将一系列常规表达式分组。如：{Letter}({Letter}|{Digit})*
| 表达式间的逻辑或。
"一些符号" 字符的字面含义。元字符具有。如："*" 相当于 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"后跟有后续表达式，
只匹配模版中"/"前面的部分。如：模式为 ABC/D 输入 ABCD，
时ABC会匹配ABC/D，而D会匹配相应的模式。输入ABCE的话，
ABCE就不会去匹配ABC/D。

B.规则部分的优先级

规则部分具有优先级的概念，先举个简单的例子：

%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此时，如果输入内容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析词法时，是逐个字符进行读取，自上而下进行规则匹配的，读取到第一个A字符
时，遍历后发现三个规则皆匹配成功，Lex会继续分析下去，读至第五个字符时，发现
"AAAA"只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符
匹配规则。
如果将规则
AAAA {printf("THREE\n");};
改为
AAAAA {printf("THREE\n");};
./parser < file1.txt 输出结果为：
THREE
TWO

再来一个特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
并输入title，Lex解析完后发现，仍然存在两个规则，这时Lex只会选择第一个规则，下面
的则被忽略的。这里就体现了Lex的顺序优先级。把这个例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex编译时会提示：warning, rule cannot be matched.这时处理title字符时，匹配
到第一个规则后，第二个规则就无效了。
再把刚才第一个例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 显示效果是一样的，最后一项规则肯定是会忽略掉的。

C.规则部分的使用变量
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之间，加入了一些类似变量的东西，注意是没有;的，这表示int，float分
别代指特定的含义，在两个%%之间，可以通过{int}{float}进行直接引用，简化模
式定义。

(3) 用户子程序部分
最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子
程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，
当编译时不带-ll选项时，是必须加入main函数和yywrap(yywrap将下后面说明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 进行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}

三.Lex(Lexical Analyzar) 一些的内部变量和函数
内部预定义变量：
yytext char * 当前匹配的字符串
yyleng int 当前匹配的字符串长度
yyin FILE * lex当前的解析文件，默认为标准输出
yyout FILE * lex解析后的输出文件，默认为标准输入
yylineno int 当前的行数信息
内部预定义宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的
默认动作

内部预定义的函数：
int yylex(void) 调用Lex进行词法分析
int yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解
析。 因此它可以用来解析多个文件。代码可以写在第三段，这
样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的
文件，直到所有的文件都被解析。最后，yywrap() 可以返回1
来表示解析的结束。

lex和flex都是解析Lex文件的工具，用法相近，flex意为fast lexical analyzer generator。
可以看成lex的升级版本。

相关更多内容就需要参考flex的man手册了，十分详尽。

四.关于Lex的一些综述
Lex其实就是词法分析器，通过配置文件*.l，依据正则表达式逐字符去顺序解析文件，
并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈，
它不适合用于剖析外壳结构。而yacc增加了一个堆栈，并且能够轻易处理像括号这样的
结构。Lex善长于模式匹配，如果有更多的运算要求就需要yacc了。

⑶ 编译原理 试题求解

⑷ 编译原理试题

你发那么多条求助信息，也不给点分，大家怎么帮你啊，我来回答吧！记得给我追加分啊。
1.若源程序是用高级语言编写的,目标程序是 机器语言程序或汇编程序 ,则其翻译程序称为编译程序.
2.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别 单词 。
3.编译方式与解释方式的根本区别为是否生成目标代码。
4.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型 。
设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。
继续做题中.......

⑸ 信息管理与信息系统(请回答提问)

业务培养目标：本专业培养具备现代管理学理论基础、计算机科学技术知识及应用能力，掌握系统思想和信息系统分析与设计方法以及信息管理等方面的知识与能力，能在国家各级管理部门、工商企业、金融机构、科研单位等部门从事信息管理以及信息系统分析、设计、实施管理和评价等方面的高级专门人才。
业务培养要求：本专业学生主要学习经济、管理、数量分析方法、信息资源管理、计算机及信息系统方面的基本理论和基本知识，受到系统和设计方法以及信息管理方法的基本训练，具备综合运用所学知识分析和解决问题的基本能力。
毕业生应获得以下几方面的知识和能力：
l．掌握信息管理和信息系统的基本理论基本知识；
2．掌握管理信息系统的分析方法、设计方法和实现技术；
3．具有信息组织、分析研究、传播与开发利用的基本能力；
4．具有综合运用所学知识分析和解决问题的基本能力；
5．了解本专业相关领域的发展动态；
6．掌握文献检索、资料查询、收集的基本方法，具有一定的科研和实际工作能力。
[编辑本段]主干课程
主干学科：管理学、经济学、计算机科学与技术。
主要课程：经济学、会计学、市场营销学、生产与运作管理、组织战略与行为学、管理学原理、应用数理统计、运筹学、计算机系统与系统软件、数据结构与数据库等。
主要实践性教学环节：程序设计实习、管理软件实习、毕业设计等。一般安排18周，其中毕业设计不少于12周。
修业年限：四年
授予学位：管理学学士
相近专业：管理科学 工程管理 体育产业管理 资产评估
什么样的一门学科-对信息进行分类、管理、以及研究如何应用的科学
这个专业主要是研究信息管理以及信息系统分析、设计、实施、管理和评价等方面的基本理论和方法。通俗地讲，就是从信息中发掘财富。现代社会正是信息化社会，大量纷繁的信息如何管理，并且从中获得有效的信息，正是信息管理科学的研究重点。与计算机结合，使计算机作为工具，信息管理更加有效和实用。随着企业经营规模的现代化，对信息管理的要求越来越强烈。例如铁路订票系统，就是对车票这种信息的查询和管理系统。可以说软件开发的最主要面向的客户就是帮助企业制作良好的信息管理系统。信息管理涉及咨询、服务、物流等很多行业，有很多的就业机会。
授课的内容— 偏重计算机、涉及管理课程
学习的内容涵盖计算机学科和管理学科的核心课程。管理学科方面有会计学、经济学、管理学、统计学；计算机方面有高级语言程序设计、数据结构、数据库、操作系统、计算机网络。两学科综合课程有电子商务、管理信息系统等。独立设计、实现小型信息系统或大型信息系统中的某一子系统，并在此基础上完成毕业设计论文，最后一个学期还应安排相应的管理软件上机实习。
专门设置信息管理和信息系统专业的院校很多，如中国人民大学、清华大学、北京大学、武汉大学、哈尔滨工业大学、西安交通大学、浙江大学、西交利物浦大学等。其中工科院校偏重对计算机应用的学习，文理院校偏重在管理上的研究，另外西交利物浦大学（由西安交通大学和英国利物浦大学在中国苏州联合创办的一所具有独立法人的招分在一本以上的大学）所开设的此专业方向则为“电子金融方向”。电子金融是指应用电子通信和电子计算来提供金融服务和金融市场，它包括电子支付系统、金融服务企业的运营以及金融市场的操作。计算机系统、互联网及其相关技术作为新的分配渠道，为金融服务企业有效地创造满足他们客户的需求的产品提供了条件。同时，这些新的技术让客户能轻松的利用广泛的资源和供应商得到金融信息和服务，从而打破了金融服务企业竞争的壁垒。这使得金融服务行业需要不断的创新，也加大了市场对既拥有必要的计算机技能，还同时了解金融产品、金融服务以及金融服务商如何运营等专业知识的毕业生的需求。电子金融专业就是为了满足市场的这一需求而开设的。
有关联的其他专业：计算机科学与技术、企业管理、情报学、图书馆学。
名称不同但实质相同的专业： 计算机信息管理
信息管理专业，是一个涵盖面很广的专业，所以，在不同的学校的内容可能差异很大。
专家提醒
这是一个适应面相当广的专业。就业机会很多，近年来主要是：
软件开发人员-----帮助企业和组织问题，起薪一般在2000-3000元/月；
要注意这个专业在有的学校实际是学习计算机软件，有的可能是以前的图书馆系的改名，报考是一定要查明这些情况。
毕业后干什么— 主要是与计算机应用相关的工作，还有一些信息管理的工作
网络或系统管理员------企业或组织高效运行的保障，起薪一般在1500-3000元/月；
企业信息管理员 —— 在企业中从事信息搜集、管理工作，起薪一般在1000-3000元/月。
报考什么样的学校—— 应查明各校研究方向上的不同
[编辑本段]专业所学课程
01计算机基础
02形势与政策
03思想道德修养与法律基础
04体育
05军事理论
06大学生心理素质拓展训练
07高级语言程序设计
08西方经济学原理
09线性代数
10数据库应用
11中国近现代史纲要
12高等数学
13管理学原理
14概率论与数理统计
15数据结构
16面向对象程序设计
17中国化马克思主义
18大学英语
19数据库系统原理
20计算机操作系统
21市场调查与预测
22计算方法
23多媒体技术
24计算机硬件技术概论
25马克思主义基本原理
26离散数学
27运筹学
28管理应用软件开发
29市场营销概论
30电子商务概论
31可视化程序设计
32财务管理
33动态网页应用
34计算机网络
35企业战略管理
36数据仓库与数据挖掘
37信息系统分析设计
38管理信息系统
39Unix系统与编译技术
40文学修养
41就业指导
42决策支持系统
43企业资源计划
44统一建模语言（UML）
45人力资源管理
46微观经济学
47宏观经济学
48信息安全概论
49数据库原理
50JAVA语言
51知识产权法
52企业竞争情报
53信息分析与预测
54计算机实用软件
55编译原理
56概率论与数理统计
57计算机系统维护
58市场营销学
59线性代数
[编辑本段]开设院校
山东中医药大学 山东理工大学 大连海事大学 吉林化工学院 福建工程学院 重庆师范学院 贵州大学 贵州财经学院 贵州民族学院 云南大学 昆明理工大学 云南财贸学院 西北大学 西安石油大学 西安财经学院 西北师范大学 兰州商学院 新疆农业大学 新疆财经学院 北京工业大学 北京工商大学 北京物资学院 北京机械工业学院 北京联合大学 首都经济贸易大学 天津工业大学 天津理工学院 天津师范大学 天津商业大学 天津财经大学 河北大学 河北理工学院 河北科技大学 河北经贸大学 山西大学 山西财经大学 内蒙古大学 辽宁大学 辽宁工程技术大学 锦州师范学院 吉林工学院 黑龙江大学 大庆石油学院 哈尔滨商业大学 上海工程技术大学 上海大学 南京航空航天大学 江苏大学 扬州大学 杭州商学院 浙江财经学院 安徽大学 安徽理工大学 仰恩大学 江西师范大学 南昌大学 济南大学 山东经济学院 山东工商学院 青岛大学 河南科技学院 河南师范大学 河南财经学院 湘潭大学 湖南商学院 广东金融学院 华南师范大学 广东商学院 广东工业大学 广西大学 中南民族大学 中央财经大学 东北财经大学 上海财经大学 江西财经大学 山东财政学院 中南财经政法大学 对外经济贸易大学 湖南大学 西南财经大学 西安交通大学 中国农业大学 南京农业大学 北京林业大学 东北电力学院 三峡大学 河海大学 北京邮电大学 北京信息工程学院 南京邮电学院 杭州电子工业学院 重庆邮电学院 电子科技大学 北京城市学院 西安电子科技大学 北京交通大学 西南交通大学 上海海运学院 北京广播学院 中国医科大学(五年) 吉林大学(五年) 中南大学(五年) 北京印刷学院 华侨大学 暨南大学 长春税务学院 中国科学技术大学 华东船舶工业学院 北京理工大学 南京理工大学 重庆工业管理学院 北京航空航天大学 郑州航空工业管理学院 哈尔滨工业大学 武汉理工大学 安徽财经大学（大三分两个方向：信息管理；信息系统） 北京大学 中国人民大学 清华大学 北京科技大学 北京师范大学 北京外国语大学 南开大学 天津大学 大连理工大学 东北大学 吉林大学 复旦大学 同济大学 东华大学 华东师范大学 南京大学 东南大学 浙江大学 厦门大学 厦门理工学院 山东大学 武汉大学 华中科技大学 华中师范大学 中南大学 吉首大学 中山大学 华南理工大学 重庆大学 西南大学 四川大学 西安交通大学 兰州大学 深圳大学 哈尔滨理工大学 西北工业大学 郑州大学 合肥工业大学 延边大学 广西民族学院 北京服装学院 首都师范大学 河北工业大学 太原重型机械学院 华北工学院 山西农业大学 内蒙古农业大学 内蒙古财经学院 沈阳航空工业学院 沈阳理工大学 辽宁石油化工大学 沈阳化工学院 大连工业大学 沈阳建筑大学 沈阳师范学院 长春理工大学 黑龙江科技学院 上海外国语大学 南京工业大学 盐城工学院 中国药科大学 南京财经大学 浙江科技学院 浙江工程学院 温州医学院 东华理工大学 南昌航空工业学院 山东建筑工程学院 河南大学 新乡医学院 湖北大学 中国地质大学 武汉科技大学 武汉科技学院 五邑大学 广西工学院 桂林电子工业学院 桂林工学院 重庆交通学院 重庆工商大学 西南科技大学 西南石油学院 四川理工学院 成都理工大学 成都信息工程学院 贵州师范大学 云南农业大学 西安理工大学 西安邮电学院 西北农林科技大学 青海民族学院 宁夏大学 北京语言大学 国际关系学院 天津外国语学院 河北建筑科技学院 唐山学院 华北科技学院 中央司法警官学院 山西医科大学 长治医学院 大连外国语学院 吉林农业大学 上海应用技术学院 上海杉达学院 淮阴工学院 南京林业大学 嘉兴学院 温州师范学院 安庆师范学院 皖南医学院 阜阳师范学院 合肥学院 福州大学 浙江传媒学院（分两个方向：网络、多媒体）江西科技师范学院 德州学院 泰山医学院 济宁医学院 烟台师范学院 河南理工大学（原焦作工学院） 安阳师范学院 武汉工业学院 南华大学 衡阳师范学院 广东药学院（分两个方向：医药软件工程方向和医药信息方向） 玉林师范学院 重庆三峡学院 伊犁师范学院 河南科技大学等�河北工程大学 鲁东大学 山东政法学院 西藏民族学院 大连交通大学 华北电力大学（北京） 北京信息科技大学 安康学院

⑹ 编译原理试题

习题一、单项选择题
1、将编译程序分成若干个“遍”是为了 。
a．提高程序的执行效率
b．使程序的结构更加清晰
c．利用有限的机器内存并提高机器的执行效率
d．利用有限的机器内存但降低了机器的执行效率
2、构造编译程序应掌握 。
a．源程序 b．目标语言
c．编译方法 d．以上三项都是
3、变量应当 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、编译程序绝大多数时间花在 上。
a．出错处理 b．词法分析
c．目标代码生成 d．管理表格
5、 不可能是目标代码。
a．汇编指令代码 b．可重定位指令代码
c．绝对指令代码 d．中间代码
6、使用 可以定义一个程序的意义。
a．语义规则 b．词法规则
c．产生规则 d．词法规则
7、词法分析器的输入是 。
a．单词符号串 b．源程序
c．语法单位 d．目标程序
8、中间代码生成时所遵循的是- 。
a．语法规则 b．词法规则
c．语义规则 d．等价变换规则
9、编译程序是对 。
a．汇编程序的翻译 b．高级语言程序的解释执行
c．机器语言的执行 d．高级语言的翻译
10、语法分析应遵循 。
a．语义规则 b．语法规则
c．构词规则 d．等价变换规则
解答
1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多的就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。
6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。
7、b 8、c 9、d 10、c
二、多项选择题
1、编译程序各阶段的工作都涉及到 。
a．语法分析 b．表格管理 c．出错处理
d．语义分析 e．词法分析
2、编译程序工作时，通常有 阶段。
a．词法分析 b．语法分析 c．中间代码生成
d．语义检查 e．目标代码生成
解答
1．b、c 2. a、b、c、e
三、填空题
1、解释程序和编译程序的区别在于 。
2、编译过程通常可分为5个阶段，分别是 、语法分析 、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是 ，最后阶段的输出为 程序。
4、编译程序是指将 程序翻译成 程序的程序。 解答
是否生成目标程序 2、词法分析 中间代码生成 3、源程序 目标代码生成 4、源程序 目标语言
一、单项选择题
1、文法G：S→xSx|y所识别的语言是 。
a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
2、文法G描述的语言L(G)是指 。
a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}
c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)}
3、有限状态自动机能识别 。
a. 上下文无关文法 b. 上下文有关文法
c.正规文法 d. 短语文法
4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 。
a. 若f(a)>g(b)，则a>b b.若f(a)<g(b)，则a<b
c. a~b都不一定成立 d. a~b一定成立
5、如果文法G是无二义的，则它的任何句子α 。
a. 最左推导和最右推导对应的语法树必定相同
b. 最左推导和最右推导对应的语法树可能不同
c. 最左推导和最右推导必定相同
d. 可能存在两个不同的最左推导，但它们对应的语法树相同
6、由文法的开始符经0步或多步推导产生的文法符号序列是 。
a. 短语 b.句柄 c. 句型 d. 句子
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
则句型P+T+i的句柄和最左素短语为 。
a.P+T和i b. P和P+T c. i和P+T+i d.P和T
8、设文法为：S→SA|A
A→a|b
则对句子aba，下面 是规范推导。
a. SÞSAÞSAAÞAAAÞaAAÞabAÞaba
b. SÞSAÞSAAÞAAAÞAAaÞAbaÞaba
c. SÞSAÞSAAÞSAaÞSbaÞAbaÞaba
d. SÞSAÞSaÞSAaÞSbaÞAbaÞaba
9、文法G：S→b|∧(T)
T→T,S|S
则FIRSTVT(T) 。
a. {b,∧,(} b. {b,∧,)} c.{b,∧,(,，} d.{b,∧,),，}
10、产生正规语言的文法为 。
a. 0型 b. 1型 c. 2型 d. 3型
11、采用自上而下分析，必须 。
a. 消除左递归 b. 消除右递归 c. 消除回溯 d. 提取公共左因子
12、在规范归约中，用 来刻画可归约串。
a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语
13、有文法G：E→E*T|T
T→T+i|i
句子1+2*8+6按该文法G归约，其值为 。
a. 23 B. 42 c. 30 d. 17
14、规范归约指 。
a. 最左推导的逆过程 b. 最右推导的逆过程
c. 规范推导 d. 最左归约的逆过程
[解答]
1、选c。
2、选a。
3、选c。
4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以，由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。
5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左推导，则必然有二义性。故选a。
6、选c。
7、由图2-8-1的语法树和优先关系可以看出应选b。

8、规范推导是最左推导，故选d。
9、由T→T,…和T→(… 得FIRSTVT(T))={(,，)}；
由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即
FIRSTVT(T)={b,∧,(,，}； 因此选c。
10、d 11、c 12、b 13、b 14、b
二、多项选择题
1、下面哪些说法是错误的 。
a. 有向图是一个状态转换图 b. 状态转换图是一个有向图
c.有向图是一个DFA d.DFA可以用状态转换图表示
2、对无二义性文法来说，一棵语法树往往代表了 。
a. 多种推导过程 b. 多种最左推导过程 c.一种最左推导过程
d.仅一种推导过程 e.一种最左推导过程
3、如果文法G存在一个句子，满足下列条件 之一时，则称该文法是二义文法。
a. 该句子的最左推导与最右推导相同
b. 该句子有两个不同的最左推导
c. 该句子有两棵不同的最右推导
d. 该句子有两棵不同的语法树
e.该句子的语法树只有一个
4、有一文法G：S→AB
A→aAb|ε
B→cBd|ε
它不产生下面 集合。
a. {anbmcndm|n,m≥0} b. {anbncmdm|n,m>0}
c. {anbmcmdn|n,m≥0} d. {anbncmdm|n,m≥0}
e. {anbncndn|n≥0}
5、自下而上的语法分析中，应从 开始分析。
a. 句型 b. 句子 c. 以单词为单位的程序
d. 文法的开始符 e. 句柄
6、对正规文法描述的语言，以下 有能力描述它。
a.0型文法 b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法
解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e
三、填空题
1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ，它一定只出现在产生式的 部。
2、最左推导是指每次都对句型中的 非终结符进行扩展。
3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。
4、采用 语法分析时，必须消除文法的左递归。
5、 树代表推导过程， 树代表归约过程。
6、自下而上分析法采用 、归约、错误处理、 等四种操作。
7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。
解答 1、空集 终结符 右
2、最左
3、自上而上 自下而上
4、自上而上
5、语法 分析
6、移进 接受
7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限
四、判断题
1、文法 S→aS|bR|ε描述的语言是(a|bc)* ( )
R→cS
2、在自下而上的语法分析中，语法树与分析树一定相同。 （ ）
3、二义文法不是上下文无关文法。 （ ）
4、语法分析时必须先消除文法中的左递归。 （ ）
5、规范归约和规范推导是互逆的两个过程。 （ ）
6、一个文法所有句型的集合形成该文法所能接受的语言。 （ ）
解答 1、对 2、错 3、错 4、错 5、错 6、错
五、简答题
1、句柄 2、素短语 3、语法树 4、归约 5、推导
[解答]
1、句柄：一个句型的最左直接短语称为该句型的句柄。
2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。
3、语法树：满足下面4个条件的树称之为文法G[S]的一棵语法树。
①每一终结均有一标记，此标记为VN∪VT中的一个符号；
②树的根结点以文法G[S]的开始符S标记；
③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；
④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,XK，则A→X1,X2,…,XK，必然是G的一个产生式。
4、归约：我们称αγβ直接归约出αAβ，仅当A→γ 是一个产生式，且α、β∈(VN∪VT)*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。
5、推导：我们称αAβ直接推出αγβ，即αAβÞαγβ，仅当A→ γ 是一个产生式，且α、β∈(VN∪VT)*。如果α1Þα2Þ…Þαn，则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导，则称α1可推导出αn。推导是归约的逆过程。
六、问答题
1、给出上下文无关文法的定义。
[解答]
一个上下文无关文法G是一个四元式（VT,VN,S, P），其中：
●VT是一个非空有限集，它的每个元素称为终结符号；
●VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=Φ；
●S是一个非终结符号，称为开始符号；
●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈VN，
α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。
2、文法G[S]：
S→aSPQ|abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
（1）它是Chomsky哪一型文法？
（2）它生成的语言是什么？
[解答]
（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：
SÞabQÞabc
SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc
SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞ
aaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc
……
于是得到文法G[S]生成的语言L={anbncn|n≥1}
3、按指定类型，给出语言的文法。
L={aibj|j＞i≥1}的上下文无关文法。
【解答】
（1）由L={aibj|j＞i≥1}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→bS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法G[S]为：
G[S]：S→aSb|Sb|b
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）写出句子acabcbbdcc的最左推导过程。
【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示
句柄:AaB Bd

图2-8-2 语法树
（2）句子acabcbbdcc的最左推导如下：
SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA
ÞacabcbbdcAÞacabcbbdcc
5、对于文法G[S]：
S→（L）|aS|a L→L, S|S
（1）画出句型（S,（a））的语法树。（2）写出上述句型的所有短语、直接短语、句柄和素短语。
【解答】
（1）句型（S,（a））的语法树如图2-8-3所示

（2）由图2-8-3可知：
①短语：S、a、(a)、S,(a)、(S,(a))；
②直接短语：a、S；
③句柄：S；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；

因此素短语为a。
6、考虑文法G[T]：
T→T*F|F
F→F↑P|P
P→（T）|i
证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。
【解答】
首先构造T*P↑（T*F）的语法树如图2-8-4所示。

由图2-8-4可知，T*P↑（T*F）是文法G[T]的一个句型。
直接短语有两个，即P和T*F；句柄为P。

一、单项选择题
1、词法分析所依据的是 。
a. 语义规则 b. 构词规则 c. 语法规则 d. 等价变换规则
2、词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置
c. 单词的种别编码和自身值 d. 单词自身值
3、正规式M1和M2等价是指 。
a. M1和M2的状态数相等 b. M1和M2的有向弧条数相等
c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等
4、状态转换图（见图3-6-1）接受的字集为 。

a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合
c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合
5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。
a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好
c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段
解答 1、b 2、c 3、c 4、d 5、b
二、多项选择题
1、在词法分析中，能识别出 。
a. 基本字 b. 四元式 c. 运算符
d. 逆波兰式 e. 常数
2、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。
a. b(ab)* b. b(ab)+ c.(ba)*b
d. (ba)+b e. b(a|b)
解答 1、a、c、e 2、a、b、d
三、填空题
1、确定有限自动机DFA是 的一个特例。
2、若二个正规式所表示的 相同，则认为二者是等价的。
3、一个字集是正规的，当且仅当它可由 所 。
解答 1、NFA 2、正规集 3、DFA（NFA）所识别
四、判断题
1、一个有限状态自动机中，有且仅有一个唯一终态。 （ ）
2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。 （ ）
3、自动机M和M′的状态数不同，则二者必不等价。 （ ）
4、确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ）
5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ）
6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 （ ）
7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。 （ ）
8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。 （ ）
解答 1 、2、3、错 4、5、6、7、8、正确
五、基本题
1、设M＝（{x,y}, {a,b}, f,x,{y}）为一非确定的有限自动机，其中f定义如下：
f（x,a）＝{x,y} f（x,b）＝{y}
f（y,a）＝φ f（y,b）＝{x,y}
试构造相应的确定有限自动机M′。
解答：对照自动机的定义M=(S,Σ,f,S0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有限自动机，先画出NFA M相应的状态图，如图3-6-2所示。

用子集法构造状态转换矩阵表3-6-3所示。
I Ia Ib
{x} {x,y} {y}
{y} — {x,y}
{x,y} {x,y} {x,y}
将转换矩阵中的所有子集重新命名而形成表3-6-4所示的状态转换矩阵。
表3-6-4 状态转换矩阵
a b
0 2 1
1 — 2
2 2 2
即得到M′=（{0,1,2}, {a,b}, f,0, {1,2}），其状态转换图如图3-6-5所示。

将图3-6-5的DFA M′最小化。首先，将M′的状态分成终态组{1，2}与非终态组{0}；其次，考察{1,2}。由于{1,2}a={1,2}b={2}⊂{1,2}，所以不再将其划分了，也即整个划分只有两组{0}，{1,2}：令状态1代表{1,2}，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图3-6-6所示化简DFA M′。

2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M；
解答：首先用A+=AA*改造正规式得：b*(d|ad)(b|ab)(b|ab)*；其次，构造该正规式的NFA M，如图3-6-7所示。