《编译原理》课程教学资源:第二章(2-4)语法分析一自上而下分析

214语法分析、自上而下分析 本章主要介绍语法分析的处理 要进行语法分析,必须对语言的语法结 构进行描述。 ●采用正规式和有限自动机可以描述和识别语 言的单词符号; 用上下文无关文法来描述语法规则
2.4 语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析,必须对语言的语法结 构进行描述。 ⚫ 采用正规式和有限自动机可以描述和识别语 言的单词符号; ⚫ 用上下文无关文法来描述语法规则

2.4.1语法分析器的功能 语法分析的任务是分析一个文法的句子 结构 语法分析器的功能:按照文法的产生式 (语言的语法规则),识别输入符号串是 否为一个句子(合式程序)
2.4.1 语法分析器的功能 语法分析的任务是分析一个文法的句子 结构。 语法分析器的功能:按照文法的产生式 (语言的语法规则),识别输入符号串是 否为一个句子(合式程序)

单词符号 语法分 源程序词法分 语法分析树编译程序 析器 取下一单词 析器 后续部分 符号表
源程序 单词符号 取下一单词 ... 语法分 词法分 析树 析器 语法分 析器 符号表 编译程序 后续部分

定义:假定G是一个文法,S是它的开始符号 如果s=则a称是一个句型。仅含终结 符号的句型是一个句子。文法G所产生的句子的 全体是一个语言,将它记为L(G)。 L(G)={c1S→c,c∈I}
* S ( ) { | , } * VT L G = S + ❑定义:假定G是一个文法,S 是它的开始符号。 如果 ,则称是一个句型。仅含终结 符号的句型是一个句子。文法G所产生的句子的 全体是一个语言,将它记为 L(G)

●语法分析的方法: 自下而土分析法( Bottom-up) 基本思想:从输入串开始,逐步进行“归约”, 直到文法的开始符号。即从树末端开始,构造语 法树。所谓归约,是指根据文法的产生式规则, 把产生式的右部替换成左部符号。 ●算符优先分析法:按照算符的优先关系和结合性质 进行语法分析。适合分析表达式。 LR分析法:一种更一般的自下而上分析法
语法分析的方法: ⚫ 自下而上分析法(Bottom-up) 基本思想:从输入串开始,逐步进行“归约” , 直到文法的开始符号。即从树末端开始,构造语 法树。所谓归约,是指根据文法的产生式规则, 把产生式的右部替换成左部符号。 ⚫ 算符优先分析法:按照算符的优先关系和结合性质 进行语法分析。适合分析表达式。 ⚫ LR分析法:一种更一般的自下而上分析法

G(E):E>il E+EIE-EI E*E IE/E I(E) Ei+i 三“E十i E+i E+E E E k E
G(E): E → i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + * E i i E E E E

●自上而下分析法(Top-down) 基本思想:它从文法的开始符号出发,反 复使用各种产生式,寻找匹配"的推导 递归下降分析法:对每一语法变量(非终结符) 构造一个相应的子程序,每个子程序识别一定的 语法单位,通过子程序间的信息反馈和联合作用 实现对输入串的识别 预测分析程序 优点:直观、简单和宜于手工实现
⚫ 自上而下分析法(Top-down) 基本思想:它从文法的开始符号出发,反 复使用各种产生式,寻找"匹配"的推导。 ⚫ 递归下降分析法:对每一语法变量(非终结符) 构造一个相应的子程序,每个子程序识别一定的 语法单位,通过子程序间的信息反馈和联合作用 实现对输入串的识别。 ⚫ 预测分析程序 优点:直观、简单和宜于手工实现

242自上而下分析面临的问 自上而下就是从文法的开始符号出发,向下 推导,推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法 ●自上而下分析的主旨:对任何输入串,试图 用一切可能的办法,从文法开始符号(根结 点)出发,自上而下地为输入串建立一棵语 法树。或者说,为输入串寻找一个最左推导
2.4.2 自上而下分析面临的问 题 自上而下就是从文法的开始符号出发,向下 推导,推出句子。 ⚫ 带“回溯”的 ⚫ 不带回溯的递归子程序(递归下降)分析方法。 自上而下分析的主旨:对任何输入串,试图 用一切可能的办法,从文法开始符号(根结 点)出发,自上而下地为输入串建立一棵语 法树。或者说,为输入串寻找一个最左推导

●例341假定有文法G(S) (1)s→xAy (2)A→** 分析输入串xy(记为)
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|* 分析输入串x*y(记为)。 x*y S IP x*y S x A y x*y S IP x A y x*y S IP x A y * * x*y S IP x A y * * x*y S IP x A y * x*y S IP x A y *

●当某个非终结符有多个产生式候选时,可 能带来如下问题 1.回溯问题 分析过程中,当一个非终结符用某一个候选匹配成 功时,这种匹配可能是暂时的。出错时,不得不“回 溯 2.文法左递归问题 一个文法是含有左递归的,如果存在非终结符P P→PC ◆含有左递归的文法将使自上而下的分析陷入无限 循环
当某个非终结符有多个产生式候选时,可 能带来如下问题: 1. 回溯问题 分析过程中,当一个非终结符用某一个候选匹配成 功时,这种匹配可能是暂时的。出错时,不得不“回 溯” 。 2. 文法左递归问题。 一个文法是含有左递归的,如果存在非终结符P PP + 含有左递归的文法将使自上而下的分析陷入无限 循环
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 《JavaScript》权威指南简介.ppt
- 《编译原理》课程教学资源:第三章 正则表达式常应用于文本匹配:.ppt
- 《编译原理》课程教学资源:第二章(2-3-1)对于词法分析器的要求.ppt
- 《编译原理》课程教学资源:第二章 词法分析 2.6 利用Lex自动生成扫描程序.ppt
- 《编译原理》课程教学资源:第二章 语言描述与实现 Language Description and Implementation 2.1 程序语言的语法描述.ppt
- 《编译原理》课程教学资源:第一章(1-2)编译简介.ppt
- 《编译原理》课程教学资源:语义分析和中间代码产生.ppt
- 《编译原理》课程教学资源:Chapter 5 Procedure Activations.ppt
- 《互联网软件应用与开发》综合复习材料.doc
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第四章 门电路.ppt
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第六章 时序逻辑电路.ppt
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第五章 组合逻辑电路.ppt
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第二章 半导体基本器件.ppt
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第三章 开关理论基础.ppt
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第七章 存储器和可编程逻辑器件.ppt
- 《计算机电路基础》课程教学资源(PPT课件讲稿)第一章 课程简介.ppt
- 清华大学:《数据通信原理》课程教学资源(学习讲义)软件无线电体系结构的新趋势.doc
- 清华大学:《数据通信原理》课程教学资源(学习讲义)超宽带无线通信技术及发展.doc
- 清华大学:《数据通信原理》课程教学资源(学习讲义)第12讲 无线系统及网络.ppt
- 清华大学:《无线通信工程》第10讲 抗衰落.ppt
- 《编译原理》课程教学资源:第二章(2-4-1)One parse tree only.ppt
- 《编译原理》课程教学资源:第五章 YACC.ppt
- 《编译原理》课程教学资源:第四章 对象和环境.ppt
- 《编译原理》课程教学资源:第八章 符号表.ppt
- 《编译原理》课程教学资源:第六章 属性文法.ppt
- 《编译原理》课程教学资源:第五章(5-2)过程激活.ppt
- 《编译原理》课程教学资源:第二章 语言描述与实现 Language Description and Implementation 2.5 语法分析——自下而上分析.ppt
- 《编译原理》课程教学资源:教学计划.doc
- 《编译原理》课程教学资源:第十章 优化.ppt
- 《编译原理》课程教学资源:属性文法.ppt
- 《体系结构》第二章 计算机指令集结构设计.doc
- 《体系结构》第三章 流水线技术.doc
- 《体系结构》第五章 存储层次.doc
- 《体系结构》第六章 输入输出系统.doc
- 《体系结构》第一章 计算机体系结构的基本概念.doc
- USB系统研究(学位论文)USB System Study.pdf
- 《微型计算机原理与接口技术》第10章 串行通信接口.ppt
- 《微型计算机原理与接口技术》第11章 人机交互接口技术.ppt
- 《微型计算机原理与接口技术》第12章 模拟量输入输出接口技术.ppt
- 《微型计算机原理与接口技术》第1章 微型计算机基础知识.ppt