LL LR SLR LALR傻傻分不清

muhe

2018-02-11

学习记录

撸公开课的时候被这几个文法绕晕了。搜了很多东西，合并整理方便后续查看。

首先，LL文法是自顶向下，用的是推导；LR、SLR、LALR是自底向上，用的是规约。

第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。
龙书上的判断规则是：

1
2
3

形如 A->a|β 这样的文法，满 足
        ①FIRST(α)∩ FIRST (β ) =Φ
        ②若ε∈ FIRST( α)， 要满足 FIRST(β) ∩FOLLOW(A)=Φ

如果某一文法能够构造一张分析表，使得表中每一个元素至多只有一种明确动作，则该文法称为LR文法。

具体来说：

1
2
3

1、构造它的LR(0)项目集合的DFA（即识别该文法全部活前缀的DFA）；
2、根据该DFA画出该文法的LR(0)分析表；
3、在分析表中，每格要么只有一个内容，要么没有内容，（即无冲突）则为LR(0)文法。

概括一下就是：见到First集就移进，见到终态就归约

满足下面两个条件的文法是SLR(1)文法

1
2
3

a.对于在s中的任何项目 A→α.Xβ,当X是一个终结符，且X在Follow(B)中时，s中没有完整的项目B→r.

b.对于在s中的任何两个完整项目A→α.和 B→β.,Follow(A)∩Follow(B)为空。

概括就是：见到First集就移进，见到终态先看Follow集，与Follow集对应的项目归约，其它报错。

LALR即“Look-Ahead LR”。其中，Look-Ahead为“向前看”，L代表对输入进行从左到右的检查，R代表反向构造出最右推导序列。

和LR(0)一致，只是构造自动机的时候多向前查看一个字符。

SLR(1)与LR(0)：简单的LR语法分析技术（即SLR（1）分析技术）的中心思想是根据文法构造出LR（0）自动机。

规范LR（1）语法分析技术的中心思想是根据文法构造出LR（1）自动机，而规范LR（1）自动机构造方法和LR（0）自动机的构造方法相同，只是多增加了向前搜索符号。

LALR(1)是对LR(1)项集族I中具有同心项的项集进行合并得到I’，然后根据I’进行分析的方法。

cmp