编译原理词法分析习题集无答案
《编译原理》习题
（一）——词法分析
一、是非题（请在括号内，正确的划√，错误的划×）
1．编译程序是对高级语言程序的解释执行。( )
2．一个有限状态自动机中，有且仅有一个唯一的终态。()
3．两个正规集相等的必要条件是他们对应的正规式等价。( )
4.对任何正规表达式e，都存在一个DFAM，满足L(M)＝L(e)。
二、选择题
1．词法分析器的输出结果是___。
A．( )记号
B．( )相应条目在符号表中的位置
C．( )记号和属性二元组
D．( )属性值
2．正规式M 1和M 2等价是指___。
A．( ) M1和M2的状态数相等
B．( ) M1和M2的有向边条数相等
C．( ) M1和M2所识别的语言集相等
D．( ) M1和M2状态数和有向边条数相等
3.编译过程可分为（），（），（），（），（）和（）六个阶段。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．生成目标代码
三、填空题
1．计算机执行用高级语言编写的程序主要有两种途径：
和。
6.扫描器的任务是从（）中识别出一个个（）。
17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。
1．编译程序首先要识别出源程序中每个()，然后再分析每个()并翻译其意义。
3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的()，中间代码生成、代码优化与目标代码的生成则是对源程序的()。
5．对编译程序而言，输入数据是()，输出结果是()。
6.若二个正规式所表示的相同，则认为二者是等价的。
四、名词解释题：
1．词法分析
2.扫描器
3.翻译器
4解释器
5.编译器
五、简答题字符串截取倒数第二个
(一)、描述由正规式b*(abb*)*(a|)定义的语言，并画出接受该语言的最简DFA。
答：
(二)、描述由正规式b a(bb a)b定义的语言，并画出接受该语言的最简DFA。
答：
(三).一字母表Σ={a, b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。
答：
(四).令Σ={a,b}，则正规式a*b|b*a 表示的正规集是什么？
答：
(五)、构造下列正规式相应的DFA（用状态转换图表示）
（1）0（0 | 1）*1
（2）0*10*10*10*1
（3）letter（letter | digit）*
答：
（1）
（2）
（3）
(六)．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，，{A}，{C})，其中：
(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。请画出状态转换距阵和状态转换图。
解：
(七)．编译程序和高级语言有什么区别?
(八)．编译程序的工作分为那几个阶段?
(九)、有穷自动机M接受字母表＝{0,1}上所有满足下述条件的串：
每个1都有0直接跟在右边。构造一个最小的DFA M及和M等价的正规式。
(十)、证明正规式(ab)*a与正规式a(ba)*等价（用构造他们的最小的DFA方法）。
【
答案：】
(十一)、设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)
答：
构造相应的正规式：
(3分)
NFA:
(2分)
确定化：
(3分)
（十二）、处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态
转换图。
（十三）设有字母表{a，b}上的正规式R=(ab|a)*。构造NFA，确定化，化简
解：
（1）
（2）将
（1）所得的非确定有限自动机确定化
（3）对
（2）得到的DFA化简，合并状态：
(十四)、给定文法G[S]：
S→aA|bQ；A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；
E→aB|bF F→bD|aE|b
构造相应的最小的DFA 。

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