「解析器生成器与 DSL 前端」

# 手写递归下降的典型形态
class Parser:
    def __init__(self, tokens):
        self.toks, self.pos = tokens, 0

    def peek(self):
        return self.toks[self.pos] if self.pos < len(self.toks) else None

    def expect(self, kind):
        t = self.peek()
        if t is None or t.kind != kind:
            raise ParseError(f"期望 {kind}，实际 {t}", self.pos)
        self.pos += 1
        return t

    def parse_expr(self):
        """expr := term (('+' | '-') term)*"""
        left = self.parse_term()
        while self.peek() and self.peek().kind in ("PLUS", "MINUS"):
            op = self.toks[self.pos]; self.pos += 1
            left = BinOp(op.kind, left, self.parse_term())
        return left

# 为 LL(1) 文法构造预测表
def build_ll1_table(grammar, first, follow):
    """grammar: {A: [[sym, ...], ...]}，返回 (非终结符, 记号) -> 产生式"""
    table = {}
    for A, prods in grammar.items():
        for prod in prods:
            fs = first_of_seq(prod, first)      # 该产生式首符号的 FIRST 集
            for t in fs - {"EPSILON"}:
                table[(A, t)] = prod
            if "EPSILON" in fs:                 # 能推出空串，用 FOLLOW 填表
                for t in follow[A]:
                    table[(A, t)] = prod
    return table        # 同一格被填两次即冲突，说明不是 LL(1)

# 消除左递归：expr := expr '+' term | term 改写成右递归
#   expr      := term expr_tail
#   expr_tail := '+' term expr_tail | EPSILON
# 代价是语法树变成右倾，需要后续旋转回左结合

# LR(0) 项集闭包与转移（构造 LALR 表的基础）
def closure(items, grammar):
    """对项集求闭包：点在非终结符前时，加入该非终结符的所有产生式"""
    result, changed = set(items), True
    while changed:
        changed = False
        for lhs, rhs, dot in list(result):
            if dot < len(rhs) and rhs[dot] in grammar:   # 点在非终结符前
                for prod in grammar[rhs[dot]]:
                    item = (rhs[dot], tuple(prod), 0)
                    if item not in result:
                        result.add(item); changed = True
    return frozenset(result)

def goto(items, symbol, grammar):
    """GOTO：把点越过 symbol 后求闭包"""
    moved = {(l, r, d + 1) for (l, r, d) in items if d < len(r) and r[d] == symbol}
    return closure(moved, grammar) if moved else frozenset()

# Bison 的冲突诊断
bison -v parser.y            # 生成 parser.output，含完整状态机
# 输出形如：
#   State 12 conflicts: 1 shift/reduce
#   观察 .output 里该状态的项集，判断冲突来源

# PEG 组合子：把解析器写成返回 (值, 新位置) 或 None 的函数
def literal(s):
    def parse(text, pos):
        return (s, pos + len(s)) if text.startswith(s, pos) else None
    return parse

def seq(*ps):
    def parse(text, pos):
        vals = []
        for p in ps:
            r = p(text, pos)
            if r is None:
                return None
            vals.append(r[0]); pos = r[1]
        return (vals, pos)
    return parse

def choice(*ps):
    def parse(text, pos):
        for p in ps:
            r = p(text, pos)
            if r is not None:
                return r          # 有序：第一个成功即返回，不回退
        return None
    return parse

def many(p):
    def parse(text, pos):
        vals = []
        while (r := p(text, pos)) is not None:
            vals.append(r[0]); pos = r[1]
        return (vals, pos)
    return parse

# 组装：数字列表 "1,2,3"
number = choice(literal("1"), literal("2"), literal("3"))
numlist = seq(number, many(seq(literal(","), number)))
print(numlist("1,2,3", 0))       # (['1', [',','2', ',','3']], 5)

# 左递归的迭代改写：把 expr := expr '+' term | term 改写成循环
def parse_expr(text, pos):
    left, pos = parse_term(text, pos)
    while text.startswith("+", pos):
        right, pos = parse_term(text, pos + 1)
        left = ("add", left, right)      # 迭代构造左结合树
    return left, pos

# 差：  syntax error at line 12
# 好：  line 12: 期望 ')' 或 ','，实际遇到 '}'
#           for (int i = 0; i < n; i++ {
#       提示：'(' 在第 10 列打开，可能缺少匹配的 ')'

SYNC = {"SEMICOLON", "RBRACE", "IF", "WHILE", "RETURN"}

def recover(self):
    """出错后跳到同步记号，继续解析后续语句"""
    while (t := self.peek()) is not None and t.kind not in SYNC:
        self.pos += 1
    if self.peek() is not None and self.peek().kind == "SEMICOLON":
        self.pos += 1        # 吃掉分号，避免重复报错

def parse_stmt_list(self):
    stmts, errors = [], []
    while self.peek() is not None and self.peek().kind != "RBRACE":
        mark = self.pos
        try:
            stmts.append(self.parse_stmt())
        except ParseError as e:
            errors.append(e); self.recover()
            if self.pos == mark:      # 没有前进，强制跳过防止死循环
                self.pos += 1
    return stmts, errors

// Tree-sitter 语法规则片段（grammar.js）
module.exports = grammar({
  name: 'mylang',
  extras: $ => [/\s/, $.comment],      // 空白与注释在任意位置被跳过
  rules: {
    source_file: $ => repeat($._statement),
    _statement: $ => choice($.let_stmt, $.expr_stmt),
    let_stmt: $ => seq('let', $.identifier, '=', $._expr, ';'),
    binary: $ => prec.left(1, seq($._expr, choice('+', '-'), $._expr)),
  }
});

; queries/highlights.scm：把语法树节点映射到高亮类别
(identifier) @variable
(let_stmt "let" @keyword)
(binary "+" @operator)

# 语义动作与语法解耦：用 visitor 模式，语法只负责结构
class EvalVisitor(MyLangVisitor):
    def visitBinary(self, ctx):
        left, right = self.visit(ctx.left), self.visit(ctx.right)
        return left + right if ctx.getChild(1).getText() == "+" else left - right
    def visitNumber(self, ctx):
        return int(ctx.getText())   # 求值/检查/生成各写一个 visitor

def memoize(parse_fn):
    """Packrat 记忆化：缓存 (规则, 位置) 的结果，前提是解析器无副作用"""
    cache = {}
    def wrapper(text, pos):
        key = (parse_fn.__name__, pos)
        cache.setdefault(key, parse_fn(text, pos))
        return cache[key]
    return wrapper

# 基准：对比 Packrat 开关的时间与内存权衡
# hyperfine --warmup 3 'python3 -m myparser big_file.mylang'
# /usr/bin/time -l python3 -m myparser --packrat big_file.mylang