第二章 词法分析

第二章 词法分析 典型例题 : 单项选择题 1.1.1 ．词法分析所依据的是 ____ 。 a. 语义 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf b. 构词规则 c. 语法规则 d. 等价变换规则 1.1.2 ．词法分析器的输出结果是 ____ 。 a. 单词的种别编码 b. 单词在符号 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中的位置 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)={a 2n+1 b 2m a 2p+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 最小化。 图 2.58 DFA 1.5.27 （中科院计算所 1997 年研究生试题） 为正规式 (a|b) *a(a|b) 构造一个确定的有限自动机。 1.5.28 （南开大学 1998 年研究生试题） 写出正规式 (alb) *(aa|bb)(a|b)* 的 DFA 。 1.5.29 （复旦大学 1999 年研究生试题） 将图 2.59 所示的非确定有限自动机 (NFA) 变换成等价的确定有限自动机 (DFA) 。   图 2.59 NFA 其中， X 为初态， Y 为终态。 1.5.30 （上海交大 1997 年研究生试题） 请构造与正规式 R=(a * |b * )b(ba) * 等价且状态最少的 DFA 。 1.5.31 （国防科大 1999 年研究生试题） 构造一个确定的有限自动机 DFA, 它接受∑＝ {0,1} 上的所有不带前导 0 的二进制区数。 1.5.32 （国防科大 2000 年研究生试题） 已知 DFA M 如图 2.60 所示。 图 2.60 DFA M 请给出 M 所识别的字的全体 L(M) 。 1.5.33 （华中理工 2001 年研究生试题） 构造一个确定的有穷自动机 DFA M, 它识别∑ ={a,b} 上所有满足如下条件的字符串：字 符串由 a, b 组成，且其中 b 的个数为 3k (k ≥ 0) 。 1.5.34 （华中理工 2001 年研究生试题） 正规式 (ab ) * a 与正规式 a(ba) * 是否等价？请说明理由。 1.5.35 DFA 与 NFA 有何区别 ？