编译原理例题与习题解答.

资源描述

《编译原理例题与习题解答.》由会员分享，可在线阅读，更多相关《编译原理例题与习题解答.（82页珍藏版）》请在金锄头文库上搜索。

1、例题与习题解答第二章 1 编译原理回顾 n程序语言的定义一个程序语言是一个记号系统,它主要由以下方面定义： n语法 n语义每个句子构成的规律研究语言每个句子的含义语法语义 2 编译原理语法=词法规则+语法规则 n词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：正规式和有限自动机理论 n语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、子程序、过程、函数、程序等; 描述工具：上下文无关文法回顾 3 编译原理标识符与名字 n标识符：以字母开头的，由字母数字组成的字符串。

2、 n标识符与名字两者有本质区别：标识符是语法概念名字有确切的意义和属性回顾 4 编译原理 n上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。回顾 5 编译原理 n假定G是一个文法，S是它的开始符号。如果S ，则称是一个句型。仅含终结符号的句型是一个句子。 n文法G所产生的句子的全体是一个语言，将它记为L(G) L(G) =

3、 | S 中间部分可出现任意多位数字09, 每一位用非终结符D表示; 最低位只出现1,3,5,7,9, 用A表示。由于中间部分可任意位,故需另引入一非终结符M,它包括最高位和中间部分。 13 编译原理 M B 最高位中间位 DDDA 最低位 14 编译原理解: 奇数集文法GN为: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B 15 编译原理 n8. 令文法为 E T|E+T|E-T T F|T*F|T/F F (E)|i (1) 给出 i+i*i、i*(

4、i+i)的最左推导和最右推导。解：此处仅以 i*(i+i) 为例给出答案最左推导 E T T*F F*F i*F i*(E) i*(E+T) i*(T+T) i*(F+T) i*(i+T) i*(i+F ) i*(i+i) 最右推导 E T T*F T*(E) T*(E+T) T*(E+F) T*(E+i) T*(T+i) T*(F+i) T*(i+i) F*(i+i) i*(i+i) 编译原理 n8. 令文法为 E T|E+T|E-T T F|T*F|T/F F (E)|i E E - T E - T T F F i F i i i-i-i 的语法树 (2) 给出 i+i+i、i+i*

5、i和i-i-i的语法树。 E E + T E + T T F F i F i i i+i+i 的语法树i+i*i 的语法树 E E + T T T F F i F i i * n注意：树枝和符号均不可随意增减！编译原理 9、证明文法: S iSeS | iS | i 是二义的。二义性的含义:如果文法存在某个句子对应两棵以上不同的语法树，或者两种以上不同的最左/右推导，则称这个文法是二义的。首先：找到此文法对应的一个句子 iiiei 其次：构造与之对应的两棵语法树 S i S e S i S i i S i S i S e S i i 结论：因为该文法存在句子iiiei对应两棵不同的

7、A 21 例题与习题解答第三章 22 编译原理 1. 假定NFA M=，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y， X,YS，从X到S0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。非确定有限自动机状态图的改造 23 编译原理代之为ik AB j ij AB 代之为ij A|B ij B A 代之为 ij A* ik j A 按下面的三条规则对V进行分裂: n逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然 L(M)=L(M)24 编译原理

8、确定有限自动机的确定化采用子集法设I是M的状态集的一个子集，定义I的-闭包 -closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I) 即： -closure(I)=Is|从某个sI出发经过任意条弧能到达s 25 编译原理 n设a是中的一个字符，定义 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a 弧而到达的状态集合。 n把确定化的过程: 不失一般性，设字母表只包含两个a和b ，我们构造一张表: 26 编译原理 n对一个DFA M最少化的基本思想: 把M的状态集划

9、分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。 DFA M最少化 27 编译原理 n具体做法: 对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分。假定到某个时候，已含m个子集，记为=I(1)，I(2)，I(m)，检查中的每个子集看是否能进一步划分: n对某个I(i)，令I(i)=s1,s2, ,sk ，若存在一个输入字符a使得Ia(i) 不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。 28 编译原理 n例如，假定状态s1和s2经a弧分

10、别到达t1和 t2，而t1和t2属于现行中的两个不同子集，说明有一个字， t1读出后到达终态，而t2读出后不能到达终态，或者反之，那么对于字a ， s1读出a后到达终态，而 s2读出a不能到达终态，或者反之，所以 s1和s2不等价。 s1t1 a s2t2 a i j 29 编译原理例题3.1 n给出下面描述的正规表达式以01结尾的二进制数串能被5正除的十进制整数包含奇数个1或者奇数个0的二进制数串 30 编译原理例题3.2 n构造下面正规式相应的DFA 1(0|1)*101 步骤: .根据正规式画出对应的状态转换图; .根据状态转换图画出对应的状态转换矩阵; .根据状态转换矩

11、阵得到重命名后的状态转换矩阵; .根据重命名后的状态转换矩阵得出最后的DFA. 31 编译原理 1(0|1)*101 .状态转换图 a b a d b 1(0|1)*101 a 1 (0|1)* 101 d c ef 1 0 1 1 01 g g g 32 编译原理 .状态转换矩阵 II0 I1 ab,c,d b,c,dc,dc,d,e c,dc,dc,d,e c,d,ec,d,fc,d,e c,d,fc,dc,d,e,g c,d,e,gc,d,fc,d,e 1 ab d c ef 1 0 101 g 33 编译原理 I I0I1 a b,c,d b,c,d c,d c,d,e c,dc,dc

12、,d,e c,d,ec,d,fc,d,e c,d,fc,dc,d,e,g c,d,e,gc,d,fc,d,e .重命名后的状态转换矩阵 S01 A(始态)B BCD C C D D E D E C F(终态) F(终态)ED AB 1 0C 1D 0 1 0 E 1 0 1 01 F .DFA 34 编译原理例题3.3 n设M=(x,y, a,b, f, x, y)，其中f定义如下： f(x,a)=x, y f(x,b)=y f(y,a)= f(y,b)=x,y 请构造对应的确定有限自动机。 35 编译原理【解答】对照自动机的定义，由f的定义可知 f(x,a)、f(y,b)均为多值函数

13、，因此M是一非确定有限自动机。先画出NFA M相应的状态图， 36 编译原理用子集法构造状态转换矩阵 IIaIb xx, yy y-x, y x, yx, yx, y 37 编译原理重命名后的状态转换矩阵 Sab 021 1-2 222 38 编译原理 39 编译原理 1(1010*|1(010)*1)*0 ab d c 1 0 e 0 1 0 1 f gh i 0 1 11 0 j k lm n .状态转换图 nP64-7. 构造下列正规式相应的DFA。 40 编译原理 .状态转换矩阵 II 0I 1 01,2,3 1,2,345,9,10,11 5,9,10,116,122,3 6

14、,122,3,7,8,13 2,345,9,10,11 2,3,7,8,132,3,4,8,10,115,9,10,11 2,3,4,8,10,112,3,4,8,122,3,5,9,10,11 2,3,4,8,122,3,4,85,9,10,11,13 2,3,5,9,10,114,6,122,3,5,9,10,11 2,3,4,82,3,4,85,9,10,11 5,9,10,11,136,10,11,122,3 4,6,122,3,7,8,13 6,10,11,12122,3,7,8,13 1213 1310,11 10,11122,3 41 编译原理 .重命名后的状态转换矩阵 II 0I 1 12

展开阅读全文

编译原理例题与习题解答.

最新文档