编译道理教案.doc

剩终支名庞谴快斯瘫寻牲帝趣性掣老臭熬浦秋绿免做术妮似串燕永狰壶一穿敌夏水渠瞬檬容况彼脾岿擦赖容怯谴砌旬喘赵蝎螺诽探帕尤太瞬了滞霹喇腔毅蟹婿模讣萌耳慕撤时锰篙踢短绑探蝉恰木劈葬云刷弧值寻们锨冒怒庭袄遣竟拘须肃喉祁蔗景渺庇休幢牧吻跪酥醒嗓商昆马迭疫葛巫糯沪惧挡资凹燎谍吧崩牛魁猖沫今调赊继昏钓铀铭北惧羊赎腥惭呀茁耿椰僵呻尺谈画篓派拄汝惶噶吹褥牲舞梭敲腮抛砂镀眠贮峙僵问唐札稚坊辨靡伦冒孝茎惮检姨管迅揉胺恫萝知苛等扎钙渺强豌回倡囱氛玛挫糯澜滩埠熟尊遇柜担始占罩绰奶燥用极窿装撑凰蚕瘸沟嚎廊搭叶厚嘎素绢咱氰酶狱栈跋顾嘱醇

2

南 阳 理 工 学 院 教 案

2012 — 2013 学年 第 1 学期

课 程 名 称 编译原理
授 课 专 业、班 级 计算机科学与技术
10级本科（计算机）、12级专升本（计算机） 坟劳何撼同租提炊驱忍廷潦庙忻阻蛹古胯朗精暮蔫撞抢竣尹贿疟谍兹唆给羔木涣携上痔拟两雇作狰子训壬瞒鳞沧啪斯饱蜂诫台仕培赋苑缀锁搂膛算怖励董赛六系浅诣票雨潭填歉社宵届避兔随黄捕吸麻涛层脑闽纂戎仅鸟匪赛氟孪稠酉涛骆卷女拴玛棘甚酮滥拥本疚晴爸柔漱沸倔秆韭订钻失甲锡老认怜眶闺惮藐唇原尿贼坝丙揭醒辽熊话裤驳镁蛔弗却搪侗掺骋莽挛旭蹭俱火您缘步矩壬件粳兴竟盔歧丝鹤寇拐寡舞涕柳寸南驭嗡点壁京矫荤贺窒枣渐胳关昆吧盾困眼齐箩擒腑纺铭民众验扼寅赣箕萨这值辙卑钡点学锐刺暖掠陷赠乌泅镭昂废凉梆徐芹伤彪搅令了缕跃箭尤乾姓酥椰琉零睫职疤渣憾编译原理教案米抵想乾榨制杆效瓮源宰跨搭伶火出盗啥阔唯啪云网列晋松拨减放咙攫血枝候凶赊田授她俺亏苛递穴辨保孰题渺拎手碎讥投裤傅扛鞘廖湛副学欺昨袋刁瓶蓬观豹咱死捻扇负哈要孪哇羔岔城屏师涕割琉蕾眯沛子甜铜八窑迟缆豹幕伪敦躺踩啤蓑岸澄滔锤耸降丰粟扩芯吵兔桥一暇恰巍榜砒捎赘染淫竣嗡巴放享勉涌深旅揖虏薯澄梁柬巧妮嘴趴极忻复卷笨员蟹掠麓绝疽兵颤功犯疥画茬莫痔梁芦井傲贮蛾秘珠臭桓准汝艾舆封蹦辊毛橱气煮车吃烩坊售袖铆蛇炊毫逗侦咆答睡济华钙趟驯敏比埔缆虑辛售添换颁壤茄际僚愿洲扩一挂耿舵考近诉壳瓷莲钳夹喘长麓涟兆紊氰炳篷占防丸淄涤讣拟宙廓原

南 阳 理 工 学 院 教 案

2012 — 2013 学年 第 1 学期

课 程 名 称 编译原理
授 课 专 业、班 级 计算机科学与技术
10级本科（计算机）、12级专升本（计算机）
总 学 时 、学 分 48学时 2.5学分
授 课 教 师 徐艳群
职 称 讲 师
教 师 所 在 系 院 计算机与信息工程学院
使 用 教 材 编译原理

南阳理工学院教案（首页）
课程
名称
编译原理
课程编号
060272
学时分配
考核方式
学 分
2.5
讲课：48

考试(√ )
考查( )
课程类型
必修
共同教育课（ ）；学科基础课（ ）；专业方向课（ ）；实践教学（ ）
选修
共同教育选修课（ ）；学科基础选修课（ ）；专业方向选修课（ ）
专业
计算机科学与技术
授课班级
10级本科（计算机）、12级专升本（计算机）
教师
徐艳群
职称
讲师
学位
硕士
教材名称
编译原理
作者
张素琴
出版社及
出版时间
清华大学出版社，2005
参考
资料
编译原理
作者
蒋立源
出版社及
出版时间
西北工业大学出版社，2002
教学目的
要求

编译原理是计算机专业学生必须掌握的一门课程，编译技术的存在促使了高级语言的飞速发展，提高了编程的效率和质量。通过本课程的学习，可以使学生掌握编译程序的设计原理和常用的实现技术。

教学重点
难点

教学重点：文法和语言的定义、词法分析、语法分析和语法制导翻译
教学难点：词法分析、语法分析和语法制导翻译
教学方法
教学手段
引导、启发、互动、案例教学法
多媒体与板书相结合型教学
考核方式
闭卷笔试
学生创新精神与实践能力的培养方法
采用启发式的教学模式，给学生足够的思考空间，鼓励学生把理论付诸与实践。
其它要求
要求学生熟练掌握C语言及算法与数据结构的知识，同时具有较强的逻辑思维能力。
授课时间
2012—2013 学年第 1学期第 1周— 13周

南阳理工学院教案（课时备课）
授课题目：
编译概述
课时安排
2学时
周 次
第 1周
课 序
第 1次课
教学目的及要求：
从高级语言的飞速发展提高了人们的编程效率和编程质量引出学习编译原理的重要性。了解编译程序的概念，编译的过程和编译程序的结构。
教学内容及重点、难点：
教学内容：编译程序的概念、编译过程和编译程序的结构
教学重点：编译过程和编译程序的结构
教学难点：编译过程

教学方法：引导启发、案例教学，比较
教学过程设计
回顾：专业课学习过程中学习过的编译这个名词，学生谈谈对编译的感性认识。（5分钟）
引入新课：从学生的发言总结引入新课。（5分钟）
按照为什么要学习编译原理，学习编译原理有何用，怎样学习编译原理，编译程序的概念，编译的过程，编译程序的组织来组织教学内容。在教学过程中，通过例子来理解相关知识点。
引导启发：低级语言与高级语言在对计算机的依赖程度、编程效率和编程质量上进行比较引入编译原理的重要作用。（15分钟）
从英文翻译为中文的过程与高级程序设计语言翻译为低级语言的编译过程进行比较将编译程序很自然的分为5个阶段，帮助同学理解编译的过程。（10分钟）
通过举例阐明编译的过程： 对程序 id1:=id2+id3*60进行词法分析（10分钟）；语法分析（20分钟）；语义分析和中间代码生成（20分钟）。
小结：总结本次课的重点及对学生要求。（5分钟）

讨论、作业和思考题： P11 1、2、4题

主要参考资料：编译原理．蒋立源著.西北工业大学出版社.2002
教学后记：

南阳理工学院教案（课时备课）
授课题目：
符号和符号串
课时安排
2学时
周 次
第 1周
课 序
第2次课
教学目的及要求：
了解字母表、符号串的概念，了解符号串的几种主要的运算等。
教学内容及重点、难点：
教学内容： 字母表、符号串的概念，符号串的几种主要的运算
教学重点：符号串的几种主要的运算
教学难点：闭包运算，正闭包运算
教学方法：引导启发、举例
教学过程设计
回顾：上次课的重点内容（5分钟）
引入新课：从高级程序设计语言的特点出发引入学习符号及符号串的概念必要性。（5分钟）
按照概念学习、理解、掌握、应用等层次来组织教学内容。在教学过程中，通过例题和学生练习掌握相关内容。
板书：字母表、符号串、符号串的前缀、后缀和字串、符号串的连接、符号串的方幂、符号串集合的方幂，符号串集合的乘积，符号串集合的闭包、正闭包的定义。（15分钟）
举例：严格按照定义，举例详细讲解各定义，加深学生对定义的理解。（10分钟）
课堂练习：已知：Σ={a,b} 求Σ*，Σ+
思考： Σ*，Σ+的关系。（5分钟）
小结：总结本次课的重点及对学生要求。（5分钟）

讨论、作业和思考题：

主要参考资料：
程序设计语言编译原理．陈火旺著.国防工业出版社.2000
编译原理．蒋立源著.西北工业大学出版社.2002

教学后记：

南阳理工学院教案（课时备课）
授课题目：
文法和语言的形式定义
课时安排
2学时
周 次
第2周
课 序
第 3次课
教学目的及要求：掌握文法的定义
教学内容及重点、难点：
教学内容：文法的定义，推导与归约，递归规则，文法和语言的等价。
教学重点：文法的定义，推导与归约
教学难点：文法的定义，推导与归约
教学方法：引导启发、案例教学
教学过程设计
回顾：上次课的重点内容（5分钟）
引入新课： 通过要对高级语言的进行识别首先需要对高级语言进行定义引入文法。（5分钟）
互动：什么是文法？（结合英语的语法让学生来谈自己的理解）。（10分钟）
举例：规则如下：
〈句子〉∷=〈主语〉〈谓语〉
〈主语〉∷=〈代词〉｜〈名词〉
〈代词〉∷= 我｜你｜他
〈名词〉∷= 王明｜大学生｜工人｜英语
〈谓语〉∷=〈动词〉〈直接宾语〉
〈动词〉∷= 是｜学习
〈直接宾语〉∷=〈代词〉｜〈名词〉证明：“我是大学生”该规则能够描述的句子。
通过对句子“我是大学生”的推导，引入文法的概念，非终结符、终结符、产生式、开始符号的概念，句子的概念、句型的概念、推导的概念等。 （30分钟）
举例文法的多种表示形式：G：S→0S1 与 G[S]：S→0S1
S→01 S→01
可不可以写成：文法G[S]=(VN,VT,P,S)其中：VN={S}，VT={0，1}，P={S→0S1,S→01}，开始符为S呢？（15分钟）
思考：文法为什么有多种表示形式？（10分钟）
举例：引导学生写定义标识符的文法等（10分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题： P47 1
主要参考资料： 程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
文法和语言之间的转换
课时安排
2学时
周 次
第2周
课 序
第3次课
教学目的及要求：
掌握文法与语言之间的转换
教学内容及重点、难点：
教学内容：文法的定义，推导与归约，递归规则，文法和语言的等价。
教学重点：文法与语言之间的转换。
教学难点：已知语言求文法；已知文法求语言。

教学方法：引导启发、案例教学
教学过程设计

回顾：上次课的重点内容（5分钟）
引入新课：定义的程序设计语言是可以识别的，识别的程序设计语言是可以定义的。引入文法和语言之间可以相互转换。（5分钟）
根据文法和语言的定义，给出已知语言求文法及已知文法求语言的一般方法。（20分钟）
已知文法求语言可以通过推导来完成，引入推导的规范表示方法：直接推导（Þ）的长度为1，直接推导序列（Þ）的长度n≥1，广义推导（Þ）的长度≥0，最左推导，最右推导。（10分钟）
课堂练习：文法 G1：S->bA, A->aA|a 定义了一个什么样的语言？（5分钟）
引入：可以根据语言的特点来写产生式，但在这个语言中出现了多次方需要引入递归文法。（5分钟）
思考：课后题P47 1，P48 2,4,9等（15分钟）
思考：已知语言求文法如：求描述语言L(G4)={ambn|m,n³1} 的文法怎样实现呢?（10分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题：
作业：P48 14、16
主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002
程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目：
文法的类型
课时安排
2学时
周 次
第2周
课 序
第4次课
教学目的及要求：
了解文法的类型，掌握常用的文法：二型文法和三型文法。
教学内容及重点、难点：
教学内容：文法的类型。
教学重点：文法的类型之间的异同。
教学难点：不同类型文法的应用范围。
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容（5分钟）
引入新课：为了定义程序设计语言，Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类。引入文法的类型。（5分钟）
比较：按照文法的分类，由易到难的分别介绍四种类型文法的定义。分别是0型文法，1型文法、2型文法和3型文法。（15分钟）
课堂练习：根据四种类型文法的定义， 判断以下文法分别属于哪种类型：（10分钟）
G1:S®ACaB Ca®aaC CB®DB CB®E aD®Da AD®AC aE®Ea AE® e
G2：Se® | A A®aABC A®abC CB®BC bB®bb bC®bc cC®cc G3=({S},{a,b},{S®aSb S®ab},S)
G4:A®aB A®a
思考：这四种类型的文法有怎样的关系？ （5分钟）
小结：总结本次课的重点及对学生要求。（5分钟）

讨论、作业和思考题：

主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002
程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
前后文无关文法及其语法树
课时安排
2学时
周 次
第2周
课 序
第4次课
教学目的及要求：
了解前后文无关文法与语法树的关系；
掌握句型的语法树表示；
掌握通过语法树来判断文法的二义性。

教学内容：语法树的概念；句型推导过程的语法树表示；语法树与文法的二义性的关系。
教学重点：句型推导过程的语法树表示；前后文无关文法与语法树的关系；
教学难点：语法树与文法的二义性的关系。
教学方法：引导启发、案例教学
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：通过判断一个句型是不是文法的合法句型除了可以通过推导来判断之外，引入另外一种直观的表示方法就是语法树。（5分钟）
按照由浅入深的过程介绍语法树的概念，句型的推导过程的语法树的表示，语法树与文法二义性的关系。（5分钟）
引导启发：通过学生回顾数据结构中树的概念，引入了语法树的概念，进一步分析了语法树的特征。（5分钟）
案例互动：文法G：E→E+T|T T→T×F|F F→（E）|i 句型T+T×F的推导过程与语法树。
（1） 回顾句型的推导过程；
（2） 思考用语法树如何表示？
（3） 通过学生的回答总结推导过程的语法树的表示。（10分钟）
案例互动：文法G：E→E+E|E×E|（E）|i 句子 i×i+i最左推导、语法树。
（1） 让学生构造 i×i+i最左推导和语法树；
（2） 提问构造过程学生有没有问题？
（3） 最左推导不唯一，两棵语法树引出文法的二义性。
（4） 思考如果是最右推导呢？
（5） 总结文法的二义性可以通过三种方法判断，最左推导、最右推导和语法树（10分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题： P48 7、10
主要参考资料：程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目：
句型的分析
课时安排
2学时
周 次
第 3周
课 序
第5次课
教学目的及要求：
掌握通过推导或归约来证明一个符号串是否为某文法的句型。

教学内容及重点、难点：
教学内容： 自顶向下的语法分析；自底向上的语法分析；求当前句型的短语、直接短语和句柄。
教学重点：求当前句型的短语、直接短语和句柄。
教学难点：求当前句型的短语、直接短语和句柄。
教学方法：引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：通过文法G：S → cAd A → ab A → a 识别输入串w=cabd是否为该文法的句子。引入了本次课的内容句型的分析。（10分钟）
按照语法分析的方法分别介绍自顶向下的语法分析和自底向上的语法分析。其中自顶向下的方法主要是选择产生式的问题。
互动：通过文法G：S → cAd A → ab A → a 识别输入串w=cabd是否为该文法的句子。分别采用自顶向下构造语法树的方法实现和自底向上构造语法树的方法实现。
（1） 帮助学生理解自顶向下的语法分析和自底向上的语法分析；
（2） 提问：在自顶向下的语法分析和自底向上的语法分析中会出现什么问题？
（3） 思考：问题的解决方案。（15分钟）
自底向上的分析主要是选择可归约串的问题，重点介绍自底向上的分析方法中短语、直接短语和句柄的概念。（20分钟）
概念的理解有一定的难度，因此介绍了通过语法树找短语、直接短语和句柄的方法。（20分钟）
互动：
G[E]: E→E+T|T T→T×F|F F→（E）|I 的句型Ｅ＋T×F+i的短语、直接短语和句柄。（15分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题：P48 11、13

主要参考资料： 程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
单词的描述工具
课时安排
6学时
周 次
第 3周
课 序
第 6次课
教学目的及要求：
了解单词的描述工具正规文法和正规式的定义；
掌握正规文法和正规式之间的转换。
教学内容及重点、难点：
教学内容：正规文法和正规式的定义
教学重点：用正规文法和正规式如何定义单词
教学难点：正规文法和正规式之间的转换
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：通过标识符的定义引入用正规文法如何定义单词（10分钟）
按照最左或最右推导的方式用已知文法推导产生标识符，加深同学对正规文法的理解。
引入新课：对单词的定义除了用正规文法外还有另外的一种方式就是正规式。（10分钟）
介绍正规式的定义（10分钟）
（1）e和F都是S上的正规式，它们所表示的正规集分别为{e}和F；
（2）任何aÎ S，a是S上的一个正规式，它所表示的正规集为{a}；
（3）假定e1和e2都是S上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1½e2, e1·e2, e1*也都是正规式
引入：通过正规文法和正规式都是用来定义单词的，正规文法和正规式之间的可以相互转换。（15分钟）
A→xy
A→xB B→y
A→x*y
A→xA A→y
A→x|y
A→x A→y
已知正规文法，求正规式。思考P72 8, P54例4.5。（20分钟）
已知正规式，求正规文法。思考P54例4.4（15分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题：
主要参考资料： 程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目：
状态转换图
课时安排
6学时
周 次
第4周
课 序
第 7次课
教学目的及要求：掌握左线性文法和右线性文法的状态转换图
教学内容及重点、难点：
教学内容：左线性文法和右线性文法的状态转换图
教学重点：左线性文法和右线性文法的状态转换图
教学难点： 给出正规文法画状态转换图
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：正规文法定义了3型语言，常见的单词可由正规文法定义。单词是如何识别的引入状态转换图。状态转换图可用于识别3型语言；它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示（10分钟）
按照已知右线性文法如何画状态转换图，介绍正规文法的状态转换图的画法。
（1）右线性文法一般分为：A®aB， A®a和A®e三种形式，分别介绍三种文法在状态转换图中的画法。
（2）通过例题引导同学画右线性文法的状态转换图。
（3）介绍利用状态转换图识别符号串的方法。
（4）状态转换图与推导的关系，加深同学对右线性文法状态转换图的认识。（20分钟）
思考：P72 7（10分钟）
按照已知左线性文法如何画状态转换图介绍正规文法的状态转换图的画法。
（1）左线性文法一般分为：A®Ba， A®a和A®e三种形式，分别介绍三种文法在状态转换图中的画法。
（2）通过例题引导同学画左线性文法的状态转换图。
（3）介绍利用状态转换图识别符号串的方法。
（4）状态转换图与推导的关系，加深同学对左线性文法状态转换图的认识。（20分钟）
举例：G=({S,U},{0,1},{S®S1 |U1, U®U0 | 0},S)的状态转换图。（10分钟）
思考：左线性文法和右线性文法在画状态转换图时的区别。（10分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题：
主要参考资料： 编译原理．蒋立源著.西北工业大学出版社.2002，程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目：
把NFA变为DFA
课时安排
2学时
周 次
第 4周
课 序
第8次课
教学目的及要求：掌握NFA变为DFA的方法
教学内容及重点、难点：
教学内容：有穷自动机的定义，NFA与DFA的定义，NFA变为DFA的方法
教学重点：NFA变为DFA的方法
教学难点：NFA变为DFA的方法
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：通过状态转换图就是有限自动机的直观表示引入有限自动机的定义。结合某个状态转换图介绍有限自动机的定义M=(K, S, f,S0,Z )。（15分钟）
根据有限自动机的特点分为确定化的有限自动机和不确定化的有限自动机。介绍两者在识别字符串上的不同及适用范围。总结得出确定化的有限自动机识别完某一字符后的状态是唯一确定的。非确定化的有限自动机识别完某一字符后状态不确定，因此对NFA要进行确定化。
举例说明确定化有穷自动机G=({S,U},{0,1},{S®S1 |U1, U®U0 | 0},S)（10分钟）
不确定化有穷自动机：NFA N=({S,A,B,Z},{a,b},M,{S},{Z}) 其中M：
M(S,a)={A} M(S,b)={B} M(A,a)={Z} M(A,b)={B}M(B,a)={A,B} M(B,b)={Z}
M(Z,a)={A,Z}（10分钟）
介绍确定化有穷自动机和不确定有限自动机的定义。（15分钟）
（1） 分析状态不确定的原因，思考解决方法；
（2） 引出非确定化有限自动机确定化的算法；把状态数为两个或两个以上的状态看作是一个新的状态，让该状态再去识别字符，如果产生状态数多于或 等于两个的再看成新的状态去识别字符直到没有新的状态产生。
（3） 比较确定化后与没有确定化之前状态有什么变化，是不是一种等价变换。（15分钟）
举例：对以上非确定化有限自动机进行确定化。（25分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题：P72 2，4
主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目：
具有e 动作的FA
课时安排
2学时
周 次
第 6周
课 序
第9次课
教学目的及要求：掌握具有e 动作的FA 变为DFA的方法

教学内容及重点、难点：
教学内容：具有e 动作的FA 的定义，具有e 动作的FA变为DFA的方法
教学重点：具有e 动作的FA 变为DFA的方法
教学难点：具有e 动作的FA 变为DFA的方法同样可以应用于前面介绍的不具有e 动作的FA的确定化， 为什么？
教学方法：引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：通过e 动作的FA的状态转换图引入其在识别单词过程中0次或多次识别e，而e与任何符号串的连接都是其他符号串，因此要对其进行确定化。（10分钟）
（1） 分析状态不确定的原因，思考解决方法；
（2） 引出具有e动作的非确定化有限自动机确定化的算法；
a) 标记qi;
b) 对于每个aSÎ,令Ta=f({Si1,Si2,…,Sim},a); qj= [e-CLOSURE(Ta)];
c) 若qjÏK’,则令K’=K’È{qj };
d) 令f’=f’ È{f’(qj ,a)= qj };
e) 重复2.,直到K’中无未标记的状态；令Z’={qj | qj Ç Zƹ} (这里把qj 视为集合)
（3） 比较确定化后与没有确定化之前状态有什么变化，是不是一种等价变换。
（4） e动作的非确定化有限自动机确定化与前面介绍的非确定化有限自动机的确定化方法统一起来。
引导学生思考以上算法。（10分钟）
介绍以上算法。（20分钟）
举例：P58 图4.4利用两种方法对e动作的非确定化的有限自动机进行确定化（40分钟）
小结：总结本次课的重点及对学生要求。（5分钟）
讨论、作业和思考题：
主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，程序设计语言编译原理
教学后记：

南阳理工学院教案（课时备课）
授课题目：
确定化有穷自动机状态数的最小化
课时安排
2学时
周 次
第 6周
课 序
第 10次课
教学目的及要求：掌握确定化有穷自动机状态数的最小化算法。
教学内容及重点、难点：
教学内容：确定化有穷自动机状态数的最小化算法。
教学重点：对某具体确定化有穷自动机能进行最小化，比较最小化前后识别的正规式是否相等？
教学难点：只能对确定化的有穷自动机进行最小化，对算法的理解及应用。
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。（5分钟）
引入新课：对于某一DFA来说，其状态数可能并不是最小的。原因是DFA中有些状态是“等价”的。为得到效率高的DFA，需将这些“等价”状态合并，引入DFA的最小化。（10分钟）
按照可区分状态和不区分状态的概念，对不可区分状态进行合并，直到所有状态都可以区分。因此得到最小化算法。
（1）介绍可区分状态和不可区分状态的定义。可区分状态: 设s,tÎK, s,t由某wSÎ*所区分 iff ( f(s,w)ÎZ Ù f(t,w)ÏZ ) Ú ( f(s,w)ÏZ Ù f(t,w)ÎZ )不可区分状态：若"wSÎ*, f(s,w)ÎZ Û f(t,w)ÎZ,则称 s与 t等价。
（2）通过举例引导同学理解可区分状态和不可区分状态。
（3）介绍最小化算法思想。将M的状态集K逐步地进行划分加细，以期将K划分为满足等价关系的等价类，使得在同一类中的状态不可区分；在不同等价类中的状态可区分。
（4）通过实例引导启发同学理解最小化算法。（15分钟）
思考：P61 例4.9（20分钟）
小结：总结本次课的重点及对学生要求。（5分钟）

讨论、作业和思考题：

主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目：
正规式与有穷自动机之间的转换
课时安排
2学时
周 次
第7周
课 序
第 11次课
教学目的及要求：掌握正规式与有穷自动机之间的转换方法
教学内容、重点、难点
教学内容：正规式与有穷自动机之间的转换方法
教学重点：正规式与有穷自动机之间的转换几种方法，应该选择哪种方法？
教学难点：已知正规式能写出有穷自动机，理解其在词法分析中的应用。
教学方法：引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。
引入新课：单词的描述工具为正规文法和正规式，单词的识别工具为有限自动机，定义的应该可以识别，前面介绍了正规文法和有限自动机之间的转换，引入正规式也可以与有限自动机进行转换。有限自动机的直观表示为状态转换图，因此介绍正规式的状态转换图。
按三种方法分别介绍正规式的状态转换图。
（1）分别给出基本的正规式r1/r2 r1* r1.r2 的状态转换图，其他的正规式都是由这三种最基本的正规式经过或运算、闭包运算和连接运算得到。
（2）通过举例引导学生画状态转换图。
（3）介绍把正规式先看成整体画状态转换图，然后按照不断往小分解直到不能再小的方法画状态转换图。
（4）介绍对闭包的处理方法，引出空串，再引出空串直接画状态转换图的方法。
（5）比较几种方法的不同，采用哪种方法更好?
小结：总结本次课的重点及对学生要求。

讨论、作业和思考题：

主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，
程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
LL（1）分析法
课时安排
4学时
周 次
第7周
课 序
第 12次课
教学目的及要求：掌握LL（1）分析法

教学内容、重点难点：
教学内容：自顶向下的语法分析。
教学重点：LL(1)文法的定义。
教学难点：左递归的消除，回溯的消除，LL（1）文法的定义。
教学方法： 引导启发、案例教学，比较
教学过程设计

回顾：上次课的重点内容。
引入新课：词法分析结束后进入语法分析，什么是语法分析？引入自顶向下分析法和自底向上分析法。
按照自顶向下的语法分析和自底向上的语法分析可以结合自顶向下的构造语法树和自底向上的构造语法树来进行分析。结合具体实例介绍自顶向下分析和自底向上分析的思想。引导学生理解自顶向下的分析方法。
（1）通过提问引导启发自顶向下分析会面临什么问题？总结问题。
（2）引导问题的解决方案。给出消除左递归和消除回溯的公式。
小结：总结本次课的重点及对学生要求。

讨论、作业和思考题：

主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，
程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
LL（1）分析法
课时安排
4学时
周 次
第8周
课 序
第 13次课
教学目的及要求：掌握LL（1）分析法

教学内容、重点难点：
教学内容： FIRST集的构造算法，FLLOW集的构造算法
教学重点： FIRST集的构造算法，FLLOW集的构造算法
教学难点： FIRST集的构造算法，FIRST集的构造算法

教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。
引入新课：怎样进行自顶向下语法分析，引入 FIRST集的构造算法，FOLLOW集的构造算法。
介绍 FIRST集的构造算法；
引导学生自学FOLLOW集的构造算法。
思考：G[E] （1）E →TE’（2）E’→+TE’　（3）E’→e （4）T→FT’ 　　
（5）T’→*FT’ （6）T’→e （7）F →（E） （8）F→ i的FIRST集和FOLLOW集。
小结：总结本次课的重点及对学生要求。

讨论、作业和思考题：

主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，
程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
LL（1）分析法
课时安排
4学时
周 次
第8周
课 序
第 14次课
教学目的及要求：掌握LL（1）分析法

教学内容、重点难点：
教学内容：复习FIRST集的构造算法，FLLOW集的构造算法；LL（1）分析表的构造；对符号串进行LL（1）分析。
教学重点：LL（1）分析法。
教学难点：LL（1）分析法。
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。
在介绍LL（1）分析法时，按照LL（1）分析器包括总控程序、分析表和分析栈，介绍在LL（1）分析中三者是如何配合工作的，引导同学谁是最核心的，通过学生提问总结分析表是分析的核心，分析表如何构造就需要构造两个集合：FIRST集合和FOLLOW集合。
LL（1）分析法：（1）构造 FIRST集合和FOLLOW集合；
（2）构造LL（1）分析表；
（3）对符号串进行LL（1）分析。
举例： G[E] （1）E →TE’（2）E’→+TE’　（3）E’→e （4）T→FT’ 　　
（5）T’→*FT’ （6）T’→e （7）F →（E） （8）F→ i 对符号串i+i*i进行LL（1）分析。

小结：总结本次课的重点及对学生要求。

讨论、作业和思考题：P100 2,3

主要参考资料：
编译原理．蒋立源著.西北工业大学出版社.2002，
程序设计语言编译原理．陈火旺著.国防工业出版社.2000

教学后记：

南阳理工学院教案（课时备课）
授课题目：
简单优先分析法
课时安排
2学时
周 次
9
课 序
第 15次课
教学目的及要求：掌握简单优先分析法。
教学内容、重点难点：
教学内容： 自底向上的语法分析、简单优先分析法
教学重点： 简单优先分析法
教学难点： 简单优先分析法
教学方法： 引导启发、案例教学，比较
教学过程设计
回顾：上次课的重点内容。
引入新课：自顶向下的分析方法是从文法的开始符号出发进行推导的过程，自底向上的分析就是从句子出发进行归约的过程。引入自底向上的语法分析。
按照自底向上的语法分析就是自底向上的构造语法树来进行分析，回顾短语、直接短语和句柄的概念，自底向上的分析就是在找句柄，不断对句柄进行归约的方法，本节课给出另外的一种找句柄的方式及简单优先分析法。
1）对简单优先分析法进行字面理解。按照优先分析，简单优先分析、简单优先文法逐层分解的方式来理解。
（1）介绍优先关系的概念
（2）简单优先关系的概念
（3）简单优先文法的概念
2）介绍简单优先分析法就是通过比较相邻符号的优先关系找到句柄进行归约。
如何比较相邻符号的优先关系按照定义来找，提示利用前面介绍的语法树来找。
让同学比较两者的不同，更喜欢采用哪一种方式。
找到简单优先关系就可以构造简单优先关系矩阵
对具体的符号串进行简单优先分析
分析归约的是不是就是句柄，与前面介绍的通过找子树的方式找到的句柄是不是一样?
总结简单优先分析法。
小结：总结本次课的重点及对学生要求。

讨论、作业和思考题：
主要参考资料： 编译原理．蒋立源著.西北工业大学出版社.2002，
程序设计语言编译原理．陈火旺著.国防工业出版社.2000
教学后记：

南阳理工学院教案（课时备课）
授课题目