当前课程知识点:编译技术 > 第三章 语法分析 > 3.2 自上而分析中的文法 > 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 编译技术绪论
--编译原理介绍--作业
-2.1 词法记号 串和语言
--2.1 词法记号 串和语言--作业
-2.2 正规式 状态转换图
--2.2 正规式 状态转换图--作业
-2.3 有限自动机
--2.3 有限自动机--作业
-2.4 DFA构建 子集构造法 DAF化简
-2.5 Lex
-3.1 上下文无关文法
--3.1.3 推导
-3.2 自上而分析中的文法
--3.2 上下文无关文法--作业
--3.2.3 语言和文法--作业
-3.3 自上而下分析
-3.4 自下而上分析
--3.4 自下而上分析--作业
-3.5 LR分析器
-4.1 语法制导的定义
--4.1 语法制导的定义--作业
-4.2 S属性的自下而上计算
-4.3 L属性定义
--4.3 L属性定义--作业
-4.4 L属性的自下而上计算
--4.4 L属性的自下而上计算--作业
-5.1 概述
--5.1 概述
--概述-作业
-5.2 全局栈式存储分配
-5.3 调用序列
--5.3 调用序列
-5.4 非局部名字的访问
--5.4 非局部名字的访问--作业
-6.1 中间代码生成
-6.2 作用域信息的保存
-7.1 代码生成器设计中的问题
-7.2 目标机器
--7.2 目标机器
--7.2 目标机器--作业
-7.3 基本块和流图
-7.4 一个简单的代码生成器
-8.1 基于Python的编译器框架演示视频和代码
-8.2 代码介绍
--8.2.4 SA
-8.3 SimpleJava

