资源描述:
《太原师范学院2010编译答案A.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、院(系)_______________专业_______________班级_______________学号_______________姓名_______________………...………………………….密………………………..封…………………………..线……………………………………………………………..太原师范学院2010-2011第一学期期末考试编译原理试卷(A)参考答案一、⒈×⒉×⒊√⒋√⒌√⒍√⒎×⒏×⒐×⒑√二、⒈AC⒉B⒊DC⒋B⒌D⒍E⒎B⒏B⒐D⒑B三、⒈传值、传地址、换名⒉局部优化、全局优化、循环优化⒊堆式、栈式⒋记录变量名字并收集其各种属性,如有关
2、存储分配、类型、作用域,过程参数个数、类型、传递方式、返回值类型等。⒌后缀表达式、图形表示如语法树、DAG、三地址代码。⒍保留字、标识符、常量、算符、分界符。⒎基础文法、语义动作或语义子程序。⒏正规式、正规文法、DFA/NFA。⒐(Q,∑,δ,S0,F)⒑返回值、参数、控制链、访问链、保存的机器状态、局部数据、临时数据。四、回答题⒈①二元赋值x=yopz②一元赋值x=opy③复写x=y④无条件转移gotoL⑤条件转移ifxrelopygotoL⑥过程调用与返回paramx、callp,n、returny⑦索引赋值x=y[i]x[i]=y⑧地址和指针赋值x=&y、x=*y、
3、*x=y⒉公共子表达式删除、复写传播、死代码删除、代码外提、强度削弱、归纳变量删除⒊Chomsky把文法分成四种类型,即0型、1型、2型、3型,区别在于对产生式的不同限制。令文法为G=(Vt,Vn,S,P),其每个产生式α→β满足以下条件:①α∈(Vn∪Vt)*且至少包含一个非终结符,β∈(Vn∪Vt)*,称为短语结构文法,对应自动机为图灵机,对应语言为递归可枚举语言。②
4、α
5、≦
6、β
7、,除S→ε外;或αAβ→αγβ为其产生式,且α、β不能为空,α、β为其上下文,对应自动机为线性有界自动机,对应语言为上下文有关语言。③产生式为A→β,A∈Vn,对应上下文无关文法,对应自动机
8、为下推自动机,对应语言为上下文无关语言④产生式为→aB
9、a,其中a∈Vt,对应自动机为NFA、DFA,对应语言为正规语言,对应文法为正规文法。⒋①绝对机器语言程序,装入固定的起始地址,程序可以迅速地编译执行。②可重定位机器语言程序,可装入任意起始地址,内含重定位信息,通过连接装入程序把一组可重定位目标模块连接成可执行目标程序。③汇编语言程序,产生符号指令,利用汇编器的宏机制生成代码。⒌可用表达式数据流方程以表达式集合为论域的正向方程,迁移函数形式为e_genB∪(x-e_killB),边界条件为OUT[ENTRY]=Φ,汇合算符为∩,方程形式为OUT[B]=fB(IN[B
10、]),IN[B]=∧OUT[P],其中P为B的前驱。初始化条件为OUT[B]=U迭代算法:输入程序流图及各块的e_genB和e_killB输出除ENTRY外的各块B的IN[B]和OUT[B]OUT[ENTRY]=Φ;For(除了ENTRY块以外的每个块B)OUT[B]=U;While(任意一个OUT出现变化)For(除了ENTRY以外的每个块B){IN[B]=∩OUT[P];OUT[B]=e_genB∪(IN[B]-e_killB);}⒍T1=2T2=5T3=S-RT4=S+RA=T2*T4T6=T3*T4五、解析题⒈S→S(*T
11、/T)
12、T消除左递归S→TS′S′→(*
13、T
14、/T)S′
15、εT→T(+F
16、-F)
17、F消除左递归T→FT′T′→(+F
18、-F)T′
19、εFIRST(S)=FIRST(T)=FIRST(F)={(,id}FOLLOW(S′)=FOLLOW(S)={#,)}FOLLOW(T′)=FOLLOW(T)=FIRST(S′)={*,/}S(){symtoken;token=getsym();If(token∈FIRST(S)){T();S′();}Elseerror();}S′(){symtoken;token=getsym();if(token==“*”
20、
21、token==“/”){T();S′()}elseif(!(token
22、∈FOLLOW(S′)error();}T(){symtoken;token=getsym();If(token∈FIRST(T)){F();T′();}Elseerror();}T′(){symtoken;token=getsym();if(token==“+”
23、
24、token==“-”){F();T′()}elseif(!(token∈FOLLOW(T′)error();}F(){symtoken;token=getsym();if(token==“(”){S();token=getsym();if(token!=”)”er