北方工业大学编译原理习题集Word格式文档下载.docx
《北方工业大学编译原理习题集Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《北方工业大学编译原理习题集Word格式文档下载.docx（51页珍藏版）》请在冰点文库上搜索。
ND8=>
N68=>
D68=>
7、写一个文法，使其语言是奇数集，且每个奇数不以0开头。
本题要构造一个文法，由它产生的句子是奇数，且不以0开头。
也就是说它的每个句子都以1、3、5、7、9中某数结尾。
如果数字只有一位，则满足要求；
如果有多位，则要求第一位不能是0；
而中间有多少位，每位是什么数字则没有要求。
因此我们可以把这个文法分3部分完成，分别用3个非终结符来产生句子的第一位、中间部分和最后一位。
引入几个非终结符，其中，一个
第三章词法分析
1、编写一个对于Pascal源程序的预处理程序。
该程序的作用是，每次被调用时都将下一个完整的语句送进扫描缓冲区，去掉注释行，同时要对源程序列表打印。
2、请给出以下C++程序段中的单词符号及其属性值。
intCInt：
：
nMulDiv（intn1，intn2）
{
if（n3==0）return0；
elsereturn（n1*n2）/n3；
}
3、用类似C或Pascal的语言编写过程GetChar，GetBC和Concat。
4、用某种高级语言编写并调试一个完整的词法分析器。
5、证明3.3.1中关于正规式的交换律、结合律等五个关系。
6、令A、B和C是任意正规式，证明以下关系成立：
A∣A=A
（A*）*=A*
A*=ε∣AA*
（AB）*A=A（BA）*
（A∣B）*=（A*B*）*=（A*∣B*）*
A=b∣aA当且仅当A=a*b
证明：
（1）、A∣A=A
L（A∣A）=L（A）∪L（A）=L（A），所以有A∣A=A。
（2）、（A*）*=A*
（3）、A*=ε∣AA*
通过证明两个正规式所表示的语言相同来证明两个正规式相等。
L（ε∣AA*）=L（ε）∪L（A）L（A*）=L（ε）∪L（A）（L（A））*
=L（ε）∪L（A）（（L（A））0∪（L（A））1∪（L（A））2∪（L（A））3∪…）
=L（ε）∪（L（A））1∪（L（A））2∪（L（A））3∪（L（A））4∪…
=（L（A））*=L（A*）
即：
L（ε∣AA*）=L（A*），所以有：
A*=ε∣AA*
（4）、（AB）*A=A（BA）*
利用正规式的分配率和结合律直接推导。
（AB）*A=（（AB）0∣（AB）1∣（AB）2∣（AB）3∣…）A
=εA∣（AB）1A∣（AB）2A∣（AB）3A∣…
=Aε∣A（BA）1∣A（BA）2∣A（BA）3∣…
=A（ε∣（BA）1∣（BA）2∣（BA）3∣…）
=A（BA）*
（AB）*A=A（BA）*
（5）、（A∣B）*=（A*B*）*=（A*∣B*）*
证明:
先证（A∣B）*=（A*B*）*
因为L（A）
L（A）*L（B）*,L（B）
L（A）*L（B）*
故:
L（A）∪L（B）
于是由本题第二小题结论可知（L（A）∪L（B））*
（L（A）*L（B）*）*①
又L（A）
L（A）∪L（B）,L（B）
L（A）∪L（B）
L（A）*
（L（A）∪L（B））*
L（B）*
因此有:
L（A）*L（B）*
（L（A）∪L（B））*（L（A）∪L（B））*=（（L（A）∪L（B））*）2
故（L（A）*L（B）*）*
（（L（A）∪L（B））*）*
由本题第二小题得:
（（L（A）∪L（B））*）*=（L（A）∪L（B））*
故得:
（L（A）*L（B）*）*
（L（A）∪L（B））*②
则由①②得:
（L（A）∪L（B））*=（L（A）*L（B）*）*
由于L（（A*B*））*=（L（A*B*））*=（L（A*）L（B*））*=（L（A）*L（B）*）*
即有（L（A）∪L（B））*=L（（A*B*））*③
而（A|B）*对应的语言为（L（A）∪L（B））*,且（A*B*）*对应的语言为L（（A*B*））*
则根据③得（A|B）*=（A*B*）*
再证:
（A*|B*）*=（A*B*）*
因为:
A,B是任意正规式,由以上结论得:
（A*|B*）*=（（A*）*（B*）*）*
又由本题第二小题目的结论可得：
（A*）*=A*，（B*）*=B*
因此，（A*|B*）*=（A*B*）*
综合上述两种结论，最后得：
（A∣B）*=（A*B*）*=（A*∣B*）*
（6）、A=b∣aA当且仅当A=a*b
7、构造下列正规式相应的DFA
1（0∣1）*101
1（1010*∣1（010）*1）*0
0*10*10*10*
（00∣11）*（（01∣10）（00∣11）*（01∣10）（00∣11）*）*
（1）、1（0∣1）*101
第一步：
根据正规式构造NFA，先引入初始状态X和终止状态Y：
再对该转换图进行分解，得到分解后的NFA如下图：
第二步：
对NFA进行确定化，获得状态转换矩阵：
状态
1
{X}
Ø
{1，2，3}
{2，3}
{2，3，4}
{2，3，5}
{2，3，4，Y}
根据转换矩阵获得相应的DFA：
第三步：
化简该DFA，获得最简的DFA即为所求。
首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5}已经不可划分，只需考虑集合{0，1，2，3，4}。
{0，1，2，3，4}0={2，4，-}，{0，1，2，3，4}1={1，3，5}
因为{1，3，5}和{2，4，-}不在一个集合里面，所以需要对集合{0，1，2，3，4}进行进一步的划分，检查其中的所有状态。
状态0不能接受字符0，需要把状态0划分出来；
另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：
{0}，{1，2，3}，{4}，{5}。
检查集合{1，2，3}，{1，2，3}0={2，4}，不属于同一个集合，因此要对集合{1，2，3}进行进一步划分，划分结果为5个集合：
{0}，{1，2}，{3}，{4}，{5}。
检查集合{1，2}，{1，2}0={2}，{1，2}1=3，不需要进行进一步划分。
所以最终划分结果为5个集合：
所以，最终所求DFA如下图示：
（2）、1（1010*∣1（010）*1）*0
（3）、0*10*10*10*
（4）、（00∣11）*（（01∣10）（00∣11）*（01∣10）（00∣11）*）*
8、给出下面正规表达式：
（1）以01结尾的二进制数串；
（2）能被5整除的十进制整数；
（3）包含奇数个1或奇数个0的二进制数串；
（4）英文字母组成的所有字符串，要求符号串中的字母依照字典序排列；
（5）没有重复出现的数字的数字符号串的全体；
（6）最多有一个重复出现的数字的数字符号串的全体；
（7）不包含子串abb的由a和b组成的符号串的全体。
解：
分析题意，要求的是二进制数串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两步完成：
一部分实现由0和1构成的任意串，一部分即01，然后将它们连结在一起就可以了，所以所求为（1︱0）*01。
分析题意，本题要求的是十进制整数，也就是由0至9这10个数字组成的字符串，并且不能以0开头（整数“0”除外），要求能被5整除，则该串必须以0或者5结尾。
根据分析，可以把本题分成两种情况考虑：
一种情况时该整数只有一位，则该整数有0和5两种可能；
另一种情况是该整数有多位，则该整数可以分成三部分考虑：
一是第一位必须不为0；
二是最后一位必须为0或5；
三是中间部分可有可无，并且可以由0到9之间任意数字构成，所以所求为（1︱2︱3︱4︱5︱6︱7︱8︱9）（0︱1︱2︱3︱4︱5︱6︱7︱8︱9）*（0︱5）（0︱5）。
本题求二进制串，并且要求包含奇数个0或奇数个1，由于0和1都可以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另一种情况也可以类似求得。
考虑包含奇数个0的字符串：
由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第一段为二进制串的开始到第一个0为止，这一段包含一个0，并且0的前面有0个或多个1。
对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1。
如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串（这些全1串在前面划分的串之间或最后），则该二进制串就有奇数个0，所以该二进制串可以这样描述：
以第一段（1*0）开始，后面由全1串（1*）以及包含两个0的串（01*0）组成，所以包含奇数个0的正规表达式为1*0（1︱01*0）*。
所以本题所求为1*0（1︱01*0）*︱0*1（0︱10*1）*。
9、对下面情况给出DFA及正规表达式：
（1）{0，1}上的含有子串010的所有串；
（2）{0，1}上不含子串010的所有串。
（1）、
（2）、直接写出满足条件的正规表达式。
考虑满足条件的字符串中的1：
在串的开始部分可以有0个或多个1，串的尾部也可以有0个或多个1，但串的中间只要出现1则至少在两个以上，所以满足条件的正规表达式为1*（0∣111*）*1*。
所求的DFA如下图所示：
10、一个人带着狼、山羊和白菜在一条河的左岸。
有一条船，大小正好能装下这个人和其他三件东西中的一件。
人和他的随行物都要过到河的右岸。
人每次只能将一件东西摆渡过河。
但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。
类似地，若羊和白菜留下来无人照看，羊将会吃掉白菜。
请问是否有可能渡过河去，使得羊和白菜都不被吃掉？
如果可能，请用有限自动机写出渡河的方法。
11、
12、将图3.18的（a）和（b）分别确定化和最小化。
（1）、图（a）中为一个NFA，所以需要先对它进行确定化，得到DFA，然后再对DFA进行最小化。
首先进行确定化，如下两个表所示：
a
b
{0}
{0，1}
{1}
2
根据状态转换矩阵得到如下图所示的DFA：
化简后的DFA为：
（2）、题中所给即为一个DFA，不需要确定化，只对它进行最小化即可。
首先将状态划分为两个集合{{0，1}，{2，3，4，5}}。
有{0，1}a={1}，{0，1}b={2，4}和{2，3，4，5}a={1，3，0，5}，{2，3，4，5}b={2，3，4，5}，所以可以进一步划分为{{0，1}，{2，4}，{3，5}}，然后有{0，1}a={1}，{0，1}b={2，4}，{2，4}a={1，0}，{2，4}b={3，5}，{3，5}a={3，5}，{3，5}b={2，4}。
因此，最后划分结果是{{0，1}，{2，4}，{3，5}}。
最小化后的DFA如下图所示：
13、
（1）给出描述C浮点数的DFA；
14、构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串：
每个1都有0直接跟在右边。
对这类题型的固定解法分4步进行：
首先根据语言写出正规表达式；
然后根据正规表达式构造相应的NFA；
然后，对NFA进行确定化得到DFA；
最后对DFA化简得到最简DFA。
写出正规表达式。
根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是（0︱10）*。
构造NFA。
首先得出下图：
然后对上图进行分解后得到如下图所示的NFA。
确定化，得到DFA。
确定化结果如表14.1所列；
给状态编号，得到表14.2所示的状态转换矩阵：
{X，1，Y}
{1，Y}
{2}
表14.1状态转换矩阵
表14.2新的状态转换矩阵
根据状态转换矩阵得到DFA如下图所示：
第四步：
对该DFA进行最小化。
其分析过程如下：
{0，1}，{2}
{0，1}0={1}，{0，1}1={2}
最小化后的DFA如图所示，该DFA即为所求。
15、给定右线性文法G：
S→0S∣1S∣1A∣0B
A→1C∣1
B→0C∣0
C→0C∣1C∣0∣1
求出一个与G等价的左线性文法。
根据右线性文法求左线性文法没有直接的方法，但可以通过状态转换图去转换。
可以先求出文法G的状态转换图，再根据状态转换图写出相应的左线性文法。
文法G对应的状态转换图如下所示：
对状态转换图进行确定化，得到状态转换矩阵：
{S}
{S，B}
{S，A}
{S，B，C，Z}
{S，A，C，Z}
给状态编号，得到新的状态转换矩阵：
3
4
根据状态转换矩阵获得DFA如下：
还可以对上图的DFA进行化简，状态3和4可以合并，化简后的DFA如下图所示：
不难看出，该DFA接受的语言是{0，1}上包含00或11的字符串。
根据化简后的DFA，我们可以写出相应的左线性文法G’：
T→A0∣B1∣T0∣T1
A→B0∣0
B→A1∣1
16、*非形式的说明
17、*下面的字集是否为正规集？
或写出其正规式，或给出否证。
（1）L1={anbn∣n≥0}；
（2）L2={x}；
（3）L3={}。
18、假定L和M都是正规集：
（1）证明L∪M、L∩M和～M（补集）也是正规的；
（2）L′是L中每个字的逆转，证明L也是正规的。
19、写出描述ANSIC的单词符号的LEX程序。
20、假定有正规定义式
A0→a∣b
A1→A0A0
……
An→An-1An-1
考虑词形An
（1）把An中所有简名都换掉，最终所得的正规式的长度是多少？
（2）字集An的元素是什么？
把它们非形式的表示成n的函数；
（3）证明识别An的DFA只需用2n+1个状态就足够了。
21、把LEX的“动作”成分加以充实使得可用它来编写语法制导编辑器。
第四章语法分析——自上而下分析
1、考虑下面的文法
G1：
S→a∣∧∣（T）
T→T，S∣S
（1）消去G1的左递归。
然后对每个非终结符，写出不带回溯的递归子程序。
（2）经改写后的文法是否是LL
（1）的？
给出它的预测分析表。
（1）按照T、S的顺序消除左递归，得到文法：
G’（S）
S→a∣∧∣（T）
T→ST’
T’→，ST’∣ε
对于非终结符S,T,T’的递归子程序如下：
ProcedureS;
Begin
Ifsym=‘a’orsym=‘^’
Thenadvance
Elseifsym=‘（‘
Thenbegin
Advance;
T;
Ifsym=’）’
Thenadvance
Elseerror
End
Elseerror
Ends;
ProcedureT;
S;
T’;
ProcedureT’
Begin
Ifsym=‘,’
Thenbegin
Advance;
S;
T’
Ends
ends;
（2）计算每个非终结符的FIRST集合和FOLLOW集合：
FIRST（S）={a，∧，（}
FIRST（T）={a，∧，（}
FIRST（T’）={，，ε}
FOLLOW（S）={），’，’，#}
FOLLOW（T）={）}
FOLLOW（T’）={）}
从而可见改造后的文法符合LL
（1）文法的充分必要条件，所以是LL
（1）的。
该文法的预测分析表
^
（
）
#
S
S->
（T）
T
T->
ST’
T’
T’->
ξ
ST’
2、对下面的文法G：
E→TE’
E’→+E∣ε
T→FT’
T’→T∣ε
F→PF’
F’→*F’∣ε
P→（E）∣a∣b∣∧
（1）计算这个文法的每个非终结符的FIRST和FOLLOW。
（2）证明这个文法是LL
（1）的。
（3）构造它的预测分析表。
（4）构造它的递归下降分析程序。
分析：
对于这类题目，我们首先应当检查文法是否符合LL
（1）文法的条件，根据需要，先通过消除左递归、提取右公因子的方法，把文法改造成符合LL
（1）文法的条件，在此基础上，我们才能构造出不带回溯的递归下降识别程序。
注意，本题在构造子程序时，对于每个产生式候选，在调用第一个非终结符对应的子程序之前，检查了首符集。
（1）计算每个非终结符的FIRST集合和FOLLOW集合如下：
FIRST（E）={（，a，b，∧}
FIRST（E’）={+，ε}
FIRST（T）={（，a，b，∧}
FIRST（T’）={（，a，b，∧，ε}
FIRST（F）={（，a，b，∧}
FIRST（F’）={*，ε}
FIRST（P）={（，a，b，∧}
FOLLOW（E）={#，）}
FOLLOW（E’）={#，）}
FOLLOW（T）={+，），#}
FOLLOW（T’）={+，），#}
FOLLOW（F）={（，a，b，∧，+，），#}
FOLLOW（F’）={（，a，b，∧，+，），#}
FOLLOW（P）={*，（，a，b，∧，+，），#}
（2）本文法是LL
（1）文法。
通过观察可知文法中不含有左递归，满足LL
（1）文法定义的第一个条件。
考虑下列产生式：
因为：
FIRST（+E）∩FIRST（ε）={+}∩{ε}=Ø
FIRST（E’）∩FOLLOW（E’）={+}∩{#，）}=Ø
FIRST（T）∩FIRST（ε）={（，a，b，∧}∩{ε}=Ø
FIRST（T’）∩FOLLOW（T’）={（，a，b，∧}∩{+，），#}=Ø
FIRST（*F’）∩FIRST（ε）={*}∩{ε}=Ø
FIRST（F’）∩FOLLOW（F’）={*}∩{（，a，b，∧，+，），#}=Ø
FIRST（（E））∩FIRST（a）∩FIRST（b）∩FIRST（∧）=Ø
所以该文法是LL
（1）文法。
（3）构造其预测分析表：
预测分析表
+
*
（
）
a
b
^
#
E
E→TE’
E’
E’→+E
E’→ξ
E’->
T→FT’
T’→FT’
T→FT’
T’→ξ
T’→T
T’→T
T’→T
F
F→PF’
F→PF’
P→PF’
F’
F’→ξ
F’→*F’
F’→ξ
P
P→（E）
P→a
P→b
P→^
（4）构造其递归下降分析程序：
ProcedureE;
T;
E’
End;
ProcedureE’;
Ifsym=‘+’
Thenbegin
Acvance
升级会员 