编译原理第4章测试卷_0

1、编译原理第4章测试卷 编译原理 xxxx年第二学期第四单元测试试卷 （闭卷考试） 时间：45分钟 满分：100分 姓名 班级 出题人 班级 软件12-4 题目 一 二 三 四 五 总分 得分 一、选择题（5*2分）（每题1分，共10分） 1. 下列文法中，_是ll(1)文法。 a. sasb|ab b. sab|sab c. sas|b d. sas|a 2. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于 分析法。 a. 自左至右 b. 自顶向下 c. 自底向上 d. 自右向左 3. 自上而下分析面临的四个问题中，不包括 。 a. 需消除左递归；b. 存在回朔；c. 虚假匹配；d.

2、 寻找可归约串 4. 语法分析器接收以_为单位的输入，并产生有关信息供以后各阶段使用。 a. 表达式；b. 产生式； c 单词；d. 语句； 5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号（根结点）出发，_。 a. 为输入串寻找最右推导； b. 为输入串寻找最左直接子树； c. 为输入串建立最右直接子树；d. 为输入串寻找最左推导； 二、简答题（2*10分）（每题10分，共20分） 6. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？ 7. 为什么要消除回溯？ 三、分析题（4题共70分） 8.设有文法gs： sab abb|aa bsb|a 试消除

3、该文法的左递归。（15分） 9.已知文法ge： ge：ee+t|t tt*f|f fi|(e) 请按递归子程序法为其构造语法分析程序。（20分） 10文法gm是否是ll(1)文法，说明理由。（gm：mtb tba| bdb|et| dd| 15分） 11. 已知文法gs： s ubdz b br | w d ef e y | ? f x | ? (1) 求每个非终结符的first和follow集。 (2) 构造这个文法的ll(1)分析表 (3) 说明这个文法不是ll(1)的; (3) 尽可能少地修改此文法,使其成为能产生相同语言的ll(1)文法.（20分） 第四章答案 1-5 b d d c

4、d 6. 答：词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子。词法分析的一个输入符号串是由单个符号组成的单词；语法分析的输入符号串是由词法分析得来的单词组成的句子。 7. 假定当前轮到非终结符a去执行匹配任务，a共有n个候选?1、?2、?n，这时候该用哪一个候选去替换a，原始的办法是采用对所有候选采取“试探”的方法。如果某个候选不成功就需要“回退”。这个回退的过程会导致前次匹配的许多工作推到重来，效率低。而且，最终匹配不成功的时候，难以直到输入串中出错的确切位置。 8.解：本题考查消除左递归的方法。 应用消除文法左递归的算法对文法gs消除左递归的过程如下： （1） 将非终结符

5、排序为：u1=s，u2=a，u3=b （2） 进入算法排序： i=1时，对文法无影响 i=2，j=1时：aaa有直接左递归，消去该直接左递归，得 abba aaa| i=3，j=1时：改写文法，有 babb|a j=2时：改写文法，有 bbbabb|a无左递归。 （3） 所以文法gs消除左递归后变为： gs：sab abba aaa| bbbabb|a 9.解：本题考查递归子程序的构造方法。 本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。 因为文法只有左递归，采用扩充的bnf范式消除文法左递归得到： ge：et+t tf*f fi|(e) 然后再应用书中介绍的方法即可求解。 假定用“advanc