编译原理试卷二

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

1、一、选择1.下面说法正确的是：A一个正规式只能对应一个确定的有限状态自动机；B一个正规语言可能对应多个正规文法；2.算符优先分析与规范归约相比的优点是：A归约速度快B对文法限制少3.一个LR（1）文法合并同心集后若不是LALR（1）文法：A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突4.下面说法正确的是：ALex是一个词法分析器的生成器BYacc是一个语法分析器二、问答题问答第1题(5分)将文法G[S]改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。　　G[S]：S→SAe

2、AeA→dAbA

3、dA

4、d解：文法G[S]改写为等价的不含左

5、递归和左公共因子的G'[S]为：　　S→AeS'　　S'→AeS'

6、ε　　A→dA'　　A'→AB

7、ε　　B→bA

8、ε问答第2题(10分)判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。　　S→aD　　D→STe

9、ε　　T→bH

10、H　　H→d

11、ε首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集S{a}.........{#，b，d，e}.D{a，ε}....{#，b，d，e}T{b，d，ε}{e}.............H{d，ε}....{e}............. 由于select（D→STe

12、）∩select（D→ε）={a}∩{#，b，d，e}=　　select（T→bH）∩select（T→H）={b}∩{e}=　　select（H→d）∩select（H→ε）={d}∩{e}=所以该文法是LL(1)文法，LL(1)分析表如下表。LL(1)分析表 aebd#S→aD.    D→STe→ε→ε→ε→εT →H.→bH→H. H →ε →d. 问答第3题(5分)给出与正规式R＝（(ab)*

13、b）*（a

14、(ba)*）a等价的NFA。解：与正规式R＝（(ab)*

15、b）*（a

16、(ba)*）a等价的NFA如下图问答第4题解：根据所给的PL/0示意程序完成下列要求。（1）(4分)给出当程序

17、执行到A过程体的write(c)语句时的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容；（2）(2分)说明在过程D中，当执行c:=b*a；语句时，变量c和b的存取位置是如何确定的（请填在下面的相应括号内）。　　c的存取位置=（）　　b的存取位置=（）PL/0示意程序为：　　varc;　　procedureM;　　　　procedureA;　　　　begin(*A*)　　　　　write(c);　　　　end(*A*)　　　procedureZ;　　　　vara,b;　　　　procedureD　　　　　begin(*D*)　　　　　　c:=b*a；　　　　　　callA;　

18、　　　　end；(*D*)　　　　begin(*Z*)　　　　　callD;　　　　end；(*Z*)　　　begin(*M*)　　　　callZ;　　　end；(*M*)　　begin(*main*)　　　callM;　　end.(*main*)解：（1）当程序执行到A过程体的write(c)语句时的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容如下图。当程序执行到A过程时栈式存储分配布局和栈中过程最新活动记录的内容（2）在过程D中，当执行c:=b*a；语句时，变量c和b的存取位置可如下确定：由于D过程的display表内容为：d（3）D的SPd（2）Z的SPd（1）M的

19、SPd（0）Main的SP所以c的存取位置=（d（0）中Main的SP+c在Main中的偏移量）b的存取位置=（d（2）中Z的SP+b在Z中的偏移量）问答第5题（6分）试对while(a>bandabgoto(　)(　)真链头E.true=(2)goto(　)(　)真出口链(　)(3)ifa

20、a   (8)goto(　)(　) (9)    解：  应回填的值回填的次序 (1)ifa>bgoto(3)(1)真链头E.true=5(2)goto(5)(3)真出口链(5,3)(3)ifa