《编译原理》总复习-习题与试题-说课讲解.ppt

《编译原理》总复习-习题与试题-说课讲解.ppt

ID:59527464

大小:718.00 KB

页数:54页

时间:2020-11-08

《编译原理》总复习-习题与试题-说课讲解.ppt_第1页
《编译原理》总复习-习题与试题-说课讲解.ppt_第2页
《编译原理》总复习-习题与试题-说课讲解.ppt_第3页
《编译原理》总复习-习题与试题-说课讲解.ppt_第4页
《编译原理》总复习-习题与试题-说课讲解.ppt_第5页
资源描述:

《《编译原理》总复习-习题与试题-说课讲解.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、《编译原理》总复习-习题与试题-2010第一章引言<1>语言的翻译不同的翻译形式:汇编、编译、转换(预编译)、逆向翻译翻译方法:2<2>编译器的基本组成3<3>编译器的分析-综合模式<4>编译器的扫描遍数与编译器的编写4第二章词法分析构词规则与词法分析:首先规定单词形成的规则,称为构词规则;然后根据构词规则识别输入序列,称为词法分析。主要内容:<1>记号、模式与单词<2>记号的说明-模式的形式化描述(正规式与正规集)<3>记号的识别-有限自动机<4>从正规式到词法分析器词法分析器的作用:滤掉源程序中的无用成分;处理与具体操作系统或机器有关的输入;识别记号并交给语法

2、分析器;调用符号表管理器和出错处理器进行相关处理。5<1>记号、模式与单词模式(pattern):规定单词识别的规则记号(token):按照某模式识别出的一类单词(记号种类)单词(lexeme):被识别出的字符串本身词法分析器的输出:记号=记号种类+记号属性<2>记号的说明-模式的形式化描述正规式与正规集正规式与正规集的定义(基本正规式、三个运算)正规式的等价(描述相同的集合)利用正规式的等价对正规式进行化简(正规式的代数性质)用正规式形式化描述模式如何用正规式描述程序设计语言中常见的记号,如标识符、数字、运算符和分隔符等正规式的简化形式以及辅助定义与规则6<3>

3、记号的识别-有限自动机(FA)NFA与DFA的定义:FA=(S,Σ,move,s0,F);NFA与DFA的表示:定义表示、状态转换图、状态转换矩阵;NFA与DFA的关键区别:NFA的不确定性:有ε状态转移;当前状态下,对同一字符有多于一个的下一状态转移;用NFA识别输入序列的弱点:尝试所有路径才能确定一个输入不被接收、回溯带来的问题;模拟DFA的算法(算法2.1):用DFA识别记号。7<4>从正规式到词法分析器构造NFA的Thompson算法(算法2.2):与正规式的对应关系;模拟NFA的“并行”算法(算法2.3);从NFA构造DFA-子集法(算法2.5):smo

4、ve(S,a)与ε-闭包(T)的计算;DFA的最小化-可区分的概念:所有不可区分的状态看作是一个状态(算法2.6);灵活运用各种方法构造DFA(正规式化简、状态转换图等),特别是手工构造和算法构造的区别(考虑(a

5、b)*abb的NFA)。第三章语法分析语法分析是编译器中的重要阶段之一,可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义:根据一定的规则构成语言的各种结构,即语法规则;根据语法规则识别输入序列(记号流)中的语言结构,即语法分析。语法分析的分析对象是组成语言的句子,句子具有层次结构的特征,表征该结构的最好方法是树,从而使得对语法的分析就有了从根

6、到叶子和从叶子到根两种分析方法。主要内容<1>程序设计语言与文法<2>有关推导的基本概念<3>自上而下分析<4>自下而上分析9<1>程序设计语言与文法正规式与正规文法:正规式与正规文法用于描述线性结构,如构成句子的记号(终结符);识别正规语言的自动机是有限自动机,它们的特征是没有记忆能力;上下文无关文法(CFG=(N,T,S,P)):CFG用于描述层次结构,如构成程序的句子;识别CFL的自动机是下推自动机,它是在有限自动机的基础上增加了一个下推栈,从而有了简单的记忆能力;文法的分类:0型、1型、2型和3型文法词法分析器与语法分析器:FA与PDA10<2>有关推导的

7、基本概念CFG产生语言的基本方法-推导:从文法的开始符号开始,反复地用产生式的右部替换句型中的非终结符。推导的基本概念:句子、直接推导、最左推导、左句型(最右推导、右句型);(定义3.2、3.3、3.4)分析树与语法树:分析树和语法树都反映了语言结构;分析树还记录了分析的过程(含有非终结符);(定义3.5、3.6)文法的二义性:二义性的本质是在文法中缺少对文法符号优先级和结合性的限制,从而使得一个句子可以推导出多于一棵分析树。(定义3.7)二义性的消除:改写二义文法为非二义文法;(两个关键步骤)对文法符号施加优先级与结合性的限制,使得分析的每一步有唯一选择。11<

8、3>自上而下分析分析方法:推导,从上到下构造分析树,是一种预测的、试探的方法;对文法的要求:没有公共左因子和左递归左递归与直接左递归(定义3.9)消除直接左递归与左递归(算法3.1、3.2)提取公共左因子(类似于提取公因式)递归下降子程序方法:匹配终结符,展开非终结符(子程序调用)12<3>自上而下分析(续)预测分析表方法:工作方式与过程:PDA(DPDA)格局:(栈内容,当前剩余输入,改变格局的动作)改变格局的动作:匹配终结符、展开非终结符、接受、报错驱动器(算法3.4)预测分析表和分析表的构造:分析表的构成与意思:M[A,a]FIRST集合与FOLLOW集合(

9、定义3.1

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。