3.1.3 Derivations在线视频

各位同学大家好

欢迎大家来学习语法分析这一课

接下来我们学习

上下文无关文法当中的推导的含义

推导是什么意思呢

是使我们从文法当中推出来

文法所描述的语言当中

所包含的合法串集合的动作

所以其实推导是一个动作

这个动作要做的功能是什么

是推导出来

所描述语言所包含的

合法串的集合

我们再看一下推导具体是什么

我们把产生式

看成是重写的规则

把符号串当中的非终结符

用产生式当中右部的串来进行代替

我们可以一直来进行这样的推导

一直到产生式的右部

推出来的串当中

只包含终结符

那就不能再进行推导

比如说

前面的产生式文法

我们把它进一步的简写

变成 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是完全等价的文法

我们再看文法3

它只是把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

这个产生式

整个推导的过程就结束了

我们会观察到

其实推导的过程

是隐含着这样的一颗分析树的

那么从语法分析器

设计的角度来看

我们要保证文法能推导出来

所有正确的语法表示

并且只能是这些表示

也就是说

我们要保证我们的推导过程

可以推导出所有正确的表示

只要是正确的表示

它就能推导出来

但是只是这些表示

不会包含任何一个错误的表示

这是语法分析器里边要求的

这一讲就介绍到这

谢谢大家