南师计算机编译原理2013A卷.doc

南京师范大学2012-2013学年 第二学期 计算机学院计算机专业《编译原理》课程期末试卷 （A卷） 班级: 任课教师: 学号: 姓 名: 题号 一　 二 三 四 五 六 七 八 九 十 十一 十二 总分 得分 （6分）简述一个典型的编译程序总体上由哪些部分组成？ （10分）设有文法如下： G[S]: S::=T+S|T-S|T T::=L*T|L/T|L L::=(S)|a|b 问：1、(3分)给出该文法的非终结符号集合VN。 2、(4分)给出该文法的终结符号集合VT。 3、（3分）给出句子(a-b)*a的最右推导。 三、（8分）设有文法如下： G(S): S::= (L)|a L::=L,S|S 问：１、(6分)给出句型(L,S,(a))的所有短语、直接短语、句柄。 ２、(2分)给出句型(S,S,(a))的所有的素短语。 四、（7分）设计一个DFA，识别出所有的由0、1所成的串，要求：每一个1后边必须跟至少一个0。如：0是合法的。010也是合法的。但01是不合法的。 五、（9分）设有文法如下： G[S] S::=SaSb S::=bS S::=ε 注：ε表示空 给出ＬＬ（１）分析表（7分）该文法是ＬＬ（１）文法吗？（２分） 六、（6分）设有文法如下： G[S] : E ::=EE|(E)|() 证明该文法是二义性文法。 七、(9分) 设有数组定义如下：int a[5][10];设数组按行存放，每一个int占四个字节。现有语句 while( i10 ) { if(i5) { i=a[i+1][i*2]; } else{ i=i+1; } } 写出该语句翻译成的目标代码（三地址代码或四元式）。若目标代码是四元式序列。则请从100号单元开始。 八、（10分）设有文法G[S]： S::=S+S S::=a S::=ε 注：ε表示空 给出该文法的SLR（1）分析表。(8分)该文法是SLR(1)文法吗？（2分） 九、（8分）设有文法G[S]如下：S::=L,（S） L::= S | i 问：1、给出该文法的算符优先关系表。(填写下表)(6分)，该文法是算符优先文法吗？（2分） （ ） , i ( ) , i 十、(8分)设有文法如下G[S’]： 　　　S’::=S S::=L=R S::=R L::=*R L::=i R::=L 将下边两个LR(1)项目集填充完整： 十一、（6分+7分）设C语言函数的活动记录结构如下（已简化）,运行栈自底向上增长： 6 其它 5 临时变量 4 局部变量 3 老SP(调用者的SP) 2 返回地址 1 形式参数 现有C程序如下： int f(int n,int m) { int k; if (n+m=0) k=0; else k=n*m + f(n-1,m-2); return k; } void main() { int p; p=f(5,4); ………….//其它语句 } ------------------------------① 问： 1、(6分)设采用标识符栈来登记标识符的作用域及其它信息。而且该标识符表中内容需要留到以后阶段使用。当编译到①处时，画出标识符栈中内容。 2、(7分)运行时当第二次（递归）进入f后即：main()-f(5,4)-f(4,2)时，给出整个运行栈的内容。 十二、（6分）设有文法G[S]： S::=(A,(A)) A::=(A) A::= ε　　注：ε表示空 给该文法配上语义规则，计算并打印出括号嵌套的最大深度。如：（（），（（）））是３，而（（），（））是２。（（（（））），（））是４。 第 2 页 共 1 页 第 1 页 共 7 页 L I0: S’::=.S, # I1: