LR分析

自底向上分析方法是一种移进-规约过程：当分析的栈顶符号串形成句柄（可规约串）时采取规约动作。LR分析法就是一种一种能根据当前分析栈中的符号串和向右顺序查看输入串的k个符号即可唯一确定分析器的动作是移进还是规约和用哪个产生式规约。值得注意的是：LR分析是规范规约过程（最左规约），即规范推导过程（最右推导）的逆过程。通过一个案例来考察这一点：


产生式：

$S\rightarrow aAcBe[1]$

$A\rightarrow b[2]$

$A\rightarrow Ab[3]$

$B\rightarrow d[4]$

对输入串的进行最右推导：$S\Rightarrow aAcBe[1]\Rightarrow aAcd[4]e[1]\Rightarrow aAb[3]cd[4]e[1]\Rightarrow ab[2]b[3]cd[4]e[1]$

它的逆过程-最左规约为：$ab[2]b[3]cd[4]e[1]\Leftarrow aAb[3]cd[4]e[1]\Leftarrow aAcd[4]e[1]\Leftarrow aAcBe[1]\Leftarrow S$


本章介绍当k<=1时LR分析器的基本构造原理和方法。关于k的含义：LR（k）当k=0时表示分析器不需要向右查看输入符号。本篇主要介绍LR(0)、SLR(1)、LR(1)和LALR(1)四种分析器的构造方法。

LR分析概述

LR分析器包括三个组成部分：总控程序、分析表和分析栈。
总控程序对所有的LR分析器而言都是相同的。
文法和分析表都会影响分析表的构造。分析表可分为ACTION表和GOTO表两部分。都可用二维数组表示。
分析栈包括文法符号栈和相应的状态栈。

LR(0)分析

LR(0)分析表构造的思想和方法是构造其他LR分析表的基础。

可归前缀和子前缀

由一个例子给出LR分析的基本原理，并给出可归前缀和活前缀的形式化定义。


由LR分析板块的案例可知，每次规约前句型的前部依次为：

ab[2]、aAb[3]、aAcd[4]、aAcBe[1]

这也是每次采取规约动作前符号栈中的内容，这种前部也称为可归前缀。

再来分析上述每个前部的前缀：

$\theta,a,ab$

$\theta,a,aA,aAb$

$\theta,a,aA,aAc,aAcd$

$\theta,a,aA,aAc,aAcB,aAcBe$

将规范句型中形成可归前缀之前包括可归前缀在内的所有前缀称为活前缀。只要在规范规约过程中的任何时刻，只要分析过的部分（即在符号栈中的符号串）均为规范句型的活前缀，则表明输入串已被分析的部分是该文法某规范句型的一个正确部分。


拓广文法：在原文法G中增加产生式$S’\rightarrow S$所得的文法即为拓广文法。其中S为原文法的开始符号。


活前缀的形式化定义：略。

识别活前缀的有限自动机

活前缀及可归前缀的一般计算方法

LR(0)项目集规范族的构造-更实用的构造可识别可归前缀的有限自动机的方法

  • LR(0)项目

    例如，产生式$S\rightarrow aAcBe$对应有6个项目。

    $S\rightarrow ·aAcBe$

    $S\rightarrow a·AcBe$

    $S\rightarrow aA·cBe$

    $S\rightarrow aAc·Be$

    $S\rightarrow aAcB·e$

    $S\rightarrow aAcBe·$

    圆点的左部表示分析过程的某时刻欲用该产生式规约时已识别过的句柄部分，圆点右部表示期待的后缀部分。
  • 构造识别活前缀的NFA

    在介绍NFA的构造前，首先明确几个概念：

    由于S’仅在第一个产生式的左部出现，因此规定项目1为初态。

    其余每个状态都为活前缀的识别态。


    构造流程：

    1.将文法的所有产生式的项目列出，并使每个项目都作为NFA的一个状态。

    2.确定状态之间的转换关系：

    若i项目为：$X\rightarrow X_1X_2···X_{i-1}·X_i···X_n$

    若j项目为: $X\rightarrow X_1X_2···X_{i-1}X_i·X_{i+1}···X_n$

    若出现j项目落后于i项目一个符号的情况，在i到j状态连一条$X_i$的箭弧

    如果$X_i$为非终结符，则i状态会连接向以$X_i$为左部的新的状态。且箭弧上标记为$\epsilon$。


    通过一个案例学习：

    LR(0)项目

    LR(0)NFA
  • 构造LR(0)项目集规范族
  • 构造LR(0)分析表
  • LR(0)分析器的工作流程

SLR(1)分析

大多数实用的程序设计语言的文法不能满足LR(0)文法的条件，故引出SLR(1)文法，其思想是基于容许LR(0)规范族中有冲突的项目集，用向前查看一个符号的办法来解决冲突。


通过考察一个案例来体会SLR(1)解决冲突的思想

对于如下的文法案例:

$(0)S’\rightarrow S$

$(1)S\rightarrow rD$

$(2)D\rightarrow D,i$

$(3)D\rightarrow i$

首先构造该文法的LR(0)项目集规范族，如下图所示：

SLR(1)_demo_规范族

然后使用GO函数构造识别活前缀的DFA，如下图所示：

SLR(1)_demo_DFA

其中状态I3中存在“移进-规约冲突”。此时只要保证S的后跟符号集（FOLLOW集）与移进项目的移进符号的集合（{,}）不冲突时，这种移进-规约冲突便可解决。判定冲突是否能解决的形式化定义如下：

对于LR(0)规范族中含以下冲突的项目集：

$I={X\rightarrow\alpha ·b\beta ,A\rightarrow\gamma ·,B\rightarrow\delta ·}$

只要满足：

FOLLOW(A)∩FOLLOW(B)=$\emptyset$

FOLLOW(A)∩{b}=$\emptyset$

FOLLOW(B)∩{b}=$\emptyset$

即表明该冲突可以由SLR(1)分析方法解决。


接上文，冲突的解决方法：

当在状态I时，如果面临某输入符号为a，则可ACTION按以下规定决策：

  • 若a=b，则移进。
  • 若a∈FOLLOW(A)，则用产生式$A\rightarrow\gamma$进行规约。
  • 若a∈FOLLOW(B)，则用产生式$B\rightarrow\delta$进行规约。
  • 此外，报错。