编译原理平时作业

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是符合要求的串，|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

2、)等价的正规表达式，即S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S为：(00|11)|(01|10)(00|11)*(01|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结束的符号串的集合。DFAM=(0，1，q0，q1，q2，q0，q2，)其中定义如下:（q0，0）=q1（q0，1）=q0（q1，0）=q2（q1，1）=q0（q2，0）=q2（q2，1）=q0(2)所有具有3个0的符号串的集合。正则表达式: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

3、，1）=q33 下面是用正规式表示的变量声明：( int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。4 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：stmt if expr then stmt |matched-stmt matched-stmt if expr then matched-stmt else stmt |other 试说明此文法仍然是二义性的。 答：1.考虑句子ifethenifethenotherelseifethenotherelseother它具有如下所示的两种分析树则上面给出的if-then-else文法仍是二义性的5 证明下面文法是SLR(1)文法，并构造其SLR分析表。EE+T|T TTF|F FF*|a|b 6 为下面的文法构造LALR(1)分析表SE EE+T|TT(E)|a7 （1）通过构造识别活前缀的DFA和构造分析表，来证明文法E E + id | id是SLR(1)文法。（2）

4、下面左右两个文法都和（1）的文法等价E E + M id | idE M E + id | idM eM e请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。（1）先给出接受该文法活前缀的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再构造SLR分析表如下：状态 动作转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中没有多重定义的条目，因此该文法是SLR(1)的。（2）只有文法E M E + id | idM e不是LR(1)文法。因为对于句子id+id+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | eint realid,$DDTLDTLTTintTrealLLid RRR , id RR e9 下面的文法产生的表达式是对整型和实

5、型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。 EE+T|T Tnum.num|num （a）给出一个语法制导定义以确定每个子表达式的类型。 （b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。10 假设说明是由下列文法产生的： Did L L,id L|:T Tinteger |real （a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （b）从（a）中的翻译模式构造一个预翻译程序。 11为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。E E *E | +E | -E | unsigned_integer12为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。

6、）S L . R | LL L B | BR B R | BB 0 | 113 试问下面的程序将有怎样的输出？分别假定： （a）传值调用（call-by-value）； （b）引用调用（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.14 对以下的Pascal程序画出过程c第二次被激活时的运行栈，控制链和访问链。说明在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. main15 下面给出一个 C 语言程序及

7、其在 SPARC/SUN 工作站上经某编译器编译后的运行结果。从运行结果看，函数 func中 4个局部变量 i1, j1, f1, e1的地址间隔和它们类型的大小是一致的，而 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( Sizes 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，请问为什么？分析：long类型数据

《编译原理平时作业》由会员jay****li分享，可在线阅读，更多相关《编译原理平时作业》请在金锄头文库上搜索。