第一章：编译系统概述
一．单选题
1．编译程序前三个阶段完成的工作是（ C ）。
A．词法分析、语法分析和代码优化   
B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成
D．词法分析、语法分析和代码优化
2．编译程序绝大多数时间花在（ D ）上。
  A．出错处理    B．词法分析    C．目标代码生成  D．表格管理
3．编译程序是对（ C ）。
  A．汇编程序的翻译          B．高级语言程序的解释执行 
C．高级语言的翻译          D．机器语言的执行
4．在使用高级语言编程时，首先可通过编译程序发现源程序的全部（  A  ）错误。
  A．语法      B．语义      C．语用        D．运行
二．填空题
1．编译程序首先要识别出源程序中每个( 单词 )，然后再分析每个( 句子 )并翻译其意义。
2．通常把编译过程分为分析前端与后端两大阶段。词法、语法和语义分析是对源程序的( 分析 )，中间代码生成、代码优化与目标代码的生成则是对源程序的 (综合 )。
3．对编译程序而言，输入数据是( 源程序 )，输出结果是( 目标程序 )。
4．对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、
代码生成）报告的。
（1） else 没有匹配的if  （语法分析）
（2） 数组下标越界  （语义分析）
（3） 使用的函数没有定义  （语法分析）
（4） 在数中出现非数字字符  （词法分析）
5．如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段： （  编译阶段  ） 和（ 运行阶段  ）。如果编译程序生成的目标程序是汇编语言程序，则源程序的执行方式分成三个阶段：（  编译阶段  ）（ 汇编阶段 ）和（ 运行阶段   ）。
6．编译程序在其工作过程使用最多的数据结构是（  表   ），它记录着源程序中各种信息，以便查询或修改，在这些（  表  ）中，尤以（  符号表    ）最重要，它的生存期最长，使用也最频繁。
完成字符串是什么三．简述题：
1．编译程序的工作分为那几个阶段?
答：词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间
代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。
第二章 词法分析
一．单选题：
1．语言是（ A ）。
A．句子的集合    B．产生式的集合  C．符号串的集合  D．句型的集合
2．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（ B  ）。                           
    A． 字符        B．单词          C．句子        D．句型
3．词法分析的任务是（ A ）。
    A．识别单词  B．分析句子的含义  C．识别句子    D．生成目标代码
4．DFA（如图所示）接受的字集为（ D ）。
   
A．以0开头的二进制数组成的集合    B．以0结尾的二进制组成的集合
    C．含奇数个0的二进制组成的集合    D．含偶数个0的二进制组成的集合 
5．词法分析器的输出结果是（ C ）。
    A．单词的种别编码                  B．单词在符号表中的位置
    C．单词的种别编码和自身的值        D．单词自身值
二．填空题：
1．描述程序设计语言的词法的机制是（正则表达式），识别机制是（有穷状态自动机）。
2．最小状态DFA的含义是（没有多余状态，没有两个状态等价）。
3．确定有限自动机DFA是（ NFA   ）的一个特例。
4．确定的有穷自动机是一个（ 五元组 ），通常表示为（ DFA = ( S，∑，f , s0  Z ) ）。
三、简述题：
1．词法分析
答：词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。
四．综合应用题：
1．设有非确定的有自限动机NFA  M=({A，B，C}，{0，1}，，{A}，{C})，其中：
 (A，0)={C}   (A，1)={A，B}   (B，1)={C}   (C，1)={C}。请画出状态转换距阵和状态转换图。
解：
状态转换距阵为：
0
1
A
C
A，B
B
C
C
C
状态转换图为：
2．有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放 ≥3分的硬币，便可得到一块糖（注意；只给一块并且不钱）。
（1）写出售货机售糖的正则表达式；
（2）构造识别上述正则式的最简DFA。
     
解：（1）设a = 1, b = 2,，则售货机售糖的正则表达式为：a (b | a (a | b)) | b (a | b) 。
  （2）画出与正则表达式a (b | a (a | b)) | b (a | b)对应的NFA，如图所示：
                                       
3．设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
解：构造相应的正规式：(0|1)*1(0|1) 
NFA: 
                1                        1
                                1       
                  0                        0
确定化：(3分)
I
{0,1,2}
{1,2}
{1,2,3}
{1,2}
{1,2}
{1,2,3}
{1,2,3}
{1,2,4}
{1,2,3,4}
{1,2,4}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,4}
{1,2,3,4}
                            0
                                                      1
              0          1        0          0
                      0                1
           
                  1                      1
4．构造一个DFA，使其接受 = {0， 1}上0和1的个数都是偶数的字符串。
解：
5．构造一个字母表{0，1}上的DFA，其接受的串中所含0的数目能被3除尽。
解：
6．写出在 = {a , b}上不是a开头的，以aa结尾的的字符串集合的正规表达式，并直接构造与之等价的状态最少的DFA。
解：
7．写一个文法使其语言为L(G)={anbncm| m，n ≥ 1，n为奇数，m为偶数}。
解： 文法G(S)：
8．构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。
解：构造相应的正规式：(a|b)*ab(a|b)*
          a                                          a
                            a        b                     
          b                                            b
确定化：
I
{0,1,2}
{1,2,3}
{1,2}
{1,2,3}
{1,2,3}
{1,2,4,5,6}
{1,2}
{1,2,3}
{1,2}
{1,2,4,5,6}
{1,2,3,5,6}
{1,2,5,6}
{1,2,3,5,6}
{1,2,3,5,6}
{1,2,4,5,6}
{1,2,5,6}
{1,2,3,5,6}
{1,2,5,6}
                            b                        b

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。