LR分析表的构造

LR分析的两个阶段

  1. 产生分析表
  2. 语法分析

image-20201025203757230

分析结果是一个是否属于该文法的判断结果或者语法树。

复习

image-20201025204110314

  • 分析栈内的符号串和剩下的输入符号串能构成一个规范句型
  • 一旦栈顶出现句柄(可归约串),则进行归约
  • 栈内永远不会出现句柄之后的符号

image-20201025204517023

字前缀与活前缀

字的前缀指的是任意字的首部,abc的前缀有ε,a,ab,abc。

活前缀指的是规范句型的一个前缀,这种前缀不包含句柄之后的任何符号。

image-20201025204802535

活前缀右边添加一些非终结符或终结符即可得到规范句型。

LR分析过程中的任何时候,栈里面的文法符号应该是活前缀,再加上输入串的剩余部分依旧是规范句型。只要输入串的已扫描部分(分析栈中的符号串)始终保持是活前缀,意味着之前的移进归约就没错,所以LR分析表的作用是给LR分析器正确的移进/归约指示(确保分析栈中的符号串为活前缀)

规范归约过程,要保证分析栈中始终是活前缀。

活前缀识别

对于文法G 可以构造DFA,能用于识别G的所有活前缀。

文法扩展:

保证文法开始符号只有一个产生式,开始符号不会出现在其他产生式右部。

image-20201025211617520

image-20201025213240859

每个项目表示了在分析过程中我们看到的项目,点左边的是已经看到的,右边的是期待看到的。

移进项目: 已经识别了α,期待后面的部分,然后接着的还是一个终结符,所以把终结符a移入。

待约项目: 已经识别了α,期待后面的部分,马上归约形成非终结符B,等待着非终结符B归约形成再继续前进。

表达了分析过程中的不同阶段,可以连接成一个自动机。

image-20201025213636368

方法1

构造DFA:

  1. 构造识别文法所有前缀的NFA

    LR(0)项目按照意义构造成NFA

    image-20201025214112356

    待约状态,画出ε到所有的A刚开始形成的项目(期盼着能归约出A,所以需要转到A开始归约的项目)。如果A这真的归约成功,那么转移到k状态。

    image-20201025214534465

    注意双层圈对应的句柄识别态,马上可以归约

  2. NFA确定化

    子集法得到DFA,如果是活前缀,一定能被DFA接受。 LR分析器的状态就是DFA的状态

输入串识别过程就是在DFA中游走的过程

image-20201025214955582

image-20201025215128841

LR分析表就是根据DFA来指导LR分析器在栈里面进行移进或归约。

规范族(元素是集合的集合)

image-20201025215354450

方法2

利用有效项目直接计算项目集规范族,从而构造识别活前缀的DFA。

里面的符号的R指的是最右推导。

有效项目指的是

image-20201025220317580

DFA中从初态出发,沿着活前缀识别到达的状态集里面的项目就是相对于这个活前缀有效的项目。

image-20201025221254379

image-20201025221523520

所以B的后面两个项目也是有效的(点在左边)

image-20201025222143937

这个证明...我读都读不出来...

项目集规范族的构造

image-20201025222426300

扩展之后,接受态只有一种。

image-20201025222609048

image-20201025222852948

如果i在闭包里面,那么j也应该在闭包里面。

状态转换函数

项目集之间的转换关系

image-20201025223239975

GO状态转换函数,相当于当前项目集在多识别了一个X后的有效项目集

待约项目注意可以继续做闭包。

每个项目集Ix都可以向下走

I1 I2 I3 还可以拿出来找GO函数,求项目集

LR(0)项目集规范族的构造方法

通过计算有效项目获得G‘[s]的项目集规范族

该伪码返回项目集规范族。

image-20201026170551089

循环完毕之后C就是项目集规范族了(元素全部都是项目集),转换函数GO将这些项目集练成DFA

只有一个归约项目时 如项目集1,不能再继续前进

image-20201026171133530

image-20201026171203940

两种方法本质上是一样的。

构造LR(0)分析表

image-20201026180615577

对于状态5里面的B->·d,表示句柄还没形成,需要移进d

而对于状态11里面的B->d·,表示句柄已经形成,可以进行归约(归约项目告诉我们要归约),并且是规约成B。然后回到3状态,并把B压入(转移到7状态) 这就是归约时查GOTO表的具体表现。

同一个活前缀可能有若干个项目对应有效。如果同时有移进和归约就会出现冲突。

image-20201026181013887

如上面的那个项目集规范族里面就没有同时出现移进和归约,可以用来构造LR(0)分析表。

DFA转LR0分析表

image-20201026181207765

把状态集合中的每个项目告诉我们的动作写道ACTION和GOTO表中。

构造算法如下

根据GO函数Ik面临符号a时转移到Ij,那么 ACTION表中 k,a写为sj(移进j)(同时a也要压入分析栈)

关于第二点,k处于栈顶时,符号栈栈顶一定是句柄,那么可以可以进行归约,只要进入到Ik不需要看下一个字符是什么便可以进行归约(LR0中0的含义)

关于第四点,对于非终结符,对应关系写到GOTO表中(归约形成非终结符后压栈同时查GOTO表压入的状态)

image-20201026182018951

image-20201027131317005

状态6进行归约,使用第一个产生式,所以全部写成r1,(不管当前输入是什么,所以是LR 0)

使用LR0分析表对字符串进行分析

image-20201105125028738

image-20201105125121284

image-20201105125232576

文章目录