第78集：LL(1)分析表构造

学习目标

• 掌握FIRST集的定义和计算方法
• 学会计算FOLLOW集
• 理解LL(1)分析表的构造原理
• 掌握构建LL(1)分析表的步骤
• 通过示例演练巩固LL(1)分析表的构造技巧

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

LL(1)分析表是预测分析器的核心组件，它是一个二维表格，用于指导预测分析器在分析过程中选择正确的产生式。

LL(1)分析表的结构

LL(1)分析表通常表示为一个二维数组 M，其中：

• 行：对应文法的非终结符
• 列：对应文法的终结符（包括结束符 $）
• 表项：对于每个非终结符 A 和终结符 a，M[A, a] 表示当当前栈顶符号是 A 且当前输入Token是 a 时，应该使用的产生式 A → α，或者表示错误

LL(1)分析表的作用

LL(1)分析表的作用是：

1. 指导产生式选择：在预测分析过程中，根据当前栈顶非终结符和当前输入Token，选择正确的产生式
2. 避免回溯：通过预计算的信息，确保每个表项最多只有一个产生式，避免回溯
3. 提高分析效率：直接查表获取产生式，不需要尝试多个产生式

二、FIRST集的计算

FIRST集是构造LL(1)分析表的重要组成部分，它表示一个符号串能够推导出的所有可能的第一个终结符的集合。

FIRST集的定义

1. 对于终结符 a：FIRST(a) = {a}

2. 对于非终结符 A：FIRST(A) 是所有可能由 A 推导出的第一个终结符的集合，即：

   • 如果 A → ε 是一个产生式，则 ε ∈ FIRST(A)
   • 如果 A → X₁X₂...Xₙ 是一个产生式，且 X₁ 是终结符，则 X₁ ∈ FIRST(A)
   • 如果 A → X₁X₂...Xₙ 是一个产生式，且 X₁ 是非终结符，则 FIRST(X₁) 中除 ε 以外的所有元素都属于 FIRST(A)；如果 X₁ ⇒* ε，则 FIRST(X₂) 中除 ε 以外的所有元素也属于 FIRST(A)，以此类推

3. 对于符号串 α = X₁X₂...Xₙ：FIRST(α) 是所有可能由 α 推导出的第一个终结符的集合，计算方法类似非终结符的FIRST集

FIRST集的计算算法

计算FIRST集的算法如下：

1. 初始化：对于每个终结符 a，FIRST(a) = {a}；对于每个非终结符 A，FIRST(A) 初始化为空集

2. 迭代计算：反复应用以下规则，直到所有FIRST集不再变化：

   • 对于每个产生式 A → α：
     a. 令 β = α
     b. 重复：
     i. 如果 β 为空串，则将 ε 添加到 FIRST(A)
     ii. 否则，令 X 为 β 的第一个符号：
     - 如果 X 是终结符，则将 X 添加到 FIRST(A)，停止
     - 如果 X 是非终结符：
     - 将 FIRST(X) 中除 ε 以外的所有元素添加到 FIRST(A)
     - 如果 ε ∈ FIRST(X)，则令 β 为 β 去除第一个符号后的剩余部分
     - 否则，停止

示例：计算FIRST集

考虑以下文法：

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

计算各非终结符的FIRST集：

1. **FIRST(F)**：

   • F → (E)，所以 ( ∈ FIRST(F)
   • F → id，所以 id ∈ FIRST(F)
   • 因此，FIRST(F) = {(, id}

2. **FIRST(T')**：

   • T' → * FT'，所以 * ∈ FIRST(T')
   • T' → ε，所以 ε ∈ FIRST(T')
   • 因此，FIRST(T') = {*, ε}

3. **FIRST(T)**：

   • T → FT'
   • FIRST(F) = {(, id}，且 F 不能推导出 ε
   • 因此，FIRST(T) = FIRST(F) = {(, id}

4. **FIRST(E')**：

   • E' → + TE'，所以 + ∈ FIRST(E')
   • E' → ε，所以 ε ∈ FIRST(E')
   • 因此，FIRST(E') = {+, ε}

5. **FIRST(E)**：

   • E → TE'
   • FIRST(T) = {(, id}，且 T 不能推导出 ε
   • 因此，FIRST(E) = FIRST(T) = {(, id}

三、FOLLOW集的计算

FOLLOW集是构造LL(1)分析表的另一个重要组成部分，它表示一个非终结符后面可能跟随的所有终结符的集合。

FOLLOW集的定义

对于非终结符 A，FOLLOW(A) 是所有可能出现在 A 后面的终结符的集合，即：

• 如果 A 是开始符号，则结束符 $ ∈ FOLLOW(A)
• 如果存在产生式 B → αAβ，则 FIRST(β) 中除 ε 以外的所有元素都属于 FOLLOW(A)
• 如果存在产生式 B → αA 或 B → αAβ且 ε ∈ FIRST(β)，则 FOLLOW(B) 中的所有元素都属于 FOLLOW(A)

FOLLOW集的计算算法

计算FOLLOW集的算法如下：

1. 初始化：对于开始符号 S，将 $ 添加到 FOLLOW(S)；对于其他非终结符 A，FOLLOW(A) 初始化为空集

2. 迭代计算：反复应用以下规则，直到所有FOLLOW集不再变化：

   • 对于每个产生式 A → αBβ：
     a. 将 FIRST(β) 中除 ε 以外的所有元素添加到 FOLLOW(B)
     b. 如果 ε ∈ FIRST(β)，则将 FOLLOW(A) 中的所有元素添加到 FOLLOW(B)
   • 对于每个产生式 A → αB：
     a. 将 FOLLOW(A) 中的所有元素添加到 FOLLOW(B)

示例：计算FOLLOW集

继续使用上面的文法：

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

计算各非终结符的FOLLOW集：

1. 初始化：

   • FOLLOW(E) = {$}
   • FOLLOW(E') = ∅
   • FOLLOW(T) = ∅
   • FOLLOW(T') = ∅
   • FOLLOW(F) = ∅

2. 迭代计算：

   **处理产生式 E → TE'**：

   • B = T，β = E'

   • FIRST(E') = {+, ε}，所以将 + 添加到 FOLLOW(T)

   • 因为 ε ∈ FIRST(E')，所以将 FOLLOW(E) = {$} 添加到 FOLLOW(T)

   • 因此，FOLLOW(T) = {+, $}

   • B = E'，β = ε

   • 所以将 FOLLOW(E) = {$} 添加到 FOLLOW(E')

   • 因此，FOLLOW(E') = {$}

   **处理产生式 E' → + TE'**：

   • B = T，β = E'

   • FIRST(E') = {+, ε}，所以将 + 添加到 FOLLOW(T)

   • 因为 ε ∈ FIRST(E')，所以将 FOLLOW(E') = {$} 添加到 FOLLOW(T)

   • 因此，FOLLOW(T) 保持 {+, $}

   • B = E'，β = ε

   • 所以将 FOLLOW(E') = {$} 添加到 FOLLOW(E')

   • 因此，FOLLOW(E') 保持 {$}

   **处理产生式 T → FT'**：

   • B = F，β = T'

   • FIRST(T') = {*, ε}，所以将 * 添加到 FOLLOW(F)

   • 因为 ε ∈ FIRST(T')，所以将 FOLLOW(T) = {+, $} 添加到 FOLLOW(F)

   • 因此，FOLLOW(F) = {*, +, $}

   • B = T'，β = ε

   • 所以将 FOLLOW(T) = {+, $} 添加到 FOLLOW(T')

   • 因此，FOLLOW(T') = {+, $}

   **处理产生式 T' → * FT'**：

   • B = F，β = T'

   • FIRST(T') = {*, ε}，所以将 * 添加到 FOLLOW(F)

   • 因为 ε ∈ FIRST(T')，所以将 FOLLOW(T') = {+, $} 添加到 FOLLOW(F)

   • 因此，FOLLOW(F) 保持 {*, +, $}

   • B = T'，β = ε

   • 所以将 FOLLOW(T') = {+, $} 添加到 FOLLOW(T')

   • 因此，FOLLOW(T') 保持 {+, $}

   **处理产生式 F → (E)**：

   • B = E，β = )
   • FIRST()) = {)}, 所以将 ) 添加到 FOLLOW(E)
   • 因此，FOLLOW(E) = {$, )}

   **再次处理产生式 E → TE'**：

   • B = T，β = E'

   • FIRST(E') = {+, ε}，所以将 + 添加到 FOLLOW(T)

   • 因为 ε ∈ FIRST(E')，所以将 FOLLOW(E) = {$, )} 添加到 FOLLOW(T)

   • 因此，FOLLOW(T) = {+, $, )}

   • B = E'，β = ε

   • 所以将 FOLLOW(E) = {$, )} 添加到 FOLLOW(E')

   • 因此，FOLLOW(E') = {$, )}

   **再次处理产生式 E' → + TE'**：

   • B = T，β = E'

   • FIRST(E') = {+, ε}，所以将 + 添加到 FOLLOW(T)

   • 因为 ε ∈ FIRST(E')，所以将 FOLLOW(E') = {$, )} 添加到 FOLLOW(T)

   • 因此，FOLLOW(T) = {+, $, )}

   • B = E'，β = ε

   • 所以将 FOLLOW(E') = {$, )} 添加到 FOLLOW(E')

   • 因此，FOLLOW(E') 保持 {$, )}

   **再次处理产生式 T → FT'**：

   • B = F，β = T'

   • FIRST(T') = {*, ε}，所以将 * 添加到 FOLLOW(F)

   • 因为 ε ∈ FIRST(T')，所以将 FOLLOW(T) = {+, $, )} 添加到 FOLLOW(F)

   • 因此，FOLLOW(F) = {*, +, $, )}

   • B = T'，β = ε

   • 所以将 FOLLOW(T) = {+, $, )} 添加到 FOLLOW(T')

   • 因此，FOLLOW(T') = {+, $, )}

   **再次处理产生式 T' → * FT'**：

   • B = F，β = T'

   • FIRST(T') = {*, ε}，所以将 * 添加到 FOLLOW(F)

   • 因为 ε ∈ FIRST(T')，所以将 FOLLOW(T') = {+, $, )} 添加到 FOLLOW(F)

   • 因此，FOLLOW(F) 保持 {*, +, $, )}

   • B = T'，β = ε

   • 所以将 FOLLOW(T') = {+, $, )} 添加到 FOLLOW(T')

   • 因此，FOLLOW(T') 保持 {+, $, )}

3. 最终结果：

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

四、LL(1)分析表的构造

LL(1)分析表的构造基于FIRST集和FOLLOW集，它为每个非终结符和终结符的组合指定应该使用的产生式。

LL(1)分析表的构造算法

构造LL(1)分析表的算法如下：

1. 初始化：创建一个二维表格 M，行对应非终结符，列对应终结符（包括结束符 $），所有表项初始化为错误

2. 填充表格：对于每个产生式 A → α：
   a. 计算 FIRST(α)
   b. 对于每个终结符 a ∈ FIRST(α)：

   • 将产生式 A → α 填入 M[A, a]
     c. 如果 ε ∈ FIRST(α)，则对于每个终结符 b ∈ FOLLOW(A)：
   • 将产生式 A → α 填入 M[A, b]

3. 检查冲突：如果任何表项有多个产生式，则文法不是LL(1)的

示例：构造LL(1)分析表

继续使用上面的文法和计算得到的FIRST集和FOLLOW集：

FIRST集：

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

FOLLOW集：

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

构造LL(1)分析表：

分析表的解释

• 当栈顶符号是 E 且当前输入Token是 id 或 ( 时，使用产生式 E → TE'
• 当栈顶符号是 E' 且当前输入Token是 + 时，使用产生式 E' → + TE'；当当前输入Token是 ) 或 $ 时，使用产生式 E' → ε
• 当栈顶符号是 T 且当前输入Token是 id 或 ( 时，使用产生式 T → FT'
• 当栈顶符号是 T' 且当前输入Token是 * 时，使用产生式 T' → * FT'；当当前输入Token是 +、) 或 $ 时，使用产生式 T' → ε
• 当栈顶符号是 F 且当前输入Token是 id 时，使用产生式 F → id；当当前输入Token是 ( 时，使用产生式 F → (E)

五、LL(1)分析表的使用

LL(1)分析表用于预测分析器中，指导分析过程。预测分析器的工作过程如下：

预测分析器的工作过程

1. 初始化：将开始符号压入栈，输入指针指向第一个Token
2. 循环：
   a. 取出栈顶符号 X
   b. 如果 X 是终结符：
   i. 如果 X 与当前输入Token匹配，输入指针前进一位
   ii. 否则，分析失败
   c. 如果 X 是结束符 $：
   i. 如果当前输入Token也是 $，分析成功
   ii. 否则，分析失败
   d. 如果 X 是非终结符：
   i. 查看分析表 M[X, a]，其中 a 是当前输入Token
   ii. 如果 M[X, a] 是产生式 X → α，将 X 弹出栈，将 α 逆序压入栈
   iii. 如果 M[X, a] 是错误，分析失败

示例：使用LL(1)分析表分析表达式

使用上面构造的LL(1)分析表，分析输入串 id + id * id $：

六、LL(1)文法的判定

一个文法是LL(1)的，当且仅当构造的LL(1)分析表中没有冲突（即每个表项最多只有一个产生式）。

冲突的类型

LL(1)分析表中可能出现的冲突包括：

1. FIRST集冲突：对于同一个非终结符 A 和终结符 a，多个产生式的FIRST集都包含 a
2. FOLLOW集冲突：对于产生式 A → ε，终结符 a 同时属于某个产生式的FIRST集和 A 的FOLLOW集

解决冲突的方法

1. 消除左递归：左递归会导致FIRST集冲突
2. 提取左公因子：左公因子会导致FIRST集冲突
3. 重写文法：对于某些特殊情况，可能需要重写文法以避免冲突

七、代码示例：计算FIRST集和FOLLOW集

下面是一个简单的Python代码，用于计算文法的FIRST集和FOLLOW集：

class GrammarAnalyzer:
    def __init__(self, productions, start_symbol):
        """
        初始化文法分析器
        productions: 字典，键为非终结符，值为产生式右部列表
        start_symbol: 开始符号
        """
        self.productions = productions
        self.start_symbol = start_symbol
        self.non_terminals = set(productions.keys())
        self.terminals = self._collect_terminals()
        self.first = {}
        self.follow = {}
        self._initialize_first()
        self._initialize_follow()
    
    def _collect_terminals(self):
        """收集所有终结符"""
        terminals = set()
        for prods in self.productions.values():
            for prod in prods:
                for symbol in prod:
                    if symbol not in self.non_terminals:
                        terminals.add(symbol)
        return terminals
    
    def _initialize_first(self):
        """初始化FIRST集"""
        # 终结符的FIRST集
        for terminal in self.terminals:
            self.first[terminal] = {terminal}
        # 非终结符的FIRST集初始化为空
        for nt in self.non_terminals:
            self.first[nt] = set()
    
    def _initialize_follow(self):
        """初始化FOLLOW集"""
        for nt in self.non_terminals:
            self.follow[nt] = set()
        # 开始符号的FOLLOW集包含$
        self.follow[self.start_symbol].add('$')
    
    def compute_first(self):
        """计算所有非终结符的FIRST集"""
        changed = True
        while changed:
            changed = False
            for nt, prods in self.productions.items():
                for prod in prods:
                    current_first = set()
                    beta = prod
                    has_epsilon = True
                    
                    while beta and has_epsilon:
                        first_symbol = beta[0]
                        if first_symbol in self.terminals:
                            current_first.add(first_symbol)
                            has_epsilon = False
                        else:
                            # 非终结符
                            first_of_symbol = self.first[first_symbol]
                            current_first.update(first_of_symbol - {'ε'})
                            if 'ε' not in first_of_symbol:
                                has_epsilon = False
                            else:
                                beta = beta[1:]
                    
                    if not beta:
                        current_first.add('ε')
                    
                    # 检查是否有变化
                    if not current_first.issubset(self.first[nt]):
                        self.first[nt].update(current_first)
                        changed = True
        return self.first
    
    def compute_follow(self):
        """计算所有非终结符的FOLLOW集"""
        # 确保FIRST集已计算
        if not self.first:
            self.compute_first()
        
        changed = True
        while changed:
            changed = False
            for nt, prods in self.productions.items():
                for prod in prods:
                    for i, symbol in enumerate(prod):
                        if symbol in self.non_terminals:
                            # 计算beta = prod[i+1:]
                            beta = prod[i+1:]
                            if beta:
                                # 计算FIRST(beta)
                                first_beta = set()
                                has_epsilon = True
                                temp_beta = beta
                                
                                while temp_beta and has_epsilon:
                                    b_symbol = temp_beta[0]
                                    if b_symbol in self.terminals:
                                        first_beta.add(b_symbol)
                                        has_epsilon = False
                                    else:
                                        first_beta.update(self.first[b_symbol] - {'ε'})
                                        if 'ε' not in self.first[b_symbol]:
                                            has_epsilon = False
                                        else:
                                            temp_beta = temp_beta[1:]
                                
                                # 将FIRST(beta)中除ε以外的元素添加到FOLLOW(symbol)
                                if first_beta - {'ε'}:
                                    if not (first_beta - {'ε'}).issubset(self.follow[symbol]):
                                        self.follow[symbol].update(first_beta - {'ε'})
                                        changed = True
                                
                                # 如果beta可以推导出ε，将FOLLOW(nt)添加到FOLLOW(symbol)
                                if not temp_beta:
                                    if not self.follow[nt].issubset(self.follow[symbol]):
                                        self.follow[symbol].update(self.follow[nt])
                                        changed = True
                            else:
                                # beta为空，将FOLLOW(nt)添加到FOLLOW(symbol)
                                if not self.follow[nt].issubset(self.follow[symbol]):
                                    self.follow[symbol].update(self.follow[nt])
                                    changed = True
        return self.follow
    
    def construct_parsing_table(self):
        """构造LL(1)分析表"""
        # 确保FIRST和FOLLOW集已计算
        if not self.first:
            self.compute_first()
        if not self.follow:
            self.compute_follow()
        
        # 初始化分析表
        parsing_table = {}
        for nt in self.non_terminals:
            parsing_table[nt] = {}
            for terminal in self.terminals:
                parsing_table[nt][terminal] = None
            parsing_table[nt]['$'] = None
        
        # 填充分析表
        for nt, prods in self.productions.items():
            for prod in prods:
                # 计算FIRST(prod)
                first_prod = set()
                has_epsilon = True
                temp_prod = prod
                
                while temp_prod and has_epsilon:
                    symbol = temp_prod[0]
                    if symbol in self.terminals:
                        first_prod.add(symbol)
                        has_epsilon = False
                    else:
                        first_prod.update(self.first[symbol] - {'ε'})
                        if 'ε' not in self.first[symbol]:
                            has_epsilon = False
                        else:
                            temp_prod = temp_prod[1:]
                
                # 处理FIRST(prod)中的终结符
                for terminal in first_prod:
                    if terminal != 'ε':
                        parsing_table[nt][terminal] = (nt, prod)
                
                # 如果prod可以推导出ε，处理FOLLOW(nt)中的终结符
                if not temp_prod:
                    for terminal in self.follow[nt]:
                        parsing_table[nt][terminal] = (nt, prod)
        
        return parsing_table
    
    def print_first(self):
        """打印FIRST集"""
        print("FIRST集:")
        for symbol, first_set in self.first.items():
            print(f"FIRST({symbol}) = {first_set}")
    
    def print_follow(self):
        """打印FOLLOW集"""
        print("\nFOLLOW集:")
        for nt, follow_set in self.follow.items():
            print(f"FOLLOW({nt}) = {follow_set}")
    
    def print_parsing_table(self, parsing_table):
        """打印LL(1)分析表"""
        print("\nLL(1)分析表:")
        # 打印表头
        headers = list(self.terminals) + ['$']
        print("\t" + "\t".join(headers))
        # 打印表内容
        for nt in self.non_terminals:
            row = [nt]
            for terminal in headers:
                entry = parsing_table[nt].get(terminal)
                if entry:
                    row.append(f"{entry[0]}→{''.join(entry[1])}")
                else:
                    row.append("-")
            print("\t".join(row))

# 测试
if __name__ == "__main__":
    # 定义文法
    productions = {
        'E': [['T', "E'"]],
        "E'": [['+', 'T', "E'"], ['ε']],
        'T': [['F', "T'"]],
        "T'": [['*', 'F', "T'"], ['ε']],
        'F': [['(', 'E', ')'], ['id']]
    }
    
    analyzer = GrammarAnalyzer(productions, 'E')
    analyzer.compute_first()
    analyzer.compute_follow()
    parsing_table = analyzer.construct_parsing_table()
    
    analyzer.print_first()
    analyzer.print_follow()
    analyzer.print_parsing_table(parsing_table)

八、LL(1)分析表的优缺点

优点

1. 确定性分析：LL(1)分析表确保分析过程是确定性的，没有回溯
2. 分析效率高：分析过程是线性的，时间复杂度为O(n)，其中n是输入串的长度
3. 错误定位准确：当分析失败时，可以精确定位错误位置
4. 易于实现：基于LL(1)分析表的预测分析器易于实现

缺点

1. 文法限制：只能处理LL(1)文法，很多自然文法不是LL(1)的
2. 分析表大小：对于复杂的文法，分析表可能非常大
3. 需要消除左递归：左递归会导致分析表冲突
4. 需要提取左公因子：左公因子会导致分析表冲突

九、LL(1)分析的最佳实践

1. 文法设计

• 消除左递归：确保文法没有左递归
• 提取左公因子：消除文法中的左公因子
• 保持简单：设计文法时尽量保持简单，避免复杂的产生式

2. FIRST集和FOLLOW集计算

• 仔细计算：确保FIRST集和FOLLOW集的计算正确无误
• 验证结果：使用小例子验证计算结果
• 自动化计算：对于复杂的文法，使用工具自动计算FIRST集和FOLLOW集

3. 分析表构造

• 检查表项冲突：构造分析表后，检查是否有冲突
• 处理冲突：如果有冲突，重写文法以消除冲突
• 优化表大小：对于大型文法，考虑使用压缩技术减小分析表的大小

十、自测题

1. 什么是FIRST集？如何计算FIRST集？
2. 什么是FOLLOW集？如何计算FOLLOW集？
3. LL(1)分析表的构造方法是什么？
4. 如何判断一个文法是否是LL(1)的？
5. 左递归和左公因子为什么会导致LL(1)分析表冲突？
6. 使用LL(1)分析表分析输入串 (id + id) * id $，写出分析过程。

十一、总结与展望

本集详细介绍了LL(1)分析表的构造方法，包括FIRST集和FOLLOW集的计算，以及如何基于这些集合构建LL(1)分析表。LL(1)分析表是预测分析器的核心组件，它确保分析过程是确定性的，没有回溯，提高了分析效率。

在构造LL(1)分析表时，需要注意以下几点：

1. 正确计算FIRST集：FIRST集是构造分析表的基础，必须计算正确
2. 正确计算FOLLOW集：FOLLOW集用于处理ε产生式，也必须计算正确
3. 检查分析表冲突：如果分析表有冲突，文法不是LL(1)的，需要重写文法
4. 消除左递归和左公因子：左递归和左公因子会导致分析表冲突，需要提前消除

在接下来的几集中，我们将继续学习语法分析的其他方法：

• LL(1)分析器实现：基于分析表的预测分析器实现
• 自底向上分析概述：介绍移进-归约分析和LR分析
• LR(0)分析法：介绍LR(0)分析的基本原理

通过这些学习，我们将能够掌握各种语法分析方法的实现技巧，为构建完整的编译器打下坚实的基础。

十二、参考资料

1. 《编译原理》（龙书）- Alfred V. Aho 等
2. 《现代编译原理》（虎书）- Andrew W. Appel
3. 《编译器设计》- Keith D. Cooper 等
4. LL(1)文法 - 维基百科
5. FIRST集和FOLLOW集 - 编译原理教材
6. 《形式语言与自动机》- John E. Hopcroft 等