上下文无关文法的句型分析在线视频

同学们好

这节课给大家介绍

上下文无关文法的句型分析

句型分析就是识别一个符号串

是否为某个文法句型

进一步说

就是当给定一个符号串时

试图按照文法的规则为符号串构造

推导或构造语法树

以此识别它是不是这个文法的句型

当符号串全部由终结符组成时

那就是识别它是不是文法的句子

在编译系统实现中

把完成句型分析的程序

称为分析程序或识别程序

分析算法又称为识别算法

常见的分析方法有两种

一种是自顶向下的分析方法

一种是自底向上的分析方法

自顶向下的分析方法

是从文法的开始符号出发

反复使用各种产生式

寻找“匹配”的输入符号串的推导

自下而上的方法

是从输入符号串开始

逐步进行"归约"

直至归约到文法的开始符号

来看这里这个文法

我们要识别输入串

cabd是不是这个文法的句子

大家看

这里是自顶向下的推导过程

再来看 这里是自下而上的规约过程

下面我们分别来介绍

先看自顶向下的分析过程

对于一个文法而言

从文法的开始符号

到某一个句型的推导过程

可能不唯一

例如说这个文法

我们来看句子 i+i*i 的推导过程

我们这里就给出了

三种从E到 i+i*i 的推导情况

为了让计算机能够自动地进行推导

通常我们只考虑

最左或者是最右推导

这里的第(2)种是最左推导

第(3)种是最右推导

大家可以看到

从形式上

如果从符号串

到符号串β的推导序列

是这种情况

那么总有

x是终结符时

那么我们称之为是最左推导

总有y是终结符时

我们称之为是最右推导

最左推导

或者是最右推导得到的句型

我们称之为左句型或者是右句型

最右推导我们称之为规范推导

右句型就是规范句型

每个句子都有相应的最左或者最右推导

因此 句子即是左句型也是右句型

但是 并不是所有的句型

都有最左和最右推导

比方说这个文法G

那么E + E+i*T

它即不是左句型

也不是右句型

因为最左或者最右推导

推导不出来这个句型

对于给定的符号串w

采用自顶向下的分析来判断

w是不是这个语言的句子

它常见的方法就是

试图建立从文法的开始符号S

到w的最左推导

显然 每一步推导时

对应于最左非终结符相应的产生式

可能会有多个

如果没有特殊的办法

我们只能一个一个地去试探

所以 推导过程可能是带回溯的

比如说文法G

那推导句子i+i*i的过程中

由E开始

我们可以选择的规则就有两个

一个是E→E+T

一个是E→T

所以这个过程是需要试探与回溯的

为了提高效率

在自顶向下的语法分析过程中

我们尽可能的避免回溯

我们再来看

自底向上的语法分析方法

自底向上的语法分析就是从

给出的符号串w出发

试图以与推导相反的方向

为w建立一个规范规约

最终得到文法的开始符号

推导的逆过程称作归约

最右推倒的逆过程就是规范规约

比如说文法G

句型i+i*i的最右推导是这样子的

大家可以看

从E一直运用规则推导到句子i+i*i

归约就是从右边的i+i*i

一路归约到文法的开始符号E

所以 归约我们可以描述为

当有符号串β α δ

文法规则中有一条产生式

A定义为α

那么把符号串β α δ中的子串α

替换为产生式左部的符号A

得到一个新的符号串β A δ

这样的一步动作

我们称为进行了一步归约

例如 这里文法G中的符号串

F+i*i

这其中的F

我们可以按照产生式T定义为F

归约为T

我们可以得到一个新的符号串

T+i*i

如果从给定的符号串w出发

我们一步一步将其进行归约

最终能够得到文法的开始符号

那么说明w

就是这个文法定义的一个句子

归约成功

否则的话 归约失败

如果归约的每一步

都归约的是当前符号串中

最左边的

某个产生式的右部

那么我们称

这个归约是规范归约

也就是最左归约

下面我们来看三个概念

短语 直接短语和句柄

假如文法G[S]中

从文法开始符号

可以推导出句型αAδ

A可以推导出β

那么我们就称β是句型αβδ

相对于非终结符A的短语

如果A定义为 β是一个产生式

那么则称β是句型α β δ

相对于A 的直接短语

一个句型的最左边的直接短语

我们称之为这个句型的句柄

我们来看这个文法

这里是从开始符号E 推导出句型

E+T*F+i 的语法树

E可以经过若干步

推导到E+T+i

因为有一条规则T->T*F

所以推导出来=> E+T*F+i

那么T*F

就是句型 E+T*F+i

相对于TF的直接短语

我们从语法树上

还可以清楚地看到

其中句型E+T*F+i中的

短语还有 i

E+T*F+i

直接短语就是T*F

还有一个i

句柄自然是最左边的直接短语了

就是T*F

那我们通过定义可以知道

直接短语也是短语

但短语不一定是直接短语

从语法树中可以看到

句型E+T*F+i中E+T

绝不是它的一个直接短语

因为虽然E

因为虽然有规则E->E+T

但是不存在从E到E*F+i的推导

自底向上分析过程中

主要的问题就是寻找句柄

每一步归约就是将句柄进行归约

这节课就讲到这里

谢谢大家