发布时间 : 星期五 文章《编译原理》期中及期末习题更新完毕开始阅读22792f0df12d2af90242e68e
z：=x+z； end； begin
a：=5； b：=2； p(a*b,a,a)； print(a) end．
若参数传递的方法分别为（1)传值、(2)传地址、(3)传名，试问程序执行所输出的结 果分别是什么？
1.5.14 有一段程序为： PROGRAM sample; x：integer；
PROCEDURE sun(m：integer)； BEGIN｛sun｝ M：=11； x：=m+ END；｛sun｝ BEGIN
X：=100； sun（x）； write（x） END；
请用（1）传地址；（2）传值；（3）传结果；(4)传名的参数传递方式，给出程序的运行 结果。
1.5.15有一程序如下：
PROGRAM ex； a：integer；
PROCEDURE PP(x：integer)； BEGIN｛PP｝ a：=5；x：=a+1 END；｛PP｝ BEGIN a：=2； PP（a）； write（a） END ． 用（1)传地址；(2)传值；（3)传结果；(4)传名等4种参数传递方式，；试写出程序的 运行结果。
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。