编译原理考试复习题编译原理考试复习题.docVIP

河南城建学院2010学年第一学期期末考试 《编译原理》试题（A卷） 一、填空题：（每空1分，共10分）? 1、符号表项的组织常采用线性法、二分法和（散列法）。? 2、整个编译过程可以划分成五个阶段：（词法分析）、语法分析阶段、（语义分析及中间代码生成）、（代码优化）和目标代码生成阶段。? 3、对于文法G，仅含终结符号的句型称为（句子）。 ?4、逆波兰式ab+c+d*e-所表达式为（(a+b+c)*d-e）。? 5、语言翻译常用的两种形式是（编译）和（解释）。? 6、词法分析器输出的是单词符号，语法分析器输出的是（语法单元）。 二、选择题：（每空2分，共10分）? 1、3型文法是（D）是语法分析使用的文法。? A．短语文法???B.上下文有关文法????C.上下文无关文法????D.正规文法? 2、语法分析是依据语言的（A）规则进行的，中间代码产生是依据语言的（）规则进行的。?? A．语法，?推导????B．语义，产生式???C．语法，?语义????D．推导，?产生式? 3、错误“变量类型声明不一致”将在（???C????）阶段发现。? A．词法分析??B.语法分析????C.语义分析??????D.目标代码生成? 4、下列（??D?）不是数据空间的使用方法和管理方法? A．静态存储分配????B.栈式动态存储分配????C.堆式动态存储分配????D.段页式存储分配 三、计算题：（每题6分，共24分）? 1、对给定正规表达式b*(d∣ad)?(b∣ab)+构造其NFA?M。 解：先用R+=RR*改造题设的正规表达式为b*(d∣ad)?(b∣ab)?(b∣ab)*，然后构造其? NFA?M，如图: 2、试给出下列语句的四元式序列：? if?(a0∧b＞5)?X[1,1]＝=1;?else?X[3,2]＝0;????其中，X是10×20的数组(每维下界为1)且按行存放；一个数组元素占用两个字节，机器按字节编址。? 解： 100?(j,?a,?0,?102)? 101?(j,_,?_,110)? 102?(j,b,5,104)? 103?(j,?_,_,110)? 104?(*,1,40,T1)? 105?(*,1,2,T2)? 106?(+,T1,T2,T3)? 107?(?,X,42,T4)? 108?([?]=,1,?_,T4[T3])? 109?(j,?_,_,115)? 110?(*,3,40,T1)? 111?(*,2,2,T2)? 112?(+,T1,T2,T3)? 113?(?,X,42,T4)? 114?([?]=,0,?_,T4[T3])? 115 3、已知文法G[E]为：????????E→T∣E＋T????????T→F∣T*F????????F→(E)∣i? ???????试确定T＋T*F＋i的最左素短语。? 解：短语有：T+T*F+i????????????T+T*F????????????T????????????T*F????????????i? 根据最左素短语必须具备的条件及短语的要求得到最左素短语为T*F。 4、对文法G[S]????S→a|∧|(T)???T→T，S|S?? ??(1)?给出(a,(a,a))的最左推导。? 是二义性文法。? 解：对(a,(a,a)的最左推导为：??? S→ (T)?→(T,S)?→(S,S)?→?(a,S)???→(a,(T))????→?(a,(T,S))??→???(a,(S,S))??→?(a,(a,S))?→??(a,(a,a))? 四、证明题（每题8分，共16分）? 1、试证明文法G＝({E，O},{（,）,＋,*,v,d},P,E)，其中P为： E→EOE∣(E)∣v∣d?O→＋∣*??是二义性文法。? 证明：对于句子v*v+d的语法树不只一棵，可画出语法树或写出两个不同的最左推导。 2、文法? ?E→E+E∣E*E∣E/E∣E↑E∣(E)?∣i? 试证明该文法是算符文法，但不是算符优先文法。? 证明：由于文法G[E]中的任何产生式右部都不含两个相邻的非终结符，所以G[E]是算符文法。此外，因为? ?????????(1)?由于存在E→E+E，而E+E中的第二个E可推出E??E*E，即有+?*；??????????(2)?由于存在E→E*E，而E*E中的第一个E可推出??E??E+E，即有+?*。? ?????????此即运算符+和*之间同时存在着两种不同的优先关系，故文法G[E]不是一个算符优先文法。 五、综合题（第1小题10分，第2、3小题各15分）?1、对下图的流图：? ??(1)?求出流图中各结点n的必经结点集D(n)；????(2)?求出流图中的回边；???(3)?求出流图中的循环。? 解： D(1)={1}?