名称: 解析器生成器描述: ‘从语法规范生成LALR(1)和递归下降解析器。使用场景: (1) 构建编译器, (2) 创建DSLs, (3) 解析配置文件。’ 版本: 1.0.0 标签:

编译器
解析
语法
前端难度: 中级语言:
python
ocaml
rust 依赖项:
词法分析器生成器

解析器生成器

从上下文无关语法规范生成解析器。

使用场景

为新语言构建编译器
创建领域特定语言解析器
解析结构化文本/数据格式
从源代码生成抽象语法树

此技能功能

解析语法规范 - 将BNF转换为内部表示
生成解析器 - LALR(1)或递归下降
处理歧义 - 通过优先级/结合性解决
报告错误 - 生成有意义的错误消息

关键概念

def peek(self, type: str) -> bool:
    """检查当前令牌类型是否匹配"""
    return self.current().type == type

# 语法规则

def parse_expr(self):
    """Expr -> Term (('+' | '-') Term)*"""
    result = self.parse_term()
    
    while self.peek("PLUS") or self.peek("MINUS"):
        op = self.consume().value
        right = self.parse_term()
        result = BinOp(op, result, right)
    
    return result

def parse_term(self):
    """Term -> Factor (('*' | '/') Factor)*"""
    result = self.parse_factor()
    
    while self.peek("TIMES") or self.peek("DIV"):
        op = self.consume().value
        right = self.parse_factor()
        result = BinOp(op, result, right)
    
    return result

def parse_factor(self):
    """Factor -> NUMBER | '(' Expr ')'"""
    if self.peek("NUMBER"):
        return Number(int(self.consume().value))
    
    if self.peek("LPAREN"):
        self.consume()
        result = self.parse_expr()
        self.consume("RPAREN")
        return result
    
    raise ParseError(f"Unexpected token: {self.current()}")

抽象语法树节点

@dataclass
class ASTNode:
    """抽象语法树节点基类"""
    pass

@dataclass
class Number(ASTNode):
    value: int

@dataclass
class BinOp(ASTNode):
    op: str
    left: ASTNode
    right: ASTNode

@dataclass
class UnaryOp(ASTNode):
    op: str
    operand: ASTNode

@dataclass
class Var(ASTNode):
    name: str

@dataclass
class Assign(ASTNode):
    name: str
    value: ASTNode

@dataclass
class If(ASTNode):
    condition: ASTNode
    then_branch: ASTNode
    else_branch: Optional[ASTNode]

@dataclass
class While(ASTNode):
    condition: ASTNode
    body: ASTNode

@dataclass
class Block(ASTNode):
    statements: list[ASTNode]

LALR(1) 解析器生成器

# 简化LALR(1)解析器生成器
from collections import defaultdict

class Grammar:
    def __init__(self):
        self.productions = []  # [(lhs, [rhs symbols])]
        self.terminals = set()
        self.nonterminals = set()
        self.start = None
    
    def add_production(self, lhs, rhs):
        """添加产生式: lhs -> rhs"""
        self.productions.append((lhs, rhs))
        self.nonterminals.add(lhs)
        for sym in rhs:
            if sym.islower() or sym in ('+', '*', '(', ')'):
                self.terminals.add(sym)
            else:
                self.nonterminals.add(sym)
    
    def augmented_start(self):
        """创建增广文法 S' -> S"""
        self.start = self.productions[0][0]
        self.productions.insert(0, ("S'", [self.start]))
        self.nonterminals.add("S'")

# 项: 产生式加点位置
@dataclass
class LRItem:
    lhs: str
    rhs: tuple
    dot: int  # 在rhs中的位置
    lookaheads: set

def closure(items, grammar):
    """计算LR(1)项的闭包"""
    closure_set = set(items)
    changed = True
    
    while changed:
        changed = False
        for item in list(closure_set):
            if item.dot < len(item.rhs):
                symbol = item.rhs[item.dot]
                if symbol in grammar.nonterminals:
                    # 查找此非终结符的所有产生式
                    for lhs, rhs in grammar.productions:
                        if lhs == symbol:
                            # 计算向前看符号
                            beta = item.rhs[item.dot + 1:]
                            new_lookaheads = compute_lookahead(
                                item.lookaheads, beta, grammar
                            )
                            new_item = LRItem(lhs, rhs, 0, new_lookaheads)
                            if new_item not in closure_set:
                                closure_set.add(new_item)
                                changed = True
    
    return closure_set

def compute_lookahead(lookaheads, beta, grammar):
    """计算GOTO的向前看符号"""
    result = set(lookaheads)
    for symbol in beta:
        if symbol in grammar.terminals:
            return {symbol}
        # 处理可空非终结符
        if is_nullable(symbol, grammar):
            continue
        break
    return result

def goto(items, symbol, grammar):
    """计算GOTO(I, X)"""
    goto_set = set()
    for item in items:
        if item.dot < len(item.rhs) and item.rhs[item.dot] == symbol:
            new_item = LRItem(
                item.lhs, 
                item.rhs, 
                item.dot + 1, 
                item.lookaheads
            )
            goto_set.add(new_item)
    return closure(goto_set, grammar)

def build_lalr_table(grammar):
    """构建LALR(1)解析表"""
    grammar.augmented_start()
    
    # 构建规范集
    C = [closure({LRItem("S'", (grammar.start,), 0, {"$"})}, grammar)]
    
    # ... (完整算法在生产代码中)
    
    # 构建动作/转移表
    action = {}
    goto_table = {}
    
    # ... 填充表
    
    return action, goto_table

使用LALR解析器

def lalr_parse(tokens, grammar):
    """LALR(1)解析器"""
    action, goto = build_lalr_table(grammar)
    
    stack = [0]  # 状态栈
    symbols = []  # 符号栈
    
    while True:
        state = stack[-1]
        token = tokens[lookahead]
        
        if (state, token.type) in action:
            action_entry = action[(state, token.type)]
            
            if action_entry[0] == 'shift':
                stack.append(action_entry[1])
                symbols.append(token)
                lookahead += 1
            
            elif action_entry[0] == 'reduce':
                prod = action_entry[1]
                lhs, rhs = grammar.productions[prod]
                # 弹出len(rhs)个状态和符号
                for _ in range(len(rhs)):
                    stack.pop()
                    symbols.pop()
                # 压入非终结符
                symbols.append(lhs)
                # 新状态
                new_state = goto[stack[-1], lhs]
                stack.append(new_state)
            
            elif action_entry[0] == 'accept':
                return symbols[1]  # 返回抽象语法树
            
            else:
                raise ParseError(f"未知动作: {action_entry}")
        else:
            raise ParseError(f"意外令牌: {token}")

关键概念

概念	描述
终结符	来自词法分析器的令牌 (NUMBER, IDENT)
非终结符	语法符号 (Expr, Stmt)
产生式	定义非终结符的规则
LR(0) 项	带有点位置的产生式
向前看符号	决定动作的令牌
冲突	移进/归约或归约/归约歧义

优先级与结合性

# 在语法中指定
precedence = [
    ('left', ['PLUS', 'MINUS']),
    ('left', ['TIMES', 'DIV']),
    ('right', ['UMINUS']),  # 一元减号
]

# 在解析器生成时解决
# 1. 移进 > 归约用于明确优先级
# 2. 左结合: 在最左匹配时归约
# 3. 右结合: 在最右匹配时归约

技巧

从简单语法开始，逐步添加功能
使用左递归进行递归下降（或转换为右递归）
优雅处理错误（错误产生式，恢复）
在抽象语法树中跟踪源位置
在解析期间考虑语义动作

常见问题

问题	解决方案
左递归	转换为右递归
歧义	使用优先级/结合性
无限循环	检查ε产生式
错误消息差	添加错误产生式

权衡与限制

算法权衡

方法	优点	缺点
递归下降	简单直观，错误消息好	左递归问题，回溯
LL(1)	可预测，无回溯	表达能力有限
LR(1)/LALR	最强大，确定性	表生成复杂
GLR	处理歧义	复杂，错误消息难

不使用此方法的情况

对于高度歧义的语法: 考虑解析表达式文法 (PEGs) 或 GLR
对于流式/大输入: 考虑增量解析
对于错误恢复: 使用错误产生式和恢复策略

限制

LL/LR 限制: 并非所有上下文无关文法都可解析
歧义: 某些语法天生歧义；必须解决
错误消息: 解析器错误可能晦涩；需要努力以获得良好用户体验
左递归: 传统递归下降失败；需要转换

评估标准

高质量解析器生成器应具备:

标准	应查看的内容
覆盖率	处理完整语法（不仅是子集）
错误恢复	错误后能继续
错误消息	清晰，显示位置
抽象语法树质量	保留源信息
性能	线性时间解析
歧义处理	正确解决冲突

质量指标

✅ 好: 完整语法覆盖，良好错误消息，保留位置 ⚠️ 警告: 有限语法覆盖，错误消息差 ❌ 差: 接受错误解析，在有效输入时崩溃

经典参考

参考	重要性
Aho, Lam, Sethi, Ullman, “编译器：原理、技术与工具” (龙书)	第4-5章关于解析；LR解析理论
Grune & Jacobs, “解析技术：实用指南”	解析算法综合调查
Knuth, “关于上下文无关文法的翻译”	原始LR(k)论文
DeRemer, “简单LR(k)文法” (1971)	LALR论文
Norvell, “解析导论”	LR解析优秀教程

研究工具与工件

现实世界解析器生成器和工具:

工具	语言	可学习内容
ANTLR 4	Java	ALL(*)解析，语义谓词
Menhir	OCaml	LR(1)，增量，错误消息
Yacc/Bison	C	经典LALR，经过实战检验
Happy	Haskell	LALR(1)，带可选GLR扩展
Lalrpop	Rust	Rust集成，错误恢复
pest	Rust	PEG解析，文法推导

解析器生成器研究

GLR (广义LR) - 优雅处理歧义
增量解析 - 小编辑后重新解析
错误恢复 - 解析错误，继续，报告
Packrat解析 - 带记忆化的PEG

研究前沿

1. 自适应解析

方法: 基于输入选择解析策略
论文: “自适应LL(*)解析” (Parr & Fisher)
工具: ANTLR 4的ALL(*)算法
优势: 处理更多文法

2. 增量解析

方法: 编辑后重用解析树
论文: “增量解析” (Wagner & Graham)
工具: Roslyn (C#), tree-sitter
优势: 对IDE快速

3. 错误恢复策略

方法: 从错误恢复，继续解析
论文: “LR解析器中的错误恢复” (Burke & Fisher)
技术: 恐慌模式，短语级，部分解析
优势: 更好错误消息

4. PEGs vs CFGs

PEG: 解析表达式文法（有序选择）
CFG: 上下文无关文法（歧义）
论文: “解析表达式文法” (Ford)
工具: PEG.js, pest, Scala解析器组合器

实现陷阱

陷阱	实际后果	解决方案
左递归	递归下降无限循环	转换为右递归或使用packrat
歧义	意外解析	使用优先级，GLR
ε循环	解析器挂起	固定点检测
错误优先级	“移进/归约冲突”	正确定义优先级
缺少错误恢复	单个错误停止解析	添加错误产生式

"悬空else"问题

经典文法歧义:

stmt → if expr then stmt
      | if expr then stmt else stmt
      | ...

if E1 then if E2 then S1 else S2
-- else绑定到哪个if？
-- 标准: 绑定到最内层（移进-归约冲突）

LR冲突解决

%left '+' '-'
%left '*' '/'
%right '='  /* 最低优先级 */

/* 在expr中:  expr: expr '+' expr  %prec '+'  */
/* 使用%prec为规则分配优先级 */

这就是bison使用优先级声明的原因！

解析器生成器Skill parser-generator

解析器生成器

使用场景

此技能功能

关键概念

抽象语法树节点

LALR(1) 解析器生成器

使用LALR解析器

关键概念

优先级与结合性

技巧

常见问题

权衡与限制

算法权衡

不使用此方法的情况

限制

评估标准

质量指标

相关技能

经典参考

研究工具与工件

解析器生成器研究

研究前沿

1. 自适应解析

2. 增量解析

3. 错误恢复策略

4. PEGs vs CFGs

实现陷阱

"悬空else"问题

LR冲突解决