Arya

第四章 语法分析(二) note
[+] 竟然出乎预料的下雪了,昨天沉溺钢之炼金术师一整天,啊,摸鱼真快乐(趴桌[+] 出门买点坚果好了,学习学的脑...
扫描右侧二维码阅读全文
31
2019/01

第四章 语法分析(二) note

[+] 竟然出乎预料的下雪了,昨天沉溺钢之炼金术师一整天,啊,摸鱼真快乐(趴桌
[+] 出门买点坚果好了,学习学的脑阔疼

第四章 语法分析(二) note

自底向上的语法分析

  • 从分析树的底部(叶节点) 向顶部(根节点)方向构造分析树
  • 可以看成是将输入串w归约为文法开始符号S的过程
  • 的语法分析采用最左推导方式
  • 的语法分析采用最左归约方式(反向构造最右推导)
  • 自底向上语法分析方式的通用框架:
    移入-规约分析(Shift-Reduce Parsing)

接下来举了一个移入—归约分析的例子

Image4-2-1.png

每次规约的符号串称为"句柄"
站内符号串+剩余输入="规范句型"

移入—归约分析的工作过程

  • 在对输入串的一次从左到右扫描的过程中,语法分析器将零个或多个输入符号移入栈的顶端,直到它可以对栈顶的一个文法符号串β进行归约为止
  • 然后,它将β归约为某个产生式的左部
  • 语法分析器不断地重复这个循环,直到它检测到一个语法错误,或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时,语法分析器停止运行并宣称成功完成了语法分析)为止

移入—归约分析器可采取的4种动作

  • 移入:将下一个符号移到站的顶端
  • 规约:被规约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端,并决定用哪个非终结符来替换这个串
  • 接收:宣布语法分析过程成功过完成
  • 报错:发现一个语法错误,并调用恢复子例程

移入—归约分析中存在的问题
这里简单的举了一个例子

var iA,iB:real

虽然这个语句是该文法的一个合法表示形式,大还是利用这样的规约方式却无法获得正确的答案

Image4-2-2.png

实际上我们在$ var <IDS>,iB这一步的归约出了问题,因为这里我们不仅可以通过第(2)个式子将iB规约成<IDS>,我们也可以t通过第(3)个式子将<IDS>,i规约成为<IDS>

于是经过这样的修改,我们可以得出正确的规约方式

Image4-2-3.png

这里造成错误的原因:错误地识别了句柄

这里简单的分析一下错误的原因(红色表示在栈中,蓝色表示剩余输入)

Image4-2-4.png

在这里我们可以看出,iB虽然是产生式(2)的右部,但是在分析树中,iB并不是某个高度为2的子树的边缘,因此iB并不是当前举行的直接短语,而实际上这棵树存在两棵高度为2的子树
1:<IDS>->{<IDS> , iB}
2:<T>->{real}
在自底向上分析中我们采取的是最左归约,因此这里的句柄,实际上是当前句型的最左直接短语,且第2句在剩余输入中,所以我们选择第一句作为归约方式,故只有这样才可以得出正确答案

LR分析法

LR文法
LR文法是最大的,可以构造出相应移入—归约语法分析器的文法分类

  • L:对输入进行从左到右的扫描
  • R:反向构造出一个最右推导序列
    为了准确的识别句柄,LR分析器需要向先查看k个符号的LR分析,这样的分析器称为LR(k)分析器

对于大多数描述计算机程序设计语言的上下文无关文法来说,最多向前查看1个输入符号就足够了,因此k=0k=1这两种情况具有实践意义,当省略(k)时,表示k=1

LR分析法的基本原理
上一节我们举了一个关于自底向上分析中可能存在的问题,那么可以得出自底向上分析的关键问题是在于如何争取地识别句柄

句柄是逐步形成的,用"状态"表示句柄识别的进展过程。

这里举了一个小例子解释了一下每个状态

Image4-2-5.png

可以看出,LR分析器基于这样的一些状态来构造自动机进行句柄的识别

LR分析器的结构
这里给出了LR分析器的总体结构

Image4-2-6.png

可以看出,LR分析器与移入—归约分析器不同的是,LR分析器还包含一个与符号栈平行的状态栈

接下来举了一个例子讲解了LR分析表的结构

Image4-2-7.png

GOTO表中对应着该语法的非终结符,GOTO表中得每一项表示在某一状态遇到某一非终结符进入的后继状态

这里举了一个例子
假设我们输入

b a b

接下来我来手动叙述一下这个归约过程以及如何使用分析表

//初始
栈                   剩余输入
0                   
$                   bab$

初始时,我们先将待分析的输入串放入到输入缓冲区中,后面连接上结束符$,初始的时候,栈中只有一个状态0,符号栈中只有一个符号标记$

接下来我们开始分析,首先从初始状态0号开始,当前的输入符号是b,那么我们通过查表得s4,这里表示一个移入动作,即将b移入到栈中,并且进入到状态4,得

栈                   剩余输入
04                  
$b                   ab$

那么状态4遇到当前输入符号a,得到r3,表示一个归约动作,即,利用号产生式进行归约,得到B,将b出栈,B进栈

栈                   剩余输入
0                  
$B                   ab$

此时状态栈顶为状态00遇到刚归约出的B,通过查表得,进入到状态2,即将状态2进栈

栈                   剩余输入
02                  
$B                   ab$

此时状态2遇到当前的输入符号a时,得到s3,移入a后进入状态3,接下来状态3遇到b,为s4,即移入b进入状态4

栈                   剩余输入
0234                  
$Bab               $

之后状态4遇到$,查表得r3, 利用产生式进行归约,将b归约为B,并将b连同状态4一起出栈后,B进栈

栈                   剩余输入
023                  
$BaB               $

此时状态3遇到刚归约出的B,进入到状态6

栈                   剩余输入
0236                  
$BaB               $

栈顶的状态6遇到$时,得r2,调用产生式进行归约,并将aB连同其对应的状态36一起出栈,将B进栈

栈                   剩余输入
02                  
$BB               $

接下来状态2遇到刚规约出的B,进入状态5

栈                   剩余输入
025                  
$BB               $

状态5遇到$r1,利用产生式进行归约后

栈                   剩余输入
0                  
$S                  $

此时状态0遇到S进入状态1

栈                   剩余输入
01                 
$S                  $

最后状态1遇到$,得acc即为归约结束,成功接收。

接下展示了LR分析器的工作过程

Image4-2-8.png

Image4-2-9.png

Image4-2-10.png

利用伪代码解释了一下LR分析算法

Image4-2-11.png

那么如何构造给定文法的LR分析表呢?
我们有以下4种方法

  • LR(0)分析
  • SLR分析
  • LR(1)分析
  • LALR分析

接下来一一介绍

LR(0)分析法

LR(0)项目
右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目(简称为项目)

A=α·β

例如

Image4-2-12.png

可以看出上图中有4个项目,每个项目描述了句柄识别的状态。对于产生式A->ε 只产生一个项目A->·

增广文法(Augmented Grammar)
如果G是一个以S为开始符号的文法。则G的增广文法G'就是在G中加上新开始符号S'和产生式S'->S而得到的文法

举了一个例子

Image4-2-13.png

可以看出上面两个式子是等价的,那么问题来了,为什么要引入增广文法呢?

实际上引入这个新的开始产生式的目是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态。例如,上图左边的文法开始符号E出现在了两个产生式的左部,而右边的开始符号E'仅出现在一个产生式的左部。

下面举了一个例子,为5个产生式以及对应的项目

Image4-2-14.png

Image4-2-15.png

接下来介绍了一下后继项目(Successive Item)

  • 同属于一个产生式的项目,但原点的位置只相差一个符号,则称后者是前者的后继项目
  • A->α·Xβ的后继项目是A->αX·β

接下来介绍了上述15个项目中,存在的等价项目

Image4-2-16.png

也就是说,当一个项目的'·'后面存在非终结符时,这个项目就存在着等价项目。我们可以把所有等价项目组成一个项目集(I),称为项目集闭包(Closure of Item Sets),每个项目集闭包对应着自动机的一个状态。

接下来举了一个例子

Image4-2-17.png

得出了文法的转换图和转换表,建议看视频,超级详细的讲解,其中有趣的是I4,I5,I6因为都是归约状态,所以对应的都是I0中的产生式,所以无论遇到什么符号,都是对应的'rn'的形式(n为该状态对应的产生式)

LR(0)分析表构造算法

这里给出了CLOSURE()函数的数学定义

Image4-2-18.png

这里是伪代码的表示形式

Image4-2-19.png

GOTO()函数的数学定义

Image4-2-20.png

伪代码表示形式

Image4-2-21.png

从文法的初始项目开始,利用CLOSURE()函数和GOTO函数就可以构造LR(0)自动机的状态集

Image4-2-22.png

这里给了LR(0)分析表构造算法

Image4-2-23.png

LR(0)自动机的形式化定义

Image4-2-24.png

此处F表示终止状态

那么接下来研究LR(0)分析过程中的冲突,举了一个例子(例4-1)

Image4-2-25.png

这里的I2存在冲突现象。根据I2中的两个项目

E->T· # 项目1
T->T`*F #项目2

我们可以看出项目1是个归约项目,无论遇到什么输入符号,我们都进行归约动作,把栈顶的T规约为E;而第2个项目当输入符号为*时,采取移入操作,并转入状态7,所以在遇到输入符号为*时,产生冲突。这样的冲突叫做“移进/归约冲突”

Image4-2-26.png

除了“移进/归约冲突”以外,还有“归约/归约”冲突,这里也举了一个例子(例4-2)

Image4-2-27.png

在I2中,有两个项目

B->·
T->·

这两个项目都是归约状态,所以我们并不知道应该选择哪一个项目,此外这个状态中还有移入项目,与归约项目也是存在着冲突的

所以我们得出这样的结论:
如果LR(0)分析表中没有语法分析冲突,那么给定的文法就称为LR(0)文法

所以由此可见,不是所有的CFG(上下文无关文法)都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法

SLR分析

上一节说了,LR(0)分析容易产生冲突,而产生中途的原因是因为k=0,也就是说,LR(0)分析在构造项目时,向前查看0个符号,也就是说没有向前查看符号,即未考虑文法符号的上下环境

那么接着上一节的例4-1一个冲突的例子

Image4-2-28.png

我们可以从FOLLOW集得知,*不在FOLLOW(E)中,也就是说,即使归约出E,后面也不可能连着*,所以说这里不应该进行归约。

接下来就引入了SLR分析

Image4-2-29.png

通过以上的分析我们可以看出,SLR分析向前查看了一个符号就可以确定是否向前归约,以及如何向前归约,也就是k=1,所以SLR分析也叫作SLR(1)分析,这里的Ssimple

这样我们可以得出例4-1的SLR分析表

Image4-2-30.png

LR(0)分析表不同的是,SLR中的归约状态只有在遇到FOLLOW集中的元素才进行归约动作

这里是例4-2的SLR分析表

Image4-2-31.png

这里给出了SLR分析表的构造算法

Image4-2-32.png

如果给定文法的SLR分析表中不存在有冲突的动作,那么该文法称为SLR文法

那么,你以为SLR分析就是完美的了吗?当然不是,SLR分析中也存在冲突。

Image4-2-33.png

那么接下来就要引入LR(1)分析法

LR(1)分析法

LR(1)分析法的提出

首先先来看一下SLR分析法存在的问题:

  • SLR只是简单地考察下一个输入符号b是否属于归约项目A->α相关联的FOLLOW(A),但b∈FOLLOW(A)只是归约的α的一个必要条件,而非充分条件
    由上可以看出,FOLLOW集只可以帮我们帮排一些不合理的归约,但没有办法确保正确的归约

实际上对于产生式A->α的归约,在不同使用位置,A会要求不同的后继符号

这里举了一个小例子

Image4-2-34.png

LR(1)项目定义
将一般形式为 [A→α·β, a]的项称为LR(1) 项,其中A→αβ
一个产生式,a是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下,A后面必须紧跟的终结符,称为该项的展望符(lookahead)

  • LR(1) 中的1指的是项的第二个分量的长度
  • 在形如[A→α·β, a]且β ≠ ε的项中,展望符a没有任何作用
  • 但是一个形如[A→α·;a]且β≠ε的项在只有在下一个输入符号等于a时才可以按照A→α进行归约,这样的a的集合总是FOLLOW(A)的子集,而且它通常是一个真子集

那么LR(1)的等价项目是什么呢?

Image4-2-35.png

这里举了一个例子,展示了LR(1)各个状态

Image4-2-36.png

建议手动模拟一遍,加深印象

Image4-2-37.png

这样就构造出了LR(1)分析表

Image4-2-38.png

我们将LR(1)状态机与SLR状态机进行对比,可以发现LR(1)自动机比SLR自动机多了四个状态

如果除展望符外,两个LR(1)项目集是相同的,则称这两个LR(1)项目集是同心

最后给出了LR(1)项目闭包的计算

Image4-2-39.png

GOTO函数的伪代码

Image4-2-40.png

项集族的伪代码

Image4-2-40.png

LR(1)分析表构造算法

Image4-2-41.png

如果LR(1)分析表中没有语法分析冲突,那么给定的文法就称为LR(1)文法

LALR分析法

LALR分析法的提出
从上面的例子我们可以看出,LR(1)分析法中存在着同心项的集合,也就是说LR(1)分析法实际上是根据展望符集合的不同,将原始的LR(0)项目进行分裂,分裂成了不同的LR(1)项目,所以额外长产生了很多状态。

为了使LR(1)状态实用化,我们要想办法减少项目数

Image4-2-42.png

在这个例子中,I8与I10为同心项目集,可以进行合并,同理I4与I11之间也不存在状态冲突,I5也可以与I12合并,I7与I13军可以进行合并。这样,我们将没有冲突的状态同心项目集进行合并,可以极大减少状态机的项目数,也节省空间。

LALR(lookahead—LR)分析的基本思想

  • 寻找具有相同核心的LR(1)项集,并将这些项集
    合并为一个项集。 所谓项集的核心就是其第一分

量的集合

  • 然后根据合并后得到的项集族构造语法分析表
  • 如果分析表中没有语法分析动作冲突,给定的文法就称为LALR(1)文法,就可以根据该分析表进行语法分析

我们将可以合并的同心状态集合给合并后得到

Image4-2-43.png

接下来我们构造新的LALR分析表

Image4-2-44.png

当然,这种方法依然会产生冲突

Image4-2-45.png

为什么不产生“移入—归约”冲突呢,因为同心项目集,它们的心是相同的,因此我们在合并同心集合的时候,实际上我们合并的是对应项的展望符集合。而展望符只在归约的时候起作用,在移入的时候是不起作用的。因此,只要合并前不存在“移入—归约”冲突,那么合并后也不会存在“移入—归约”冲突

但是,合并同心集后,虽然不产生冲突,但可能会推迟错误的发现。

Image4-2-46.png

这一段老师讲的特别好,建议看原视频

LALR(1)的特点

  • 形式上与LR(1)相同
  • 大小上与LR(0)/SLR相当
  • 分析能力介于SLRLR(1)之间
    SLR<LALR(1)<LR(1)
  • 合并后的展望符集合仍为FOLLOW集的子集

二义性文法的LR分析

  • 每个二义性文法都不是LR的
  • 某些类型的二义性文法在语言的描述和实现中很有用且更简短,更自然

Image4-2-47.png

我们可以使用优先级和结合性解决冲突

Image4-2-48.png

我们可以看出I7与I8存在移入—归约冲突
那么在I7和I8中,当下一个输入符号是+*时,由FOLLOW(E)可以看出,可以采用归约,也可以采用移入。

先看I7,栈顶的输入串是E->E+E·,那么如果栈外的下一个输入符号是*时,因为*的优先级高于+,此时我们应当把*移入到栈中,先算乘法运算,所以I7此时进入I5,执行的是移入动作;如果下一个符号是+,因为加法是左结合的,因此我们应该执行E->E+E·,所以这时候执行归约动作。

在I8中,栈顶是E->E*E·,因此无论下一个输入符号是+还是*,我们都执行·归约动作

这就是二义性算数表达式文法的SLR分析表

Image4-2-49.png

因此,应该保守地使用二义性文法,并且必须在严格
控制之下使用,因为稍有不慎就会导致语法分
析器所识别的语言出现偏差

LR分析中的错误处理

语法错误的检测
当LR分析器在查询分析表并发现一个报错条目时,就检测到了一个语法错误。

错误恢复策略

  • 恐慌模式错误恢复
  • 短语层次错误恢复

恐慌模式错误恢复

Image4-2-50.png

  • 从栈顶向下扫描,直到发现某个状态si,它有一个对应于某个非终结符A的GOTO目标,可以认为从这个A推导出的串中包含错误
  • 然后丢弃0个或多个输入符号,直到发现一个可能合法地跟在A之后的符号a为止。
  • 之后将si+1 = GOTO(si , A)压入栈中,继续进行正常的语法分析

短语层次错误恢复

  • 检查LR分析表中的每一个报错条目,并根据语
    言的使用方法来决定程序员所犯的何种错误最有

可能引起这个语法错误

  • 然后构造出适当的恢复过程

接下来举一个例子,展示如何构造错误处理历程

Image4-2-51.png

简单解释一下每一个错误处理:

Image4-2-52.png

Last modification:January 31st, 2019 at 04:58 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment