第二章词法分析
2.1 完成下列选择题：
(1) 词法分析器的输出结果是 c 。
a. 单词的种别编码 b. 单词在符号表中的位置。
c. 单词的种别编码和自身值 d. 单词自身值。
(2) 正规式m1和m2等价是指 c 。
a. m1和m2的状态数相等
b. m1和m2的有向边条数相等。
c. m1和m2所识别的语言集相等
d. m1和m2状态数和有向边条数相等
3) dfa m(见图2-1)接受的字集为 d 。
a. 以0开头的二进制数组成的集合
b. 以0结尾的二进制数组成的集合
c. 含奇数个0的二进制数组成的集合。
d. 含偶数个0的二进制数组成的集合
图2-1 习题2.1的dfa m
2.2 什么是扫描器？扫描器的功能是什么？
【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。
2.3 设m=(,f, x, )为一非确定的有限自动机，其中f定义如下：
f(x,a)==
f(y,af=
试构造相应的确定有限自动机m′。
【解答】 对照自动机的定义m=(s,σ,f,so,z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此m是一非确定有限自动机。
先画出nfa m相应的状态图，如图2-2所示。
图2-2 习题2.3的nfa m
用子集法构造状态转换矩阵，如表2-1所示。
表2-1 状态转换矩阵
将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到。
m′=(f,0,)，其状态转换图如图2-3所示。
表2-2 状态转换矩阵。
将图2-3所示的dfa m′最小化。首先，将m′的状态分成终态组与非终态组。其次，考察，由于a=b= ，所以不再将其划分了，也即整个划分只有两组：
和。令状态1代表，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的dfa m′。
图2-3 习题2.3的dfa m′
图2-4 图2-3化简后的dfa m′
2.4 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。
【解答】 正规式(ab)*a对应的nfa如图2-5所示，正规式a(ba)*对应的nfa如图2-6所示。
图2-5 正规式(ab)*a对应的nfa
图2-6 正规式a(ba)*对应的dfa
这两个正规式最终都可得到最简dfa，如图2-7所示。因此，这两个正规式等价。
图2-7 最简nfa
2.5 设有l(g)=。
(1) 给出描述该语言的正规表达式；
(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。
【解答】 该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的nfa如图2-8所示。
图2-8 习题2-5的nfa
用子集法将图2-8确定化，如图2-9所示。
由图2-9重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)
按顺序重新命名为后得到最简的dfa，如图2-10所示。
图2-9 习题2.5的状态转换矩阵
图2-10 习题2.5的最简dfa
2.6 有语言l=，试构造接受该语言的确定有限状态自动机(dfa)。
【解答】 对于语言l，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出l的正规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的nfa，如图2-11所示。
图2-11 习题2.6的nfa
用子集法将图2-11的nfa确定化，如图2-12所示。
图2-12 习题2.6的状态转换矩阵
由图2-12可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为。
按顺序重新命名为，则得到最简dfa，如图2-13所示。
图2-13 习题2.6的最简dfa
2.7 已知正规式((a|b)*|aa)*b和正规式(a|b)*b。
(1) 试用有限自动机的等价性证明这两个正规式是等价的；
(2) 给出相应的正规文法。
【解答】 (1) 正规式((a|b)*|aa)*b对应的nfa如图2-14所示。
图2-14 正规式((a|b)*|aa)*b对应的nfa
用子集法将图2-14所示的nfa确定化为dfa，如图2-15所示。
图2-15 图2-14确定化后的状态转换矩阵
由于对非终态的状态来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。
由此得到最简dfa，如图2-16所示。
正规式(a|b)*b对应的nfa如图2-17所示。
表2-3 合并后的状态转换矩阵
图2-16 习题2.7的最简dfa
图2-17 正规式(a|b)*b对应的nfa
用子集法将图2-17所示的nfa确定化为如图2-18所示的状态转换矩阵。
图2-18 图2-17确定化后的状态转换矩阵
比较图2-18与图2-15，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的dfa如图2-16所示。因此，两个自动机完全一样，即两个正规文法等价。
(2) 对图2-16，令a对应状态1，b对应状态2，则相应的正规文法g[a]为。
g[a]：a→aa|bb|b
b→aa|bb|b
g[a]可进一步化简为g[s]：s→as|bs|b(非终结符b对应的产生式与a对应的产生式相同，故两非终结符等价，即可合并为一个产生式)。
2.8 下列程序段以b表示循环体，a表示初始化，i表示增量，t表示测试：
i=1;while (i<=n)
sun=sun+a[i];
i=i+1;}
请用正规表达式表示这个程序段可能的执行序列。
解答】 用正规表达式表示程序段可能的执行序列为a(tbi)*。
2.9 将图2-19所示的非确定有限自动机(nfa)变换成等价的确定有限自动机(dfa)。
图2-19 习题2.9的nfa
其中，x为初态，y为终态。
【解答】 用子集法将nfa确定化，如图2-20所示。
图2-2习题2.9的状态转换矩阵
图2-20所对应的dfa如图2-21所示。
图2-21 习题2.9的dfa
图2-22 习题2.9的最简dfa
对图2-21的dfa进行最小化。首先将状态分为非终态集和终态集两部分：和。
由终态集可知，对于状态，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分。
对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为。
按顺序重新命名为，得到最简dfa如图2-22所示。
2.10 有一台自动售货机，接收1分和2分硬币，**3分钱一块的硬糖。顾客每次向机器中投放≥3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。
(1) 写**货机售糖的正规表达式；
(2) 构造识别上述正规式的最简dfa。
【解答】 (1) 设a=1，b=2，则售货机售糖的正规表达式为a (b|a(a|b))|b(a|b)。
(2) 画出与正规表达式a(b|a(a|b))|b(a|b)对应的nfa，如图2-23所示。
图2-23 习题2.10的nfa
用子集法将图2-21的nfa确定化，如图2-24所示。
图2-24 习题2.10的状态转换矩阵
由图2-24可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态、、、按顺序重新命名为，则得到最简dfa，如图2-25所示。
图2-25 习题2.10的最简dfa
编译原理第二章作业
1.pl 0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。pl 0 语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。数组 code 存放的只读目标程序，它在运行时不改变。运行时的数据区 s 是由解释程序定义的一维整型数组，解释执行时对数据空间 ...
编译原理第二章习题
第2章习题。1 文法g s 为 s ac ab a ab b bc 写出l g s 的全部元素。答案 s ac abc 或s ab abc 所以l g s 2 令文法g为 n d nd d 0 1 2 3 4 5 6 7 8 9 1 g的语言l g 是什么？2 给出句子0568的最左推导和最右推导。...
编译原理作业集 第二章
1.程序语言的定义 2.高级程序语言一般结构和主要共同特征 3.正确理解上下文无关文法基本概念，包括 文法的定义 推导 句型 句子 语言 语法树 二义性等 4.chomsky文法分类 掌握和理解程序语言的定义 高级语言的一般特征及程序语言的语法描述。1.语法，词法规则与语法规则 2.语义和语义规则 ...