当前课程知识点:编译技术 >  第三章 语法分析 >  3.2 自上而分析中的文法 >  3.2.2 提取左因子

返回《编译技术》慕课在线视频课程列表

3.2.2 提取左因子在线视频

下一节:3.2.3 语言和文法

返回《编译技术》慕课在线视频列表

3.2.2 提取左因子课程教案、知识点、字幕

各位同学大家好

这一节我们继续来学习

语法分析中的提取左因子方法

接下来我们来学习

如何提取左因子

我们以if语句为例

我们先来看一下程序中

if语句的原始文法

S可以产生if E then S

或者if E then S else S 或者other

这个地方我们发现

红色的字体部分

if E then S

是包含左因子的

我们可以采取提取左因子的方法

来修改文法

我们看到由于左因子的存在

我们在进行if语句的处理的时候

难以判断使用哪一个产生式

来进行匹配

也就是说

这个地方存在左因子if E then S

我们可以提取左因子

来推迟进行这样的选择

我们看到当某一步的推导

如果存在左因子的时候

我们可以采取提取左因子的方法

来修改原有的文法

假设文法是

S可以产生aCb

C可以产生cd或者c

我们可以通过改写文法

将C改为 C产生cC'

C'产生d或者空串

这样我们就可以通过

提取左因子的方法

推迟我们做出的选择

从而可以知道

我们下一步来使用的产生是哪一个

我们接下来观察

一般的左因子提取方法

假设有一个左因子的文法

A产生αβ1 或者αβ2

我们观察到α是左因子

所以我们可以通过

改写这个文法来提取左因子

A产生αA'

我们使用A'来表示β1或者β2

我们仍然可以使用

提取左因子的方法

来解决if else语句的问题

我们看到针对悬空else的文法

我们可以将它提取左因子之后

将它改为

statements产生if expr then statement

后边跟着的是可选的else部分

或者其他

而可选的else这个部分

可以是else statement或者空串

接下来我们来学习

一般的提取左因子的方法

假设有一个产生式

A可以产生αb1或者αb2或者αbm

或者γ1 γ2到γp

我们可以将这个文法

进行改写

A产生αA'或者γ1 γ2一直到γp

而A'它用来表示

b1或者b2一直到bm这样

我们就可以使用

这种方法

将所有的左因子提取出来

从而使得文法不存在左因子

在自上而下的分析中

我们看到

我们的基本思想是

寻找输入串的最左推导

也就是采取最左推导

来进行自上而下的分析

我们试图根据输入单词

来决定

每一次使用哪一个产生式来进行最左推导

所以我们的基本过程就是

从产生式的开始符号S出发

构造输入串的最左推导

从根节点开始进行匹配

按照最左推导相应的顺序

自上而下构造输入串的语法分析树

我们来回顾一下

这个小节

我们所学习的内容

我们将上下文无关文法中的左因子

进行取出来

我们消除了左递归

在完成了这两步之后

我们就可以来进行自上而下的推导

那也就是使用最左推导

来构造我们需要的语法树

这一小节就到这

谢谢大家

编译技术课程列表:

第一章 绪论

-1.1 编译技术绪论

--1.1 编译技术绪论

--编译原理介绍--作业

第二章 词法分析

-2.1  词法记号 串和语言

--2.1 词法记号 串和语言

--2.1  词法记号 串和语言--作业

-2.2  正规式 状态转换图

--2.2 正规式 状态转换图

--2.2  正规式 状态转换图--作业

-2.3  有限自动机

--2.3 有限自动机

--2.3  有限自动机--作业

-2.4  DFA构建 子集构造法 DAF化简

--2.4 DFA构建

-2.5 Lex

--2.5 词法分析工具Lex

第三章 语法分析

-3.1 上下文无关文法

--3.1.1 语法分析概述

--3.1.2 上下文无关文法定义

--3.1.3 推导

--3.1.4 二义性

-3.2 自上而分析中的文法

--3.2.1 消除左递归

--3.2.2 提取左因子

--3.2 上下文无关文法--作业

--3.2.3 语言和文法

--3.2.3 语言和文法--作业

-3.3 自上而下分析

--3.3.1 first follow

--3.3.2 LL(1)文法

--3.3.3 递归下降分析

--3.3.4 非递归下降分析的预测分析器

-3.4 自下而上分析

--3.4.1 归约句柄

--3.4.2 移进归约分析过程

--3.4 自下而上分析--作业

-3.5 LR分析器

--3.5.1 LR分析器

--3.5.2 活前缀

--3.5.3 SLR分析方法

--3.5.4 规范的LR分析方法

--3.5.5 LALR分析方法

--3.5.6 LR分析方法特点

--3.5.7 非二义且非LR的上下文无关文法

第四章 语法指导的翻译

-4.1 语法制导的定义

--4.1.1 属性文法

--4.1.2 属性依赖图和计算次序

--4.1 语法制导的定义--作业

-4.2 S属性的自下而上计算

--4.2.1 S属性的自下而上计算

--4.2.2 栈代码

-4.3 L属性定义

--4.3.1 L属性定义

--4.3.2 翻译方案

--4.3.3 预测翻译器的设计

--4.3 L属性定义--作业

-4.4 L属性的自下而上计算

--4.4.1 L属性的自下而上计算

--4.4.2 模拟继承属性的计算

--4.4 L属性的自下而上计算--作业

第五章 运行时存储空间的组织与管理

-5.1  概述

--5.1 概述

--概述-作业

-5.2  全局栈式存储分配

--5.2 全局栈式存储

-5.3  调用序列

--5.3 调用序列

-5.4 非局部名字的访问

--5.4 非局部名字

--5.4 非局部名字的访问--作业

第六章 中间代码生成

-6.1 中间代码生成

--6.1 中间代码生成概述

-6.2 作用域信息的保存

--6.2 声明语句-作用域信息的保存

第七章 代码生成

-7.1 代码生成器设计中的问题

--7.1 代码生成器的设计中的问题

-7.2 目标机器

--7.2 目标机器

--7.2  目标机器--作业

-7.3 基本块和流图

--7.3 基本块和流图

-7.4 一个简单的代码生成器

--7.4 一个简单的代码生成器

第八章 基于Python的编译器框架实现

-8.1 基于Python的编译器框架演示视频和代码

--8.1 基于Python的编译器框架演示

-8.2 代码介绍

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

3.2.2 提取左因子笔记与讨论

也许你还感兴趣的课程:

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