当前课程知识点:编译原理 >  第4章 自顶向下的语法分析 >  4.1 自顶向下语法分析及其面临的问题 >  自顶向下语法分析及其面临的问题

返回《编译原理》慕课在线视频课程列表

自顶向下语法分析及其面临的问题在线视频

下一节:自顶向下语法分析及其面临的问题

返回《编译原理》慕课在线视频列表

自顶向下语法分析及其面临的问题课程教案、知识点、字幕

大家好

在我们讨论过词法分析之后

我们来看语法分析

语法分析是编译程序的核心部分

它的作用呢就是按照程序语言的语法规则

从由词法分析输出的源程序符号串当中

去识别出各类的语法成分

也就是看看输入的符号串能否构成一个正确的句子

同时进行语法检查

输出程序内部的中间表示形式

譬如语法树

为语义分析和代码的生成去做准备

由于正则表达式和正则文法它是等价的

但是它们的描述能力是有限的

而高级程序设计语言它的语法结构

适合用上下文无关文法来描述

因此呢我们把上下文无关文法

作为语法分析的基础

也就是说呢这个规则

是用上下文无关文法的产生式来定义的

例如对于这样的一段原程序if (a>1) b=100;

词法分析呢识别出

这段原程序当中的单词符号序列

语法分析呢就是在这个基础之上

根据上下文无关文法为其构建语法树

按照语法分析树它的建立方法

我们可以粗略地把语法分析分做两类

一类是自顶向下的分析法

另一类呢是自底向上的分析法

自顶向下的分析方法

是从文法的开始符号出发

通过推导的过程

试图产生与输入串相匹配的句子

也就是说

从树根开始往下构造语法树

直到建立每个树叶的这样的一个分析方法

自底向上的分析方法

是从输入串出发

通过归约过程

试图归约到文法的开始符号

也就是说从语法树的末端开始

向上进行归约也就是修剪

直至剩下根结点这样的一个分析过程

接下来我们来看

自顶向下的语法分析

也就是说呢我们从文法的开始符号S出发

采用最左推导

试图逐步去推出输入串α这样的一个过程

在这个分析过程当中呢

S是作为语法树的根

试图我们从上而下地去

为α构造一棵语法树的过程

如果叶结点从左向右排列恰好α

则表示α是文法的句子

而这棵语法树呢也就是句子α它的语法结构

如果构造不出这样的一棵语法树

那么α就不是我们文法的句子

接下来我们来看这样一个例子

首先呢我们令开始节点S为树的根结点

IP呢指向输入串

用S它的

产生式去来匹配我们的输入串

首先呢我们完成一步推导

S→aAb

也就是说用aAb去来替代s

这个时候呢我们检查到

IP这个指针所指向的字符是a

它和这个句型当中的a是匹配的

那么IP这个指针就后移

句型的第二个符号是A

是非终结符

这个时候呢就将匹配的任务

交给这个非终结符

那么究竟选用A的哪一个产生式

去来匹配这个输入串呢

因为A呢有两个产生式

如果我们选用第一个产生式

完成进一步推导

A→cd

也就说用cd去来代替这个A

我们检查到推导式的

右部的第一个c和IP所指向的这个c是匹配的

所以IP这个指针就继续后移

产生式第二个符号d

和IP这个时候所指向的符号b是不匹配的

于是呢这个匹配的过程就失败了

那么去需要砍掉A的子树

恢复到A没有生成子树的状态

同时呢IP这个指针呢也要恢复到

刚才的指向c的时候

接下来我们选用A的第二个产生式

A→c

那么用c去来代替A

这个时候我们发现

IP所指向的c和产生式的c匹配

IP指针继续后移指向b

和S产生式的最后一个符号b匹配

这样的话呢就建立出了这样一棵语法树

而且这棵语法树它的末端结点是acb

这和我们的输入串acb是匹配的

大家发现

构建语法树的过程

其实也建立了这样的一个推导过程

S→aAb→acb

说明呢acb是正确的句型

在我们刚才使用自顶向下的分析方法当中

我们发现

分析的过程是带有预测性的

对输入符号串要预测属于什么样的语法成分

然后呢我们要根据这个语法成分它的文法

来建立相应的语法树

而且自顶向下的分析过程

是一种试探的过程

因为呢对于某一个非终结符来说

它可能有多个产生式

自顶向下的分析过程呢就要

尽一切的方法

选用不同的规则来去设法建立这样的语法树的过程

由于呢这是一个试探的过程

所以难免会出现匹配失败的时候

所以这个分析的过程呢需要进行回溯

因此我们也称这种方法是带回溯的

自顶向下的分析方法

好了 那我们来看一下在刚才构建

推导的过程当中我们会遇到什么样的问题

第一个问题就是有的时候

我们的分析工作要

部分地或者是全部退回去重做

这就是回溯的问题

那么究竟是什么样的原因

造成了回溯的原因呢

这是因为在文法当中

对于某一个非终结符来说

它可能有多个产生式

比如说

在这个例子当中U它有3个产生式

如果我们根据所面临的输入符号

没有办法准确的去确定

到底应该选择哪一个产生式的时候

就可能会出现回溯

回溯带来的后果就是严重的低效率

因为语法分析要重做

有的时候语义分析和语法分析是同时进行的

那么回溯也会让语义处理工作要推倒重来

回溯的方法

只有在理论上是有意义的

实际当中呢我们并不常用

我们再来看一下这个文法

E→E+T|T

T→T*F|F

F→(E)|i

这个文法呢定义的其实是一个产生式

我们发现这个文法当中

有形如A→Aα的这样的产生式

α指的是字符串

那么这样的文法呢我们叫它左递归文法

而且呢这个例子是一个直接左递归文法

我们按照刚才我们所使用的

自顶向下的分析方法

从左向右来扫描源程序

同时我们实施的是最左推导

我们来给出

这个表达式i*i+i

自顶向下的分析过程

会发现

构建语法树的时候陷入了死循环

这是因为在我们这个例子当中

当我们用

非终结符E去匹配输入串的时候

结果我们采用的是最左推导

但是推导出来的句型当中的

最左边的非终结符仍然是E

所以就会出现死循环的问题

如果文法具有间接左递归

也会出现这个死循环

只不过是这个循环的圈子可能会兜的更大一些

自顶向下的分析方法

是没有办法处理左递归性文法的

同学们

在这节当中呢我们讨论的是自顶向下的分析方法

自顶向下的分析法是从文法的开始符号出发

企图推导出与输入的单词串完全相匹配的句子

如果我们可以推导出这样的一个句子

它和输入串完全相同的话

那么说明我们这个输入串是正确的句子

否则在这个过程当中

就会出现匹配失败的问题

自顶向下的分析方法呢可以分做

确定的和不确定的两种

不确定的方法就是我们刚才所看到的

带回溯的分析方法

这个带回溯的分析方法

是一种穷举的试探方法

这种方法呢是没有办法

处理左递归文法的

而且还会产生回溯的问题

可是我们也发现

左递归和回溯的问题

它的产生的原因

直接与描述语言的文法是有关的

因此

要对文法进行确定的自顶向下分析方法

首先应该改造文法

使其不含左递归和回溯

这节课呢就到这里

谢谢大家

编译原理课程列表:

第1章 编译原理概述

-1.1 什么是编译原理

--什么是编译原理

--什么是编译程序

--讨论:翻译程序、汇编程序、编译程序、解释程序的区别和联系。

--练习1

-1.2 编译的基本过程

--编译的基本过程

--编译的基本过程

--讨论:表格管理和出错处理

--练习2

-1.3 编译程序的组织

--编译程序的组织

--编译程序的组织

--练习3

-编译原理概述

第2章 编译理论基础

-2.1 文法与语言

--文法与语言

--文法与语言

-2.2 文法和语言的形式定义

--文法和语言的形式化定义

--文法和语言的形式化定义

--讨论:高级语言的一般特点

--练习1

-2.3 文法的类型

--文法的类型

--文法的类型

--练习2

-2.4 上下文无关文法及语法树

--上下文无关文法及语法树

--上下文无关文法及语法树

--练习3

-2.5 上下文无关文法的句型分析

--上下文无关文法的句型分析

--上下文无关文法的句型分析

--练习4

-编译理论基础作业

-讨论:识别不同文法的实验方法

第3章 词法分析

-3.1 词法分析概述

--词法分析概述

--词法分析概述

--练习1

-3.2 正规文法和状态转换图

--正规文法和状态转换图

--正规文法和状态转换图

--练习2

-3.3 有限状态自动机

--有限状态自动机

--有限状态自动机

--讨论:有限状态自动机的应用

--练习3

-3.4 NFA与DFA的等价性

--NFA与DFA的等价性(上)

--NFA与DFA的等价性(下)

--NFA与DFA的等价性

--练习4

-3.5 正规表达式与正规集

--正规表达式与正规集

--正规表达式与正规集

--讨论:正规式的应用

--练习5

-3.6 正规文法与正规式

--正规文法与正规式

--正规文法与正规式

--练习6

-3.7 正规式与FA

--正规式与FA

--正规式与FA

--练习7

-词法分析作业

-讨论:如何实现词法分析器

第4章 自顶向下的语法分析

-4.1 自顶向下语法分析及其面临的问题

-- 自顶向下语法分析及其面临的问题

--自顶向下语法分析及其面临的问题

--自上而下语法分析中面临的问题

--练习1

-4.2 文法的等价转化

--文法的等价转化

--文法的等价转化

--讨论:什么样的文法才是等价的?

--练习2

-4.3 LL(1)文法与递归下降分析法

--LL(1)文法与递归下降分析法

--LL(1)文法与递归下降分析法

--LL(1)分析法和递归下降法的异同

--练习3

-4.4 构建FIRST集合FOLLOW集合

--构建FIRST集合FOLLOW集合

--构建FIRST集合FOLLOW集合

--讨论:FIRST集合FOLLOW集合的关系

--练习4

-4.5 LL(1)分析器工作原理

-- LL(1)分析器工作原理

--LL(1)分析器工作原理

-4.6 LL(1)分析表构造算法

--LL(1)分析表构造算法

--LL(1)分析表构造算法

--练习5

-讨论:自顶向下语法分析算法的实现方式

第5章 自底向上的语法分析

-5.1 自底向上的语法分析及优先分析

--自底向上的语法分析及优先分析

--自底向上的语法分析及优先分析

--练习1

-5.2 LR分析器

--LR分析器

--LR分析器

--练习2

-5.3 活前缀和LR(0)项目

-- 活前缀和LR(0)项目

--活前缀和LR(0)项目

--练习3

-5.4 构造识别活前缀的FA

--构造识别活前缀的FA

--构造识别活前缀的FA

--练习4

-5.5 LR(0)分析表构造算法

--LR(0)分析表构造算法

--LR(0)分析表构造算法

--练习5

-5.6 SLR(1)分析法

--SLR(1)分析法

--SLR(1)分析法

--练习6

-5.7 LR(1)分析法与LALR分析法

--LR(1)分析法与LALR分析法(上)

--LR(1)分析法与LALR分析法(下)

--LR(1)分析法与LALR分析法

--练习7

-讨论:比较四种LR分析法

第6章 语法制导翻译和中间代码生成

-6.1 语义分析和语法制导翻译概述

--语义分析和语法制导翻译概述

--语义分析和语法制导翻译概述

--练习1

-6.2 常见中间语言简介

--常见中间语言简介

--常见中间语言简介

--讨论:为什么要引入中间代码

--练习2

-6.3 简单算术表达式和赋值语句翻译

--简单算术表达式和赋值语句翻译

--简单算术表达式和赋值语句翻译

--练习3

-6.4 布尔表达式和复制语句翻译

--布尔表达式和复制语句翻译

--布尔表达式和复制语句翻译

-6.5 拉链和回填

--拉链与回填

--拉链与回填

--练习4

-6.6 程序控制语句翻译

--程序控制语句翻译

--程序控制语句翻译举例

--程序控制语句翻译

--练习5

-6.7 for循环语句的翻译

--for循环语句的翻译

--for循环语句的翻译

-6.8 GOTO语句和情况语句的翻译

--GOTO语句和情况语句的翻译

--GOTO语句和情况语句的翻译

--练习6

-6.9 含数组元素的算术表达式的翻译

--含数组元素的算术表达式的翻译

--含数组元素的算术表达式的翻译

--练习7

-6.10 数组元素赋值语句的翻译

--数组元素赋值语句的翻译

--数组元素赋值语句的翻译

--练习8

-讨论:三元式和四元式

第7章 符号表

-7.1 符号表概述

--符号表概述

--符号表概述

--练习1

-7.2 符号表的建立

--符号表的建立

-- 符号表的建立

--练习2

-讨论:符号表

第8章 运行时存储空间组织

-8.1 运行时存储空间组织概述

--运行时存储空间组织概述

--运行时存储空间组织概述

-8.2 运行时分配策略

--运行时分配策略

--运行时分配策略

--练习

第9章 中间代码优化

-9.1 线性窥孔优化

--线性窥孔优化

--线性窥孔优化

-9.2 基本块及其优化方法

--基本块及其优化方法

--基本块及其优化方法

-9.3 循环概念

--循环概念

--循环概念

-9.4 循环优化

--循环优化

--循环优化

-代码优化作业

-讨论:代码优化

自顶向下语法分析及其面临的问题笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。