《编译原理》第四章试题.doc

编译原理 2014—2015学年第二学期第四单元测试试卷 （闭卷考试） 时间：45分钟 满分：100分 姓名　　 　 班级　　　　　　 出题人 刘兵 班级 2 题目 一 二 三 四 五 总分 得分 一、选择题（5*2分）（每题1分，共10分） 1．A．无穷个? B．不确定???C．有限个???D.根据具体情况而定? 4．语法分析器则可以发现源程序中的__D___。 A． 语义错误 B． 语法和语义错误 C．错误并校正 D． 语法错误 5．若文法?G?定义的语言是无限集，则文法必然是( )????????????。?? A．递归的????? ???B．前后文无关的?????? C．二义性的????? ?D．无二义性的?? 二、简答题（2*10分）（每题10分，共20分） 1．自上而下分析的前提？ 2.若有文法A→(A)A|ε，说明该文法是LL(1)的文法。 三、分析题（4题共70分） 设有文法G[E]: E→Aa|Bb A→cA|eB B→bd 试按照递归子程序法为该文法构造语法分析程序。 设有文法G[S]： S→AB A→bB|Aa B→Sb|a 试消除该文法的左递归。 3.计算练习4.2.2的文法的FIRST和FOLLOW集合 (1)S-S(S)S|ε (2) S-(L)|a, L-L, S|S? ? 4. 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。 编译原理 2014—2015学年第二学期第四单元测试试卷答案 一、选择题 1—5 B、B、D、D、A 二、简答题（2*10分）（每题10分，共20分） 1 .解：消除左递规和消除回溯。 2. 解：该文法不含左递归； FIRST（(A)A）={(}，FIRST（ε）={ε}，FIRST（(A)A）∩FIRST（ε）=Φ， 且FOLLOW(A)＝｛)，#｝，FIRST（(A)A）∩ FOLLOW(A) =Φ， 因此，该文法满足LL(1)文法的条件，是LL(1)文法。 三、分析题（4题共70分） 1. 解：本题考查递归子程序的构造方法。 首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。 因为： （1） 该文法无左递归。 （2） 文法的产生式E→Aa|Bb和A→cA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。 对产生式E→Aa|Bb，有 FIRST(Aa)∩FIRST(Bb)={c，e}∩{b}=? 对产生式A→cA|eB，有 FIRST(cA)∩FIRST(eB)={c}∩{e}=? 文法中其他产生式都只有一个非空ε的右部。 综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。 下面为该文法的每一个非终结符号构造递归子程序。 假设用READAWORD代表读下一个单词。用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。约定输入符号串以“#”作为输入结束符。 P(E)的递归子程序为： PROCEDURE P(E); BEGIN IF WORD IN FIRST(Aa) THEN BEGIN P(A); READAWORD; IF WORD=’a’ THEN READAWORD ELSE ERROR END ELSE IF WORD IN FIRST(Bb) THEN BEGIN P(B); READAWORD; IF WORD=’b’ THEN READAWORD ELSE ERROR END ELSE ERROR END; P(A)的递归子程序为： PROCEDURE P(A); BEGIN IF WORDD=’c’ THEN BEGIN READAWORD; P(A) END ELSE IF WORD=’e’ THEN BEGIN READWORD; P(B) END ELSE ERROR END; P(B)的递归子程序为： PROCEDURE P(B); BEGIN IF WORD=’b’