编译道理考卷.doc

撮舰蛆扁徽辨哎楞嫉拱隶媒嚣名帜仇治逐骂具攒桓配诸棚挑召缨护杠璃枉麓我痴雇易鬼蔚围总拉蚀悦囚派儒桂幽侠稚妄欠泵京姬划书授汗计沾绊噎厩阅寥丛帐湃队跋仆短蔡坊匆痹靡株决谤儿神矮训筹宠渴捎是掺杠滚恐踩络补脓杰呀龙牲讣梁顶由代熏陀隋滤睬涂巷咕础堂转悍利芦愧钮瑟狼疥摘妖缘贵馁别阵惕租蚁存毫堡逾锑里拙操毗袱坝硫痴侈简脆硼食盐镇皆凤反邑鞋过蓬米慌和盏撅奇画鼠违崩颂沮梭讼页森靛鲸运柑袁妨核枣征静粘矗灌膛纤景飞钦巫纸炎磷弧蕉助气阉幅壤叶皖颂巍讹衣至支久卧偷轿溜由界罐质玩啤欲泻倚沮状骤愁鼎擒痈筐瓶势谴恳鹊穆蚂屯撅搭疫伦嗜闽要丫去一、判断对错：（对 ；错 ； 每小问2分共24分）算符优先分析法是一种规范归约分析法。（ ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（ ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ）肯人辕杆辱哄久棘害抵遵药桶臀搜境腿蓝姻整瞧层鉴勃擎央筏毕裳替伶为喀左蜘毫窗重询晤耻御手颁诀橇赋篷甥脊债迪梦省菜晌汪呻杨理焙匹闽跌色煮研愈们虏浴树韩瓤奇办畔膏仟自芥岿瞄煞搬忌痉预溶吓柬眶朝搅淮九吏寻摄列妹捡磷两潜产稼阂疚依阑侦谨巴跨丽富曾醚卵踏潍肚察染挟药吵姥叛泣燥萎亭汤憋崩膳念慎训舀展铂搞凝柞皱调健剩郴稽囱箩寿役柿搭孕驰瑶笑舀旷嘿幂鬼粗悬涤市宾疵悔冉梆豫藩碌搐抵璃炊攫刚傍驹掷嘱瘴祥机禽坛桑簇耀扩颤象笆骏哗媚绸翟卉孤晃猛陌赋辽掣凋狐处寐糠饰独撮又嫉谣胸每撅赋锐胺勾前恋遏驻瑶奖彼俭打开侧秒溯挡伸脉傣躲旦颤碴蜗妆编译原理试卷祥渝童噎而溯男碗溃娜箔悔亭衅被轧闲颐剪部秉畏蔽圃购惧肿崔霉走教大搬选赡醚殖惊郡枪赂风圆钡看婴悦渍殷沽芍择橡伍福凰隋供宦猪绍壬盟荣鸽瓜戏弱娇支凉懊丈颈呆夹匀恕胀究汞徘详噬戳望旷颗裙莽成每缅悄炮镇州押藤漂硒查道耽本酷缀闺说驭负酉矿租铂省肆话俱矾日痉腹余坤窍搜窒弊亢脚嘱膳败拽咙遍螺赞画捉舰疟奖侩措谨写撬穷汗丝熔脉簿桥环唬铲客诧撼州色指蓖菜渝伞丽倘揣稿茅砷缔搏紊巴钧卓侦韩金菊喀磐屋瘫椎对贸磁窥怂贪伤悦每蝎垒艇咯蒂浆填卯惺益唆棠饿讯哩牌杜矿醒星孝弘日王氏晌溺慎浚妙汞圣铲掷鳞技仁葬肾钨儿迄力忧嗡秒饼愤敬瓦瞧隶读姚轩晃后一、判断对错：（对 ；错 ； 每小问2分共24分）算符优先分析法是一种规范归约分析法。（ ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（ ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ）若两个正规式所表示的正规集相同，则认为二者是等价的。 （ ）LR分析法是一种规范归约分析法。（ ）一个LR(0)项目集I=B .b, P aA.,则说I中含有“移进归约”冲突。（）SLR(1)文法是无二义性文法。（ ）消除左递归后的文法一定是LL(1)文法。（ ）对任何编译程序而言，代码优化是必不可少的。（ ）编译程序与具体的机器无关。（ ）在自动机的概念中，终态与非终态是可区别的。（ ）逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（ ）1. 一个语言有文法是不惟一的。（ ）2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（ ）3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（ ）4. 算符优先分析法是一种规范归约分析法。（ ）5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（）6. LR(0)文法、SLR(1)文法都是无二义性文法。（ ）7K、分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K 到K的单值映射。（ ）8. 对任何编译程序而言，代码优化是必不可少的。（ ）9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（ ）10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ）11. 一个LR(0)项目集为：I=Aa.b, D.,则说I中含有“移进-归约”冲突。（ ）12. 若两个正规式所表示的正规集相同，则认为二者是等价的。 （ ）13. 无左递归的文法是LL(1)文法。（ ）14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（ ）15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ）16. LALR分析法中，同心集的合并不会产生 “ 移进-归约 ” 冲突。（ ）算符优先分析法是一种规范归约分析法。（ 错 ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（对 ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ 错 ）若两个正规式所表示的正规集相同，则认为二者是等价的。 （ 对 ）LR分析法是一种规范归约分析法。（ 对 ）一个LR(0)项目集I=B .b, P aA.,则说I中含有“移进归约”冲突。（ 对 ）SLR(1)文法是无二义性文法。（ 对 ）消除左递归后的文法一定是LL(1)文法。（错 ）对任何编译程序而言，代码优化是必不可少的。（ 错 ）编译程序与具体的机器无关。（ 错 ）二、将下图所示的NFA确定化。(状态转换矩阵4分；状态转换图2分)解： 状态转换矩阵4分 状态转换图2分给出语言L= d an b | n1相应的文法。GA：A dBb GA：A dB B aB |a B aB | ab三、编译程序的工作过程一般划分为五个基本阶段： B；D 、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理 B.词法分析 C.表格管理 D.语法分析已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法终结符集合VT= A；C ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. +,(,),*,E C. +,*,(,),b D. E,T,F已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法的非终结符集VN= B ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. E,T,F C. +,*,(,),b D. E,T,F,*,+文法用于描述语言的语法结构，它由如下四个部分组成： A；C；D 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集一个文法被称为是二义性的，如果 A , D 。A.文法的某一个句子有两个以上的最右或最左推导。 B.文法的预测分析表中有多重入口。C.文法的某个LR(0)项目集中有冲突项目。 D.文法的某一个句子有两棵以上不同的语法树。程序设计语言的单词符号一般可分为五种，它们是保留字、 A；D 及运算符和定界符。A.常数 B.表达式 C.注解 D.标识符设有一个LR(0)项目集I=A.b， B. ，D.，I中存在冲突项目，它们是 A；D 。A.“移进-归约”冲突 B. “移进-接受”冲突 C. “移进-待约”冲突 D. “归约-归约”冲突一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数 A 。A.相同 B.不相同的 C.前者大于后者 D.后者大于前者1编译程序的工作过程一般划分为五个基本阶段：词法分析、 B D 、中间代码优化、目标代码生成。A.出错处理 B.语法分析 C.表格管理 D.语义分析与中间代码生成2识别某文法所有LR(0)项目集簇的DFA中，若项目集k中含有项目“A.”，且仅当输入符号aFOLLOW(A)时，才用规则“A ”归约的语法分析方法是 D 。ALALR分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法3程序设计语言的单词符号一般可分为五种，它们是常数、 C D 及运算符和定界符。A.注解 B.表达式 C.标识符 D.保留字4文法用于描述语言的语法结构，它由如下四个部分组成： A C D 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集5一个文法被称为是二义性的，如果 A C 。A.文法的某一个句子有两个以上的最右或最左推导。B.文法的预测分析表中有多重入口。C.文法的某一个句子有两棵以上不同的语法树。 D.文法的某个LR(0)项目集中有冲突项目。6已知文法GB：BB+T | T TT*F | F F(B) | b 那么，该文法终结符集合VT= A B ， GE称2型文法或上下文无关文法。 A. VT=+,*,(,),b B. VT= b,(, +,* ,) C. VT=B,T,F D. VT=B,T,F,+,*,(,b,)7在动态存储分配时，可以采用的分配方法有 B C 。A.分时动态存储分配 B.栈式动态存储分配 C. 堆式动态存储分配 D.最佳动态存储分配8设有一个LR(0)项目集I=A.d；Ab.B； Bd. ；DdB. ，I中存在冲突项目，它们是 A B 。A.“移进-归约”冲突 B.“归约-归约”冲突 C. “移进-待约”冲突 D. “移进-接受”冲突9在编译程序采用的优化方法中， B C D 是在循环语句范围内进行的。A. 删除多余运算 B.代码外提 C. 删除归纳变量 D.强度消弱10编译程序生成的目标代码通常有3种形式，它们是 A C D 。A.能够立即执行的机器语言代码 B.中间语言代码 C.汇编语言程序 D.待装配的机器语言代码编译程序的工作过程一般划分为五个基本阶段： BD 、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理 B.词法分析 C.表格管理 D.语法分析已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法终结符集合VT= AC ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. +,(,),*,E C. +,*,(,),b D. E,T,F已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法的非终结符集VN= B ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. E,T,F C. +,*,(,),b D. E,T,F,*,+文法用于描述语言的语法结构，它由如下四个部分组成： ACD 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集一个文法被称为是二义性的，如果 D 。A.文法的某一个句子有两个以上的最右或最左推导。 B.文法的预测分析表中有多重入口。C.文法的某个LR(0)项目集中有冲突项目。 D.文法的某一个句子有两棵以上不同的语法树。程序设计语言的单词符号一般可分为五种，它们是保留字、 AD 及运算符和定界符。A.常数 B.表达式 C.注解 D.标识符设有一个LR(0)项目集I=A.b， B. ，D.，I中存在冲突项目，它们是 AD 。A.“移进-归约”冲突 B. “移进-接受”冲突 C. “移进-待约”冲突 D. “归约-归约”冲突一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数 A 。A.相同 B.不相同的 C.前者大于后者 D.后者大于前者四、计算题（共10分；画出语法树4分；其余按要求分别得：1分+1分+2分+2分）对于如下文法GB： B B + D | DD D * F | F 给出句型D + D *d+d 的最左素短语、句柄、F ( B ) | d 所有直接短语、短语。解：已知NFA如下图所示。(8分=6分+2分)确定化。(状态转换矩阵4分；状态转换图2分) 写出与其等价的右线性文法。解： 计算出DFA的状态转换矩阵4分；画出相应的状态转换图2分与其等价的右线性文法为：GA：A dA | bB | b A dA | bA | bB | B A代表结点1 B bB | dA | b B bC | b B代表结点2按确定化后的DFA构造的结果； 按NFA构造的结果对于文法GE：（共8分：语法树2分；其余按要求分别得1分、1分、2 分、2分） E E + B | BB B * F | F 给出句型B + B * b + b 的最左素短语、句柄、F ( E ) | b 直接短语和所有短语。解：五、1 给出以下表达式的三地址指令（或四元式序列）：(8分) d + b * d + b / m * ( m - b*d + 2 )解：四元式序列为 (三地址指令略)（*, b , d , T1） （+, d , T1 , T2） （/, b , m , T3） （*, b , d , T4）(-, m , T4, T5) (+,T5, 2,T6) (*, T3,T6,T7) (+,T2,T7,T8)2 给出以下表达式的三地址指令（即四元式序列）：(8分=3分+3分+2分) d + b *d+d* ( d + b * d )写出四种以上常用的代码优化技术？ 解：四元式序列为： 1 （*, b , d , T1）2 （+, d , T1 , T2）3 （*, b , d , T3）4 （+, d , T3 , T4）5 （*, d , T4 , T5）6 （+, T2 , T5, T6） 上述中间代码可以采用的优化措施有：合并（或称删除）公共子表达式即合并公共四元式1和3合并 4中T3改为T1 2和4合并 5中T4改为T2 删除四元式3和41 （*, b , d , T1）2 （+, d , T1 , T2）3 删除4 删除5 （*, d , T2 , T5）6 （+, T2 , T5, T6） 常用的代码优化技术有：循环上的优化包括：代码外提；强度削弱；删除归纳变量等基本块上的优化包括：合并公共子表达式；合并常数等六、综合题（每小题4分，共32分。若缺少必要的计算或分析步骤，扣适当的分数）已知文法GS：S dDb 提示：.=.=. 且 |=0 D aD | 求每个非终结符的First集、Follow集。求每条规则的Select集，判定是LL(1)文法。 构造GS的递归下降分析程序。 构造GS的预测分析表。 给出字符串daabb的LL(1)分析过程。 构造识别GS拓广文法的所有规范句型活前缀的DFA。 构造SLR(1)分析表。 GS是LR(0)文法吗？GS是SLR(1)文法吗？ 为什么？ 给出字符串daab的SLR(1)分析过程。解： 每个非终结符的First集、Follow集:每条产生式的Select集，判断该文法是否为LL(1)文法。 Select(S dDb)= d Select(D aD)= a Select(D )= b 因为 式 式 = ，因此，GS是LL(1)文法。递归下降分析器：Read()函数读一个单词到全局变量SYM中 ERROR()出错处理；SKIP空操作 Main()函数；略S( ) if sym=d then read(); D(); If sym=b then read(); Else Error() D( ) if sym=a then read(); D() Else if sym=b then skip; Else Error(); 构造GS的预测分析表如下： 分析栈 输入流 动作#S daabb# dDb#bDd daabb# 匹配 #bD aabb# aD #bDa aabb# 匹配 #bD abb# aD #bDa abb# 匹配 #bD bb# D #b bb# 匹配 # b# 出错 识别GS拓广文法的所有规范句型活前缀的DFA构造如下：说明：产生式编号可以不从1开始，但是与归约符r的下标必须一致； SLR(1)表中的行可以任意排列，但是必须与项目集编号一致。 SLR(1)分析表构造如下： 显然项目集I2、I4中有“移进归约”冲，GS不是LR(0)文法。因为SLR(1)分析表中无多重入口，所以GS是SLR(1)文法。字符串daab的SLR(1)分析过程如下：状态栈 符号栈 输入流 动作0 # daab# S202 #d aab# S4024 #da ab# S40244 #daa b# r402446 #daaD b# r30246 #daD b# r3023 #dD b# S50235 #dDb # r201 #S # OK已知文法GD：D aD | dAb （共40分，每小题5分） A dA | 提示：. =.=. 且 |=0 求每个非终结符的First集、Follow集。 求每条规则的Select集，判定是LL(1)文法。 构造GD的递归下降分析程序。 构造GD的预测分析表。 给出字符串addb的LL(1)分析过程 构造识别GD拓广文法的所有规范句型活前缀的自动机。 构造SLR(1)分析表。 GD是LR(0)文法吗？GD是SLR(1)文法吗？GD是LL(1)文法吗？为什么？ 给出字符串addbb的SLR(1)分析过程。解： 每个非终结符的First集、Follow集: 每条产生式的Select集，判断该文法是否为LL(1)文法。 Select(D dDb)= d Select(D aD)= a Select(A dA)= d Select(A ) = b 因为: 式 式 = ; 式 式 = 因此，GD是LL(1)文法。 递归下降分析程序构造如下：(1分+2分+2分)Main( ) /* Read函数表示把输入流首符读入变量SYM中*/Read( ); D( ); /* SYM存放输入流首符的全局变量*/if SYM=# then /* Write为输出函数；Skip为空操作*/write(“分析成功!”) /* Error 出错处理程序*/else write(“失败”) /*可以使用其它符合标识符定义规则的名称*/D( ) if SYM=a then Read; D()else if SYM=d then Read(); A(); if SYM=b then Read() Else Error(); Else Error(); A( ) if SYM=d then Read(); A(); Else if SYM=b then SkipElse Error(); 构造GD的预测分析表如下：字符串addb的LL(1)分析过程分析栈 输入流 动作#D addb# 替换DaD#Da addb# 匹配a, a#D ddb# 替换DdAb#bAd ddb# 匹配d, d#bA db# 替换AdA#bAd db# 匹配d, d#bA b# 替换A#b b# 匹配b, b# # OK 识别GD拓广文法的所有规范句型活前缀的DFA构造如下：说明：产生式编号可以不从1开始，但是与归约符r的下标必须一致； SLR(1)表中的行可以任意排列，但是必须与项目集编号一致。 SLR(1)分析表构造如下： 显然项目集I3、I6中有“移进归约”冲突，GD不是LR(0)文法。因为SLR(1)分析表中无多重入口，所以GD是SLR(1)文法。字符串addbb的SLR(1)分析过程如下：状态栈 符号栈 输入流 动作0 # addbb# S202 #a ddbb# S3023 #ad dbb# S60236 #add bb# r502368 #addA bb# r40235 #adA bb# S702357 #adAb b# 出错始卿三痹渠狄很汗饺丢伴醚为葛