编程语言B卷+参考答案.docx

1、编程语言B卷+参考答案编程语言B卷+参考答案 学院 专业 姓名 学号 座号( 密 封 线 内 不 答 题 )密封线线_ _ 深圳大学期末考试试卷开/闭卷闭卷A/B卷B课程编号15030600课程名称编程语言学分2.5命题人(签字) 审题人(签字) 年 月 日题号一二三四五六七八九十基本题总分附加题得分评卷人一选择题（共10题，每小题2分，共20分，答案请填写在第四大题前的表格中）1. 以下哪条不影响语言的可读性？( ) A简单性 B. 正交性 C. 语法设计 D. 类型检查2. 开发专家系统时，通过描述事实和规则由模式匹配得出结论，这种情况下适用的编程语言是（ ）。 A逻辑式语言 B函数式语言

2、 C脚本语言 D命令式(或过程式)语言3. 考虑以下文法： a | b b | b以下语句中哪个属于该文法生成的语言？( )A.bbaabbB.bbababbC.babaabbD.bababb4.以下哪些文法有二义性? （ ）A. +| * a|b|cB. +*| a|b|cC. *| +21. 按照运算符的优先级从高到低排序有+， -（一元），=,and,结合性为从右到左，写出下列表达式的运算顺序。(1) a+bc=0 and c+d=(-a）(2) c(-d)=a and -a+by) then b = a-3 else b=2*a-1; b52. （6分）考虑下列程序：int x;voi

3、d setx(int n) x = n;void printx() print(x); /打印函数void foo(function S, function P, int n) int x = 5; if n % 2 = 1 then setx(n); else S(n); if n 3 then printx(); else P();setx(0);foo(setx, printx, 1); printx();setx(0);foo(setx, printx, 2); printx();setx(0);foo(setx, printx, 3); printx();setx(0);foo(se

4、tx, printx, 4); printx();假设语言采用动态作用域，那么(1)当采用浅绑定时，这个程序将打印出什么？(2)当采用深绑定时，这个程序将打印出什么？3. （4分）考虑下列程序int i = 0;int fun(int k) if(i % 2 = 0) return k*2; return k;void main() int x = 3; x = +i + fun(x);(1)如果操作数是从左到右计算，x的值什么？简要写出计算过程。(2)如果操作数是从右到左计算，x的值什么？简要写出计算过程。4. （9分）考虑下列程序void swap(int a, int b) a = a+

5、b; b = a-b; a = a-b; void main() int value = 2, list5 = 1,2,3,4,5; swap(value, list0); swap(list0, value); swap(value, listvalue);对以下每种参数传递方法，在每个swap调用后，变量value和list的值分别是什么？（1）按值传递（2）按引用传递（3）按值-结果传递五、解答题（共2题，25+10，35分）1.（25分）假设某语言的表达式遵循如下的结合性和优先级规则： 优先级最高*(乘方)%, 一元+,一元-最低*,/结合性左结合%,一元+,一元-右结合*,*,/(1

6、)假设操作数是整数和c,d,e,且允许括号，请根据以上优先级和结合性，写出BNF(2)根据（1）中的BNF，写出表达式+4%3/3*3的推导树及其最右推导前五步和后五步(3)请写出计算这些表达式的属性文法，并对（2）中表达式进行计算2.（10分）给定下列程序r = x;q = 0;while (y = r) r = r y; q = q + 1;请分别写出在状态x=7,y=3下的操作语义和指称语义（包括具体过程）附加题 （共2题，10+20，共30分）1.（10分）假设FOR语句的形式为FOR (; ; ),以计算最弱前置条件为例，设计FOR语句的公理语义。2. （20分）利用附加题1中的规则

7、，计算下列程序P和后置条件的最弱前置条件（包括具体过程）f = 1;for(c = n; c 1; c = c1) x = f;for(y = c; y 1; y = y-1) f = f + x; f = n!201702编程语言试卷 B 参考答案与评分标准一、选择题（10小题，每小题2分，共20分）DADBC DDACA二、判断题（10小题，每小题1分，共10分）TTFTF FTTTF三、填空题（5个空，每空2分，共10分）21（1）(a+b)1c)2=0)3 and (c+d)4=(-a)5)6)7(2) (c (-d)1)2=a)3 and (-(a+b)4)5=(-b)6d)7)8)

8、922（1）(a+b)1c)2=0)3 and c)4+d)5=(-a)6)7(2) (c (-d)1)2=a)3 and (-a)4)5+b)65，即a8；条件不成立时，2a-15，即a3（1分）。因此if语句的前置条件是a8（1分）。最后的前置条件为2ba8（1分）。2. （6分）（1）1，0；2，0；3，0；4，0（第一组和第三组各1分，第二组和第四组各0.5分）（2）1，0，5，2；0，0；4，4（第一组和第三组各1分，第二组和第四组各0.5分）3. （4分）（1）从左到右：先算+i, 得1（此时i1），再算fun(x)，得3，结果为4（2分）（2）从左到右：先算fun(x)，得6，再

9、算+i, 得1（此时i1），结果为7（2分）注：只写结果无过程得1分4. （9分）（1）按值传递：value=2, list5 = 1,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)（2）按引用传递：value=1, list5 = 2,2,3,4,5 (1分)value=2, list5 = 1,2,3,4,5 (1分)value=3, list5 = 1,2,2,4,5 (1分)（3）按值结果传递：value=1, list5 = 2,2,3,4,5 (1分)value=2, list5

10、= 1,2,3,4,5 (1分)value=3, list5 = 1,2,2,4,5 (1分)五、解答题（25+10=35分）1. (1) （5分） - * | / | - % | - + | - | - * | - INT | c | d | e | ( )注：只要文法正确即可得5分，否则根据产生式酌情给分，例如3个产生式1分（2）推导树（略）（5分），最右推导（略）（5分，每步0.5分）（3）属性文法，其中属性为val (1分) - * 语义函数：.val = mul(.val, .val) - / 语义函数：.val = div(.val, .val) - 语义函数：.val = .va

11、l - % 语义函数：.val = mod(.val, .val) - 语义函数：.val = .val - + 语义函数：.val = .val - - 语义函数：.val = -.val - 语义函数：.val = .val - * 语义函数：.val = power(.val, .val) - 语义函数：.val = .val - INT | a | b | c 语义函数：.val = lookup(table)l -( )语义函数：.val = .val注：只要语义函数符合（1）文法即可得6分，否则根据语义函数酌情给分，例如5个语义函数2分求值过程（略，可在（2）中推导树中标明），3分

12、，只给正确结果得1分。2.（10分）记整个程序为P，循环语句为W。操作语义（5分）r=x, x=7,y=3 - x=7,y=3,r=7q=0, x=7,y=3,r=7 - x=7,y=3,r=7,q=0 (1分)（可合并为r=x; q=0, x=7,y=3 -x=7,y=3,r=7,q=0）在x=7,y=3,r=7,q=0下，y x=7,y=3,r=4,q=0q=q+1, x=7,y=3,r=4,q=0 - x=7,y=3,r=4,q=1 （1分）(可合并r=r-y; q=q+1, x=7,y=3,r=7,q=0 - x=7,y=3,r=4,q=1)在x=7,y=3,r=4,q=1下，y x=

13、7,y=3,r=1,q=2 （1分）在x=7,y=3,r=4,q=1下，y x=7,y=3,r=1,q=2 （1分）指称语义（5分）M(P)(x=7,y=3) = M(r=x; q=0; W)(x=7,y=3)= (M(W) M(r=x; q=0;) (x=7,y=3)= M(W)( M(r=x; q=0;)(x=7,y=3) )= M(W)( x=7,y=3,r=7,q=0 ) (1分)= M(r=r-y; q=q+1; W)( x=7,y=3,r=7,q=0 )= (M(W) M(r=r-y; q=q+1;) (x=7,y=3,r=7,q=0) (0.5分)= M(W)( M(r=r-y;

14、 q=q+1;)(x=7,y=3,r=7,q=0) )= M(W)( x=7,y=3,r=4,q=1 ) (1分)= M(r=r-y; q=q+1; W)( x=7,y=3,r=4,q=1 )= (M(W) M(r=r-y; q=q+1;) (x=7,y=3,r=4,q=1) (0.5分)= M(W)( M(r=r-y; q=q+1;)(x=7,y=3,r=4,q=1) )= M(W)( x=7,y=3,r=1,q=2 ) (1分)=x=7,y=3,r=1,q=2 (1分)附加题（10+20=30分）1 （10分）若P stmt1 I，且I and cond stmt3;stmt2 I，那么则

15、有P FOR (stmt1; cond; stmt2) stmt3 I and not cond注：转化WHILE语句也可以。2 （20分）外层For语句的不变式I1为 fn!/c! and c=0里层For语句的不变式I2为 f(n!/c!)*(c-y+1) and y0 and c=y and x =(n!/c!)(1)证明外层循环终止时能推出给定的后置条件(2) 求解外层for的最弱前置条件(2.1) 求解内层for的最弱前置条件(2.2) 求解x=f的最弱前置条件(3)求解f1的最弱前置条件 (n=0)(1)证明外层循环终止时能推出给定的后置条件I1 and not c 1 = fn!

16、/c! and c=0 and c fn!/c! and c!=1 = fn!(2) 求解外层for的最弱前置条件(2.1) 证明I1 and c1 x=f;内层for;c=c-1 I1 fn!/(c-1)! and c-1=0 c=c-1 fn!/c! and c=0(2.1.1) 此次需计算内层for在fn!/(c-1)! and c=1的最弱前置条件(2.1.1.1) 先证明内层for终止时能推出给定的后置条件I2 and not y 1 = f=(n!/c!)*(c-y+1) and y0 and c=y and y f(n!/c!)*c and c=1 = fn!/(c-1)! an

17、d c=1(2.1.1.2) 证明I2 and y1 f=f+x;y=y-1 I2在I2下求f=f+x;y=y-1的最弱前置条件为f+x(n!/c!)*(c-y+2) and y1 and c=y-1 and x =(n!/c!)即f = (n!/c!)(c-y+1) and y1 and c y and x=(n!/c!)因此I2 and y1 成立即内层for的前置条件为I2y-c= f = (n!/c!)(c-c+1) and c0 and c= c and x=(n!/c!)即f = (n!/c!) and c0 and x=(n!/c!)(2.1.2) 求xf的最弱前置条件 f = (n!/c!) and c0 x=f f = (n!/c!) and c0 and x=(n!/c!)即I1 and I