当前课程知识点:编译技术 > 第三章 语法分析 > 3.3 自上而下分析 > 3.3.2 LL(1)文法
各位同学大家好
今天我们继续来学习语法分析
这节课我们来学习
语法分析中的LL1文法
LL1文法是在first集和follow集定义的基础上
加了两个条件
我们来看一下这两个条件
假设有两个产生式
A可以产生α或者β
对于LL1文法
它的要求有两点
first(α)和first(β)相交等于空
或者如果在β可以推导为空串的情况下
我们要求first(α)和follow(A)相交等于空
满足了这两点
我们可以知道
在进行自上而下推导的时候
可以顺利的决定
每一步是把A推导为α
还是把A推导为β
当然我们其实也可以观察到
LL1文法自然的 它包含一些明显的性质
比如说不包含公共左因子
它不是二义性的
肯定也不含有左递归
比如说
对于我们之前看到的这个例子
我们来判断一下
它到底是不是LL1文法
对于E产生式TE'
T产生式FT'
对于这两条产生式来说
它其实不涉及到LL1中
这两个条件的判定
所以我们重点需要判定的是
E'产生+TE'或者空串
T'产生 *FT'或者空串
对于F产生(E)或者id
很明显的
我们可以在任何一个情况知道
是将F推导为带左括号的产生式
还是将它推导为id
所以我们只需要判断这两个产生式
我们根据之前求出的
First集和follow集
可以看到
对于产生式 E产生+TE'
或者空串来说
由于E'可以推导为空串
所以我们其实需要判定
first(+TE')和follow(E')
相交是不是为空
那么first(+TE') 它的集合等于+
而follow(E')
我们之前求得的结果
等于右括号 ) 和$
所以它们俩相交是为空的
对于T'产生*FT'或者空串来说
我们仍然需要去判定
First(*FT')和follow(T')相交是不是为空
根据之前的结果
First(*FT')等于 *号
follow(T')
等于加+ ) $
所以它们相交为空
根据这两个产生式
我们可以判断出来
这个文法是LL1文法
接下来我们可以看到
如果我们再求出一个文法的
First集和follow集之后
假设它满足我们的要求
是LL1文法
那么我们就可以来进行
自上而下的预测分析
我们通过构造非递归的预测分析表
可以来进行构造语法树
分析一个串
是不是属于文法
我们看在进行自上而下分析的时候
其实是有两种分析方法
一种是递归下降的预测分析方法
一种是非递归的预测分析方法
稍后我们会学习
非递归的预测分析方法
我们需要去构造
非递归的预测分析表
然后再来进行非递归的预测分析
关于LL1文法的部分
我们就学习到
这一小节结束
谢谢大家
-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