当前课程知识点:编译技术 > 第三章 语法分析 > 3.1 上下文无关文法 > 3.1.3 推导
各位同学大家好
欢迎大家来学习语法分析这一课
接下来我们学习
上下文无关文法当中的推导的含义
推导是什么意思呢
是使我们从文法当中推出来
文法所描述的语言当中
所包含的合法串集合的动作
所以其实推导是一个动作
这个动作要做的功能是什么
是推导出来
所描述语言所包含的
合法串的集合
我们再看一下推导具体是什么
我们把产生式
看成是重写的规则
把符号串当中的非终结符
用产生式当中右部的串来进行代替
我们可以一直来进行这样的推导
一直到产生式的右部
推出来的串当中
只包含终结符
那就不能再进行推导
比如说
前面的产生式文法
我们把它进一步的简写
变成 E 可以产生 E+E | E×E | (E) | -E | id
那么我们可以用这个产生式来进行推导
推导
我们就写成两个横线这样的
双箭头
推导
我们就把它写成两个横线
这样的箭头
双箭头
E 可以推导 -E
然后 负号当中的 E
进一步可以推导成 (E)
所以最开始的 E
就推导成了 -(E)
进一步的括号当中的E
可以推导为 E+E
然后第一个 E 可以推导成id
第二个 E 也可以推导成id
最终原来的 E
就推导成了 -( id + id )
整个串当中
只有产生式右部的串
只有终结符
E 这一步推导就结束了
所以其实推导就是我们从文法的
开始符号 E 开始
推导出符合语法的句子来
那么什么是句子呢
如果我们推导出来的串当中
不包含任何的非终结符
也就是它都是终结符组成的串
它就是一个句子
那么句型是我们在推导的过程中
出现的这些串
我们把它叫做一个句型
上下文无关文法
描述的集合
我们就把它叫做
上下文无关文法对应的语言
我们还有一个概念
叫等价的文法
稍后来讲
我们再看一下
我们使用S推导*α
表示零步或者多步的推导
S可以推导+w
那么加号的推导表示的是
一步或多步的推导
我们看直接推导的
这个步骤的意思
A可以产生γ
是文法 G 的一个产生式
那么直接推导的意思就是
αAβ 在这一步
α 和 β 不变
而 A 推导成 γ
所以 αAβ
就可以推导成 αγβ
我们来看一下 文法G
S→ 0S1 S→01
那么0S1当中的S可以进行直接推导
推导为0S1
也就是0S1可以推导为00S11
那么类似的,00S11可以直接推导
得到000S111,剩下的类似
当然S也可以直接推导为0S1
下面我们看一下等价的文法的含义
文法1当中
S→aAb A→ab A→aAb A→ε
那么文法2和文法1
只是产生式顺序不同
在产生式集合当中
我们其实是不强调顺序
所以文法1和文法2是完全等价的文法
我们再看三文法
它只是把A产生式
给它用了简写的方法
E可以产生 ab | aAb | ε
那么它和文法1、文法2
仍然是等价的文法
这一页当中
这三个文法都是等价的文法
接下来我们再看一下
最左推导和最右推导的含义
比如说
我们在进行推导的时候
E推导成 -E
再推导成-(E)
然后其中的E
推导成 E+E
到这一步
我们是推导左边的 E
还是推导右边的 E
如果我们每一步的推导当中
都是从最左边的一个非终结符
开始推导
那么这个就被叫做最左推导
像我们这里边列出的例子
E在这一步
去推导左边的E
所以就可以推导成 -(id+E)
然后在最后得到 -(id+id) 结束
那么我们还可以选择
每一次推导的时候
推导最右边的那一个非终结符
这就被叫做最右推导
也被叫做规范推导
同样的步骤
我们在这一步
可以将它推导成
E可以推导 -(E+id)
然后再推导得到 -(id+id)
我们再观察一下
最左推导和最右推导
它们之间的分析树是不不一样的
大家看最左推导
就是左边的样子
到这个时候分析树
是最左边的 E 长出了叶子
而最右推导
是在这一步右边的E
长出了id这个叶子
当然最终得到的分析树是一样的
那么我们再看一下
文法推导
和分析树之间的关系
针对一个表达式
我们语法分析的目标是什么呢
我们给定一个句子
比如说id+id×id
我们怎么判断这个句子
是满足文法所描述的语法规则呢
也就是说
你给出一个句子
这个句子就相当于是
我们的源程序
经过词法分析
处理之后得到的句子
比如说id+id*id
这是经过词法分析处理之后
得到的这样的一个句子
怎么样判断句子
是不是我们这门语言所描述的语法规则
也就是它在语法上是符合我们程序要求的呢?
怎么判断呢?
我们的判断方法就是
判断一下
是不是存在着一个推导
使得我们可以从文法的开始符号
推导出来
给定的句子
如果能推导出来
就说明它是满足文法要求的
如果不能推导出来
就说明这个句子
不满足
这个文法
所描述的语法规则
就是有语法问题的
我们再来看一下推导过程
从E出发
如何得到id+id*id这样的一个串呢
首先从E出发
我们将它推导为E+E
我们用到了产生式E
可以产生E+E
然后我们将左边的 E
推导为id
我们用到了 E→id 这个产生式
接下来我们将右侧E
推导成E*E
我们用到了 E→E*E 这个产生式
假设我们采用最左推导
那么左边的E继续推导成id
我们又用到了 E→id 这个产生式
然后右边的
最右边的E
推导成id
我们再一次用到了 E→id
这个产生式
整个推导的过程就结束了
我们会观察到
其实推导的过程
是隐含着这样的一颗分析树的
那么从语法分析器
设计的角度来看
我们要保证文法能推导出来
所有正确的语法表示
并且只能是这些表示
也就是说
我们要保证我们的推导过程
可以推导出所有正确的表示
只要是正确的表示
它就能推导出来
但是只是这些表示
不会包含任何一个错误的表示
这是语法分析器里边要求的
这一讲就介绍到这
谢谢大家
-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

