自己动手开发编译器（六）上下文无关语言和文法

自己动手开发编译器（六）上下文无关语言和文法

在前几篇文章中，我们聊了词法分析，学会了如何把源代码拆成一个个“单词”（Token）。但光有单词还不够，就像你认识“我”、“爱”、“你”这三个词，但如果不按语法规则排列，就无法表达完整的意思。这一篇，我们进入编译器的“语法分析”阶段，核心就是上下文无关文法（Context-Free Grammar，CFG）。### 为什么叫“上下文无关”？想象一下，在自然语言里，“我打他”和“他打我”意思完全不同，因为“打”这个动作的发出者和接受者取决于“上下文”（谁在前面谁在后面）。但在编程语言里，我们看一个语句的结构，不需要知道变量具体存了什么值，只需要知道它的类型和语法位置。比如：if (x > 0) { y = 1; }我们解析这个语句时，只关心if后面是个括号表达式，里面是个比较运算，后面是花括号包裹的代码块——这些规则是固定的，不依赖x和y的具体值。这种“只要看当前符号序列，就能判断是否符合规则”的语言，就叫上下文无关语言。### 文法的形式化定义一个上下文无关文法（CFG）就是一组规则，形式如下：A -> α其中A是一个非终结符（比如Expression、Statement），α是一串终结符（比如+、x、5）和非终结符的混合。终结符就是词法分析产出的 Token，非终结符就是我们自己定义的抽象语法单元。举个例子，一个简单的算术表达式文法：Expression -> Expression + Term | TermTerm -> Term * Factor | FactorFactor -> ( Expression ) | Number这里Number就是终结符（比如5、3），Expression、Term、Factor是非终结符。这个文法能描述类似(5 + 3) * 2这样的表达式。### 上下文无关文法能做什么？它能帮我们回答两个问题：1.给定一串 Token，它是否符合这个文法的规则？（判断正确性）2.如果符合，它对应的语法树（AST）长什么样？（为后续代码生成打基础）我们举一个实际例子，写一个简单的解析器，用 Python 实现一个只支持加法和乘法的表达式解析器。python# 一个简单的递归下降解析器，支持 + 和 * ，遵循优先级（乘法优先）# 终结符：NUMBER, '+', '*', '(', ')'class Token: def __init__(self, type, value): self.type = type self.value = valuedef tokenize(s): """把字符串拆成 Token 列表，这里简化处理，只支持数字和运算符""" tokens = [] i = 0 while i < len(s): if s[i].isdigit(): j = i while j < len(s) and s[j].isdigit(): j += 1 tokens.append(Token('NUMBER', int(s[i:j]))) i = j elif s[i] == '+': tokens.append(Token('PLUS', '+')) i += 1 elif s[i] == '*': tokens.append(Token('STAR', '*')) i += 1 elif s[i] == '(': tokens.append(Token('LPAREN', '(')) i += 1 elif s[i] == ')': tokens.append(Token('RPAREN', ')')) i += 1 else: raise ValueError(f"无法识别的字符: {s[i]}") tokens.append(Token('EOF', None)) return tokensclass Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): return self.tokens[self.pos].type def consume(self): token = self.tokens[self.pos] self.pos += 1 return token # 文法规则： # expr -> term ( '+' term )* # term -> factor ( '*' factor )* # factor -> NUMBER | '(' expr ')' def parse_expr(self): """解析表达式，最低优先级：加法""" left = self.parse_term() while self.peek() == 'PLUS': self.consume() right = self.parse_term() left = ('+', left, right) # 生成简单的AST节点 return left def parse_term(self): """解析项，优先级高于加法""" left = self.parse_factor() while self.peek() == 'STAR': self.consume() right = self.parse_factor() left = ('*', left, right) return left def parse_factor(self): """解析因子，最高优先级：数字或括号""" if self.peek() == 'NUMBER': token = self.consume() return token.value elif self.peek() == 'LPAREN': self.consume() expr = self.parse_expr() if self.peek() != 'RPAREN': raise SyntaxError("缺少右括号") self.consume() return expr else: raise SyntaxError("语法错误")# 测试tokens = tokenize("3 + 5 * ( 2 + 4 )")parser = Parser(tokens)ast = parser.parse_expr()print("AST:", ast)这段代码实现了递归下降解析，它直接按照文法规则一层层递归，生成一个嵌套的树结构。你可以看到，parse_expr调用了parse_term，parse_term又调用了parse_factor，这就是“上下文无关”的体现：每个函数只关心当前输入是否符合自己的规则，不关心外面发生了什么。### 二义性与优先级你可能会问：为什么我们要把加法放在term外面，而不是直接写expr -> expr + expr | expr * expr？因为那样会产生二义性。比如输入"1 + 2 * 3"，如果文法写成expr -> expr + expr | expr * expr | NUMBER，那么既可以把1 + 2看作一个整体，再乘以3，也可以把2 * 3看作一个整体，再加1。这会导致解析器无法确定该用哪条规则，产生多种可能的语法树。而我们的设计（乘法优先）就消除了二义性：乘法在term层，加法在expr层，这样1 + 2 * 3只能被解析为1 + (2*3)，因为expr先看到1，然后遇到+，再调用term去解析2 * 3，而不是反过来。### 消除左递归另一个重要问题是左递归。比如文法expr -> expr + term | term，我们的解析器在parse_expr里一开始就调用parse_expr，会无限递归下去，导致栈溢出。解决办法是把它改写成右递归或迭代形式。上面代码中我们用了while循环，这就是把expr -> expr + term改写成expr -> term ( '+' term )*的效果——星号表示零次或多次重复，用循环处理。### 构建语法树（AST）解析器在匹配规则时，可以同时构建抽象语法树（AST）。上面代码中我们用元组表示节点，比如('+', left, right)。真正的编译器会定义更复杂的节点类，但核心思想一样：根据文法规则，把 Token 序列转换成一个树形结构。后续的语义分析和代码生成都基于这棵树。### 代码示例二：用 Python 生成一个简单的计算器我们扩展上面的解析器，加入求值功能，这样就能实际计算表达式了。python# 在之前 Parser 基础上，增加求值功能def evaluate(node): """对 AST 进行求值，node 可以是数字或者 ('+', left, right) 这样的元组""" if isinstance(node, int): return node elif isinstance(node, tuple): op = node[0] if op == '+': return evaluate(node[1]) + evaluate(node[2]) elif op == '*': return evaluate(node[1]) * evaluate(node[2]) else: raise ValueError(f"未知节点: {node}")# 测试tokens = tokenize("2 + 3 * ( 4 + 5 )")parser = Parser(tokens)ast = parser.parse_expr()result = evaluate(ast)print("计算结果:", result) # 输出 2 + 3 * 9 = 29这个例子展示了如何把“语法分析”和“语义处理”分开：解析器负责生成树，求值器负责遍历树。真实编译器的代码生成阶段也是类似，只不过输出的是汇编代码而不是数字。### 上下文无关文法的实际应用场景-语法高亮：编辑器根据文法规则给代码上色。-静态分析工具：比如 ESLint 或 Pyflakes，它们解析代码后检查潜在错误。-模板引擎：如 Jinja2、Mustache，它们解析模板字符串，生成渲染逻辑。-数据库查询语言：SQL 解析器也是用 CFG 实现的。### 总结上下文无关文法是编译器前端（词法分析 + 语法分析）的理论基石。它让我们可以用一套形式化的规则描述编程语言的语法，并据此写出解析器。本篇我们介绍了：- 什么是上下文无关语言和文法（CFG）- 如何用递归下降解析器实现简单的文法- 如何处理优先级、左递归和二义性- 如何构建与求值语法树掌握了这些，你就具备了实现一个完整语法分析器的能力。下一步，我们会讨论语义分析（比如类型检查），敬请期待！