资源描述：
《第9章 编译原理习题课ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、期末考试考试时间：2016-05-29上午9:00-11:00考试地点：东环101答疑时间：2016-05-27下午13:00-16:002016-05-28下午13:00-17:00答疑地点：工科楼E11101复习习题课2编译原理总复习形式化方法词法的描述——三型文法、正规式语法的描述——二型文法语义处理的描述——属性文法文法的概念形式定义（四元组）句子、句型、推导、分析树文法分类3编译系统结构词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理错误处理4词法分析正规式正规文法有限自动机DFA：确定的有限自动机知识点：语言、自动机、正规式和正规文法的关系自动机和识别过
2、程的关系5主要计算题型正规语言、正规文法、正规式、自动机的互换有限自动机的生成和DFA的构造NFA的确定化DFA的最小化6一、词法分析设有正规式1(0
3、1)*1011.试构造与该正规式等价的NFA，并对其进行确定化、最小化；2.写出与最小化以后的DFA等价的正规文法；3.写出其识别的正规集(即对应的正规语言)。7正规式1(0
4、1)*101构造与该正规式等价的NFAS010,1A1B1ZCNFA确定化S010A1B1ZC10018正规式1(0
5、1)*101DFA最小化S010A1B1ZC1001与最小化以后的DFA等价的正规文法G[S]：S→1AA→0A
6、1BB→0C
7、1BC→0A
8、
9、1ZD→0B
10、1B
11、ε9正规式1(0
12、1)*1013.写出其识别的正规集(即对应的正规语言)以1开头，以101结尾的二进制数10语法分析自顶向下分析递归子程序法LL(1)分析法（预测分析）自底向上分析（移进归约分析）简单优先分析算符优先分析LR分析：LR(0)、SLR(1)、LR(1)、LALR(1)11语法分析自顶向下分析递归子程序法LL(1)分析法（预测分析）自底向上分析（移进归约分析）简单优先分析算符优先分析LR分析：LR(0)、SLR(1)、LR(1)、LALR(1)12自顶向下分析消除左递归、提取左因子计算FIRST集、FOLLOW集、SELECT集递归子程序法(了解)判
13、断是不是LL(1)文法设计子程序LL(1)分析法（预测分析法）填写预测分析表分析某个符号串是否为句子13自顶向下分析常见题型消除左递归（直接、间接）消除左因子(提左公因子)求FIRST集求FOLLOW集求SELECT集编制递归子程序（了解）计算预测分析表(LL(1)分析表)跟踪预测分析过程14LL分析的概念根据当前输入符号，唯一地确定采用哪个产生式进行推导LL(1)文法何时改写文法适用范围左递归、左因子、FIRST、FOLLOW集和SELECT集的概念15二、LL(1)文法1、计算该文法的每个非终结符的FIRST集和FOLLOW集；2、求每个产生式的SELECT集；3、构造LL(1
14、)分析表(终结符排列顺序为：adbe#)，并判断G[S]是否为LL(1)文法；4、若G[S]是LL(1)文法，则分析符号串aaabd#是否为文法的句子，并给出分析过程。分析时包含以下4列：步骤分析栈输入串使用产生式G[S]：S→aHH→aMd
15、dM→Ab
16、εA→aM
17、e161、计算该文法的每个非终结符的FIRST集和FOLLOW集；G[S]：S→aHH→aMd
18、dM→Ab
19、εA→aM
20、e非终结符FIRST集FOLLOW集S{a}{#}H{a,d}{#}M{a,e,ε}{d,b}A{a,e}{b}2、求每个产生式的SELECT集；产生式SELECT集S→aH{a}H→aMd{a}H→
21、d{d}M→Ab{a,e}M→ε{d,b}A→aM{a}A→e{e}173、构造LL(1)分析表(终结符排列顺序为：adbe#)，并判断G[S]是否为LL(1)文法；adbe#SaHHaMdDMAbεεAbAaMe产生式SELECT集S→aH{a}H→aMd{a}H→d{d}M→Ab{a,e}M→ε{d,b}A→aM{a}A→e{e}184、若G[S]是LL(1)文法，则分析符号串aaabd#是否为文法的句子，并给出分析过程。分析时包含以下4列：步骤分析栈输入串使用产生式1#Saaabd#S→aH2#Haaaabd#a匹配3#Haabd#H→aMd4#dMaaabd#a匹配5#dM
22、abd#M→Ab6#dbAabd#A→aM7#dbMaabd#a匹配8#dbMbd#M→ε9#dbbd#b匹配10#dd#d匹配11##接受adbe#SaHHaMdDMAbεεAbAaMe分析成功，所以符号串aaabd#是文法的句子。19移近归约分析概念移进、归约、句柄、规范归约移近归约冲突、归约归约冲突核心如何寻找和确定句型中的句柄各种方法的区别20简单优先分析（了解）简单优先分析的基本思想简单优先关系分析过程21算符优先分析算符文法(OG)的定义算符优先关系的定义
