自底向上的语法分析及优先分析在线视频

大家好

在讨论完自顶向下的语法分析后呢

我们来看自底向上的语法分析

从推导的角度来看

自底向上的语法分析是

从输入符号串开始进行归约

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

从语法树的角度来看

它将输入符号

作为语法树的叶结点

从底往上去构造语法树

规范归约呢总是对句型当中的

最左边的可归约串来进行归约

那么与从左向右来看句型

和程序的习惯是一致的

下面呢我们来看

自底向上的语法分析的过程

例如表达式的文法的句子

i*i＋i

它对应的最右推导是这样子的

那么与之相对应的自底向上的

语法树的建立过程是这样

从叶节点最左边的i开始

规约成F再规约成为T

第二个i规约成F

此时T*F可以规约为T

T规约为E

接下来将最右边的i规约为F

再规约为T

那么这个时候

E+T最后就规约成了E

这是自底向上的语法树的建立过程

自底向上的语法分析

采用的策略呢是移进规约分析

移进呢就是将

一个终结符推进符号栈

归约呢就是将0个或多个符号

从栈当中去弹出

弹出的符号就是文法产生式右部

在根据产生式

将一个非终结符压入到符号栈当中去

移进归约的过程是规范推导

也就是说最右推导它的逆过程

所以呢它是规范归约

因此在自底向上的分析过程当中

关键是寻找句柄

也就是说

在我们刚才进行

移进规约的过程当中

我们需要确定何时可以在栈顶

出现可规约的符号串

刚才我们谈到了移进和规约

这就是我们要使用符号栈

然后把输入的符号逐一的移到栈里去

当栈顶如果出现了

某个产生式右部的时候

那么就可以把它归约成

这个产生式的左部

下面我们来看一个这样的例子

分析一下

这个输入串abbcde

是否是这个文法的句子

规约的过程是这样的

首先呢我们将a入栈

接下来将b入栈

这个时候发现

栈顶的b其实是一个句柄

b出栈归约成A入栈

接下来把第二个b入栈

这个时候我们发现

b还有A和b都是句柄

那么究竟规约哪一个呢

这是我们后面要解决的问题

那么这里呢我们先将

这个A和b出栈规约为A再入栈

接下来将c和d依次入栈

这时候在栈顶

有出现了一个可归约的串就是d

d出栈之后规约为B

再入栈接下来将e入栈

我们可以看到这个时候

栈当中的所有的字符形成了一个句柄

它们出栈规约为s再入栈

那么句子的分析就到此结束了

而且分析栈当中

只剩下了文法的开始符号S

说明这个输入串是正确的句子

那么今天呢我们先给大家介绍一种

自底向上的分析方法

就是优先分析法

优先分析法呢分为两类

一类是简单优先分析法

就是按照一定的规则

求出文法当中所有的符号

包括非终结符和终结符

它们之间的优先关系

将按照这种关系

来确定规约的过程当中它的句柄

它的优点呢就是

这是一个规范的规约分析准确规范

但是它的缺点就是

因为它比较的是所有符号它的优先集

所以分析的效率比较低

实用价值并不大

另外一种呢是

算符优先分析法

它是按照一定的原则

先求出文法当中

所有终结符之间的优先关系

只要碰到句柄就规约

它的优点就是分析的速度比较快

特别适用于表达式的分析

缺点就是

它并不是规范的规约

那么我们先来看

在简单优先分析法当中

首先来定义优先关系

如果文法是一个

已经化简之后的文法

s和t呢属于这个文法当中的符号

如果文法当中存在

这样的一个规范句型α

s和t是相邻的

那么s t与α的句柄之间的关系

必有下述情况之一

第一种情况是s在句柄当中

而t并不在句柄当中

优先关系是s大于t

第二种情况是

s和t都在规约为A的这个句柄当中

那么因此s和t的优先关系是相等的

第三钟情况是s不在句柄当中

但是t呢在规约为A的句柄当中

优先级是s小于t

那么另外呢可能还有其他的一些情况

就是s和t都不在句柄当中

那么一定会存在某一个句型

使得它们可以进入到

我们上面所说的这三种情况之一

但是如果说s和t

在任何的句型当中

都不可能相邻的出现的话

那么我们就认为

s和t是没有关系的

注意这种优先关系并不是对称的

如果文法满足下面这些条件

比如说

任意两个产生式没有相同的右部

而且文法符号符号集当中的

任何两个符号之间

最多只存在一种优先关系的话

那么这个文法就是

简单优先文法

简单优先分析算法就是

对于一个这样的用#括起来的符号串

将第一个#以及

输入的符号依次逐个的入栈

直到栈顶出现的符号

ai它的优先级要大于

下一个要输入符号ai+1

这个时候呢

ai其实就是句柄的尾符号

然后呢我们就向栈底的方向去寻找

句柄的头符号ak

那么ak-1的优先级呢要

小于ak并且ak到ai

所有的符号它的优先关系都是相等的

这样的话我们就得到了一个句柄

这个句柄就是ak…… ai

我们就可以对这个符号串进行归约了

接着呢就是不断的重复

刚才我们所说到的进栈

发现句柄的尾巴然后去寻找句柄的头

然后在进行规约这样的一个过程

直到输入的符号串

全部分析结束为止

刚才给大家介绍的简单优先分析法

那么它确定得是

所有文法符号的优先关系

所以它的分析效率是很低的

接下来我们来介绍

另外一种优先分析法

就是算符优先分析法

首先什么是算符文法呢

一个文法如果他的任意一个产生式的

右部都不含两个相邻的非终结符

也就是说这个文法

不包含下列这样的一个产生式

这个产生式当中呢

它的两个非终结符B和C是相邻的

我们称这样的文法叫算符文法

也就是说Operater Grammar

比如说大家所看到的表达式文法

就是一种典型的算符文法

产生式左边的E是运算的结果

右部的E是运算对象

而中间+ *都是运算符

算符优先分析法它的思路

就是根据文法的终结符的

优先关系来确定可归约串

对于算符优先分析法来说

规约的意义就是将一个

或者多个运算对象

与对应的这个运算符构成符号串

然后合并成一个非终结符

那么实际上就体现出了

对运算对象

进行运算符所规定的运算

那么最后规约出来的

非终结符就代表的是运算的结果

表达式的自底向上的归约过程

实质上就体现得是

表达式它的运算过程

我们来看一下

在算符优先分析法当中

它的优先关系是什么样子的呢

由A可以推导出这样的的两个句型

我们构造出了

可以规约为A的语法子树

δ可以是ε或非终结符B

大家可以看到

a和b是在同一句柄上的

他们可以同时归约

所以说a和b的优先级是相同的

比如说有产生式F→（E）

那么所以终结符（

和终结符）它的优先集是相等的

由A和B推导出的两个句型

那么构造可以规约为A

和B的语法子树

δ可以是ε或非终结符C

那么大家可以看到的出b先规约

a后规约

所以说呢a的优先级低于b

例如在我们刚才的表达式文法当中

有这样的产生式

E→E+T

那么T呢有经过若干步推导

可以得到T×F

那么因此+的优先集是小于×的

那么最后我们来看

由A和B推导出的两个句型

构造出可以规约为A和B的语法子树

δ可以是ε或非终结符C

我们看到在这个例子当中呢

a先规约b后规约

那么因此呢a的优先级是大于b的

还是我们刚才说到的表达式文法

由E→E+T

那么E呢有经过若干步推导

可以推导出

T×F

那么×的优先集是大于+的

我们先来分析一下

算符优先文法它的句子的样式

大家可以发现

算符文法它的任何句型当中

均无两个相邻的非终结符

但是可以出现两个相邻的终结符

在这个句型当中呢

如果说蓝色的字符它是句柄的话

那么ai-1的优先级小于ai的

aj的优先级大于aj+1

中间的所有的终结符的

优先级的关系是相等的

也就是说句柄是从小于关系开始

到大于关系结束

需要强调的一点是

算符优先分析法它不是规范归约

规范规约关键是寻找句柄

但是算符优先分析法它的规约的过程

关键的问题是寻找最左素短语

首先素短语呢它是短语

其中至少包含一个终结符

但是不包含其它的素短语

最左素短语顾名思义

就是出现在句型最左边的素短语

比如说在这个句型当中

T+T*F+i

我们去寻找一下它的最左素短语

首先呢我们按照最右推导

来构造出一棵这样的语法树

我们来观察一下

我们可以看到短语有T

T*F

T+T*F

i

T+T*F+i

素短语就是有T*F和i

因为它里面有一个终结符

那么最左边的素短语就是什么呢

T*F

就好比我们在

这个表达式运算的过程当中

我们先进行的是T和F的乘法运算

好了需要说明几点

素短语呢是能与前后终结符

比较优先关系的最小单位

算符优先分析法就是在不断的

寻找最左素短语进行归约的过程

下面呢我们来看一下最左素短语它的特点

那么一个算符优先文法

G它的任何这个句型的最左子串

首先呢它是素短语

那么这个素短语最左边的终结符是aj

最右边的终结符是ai

如果说这个素短语满足这些条件

aj-1优先级小于aj

ai优先级大于ai+1

aj到ai之间的终结符优先级相等

那么这个最左子串就是最左素短语

大家也可以看到

算符优先分析法它是不能够

对单个非终结符的产生式

比如说P→Q来进行归约的

接下来我们来看一下

算符优先分析算法它的大意

将输入串依此逐个存入符号栈S当中

直到符号栈顶元素Sk与

下一个待输入的符号a

存在优先关系是这样子的Sk大于a为止

那么至此

最左素短语的尾部

符号Sk就已经在

符号栈的栈顶了

那么由此往下在栈当中呢去寻找

最左素短语的头符号Sj+1

直到找到第一个小于关系为止

也就是说呢Sj

它的优先关系是小于Sj+1的

已找到最左素短语Sj+1…Sk

那么就可以规约为某一个非终结符N

并且进行相应的语义处理

算符优先文法适用范围

比简单优先文法大得多

许多程序设计语言

都可以用它来分析

而且呢它的分析表构造起来比较简单

甚至可以用手工来进行构造

算符优先分析比规范归约要快得多

因为它跳过了许多单非终结符的归约

这既是优点也是缺点

因为它忽略了

非终结符在归约当中的作用

所以说它可能会把本来

不成为句子的输入串

误认为句子

而且有些文法呢不满足

算符优先文法它的一些条件

所以必须重写

那么有的时候甚至无法重写

事实上许多符号对

之间是不存在优先关系的

而且如果说终结符它的数量多的话

优先表可能会占用非常多的空间

刚才我们给大家介绍了

自底向上的分析

策略以及它的关键点

还向大家简要的

介绍了两种优先分析法

那么这节课就到这里

谢谢大家