编译原理试题.doc

/东南大学一、文法G1：EET+|TTTF*|FFFP|PPE|i1、试证明符号串TET+*i是G1的一个句型（要求画出语法树）。2、写出该句型的所有短语，简单短句和句柄。三、1、试写出一个上下文无关文法G3，它能产生配对的圆括号串（例如，（），（），（）（）等，甚至包含0对括号）。2、使用文法G3给出输入串（）（）#的自上而下分析过程。四、已知文法G4：SaAb|Sc|AaAb|1、给出G4文法的LR（0）项目集规范族；2、构造SLR分析表；3、G4文法所定义的语言；4、已知有如下文法及相应的LR分析表，试给出语句01001#的LR分析过程（填写下表）。SAAAA1AA0五、1、翻译下面语句成四元式中间代码序列和后缀式（逆波兰式）；while x+ya doif ab） or （c=d） and not （e20 GOTO（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：=T9T8（13）T4T3：=T10+J（14）I：=I+1（15）goto（2）（16）ret1、分划基本块。2、对代码施行各种可能的优化，并写出优化过程中采用了何种优化策略。一、已知文法G1：SaB|BbC|bDCcB|cDd1、试构造一个最小DFA，画出状态转换图。2、由该DFA给出它所识别的语言（用正规式表示）。二、已知正规式=ab*c*d，1、试构造一个DFAM，其接受的语言为此（画出图）；2、由该DFAM写出对应的正规文法（古线性）。三、文法G3：SABAB|AaBa1、求出各非终结符N的Firstvt（N）和Lastvt（N），构造包括语句括号#在内的算符优先表；四、已知文法G4：TT*F|FF（T）|i1、试给出语句（i*i）#的自上而下分析过程（填下表）；2、画出对应的语法树，指出每一步归纳的句柄。步骤栈内输入动作五、已知文法G5：0、EE1、EE+T2、ET3、Ti列出LR（0）项目集规范族，求出各非终结符N的Follow集合，构造SLR分析表。六、翻译如下语句成四元式序列（由语法制导生成）while ab and a=d；七、按语法制导翻译下段程序成四元式序列（不要优化），设数组A：array110，110 of int；每个下标变量占1字编址，数组按行存放，Z为函数名。beginAi，j：=Ai，j+2；B：=Z（Ai，j）*5end八、将如下一段四元式序列进行块内优化和循环优化（强度减弱及删除基本归纳变量），写出优化后的四元式序列。（要求先划分基本块）（1）i：=1（2）if i100 goto（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（9）goto（2）（10）一、已知正规文法中的左线性文法G1：SSa|Sb|c试构造无产生式的等价右线性文法，并构造相应的确定有限自动机DFA，画出状态转换图即可。二、已知正规文法（X为开始符号）G2：X0Y|1Z|0Y0X|1Y|1Z1X1、该文法产生语言是什么？请用正规式表示。2、构造最简的确定有限自动机DFA，并画出状态转换图。2、给出文法改写以后的各非终结符X的First（X）与Follow（X）集合，并由此判定它是否是LL（1）文法四、已知表达式文法（已拓广）G4：EEEE+E|i1、试构造文法G4的LR（0）项目集规范族；五、已知文法（Z为开始符号）G5：ZbMbM（Ma）|a1、试构造算符优先分析表六、翻译成中间代码1、将如下程序段翻译成后缀式（逆波兰式），填在一维数组POSTi中，设i初值=1.t：=15；b：=20；while tb doif tb then t：=t-belse b：=b-t；2、翻译布尔表达式成转移四元式序列，并指出待填真假链序号。（ab+1）and not（c+2d）or f（x）注：f（x）为布尔函数。八、已知如下程序段a：=1；while a=10 dobeginif ab thenAa，b：=Aa，b+2；a：=a+1；end；1、按语法制导生成四元式中间代码序列；2、将中间代码序列划分成基本块，画出程序流图，并指出循环结点集；3、执行循环中代码外提，强度减弱优化和基本块内删除公共子表达式优化，最后画出包含优化后的中间代码的程序流图。 注：数组A：array110，110 of int；按行存放，每个下标变量占1字编址，首地址为addrA./上海交大八、已知如下程序段a：=1；while a=10 dobeginif ab thenAa，b：=Aa，b+2；a：=a+1；end；1、按语法制导生成四元式中间代码序列；2、将中间代码序列划分成基本块，画出程序流图，并指出循环结点集；3、执行循环中代码外提，强度减弱优化和基本块内删除公共子表达式优化，最后画出包含优化后的中间代码的程序流图。 注：数组A：array110，110 of int；按行存放，每个下标变量占1字编址，首地址为addrA.清华大学1997年研究生入学考试 编译原理试题（共50分）5(6分)试对下面基本块进行优化 应用DAG对该基本块进行优化，给出优化后的语句序列。 给出当只有L在基本块出口后为活跃时的优化结果。 基本块为： X=BC Y=B/C Z=X+Y W=9Z 6(6分)已知文法GS为：SdABAaA|aBBb| 试向GS是否为正规文法，为什么？ GS新产生的语言是什么？GS能否改写为等价的正规文法？3(8分)专有文法GS为： 专Sa|b|（A）共ASdA|S 完成下列算符优先关系表，并判断GS是否为算符优先文法。同济GS的算符优先关系表业表1 算符优先关系表共济网ab()D#密云路a kaoyangjb 1号(=8#信箱d # = 给出句型（sdsds）的短语，简单短语句柄，素短语和最大素短语。 给出输入串（adb）的分析过程。4 (8分)已知文法GS为：SaAd|；Bd|aB|；AAaBa 试判断GS是否为LALR（1）文法 当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。1、 请写出在a,b上，2、 不3、 是a开头的，4、 以aa结尾的字符串集合的正规表达式，5、 并构造与之等价的状态最少的的DFA。（9分）三、给出文法G2:S SaS SbS cSd eS f1、 请证实这是一个二义文法；2、 给出什么的约束条件，3、 可构造出无冲突的LR分析表？请证实你的论点。（8分）。四、给出下列代码序列：(1) a:=b-c(2) d:=a+4(3) e:=a-b(4) f:=c+e(5) b:=b+c(6) c:=b-f(7) if b (8) b:=b-c(