第54集：LL(1)预测分析器

学习目标

理解LL(1)预测分析器的基本原理
掌握预测分析表的构建方法
了解LL(1)分析器的工作过程
学会处理LL(1)分析中的错误恢复
能够使用Python实现简单的LL(1)预测分析器

1. LL(1)预测分析器概述

1.1 基本原理

LL(1)预测分析器是一种基于表驱动的自顶向下语法分析方法，它的基本原理是：

从左到右扫描输入符号串
构建最左推导
每一步只需要向前看一个符号就能决定使用哪个产生式
使用预测分析表来存储产生式的选择信息

1.2 与递归下降分析器的比较

递归下降分析器：

用递归函数实现，代码结构清晰
对于简单文法实现容易
可能存在回溯问题
错误处理相对简单

LL(1)预测分析器：

基于表驱动，使用非递归实现
对于复杂文法更系统
无回溯，效率更高
错误处理需要额外设计

1.3 组成部分

LL(1)预测分析器由以下三部分组成：

输入缓冲区：存储待分析的词法单元序列，以结束符 $ 结尾
分析栈：存储文法符号，初始时包含开始符号和结束符 $ 3. 预测分析表：二维表，根据当前栈顶符号和当前输入符号决定下一步操作

2. 预测分析表的构建

2.1 构建步骤

消除左递归：确保文法无左递归
提取左因子：确保文法是LL(1)的
计算FIRST集：对每个文法符号串计算FIRST集
计算FOLLOW集：对每个非终结符计算FOLLOW集
构建分析表：根据FIRST集和FOLLOW集填充分析表

2.2 FIRST集的计算

计算规则：

对于终结符 a，FIRST(a) = {a}
对于非终结符 A：
- 如果有产生式 A → ε，则 ε ∈ FIRST(A)
- 如果有产生式 A → X₁X₂...Xₙ，则对于每个 i 从 1 到 n：
  - 将 FIRST(Xᵢ) 中除 ε 以外的符号加入 FIRST(A)
  - 如果对于所有 j < i，ε ∈ FIRST(Xⱼ)，则继续；否则停止
- 如果对于所有 i，ε ∈ FIRST(Xᵢ)，则 ε ∈ FIRST(A)

示例：

对于文法：

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id | num

计算FIRST集：

FIRST(E) = FIRST(T) = FIRST(F) = {(, id, num}
FIRST(E') = {+, ε}
FIRST(T) = FIRST(F) = {(, id, num}
FIRST(T') = {*, ε}
FIRST(F) = {(, id, num}

2.3 FOLLOW集的计算

计算规则：

对于开始符号 S，将 $ 加入 FOLLOW(S)
对于产生式 A → αBβ：
- 将 FIRST(β) 中除 ε 以外的符号加入 FOLLOW(B)
- 如果 ε ∈ FIRST(β)，则将 FOLLOW(A) 加入 FOLLOW(B)

示例：

对于上述文法，计算FOLLOW集：

FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(T') = {+, ), $}
FOLLOW(F) = {*, +, ), $}

2.4 分析表的填充

对于每个产生式 A → α，执行以下操作：

对于每个终结符 a ∈ FIRST(α)，将 A → α 填入分析表 M[A, a]
如果 ε ∈ FIRST(α)，则对于每个终结符 b ∈ FOLLOW(A)，将 A → α 填入分析表 M[A, b]

示例：

对于上述文法，构建分析表：

非终结符	id	num	+	*	(	)	$
E	E→TE'	E→TE'			E→TE'
E'			E'→+TE'			E'→ε	E'→ε
T	T→FT'	T→FT'			T→FT'
T'			T'→ε	T'→*FT'		T'→ε	T'→ε
F	F→id	F→num			F→(E)

3. LL(1)分析器的工作过程

3.1 工作步骤

初始化：将开始符号压入栈，输入指针指向第一个输入符号
循环处理：重复以下步骤直到栈为空：
- 设栈顶符号为 X，当前输入符号为 a
- 如果 X 是终结符：
  - 如果 X == a，则弹出 X，输入指针移到下一个符号
  - 否则，报错
- 如果 X 是非终结符：
  - 查看分析表 M[X, a]
  - 如果 M[X, a] 是产生式 X → α，则弹出 X，将 α 的符号按逆序压入栈
  - 如果 M[X, a] 为空，则报错
- 如果 X == $ 且 a == $，则分析成功

3.2 示例分析

以表达式 id + num 为例，使用上述文法进行分析：

初始状态：

栈：$ E
输入：id + num $

步骤1：

栈顶符号 E，当前输入 id
查分析表 M[E, id] = E→TE'
弹出 E，压入 E' T
栈：$ E' T
输入：id + num $

步骤2：

栈顶符号 T，当前输入 id
查分析表 M[T, id] = T→FT'
弹出 T，压入 T' F
栈：$ E' T' F
输入：id + num $

步骤3：

栈顶符号 F，当前输入 id
查分析表 M[F, id] = F→id
弹出 F，压入 id
栈：$ E' T' id
输入：id + num $

步骤4：

栈顶符号 id，当前输入 id
匹配成功，弹出 id，输入指针后移
栈：$ E' T'
输入：+ num $

步骤5：

栈顶符号 T'，当前输入 +
查分析表 M[T', +] = T'→ε
弹出 T'
栈：$ E'
输入：+ num $

步骤6：

栈顶符号 E'，当前输入 +
查分析表 M[E', +] = E'→+TE'
弹出 E'，压入 E' T +
栈：$ E' T +
输入：+ num $

步骤7：

栈顶符号 +，当前输入 +
匹配成功，弹出 +，输入指针后移
栈：$ E' T
输入：num $

步骤8：

栈顶符号 T，当前输入 num
查分析表 M[T, num] = T→FT'
弹出 T，压入 T' F
栈：$ E' T' F
输入：num $

步骤9：

栈顶符号 F，当前输入 num
查分析表 M[F, num] = F→num
弹出 F，压入 num
栈：$ E' T' num
输入：num $

步骤10：

栈顶符号 num，当前输入 num
匹配成功，弹出 num，输入指针后移
栈：$ E' T'
输入：$

步骤11：

栈顶符号 T'，当前输入 $
查分析表 M[T', $] = T'→ε
弹出 T'
栈：$ E'
输入：$

步骤12：

栈顶符号 E'，当前输入 $
查分析表 M[E', $] = E'→ε
弹出 E'
栈：$
输入：$

分析成功！

4. 实战案例：LL(1)预测分析器实现

4.1 文法定义

我们使用以下文法来实现LL(1)预测分析器：

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id | num

4.2 计算FIRST集和FOLLOW集

FIRST集：

FIRST(E) = {(, id, num}
FIRST(E') = {+, ε}
FIRST(T) = {(, id, num}
FIRST(T') = {*, ε}
FIRST(F) = {(, id, num}

FOLLOW集：

FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(T') = {+, ), $}
FOLLOW(F) = {*, +, ), $}

4.3 构建预测分析表

# 预测分析表
predict_table = {
    'E': {
        'id': 'T E',
        'num': 'T E',
        '(': 'T E'
    },
    'E': {
        '+': '+ T E',
        ')': 'ε',
        '$': 'ε'
    },
    'T': {
        'id': 'F T',
        'num': 'F T',
        '(': 'F T'
    },
    'T': {
        '+': 'ε',
        '*': '* F T',
        ')': 'ε',
        '$': 'ε'
    },
    'F': {
        'id': 'id',
        'num': 'num',
        '(': '( E )'
    }
}

4.4 实现LL(1)预测分析器

class LL1Parser:
    def __init__(self, tokens):
        self.tokens = tokens  # 词法单元列表
        self.pos = 0  # 当前输入位置
        self.stack = ['$', 'E']  # 分析栈，初始包含结束符和开始符号
        self.predict_table = {
            'E': {
                'id': 'T E',
                'num': 'T E',
                '(': 'T E'
            },
            'E': {
                '+': '+ T E',
                ')': 'ε',
                '$': 'ε'
            },
            'T': {
                'id': 'F T',
                'num': 'F T',
                '(': 'F T'
            },
            'T': {
                '+': 'ε',
                '*': '* F T',
                ')': 'ε',
                '$': 'ε'
            },
            'F': {
                'id': 'id',
                'num': 'num',
                '(': '( E )'
            }
        }

    def get_current_token(self):
        """获取当前输入符号"""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos].type
        else:
            return '$'

    def error(self, message):
        """报错"""
        print(f"Error at position {self.pos}: {message}")
        print(f"Current token: {self.get_current_token()}")
        print(f"Current stack: {self.stack}")
        raise Exception(message)

    def parse(self):
        """开始分析"""
        print("LL(1) Parsing Process:")
        print("Stack\t\tInput\t\tAction")
        print("-" * 50)
        
        while len(self.stack) > 0:
            # 打印当前状态
            stack_str = ' '.join(reversed(self.stack))
            input_str = ' '.join([token.type for token in self.tokens[self.pos:]] + ['$'])
            print(f"{stack_str}\t\t{input_str}", end="\t\t")
            
            X = self.stack[-1]  # 栈顶符号
            a = self.get_current_token()  # 当前输入符号
            
            if X == '$' and a == '$':
                # 分析成功
                print("Accept")
                self.stack.pop()
            elif X in ['id', 'num', '+', '*', '(', ')']:
                # X 是终结符
                if X == a:
                    # 匹配成功
                    print(f"Match {X}")
                    self.stack.pop()
                    self.pos += 1
                else:
                    # 匹配失败
                    self.error(f"Expected {X}, found {a}")
            else:
                # X 是非终结符
                if a in self.predict_table.get(X, {}):
                    production = self.predict_table[X][a]
                    if production == 'ε':
                        # 使用空产生式
                        print(f"Predict {X} → ε")
                        self.stack.pop()
                    else:
                        # 使用非空产生式
                        print(f"Predict {X} → {production}")
                        self.stack.pop()
                        # 将产生式右部逆序压入栈
                        symbols = production.split()
                        for symbol in reversed(symbols):
                            self.stack.append(symbol)
                else:
                    # 无对应的产生式
                    self.error(f"No production for {X} with input {a}")
        
        print("\nParsing completed successfully!")

# 测试代码
if __name__ == "__main__":
    from lexer import Lexer, Token
    
    # 测试表达式
    text = "id + num * (id - num)"
    print(f"Testing expression: {text}")
    
    # 词法分析
    lexer = Lexer(text)
    tokens = []
    while True:
        token = lexer.get_next_token()
        if token.type == 'EOF':
            break
        tokens.append(token)
    
    print(f"Tokens: {[str(token) for token in tokens]}")
    
    # 语法分析
    parser = LL1Parser(tokens)
    try:
        parser.parse()
    except Exception as e:
        print(f"Parsing failed: {e}")

4.5 测试示例

测试输入：

id + num * (id - num)

词法分析结果：

Tokens: [Token(id, id), Token(+, +), Token(num, num), Token(*, *), Token((, (), Token(id, id), Token(-, -), Token(num, num), Token(), ))]

语法分析过程：

LL(1) Parsing Process:
Stack		Input		Action
--------------------------------------------------
E $		id + num * ( id - num ) $		Predict E → T E'
T E' $		id + num * ( id - num ) $		Predict T → F T'
F T' E' $		id + num * ( id - num ) $		Predict F → id
id T' E' $		id + num * ( id - num ) $		Match id
T' E' $		+ num * ( id - num ) $		Predict T' → ε
E' $		+ num * ( id - num ) $		Predict E' → + T E'
+ T E' $		+ num * ( id - num ) $		Match +
T E' $		num * ( id - num ) $		Predict T → F T'
F T' E' $		num * ( id - num ) $		Predict F → num
num T' E' $		num * ( id - num ) $		Match num
T' E' $		* ( id - num ) $		Predict T' → * F T'
* F T' E' $		* ( id - num ) $		Match *
F T' E' $		( id - num ) $		Predict F → ( E )
( E ) T' E' $		( id - num ) $		Match (
E ) T' E' $		id - num ) $		Predict E → T E'
T E' ) T' E' $		id - num ) $		Predict T → F T'
F T' E' ) T' E' $		id - num ) $		Predict F → id
id T' E' ) T' E' $		id - num ) $		Match id
T' E' ) T' E' $		- num ) $		Predict T' → ε
E' ) T' E' $		- num ) $		Error at position 6: No production for E' with input -
Current token: -
Current stack: ['$', 'E', ')', "T'", "E'"]
Parsing failed: No production for E' with input -

注意： 上面的错误是因为我们的文法没有包含减号 - 的产生式。需要扩展文法来支持减法操作。

5. LL(1)分析中的错误处理

5.1 错误检测

LL(1)分析器在以下两种情况下检测到错误：

栈顶是终结符，但与当前输入符号不匹配
栈顶是非终结符，但分析表中没有对应的产生式

5.2 错误恢复策略

恐慌模式恢复：

跳过输入符号直到找到同步符号（如分号、右括号等）
弹出栈顶符号直到找到可以处理同步符号的非终结符
继续分析

短语级恢复：

对错误输入进行局部修正，如插入、删除或替换符号
选择修正后能够继续分析的操作
记录错误信息但继续分析

错误产生式：

在文法中添加专门处理错误的产生式
当遇到错误时，使用这些产生式进行恢复

5.3 错误恢复实现示例

def error_recovery(self):
    """恐慌模式错误恢复"""
    print("Error recovery started...")
    
    # 同步符号集合
    sync_symbols = ['+', '*', ')', '$']
    
    # 跳过输入符号直到找到同步符号
    a = self.get_current_token()
    while a not in sync_symbols:
        print(f"Skipping token: {a}")
        self.pos += 1
        a = self.get_current_token()
        if a == '$':
            break
    
    # 弹出栈顶符号直到找到可以处理同步符号的非终结符
    while len(self.stack) > 0:
        X = self.stack[-1]
        if X in ['$', 'E', 'T', 'F'] and a in self.predict_table.get(X, {}):
            print(f"Error recovery completed. Resuming with stack: {self.stack}")
            return
        else:
            print(f"Popping from stack: {X}")
            self.stack.pop()
    
    print("Error recovery failed. Aborting parsing.")

6. 扩展文法以支持更多操作

6.1 支持减法和除法

扩展后的文法：

E → T E'
E' → + T E' | - T E' | ε
T → F T'
T' → * F T' | / F T' | ε
F → ( E ) | id | num

6.2 重新计算FIRST集和FOLLOW集

FIRST集：

FIRST(E) = {(, id, num}
FIRST(E') = {+, -, ε}
FIRST(T) = {(, id, num}
FIRST(T') = {*, /, ε}
FIRST(F) = {(, id, num}

FOLLOW集：

FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, -, ), $}
FOLLOW(T') = {+, -, ), $}
FOLLOW(F) = {*, /, +, -, ), $}

6.3 更新预测分析表

predict_table = {
    'E': {
        'id': 'T E',
        'num': 'T E',
        '(': 'T E'
    },
    'E': {
        '+': '+ T E',
        '-': '- T E',
        ')': 'ε',
        '$': 'ε'
    },
    'T': {
        'id': 'F T',
        'num': 'F T',
        '(': 'F T'
    },
    'T': {
        '+': 'ε',
        '-': 'ε',
        '*': '* F T',
        '/': '/ F T',
        ')': 'ε',
        '$': 'ε'
    },
    'F': {
        'id': 'id',
        'num': 'num',
        '(': '( E )'
    }
}

7. 自测题

LL(1)预测分析器的基本原理是什么？
如何构建LL(1)预测分析表？
什么是FIRST集和FOLLOW集？如何计算它们？
LL(1)分析器的错误处理策略有哪些？

实现一个LL(1)预测分析器，处理以下文法：

S → if ( E ) S | while ( E ) S | { L }
L → S L | ε
E → T E'
E' → + T E' | - T E' | ε
T → F T'
T' → * F T' | / F T' | ε
F → ( E ) | id | num

8. 小结

在本集中，我们介绍了LL(1)预测分析器的基本原理、实现方法和应用场景。LL(1)预测分析器是一种基于表驱动的自顶向下语法分析方法，它通过预测分析表来存储产生式的选择信息，避免了递归下降分析中的回溯问题，提高了分析效率。我们还介绍了预测分析表的构建方法，包括FIRST集和FOLLOW集的计算，以及LL(1)分析中的错误处理策略。通过Python实现的LL(1)预测分析器，我们展示了其实际应用。

9. 下集预告

下一集将介绍 LR分析器，这是一种自底向上的语法分析方法，它比LL(1)分析器更强大，可以处理更多类型的文法，是现代编译器中常用的语法分析方法。

10. 参考资料

《编译原理》（龙书），Alfred V. Aho 等著
《编译原理教程》，蒋立源等著
《编译器设计》，Alexander A. Stepanov 等著
LL Parser - Wikipedia：https://en.wikipedia.org/wiki/LL_parser
Predictive parser - Wikipedia：https://en.wikipedia.org/wiki/Predictive_parser