第85集：LALR(1)分析法

学习目标

  • 理解LALR(1)分析的基本概念和原理
  • 掌握LALR(1)项集的构造方法
  • 学习LALR(1)分析表的构造方法
  • 理解LALR(1)分析如何平衡LR(1)分析的能力和SLR(1)分析的表大小
  • 掌握LALR(1)分析的过程和步骤
  • 比较LALR(1)分析与其他LR分析方法的优缺点
  • 通过示例练习LALR(1)分析的各个步骤
  • 了解LALR(1)分析在实际编译器中的应用

一、LALR(1)分析的基本概念

1. LALR(1)分析的定义

LALR(1)（Look-Ahead LR(1)）分析是LR(1)分析的一种优化，它通过合并LR(1)项集中的同心项集来减少分析表的大小，同时保持LR(1)分析的能力。LALR(1)分析的基本思想是：

  • 合并具有相同LR(0)部分的LR(1)项集（同心项集）
  • 合并后的项集的展望符集合是各个同心项集展望符集合的并集
  • 基于合并后的项集构造分析表

LALR(1)分析的名称中：

  • L 表示从左到右扫描输入串
  • A 表示向前看（Look-Ahead）
  • L 表示LR分析
  • R 表示构造最右推导的逆过程（最左归约）
  • 1 表示使用一个展望符来决定归约操作

2. LALR(1)分析与其他LR分析方法的关系

LALR(1)分析是LR分析家族中的一个重要成员，它在能力和表大小之间取得了平衡：

  • LR(0)分析：表最小，能力最弱
  • SLR(1)分析：表大小与LR(0)相同，能力比LR(0)强
  • LALR(1)分析：表大小与SLR(1)相近，能力接近LR(1)
  • LR(1)分析：能力最强，表最大

3. LALR(1)分析的优势

LALR(1)分析具有以下优势：

  • 分析能力：接近LR(1)分析，能够处理大多数实际编程语言的文法
  • 分析表大小：与SLR(1)分析表大小相近，适合实际应用
  • 实现复杂度：比LR(1)分析低，比SLR(1)分析高
  • 错误处理：错误检测能力与LR(1)分析相近

4. LALR(1)分析的应用

LALR(1)分析是实际编译器中最常用的LR分析方法之一，许多编译器构造工具（如Yacc/Bison）都使用LALR(1)分析。例如：

  • Yacc/Bison：Unix/Linux系统中常用的编译器构造工具
  • Bison：Yacc的GNU版本，功能更强大
  • Byacc：Berkeley Yacc，另一个Yacc变体

二、LALR(1)项集的构造

1. 同心项集的概念

同心项集是指具有相同LR(0)部分的LR(1)项集。具体来说，如果两个LR(1)项集I和J中的每个项的LR(0)部分（即不考虑展望符的部分）都相同，那么I和J是同心项集。

例如，以下两个LR(1)项集是同心项集：

I: [A → α.Bβ, a], [B → .γ, b]
J: [A → α.Bβ, c], [B → .γ, d]

它们的LR(0)部分都是 A → α.Bβ 和 B → .γ，只是展望符不同。

2. 合并同心项集的步骤

合并同心项集的步骤如下：

  1. 构造LR(1)项集规范族：按照LR(1)分析的方法构造LR(1)项集规范族
  2. 识别同心项集：找出所有具有相同LR(0)部分的LR(1)项集
  3. 合并同心项集：将同心项集合并为一个项集，合并后的项集的展望符集合是各个同心项集展望符集合的并集
  4. 重新计算转移：对于合并后的项集，重新计算转移操作

3. 合并同心项集的示例

考虑以下LR(1)项集：

I3: [A → a.Ab, $], [A → .aAb, b], [A → .ε, b]
I4: [A → a.Ab, c], [A → .aAb, b], [A → .ε, b]

这两个项集是同心项集，因为它们的LR(0)部分相同。合并后的项集为：

I34: [A → a.Ab, $c], [A → .aAb, b], [A → .ε, b]

其中，$c 表示展望符集合 {$, c}。

4. 合并同心项集的注意事项

合并同心项集时需要注意以下几点：

  • 展望符的合并：合并后的项集的展望符是各个同心项集展望符的并集
  • 转移的计算：合并后的项集的转移是基于合并后的项集计算的
  • 冲突的可能：合并同心项集可能会引入新的冲突，特别是归约-归约冲突
  • 能力的保持：在大多数情况下，LALR(1)分析能够保持LR(1)分析的能力

三、LALR(1)分析表的构造

1. LALR(1)分析表的构造步骤

LALR(1)分析表的构造步骤如下：

  1. 扩展文法：添加新的开始符号S'和产生式S'→S
  2. 构造LR(1)项集规范族：按照LR(1)分析的方法构造LR(1)项集规范族
  3. 合并同心项集：将具有相同LR(0)部分的LR(1)项集合并为一个项集
  4. 构造LALR(1)项集规范族：由合并后的项集组成
  5. 构造分析表：
    • 移进表（Action表）构造：
      • 对于状态i中的每个移进项 [A → α.aβ, b]，如果Goto(i, a) = j，则Action[i][a] = shift j
      • 对于状态i中的每个归约项 [A → α., a]，对于每个终结符a∈展望符集合，Action[i][a] = reduce A→α
      • 对于接受项 [S' → S., $]，Action[i][$] = accept
    • goto表构造：
      • 对于每个状态i和非终结符A，如果Goto(i, A) = j，则Goto[i][A] = j

2. LALR(1)分析表的冲突

合并同心项集可能会引入新的冲突，特别是归约-归约冲突。这是因为合并后的项集的展望符集合是各个同心项集展望符集合的并集，可能会导致不同的归约项在相同的展望符下产生冲突。

例如，假设有两个LR(1)项集：

I1: [A → α., a]
I2: [B → β., a]

它们是同心项集吗？不，因为它们的LR(0)部分不同（一个是 A → α.，另一个是 B → β.）。所以它们不会被合并。

另一个例子：

I1: [A → α., a], [C → γ., b]
I2: [A → α., c], [C → γ., d]

合并后的项集为：

I12: [A → α., ac], [C → γ., bd]

这里不会产生冲突，因为A和C的归约展望符集合不相交。

3. LALR(1)分析表的示例

以下是一个简单文法的LALR(1)分析表：

状态 Action Goto
a b $ S A
0 s3 r3 r3 1 2
1 acc
2 r2
3 s3 r3 r3 4
4 s5
5 r1 r1

其中：

  • s3表示移进到状态3
  • r3表示用产生式3（A→ε）进行归约
  • acc表示接受
  • 空格表示错误

四、LALR(1)分析的过程

1. LALR(1)分析的基本步骤

LALR(1)分析的过程与其他LR分析方法（如LR(0)、SLR(1)、LR(1)）的过程类似，具体步骤如下：

  1. 初始化：

    • 分析栈中压入初始状态0和结束符$
    • 输入指针指向输入串的第一个符号

  2. 分析循环：
    重复以下步骤，直到分析完成：

    • 获取当前状态：栈顶的状态为当前状态s
    • 获取当前输入符号：输入指针指向的符号为当前输入符号a
    • 查找分析表：查找Action[s][a]的值
    • 执行操作：
      • 移进（shift j）：将输入符号a和状态j压入栈，输入指针向前移动一位
      • 归约（reduce A→α）：
        • 从栈中弹出2*|α|个元素（|α|是产生式右部的长度，每个符号对应一个状态）
        • 此时栈顶的状态为t
        • 查找Goto[t][A] = k，将非终结符A和状态k压入栈
        • 输出归约信息
      • 接受（accept）：分析成功，结束分析
      • 错误（error）：分析失败，报告错误

2. LALR(1)分析的示例

示例：简单文法的LALR(1)分析

考虑以下简单文法：

S → A
A → aAb | ε

扩展后的文法为：

S' → S
S → A
A → aAb | ε

1. 构造LR(1)项集规范族

按照LR(1)分析的方法，构造LR(1)项集规范族：

  • I0: [S'→.S, $], [S→.A, $], [A→.aAb, $], [A→.ε, $]
  • I1: [S'→S., $]
  • I2: [S→A., $]
  • I3: [A→a.Ab, $], [A→.aAb, b], [A→.ε, b]
  • I4: [A→aA.b, $]
  • I5: [A→aAb., $]

2. 合并同心项集

在这个例子中，没有同心项集，所以LALR(1)项集规范族与LR(1)项集规范族相同。

3. 构造LALR(1)分析表

根据LALR(1)项集规范族，构造LALR(1)分析表：

状态 Action Goto
a b $ S A
0 s3 r3 r3 1 2
1 acc
2 r2
3 s3 r3 4
4 s5
5 r1 r1

4. 分析输入串 aabb

分析过程如下：

步骤 分析栈 剩余输入 Action Goto 说明
1 0 aabb $ s3 移进a，进入状态3
2 0 a 3 abb $ s3 移进a，进入状态3
3 0 a 3 a 3 bb $ r3 4 用A→ε归约，Goto(3,A)=4
4 0 a 3 A 4 bb $ s5 移进b，进入状态5
5 0 a 3 A 4 b 5 b $ r1 4 用A→aAb归约，Goto(3,A)=4
6 0 a 3 A 4 b $ s5 移进b，进入状态5
7 0 a 3 A 4 b 5 $ r1 2 用A→aAb归约，Goto(0,A)=2
8 0 A 2 $ r2 1 用S→A归约，Goto(0,S)=1
9 0 S 1 $ acc 接受

五、LALR(1)分析与其他LR分析方法的比较

1. 能力比较

  • LR(1)分析：能力最强，能够处理最多的文法
  • LALR(1)分析：能力接近LR(1)分析，能够处理大多数实际编程语言的文法
  • SLR(1)分析：能力比LALR(1)分析弱，无法处理某些文法
  • LR(0)分析：能力最弱，只能处理部分简单的文法

2. 分析表大小比较

  • LR(0)分析：表最小
  • SLR(1)分析：表大小与LR(0)分析相同
  • LALR(1)分析：表大小与SLR(1)分析相近
  • LR(1)分析：表最大，可能比LALR(1)分析表大很多

3. 实现复杂度比较

  • LR(0)分析：实现最简单
  • SLR(1)分析：实现比LR(0)分析复杂，需要计算FOLLOW集
  • LALR(1)分析：实现比SLR(1)分析复杂，需要构造LR(1)项集规范族并合并同心项集
  • LR(1)分析：实现最复杂，需要构造LR(1)项集规范族

4. 错误处理比较

  • LR(1)分析：错误检测能力最强，能够提供最具体的错误信息
  • LALR(1)分析：错误检测能力接近LR(1)分析
  • SLR(1)分析：错误检测能力比LALR(1)分析弱
  • LR(0)分析：错误检测能力最弱

5. 应用场景比较

  • LR(0)分析：适用于非常简单的文法
  • SLR(1)分析：适用于简单文法，实现简单
  • LALR(1)分析：适用于大多数实际编程语言的文法，是实际编译器中最常用的LR分析方法
  • LR(1)分析：适用于需要处理复杂文法的场景，但由于分析表较大，实际应用中较少直接使用

六、LALR(1)分析的局限性

1. 合并同心项集可能引入冲突

合并同心项集可能会引入新的冲突，特别是归约-归约冲突。这是因为合并后的项集的展望符集合是各个同心项集展望符集合的并集，可能会导致不同的归约项在相同的展望符下产生冲突。

例如，假设有两个LR(1)项集：

I1: [A → α., a], [B → β., b]
I2: [A → α., b], [B → β., a]

它们的LR(0)部分相同，所以是同心项集。合并后的项集为：

I12: [A → α., ab], [B → β., ab]

这里会产生归约-归约冲突，因为A和B的归约展望符集合有交集 {a, b}。

2. 错误检测位置可能不够精确

由于LALR(1)分析合并了同心项集，错误检测位置可能不如LR(1)分析精确。在某些情况下，LALR(1)分析可能会在错误发生后继续分析一段距离才检测到错误，而LR(1)分析可以在错误发生的最早位置检测到错误。

3. 构造过程复杂

LALR(1)分析的构造过程比SLR(1)分析复杂，需要构造LR(1)项集规范族并合并同心项集。这增加了实现的复杂度和计算成本。

七、LALR(1)分析的实践练习

练习：构造LALR(1)分析表

考虑以下简单文法：

S → A
A → aA | b
  1. 扩展文法，添加新的开始符号S'
  2. 构造LR(1)项集规范族
  3. 合并同心项集（如果有）
  4. 构造LALR(1)分析表
  5. 分析输入串 aab 的过程

解决方案：

  1. 扩展文法：

    S' → S
S → A
A → aA | b

  2. 构造LR(1)项集规范族：

    • I0: [S'→.S, $], [S→.A, $], [A→.aA, $], [A→.b, $]
    • I1: [S'→S., $]
    • I2: [S→A., $]
    • I3: [A→a.A, $], [A→.aA, $], [A→.b, $]
    • I4: [A→b., $]
    • I5: [A→aA., $]

  3. 合并同心项集：
    在这个例子中，没有同心项集，所以LALR(1)项集规范族与LR(1)项集规范族相同。

  4. 构造LALR(1)分析表：

    状态 Action Goto
    a b $ S A
    0 s3 s4 1 2
    1 acc
    2 r2
    3 s3 s4 5
    4 r3
    5 r1

  5. **分析输入串 aab**：

    步骤 分析栈 剩余输入 Action Goto 说明
    1 0 aab $ s3 移进a，进入状态3
    2 0 a 3 ab $ s3 移进a，进入状态3
    3 0 a 3 a 3 b $ s4 移进b，进入状态4
    4 0 a 3 a 3 b 4 $ r3 5 用A→b归约，Goto(3,A)=5
    5 0 a 3 a 3 A 5 $ r1 5 用A→aA归约，Goto(3,A)=5
    6 0 a 3 A 5 $ r1 2 用A→aA归约，Goto(0,A)=2
    7 0 A 2 $ r2 1 用S→A归约，Goto(0,S)=1
    8 0 S 1 $ acc 接受

八、LALR(1)分析在实际编译器中的应用

1. Yacc/Bison工具

Yacc（Yet Another Compiler-Compiler）是Unix系统中常用的编译器构造工具，它使用LALR(1)分析方法。Bison是Yacc的GNU版本，功能更强大，也使用LALR(1)分析方法。

使用Yacc/Bison，用户可以：

  • 以BNF（巴克斯-诺尔范式）形式定义文法
  • 在产生式中添加语义动作
  • 自动生成LALR(1)分析器代码
  • 处理文法中的冲突

2. Yacc/Bison的工作原理

Yacc/Bison的工作原理如下：

  1. 输入处理：读取用户定义的文法文件
  2. 构造项集：构造LR(1)项集规范族并合并同心项集，得到LALR(1)项集规范族
  3. 构造分析表：基于LALR(1)项集规范族构造分析表
  4. 代码生成：生成C语言（或其他语言）的分析器代码
  5. 输出文件：将生成的代码输出到文件

3. Yacc/Bison的示例

以下是一个简单的Yacc/Bison示例：

%{
#include <stdio.h>
%}

%token NUMBER PLUS MINUS TIMES DIVIDE LPAREN RPAREN

%%
expr : expr PLUS term
     | expr MINUS term
     | term
     ;

term : term TIMES factor
     | term DIVIDE factor
     | factor
     ;

factor : NUMBER
       | LPAREN expr RPAREN
       ;

%%

int main() {
    printf("Enter expression: ");
    yyparse();
    printf("Valid expression\n");
    return 0;
}

yyerror(char *s) {
    fprintf(stderr, "Error: %s\n", s);
}

这个示例定义了一个简单的算术表达式文法，并生成一个LALR(1)分析器来分析算术表达式。

4. 其他使用LALR(1)分析的工具

除了Yacc/Bison外，还有许多其他编译器构造工具使用LALR(1)分析：

  • Byacc：Berkeley Yacc，另一个Yacc变体
  • GNU Bison：支持多种语言的输出
  • ANTLR：支持LALR(1)分析和其他分析方法
  • JavaCC：Java编译器构造工具，支持LALR(1)分析

九、自测问题

  1. 选择题：LALR(1)分析是对LR(1)分析的优化，它通过什么来减少分析表的大小？
    A. 合并同心项集
    B. 减少展望符的数量
    C. 简化文法
    D. 忽略部分冲突

  2. 选择题：以下哪种LR分析方法在实际编译器中最常用？
    A. LR(0)分析
    B. SLR(1)分析
    C. LALR(1)分析
    D. LR(1)分析

  3. 简答题：简述LALR(1)分析表的构造步骤。

  4. 简答题：解释为什么合并同心项集可能会引入新的冲突。

  5. 实践题：对于文法 S→A | B, A→aA | ε, B→bB | ε，构造LALR(1)分析表，并分析输入串 aab 的过程。

十、小结

本集详细介绍了LALR(1)分析方法，包括：

  1. LALR(1)分析的基本概念：对LR(1)分析的优化，通过合并同心项集来减少分析表的大小
  2. 同心项集的概念：具有相同LR(0)部分的LR(1)项集
  3. 合并同心项集的步骤：构造LR(1)项集规范族，识别并合并同心项集
  4. LALR(1)分析表的构造：基于合并后的项集构造分析表
  5. LALR(1)分析的过程：利用分析表指导移进和归约操作
  6. LALR(1)分析的局限性：可能会引入新的冲突，错误检测位置可能不够精确
  7. LALR(1)分析在实际编译器中的应用：Yacc/Bison等工具使用LALR(1)分析

LALR(1)分析是LR分析家族中的一个重要成员，它在能力和表大小之间取得了平衡，是实际编译器中最常用的LR分析方法之一。通过学习LALR(1)分析，我们可以更深入地理解现代编译器的语法分析过程，为后续学习更复杂的编译技术打下基础。

十一、下集预告

下一集我们将学习Yacc/Bison工具的使用，这是实际编译器构造中常用的工具，它基于LALR(1)分析方法。我们将学习如何使用Yacc/Bison定义文法、添加语义动作、处理冲突，以及生成分析器代码。

参考资料

  1. 《编译原理》（龙书）- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
  2. 《现代编译原理》（虎书）- Andrew W. Appel
  3. 《编译器设计》- Keith D. Cooper, Linda Torczon
  4. Yacc/Bison用户手册
  5. LALR(1)分析算法的历史与发展

通过本集的学习，你应该对LALR(1)分析方法有了全面的了解。LALR(1)分析是实际编译器中最常用的LR分析方法之一，它通过合并同心项集，在保持LR(1)分析能力的同时，减少了分析表的大小。在后续的学习中，我们将深入探讨Yacc/Bison工具的使用，学习如何利用这些工具生成实际的编译器前端。

« 上一篇 LR(1)分析法 下一篇 » Yacc / Bison 入门
↑