LL LR SLR LALR傻傻分不清

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

0x01: 概念

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

1. LL(1)

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

1
2
3
形如 A->a|β 这样的文法,满 足
①FIRST(α)∩ FIRST (β ) =Φ
②若ε∈ FIRST( α), 要满足 FIRST(β) ∩FOLLOW(A)=Φ
2. LR(0)

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

具体来说:

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

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

3. SLR(1)

满足下面两个条件的文法是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集对应的项目归约,其它报错。

4. LALR(1)

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

5. LR(1)

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

0x02: 关系与对比

1. SLR(1)与LR(0)的关系:

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

  • LR(0):见到First集就移进,见到终态就归约

  • SLR(1)见到First集就移进,见到终态先看Follow集,与Follow集对应的项目归约,其它报错。

2. LR(1)与LR(0)的关系:

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

3. 规范LR(1)与LALR(1)的关系:

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

4. 各种文法能力的对比

cmp

0x03: 引用

LL LR SLR LALR 傻傻分不清

编译原理:LL(1),LR(0),SLR(1),LALR(1),LR(1)对比

如何判断文法是LL(1)SLR(1)LR(1)LALR(1)的?

维基百科

文章目录
  1. 1. 0x01: 概念
    1. 1.1. 1. LL(1)
    2. 1.2. 2. LR(0)
    3. 1.3. 3. SLR(1)
    4. 1.4. 4. LALR(1)
    5. 1.5. 5. LR(1)
  2. 2. 0x02: 关系与对比
    1. 2.1. 1. SLR(1)与LR(0)的关系:
    2. 2.2. 2. LR(1)与LR(0)的关系:
    3. 2.3. 3. 规范LR(1)与LALR(1)的关系:
    4. 2.4. 4. 各种文法能力的对比
  3. 3. 0x03: 引用
,