编译原理词法分析习题集带答案
《编译原理》习题（⼀）——词法分析
⼀、是⾮题（请在括号内，正确的划√，错误的划×）
1．编译程序是对⾼级语⾔程序的解释执⾏。(× )
2．⼀个有限状态⾃动机中，有且仅有⼀个唯⼀的终态。(×)
9．两个正规集相等的必要条件是他们对应的正规式等价。(× )
⼆、选择题
1．词法分析器的输出结果是_____。
A．( ) 记号 B．( ) 相应条⽬在符号表中的位置
C．( ) 记号和属性⼆元组D．( ) 属性值
2．正规式 M 1 和 M 2 等价是指_____。
A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等
C．( ) M1和M2所识别的语⾔集相等D．( ) M1和M2状态数和有向边条数相等3．语⾔是
A．句⼦的集合 B．产⽣式的集合
C．符号串的集合 D．句型的集合
4．编译程序前三个阶段完成的⼯作是
A．词法分析、语法分析和代码优化
B．代码⽣成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码⽣成
D．词法分析、语法分析和代码优化
5．扫描器所完成的任务是从字符串形式的源程序中识别出⼀个个具有独⽴含义的最⼩语法单位即
basic语言解释程序属于什么
A．字符 B．单词 C．句⼦ D．句型
6．构造编译程序应掌握______。
A．( )源程序B．( ) ⽬标语⾔
C．( ) 编译⽅法D．( ) 以上三项都是
7．词法分析的任务是
A．识别单词 B．分析句⼦的含义
C．识别句⼦ D．⽣成⽬标代码
三、填空题
1．计算机执⾏⽤⾼级语⾔编写的程序主要有两种途径：___解释__和__编译___。
3.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码⽣成），（优化）和（⽬标代码⽣成）五个阶段。
6.扫描器的任务是从（源程序中）中识别出⼀个个（单词符号）。
17.⼀张转换图只包含有限个状态，其中有⼀个被认为是（初）态;⽽且实际上⾄少要有⼀个（终）态。
1．编译程序⾸先要识别出源程序中每个(单词)，然后再分析每个(句⼦)并翻译其意义。3．通常把编译过程分为分析前端与综合后端两⼤阶段。词法、语法和语义分析是对源程序的(分析)，中间代码⽣成、代码优化与⽬标代码的⽣成则是对源程序的(综
合)。
5．对编译程序⽽⾔，输⼊数据是(源程序)，输出结果是(⽬标程序)。
四、名词解释题： 1．词法分析
词法分析的主要任务是从左向右扫描每⾏源程序的符号，按照词法规则从构成源程序的字符串中识别出⼀个个具有独⽴意义的最⼩语法单位，并转换成统⼀的内部表⽰(token)，送给语法分析程序。
13.扫描器------执⾏词法分析的程序。
五、简答题
(⼀)、描述由正规式b*(abb*)*(a| )定义的语⾔，并画出接受该语⾔的最简DFA 。答：由正规式b*(abb*)*(a| )定义的语⾔是字母表{a, b}上不含⼦串aa 的所有串的集合。最简DFA 如下：
(⼆)、描述由正规式b a(bb a) b 定义的语⾔，并画出接受该语⾔的最简DFA 。答：正规式b a(bb a) b 体现的特点是，每个a 的左边都有若⼲b ，除⾮a 是第⼀个字母。该正规式定义的语⾔是：⾄少含⼀个a ，但不含⼦串aa 的所有a 和b 的串集。最简DFA 如下：
(三). ⼀字母表Σ={a, b}，试写出Σ上所有以a 为⾸的字组成的正规集相对应的正规式。答：正规式 a ( a | b )*。
(四).令Σ={a,b}，则正规式a*b|b*a 表⽰的正规集是什么？答：.(a*b|b*a)={a,b,ab,ba,aab,bba……}
(五)、构造下列正规式相应的DFA （⽤状态转换图表⽰）（1）0（0 | 1）*1 （2）0*10*10*10*1
（3）letter （letter | digit ）*
（1）
（2）
（3）
start
1 a b b
2 start 2 a
b b 1 0
a
b
(六)．设有⾮确定的有⾃限动机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
状态转换图为
(七)．编译程序和⾼级语⾔有什么区别?
⽤汇编语⾔或⾼级语⾔编写的程序，必须先送⼊计算机，经过转换成⽤机器语⾔表⽰的⽬标程序（这个过程即编译），才能由计算机执⾏。执⾏转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语⾔源⽂件。编译程序转换过的叫⽬标程序，也就是机器语⾔。
编译程序的⼯作情况有三种：汇编型、解释型和编译型。汇编型编译程序⽤来将汇编语⾔编写的程序，按照⼀⼀对应的关系，转换成⽤机器语⾔表⽰的程序。解释型编译程序将⾼级语⾔程序的⼀个语句，先解释成为⼀组机器语⾔的指令，然后⽴即执⾏，执⾏完了，取下⼀组语句解释和执⾏，如此继续到完成⼀个程序⽌。⽤解释型编译程序，执⾏速度很慢，但可以进⾏⼈和计算机的"对话"，随时可以修改⾼级语⾔的程序。BASIC 语⾔就是解释型⾼级语⾔。编译型编译程序将级语⾔编写的程序，⼀次就会部翻译成机器语⾔表⽰的程序，⽽且过程进⾏很快，在过程中，不能进⾏⼈机对话修改。FORTRAN 语⾔就是编译型⾼级语⾔。 (⼋)．编译程序的⼯作分为那⼏个阶段?
词法分析、语法分析和语义分析是对源程序进⾏的分析(称为编译程序的前端)，⽽中间代码⽣成、代码优化和代码⽣成三个阶段合称为对源程序进⾏综合(称为编译程序的后端)，它们从源程序的中间表⽰建⽴起和源程序等价的⽬标程序。
(九)、有穷⾃动机M 接受字母表＝{0,1}上所有满⾜下述条件的串：每个1都有0直接跟在右边。构造⼀个最⼩的DFA M 及和M 等价的正规式。【】【】
(⼗)、证明正规式(ab)*a 与正规式a(ba)*等价（⽤构造他们的最⼩的DFA ⽅法）。【答案：】
1 1
0 1 1
(⼗⼀)、设={0，1}上的正规集S 由倒数第⼆个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造⼀个识别该正规集的DFA 。(8分) 答：
构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分)
1 1
1
0 0 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}
1 0 1 0 0
0 1
（⼗⼆）、处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA 的状态转换图。
（⼗三）设有字母表{a ，b}上的正规式R=(ab|a)*
。构造NFA ，确定化，化简 (2014A)
解：（1）
（
ε a b
0 1 2 3
b a a ε
ε
-
+ 0 1 2 3 4
0 1 2 3 4
（3）对（2）得到的DFA 化简，合并状态0和2 为状态2：
(⼗四)、给定⽂法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 。
解：先构造其NFA ：⽤⼦集法将NFA 确定化：
将S 、A 、Q 、BZ 、DZ 、D 、B 重新命名，分别⽤
0、1、2、3、4、5、6表⽰。因为3、4中含有z ，所以它们为终态。
令P 0＝（｛0,1,2,5,6｝,｛3,4｝）⽤b 进
⾏分割：
P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再⽤b 进⾏分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再⽤a 、b 进⾏分割，仍不变。再令｛０｝为A ，｛1，2｝为B ，｛3，4｝为C ，｛5，6｝为D 。最⼩化为右上图。
b +

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