自己动手开发编译器六上下文无关语言和文法在前几篇文章中我们聊了词法分析学会了如何把源代码拆成一个个“单词”Token。但光有单词还不够就像你认识“我”、“爱”、“你”这三个词但如果不按语法规则排列就无法表达完整的意思。这一篇我们进入编译器的“语法分析”阶段核心就是上下文无关文法Context-Free GrammarCFG。### 为什么叫“上下文无关”想象一下在自然语言里“我打他”和“他打我”意思完全不同因为“打”这个动作的发出者和接受者取决于“上下文”谁在前面谁在后面。但在编程语言里我们看一个语句的结构不需要知道变量具体存了什么值只需要知道它的类型和语法位置。比如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、3Expression、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_termparse_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- 如何用递归下降解析器实现简单的文法- 如何处理优先级、左递归和二义性- 如何构建与求值语法树掌握了这些你就具备了实现一个完整语法分析器的能力。下一步我们会讨论语义分析比如类型检查敬请期待
自己动手开发编译器六上下文无关语言和文法在前几篇文章中我们聊了词法分析学会了如何把源代码拆成一个个“单词”Token。但光有单词还不够就像你认识“我”、“爱”、“你”这三个词但如果不按语法规则排列就无法表达完整的意思。这一篇我们进入编译器的“语法分析”阶段核心就是上下文无关文法Context-Free GrammarCFG。### 为什么叫“上下文无关”想象一下在自然语言里“我打他”和“他打我”意思完全不同因为“打”这个动作的发出者和接受者取决于“上下文”谁在前面谁在后面。但在编程语言里我们看一个语句的结构不需要知道变量具体存了什么值只需要知道它的类型和语法位置。比如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、3Expression、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_termparse_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- 如何用递归下降解析器实现简单的文法- 如何处理优先级、左递归和二义性- 如何构建与求值语法树掌握了这些你就具备了实现一个完整语法分析器的能力。下一步我们会讨论语义分析比如类型检查敬请期待
