编译原理2010-2011试卷A(答案).doc

华东交通大学2010—2011学年第二学期考试卷 　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（　A　）卷 编译原理（E） 课程 课程类别：必修课 闭卷（√）、开卷( )（仅限带教材）：　　考试日期：2011.6.14 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 100 得分 考生注意事项：1、本试卷共 7 页，总分　100　分，考试时间　120　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 得分 评阅人 一、简答题 (每题 5 分，共 20 分) 　 简述编译程序与解释程序的主要差异？ 【答】 编译程序产生中间代码，且效率高； 解释程序不产生中间代码，且效率低。 文法的二义性与语言的二义性是两个相同的概念吗？请说明理由。 【答】这两个概念是不相同的。文法的二义性指的是文法所描述的语言中至少存在一个句子，而该句子对应两棵不同的语法树（或最左（右）推导）；而语言的二义性是指描述该语言的全部文法都是二义性的。 由于描述同一个语言的文法可以有多个，一个二义性文法也可能找到一个等价的无二义性文法，所以一个文法是二义性的，其描述的语言不一定就是二义性的。 简述在句型分析中的自上而下与自下而上两类分析方法的主要差异？ 【答】自上而下的分析方法是从文法的开始符号出发，反复使用推导技术，试图把要分析的句型推导出来；自下而上的分析方法是从要分析的句型出发，反复使用归约技术，试图最终归约出文法的开始符号。 为什么说“素短语是包含有终结符的直接短语”的论断是错误的？并针对文法G[E]： (1) E→E+T | T (2) T→T*F | F (3) F→i 中的句型T+T+F，举一个反例加以进一步说明。 【答】 在一个文法的句型中，其素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。而不是说是一个直接短语。 例如：文法G[E]中的句型 T+T+F，其一个素短语为：T+T，而T+T是素短语，但不是直接短语。 二、形式文法与自动机题(共 20 分) 　　 得分 评阅人 请给出生成下述语言L的上下文无关文法：（5分） L={ aibjajbi | i＞0，j≥1 } 【答】描述该语言的文法G[S]为： S→aAb |ε A→bAa | ba 对文法 G[E] : E→A│E+A │E–A A→B│A*B B→(E)│a 写出句型B-(E)*a 的短语、直接短语和句柄。（5分） 【答】该句型的对应的语法树如下： 故其短语、直接短语和句柄分别为： 短语：B；(E)；a；(E)*a；B-(E)*a 直接短语：B；(E)；a 句柄：B 设计一个最小状态数的DFA，其输入字母表是{0，1}，它能接受以以01结尾的所有由0和1组成的符号串。（10分） 【答】该语言用正规式表示为：(0|1)*01 或 (1|0)*01 识别该语言的FA为： 0 0 1 1 对该FA进行确定化： 0 1 {A} {A,B} {A} {A,B} {A,B} {A,C} {A,C} {A,B} {A} 令，T1代表{A}，T2代表{A, B}，T3代表{A,C}，则等价的DFA为： 1 0 0 1 0 1 由于f(T1,1)=T1，f(T2,1)=T3，而T1是非终态，T3是终态，所以T1和T2不等价，故此，该DFA即为最小状态数的DFA。 三、语法分析题(每题 10 分，共 30 分) 　　 得分 评阅人 1. 给定文法G[S]: S→AaAb│BbBa A→ε B→ε 证明该文法是LL(1)文法，但不是SLR(1)文法。 【答】 计算First集和Follow集 First(AaAb)={a}; First(BbBa)={b}; Follow(S)={#}; Follow(A)={a，b}; Follow(B)={a，b}; 计算各产生式的SELECT集： SELECT(S→AaAb)={a}│ ； SELECT(S→BbBa)={b} SELECT(A→ε)={a，b} SELECT(B→ε)={a，b