班 业 专 级 院 学 号 学 名 姓 … … … … … … … … … … … … … … … … … … … 线 … … … … … … … … … … … 订 … … … … … … … … … … … 装 … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … 答 … … … … … … … … … … … 题 … … … … … … … … … … … 线 … … … … … … … … … … … … … … … … … … … 西华师范大学学生试卷 得分 阅卷人 2013 年 月 日 第 1 期 共 页 考室 题号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师 得分 数学与信息学院 信息与计算科学专业 2010 级 9、10 班《编译原理》试题 B 卷 闭卷考试 时间 120 分钟 注意事项：1.满分：100 分。保持卷面整洁，否则扣卷面 2 分。 2.交卷时请将试题卷与答题卷一起交，否则扣分。 3.学生必须将姓名、班级、学号完整填写在规定的密封栏目内。否则视为废卷。 4.学生必须签到，否则出现遗漏由学生本人负责。 得分 阅卷人 一、计算题(共 32 分) 1、(9 分)给定文法 G(E): E→-EE E→+E E→a E→b E→c (1,3 分) 请写出句子“-+a-bc”的最左推导过程； (2,3 分) 画出上述句子的语法树； (3,3 分) 指出上述句子的短语、直接短语和句柄。 2、(10 分) 构造一个 2 型文法 G，使得 ( L G )   n n i a b c n |  1, i 3、(9 分) 回答下列问题。 (1,5 分) LL(1)文法中的两个“L”各指什么？“1”指什么？ (2,4 分) 什么是算符文法，什么是算符优先文法？ 4、(4 分)给出下列各式的后缀式。 (1,2 分) (a+b)*(b+c) (2,2 分) (a-(-b))/((-b)*a)  （不包括空产生式）。  0 二、词法分析(共 28 分) *) 给定正规式： ba ( a | 1、( 8 分) 根据上述正规式构造 NFA； 2、(12 分) 将第一步得到的 NFA 确定化为 DFA； 3、( 8 分) 将第二步得到的 DFA 最小化。 得分 阅卷人 三、语法分析(共 40 分) 1、(21 分) 设有文法 G(S）： S→SbA | aB B→Bb | c A→Ac | b (1,6 分) 计算每个非终结符的 FOLLOW 和 FIRST 集合； (2,5 分) 消去该文法的直接左递归并形成一个新文法 G( S )； (3,3 分) 计算 G( S )每个非终结符的 FOLLOW 集合； (4,3 分) 计算 G( S )每个候选式的 FIRST 集合； (5,4 分) G( S )是 LL(1)的吗？请说明理由。 2、(19 分)给定文法 G(S)： S→(A) A→ABB | B B→b | d (1,15 分) 构造该文法的 LR(0)项目集规范族；（注意写清步骤） (2, 2 分) 该文法是 LR(0)文法吗？为什么？ (3, 2 分) 该文法是 SLR(1)文法吗？为什么？