简介这份资源是山东大学编译原理与技术课程新版实验一至三的配套代码包面向正在学习编译器前端构建的高校学生与自学者帮助解决词法分析与语法分析从理论到代码落地的实践难题。压缩包共15个文件约30KB以8个h头文件与5个cpp源文件为核心辅以1个sh构建脚本和1个md说明文档涵盖词法分析器、语法分析器、符号表与目标代码生成等模块的接口定义与实现骨架。内容围绕有限自动机识别词素、上下文无关文法构造抽象语法树、递归下降与LR分析等关键技术展开实验一至三层层递进从识别关键字、标识符、常量与运算符到生成AST并集成前端、处理编译错误。已有57人学习下载适合希望对照课程要求动手实现Lexer与Parser、理解编译器前端整体流程的读者参考也可作为课程实验的起步模板与排错参照。1. 山东大学编译原理新版实验从词法到语义的三级跳到底在练什么如果你在山东大学选过编译原理与技术这门课大概率听过一句话实验一~三做不完期末直接裂开。新版实验把词法分析、语法分析、语义分析串成一条完整的编译前端流水线不再是各自为战的孤立练习。你最终交付的是一个能跑通自定义语言子集的微型编译器前端输入源代码输出带类型标注的中间表示。适合谁正在修这门课、想提前动手的本科生以及想用一个小项目把编译原理从纸面公式拉回工程现实的开发者。热搜里“编译原理实验”反复出现说明大家卡的不是理论是不知道从哪一行代码开始写。我带过几届学生做这套实验血泪经验就一条别一上来啃龙书先把实验框架的输入输出格式吃透再按词法→语法→语义的顺序逐个击破。下面按我实际带做的路径把三个实验拆成可复现的步骤。2. 实验一词法分析器的手写实现与正则引擎选型2.1 为什么手写 DFA 比直接调库更稳词法分析的核心任务就一个把字符流切成 Token 流。常见做法有两种一是用 flex 自动生成二是手写确定有限自动机。我一般会建议手写原因很实际——新版实验的 Token 定义里有一些边界情况比如浮点数后紧跟运算符、注释嵌套、标识符里允许下划线但数字不能开头自动生成工具处理这些要么写复杂的正则要么生成一堆你根本看不懂的状态表。手写 DFA 虽然代码量大一点但每个状态转移你都能在调试器里跟进去看翻车了也知道在哪翻的。先定义 Token 类型。假设实验要求支持的关键字有int、float、if、else、while、return运算符有 - * / !分隔符有( ) { } ; ,再加上标识符、整数常量、浮点常量、注释和空白。Token 结构体至少包含类型、原始字符串、行号三样行号是后面报错定位的后悔药。# token_def.py from enum import Enum, auto class TokenType(Enum): KEYWORD auto() IDENTIFIER auto() INT_CONST auto() FLOAT_CONST auto() OPERATOR auto() DELIMITER auto() COMMENT auto() EOF auto() class Token: def __init__(self, ttype, value, line): self.type ttype self.value value self.line line def __repr__(self): return fToken({self.type.name}, {self.value}, line{self.line})这段代码定义了 Token 的类型枚举和基本结构。line字段必须保留实验二语法分析报错时全靠它定位。value存原始字符串而不是归一化后的值因为语义分析阶段可能需要区分0x1F和31这种不同写法。2.2 状态转移表怎么画、怎么调手写词法分析器的骨架是一个while循环加一个state变量。初始状态为START每读一个字符根据当前状态和字符类别决定下一个状态。字符类别至少分四类字母/下划线、数字、运算符字符、分隔符/空白。下面是一个简化版的核心循环。# lexer.py from token_def import Token, TokenType KEYWORDS {int, float, if, else, while, return} OPERATORS {, -, *, /, , , , !, , , , !} DELIMITERS {(, ), {, }, ;, ,} class Lexer: def __init__(self, source): self.src source self.pos 0 self.line 1 self.tokens [] def tokenize(self): while self.pos len(self.src): ch self.src[self.pos] if ch in \t\r: self.pos 1 elif ch \n: self.line 1 self.pos 1 elif ch.isalpha() or ch _: self._read_identifier() elif ch.isdigit(): self._read_number() elif ch in OPERATORS or ch in (, , , !): self._read_operator() elif ch in DELIMITERS: self.tokens.append(Token(TokenType.DELIMITER, ch, self.line)) self.pos 1 else: raise SyntaxError(fUnexpected char {ch} at line {self.line}) self.tokens.append(Token(TokenType.EOF, , self.line)) return self.tokens def _read_identifier(self): start self.pos while self.pos len(self.src) and (self.src[self.pos].isalnum() or self.src[self.pos] _): self.pos 1 word self.src[start:self.pos] ttype TokenType.KEYWORD if word in KEYWORDS else TokenType.IDENTIFIER self.tokens.append(Token(ttype, word, self.line)) def _read_number(self): start self.pos is_float False while self.pos len(self.src) and (self.src[self.pos].isdigit() or self.src[self.pos] .): if self.src[self.pos] .: if is_float: break is_float True self.pos 1 value self.src[start:self.pos] ttype TokenType.FLOAT_CONST if is_float else TokenType.INT_CONST self.tokens.append(Token(ttype, value, self.line)) def _read_operator(self): two self.src[self.pos:self.pos2] if two in (, , , !): self.tokens.append(Token(TokenType.OPERATOR, two, self.line)) self.pos 2 else: self.tokens.append(Token(TokenType.OPERATOR, self.src[self.pos], self.line)) self.pos 1tokenize是主循环按字符类别分派到不同的读取函数。_read_identifier用贪心策略一直读到非字母数字下划线为止然后查关键字表决定是关键字还是标识符。_read_number处理小数点遇到第二个小数点就停避免把1.2.3吞成一个 Token。_read_operator先看两个字符的组合匹配这类双字符运算符否则退化为单字符。参数调整上最容易出问题的是注释处理。如果实验要求支持//单行注释和/* */块注释需要在主循环里加分支。块注释要记录起始行号遇到未闭合的/*要在 EOF 时报错并指出起始行。我见过太多人在这里只写了个while跳过字符结果嵌套注释或者注释里出现*/就崩了。提示写完词法分析器后先拿一段包含所有 Token 类型的测试代码跑一遍把输出打印出来逐行核对。不要急着写语法分析词法阶段的 bug 会像幽灵一样在后续阶段反复出现。3. 实验二递归下降语法分析与 AST 构建3.1 文法改写消除左递归和提取公因子实验二通常给一个表达式文法要求实现语法分析并构建抽象语法树。直接拿课本上的文法写递归下降会死循环因为表达式文法几乎都带左递归。比如E - E T | T递归下降解析器在parseE里第一件事就是调parseE栈直接溢出。必须改写成右递归形式E - T EE - T E | ε。提取公因子则是为了减少回溯比如Stmt - ID Expr ; | ID ( Args ) ;可以提取成Stmt - ID StmtTail再看StmtTail的首字符决定走赋值还是函数调用。改写后的文法要保证 LL(1)也就是每个非终结符的 FIRST 集不相交。实际操作中你可以先手算 FIRST 和 FOLLOW 集画一张预测分析表确认没有冲突再动手写代码。如果实验要求支持if-else悬挂问题记得用最近匹配原则把else绑定到最近的if。3.2 AST 节点设计与递归下降代码骨架AST 节点用类继承体系最清晰。基类ASTNode带一个accept方法用于后续遍历子类包括Program、VarDecl、FuncDecl、AssignStmt、IfStmt、WhileStmt、ReturnStmt、BinaryOp、UnaryOp、Literal、Identifier、CallExpr等。每个节点存必要的子节点和行号。# ast_nodes.py class ASTNode: def __init__(self, line): self.line line class Program(ASTNode): def __init__(self, decls, line0): super().__init__(line) self.decls decls class VarDecl(ASTNode): def __init__(self, vtype, name, init, line): super().__init__(line) self.vtype vtype self.name name self.init init class BinaryOp(ASTNode): def __init__(self, op, left, right, line): super().__init__(line) self.op op self.left left self.right right class Literal(ASTNode): def __init__(self, value, lit_type, line): super().__init__(line) self.value value self.lit_type lit_type class Identifier(ASTNode): def __init__(self, name, line): super().__init__(line) self.name name递归下降解析器的结构是一组parseXxx方法每个方法对应一个非终结符。入口是parseProgram循环调用parseDecl直到 EOF。parseDecl看当前 Token 是类型关键字还是标识符决定走变量声明还是函数声明。表达式解析按优先级分层parseExpr调parseTermparseTerm调parseFactor每层处理对应优先级的运算符。# parser.py from token_def import TokenType from ast_nodes import * class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def consume(self, ttypeNone): tok self.tokens[self.pos] if ttype and tok.type ! ttype: raise SyntaxError(fExpected {ttype}, got {tok.type} at line {tok.line}) self.pos 1 return tok def parseProgram(self): decls [] while self.peek().type ! TokenType.EOF: decls.append(self.parseDecl()) return Program(decls) def parseDecl(self): if self.peek().type TokenType.KEYWORD and self.peek().value in (int, float): return self.parseVarDecl() elif self.peek().type TokenType.IDENTIFIER: return self.parseFuncDecl() else: raise SyntaxError(fUnexpected token {self.peek()} at line {self.peek().line}) def parseVarDecl(self): vtype self.consume(TokenType.KEYWORD).value name self.consume(TokenType.IDENTIFIER).value init None if self.peek().type TokenType.OPERATOR and self.peek().value : self.consume() init self.parseExpr() self.consume(TokenType.DELIMITER) # 分号 return VarDecl(vtype, name, init, self.tokens[self.pos-1].line) def parseExpr(self): left self.parseTerm() while self.peek().type TokenType.OPERATOR and self.peek().value in (, -): op self.consume().value right self.parseTerm() left BinaryOp(op, left, right, left.line) return left def parseTerm(self): left self.parseFactor() while self.peek().type TokenType.OPERATOR and self.peek().value in (*, /): op self.consume().value right self.parseFactor() left BinaryOp(op, left, right, left.line) return left def parseFactor(self): tok self.peek() if tok.type TokenType.INT_CONST or tok.type TokenType.FLOAT_CONST: self.consume() return Literal(tok.value, tok.type.name, tok.line) elif tok.type TokenType.IDENTIFIER: self.consume() return Identifier(tok.value, tok.line) elif tok.type TokenType.DELIMITER and tok.value (: self.consume() expr self.parseExpr() self.consume(TokenType.DELIMITER) # 右括号 return expr else: raise SyntaxError(fUnexpected token {tok} in factor at line {tok.line})parseExpr和parseTerm的分层结构直接对应运算符优先级parseFactor处理括号和原子表达式。每个consume调用都带期望类型不匹配就抛异常并带行号。parseVarDecl里初始化表达式是可选的所以先peek判断有没有等号。参数调整方面如果实验要求支持一元负号需要在parseFactor里加分支遇到-就消费掉递归调parseFactor包成UnaryOp。注意一元负号的优先级高于乘除所以放在parseFactor里而不是parseTerm里。另一个坑是赋值语句和函数调用的区分两者都以标识符开头需要向前看一个 Token如果是就是赋值如果是(就是函数调用。注意递归下降解析器对错误恢复很不友好一旦抛异常整个解析就停了。如果实验要求报多个错误需要在parseDecl层面做同步捕获异常后跳到下一个分号或右大括号继续解析后面的声明。4. 实验三语义分析与符号表管理4.1 符号表的数据结构选择语义分析阶段要干三件事建符号表、做类型检查、标注 AST。符号表用哈希表加作用域链最合适。每个作用域是一个字典键是变量名值是符号信息类型、行号、是否初始化。作用域链用列表模拟栈进入块就压一个新字典退出就弹出。# symbol_table.py class Symbol: def __init__(self, name, stype, line, initializedFalse): self.name name self.stype stype self.line line self.initialized initialized class SymbolTable: def __init__(self): self.scopes [{}] def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, stype, line): if name in self.scopes[-1]: raise SemanticError(fRedeclaration of {name} at line {line}) self.scopes[-1][name] Symbol(name, stype, line) def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] return None def mark_initialized(self, name): sym self.lookup(name) if sym: sym.initialized Truedeclare只在当前作用域查重允许内层作用域遮蔽外层同名变量。lookup从最内层往外找找到就返回。mark_initialized在赋值语句处理时调用用于检测使用未初始化变量。4.2 类型检查的遍历顺序与错误恢复类型检查用后序遍历 AST先检查子节点类型再检查父节点。比如BinaryOp节点先递归检查left和right拿到两个类型后再判断是否支持这两个类型的组合。整数加整数得整数浮点加浮点得浮点整数加浮点需要隐式提升为浮点。如果遇到不支持的组合报类型错误并返回一个ERROR类型避免后续节点连环报错。# type_checker.py from ast_nodes import * from symbol_table import SymbolTable class TypeChecker: def __init__(self): self.st SymbolTable() self.errors [] def check(self, node): method check_ type(node).__name__ visitor getattr(self, method, self.generic_check) return visitor(node) def generic_check(self, node): raise SemanticError(fNo check method for {type(node).__name__}) def check_Program(self, node): for decl in node.decls: self.check(decl) def check_VarDecl(self, node): if node.init: init_type self.check(node.init) if init_type ! node.vtype and not (node.vtype float and init_type int): self.errors.append(fType mismatch in declaration of {node.name} at line {node.line}) self.st.declare(node.name, node.vtype, node.line) def check_BinaryOp(self, node): lt self.check(node.left) rt self.check(node.right) if lt ERROR or rt ERROR: return ERROR if node.op in (, -, *, /): if lt int and rt int: return int elif lt in (int, float) and rt in (int, float): return float else: self.errors.append(fInvalid operands for {node.op} at line {node.line}) return ERROR return ERROR def check_Identifier(self, node): sym self.st.lookup(node.name) if not sym: self.errors.append(fUndeclared variable {node.name} at line {node.line}) return ERROR if not sym.initialized: self.errors.append(fVariable {node.name} used before initialization at line {node.line}) return sym.stype def check_Literal(self, node): return int if node.lit_type INT_CONST else floatcheck方法用getattr动态分派到对应的check_Xxx方法这是访问者模式的简化写法。check_VarDecl先检查初始化表达式类型允许int赋给float变量但反过来不行。check_BinaryOp处理算术运算的类型提升规则。check_Identifier查符号表未声明和未初始化分别报错。错误恢复策略是每个check方法返回一个类型字符串遇到错误返回ERROR父节点看到ERROR就跳过自己的检查直接返回ERROR避免一个错误引发雪崩式报错。所有错误收集到self.errors列表里最后统一输出。提示符号表的作用域管理要和 AST 的块结构严格对应。进入IfStmt的then分支前enter_scope处理完exit_scope。循环体和函数体同理。忘记退出作用域会导致变量泄漏到外层类型检查结果全错。5. 避坑与排查三个实验里最容易翻车的五个地方现象一词法分析器把1.2.3识别成一个浮点数。原因是在_read_number里只判断了字符是不是数字或小数点没有限制小数点只能出现一次。解决方法是加一个is_float标志遇到第二个小数点就跳出循环让后续字符走别的分支报错或单独成 Token。现象二语法分析器在解析if (a b) { ... }时栈溢出。原因是表达式文法存在左递归parseExpr直接递归调用了自己。解决方法是把文法改写成右递归形式或者在递归下降里用循环代替递归处理左结合的运算符。我一般用循环代码更直观。现象三语义分析报“变量未声明”但变量明明在上一行声明了。原因是符号表的作用域管理有问题声明时压入了新作用域但没退出导致后续查找从错误的作用域链开始。排查方法是打印符号表的作用域栈看声明和查找时栈的深度是否一致。常见错误是在parseBlock里enter_scope后忘记在块结束时exit_scope。现象四类型检查把int和float相加报成错误。原因是check_BinaryOp里只处理了同类型运算没有实现隐式类型提升。解决方法是加一个promote函数把int和float统一提升到float再判断。注意赋值语句的方向性float int合法int float不合法。现象五AST 遍历时某些节点没有被访问到。原因是访问者模式的分派方法名拼写错误getattr找不到对应方法就调了generic_check抛异常但异常被上层捕获后静默跳过了。排查方法是在generic_check里打印节点类型和行号确认哪些节点走了默认分支。常见遗漏是UnaryOp、CallExpr这类不常用的节点。6. 进阶技巧用 AST 解释执行验证前端正确性三个实验做完你手里有一个能生成 AST 并完成类型检查的前端。但怎么证明它是对的最直接的办法是写一个简单的 AST 解释器把程序跑起来看输出。这比对着 Token 流和 AST 打印结果肉眼核对高效得多而且能发现一些类型检查覆盖不到的运行时问题。解释器的核心是一个evaluate方法对每种 AST 节点求值。变量环境用字典模拟函数调用需要维护调用栈。下面是一个支持算术表达式和变量声明的极简解释器。# interpreter.py from ast_nodes import * class Interpreter: def __init__(self): self.env {} def eval(self, node): method eval_ type(node).__name__ return getattr(self, method)(node) def eval_Program(self, node): result None for decl in node.decls: result self.eval(decl) return result def eval_VarDecl(self, node): val self.eval(node.init) if node.init else 0 self.env[node.name] val return val def eval_BinaryOp(self, node): left self.eval(node.left) right self.eval(node.right) if node.op : return left right if node.op -: return left - right if node.op *: return left * right if node.op /: if right 0: raise RuntimeError(fDivision by zero at line {node.line}) return left / right raise RuntimeError(fUnknown operator {node.op}) def eval_Literal(self, node): if node.lit_type INT_CONST: return int(node.value) return float(node.value) def eval_Identifier(self, node): if node.name not in self.env: raise RuntimeError(fUndefined variable {node.name} at line {node.line}) return self.env[node.name]eval同样用getattr分派。eval_VarDecl把变量值存进self.enveval_Identifier从环境里取。eval_BinaryOp处理四则运算除法检查除零。这个解释器虽然简单但足以验证词法、语法、语义三个阶段是否协同工作。验证流程是这样的先写一段测试程序包含变量声明、算术表达式、括号嵌套、类型混合运算。用词法分析器生成 Token 流肉眼扫一遍确认没有奇怪的 Token。再用语法分析器生成 AST打印出来看结构是否符合预期。然后跑类型检查确认没有误报和漏报。最后用解释器执行把结果和手工计算的结果对比。如果四个环节都通过基本可以确定前端实现是正确的。我自己的习惯是每完成一个实验就写一组回归测试用例把输入程序和期望输出存成文件。改代码后跑一遍全部用例避免修一个 bug 引入两个新 bug。这套实验的代码量不大但边界情况多回归测试是唯一的后悔药。希望帮到你。本文还有配套的精品资源点击获取
山东大学编译原理实验：词法、语法、语义分析全流程实战
简介这份资源是山东大学编译原理与技术课程新版实验一至三的配套代码包面向正在学习编译器前端构建的高校学生与自学者帮助解决词法分析与语法分析从理论到代码落地的实践难题。压缩包共15个文件约30KB以8个h头文件与5个cpp源文件为核心辅以1个sh构建脚本和1个md说明文档涵盖词法分析器、语法分析器、符号表与目标代码生成等模块的接口定义与实现骨架。内容围绕有限自动机识别词素、上下文无关文法构造抽象语法树、递归下降与LR分析等关键技术展开实验一至三层层递进从识别关键字、标识符、常量与运算符到生成AST并集成前端、处理编译错误。已有57人学习下载适合希望对照课程要求动手实现Lexer与Parser、理解编译器前端整体流程的读者参考也可作为课程实验的起步模板与排错参照。1. 山东大学编译原理新版实验从词法到语义的三级跳到底在练什么如果你在山东大学选过编译原理与技术这门课大概率听过一句话实验一~三做不完期末直接裂开。新版实验把词法分析、语法分析、语义分析串成一条完整的编译前端流水线不再是各自为战的孤立练习。你最终交付的是一个能跑通自定义语言子集的微型编译器前端输入源代码输出带类型标注的中间表示。适合谁正在修这门课、想提前动手的本科生以及想用一个小项目把编译原理从纸面公式拉回工程现实的开发者。热搜里“编译原理实验”反复出现说明大家卡的不是理论是不知道从哪一行代码开始写。我带过几届学生做这套实验血泪经验就一条别一上来啃龙书先把实验框架的输入输出格式吃透再按词法→语法→语义的顺序逐个击破。下面按我实际带做的路径把三个实验拆成可复现的步骤。2. 实验一词法分析器的手写实现与正则引擎选型2.1 为什么手写 DFA 比直接调库更稳词法分析的核心任务就一个把字符流切成 Token 流。常见做法有两种一是用 flex 自动生成二是手写确定有限自动机。我一般会建议手写原因很实际——新版实验的 Token 定义里有一些边界情况比如浮点数后紧跟运算符、注释嵌套、标识符里允许下划线但数字不能开头自动生成工具处理这些要么写复杂的正则要么生成一堆你根本看不懂的状态表。手写 DFA 虽然代码量大一点但每个状态转移你都能在调试器里跟进去看翻车了也知道在哪翻的。先定义 Token 类型。假设实验要求支持的关键字有int、float、if、else、while、return运算符有 - * / !分隔符有( ) { } ; ,再加上标识符、整数常量、浮点常量、注释和空白。Token 结构体至少包含类型、原始字符串、行号三样行号是后面报错定位的后悔药。# token_def.py from enum import Enum, auto class TokenType(Enum): KEYWORD auto() IDENTIFIER auto() INT_CONST auto() FLOAT_CONST auto() OPERATOR auto() DELIMITER auto() COMMENT auto() EOF auto() class Token: def __init__(self, ttype, value, line): self.type ttype self.value value self.line line def __repr__(self): return fToken({self.type.name}, {self.value}, line{self.line})这段代码定义了 Token 的类型枚举和基本结构。line字段必须保留实验二语法分析报错时全靠它定位。value存原始字符串而不是归一化后的值因为语义分析阶段可能需要区分0x1F和31这种不同写法。2.2 状态转移表怎么画、怎么调手写词法分析器的骨架是一个while循环加一个state变量。初始状态为START每读一个字符根据当前状态和字符类别决定下一个状态。字符类别至少分四类字母/下划线、数字、运算符字符、分隔符/空白。下面是一个简化版的核心循环。# lexer.py from token_def import Token, TokenType KEYWORDS {int, float, if, else, while, return} OPERATORS {, -, *, /, , , , !, , , , !} DELIMITERS {(, ), {, }, ;, ,} class Lexer: def __init__(self, source): self.src source self.pos 0 self.line 1 self.tokens [] def tokenize(self): while self.pos len(self.src): ch self.src[self.pos] if ch in \t\r: self.pos 1 elif ch \n: self.line 1 self.pos 1 elif ch.isalpha() or ch _: self._read_identifier() elif ch.isdigit(): self._read_number() elif ch in OPERATORS or ch in (, , , !): self._read_operator() elif ch in DELIMITERS: self.tokens.append(Token(TokenType.DELIMITER, ch, self.line)) self.pos 1 else: raise SyntaxError(fUnexpected char {ch} at line {self.line}) self.tokens.append(Token(TokenType.EOF, , self.line)) return self.tokens def _read_identifier(self): start self.pos while self.pos len(self.src) and (self.src[self.pos].isalnum() or self.src[self.pos] _): self.pos 1 word self.src[start:self.pos] ttype TokenType.KEYWORD if word in KEYWORDS else TokenType.IDENTIFIER self.tokens.append(Token(ttype, word, self.line)) def _read_number(self): start self.pos is_float False while self.pos len(self.src) and (self.src[self.pos].isdigit() or self.src[self.pos] .): if self.src[self.pos] .: if is_float: break is_float True self.pos 1 value self.src[start:self.pos] ttype TokenType.FLOAT_CONST if is_float else TokenType.INT_CONST self.tokens.append(Token(ttype, value, self.line)) def _read_operator(self): two self.src[self.pos:self.pos2] if two in (, , , !): self.tokens.append(Token(TokenType.OPERATOR, two, self.line)) self.pos 2 else: self.tokens.append(Token(TokenType.OPERATOR, self.src[self.pos], self.line)) self.pos 1tokenize是主循环按字符类别分派到不同的读取函数。_read_identifier用贪心策略一直读到非字母数字下划线为止然后查关键字表决定是关键字还是标识符。_read_number处理小数点遇到第二个小数点就停避免把1.2.3吞成一个 Token。_read_operator先看两个字符的组合匹配这类双字符运算符否则退化为单字符。参数调整上最容易出问题的是注释处理。如果实验要求支持//单行注释和/* */块注释需要在主循环里加分支。块注释要记录起始行号遇到未闭合的/*要在 EOF 时报错并指出起始行。我见过太多人在这里只写了个while跳过字符结果嵌套注释或者注释里出现*/就崩了。提示写完词法分析器后先拿一段包含所有 Token 类型的测试代码跑一遍把输出打印出来逐行核对。不要急着写语法分析词法阶段的 bug 会像幽灵一样在后续阶段反复出现。3. 实验二递归下降语法分析与 AST 构建3.1 文法改写消除左递归和提取公因子实验二通常给一个表达式文法要求实现语法分析并构建抽象语法树。直接拿课本上的文法写递归下降会死循环因为表达式文法几乎都带左递归。比如E - E T | T递归下降解析器在parseE里第一件事就是调parseE栈直接溢出。必须改写成右递归形式E - T EE - T E | ε。提取公因子则是为了减少回溯比如Stmt - ID Expr ; | ID ( Args ) ;可以提取成Stmt - ID StmtTail再看StmtTail的首字符决定走赋值还是函数调用。改写后的文法要保证 LL(1)也就是每个非终结符的 FIRST 集不相交。实际操作中你可以先手算 FIRST 和 FOLLOW 集画一张预测分析表确认没有冲突再动手写代码。如果实验要求支持if-else悬挂问题记得用最近匹配原则把else绑定到最近的if。3.2 AST 节点设计与递归下降代码骨架AST 节点用类继承体系最清晰。基类ASTNode带一个accept方法用于后续遍历子类包括Program、VarDecl、FuncDecl、AssignStmt、IfStmt、WhileStmt、ReturnStmt、BinaryOp、UnaryOp、Literal、Identifier、CallExpr等。每个节点存必要的子节点和行号。# ast_nodes.py class ASTNode: def __init__(self, line): self.line line class Program(ASTNode): def __init__(self, decls, line0): super().__init__(line) self.decls decls class VarDecl(ASTNode): def __init__(self, vtype, name, init, line): super().__init__(line) self.vtype vtype self.name name self.init init class BinaryOp(ASTNode): def __init__(self, op, left, right, line): super().__init__(line) self.op op self.left left self.right right class Literal(ASTNode): def __init__(self, value, lit_type, line): super().__init__(line) self.value value self.lit_type lit_type class Identifier(ASTNode): def __init__(self, name, line): super().__init__(line) self.name name递归下降解析器的结构是一组parseXxx方法每个方法对应一个非终结符。入口是parseProgram循环调用parseDecl直到 EOF。parseDecl看当前 Token 是类型关键字还是标识符决定走变量声明还是函数声明。表达式解析按优先级分层parseExpr调parseTermparseTerm调parseFactor每层处理对应优先级的运算符。# parser.py from token_def import TokenType from ast_nodes import * class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def consume(self, ttypeNone): tok self.tokens[self.pos] if ttype and tok.type ! ttype: raise SyntaxError(fExpected {ttype}, got {tok.type} at line {tok.line}) self.pos 1 return tok def parseProgram(self): decls [] while self.peek().type ! TokenType.EOF: decls.append(self.parseDecl()) return Program(decls) def parseDecl(self): if self.peek().type TokenType.KEYWORD and self.peek().value in (int, float): return self.parseVarDecl() elif self.peek().type TokenType.IDENTIFIER: return self.parseFuncDecl() else: raise SyntaxError(fUnexpected token {self.peek()} at line {self.peek().line}) def parseVarDecl(self): vtype self.consume(TokenType.KEYWORD).value name self.consume(TokenType.IDENTIFIER).value init None if self.peek().type TokenType.OPERATOR and self.peek().value : self.consume() init self.parseExpr() self.consume(TokenType.DELIMITER) # 分号 return VarDecl(vtype, name, init, self.tokens[self.pos-1].line) def parseExpr(self): left self.parseTerm() while self.peek().type TokenType.OPERATOR and self.peek().value in (, -): op self.consume().value right self.parseTerm() left BinaryOp(op, left, right, left.line) return left def parseTerm(self): left self.parseFactor() while self.peek().type TokenType.OPERATOR and self.peek().value in (*, /): op self.consume().value right self.parseFactor() left BinaryOp(op, left, right, left.line) return left def parseFactor(self): tok self.peek() if tok.type TokenType.INT_CONST or tok.type TokenType.FLOAT_CONST: self.consume() return Literal(tok.value, tok.type.name, tok.line) elif tok.type TokenType.IDENTIFIER: self.consume() return Identifier(tok.value, tok.line) elif tok.type TokenType.DELIMITER and tok.value (: self.consume() expr self.parseExpr() self.consume(TokenType.DELIMITER) # 右括号 return expr else: raise SyntaxError(fUnexpected token {tok} in factor at line {tok.line})parseExpr和parseTerm的分层结构直接对应运算符优先级parseFactor处理括号和原子表达式。每个consume调用都带期望类型不匹配就抛异常并带行号。parseVarDecl里初始化表达式是可选的所以先peek判断有没有等号。参数调整方面如果实验要求支持一元负号需要在parseFactor里加分支遇到-就消费掉递归调parseFactor包成UnaryOp。注意一元负号的优先级高于乘除所以放在parseFactor里而不是parseTerm里。另一个坑是赋值语句和函数调用的区分两者都以标识符开头需要向前看一个 Token如果是就是赋值如果是(就是函数调用。注意递归下降解析器对错误恢复很不友好一旦抛异常整个解析就停了。如果实验要求报多个错误需要在parseDecl层面做同步捕获异常后跳到下一个分号或右大括号继续解析后面的声明。4. 实验三语义分析与符号表管理4.1 符号表的数据结构选择语义分析阶段要干三件事建符号表、做类型检查、标注 AST。符号表用哈希表加作用域链最合适。每个作用域是一个字典键是变量名值是符号信息类型、行号、是否初始化。作用域链用列表模拟栈进入块就压一个新字典退出就弹出。# symbol_table.py class Symbol: def __init__(self, name, stype, line, initializedFalse): self.name name self.stype stype self.line line self.initialized initialized class SymbolTable: def __init__(self): self.scopes [{}] def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, stype, line): if name in self.scopes[-1]: raise SemanticError(fRedeclaration of {name} at line {line}) self.scopes[-1][name] Symbol(name, stype, line) def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] return None def mark_initialized(self, name): sym self.lookup(name) if sym: sym.initialized Truedeclare只在当前作用域查重允许内层作用域遮蔽外层同名变量。lookup从最内层往外找找到就返回。mark_initialized在赋值语句处理时调用用于检测使用未初始化变量。4.2 类型检查的遍历顺序与错误恢复类型检查用后序遍历 AST先检查子节点类型再检查父节点。比如BinaryOp节点先递归检查left和right拿到两个类型后再判断是否支持这两个类型的组合。整数加整数得整数浮点加浮点得浮点整数加浮点需要隐式提升为浮点。如果遇到不支持的组合报类型错误并返回一个ERROR类型避免后续节点连环报错。# type_checker.py from ast_nodes import * from symbol_table import SymbolTable class TypeChecker: def __init__(self): self.st SymbolTable() self.errors [] def check(self, node): method check_ type(node).__name__ visitor getattr(self, method, self.generic_check) return visitor(node) def generic_check(self, node): raise SemanticError(fNo check method for {type(node).__name__}) def check_Program(self, node): for decl in node.decls: self.check(decl) def check_VarDecl(self, node): if node.init: init_type self.check(node.init) if init_type ! node.vtype and not (node.vtype float and init_type int): self.errors.append(fType mismatch in declaration of {node.name} at line {node.line}) self.st.declare(node.name, node.vtype, node.line) def check_BinaryOp(self, node): lt self.check(node.left) rt self.check(node.right) if lt ERROR or rt ERROR: return ERROR if node.op in (, -, *, /): if lt int and rt int: return int elif lt in (int, float) and rt in (int, float): return float else: self.errors.append(fInvalid operands for {node.op} at line {node.line}) return ERROR return ERROR def check_Identifier(self, node): sym self.st.lookup(node.name) if not sym: self.errors.append(fUndeclared variable {node.name} at line {node.line}) return ERROR if not sym.initialized: self.errors.append(fVariable {node.name} used before initialization at line {node.line}) return sym.stype def check_Literal(self, node): return int if node.lit_type INT_CONST else floatcheck方法用getattr动态分派到对应的check_Xxx方法这是访问者模式的简化写法。check_VarDecl先检查初始化表达式类型允许int赋给float变量但反过来不行。check_BinaryOp处理算术运算的类型提升规则。check_Identifier查符号表未声明和未初始化分别报错。错误恢复策略是每个check方法返回一个类型字符串遇到错误返回ERROR父节点看到ERROR就跳过自己的检查直接返回ERROR避免一个错误引发雪崩式报错。所有错误收集到self.errors列表里最后统一输出。提示符号表的作用域管理要和 AST 的块结构严格对应。进入IfStmt的then分支前enter_scope处理完exit_scope。循环体和函数体同理。忘记退出作用域会导致变量泄漏到外层类型检查结果全错。5. 避坑与排查三个实验里最容易翻车的五个地方现象一词法分析器把1.2.3识别成一个浮点数。原因是在_read_number里只判断了字符是不是数字或小数点没有限制小数点只能出现一次。解决方法是加一个is_float标志遇到第二个小数点就跳出循环让后续字符走别的分支报错或单独成 Token。现象二语法分析器在解析if (a b) { ... }时栈溢出。原因是表达式文法存在左递归parseExpr直接递归调用了自己。解决方法是把文法改写成右递归形式或者在递归下降里用循环代替递归处理左结合的运算符。我一般用循环代码更直观。现象三语义分析报“变量未声明”但变量明明在上一行声明了。原因是符号表的作用域管理有问题声明时压入了新作用域但没退出导致后续查找从错误的作用域链开始。排查方法是打印符号表的作用域栈看声明和查找时栈的深度是否一致。常见错误是在parseBlock里enter_scope后忘记在块结束时exit_scope。现象四类型检查把int和float相加报成错误。原因是check_BinaryOp里只处理了同类型运算没有实现隐式类型提升。解决方法是加一个promote函数把int和float统一提升到float再判断。注意赋值语句的方向性float int合法int float不合法。现象五AST 遍历时某些节点没有被访问到。原因是访问者模式的分派方法名拼写错误getattr找不到对应方法就调了generic_check抛异常但异常被上层捕获后静默跳过了。排查方法是在generic_check里打印节点类型和行号确认哪些节点走了默认分支。常见遗漏是UnaryOp、CallExpr这类不常用的节点。6. 进阶技巧用 AST 解释执行验证前端正确性三个实验做完你手里有一个能生成 AST 并完成类型检查的前端。但怎么证明它是对的最直接的办法是写一个简单的 AST 解释器把程序跑起来看输出。这比对着 Token 流和 AST 打印结果肉眼核对高效得多而且能发现一些类型检查覆盖不到的运行时问题。解释器的核心是一个evaluate方法对每种 AST 节点求值。变量环境用字典模拟函数调用需要维护调用栈。下面是一个支持算术表达式和变量声明的极简解释器。# interpreter.py from ast_nodes import * class Interpreter: def __init__(self): self.env {} def eval(self, node): method eval_ type(node).__name__ return getattr(self, method)(node) def eval_Program(self, node): result None for decl in node.decls: result self.eval(decl) return result def eval_VarDecl(self, node): val self.eval(node.init) if node.init else 0 self.env[node.name] val return val def eval_BinaryOp(self, node): left self.eval(node.left) right self.eval(node.right) if node.op : return left right if node.op -: return left - right if node.op *: return left * right if node.op /: if right 0: raise RuntimeError(fDivision by zero at line {node.line}) return left / right raise RuntimeError(fUnknown operator {node.op}) def eval_Literal(self, node): if node.lit_type INT_CONST: return int(node.value) return float(node.value) def eval_Identifier(self, node): if node.name not in self.env: raise RuntimeError(fUndefined variable {node.name} at line {node.line}) return self.env[node.name]eval同样用getattr分派。eval_VarDecl把变量值存进self.enveval_Identifier从环境里取。eval_BinaryOp处理四则运算除法检查除零。这个解释器虽然简单但足以验证词法、语法、语义三个阶段是否协同工作。验证流程是这样的先写一段测试程序包含变量声明、算术表达式、括号嵌套、类型混合运算。用词法分析器生成 Token 流肉眼扫一遍确认没有奇怪的 Token。再用语法分析器生成 AST打印出来看结构是否符合预期。然后跑类型检查确认没有误报和漏报。最后用解释器执行把结果和手工计算的结果对比。如果四个环节都通过基本可以确定前端实现是正确的。我自己的习惯是每完成一个实验就写一组回归测试用例把输入程序和期望输出存成文件。改代码后跑一遍全部用例避免修一个 bug 引入两个新 bug。这套实验的代码量不大但边界情况多回归测试是唯一的后悔药。希望帮到你。本文还有配套的精品资源点击获取