编译原理作业

《编译原理作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、编译原理作业P7：1.1；1.2自编2.1；2.2自编2.3；2.4自编2.5自编3.1自编3.2自编3.3；3.4P100.4.1；4.2自编4.3；4.4自编5.1自编5.2自编7.1；7.2自编8.1P7：1.1P7；1.2自编2.1文法G[S]：S→xSx│y所识别的语言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*【解答】自编2.2令文法G[N]为G[N]:N→D∣ND　　D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9　　(1) G[N]的语言L(G)是什么?　　(2)给出句子0127、34和568的最左推导和最右推导。【解答】自编2.3对于文法G[S

2、]:S→(L)∣aS∣a　　L→L,S∣S　　(1)画出句型(S,(a))的语法树；　　(2)写出上述句型的所有短语、直接短语、句柄。【解答】自编2.4已知文法G[S]为S→SaS∣ε，试证明文法G[S]为二义文法。　【解答】自编2.5按指定类型，给出语言的文法。　　(1) L={aibj│j>i≥1}的上下文无关文法；　　(2)字母表∑={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；自编3.1什么是扫描器？扫描器的功能是什么？自编3.2结合自动机证明：正规式(ab)*a与正规式a(ba)*是否等价？给出分析过程。自编3.3已知自动机DFA如图3-4所示图3-

3、4DFA写出其对应的语言，分别用正规文法和自然语言描述。【解答】自编3.4设有L(G)={a2n+1b2ma2p+1

4、 n≥0,p≥0,m≥1}。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】P100：4.1P100；4.2自编4.3在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？【解答】自编4.4设有文法G[S]:S→a

5、b

6、(A)A→SdA

7、S(1)构造算符优先关系表；(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；【解

8、答】自编5.1(1)四元式之间的联系是通过实现的。a.指示器b.临时变量c.符号表d.程序变量(2)间接三元式表示法的优点为。a.采用间接码表，便于优化处理b.节省存储空间，不便于表的修改c.便于优化处理，节省存储空间d.节省存储空间，不便于优化处理(3)表达式(┐A∨B)∧(C∨D)的逆波兰表示为。a.┐AB∨∧CD∨b.A┐B∨CD∨∧c.AB∨┐CD∨∧d.A┐B∨∧CD∨【解答】自编5.2(4)有一语法制导翻译如下所示：S→bAb{print″1″}A→(B{print″2″}A→a{print″3″}B→Aa){print″4″}若输入序列为b(((aa)a)a)b，且

9、采用自下而上的分析方法，则输出序列为。【解答】自编7.1将下面程序划分为基本块并作出其程序流图。read(A,B)F=1C=A*AD=B*BifC100gotoL2haltL2:F=F-1gotoL1【解答】自编7.2试画出如下中间代码序列的程序流图，并求出：(1)各结点的必经结点集合D(n)；(2)流图中的回边与循环。J=0L1：I=0if I<8gotoL3L2：A=B+CB=D*CL3：if B=0gotoL4writeBgotoL5L4：I=I

10、+1ifI<8gotoL2L5：J=J+1if J<=3gotoL1halt【解答】自编8.1何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？【解答】