资源描述：
《太原师范学院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
