编译原理平时作业问题详解.docx

1、编译原理平时作业问题详解平时作业1 对于下列语言分别写出它们的正规表达式。 (1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。答：令Letter表示除这五个元音外的其它字母。(letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 答： A*B*.Z*(3)=0,1上的含偶数个1的所有串。答：(0|10*1)*(4)=0,1上的含奇数个1的所有串。答：(0|10*1)*1(5)具有偶数个0和奇数个1的有0和1组成的符号串的全体。答：设S是符合要求的串，|

2、S|=2k+1 (k0）。则 SS10|S21，|S1|=2k (k0），|S2|=2k (k0）。且S1是0,1上的串，含有奇数个0和奇数个1。S2是0,1上的串，含有偶数个0和偶数个1。 考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S为： (00|11)|(01|10)(00|11)*(01|

3、10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|11)*(01|10)*1(6)不包含子串011的由0和1组成的符号串的全体。答：1*|1*0(0|10)*(1|)(7)由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答： 假设w的自动机如下：对应的正规表达式：(1(01*0)1|0)*2 给出接受下列在字母表0,1上的语言的DFA。(1)所有以00结束的符号串的集合。(2)所有具有3个0的符号串的集合。答：(1) DFAM=(0，1，q0，q1，q2，q0，q2，)其中定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1

4、，1）=q0（q2，0）=q2 （q2，1）=q0(2)正则表达式: 1*01*01*01* DFAM=(0，1，q0，q1，q2，q3，q0，q3，)其中定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1，1）=q1（q2，0）=q3 （q2，1）=q2（q3，1）=q3 3 下面是用正规式表示的变量声明： ( int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。答：D T L ; T int | float L L, id | id4 试分析下面给出的if-then-else语句的文法，它的提

5、出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：stmt if expr then stmt |matched-stmt matched-stmt if expr then matched-stmt else stmt |other 试说明此文法仍然是二义性的。 答：考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other i

6、f esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other 则上面给出的if-then-else文法仍是二义性的。5 证明下面文法是SLR(1)文法，并构造其SLR分析表。E

7、E+T|T TTF|F FF*|a|b 答：该文法的拓广文法G为 (0) E E(1) E E+T(2) E T(3) T TF(4) T F(5) F F*(6) F a(7) F b其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = EE, EE+T, ET, TTF, TF, FF*,Fa, Fb I1 = EE, EE+TI2 = ET, TTF, FF*, Fa, FbI3 = TF, FF* I4 = Fa I5 = Fb I6 = EE+T, TTF, TF, FF*, Fa, Fb I7 = TTF, FF* I8 = FF*I9 = EE+T, TTF

8、, FF*, Fa, Fb求FOLLOW集：FOLLOW(E)=, FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。6 为下面的文法构造LALR(1)分析表SE EE+T|TT(E)|a答：其拓广文法G： (0) S S(1) S E(2) E E+T(3) E T(4) T (E)(5) T a构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = SS, $, SE, $, EE+T, $/+, ET, $/+,T(E), $/+, Ta, $/+ I1

9、= SS, $ I2 = SE, $, EE+T, $/+ I3 = ET, $/+I4 = T(E), $/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I5 = Ta, $/+ I6 = EE+T, $/+, T(E), $/+, Ta, $/+I7 = T(E), $/+, EE+T, )/+ I8 = ET, )/+I9 = T(E), )/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I10 = Ta, )/+ I11 = EE+T, $/+ I12 = T(E), $/+I13 = EE+T, )/+, T(

10、E), )/+, Ta, )/+ I14 = T(E), )/+, EE+T, )/+I15 = EE+T, )/+ I16 = T(E), )/+合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下： I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/+, Ta, $/+I1 = SS, $ I2 = SE, $, EE+T, $/+ I3,8 = ET, $/+/)I4,9 = T(E), $/+/), EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I5,10 = Ta, $/+/) I6,13 = EE+

11、T, $/+/), T(E), $/+/), Ta, $/+/)I7,14 = T(E), $/+/), EE+T, )/+ I11,15 = EE+T, $/+/) I12,16 = T(E) , $/+/)LALR分析表如下：7 （1）通过构造识别活前缀的DFA和构造分析表，来证明文法E E + id | id是SLR(1)文法。答：先给出接受该文法活前缀的DFA如下：再构造SLR分析表如下： 动作转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中没有多重定义的条目，因此该文法是SLR(1)的。（2）下面左右两个文法都和（1）的文法等价

12、E E + M id | id E M E + id | id M M 请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。答：只有文法 E M E + id | id M 不是LR(1)文法。因为对于句子id+id+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8 根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。 D TL T int | real L id R R , id R | 答：先计算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(

13、L) = id FIRST(R) = ,FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealid,$DD - TLD - TLTT - intT - realLL - idRRR - ,idRR - 9 下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。 EE+T|T Tnum.num|num （a）给出一个语法制导定义以确定每个子表达式的类型。 （b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值

14、转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。答： (a):产生式语义规则E E1+TIF (E1.type=integer) and (T.type=integer) THEN E.type:=integerELSE E.type:=realE TE.type:=T.typeT num.numT.type:=realT numT.type:=integer(b):产生式语义规则E E1+TIF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(+,E1.val,T.val) EN

15、DELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=realE1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(+,E1.val,T.val)ENDE TE.type:=T.typeE.val:=T.valT num.numT.type:=realT.val:=num.num.lexvalT numT.type:=integerT.val:=num.lexva

16、l10 假设说明是由下列文法产生的： Did L L,id L|:T Tinteger |real （a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （b）从（a）中的翻译模式构造一个预翻译程序。 答： (a)：产生式翻译模式D id LD.Type:=L.Typeaddtype(id.entry, D.type)L ,id L1L.Type:=L1.Typeaddtype(id.entry, L.type)L :TL.type:=T.typeT integerT.type:=integerT realT.type:=real(b)： Procedure D; begin If l

17、ookahead=id then BeginMatch(id);D.type=L;addtype(id.entry,D.type) endelse error endFunction L: DataType;BeginIf lookahead=, then Begin Match(,); If lookahead=id then begin match(id);L.Type=L; addtype(id.entry,L.type); return(L.type) end Else error EndElse if lookahead=: thenBeginMatch(:);L.Type=T;re

18、turn(L.Type)endelse errorEnd Function T: DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer)endelse If lookahead=real thenBeginMatch(real);return(real)endelse errorend11 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。E

19、E *E | +E | E | unsigned_integer答： E E1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG E +E1 E.sign := E1.sign E E1 if E1.sign= POS then E.sign := NEG else E.sign := POSE unsigned_integer E.sign := POS12 为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。

20、） S L . R | L L L B | B R B R | B B 0 | 1答： S L . R S. val := L. val + R. val S L S. val := L. val L L1 B L. val := L1. val 2 + B. valL B L. val := B. val R B R1 R. val := (R1. val + B. val)/2R B R. val := B. val/2 B 0 B. val := 0B 1 B. val := 113 试问下面的程序将有怎样的输出？分别假定： （a）传值调用（call-by-value）； （b）引用调用

21、（call-by-reference）； （c）复制恢复（copy-restore）； （d）传名调用（call-by-name）。 program main(input,output）； procedure p（x,y,z）； begin y：y1； z：zx； end； begin a：2； b：3； p(ab,a,a)； print a end.答：1)传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的地方

22、。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，过程体对形式参数的任何引用1或赋值都被处理成对形式单元的间接访问。当调用段工作完毕返回时，形式单元(它们都是指示器)所指的实在参数单元就持有所指望的值。 2)传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访问。但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单元之中。 3)传值：所谓传值，是一种简单的参数传递

23、方法。调用段把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那末，在被调用段中无法改变实参的值。 4)传名：所谓传名，是一种特殊的形实参数结合方式。解释“传名”参数的意义：过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。 (a)2； (b)8； (c)7； (d)9。14 对以下的Pascal程序画出过程c第二次被激活时的运行栈，控制链和访问链

24、。说明在c中如何访问变量x。program env； procedure a； var x:integer； procedure b； procedure c； begin x:=2；b end；procedure c begin c end；procedure b begin b end；procedure a begin a end. main答：说明：c中沿着存取链向前走两步，到过程a的活动记录中就可以访问到变量x。15 下面给出一个 C 语言程序及其在 SPARC/SUN 工作站上经某编译器编译后的运行结果。从运行结果看，函数 func中 4个局部变量 i1, j1, f1, e1的地

25、址间隔和它们类型的大小是一致的，而 4个形式参数 i, j, f, e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。注意，输出的数据是八进制的。 func (i, j, f, e) short i, j; float f, e; short i1, j1; float f1, e1; printf( Address of i, j, f, e = %o, %o, %o, %o n, &i, &j, &f, &e); printf( Address of i1, j1, f1, e1 = %o, %o, %o, %o n, &i1, &j1, &f1, &e1); printf( Si

26、zes of short, int, long, float, double = %d, %d, %d, %d, %d n, sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double) ); main() short i, j; float f, e; func(i, j, f, e); 运行结果是： Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554 Address of i1, j1, f1, e1 = 35777772426, 35777772424, 35777772420, 35777772414 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8，请问为什么？答：C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。但是对于形式参数和实在参数是不同的整型（如一个是short型，另一个是long型），或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要高级别类型数据向低级