Arya

第四章 语法分析(一) note
[+] 我好喜欢我的英雄学院~抱走轰总~第四章 语法分析 note自顶向下分析概述自顶向下的分析(Top-Down...
扫描右侧二维码阅读全文
29
2019/01

第四章 语法分析(一) note

[+] 我好喜欢我的英雄学院~抱走轰总~

第四章 语法分析 note

自顶向下分析概述

自顶向下的分析(Top-Down Parsing)

  • 从分析树的顶部(根节点)向底部(叶节点)方向构造分析树
  • 可以看成是从文法开始符号S推导出词串w的过程
    这里举了一个简单的小例子

Image4-3.png

  • 每一步推导中,都需要做两个选择
    1.替换当前句型中的哪个非终结符
    2.用该非终结符的哪个候选式进行替换

那么为了回答这两个问题,引出了一个概念

最左推导(Left-most Derivation)
在最左推导中,总是选择每个句型的最左非终结符进行替换

Image4-4.png

此处的lmleft-most的简写形式

最右推导(Right-most Derivation)
在最右推导中,总是选择每个句型的最右非终结符进行替换

Image4-5.png

在自底向上的的分析中,总是采用最左规约的方式,因此把最左规约称为规范规约,而最右推导相应地称为规范推导

最左推导和最右推导的唯一性
例如对于这个分析树来说

Image4-6.png

一下几种推导方式均可

1. E=>E+E
=>E+(E)
=>E+(E+E)
=>E+(id+E)
=>id+(id+E)
=>id+(id+id)

2.E=>E+E
=>id+E
=>id+(E)
=>id+(E+E)
=>id+(E+id)
=>id+(id+id)

3.E=>lm E+E
=>lm id+E
=>lm id+(E)
=>lm id+(E+E)
=>lm id+(id+E)
=>lm id+(id+id)

4. E=>rm E+E
=>rm E+(E)
=>rm E+(E+E)
=>rm E+(E+id)
=>rm E+(id+id)
=>rm id+(id+id)

以上关于这个棵树的所有推导方法都是正确的,但是只有3是最左推导,4是最右推导,且二者均唯一

自顶向下的语法分析采用最左推导的方式

  • 总是选择每个句型的最左非终结符进行替换
  • 根据输入流中的下一个终结符,选择最左非终结符的一个候选式

接下来举了一个例子,这里强烈建议看视频,老师说的也太好了点吧(大哭)

Image4-7.png

自顶向下语法分析的通用形式

  • 递归下降分析(Recursive-Descent Parsing)
    由一组过程组成,每个过程对应一个非终结符
  • 从文法开始符号S对应的过程开始,其中递归调用文法中其他非终结符对应的过程。如果S对应的过程恰好扫描了整个输入串,则成功完成语法分析

Image4-8.png

如果当前候选式不符合表达式,那么就要退回到上一步,选择别的候选式,直到找到匹配的为止,这个过程就叫做回溯(backtracking)

回溯导致效率低下。需要回溯的分析器也叫做不确定的分析器,如果在分析过程中我们能够预测正确的产生式,那么就不需要回溯,这种分析叫做预测分析

预测分析(Predictive Parsing)

  • 预测分析递归下降分析技术的一个特例,通过在输入中向前看固定个数(通常为1)符号来选择正确的A-产生式
    可以对某些文法构造出向前看k个输入符号的预测分析器,该类文法有时也称为LL(k)文法类
  • 预测分析不需要回溯,是一种确定的自顶向下分析方法

文法转换

首先举了一个例子:
文法G

S->aAd|aBe
A->c
B->b

输入:abc

但此时出现了一个问题,因为S可以转换成两个不同的候选式且开头字母均为a,所以此时哦们不能确定要选择哪一个,于是产生了回溯

换言之,当同一个非终结符的多个候选式存在共同前缀,将导致回溯现象

接下来又举了一个例子
文法G

E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|id

输入:id+id*id

这时容易产生如下的死循环

E=>E+T
 =>E+T+T
 =>E+T=T
 =>……

这里老师补充了几个知识点

  • 含有A->Aa形式产生的文法称为是直接左递归的(immediate left recursive)
  • 如果一个文法中有一个非终结符A使得对某个串a存在一个推导A=>+ Aa,那么这个文法就是左递归
  • 经过两步或两步以上推导产生的左递归称为是间接左递归

所以,左递归文法会使递归下降分析器陷入无限循环

这里我们就需要消除直接左递归

假设我们存在这样的一个候选式
A->Aα|β(a≠ε,β不以A开头)
我们可以根据A的第一个候选式,推导出

A=>Aα
  =>Aαα
  =>Aααα
  ……
  =>Aα……α
  =>βα……α

我们可以得出上面对应的正则表达式就是
r=βα*

因为不管上面的式子怎么扩展,我们得到的最终结果都是β为开头的表达式,所以这里我们将
A->Aα|β改写为A->βA',这里的A'是一个新的非终结符,它的功能是可以产生若干个α
所以A'->αA'|ε,由此我们可以推导出

A'=>αA'
  =>ααA'
  =>αααA"
  ……
  =>α……αA'
  =>α……α

事实上,这种消除的过程就是把左递归转换成了右递归

所以上面的问题可以进行如下的改造

Image4-9.png

那么我们由此可得消除左递归的一般形式

Image4-10.png

这里我们也可以得出消除左递归是要付出代价的——引进了一些非终结符和ε_产生式

那么怎么消除间接左递归
例:

S->Aa|b
A->Ac|Sd|ε

1.将S的定义带入A-产生式,得:

A->Ac|Aad|bd|ε

2.消除A-产生式的直接左递归,得:

A->bdA'|A'
A'->cA'|adA'|ε

Image4-11.png

所以,让我们再回到这个例子中
文法G

S->aAd|aBe
A->c
B->b

我们可以通过提取左公因子(Left Factoring)的方式来改写上述的式子

S->aS'
S'->Ad|Be
A->c
B->b

这个方法通过改写产生式来推迟决定,等读够了足够多的输入,获得足够信息后再做出正确的选择

这里是提取左公因子的算法

Image4-12.png

其中γi表示所有不以α开头的产生式体;A'是一个新的非终结符。通过不断应用这个转换,直到每个绯红姐夫的任意两个产生式体都没有公共前缀为止

LL(1)文法

递归下降分析可能会遇到回溯,从而影响效率,如果在分析的每一步都可以做出正确的选择就无需回溯,这样的分析就是预测分析

预测分析法的工作过程:
从文法开始符号出发,在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a,选择正确的A-产生式。为保证分析的确定性,选出的候选式必须是唯一的,而LL(1)文法可以使用这种技术

那么首先从s文法开始讲起

S_文法
s_文法(简单的确定性文法)的定义:

  • 每个产生式的右部都以终结符开始
  • 同一非终结符的各个候选式的首终结符不同s文法不含ε产生式

那么如果允许S_文法中包含ε产生式,会产生什么问题呢?
这里举了一个小例子

Image4-13.png

可见我们并不能推出ade,那么我们什么时候可以使用ε产生式呢?

如果当前某非终结符A与当前输入符a不匹配时,若存在A->ε,则可以通过检查a是否可以出现在A的后面来决定是否使用产生式A->ε(若文法中无A->ε,则应报错)

接下来引出了一个新的概念

Image4-14.png

依然是刚才那个例子,我们可以得出

Image4-15.png

Follow(B)={a,c}
为了叙述的方便,我们又引入了一个新的概念:

产生式的可以选集
产生式A->β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为SELECT(A->β)

  • SELECT(A->aβ)={a}[只有遇到终结符a时,才可以使用产生式A->aβ]
  • SELECT(A->ε)=Follow(A)[只有遇到Follow(A)中的元素时,才可以使用产生式A->ε]

所以当产生式互不相交时,我们就可以给出确定的分析,因此给出了q_文法的定义

q_文法

  • 每个产生式的右部或为ε,或以终结符开始
  • 具有相同左部的产生式有不相交的可选集(q_文法不含右部以非终结符未开始的产生式)

因此引入了串首终结符的概念

Image4-16.png

有了串首终结符的概念,我们可以重新定义可选集

  • 如果ε∉FIRST(α),那么SELECT(A->α)=FIRST(α)
  • 如果ε∈FIRST(α),那么SELETCT(A->α)=(FIRST(α)-{ε})∪FLLOW(A)

如果G是LL(1)的,当且仅当G的任意两个具有相同左部的产生式A->α|β满足下面的条件:

Image4-17.png

LL(1)文法的含义:

  • 第一个L表示从左向右扫描输入
  • 第二个L表示产生最左推导
  • "1"表示在每一步中只需要向前看一个输入符号来决定语法分析动作

FIRST集和FOLLOW集的计算

计算文法符号X的FIRST(X)

  • FIRST(X):可以从X推导出所有的串首终结符构成的集合
  • 如果X=>*ε,那么ε∈FIRST(X)

这里举了一个例子,老师讲的特别详细,强烈建议看原视频

Image4-18.png

这里也给出了FIRST集的算法

Image4-19.png

这里也给出了计算X1X2……Xn的FIRST集算法

Image4-20.png

计算非终结符A的FOLLOW(A)

这里给出了关于FOLLOW(A)的定义:

Image4-21.png

以及继续举了一个例子

Image4-22.png

接下来计算FOLLOW集

首先,文法的开始符号E本身就是一个句型,同时也是这个句型的开始符号,所以我们将$加入到FOLLOW(E)中,则有FOLLOW(E)={$}

根据①我们可以得出E'的所有终结符可以跟在T的后面,所以我们将E'中的所有终结符,即+加入到T的FOLLOW集中,即FOLLOW(T)={+}

由于E'的FIRST集中存在ε,也就是说E可以推出ε,那么能跟在E后面的终结符也可以跟在T后面,也就是说我们要将FOLLOW(E)中的符号添加到FOLLOW(T)中,所以现在的FOLLOW(T)={+ $}

接下来看E'E'是①中的右部最后一个符号,也就是说能跟在E后面的符号,也能跟在E'后面,因此,我们将FOLLOW(E)中的元素添加到FOLLWO(E')中,即FOLLOW(E')={$}

接下来看②,因为②中的产生式位置与①类似,所以相当于分析结果和刚才一致,跳过

之后是③,可以看到T'紧跟在F后面,所以我们可以将T'FIRST集中的*加入到F的FOLLOW集中,即FOLLOW(F)={*}

又因为T'可以推导出空串,那么可以跟在T后面的终结符就可以跟在F后面,所以将FOLLOW(T)中的元素添加到FOLLOW(F)中,FOLLW(F)={* + $ }

接下来看T'T'是③中最后一个符号,所以可以跟在T后面的符号也可以跟在T'后面,因此将FOLLOW(T)中的元素添加在FOLLOW(T')中,即FOLLOW(T')={+ $}

在④中,FT所处的位置与③一致,跳过

最后是⑤,F中有非终结符E,而E后面有终结符),所以将)加入到FOLLOW(E)中,即FOLLOW(E)={$ )}

又因为FOLLOW(E)中添加了符号),所以依赖于FOLLOW(E)FOLLOW(E')中也要增加符号,即为FOLLOW(E')={$ )},所以依赖FOLLOW(E)'FOLLOW(T)中也要增加),即FOLLOW(T)={+ $ )},最后,依赖FOLLOW(T)FOLLOW(F)也要增加),即FOLLOW(F)={* + $}

综上,得出完整结果(真的打字打的好累,趴桌)

Image4-23.png

最后老师也给出了算法

Image4-24.png

当然,你以为这样结束了??想得美,你把SELECT集放在哪里了?

这里举了一个例子

Image4-25.png

其中,当表达式右部第一个符号为终结符,则直接将终结符加入SELECT集中;如果当表达式右部第一个符号为非终结符,则将该非终结符的FIRST集加入SELECT集中;如果当表达式右部第一个符号为ε时,则将表达式左部非终结符的FOLLOW集加入SELECT集中。

最后检查上述的SELECT集,其中(2)和(3)、(5)和(6)、(7)和(8)有相同的左部,但是它们的SELECT集互不相交,所以上述的表达式文法为LL(1)文法

因此我们可以构造这个表达式的预测分析表

Image4-26.png

最后做了一个小总结,LL(1)文法的分析方法有

  • 递归的预测方法
  • 非递归的预测方法

递归的预测分析法

递归的预测分析法是指:在递归下降分析中,编写每一个非终结符对应的过程时,根据预测分析表进行产生式的选择

Image4-27.png

接下来举了一个例子

Image4-28.png

因为除了(4)、(7)以外的语句左部开头都是终结符,所以对应的SELECT集很好确定,于是现在分析(4)和(7),在(4)中,我们可以得出SELECT(4)的结果应该是FOLLOW(DECLISTN)所以我们根据(1)得出了FOLLOW(DECLISTN)={:},即SELECT(4)={:},同理得出SELECT(7)={end}

同时图中也给出了非终结符的程序实现方式的伪代码模板,根据这个模板,我们可以得出以下的知识点

接下来给出了PROGRAM的对应过程的伪代码

Image4-29.png

DECLIST对应过程的伪代码

Image4-30.png

DECLISTN对应过程的伪代码

Image4-31.png

余下的我就不贴出来了,大致都是一样的

非递归的预测分析

非递归的预测分析不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析

下面是自动机的模拟图

Image4-32.png

这个自动机也叫作下推自动机,这个自动机和有穷自动机是不同的,多了一个栈(也叫下推存储器),且有穷自动机不具备存储功能

接下来举了一个例子展示了预测分析表的执行方式

Image4-33.png

这里建议配合视频食用,老师解释的很详细(赞美这位老师)

下面给出的就是表驱动预测分析法的算法,也就是上面解法

Image4-34.png

递归的预测分析法与非递归的预测分析法的比较

递归的预测分析法非递归的预测分析法
程序规模程序规模较大
不需载入分析表
主控程序规模小
需载入分析表(表较小)
直观性较好较差
效率较低分析时间大约正比于待分析程序的长度
自动生成较难较易

预测分析法实现步骤
1)构造文法
2)改造文法:消除二义性、消除左递归、消除回溯
3)求每个变量的FIRST集和FOLLOW集,从而求得每个候选式的SELECT集
4)检查是不是LL(1)文法。若是,构造预测分析表
5)对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法

预测分析中的错误检测

以下两种情况可以检测到错误

  • 栈顶的终结符和当前输入符号不匹配
  • 栈顶非终结符与当前输入符号 在预测分析表对应相中信息为空

预测分析中的错误恢复

恐慌模式

  • 忽略输入中的一些符号,直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元
    但是这种方式恢复起来通常比较慢,如果没有出现合法的同步词法单元,分析器会一直搜索下去
    故,其效果依赖与同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
  • 如果终结符在栈顶而不能匹配,一个简单的办法就是弹出此终结符

接下来用一个例子解释了这些

Image4-35.png

分析表的使用方法

  • 如果M[A,a]是空,表示检测到错误,根据恐慌模式,忽略输入符号a
  • 如果M[A,a]是synch,则弹出栈顶的非终结符A,试图继续分析后面的语法成分
  • 如果栈顶的终结符和输入符号不匹配,则弹出栈顶的终结符

Image4-36.png

Last modification:January 29th, 2019 at 09:09 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment