规范LR分析包括LR0分析法 SLR分析法 LR1分析法 LALR分析法

引言：LR分析的基本概念与重要性

LR分析（Left-to-right, Rightmost derivation）是自底向上语法分析的核心方法，它通过从左到右扫描输入字符串，并构建最右推导的逆过程来分析语法。LR分析器具有强大的表达能力，能够处理大多数上下文无关文法，且分析效率高，因此被广泛应用于编译器设计中。规范LR分析包括四种主要方法：LR(0)、SLR(1)、LR(1)和LALR(1)，它们在分析能力、状态数量和实现复杂度上各有特点。

LR分析器的核心思想是使用一个状态机来跟踪分析过程的当前状态，并根据当前状态和输入符号决定下一步动作（移进、归约、接受或报错）。这些方法的主要区别在于如何构建状态集（Item Sets）以及如何确定归约动作的适用性。理解这些方法的差异和联系，对于掌握编译原理和设计高效分析器至关重要。

LR(0)分析法：最基础的LR分析

LR(0)文法与LR(0)项目

LR(0)分析是LR分析家族中最简单的方法，它不向前查看任何输入符号来决定归约动作。LR(0)项目（Item）是在产生式右部某位置加点的产生式，例如对于产生式 A → αβγ，有四个LR(0)项目：A → ·αβγ、A → α·βγ、A → αβ·γ和A → αβγ·。

LR(0)项目集闭包的计算规则是：如果项目集中包含A → α·Bβ，那么需要将所有B的产生式（B → ·γ）加入到项目集中。LR(0)项目集的转换通过GOTO函数实现，当遇到符号X时，从当前项目集转移到新的项目集。

LR(0)分析表的构造

LR(0)分析表的构造步骤如下：

1. 构造LR(0)项目集规范族：从初始项目集开始，通过闭包和GOTO运算生成所有可能的项目集。
2. 确定状态动作：对于每个项目集和每个输入符号，确定移进、归约或报错。
3. 填充分析表：将动作填入ACTION表，将GOTO填入GOTO表。

LR(0)分析实例

考虑以下文法：

S → aA
A → b
A → ε

首先，我们构造LR(0)项目集规范族：

状态0（初始状态）：

• S’ → ·S （拓广文法）
• S → ·aA

状态1（从状态0遇到S）：

• S’ → S· （接受项目）

状态2（从状态0遇到a）：

• S → a·A
• A → ·b
• A → ·ε

状态3（从状态2遇到A）：

• S → aA· （归约项目）

状态4（从状态2遇到b）：

• A → b· （归约项目）

状态5（从状态2遇到ε）：

• A → ε· （归约项目）

对应的LR(0)分析表如下（用Python字典表示）：

# LR(0)分析表示例
action_table = {
    0: {'a': 's2', '$': 'err'},
    1: {'$': 'acc'},
    2: {'b': 's4', 'ε': 's5', 'A': 'g3'},
    3: {'$': 'r1'},  # S → aA
    4: {'$': 'r2'},  # A → b
    5: {'$': 'r3'}   # A → ε
}

goto_table = {
    0: {'S': 1},
    2: {'A': 3}
}

# 分析器伪代码
def lr0_analyzer(input_string):
    stack = [0]  # 状态栈
    input_pos = 0
    while True:
        current_state = stack[-1]
        current_symbol = input_string[input_pos]
        
        action = action_table[current_state].get(current_symbol, 'err')
        
        if action.startswith('s'):  # 移进
            next_state = int(action[1:])
            stack.append(current_symbol)
            stack.append(next_state)
            input_pos += 1
        elif action.startswith('r'):  # 归约
            rule_num = int(action[1:])
            # 根据规则弹出栈中符号
            if rule_num == 1:  # S → aA
                stack.pop(); stack.pop(); stack.pop(); stack.pop()  # 弹出 aA和状态
                stack.append('S')
                stack.append(goto_table[stack[-2]]['S'])
            elif rule_num == 2:  # A → b
                stack.pop(); stack.pop()  # 弹出 b和状态
                stack.append('A')
                stack.append(goto_table[stack[-2]]['A'])
            elif rule_num == 3:  # A → ε
                stack.append('A')
                stack.append(goto_table[stack[-2]]['A'])
        elif action == 'acc':
            return True
        else:
            return False

LR(0)的局限性

LR(0)分析法虽然简单，但存在明显的局限性。它无法处理某些看似合法的文法，因为LR(0)分析表可能产生冲突。例如，对于文法：

A → a
A → aA

在某个状态中，同时存在A → a·和A → a·A，导致移进-归约冲突。LR(0)要求分析表中每个条目只能有一个动作，这限制了其应用范围。

SLR(1)分析法：简单的LR分析

SLR(1)的基本思想

SLR(1)（Simple LR）通过引入FOLLOW集来解决LR(0)中的冲突问题。SLR(1)仍然使用LR(0)项目集规范族，但在决定归约动作时，会检查当前输入符号是否属于被归约非终结符的FOLLOW集。如果属于，则执行归约；否则，报错。

SLR(1)分析表的构造

SLR(1)分析表的构造步骤与LR(0)类似，但在确定归约动作时：

• 对于项目A → α·，只有在当前输入符号属于FOLLOW(A)时，才在ACTION表中设置归约动作。

SLR(1)分析实例

考虑以下文法：

S → L
L → a
L → aL

首先计算FOLLOW集：

• FOLLOW(S) = {$}
• FOLLOW(L) = {$, a} // 因为S → L，且L → aL

构造LR(0)项目集规范族：

状态0：

• S’ → ·S
• S → ·L
• L → ·a
• L → ·aL

状态1（遇到S）：

• S’ → S·

状态2（遇到L）：

• S → L·

状态3（遇到a）：

• L → a·
• L → a·L
• L → ·a
• L → ·aL

状态4（从状态3遇到L）：

• L → aL·

现在构造SLR(1)分析表：

# SLR(1)分析表示例
action_table = {
    0: {'a': 's3'},
    1: {'$': 'acc'},
    2: {'$': 'r1'},  # S → L, $ ∈ FOLLOW(S)
    3: {'a': 's3', '$': 'r2', 'L': 'g4'},  # $ ∈ FOLLOW(L), a ∈ FOLLOW(L)
    4: {'$': 'r3'}   # L → aL, $ ∈ FOLLOW(L)
}

goto_table = {
    0: {'S': 1, 'L': 2},
    3: {'L': 4}
}

# 归约规则：
# r1: S → L
# r2: L → a
# r3: L → aL

SLR(1)的优势与不足

SLR(1)通过FOLLOW集有效解决了许多LR(0)冲突，但仍然不够精确。在某些情况下，FOLLOW集包含的符号过多，导致不必要的归约动作，从而产生冲突。例如，对于文法：

S → aAa
S → aBb
A → c
B → c

在某个状态中，项目A → c·和B → c·同时存在，归约时需要检查FOLLOW(A)和FOLLOW(B)。如果FOLLOW(A)和FOLLOW(B)有交集，就会产生归约-归约冲突。

LR(1)分析法：规范的LR分析

LR(1)项目与向前看符号

LR(1)分析法通过为每个项目附加一个向前看符号（Lookahead）来解决SLR(1)的不足。LR(1)项目的形式为[A → α·β, a]，其中a是向前看符号，表示只有在输入符号为a时才能应用该归约。

LR(1)项目集闭包的计算规则：

1. 初始项目集包含[S’ → ·S, {$}]
2. 如果项目[A → α·Bβ, a]在集合中，则对于每个产生式B → γ，添加[B → ·γ, b]到集合中，其中b是FOLLOW(βa)中的符号。

LR(1)分析表的构造

LR(1)分析表的构造步骤：

1. 构造LR(1)项目集规范族
2. 对于每个项目集：
   • 如果包含[A → α·aβ, b]，则设置ACTION[i, a] = “移进到状态j”
   • 如果包含[A → α·, a]，则设置ACTION[i, a] = “归约A → α”
   • 如果包含[S’ → S·, \(]，则设置ACTION[i, \)] = “接受”

LR(1)分析实例

考虑以下文法：

S → aA
S → bB
A → c
B → c

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

状态0：

• [S’ → ·S, $]
• [S → ·aA, $]
• [S → ·bB, $]

状态1（遇到S）：

• [S’ → S·, $]

状态2（遇到a）：

• [S → a·A, $]
• [A → ·c, $]

状态3（遇到b）：

• [S → b·B, $]
• [B → ·c, $]

状态4（从状态2遇到A）：

• [S → aA·, $]

状态5（从状态3遇到B）：

• [S → bB·, $]

状态6（从状态2遇到c）：

• [A → c·, $]

状态7（从状态3遇到c）：

• [B → c·, $]

对应的LR(1)分析表：

# LR(1)分析表示例
action_table = {
    0: {'a': 's2', 'b': 's3'},
    1: {'$': 'acc'},
    2: {'c': 's6'},
    3: {'c': 's7'},
    4: {'$': 'r1'},  # S → aA
    5: {'$': 'r2'},  # S → bB
    6: {'$': 'r3'},  # A → c
    7: {'$': 'r4'}   # B → c
}

goto_table = {
    0: {'S': 1},
    2: {'A': 4},
    3: {'B': 5}
}

# 归约规则：
# r1: S → aA
# r2: S → bB
# r3: A → c
# r4: B → c

LR(1)的优缺点

LR(1)分析法能力最强，能够处理所有LR(1)文法，不会产生不必要的冲突。但其主要缺点是状态数量可能非常庞大，因为每个项目都带有不同的向前看符号，导致项目集数量急剧增加。这在实际实现中会带来较大的时间和空间开销。

LALR(1)分析法：向前看的LR分析

LALR(1)的基本思想

LALR(1)（Look-Ahead LR）是LR(1)的简化版本，它通过合并LR(1)项目集中具有相同核心（即去掉向前看符号的项目）的状态来减少状态数量。LALR(1)分析表的大小与SLR(1)相同，但分析能力更强，能够处理更多文法。

LALR(1)分析表的构造

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

1. 首先构造完整的LR(1)项目集规范族
2. 合并具有相同核心的LR(1)项目集
3. 在合并后的项目集中，向前看符号是原项目集向前看符号的并集
4. 根据合并后的项目集构造分析表

LALR(1)分析实例

考虑以下文法：

S → aA
A → aA
A → b

首先构造LR(1)项目集规范族，然后合并具有相同核心的状态：

状态0：

• [S’ → ·S, $]
• [S → ·aA, $]

状态1（遇到S）：

• [S’ → S·, $]

状态2（遇到a）：

• [S → a·A, $]
• [A → ·aA, $]
• [A → ·b, $]

状态3（遇到A）：

• [S → aA·, $]

状态4（从状态2遇到a）：

• [A → a·A, $]
• [A → a·A, \(] # 与上面相同，合并后向前看符号仍为\)
• [A → ·aA, $]
• [A → ·b, $]

状态5（从状态2遇到b）：

• [A → b·, $]

状态6（从状态4遇到A）：

• [A → aA·, $]

状态7（从状态4遇到a）：

• [A → a·A, $]
• [A → ·aA, $]
• [A → ·b, $]

实际上，状态4和状态7具有相同核心（A → a·A, A → ·aA, A → ·b），可以合并。合并后的状态记为状态4’，向前看符号为$。

LALR(1)分析表：

# LALR(1)分析表示例
action_table = {
    0: {'a': 's2'},
    1: {'$': 'acc'},
    2: {'a': 's4', 'b': 's5'},
    3: {'$': 'r1'},  # S → aA
    4: {'a': 's4', 'b': 's5', '$': 'r2'},  # A → aA, $ ∈ FOLLOW(A)
    5: {'$': 'r3'},  # A → b
    6: {'$': 'r2'}   # A → aA
}

goto_table = {
    0: {'S': 1},
    2: {'A': 3},
    4: {'A': 6}
}

# 归约规则：
# r1: S → aA
# r2: A → aA
# r3: A → b

LALR(1)的优势

LALR(1)分析法在状态数量和分析能力之间取得了很好的平衡。它比LR(1)更紧凑，通常只比SLR(1)稍多一些状态，但分析能力更强。许多实际的编译器生成器（如YACC、Bison）都采用LALR(1)分析法。

四种LR分析法的比较

分析能力比较

分析方法	分析能力	状态数量	冲突解决方式
LR(0)	最弱，只能处理LR(0)文法	最少	无法解决冲突
SLR(1)	较弱，能处理部分LR(1)文法	较少	使用FOLLOW集
LR(1)	最强，能处理所有LR(1)文法	最多	使用精确的向前看符号
LALR(1)	较强，能处理大多数LR(1)文法	中等	合并LR(1)状态

实际应用中的选择

在实际编译器设计中，LALR(1)是最常用的方法，因为它：

1. 状态数量可控，分析表大小适中
2. 分析能力足够强，能处理大多数编程语言文法
3. 有成熟的工具支持（YACC、Bison等）

LR(1)适用于需要处理复杂文法的场景，但需要更多资源。SLR(1)适用于简单文法，而LR(0)主要用于教学和理解基本原理。

总结

规范LR分析包括LR(0)、SLR(1)、LR(1)和LALR(1)四种方法，它们构成了自底向上语法分析的核心理论体系。从LR(0)到LR(1)，分析能力逐步增强，但实现复杂度也随之增加。LALR(1)作为LR(1)的优化版本，在实际应用中达到了最佳平衡。理解这些方法的原理和差异，对于掌握编译原理和设计高效编译器至关重要。在实际项目中，应根据文法复杂度和性能要求选择合适的分析方法。# 规范LR分析包括LR0分析法 SLR分析法 LR1分析法 LALR分析法

引言：LR分析的基本概念与重要性

LR分析（Left-to-right, Rightmost derivation）是自底向上语法分析的核心方法，它通过从左到右扫描输入字符串，并构建最右推导的逆过程来分析语法。LR分析器具有强大的表达能力，能够处理大多数上下文无关文法，且分析效率高，因此被广泛应用于编译器设计中。规范LR分析包括四种主要方法：LR(0)、SLR(1)、LR(1)和LALR(1)，它们在分析能力、状态数量和实现复杂度上各有特点。

LR分析器的核心思想是使用一个状态机来跟踪分析过程的当前状态，并根据当前状态和输入符号决定下一步动作（移进、归约、接受或报错）。这些方法的主要区别在于如何构建状态集（Item Sets）以及如何确定归约动作的适用性。理解这些方法的差异和联系，对于掌握编译原理和设计高效分析器至关重要。

LR(0)分析法：最基础的LR分析

LR(0)文法与LR(0)项目

LR(0)分析是LR分析家族中最简单的方法，它不向前查看任何输入符号来决定归约动作。LR(0)项目（Item）是在产生式右部某位置加点的产生式，例如对于产生式 A → αβγ，有四个LR(0)项目：A → ·αβγ、A → α·βγ、A → αβ·γ和A → αβγ·。

LR(0)项目集闭包的计算规则是：如果项目集中包含A → α·Bβ，那么需要将所有B的产生式（B → ·γ）加入到项目集中。LR(0)项目集的转换通过GOTO函数实现，当遇到符号X时，从当前项目集转移到新的项目集。

LR(0)分析表的构造

LR(0)分析表的构造步骤如下：

1. 构造LR(0)项目集规范族：从初始项目集开始，通过闭包和GOTO运算生成所有可能的项目集。
2. 确定状态动作：对于每个项目集和每个输入符号，确定移进、归约或报错。
3. 填充分析表：将动作填入ACTION表，将GOTO填入GOTO表。

LR(0)分析实例

考虑以下文法：

S → aA
A → b
A → ε

首先，我们构造LR(0)项目集规范族：

状态0（初始状态）：

• S’ → ·S （拓广文法）
• S → ·aA

状态1（从状态0遇到S）：

• S’ → S· （接受项目）

状态2（从状态0遇到a）：

• S → a·A
• A → ·b
• A → ·ε

状态3（从状态2遇到A）：

• S → aA· （归约项目）

状态4（从状态2遇到b）：

• A → b· （归约项目）

状态5（从状态2遇到ε）：

• A → ε· （归约项目）

对应的LR(0)分析表如下（用Python字典表示）：

# LR(0)分析表示例
action_table = {
    0: {'a': 's2', '$': 'err'},
    1: {'$': 'acc'},
    2: {'b': 's4', 'ε': 's5', 'A': 'g3'},
    3: {'$': 'r1'},  # S → aA
    4: {'$': 'r2'},  # A → b
    5: {'$': 'r3'}   # A → ε
}

goto_table = {
    0: {'S': 1},
    2: {'A': 3}
}

# 分析器伪代码
def lr0_analyzer(input_string):
    stack = [0]  # 状态栈
    input_pos = 0
    while True:
        current_state = stack[-1]
        current_symbol = input_string[input_pos]
        
        action = action_table[current_state].get(current_symbol, 'err')
        
        if action.startswith('s'):  # 移进
            next_state = int(action[1:])
            stack.append(current_symbol)
            stack.append(next_state)
            input_pos += 1
        elif action.startswith('r'):  # 归约
            rule_num = int(action[1:])
            # 根据规则弹出栈中符号
            if rule_num == 1:  # S → aA
                stack.pop(); stack.pop(); stack.pop(); stack.pop()  # 弹出 aA和状态
                stack.append('S')
                stack.append(goto_table[stack[-2]]['S'])
            elif rule_num == 2:  # A → b
                stack.pop(); stack.pop()  # 弹出 b和状态
                stack.append('A')
                stack.append(goto_table[stack[-2]]['A'])
            elif rule_num == 3:  # A → ε
                stack.append('A')
                stack.append(goto_table[stack[-2]]['A'])
        elif action == 'acc':
            return True
        else:
            return False

LR(0)的局限性

LR(0)分析法虽然简单，但存在明显的局限性。它无法处理某些看似合法的文法，因为LR(0)分析表可能产生冲突。例如，对于文法：

A → a
A → aA

在某个状态中，同时存在A → a·和A → a·A，导致移进-归约冲突。LR(0)要求分析表中每个条目只能有一个动作，这限制了其应用范围。

SLR(1)分析法：简单的LR分析

SLR(1)的基本思想

SLR(1)（Simple LR）通过引入FOLLOW集来解决LR(0)中的冲突问题。SLR(1)仍然使用LR(0)项目集规范族，但在决定归约动作时，会检查当前输入符号是否属于被归约非终结符的FOLLOW集。如果属于，则执行归约；否则，报错。

SLR(1)分析表的构造

SLR(1)分析表的构造步骤与LR(0)类似，但在确定归约动作时：

• 对于项目A → α·，只有在当前输入符号属于FOLLOW(A)时，才在ACTION表中设置归约动作。

SLR(1)分析实例

考虑以下文法：

S → L
L → a
L → aL

首先计算FOLLOW集：

• FOLLOW(S) = {$}
• FOLLOW(L) = {$, a} // 因为S → L，且L → aL

构造LR(0)项目集规范族：

状态0：

• S’ → ·S
• S → ·L
• L → ·a
• L → ·aL

状态1（遇到S）：

• S’ → S·

状态2（遇到L）：

• S → L·

状态3（遇到a）：

• L → a·
• L → a·L
• L → ·a
• L → ·aL

状态4（从状态3遇到L）：

• L → aL·

现在构造SLR(1)分析表：

# SLR(1)分析表示例
action_table = {
    0: {'a': 's3'},
    1: {'$': 'acc'},
    2: {'$': 'r1'},  # S → L, $ ∈ FOLLOW(S)
    3: {'a': 's3', '$': 'r2', 'L': 'g4'},  # $ ∈ FOLLOW(L), a ∈ FOLLOW(L)
    4: {'$': 'r3'}   # L → aL, $ ∈ FOLLOW(L)
}

goto_table = {
    0: {'S': 1, 'L': 2},
    3: {'L': 4}
}

# 归约规则：
# r1: S → L
# r2: L → a
# r3: L → aL

SLR(1)的优势与不足

SLR(1)通过FOLLOW集有效解决了许多LR(0)冲突，但仍然不够精确。在某些情况下，FOLLOW集包含的符号过多，导致不必要的归约动作，从而产生冲突。例如，对于文法：

S → aAa
S → aBb
A → c
B → c

在某个状态中，项目A → c·和B → c·同时存在，归约时需要检查FOLLOW(A)和FOLLOW(B)。如果FOLLOW(A)和FOLLOW(B)有交集，就会产生归约-归约冲突。

LR(1)分析法：规范的LR分析

LR(1)项目与向前看符号

LR(1)分析法通过为每个项目附加一个向前看符号（Lookahead）来解决SLR(1)的不足。LR(1)项目的形式为[A → α·β, a]，其中a是向前看符号，表示只有在输入符号为a时才能应用该归约。

LR(1)项目集闭包的计算规则：

1. 初始项目集包含[S’ → ·S, {$}]
2. 如果项目[A → α·Bβ, a]在集合中，则对于每个产生式B → γ，添加[B → ·γ, b]到集合中，其中b是FOLLOW(βa)中的符号。

LR(1)分析表的构造

LR(1)分析表的构造步骤：

1. 构造LR(1)项目集规范族
2. 对于每个项目集：
   • 如果包含[A → α·aβ, b]，则设置ACTION[i, a] = “移进到状态j”
   • 如果包含[A → α·, a]，则设置ACTION[i, a] = “归约A → α”
   • 如果包含[S’ → S·, \(]，则设置ACTION[i, \)] = “接受”

LR(1)分析实例

考虑以下文法：

S → aA
S → bB
A → c
B → c

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

状态0：

• [S’ → ·S, $]
• [S → ·aA, $]
• [S → ·bB, $]

状态1（遇到S）：

• [S’ → S·, $]

状态2（遇到a）：

• [S → a·A, $]
• [A → ·c, $]

状态3（遇到b）：

• [S → b·B, $]
• [B → ·c, $]

状态4（从状态2遇到A）：

• [S → aA·, $]

状态5（从状态3遇到B）：

• [S → bB·, $]

状态6（从状态2遇到c）：

• [A → c·, $]

状态7（从状态3遇到c）：

• [B → c·, $]

对应的LR(1)分析表：

# LR(1)分析表示例
action_table = {
    0: {'a': 's2', 'b': 's3'},
    1: {'$': 'acc'},
    2: {'c': 's6'},
    3: {'c': 's7'},
    4: {'$': 'r1'},  # S → aA
    5: {'$': 'r2'},  # S → bB
    6: {'$': 'r3'},  # A → c
    7: {'$': 'r4'}   # B → c
}

goto_table = {
    0: {'S': 1},
    2: {'A': 4},
    3: {'B': 5}
}

# 归约规则：
# r1: S → aA
# r2: S → bB
# r3: A → c
# r4: B → c

LR(1)的优缺点

LR(1)分析法能力最强，能够处理所有LR(1)文法，不会产生不必要的冲突。但其主要缺点是状态数量可能非常庞大，因为每个项目都带有不同的向前看符号，导致项目集数量急剧增加。这在实际实现中会带来较大的时间和空间开销。

LALR(1)分析法：向前看的LR分析

LALR(1)的基本思想

LALR(1)（Look-Ahead LR）是LR(1)的简化版本，它通过合并LR(1)项目集中具有相同核心（即去掉向前看符号的项目）的状态来减少状态数量。LALR(1)分析表的大小与SLR(1)相同，但分析能力更强，能够处理更多文法。

LALR(1)分析表的构造

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

1. 首先构造完整的LR(1)项目集规范族
2. 合并具有相同核心的LR(1)项目集
3. 在合并后的项目集中，向前看符号是原项目集向前看符号的并集
4. 根据合并后的项目集构造分析表

LALR(1)分析实例

考虑以下文法：

S → aA
A → aA
A → b

首先构造LR(1)项目集规范族，然后合并具有相同核心的状态：

状态0：

• [S’ → ·S, $]
• [S → ·aA, $]

状态1（遇到S）：

• [S’ → S·, $]

状态2（遇到a）：

• [S → a·A, $]
• [A → ·aA, $]
• [A → ·b, $]

状态3（遇到A）：

• [S → aA·, $]

状态4（从状态2遇到a）：

• [A → a·A, $]
• [A → a·A, \(] # 与上面相同，合并后向前看符号仍为\)
• [A → ·aA, $]
• [A → ·b, $]

状态5（从状态2遇到b）：

• [A → b·, $]

状态6（从状态4遇到A）：

• [A → aA·, $]

状态7（从状态4遇到a）：

• [A → a·A, $]
• [A → ·aA, $]
• [A → ·b, $]

实际上，状态4和状态7具有相同核心（A → a·A, A → ·aA, A → ·b），可以合并。合并后的状态记为状态4’，向前看符号为$。

LALR(1)分析表：

# LALR(1)分析表示例
action_table = {
    0: {'a': 's2'},
    1: {'$': 'acc'},
    2: {'a': 's4', 'b': 's5'},
    3: {'$': 'r1'},  # S → aA
    4: {'a': 's4', 'b': 's5', '$': 'r2'},  # A → aA, $ ∈ FOLLOW(A)
    5: {'$': 'r3'},  # A → b
    6: {'$': 'r2'}   # A → aA
}

goto_table = {
    0: {'S': 1},
    2: {'A': 3},
    4: {'A': 6}
}

# 归约规则：
# r1: S → aA
# r2: A → aA
# r3: A → b

LALR(1)的优势

LALR(1)分析法在状态数量和分析能力之间取得了很好的平衡。它比LR(1)更紧凑，通常只比SLR(1)稍多一些状态，但分析能力更强。许多实际的编译器生成器（如YACC、Bison）都采用LALR(1)分析法。

四种LR分析法的比较

分析能力比较

分析方法	分析能力	状态数量	冲突解决方式
LR(0)	最弱，只能处理LR(0)文法	最少	无法解决冲突
SLR(1)	较弱，能处理部分LR(1)文法	较少	使用FOLLOW集
LR(1)	最强，能处理所有LR(1)文法	最多	使用精确的向前看符号
LALR(1)	较强，能处理大多数LR(1)文法	中等	合并LR(1)状态

实际应用中的选择

在实际编译器设计中，LALR(1)是最常用的方法，因为它：

1. 状态数量可控，分析表大小适中
2. 分析能力足够强，能处理大多数编程语言文法
3. 有成熟的工具支持（YACC、Bison等）

LR(1)适用于需要处理复杂文法的场景，但需要更多资源。SLR(1)适用于简单文法，而LR(0)主要用于教学和理解基本原理。

总结

规范LR分析包括LR(0)、SLR(1)、LR(1)和LALR(1)四种方法，它们构成了自底向上语法分析的核心理论体系。从LR(0)到LR(1)，分析能力逐步增强，但实现复杂度也随之增加。LALR(1)作为LR(1)的优化版本，在实际应用中达到了最佳平衡。理解这些方法的原理和差异，对于掌握编译原理和设计高效编译器至关重要。在实际项目中，应根据文法复杂度和性能要求选择合适的分析方法。