编译原理语法分析LR1

### 编译原理 LR(1) 语法分析详解

#### 定义与特点
LR(1) 是一种自底向上的语法分析方法，其中 "L" 表示从左到右扫描输入串，“R” 表示最右推导的逆过程即规约，而 "(1)" 则意味着带有向前搜索符号的能力[^1]。这种特性允许 LR(1) 分析器在决定何时应用某一产生式的规约操作之前查看下一个输入符号。

#### 工作机制
为了实现上述功能，LR(1) 构建了一个项目集规范族，在每个项目后面附加一个向前看符号（lookahead symbol）。当构建状态转换图时，不仅考虑当前项目的完成情况，还要结合预期到来的第一个实际终结符来进行决策。这有效地减少了冲突的发生概率，并提高了识别能力[^2]。

#### 项目集及其闭包运算
对于每一个文法 G 和它的起始符号 S' -> .S ，初始项为 [S'->.S,$] 。这里 $ 表示文件结束标志。之后通过计算闭包 Closure(I)，可以得到所有可能扩展出来的新项目：

- 如果存在形如 A → α·Bβ 的项目，则将 B 所有规则中的第一个位置加上相应的向前查找标记加入 I 中；
- 对于任何非终结符 X ∈ Vn 及其对应的 FIRST(X) 集合内的成员 a (a 不等于 ε ) 或者 FOLLOW(A)，如果遇到的是空字则取跟随集中元素作为新的 look-ahead 符号。

def closure(items, grammar):
    new_items = set()
    
    while True:
        added = False
        
        for item in list(new_items | items):  # 使用联合后的集合迭代
            if not isinstance(item.lookahead, str):
                continue
                
            next_symbol_index = len(item.production.rhs.split()) - len(item.dot_position)
            
            if next_symbol_index >= 0 and item.production.lhs != 'S\'':
                next_nonterminal = item.production.rhs.split()[next_symbol_index]

                for production in grammar.productions_for(next_nonterminal):
                    lookahead_set = {item.lookahead} \
                        if item.dot_position == len(item.production.rhs.split()) or \
                           grammar.first_of(item.production.rhs[next_symbol_index:]) == {'ε'} \
                        else grammar.first_of(item.production.rhs[next_symbol_index:])
                    
                    for la in lookahead_set:
                        potential_item = Item(production=production, dot_position=[],
                                              lookahead=la)

                        if potential_item not in new_items.union(items):
                            new_items.add(potential_item)
                            added = True
                    
        if not added:
            break
            
    return new_items | items