LL(1)文法与递归下降分析法在线视频

大家好

在上一节我们对

自上而下语法分析过程的讨论当中呢

我们发现了一些问题

比如说

左递归文法带来的无限循环

或者是由于多个产生式

它的公共左因子

造成的这种虚假匹配

需要回溯

需要把已经做好的一大堆工作

包括各种表格工作

还有语义分析等等推倒重来

对多个产生式的这种穷举的试探方法

既费时又费力

无法准确的去确定

输入串当中出错的位置在哪里

带回溯的分析方法是不确定的

那么确定的自顶向下的分析方法

它的关键思想

就是如何从文法的开始符号出发

根据当前的输入符号

或者说输入单词

唯一地确定

选用哪个产生式向下推导

去构造唯一的一棵相应的语法树

也就是说在进行确定的

自顶向下的语法分析当中的

我们理想的文法是

不包含左递归

并且无需回溯

这就是一类非常重要的文法

LL(1)文法

我们先来观察一下文法G1[S]

对于输入串

pccadd来说

对应的自顶向下的

推导过程是这样子的

S→pA→pcAd→pccAdd→pccaad

在推导的过程当中呢

可以根据最左边的非终结符

唯一的去确定

选用哪一个产生式往下去推导

也就是说呢

这个分析过程是确定的

我们来总结一下这个文法的特点

首先每一个产生式的右部

是由终结符开头的

同一非终结符

它的不同产生式的右部

是由不同的终结符来开头的

再来看第二个文法G2[S]

我们为输入串ccap

来构建自顶向下的推导过程

S是根节点

生长出了A p两个节点

按照最左推导

以及我们要匹配的字符

A生长出c和A两个节点

A继续向下生长

生长出c和A两个节点

最后A生长出a叶节点

构造语法树的工作就结束了

而且从左向右的叶节点的序列

正好是ccap

我们观察到

这个文法产生式的右部有以

终结符或者是非终结符开头的

但是没有空产生式

而且同一非终结符

它的不同产生式的右部

由不同的符号开头

虽然说在这个推导的过程当中

选用哪个产生式并不直观

但是通过判断产生式右部

推出的字符串的

第一个非终结符

那么分析的过程可能是确定的

我们来看第三个文法

这个文法有着比较明显的特点

就是某个非终结符它有空产生式

接下来我们按照最左推导

为abd来构建

自顶向下的推导过程

首先S作为根节点生长出a A

A这个节点生长出b

A d三个节点

此时这个句型当中的前缀ab

和输入串的前缀ab是匹配的

那么与d匹配的工作就交给了A

此时用ε代替A

与d匹配的任务交给了A

后面的这个符号S

S为了和句型的最后一个符号匹配

选择S→d的产生式

句子abd对应的语法树就建立好了

对于这个文法来说

也就是说对于有空产生式的

非终结符来说

关键是判定

紧随这个非终结符之后的终结符

是否可以和

句型当中正在扫描到的

这个终结符匹配

那么分析的过程可能是确定的

LL(1)文法它的必要条件之一呢

就是一定不含左递归

第二就是无需回溯

从上面的3个文法当中我们发现

如果任意非终结符的产生式

它的所有候选式

能够推出的第一个终结符

互不相同的时候

或者是说当文法有空产生式

A→ε

那么A所推导的第一个终结符

要和A后面紧跟随的这个终结符

不相同的时候

那么分析的过程可以是确定的

这一节

和大家分享一个确定的

自顶向下的分析法

就是递归下降分析法

递归下降分析法采用的是

分而治之的策略

对文法中的

每个非终结符都编写一个子程序

或者是函数

那么每个子程序它的功能

就是识别由这个非终结符

所表示的语法成分

它的代码结构

由相应的非终结符的产生式的右部来决定

用产生式右部的

终结符与输入符号来进行匹配

为每一个VN构造

相应的语法分析子程序

由于描述语言的文法

经常是递归定义的

因此相应的这组子程序

也必然以互相递归的方式来进行调用

所以这种方法呢

我们也称之为递归子程序法

或者叫递归下降分析法

现在呢我们来为这个表达式文法

构建递归下降分析器

首先呢我们来消除文法当中的左递归

我们发现呢

改造之后的这个文法呢没有左递归

而且E＇ T＇和F

每个非终结符的两个产生式

推导出的

第一个字符没有交集

那么我们就可以为每一个

非终结符构建子过程

不过首先呢我们要

定义一个match函数

这个match函数呢

是来判断函数的实参i

与当前正在扫视到的单词是不是匹配

对于E

按照产生式先调用T程序再调用E'

对于T先调用F程序再调用T'

对于E'如果读取到的单词是+

那么调用match来匹配+号

然后调用T和E'

如果候选式是ε

认为自动的获取匹配

同理我们也可以构建T'它的子过程

那么对应于非终结符F的子过程

先看读取到的符号是不是i

如果是的话

我们就选用的是F→i的候选式

否则的话要看读取到的是否是（

如果是的话用(E)代替F

匹配左括号之后就调用E过程

执行完E过程之后

看读取到的字符是不是 ）

如果不是的话说明句子是错误的

返回错误信息

递归下降分析法是直接以程序的方式

来模拟产生式产生语言的过程

它为每一个非终结符都构造了一个子程序

每一个子程序它的过程体

是按这个产生式候选项的情况展开的

遇到终结符直接匹配

遇到非终结符就调用

对应的非终结符它的子过程

那么这个分析

是从调用文法的开始符号子过程开始的

直到所有非终结符都展开为

终结符并且匹配为止

如果分析的过程当中

达到了这一步

那么表示我们的分析是成功的

否则的话表明输入当中有语法错误

递归下降分析对文法的限制就是

不能有公共的左因子

不能有左递归

那么我们来看一下

如果我们的输入串是

i1+i2*i3的话

我们采用递归下降分析法

它的分析步骤是什么样子的

从文法开始符号E

对应的程序E开始

先调用子程序T

再调用E’子程序

那么对应于T程序依次调用F和T’

当前程序单词指针扫描到的是i1

因此需要匹配i1

F推出i那么指针后移指向+

接下来进入T’程序

选择候选式ε

返回E程序调用E’程序

指针后移接着调用T程序

执行F程序匹配i2

返回T程序之后调用T’程序

指针此时指向*匹配

指针继续后移指向i3

调用F程序匹配i3

指针继续后移指向字符串的结束符

再返回T’

自动获取匹配

接下来调用E’程序候选式为ε

E’自动获得匹配程序结束

从刚才的过程当中呢我们也看到了

递归下降分析法可以根据文法的规则

直接的写出相应的识别程序

各个子程序的流程图

几乎就是文法规则的图解描述

可以保证

语法分析器它的正确性

构造的方法也非常的简单

程序的结构也十分的清晰

但是呢它的缺点也非常突出

首先如果

高级语言不允许递归的话

那么就不能使用这种方法

其次

大量相互嵌套的

递归子程序的频繁调用

占用的内存越来越多

会使分析器的运行速度相当慢

这一节我们讨论了LL(1)文法它的特点

并且还和大家分享了一种

确定的自上而下的分析法

递归下降分析法

这节课就到这里

谢谢大家