1、编译原理（教案）课程名称：编译原理 授课内容：自顶向下语法分析方法LL(1)分析法 授课专业：计算机科学与技术 授课对象：本科三年级学生 授课时间：50 min 北京化工大学信息科学与技术学院史晟辉1一、教学内容（第 4 章 第 3 节）1语法分析方法的种类；2LL(1)分析法的基本步骤；3LL(1)分析法的算法；4语法分析方法的应用。二、教学目的1掌握 LL(1)分析法的算法； 2理解 LL(1)分析法的基本步骤；3了解自顶向下语法分析方法的基本原理；4培养学生运用所学的方法推导其它语法分析方法，并拓广到编译技术的应用，培养思考问题和解决问题的能力。三、教学重点1LL(1)分析表的构造；2L
2、L(1)分析过程验证源程序是否符合语法结构的过程。四、教学难点1First 集和 Follow 集的求解过程；2LL(1)分析法的分析过程验证源程序是否符合语法结构的过程。五、教学手段1课堂讲授为主。以课堂讲授为主要教学手段，适当穿插提问、思考等互动的教学方式；2多媒体演示。利用多媒体课件演示基本概念、分析过程、实例图等，使学生便于理解，加深印象，同时也加大了课堂的信息量；3板书。对内容提纲、重点过程进行板书讲解，有利于分析、比较、突出重点。4辅助网络教学。辅助编译原理课程教学网络及其它网络资源，延伸课堂教学，拓展知识，把握前沿，同时也促进师生交流和课程交流。2六、教学方法教师启发式教学、学生
3、开放式协同学习和阶梯式实践环节相结合的教学方法1教师启发式教学。教师课堂讲授的内容深入浅出，以实例引出理论，问题驱动内容，通过实例启发、对比启发等启发式教学方法，使原本过于抽象的内容生动化，促使学生积极思考，引发学生学习兴趣，提高学习效果。2学生开放式协同学习。引入“课堂 5 分钟” ，学生课上展示自己的作品，课下担当“辅导老师”营造出一个又一个辐射状的小讨论区氛围，学生中形成以点带面、多点带动多个面，辐射状开放式协同学习环境，使得课上的学习与课下的交流形成互补，激发学生学习的积极性，营造良好的学习氛围。3阶梯式实践环节。从课内实验到课程设计，实践环节的设计内容从易到难，开发规模从小到大，人员
4、也从个人到团队，形成阶梯式循序渐进实践环节。七、教学思路主线教学法。以自顶向下语法分析方法中的 LL(1)分析法为教学主线，实例证明，以线串点，讲解教学的基本内容和重点难点。八、教学进程（50min）教学要求 教学内容 教学方式时间(min)复习引题1 上节知识回顾（上下文无关文法）2上节与本节知识的衔接问题提问（编译过程出现过哪些错误？） 提问复习引出主题 1Chapter 4 Syntax Analysis4.1 The Role of the Parser4.2 Context-free grammars4.3 Top-down Parsing 4.3.1 Introduction4.3
5、.2 LL(1) Parsing3了解语法分析方法及其分类 演示：多媒体演示实际编程时出现错误提示的情况，引起兴趣。 问题一：这些错误提示是怎么得到的？能否自己编程对源程序查找出错误并给出相应的提示？用什么方法实现呢？ 引题：明确演示的内容：编译过程中的词法、语法和语义分析所得到的错误提示，进而引出研究的课题：语法分析方法。 Parsing 语 法 分 析 方 法Recursive-descent parsing递 归 下 降 法L(1) parsing()分 析 法Backtracking parsers回 溯 分 析 方 法Predictive parsers预 测 分 析 方 法LR(0
6、) parsingS(1) iLR() parsingA(1) arsingTop-down Parsing 自 顶 向 下 分 析 方 法则Z =*S, 则SL(GZ) 则 ()GZBotm-up Parsing 自 底 向 上 分 析 方 法则Z* ,则 First()Follow(A)= 无左递归； 消除左递归和左公共因子的方法 消除左递归 消除左公共因子 消除左递归和左公共因子的算法 Algorithm for General Left Recursion Removal:For i:=1 to m do For j:=1 to i-1 doReplace each grammar r
7、ule choice of the form Ai A j by the rule:Ai 1| 2 | | k, where Aj 1| 2| | k is the current rule for Aj. Algorithm for Left Factoring A Grammar:While there are changes to the grammar doFor each non-terminal A doLet be a prefix of maximal length that is sharedBy two or more production choices for AIf
8、thenLet A 1| 2| n be all the production choices for AAnd suppose that 1, 2, k share, so thatA 1| 2| k | K+1| n, the js share No common prefix, and K+1, n do not share Replace the rule A 1| 2| n by the rulesA A| K+1| nA 1| 2| k 例题求解 Example -_After Removal of the Left Recursion,exp term expexp addop
9、term expaddop +|-term factor termterm mulop factor termmulop *factor (expr) num 多媒体演示，引出问题 分析原因 讲解 讲解+辅助多媒体演示 结合算法讲解原理及方法，辅助多媒体演示算法执行过程。 板书借助板书讲解实例中消除左递归和左公共因子的求解过程。123217理解First集和Follow集的求解方法掌握算法2.2 First 集和 Follow 集 定义(1) First()=a | =*a, aV t, ,V* 若 =* ，则规定 First() 该集合称为 的首符号集合。(2) Follow(A)=a |
10、S=*A 且 aV t, aFirst(),V t*,V +,AV n 若 S=*A,且 =*，则 #Follow(A)该集合称为 A 的后继符号集合。 算法 Algorithm for Computing First(A) for All Non-Terminal A:For all non-terminal A do First(A):= ;While there are changes to any First(A) doFor each production choice AX 1X2Xn doK:=1; Continue:=true;While Continue= true and
11、k*a, where a is a token, then add Ato the table entry MA, a; （2）If Ais a production choice, and there are derivations =* and S$=*A a, where S is the start symbol and a is a token (or $), then add Ato the table entry MA, a; 例题求解 Example: Simple Arithmetic Expression Grammar exp term exp exp addop term exp exp addop + addop - term factor term term mulop factor term term mulop * factor (expr) factor num The LL(1) Parsing Table+ - * ( ) num $exp exp addop term term mulop factor 设问引出问题。 讲解结合算法讲解LL(1)分析表的定义和构造方法。 提示重点LL(1)分析表的构造为重点内容。 板书借助板书讲解实例中 LL(1)分析表的构造过程。1232重点
