《编译原理》期中及期末习题(2)

5

※<习题二>

第二章 词法分析

典型例题: 单项选择题

1.1.1．词法分析所依据的是____。 a.语义规则 b.构词规则 c.语法规则 d.等价变换规则

1.1.2．词法分析器的输出结果是____。

a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值 1.1.3．正规式MI和M2等价是指____。

a. MI和M2的状态数相等 b.Ml和M2的有向弧条数相等。

C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等 1.1.4．状态转换图（见图2.5），接收的字集为：

图2.5

a.以0开头的二进制数组成的集合 b.以0结尾的二进制数组成的集合 c.含奇数个0的二进制数组成的集合 d.含偶数个0的二进制数组成的集合

1.1.5．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此___。 a.词法分析器应作为独立的一遍 b.词法分析器作为子程序较好

c.词法分析器分解为多个过程，由语法分析器选择使用 d.词法分析器并不作为一个独立的阶段 1.1.6．词法分析器的输入是—。 a.单词符号串 b.源程序 c.语法单位 d.目标程序 1.1.7.如果L(M)=L(M'），则M与M'__。（陕西省1999年自考题） a. 等价 b．M与M'都是二义的 c. M与M'都是无二义的 d. 他们的状态数相等

1.1.8．图2.56所示的状态转换图接受的字集所对应的正规式为＿。（陕西省1997年自考题）

a. a*b*(aa|bb)a*b* b. (a|b)*(aa|bb)(a|b)

c. (a*|b*)(aa|bb)(a*|b*) d. (a*|b*)aa(a*|b*)|(a*|b*)bb(a*|b*)

图2.56 状态转换图

多项选择题：

1.2.1在词法分析中，能识别出＿。 （陕西省1998年自考题） a.基本字 b.四元式 c.运算符 d.逆波兰式 e..常数

1.2.2令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为＿。 a．b(ab)* b.b(ab) c.(ba)* b d.(ba)+b e. b(alb)*

1.2.3设∑={0,1}，则∑上字的全体可用正规式_____表示。 a.(1|0)* b.(1*|0*)* c.(1|0)+ d.(1*0*)* e.(10)*

填空题：

1.3.1 确定有限自动机DFA是_______的一个特例。

1.3.2 若二个正规式所表示的______相同，则认为二者是等价的。（陕西省1997年自考题） 1.3.3 一个字集是正规的，当且仅当它可由______所______（陕西省1997年自考题）

判断题：

1.4.1．一个有限状态自动机中，有且仅有一个唯一的终态。 （ ） 1.4.2．设r和s分别是正规式，则有L(r|s)=L(r)|L(s) （ ）

1.4.3．自动机M和M'的状态数不同，则二者必不等价。 （ ） 1.4.4．确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 1.4.5．对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 （ ） 1.4.6 对任意一个右线性文法G,都存在一个DFA M,满足L(G}=L(M) 。 （ ） 1.4.7 对任何正则表达式e,都存在一个NFA M,满足L(G)=L(e) 。 （ ） 1.4.8 对任何正则表达式e,都存在一个DFA M,满足L(G)=L(e)。 （ ） 1.4.9 两个正规集相等的必要条件是他们对应的正规式等价。（） 1.4.10 词法分析作为单独的一遍来处理较好。（）

1.4.11 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）

综合题

1.5.1 什么是扫描器？扫描器的功能是什么？

1.5.2 给出字母表∑上的正规式及其所描述的正规集的递归定义。

1.5.3 正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言能力上是否相互等价？

1.5.4 已知Pascal语言的实数表示规则如下： （1)实数十进制表示

(a)实型数的小数点前后必须出现数字： (b）必须出现小数点。

（2）实数科学表示（指数形式） (a)字母e表示以十为底的指数；

(b）字母e前必须出现实数或者整数；

（c）字母e后必须出现整数，这个整数表示实型数的指数部分。 试画出该实数对应的状态转换图。

1.5.5 设M= <{x,y}，{a,b) ,f,x, {y})为一非确定的有限自动机，其中f定义如下：

f(x,a)=｛x,y｝ f｛a,b｝=｛Y)

f(Y,a)=φ f｛y,b｝＝｛x,y｝ 试构造相应的确定有限自动机M`。

＋

1.5.6 (1）对给定正规式b*(d|ad) (b|ab)，构造其NFA M； （陕西省1997年自考题） （2) 对给定正规式(a|b)*a (a|b)，构造其DFA M。 （中科院计算所1997年研究生试题）

1.5.7 构造一个DFA,它接收∑=｛a,b｝上的所有满足下述条件的字符串，即该字符串中的每个a都有至少一个b直接跟在其右边。

1.5.8 有穷状态自动机M接受字母表∑＝{0，1｝上所有满足下述条件的串：串中至少包含两个连

续的0或两个连续的1。

（1)请给出与M等价的正规（则）式。 （2）将M最小化。

（3）构造与M等价的正规文法。

1.5.9 构造正规表达式((a|b)*|bb)*的ＤＦＡ（要求写出步骤）。

1.5.10 设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1} （1)给出描述该语言的正规表达式。

(2)构造识别该语言的确定的有穷自动机（可直接用状态图形式给出）。

1.5.11 请写出在∑＝(a,b)上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。

＋

1.5.12 有语言L={w|w∈(0,1），并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机（DFA）。

1.5.13 已知正规式(1)((a|b)*|aa)*b和正规式(2)(a|b)*b。 (1)试用有限自动机的等价性证明正规式(1)和(2)是等价的。 (2）给出相应的正规文法。

1.5.14 某操作系统下合法的文件名为device:name.extension,其中第一部分（device:）和第三部分（.extension)可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

1.5.15 Pascal语言无符号数的正规定义如下： Num→digit+(.digit+)?(E(+|-)?digit+)?

其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

1.5.16 在C语言中无符号整数可用十进制（非0打头）、八进制（0打头）和十六进(0X打头）表示，试写出其相应的文法和识别无符号数的DFA(假定位数不限)。

1.5.17 下列程序段若以B表示循环体，A表示初始化，I表示增量，T表示测试。 I:=1；

while I<=n do begin

sun:=sun+a[I];

I:=I+l End

请用正规表达式表示这个程序段可能的执行序列。

1.5.18 在操作系统的进程管理中，进程的状态转换如图2.50所示。假设现有两个进程Pi和CPU每次只能运行一个进程。当P1、P2都处于就绪状态时为初态，当P1、P2都处于睡眠状态时为终态。请用一个有限自动机来描述这个进程管理系统。

图2.50 进程状态转换图

1.5.19 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中

投放≥3分的硬币，便可得到一块糖（注意：只给一块并且不找钱）。 (1)写出售货机售糖的正规表达式。 (2)构造识别上述正规式的最简DFA。

1.5.20 证明：一不含无用状态的有限自动机M的接收集L(M)是无限集，当且仅当M相应的状态转换图中含有回路。

1.5.21 假定A和B都是正规集，请用正规集与有限自动机的等价性说明A∪B也是正规的。

1.5.22 下面的正规式等价吗？为什么？ (1)(a|b)* (2) (a*|b*)* (3)((ε|a)b*)*

1.5.23 （电子科大1996年研究生试题） 构造识别下列单词符号的状态转换图：

begin end标识符正整数＋－***，．∷＝

1.5.24 （清华大学1998年研究生试题） 请将图2.57所示的有穷自动机M1最小化。

图2.57 有穷自动机M1

1.5.25 （清华大学1998年研究生试题） 将有穷自动机M2确定化

M2=({U,V,W,X}，10,1｝,f,{U}，{W}） 其中：f(U,0）＝φ f(U,1）＝｛V,X} f(V,0)={V} f(V,l）＝tvlwl f(W,0)={X｝ f(W,1)＝{W} f(X,0)={X} f(X,1）＝{X}

1.5.26 （清华大学1998年研究生试题） 将图2.58所示的DFA最小化。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《编译原理》期中及期末习题(2)在线全文阅读。