编译原理词法分析习题集无答案

《编译原理词法分析习题集无答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译原理》习题（一）——词法分析一、是非题（请在括号内，正确的划√，错误的划×）1．编译程序是对高级语言程序的解释执行。()2．一个有限状态自动机中，有且仅有一个唯一的终态。()3．两个正规集相等的必要条件是他们对应的正规式等价。()4.对任何正规表达式e，都存在一个DFA　M，满足L(M)＝L(e)。二、选择题1．词法分析器的输出结果是_____。　A．()记号　　　　　　B．()相应条目在符号表中的位置　C．()记号和属性二元组　　D．()属性值2．正规式M1和M2等价是指_____。 A．()M1和M2的状态数相

2、等 　　      B．()M1和M2的有向边条数相等　C．()M1和M2所识别的语言集相等　　D．()M1和M2状态数和有向边条数相等3.编译过程可分为（），（），（），（），（）和（）六个阶段。4．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合5．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化6．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单

3、位即A．字符B．单词C．句子D．句型7．构造编译程序应掌握______。A．()源程序   　　　B．()目标语言     C．()编译方法    D．()以上三项都是8．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码三、填空题1．计算机执行用高级语言编写的程序主要有两种途径：和。6.扫描器的任务是从（）中识别出一个个（）。17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。1．编译程序首先要识别出源程序中每个()，然后再分析每个()并翻译其意义。3．通常

4、把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的()，中间代码生成、代码优化与目标代码的生成则是对源程序的()。5．对编译程序而言，输入数据是()，输出结果是()。6.若二个正规式所表示的相同，则认为二者是等价的。四、名词解释题：1．词法分析2.扫描器3.翻译器4解释器5.编译器五、简答题(一)、描述由正规式b*(abb*)*(a

5、e)定义的语言，并画出接受该语言的最简DFA。答：(二)、描述由正规式b*a(bb*a)*b*定义的语言，并画出接受该语言的最简DFA。答：(三).一字母表Σ={a,

6、b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。答：(四).令Σ={a,b}，则正规式a*b

7、b*a表示的正规集是什么？答：(五)、构造下列正规式相应的DFA（用状态转换图表示）（1）0（0

8、1）*1（2）0*10*10*10*1（3）letter（letter

9、digit）*答：（1）（2）（3）(六)．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，d，{A}，{C})，其中：d(A，0)={C}d(A，1)={A，B}d(B，1)={C}d(C，1)={C}。请画出状态转换距阵和状态转换图

10、。解：(七)．编译程序和高级语言有什么区别?(八)．编译程序的工作分为那几个阶段?(九)、有穷自动机M接受字母表S＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFAM及和M等价的正规式。(十)、证明正规式(ab)*a与正规式a(ba)*等价（用构造他们的最小的DFA方法）。【答案：】(十一)、设S={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(3分)NFA:(2分)确定化：(3分)（十二

11、）、处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。（十三）设有字母表{a，b}上的正规式R=(ab

12、a)*。构造NFA，确定化，化简解：（1）（2）将（1）所得的非确定有限自动机确定化ab-+013123+12312313+13123（3）对（2）得到的DFA化简，合并状态：(十四)、给定文法G[S]：S→aA

13、bQ；A→aA

14、bB

15、b；B→bD

16、aQ；Q→aQ

17、bD

18、b；D→bB

19、aA；E→aB

20、bFF→bD

21、aE

22、b构造相应的最小的DFA。