编译原理试题

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

1、//东南大学一、文法G1：　　E→ET+

2、T　　T→TF*

3、F　　F→FP↑

4、P　　P→E

5、i　　1、试证明符号串TET+*i↑是G1的一个句型（要求画出语法树）。　　2、写出该句型的所有短语，简单短句和句柄。三、　　1、试写出一个上下文无关文法G3，它能产生配对的圆括号串（例如，（），（（）），（）（（））等，甚至包含0对括号）。　　2、使用文法G3给出输入串（（））（）#的自上而下分析过程。四、已知文法G4：　　S→aAb

6、Sc

7、ε　　A→aAb

8、ε　　1、给出G4文法的LR（0）项目集规范族；　　2、构造SLR分析表；　　3、G4文法所定义的语言；　　

9、4、已知有如下文法及相应的LR分析表，试给出语句01001#的LR分析过程（填写下表）。　　S→AAA　　A→1A　　A→0五、　　1、翻译下面语句成四元式中间代码序列和后缀式（逆波兰式）；　　whilex+y>ado　　ifa<10thena：=a+1elsex：=x-1；　　2、翻译布尔表达式　　（a>b）or（c=d）andnot（e

10、、LL（1）分析必须对原有文法提取左因子和消除左递归。　　3、算符优先分析法采用“移近-归约”技术，其归约过程是规范的。　　4、文法S→aA；A→Ab；A→b是LR（0）文法（S为文法的开始符号）。　　5、一个BASIC解释程序和编译程序的不同在于，解释程序由语法制导翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。　　二、设计一个最小状态有穷自动机，识别由下列子串组成的任意字符串。（20分）　　GO，GOTO，TOO，ON　　例如：GOTOONGOTOOGOON是合法字符串。　　三、构造一个LL（1）文法G，识别语言L：（20分）　　L={ω

11、ω

12、为{0，1}上不包括两个相邻的1的非空串}　　并证明你的结论。六、设有一个子程序的四元式序列为：（20分）　　（1）I：=1　　（2）ifI>20GOTO（16）　　（3）T1：=2*J　　（4）T2：=20*I　　（5）T3：=T1+T2　　（6）T4：=addr（A）-22　　（7）T5：=2*I　　（8）T6：=T5*20　　（9）T7：=2*J　　（10）T8：=T6+T7　　（11）T9：=addr（A）-22　　（12）T10：=T9[T8]　　（13）T4[T3]：=T10+J　　（14）I：=I+1　　（15）goto（2）　　（16）ret

13、　　1、分划基本块。　　2、对代码施行各种可能的优化，并写出优化过程中采用了何种优化策略。一、已知文法G1：　　S→aB

14、ε　　B→bC

15、bD　　C→cB

16、c　　D→d　　1、试构造一个最小DFA，画出状态转换图。　　2、由该DFA给出它所识别的语言（用正规式表示）。二、已知正规式α=ab*c*d，　　1、试构造一个DFAM，其接受的语言为此α（画出图）；　　2、由该DFAM写出对应的正规文法（古线性）。三、文法G3：　　S→A[B]　　A→[B]

17、Aa　　B→a　　1、求出各非终结符N的Firstvt（N）和Lastvt（N），构造包括语句括号‘#’在内的

18、算符优先表；四、已知文法G4：　　T→T*F

19、F　　F→（T）

20、i　　1、试给出语句（i*i）#的自上而下分析过程（填下表）；　　2、画出对应的语法树，指出每一步归纳的句柄。　　步骤│栈内│输入│动作五、已知文法G5：　　0、E‘→E　　1、E→E+T　　2、E→T　　3、T→i　　列出LR（0）项目集规范族，求出各非终结符N的Follow集合，构造SLR分析表。六、翻译如下语句成四元式序列（由语法制导生成）　　whilea>banda=d；七、按语法制导翻译

21、下段程序成四元式序列（不要优化），设数组A：array[1……10，1……10]ofint；每个下标变量占1字编址，数组按行存放，Z为函数名。　　begin　　A[i，j]：=A[i，j]+2；　　B：=Z（A[i，j]）*5　　end　八、将如下一段四元式序列进行块内优化和循环优化（强度减弱及删除基本归纳变量），写出优化后的四元式序列。（要求先划分基本块）　　（1）i：=1　　（2）ifi>100goto（10）　　（3）T1：=20*i　　（4）M：=J+T1　　（5）T2：=20*i　　（6）N：=K+T2　　（7）O：=M+N　　（8）i：=i+1　

22、　（9）goto（2）　　（10）……一、已知正规文