当前课程知识点:编译原理 >  第4章 自顶向下的语法分析 >  4.2 文法的等价转化 >  文法的等价转化

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

文法的等价转化在线视频

下一节:文法的等价转化

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

文法的等价转化课程教案、知识点、字幕

同学们

我们来总结一下在上节课中

我们所讨论的

自顶向下的文法分析它的思想

其实呢就是为输入串

建立一个最左推导序列的过程

在这个过程当中呢

对输入串自左向右进行扫描

这样的话就能保证

按照从左向右扫描的顺序来匹配输入串

但是这个过程呢是一个

不断试探的过程

由于一些不确定的因素

譬如说

无法确定选用非终结符的哪一个产生式

就会出现回溯的问题

此外呢这种方法

没有办法处理左递归文法

解决这些问题

它的方法就是

对文法进行等价的转化

转化之后的文法

没有左递归

也没有回溯

那么首先呢我们来看一下

怎样消除文法的左递归

首先

文法当中如果出现这样的产生式

A→Aα的话

那么这是我们说到的

直接左递归文法

如果文法当中并不存在产生式 A→Aα

但是

A经过若干步推导

可以得到 Aα的话

那么这样的文法叫做间接的左递归文法

首先我们来看一下如何消除直接左递归

消除直接左递归需要

引入新的非终结符号A’

将A的产生式

A→Aα|β

需要强调这里边

α并不是ε

而且β也并不是以A开头的

转换的这个规则是这样子的

A → Aα或β

转换成这样的一组产生式

A → βA’

A’ → αA’| ε

大家注意啊不要丢掉这个ε

那么接下来我们就来实践一下

将上一节当中我们所遇到的

这个表达式文法

我们来消除一下它的直接左递归

我们利用消除直接左递归的规则

将E和T的产生式进行这样的转换

那么E的产生式就变成了

E→ T E’

E’→ + T E’|ε

那么T的产生式就变成

T→ F T’

T’→* F T’|ε

F的产生式继续保留

一般而言

假定

关于A的全部产生式是这样子的

其中呢每一个α都不是ε

而每一个β也不是以A开头的

那么

消除A的直接左递归

就是把这些产生式

改写成这样的一组产生式

这个ε大家不要丢掉

下面我们来介绍一个

消除任何左递归的算法

分做两步走

第一步呢就是用代入法也就是分配率

将间接左递归

把它变成直接左递归

第二步就是按照

消除直接左递归的方法

来消除递归

我们来看这个文法

A →Bb

B →Ac

B →d

虽然说在这个文法当中

没有直接左递归的产生式

但是因为B经过两步推导之后

会得到B

→Bbc

那么说明这个文法还是存在间接左递归的

我们可以先将产生式①代入产生式②

这样的话就将原来的间接左递归变成了直接左递归

得到的产生式是这样子的

B→Bbc

于是呢B的产生式就变成了B → Bbc|d

接下来我们就消除B的直接左递归

这样的话就得到了不含左递归的文法

这个文法是这样子的

A →Bb

B → dB’

B’ → bc B’ | ε

我们也可以采用另外一种带入的方法

先将(2)(3)代入(1)当中去

这样的话呢就得到了A的直接左递归产生式

那么这样的话呢我们就去消除A的直接左递归

得到不含左递归的文法

文法是这样子的

A →dbA’

A’ →cbA’|ε

大家发现

这个时候B就变成了无用的符号

那么可以把B和它的产生式删除掉了

需要说明这么几点

首先第一点

我们在进行文法的等价转换的时候

不要改变文法的开始符号

其次

大家也发现

因为代入的方法不同

得到的不含左递归的文法

可能也不同

但是它们是等价的

最后消除左递归之后

文法当中可能会出现无用的符号

我们应该把它去掉

在自顶向下的分析过程当中

由于回溯

需要推翻前面的分析

包括已经做的一大堆的语义工作

重新的去进行试探

这样大大降低了语法分析器它的工作效率

因此我们需要去消除回溯

在消除回溯之前

我们先要弄明白

引起回溯的原因是什么

当文法当中的某个非终结符有n个产生式的时候

可能就会出现回溯

我们来看第一种情况

当同一个非终结符

它的产生式左端第一个符号相同的时候

就会引起回溯

例如文法当中的产生式是这样子

A→ab|a

如果说面临的输入符号是a时候

就不能够准确的指出

到底是用产生式ab

还是使用a去代替A

然后去和我的输入串进行匹配

因此呢就需要回溯

还有一种情况就是

如果某一个非终结符

它的一个产生式是可以推出ε串的

那么也可能引起回溯

比如说文法A→Bx

B→x |ε

如果我们将B的产生式带入到A当中去

那么A的产生式就被改写成了

A→x| x x

也就是说

当面临的输入符号是x的时候

也是没有办法明确的指出

到底使用哪一个产生式

去和我的输入串相进行匹配

也可能会出现回溯

大家发现在刚才的这几个例子当中

如果这些产生式不含公共的左因子

那么我们就可以准确的指出

哪一个产生式可以唯一的代表A

去和我的输入串去进行匹配

不需要去试探

也不需要回溯

因此

消除回溯的途径

是通过对同一

非终结符的多个产生式

反复的去提取左因子

来改写文法的

假设文法当中关于A的产生式是这样子的

那么

我们可以引入新的非终结符

来改写这个文法

改写之后的文法就变成这样子了

大家发现

提取左公因子过程非常类似我们数学当中

提取公共因子的方法

只是这里需要将左公因子后面的这个产生式

由一个新的非终结符来引出

接下来我们来看一下

对于这样的两个产生式

通过提取公共左因子

来改造文法

这两个产生式是这样子的

那么这两个产生式有

公共的左因子

我们提取了这个公共左因子

我们就可以把这两个产生式

改写成这样子

注意

不能丢掉ε

但是我们也发现

提取左公因子会产生一些问题

首先呢提取左公因子

可能会导致出现新的ε产生式

其次不能解决ε产生式不确定性的问题

如果ε是一个当前的产生式

匹配符号串的当前符号时

可以先选择ε产生式

使得当前的符号与句型当中

在ε后面的符号去做匹配

但是如果之后发现

仍然存在其他的产生式

左边的第一个符号

也能与当前的符号去匹配的话

又需要去进行试探了

有一种不会出现上面问题的文法

这个就是LL(1)文法

同学们

在这一节当中

我们针对自顶向下语法分析当中的不确定性

讨论了通过消除左递归和回溯

对文法进行等价的转化

以便去使用确定的自上而下的分析方法

这一节课呢我们就讨论到这里

谢谢大家

编译原理课程列表:

第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 循环优化

--循环优化

--循环优化

-代码优化作业

-讨论:代码优化

文法的等价转化笔记与讨论

也许你还感兴趣的课程:

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