简介本资源是广东工业大学编译原理课程配套实验项目面向计算机专业本科生及编译技术初学者聚焦PL/0教学编译器的扩展开发与实践。内容围绕词法、语法及语义分析模块的改造重点实现ELSE等保留字支持、/--等运算符扩充、不等号替换及IF-ELSE条件语句增强切实提升对编译前端核心机制的理解与动手能力。压缩包共24个文件644KB含4个关键源码文件pl0.h、PL0.cpp、2个可执行程序exe、1份完整实验报告doc、若干调试中间产物pdb、obj、tmp及工程配置文件dsw、dsp、opt结构完整便于编译调试与源码追踪。已有789人学习下载提供开箱即用的可运行环境与清晰的修改对照逻辑特别适合课程实验复现、编译原理课设参考及PL/0二次开发入门。1. 广工编译原理实验不是抄代码是亲手把“hello world”喂给词法分析器嚼碎再吐出来你在广工信科院或计算机学院的机房里盯着屏幕上一行行token: ID, value: main的输出发呆——这根本不是“跑通就行”的水课实验而是你第一次亲手把人类写的int a 10;这种直觉性语句掰开、揉碎、打标签、送进语法树根部的过程。广工编译原理实验尤其对应王生原《编译原理》第3版第三章及后续章节的核心目标从来不是写个能跑的玩具程序而是建立对语言边界、形式化定义、状态迁移本质的肌肉记忆。它解决的是为什么ab会报错而a b却合法为什么if (x5)能编译但逻辑危险这些坑全藏在词法扫描器的正则规则里、在语法分析器的状态栈顶里、在符号表的哈希桶里。适合谁大三刚学完数据结构和离散数学的同学——你不需要会写LL(1)预测分析表但必须能看懂FIRST集怎么推你不用手推LR(0)项目集规范族但得明白移进-归约冲突为什么在else处爆发。这不是理论考试是用C/Java/Python把教材第三章的“有限自动机”从纸面焊进你IDE里的实操战场。2. 从正则到DFA用Python手撸词法分析器不调用re模块的硬核落地广工编译原理实验的第一关永远是词法分析。很多同学直接import re写个re.findall就交差结果在老师问“你的DFA状态转移图长什么样”时哑火。真正的广工风格是让你画出状态图、写出转移矩阵、再编码实现。我们以王生原教材第三章典型Token为例关键字if,else,while、标识符字母开头字母数字下划线、整数无符号十进制、运算符,-,*,/,,和分隔符;,(,)。下面是你能在广工机房Linux环境Ubuntu 20.04上直接运行的最小可行方案。2.1 手绘DFA状态图并编码为转移矩阵先别急着敲代码。拿出草稿纸按教材P67的“识别标识符的NFA→DFA转换”方法画出包含以下状态的DFAS0: 初始态等待输入S1: 读到字母进入标识符/关键字路径S2: 读到数字进入整数路径S3: 读到需判断是还是S4: 接收态标识符/关键字S5: 接收态整数S6: 接收态S7: 接收态单字符运算符如提示广工实验报告要求附状态图建议用graphviz生成矢量图。不要手绘拍照糊弄——老师一眼看出你没推导过。将上述状态图转化为二维列表trans_table行索引为当前状态列索引为输入字符类型用char_type函数分类# char_type.py: 字符分类工具 def char_type(c): if c.isalpha(): return LETTER elif c.isdigit(): return DIGIT elif c in -*/;(): return c # 直接用字符本身作key简化处理 elif c or c \t or c \n: return WS # whitespace else: return OTHER # dfa_trans.py: DFA转移表精简版仅含关键状态 # 索引顺序: [S0, S1, S2, S3, S4, S5, S6, S7] # 列顺序: LETTER, DIGIT, , , -, *, /, ;, (, ), WS, OTHER trans_table [ # S0: 初始态 [1, 2, 3, 7, 7, 7, 7, 7, 7, 0, -1], # 遇字母→S1, 数字→S2, →S3, 等→S7 # S1: 字母后 [1, 1, -1, -1, 4, -1, -1, -1, -1, 4, -1], # 字母/数字继续S1空格→S4(接收), 其他非法 # S2: 数字后 [-1, 2, -1, -1, -1, 5, -1, -1, -1, 5, -1], # 只接受数字空格→S5(接收) # S3: 遇到后 [-1, -1, 6, -1, -1, -1, -1, -1, -1, 6, -1], # 再遇→S6()否则S3无效 # S4: 标识符接收态需回退1位 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # 接收态不再转移 # S5: 整数接收态 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # S6: 接收态 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], # S7: 单字符运算符接收态如 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], ]参数说明trans_table[i][j]表示状态i遇到类型j字符后跳转到的状态编号。-1表示错误如S0遇到。char_type函数将无限字符空间压缩为有限类别这是DFA可实现的关键——广工实验强调“有限状态”而非正则引擎的黑匣子。状态S4/S5/S6/S7是接收态编码时需在进入该状态后立即截断当前token并返回。2.2 实现词法扫描器状态驱动回退机制教材P72强调“词法分析器必须能回退一个字符”因为需要读两个才确认而单个可能是赋值符。广工实验验收点就卡在这里你的扫描器能否正确区分ab和ab# lexer.py from char_type import char_type class Lexer: def __init__(self, source_code): self.code source_code self.pos 0 self.line 1 self.col 1 def next_token(self): if self.pos len(self.code): return (EOF, , self.line, self.col) # 跳过空白 while self.pos len(self.code) and char_type(self.code[self.pos]) WS: if self.code[self.pos] \n: self.line 1 self.col 1 else: self.col 1 self.pos 1 if self.pos len(self.code): return (EOF, , self.line, self.col) # 从S0开始DFA state 0 start_pos self.pos token_chars [] while self.pos len(self.code): c self.code[self.pos] c_type char_type(c) # 获取列索引 try: col_idx [LETTER, DIGIT, , , -, *, /, ;, (, ), WS, OTHER].index(c_type) except ValueError: col_idx 10 # OTHER # 查转移表 if state len(trans_table) and col_idx len(trans_table[state]): next_state trans_table[state][col_idx] else: next_state -1 if next_state -1: # 当前状态无法处理此字符 → 回退提交已读部分 break elif next_state in [4, 5, 6, 7]: # 接收态 # 记录当前字符然后break接收态不消耗下一个字符 token_chars.append(c) self.pos 1 # 但需检查是否为若当前是且下一个是则回退并重走 if next_state 3 and self.pos len(self.code) and self.code[self.pos] : self.pos - 1 # 回退到第一个 token_chars.pop() # 移除刚加的 state 3 # 重新进入S3 continue # 确认接收根据state返回token类型 token_str .join(token_chars) if state 4: if token_str in [if, else, while]: return (KEYWORD, token_str, self.line, self.col - len(token_str) 1) else: return (ID, token_str, self.line, self.col - len(token_str) 1) elif state 5: return (INT, token_str, self.line, self.col - len(token_str) 1) elif state 6: return (EQ, , self.line, self.col - len(token_str) 1) elif state 7: return (OP, c, self.line, self.col - len(token_str) 1) break else: # 非接收态推进 token_chars.append(c) self.pos 1 state next_state self.col 1 # 若未进入接收态报错如非法字符 if not token_chars: raise SyntaxError(fUnexpected character {self.code[self.pos]} at line {self.line}, col {self.col}) # 回退到未接收位置如S1读到!应停在S1并报错 self.pos start_pos raise SyntaxError(fInvalid token starting at line {self.line}, col {self.col}) # 测试用例广工实验十三常见输入 test_code if (a 10) { b a 1; } lexer Lexer(test_code) while True: tok lexer.next_token() print(f{tok[0]}: {tok[1]} (line {tok[2]}, col {tok[3]})) if tok[0] EOF: break逻辑说明next_token()方法严格模拟DFA执行每读一个字符查表跳转接收态立即返回token并手动控制pos指针不依赖re的自动匹配。关键细节的处理在接收态S3后二次判断若下一个是则回退pos并重走——这是广工实验报告必写的设计说明。col列号计算考虑了换行符避免实验报告中位置信息错乱老师会核对token位置与源码是否一致。3. 语法分析实战用递归下降法解析if-while语句绕开LL(1)构造的玄学陷阱广工编译原理实验的第二关是语法分析。教材第三章讲LL(1)文法但王生原第3版P112明确指出“递归下降分析器更易理解、调试适合教学实现”。广工实验十三if-while嵌套正是为此设计——它规避了构造FIRST/FOLLOW集的复杂推导让你聚焦在文法左递归消除、公共左因子提取、预测逻辑落地这三个血泪经验点上。3.1 从教材文法到可递归下降的改造原始文法教材P98程序 → 语句序列 语句序列 → 语句 | 语句语句序列 语句 → if 条件 then 语句 | while 条件 do 语句 | 赋值语句 条件 → 表达式 关系运算符 表达式 表达式 → 项 | 表达式 项 | 表达式 - 项 项 → 因子 | 项 * 因子 | 项 / 因子 因子 → ID | INT | ( 表达式 )问题来了表达式和项存在左递归直接写递归函数会无限调用。广工实验要求你手动改写// 消除左递归后的文法必须写在实验报告“文法改造”章节 表达式 → 项 表达式 表达式 → 项 表达式 | - 项 表达式 | ε 项 → 因子 项 项 → * 因子 项 | / 因子 项 | ε注意ε空串在代码中用if条件跳过不是真的返回空字符串。这是递归下降的核心技巧——用控制流替代文法产生式。3.2 Python实现递归下降分析器带错误恢复的parse_if_while广工实验验收时老师会故意给你if (x5) { y1; } else { z2; }这种带else的代码看你能否处理else悬空问题。我们的策略是不实现完整的else配对只保证if-then结构可解析符合实验十三最低要求但预留扩展接口。# parser.py from lexer import Lexer class Parser: def __init__(self, lexer): self.lexer lexer self.current_token self.lexer.next_token() def eat(self, expected_type): 匹配并消耗token if self.current_token[0] expected_type: self.current_token self.lexer.next_token() else: raise SyntaxError(fExpected {expected_type}, got {self.current_token[0]} fat line {self.current_token[2]}) def parse_program(self): 程序 → 语句序列 return self.parse_stmt_seq() def parse_stmt_seq(self): 语句序列 → 语句 | 语句语句序列 stmts [] while self.current_token[0] in [KEYWORD, ID, INT, (, {]: # 预测集合 stmts.append(self.parse_stmt()) return {type: stmt_seq, stmts: stmts} def parse_stmt(self): 语句 → if 条件 then 语句 | while 条件 do 语句 | 赋值语句 if self.current_token[0] KEYWORD: if self.current_token[1] if: return self.parse_if_stmt() elif self.current_token[1] while: return self.parse_while_stmt() elif self.current_token[0] ID: return self.parse_assign_stmt() else: raise SyntaxError(fUnexpected token {self.current_token} in statement context) def parse_if_stmt(self): if 条件 then 语句 self.eat(KEYWORD) # if self.eat(() cond self.parse_condition() self.eat()) self.eat(KEYWORD) # then — 注意广工实验十三文法中无else故此处不处理 body self.parse_stmt() return {type: if, cond: cond, body: body} def parse_while_stmt(self): while 条件 do 语句 self.eat(KEYWORD) # while self.eat(() cond self.parse_condition() self.eat()) self.eat(KEYWORD) # do body self.parse_stmt() return {type: while, cond: cond, body: body} def parse_condition(self): 条件 → 表达式 关系运算符 表达式 left self.parse_expression() op self.current_token[1] if self.current_token[0] ! OP or op not in [, !, , , , ]: raise SyntaxError(fExpected relation operator, got {self.current_token}) self.eat(OP) right self.parse_expression() return {type: condition, left: left, op: op, right: right} def parse_expression(self): 表达式 → 项 表达式 node self.parse_term() while self.current_token[0] OP and self.current_token[1] in [, -]: op self.current_token[1] self.eat(OP) right self.parse_term() node {type: binop, op: op, left: node, right: right} return node def parse_term(self): 项 → 因子 项 node self.parse_factor() while self.current_token[0] OP and self.current_token[1] in [*, /]: op self.current_token[1] self.eat(OP) right self.parse_factor() node {type: binop, op: op, left: node, right: right} return node def parse_factor(self): 因子 → ID | INT | ( 表达式 ) if self.current_token[0] ID: node {type: id, name: self.current_token[1]} self.eat(ID) return node elif self.current_token[0] INT: node {type: int, value: int(self.current_token[1])} self.eat(INT) return node elif self.current_token[0] (: self.eat(() node self.parse_expression() self.eat()) return node else: raise SyntaxError(fExpected ID, INT or (, got {self.current_token}) # 使用示例 test_code if (a 10) then b a 1; lexer Lexer(test_code) parser Parser(lexer) ast parser.parse_program() print(ast)参数说明eat()方法是核心它强制消耗token失败则抛出带位置信息的SyntaxError——广工实验报告要求错误信息精确到行列。parse_expression()中的while循环对应表达式的ε产生式当不满足/-时自然退出无需显式处理ε。parse_if_stmt()中self.eat(KEYWORD)两次调用分别吃掉if和then体现“关键词必须显式匹配”的教学要求。4. 符号表与作用域用嵌套字典实现多层作用域解决广工实验中变量重复声明的硬伤广工编译原理实验的第三关是符号表管理。很多同学卡在“为什么int a; int a;要报错而{int a;} {int a;}却合法”——这背后是作用域嵌套和符号表层次的工程落地。教材P156讲符号表结构但没告诉你如何用Python字典高效实现。我们采用嵌套字典作用域栈方案完全匹配广工实验十三对局部变量和全局变量的区分需求。4.1 符号表设计三层嵌套结构广工实验要求符号表支持全局作用域最外层函数作用域本实验暂不实现函数但需预留块作用域{...}内我们设计SymbolTable类内部用list维护作用域栈每个栈帧是dict键为变量名值为{type: int, scope_level: 0, line: 5}# symbol_table.py class SymbolTable: def __init__(self): self.scopes [{}] # 初始化全局作用域 def enter_scope(self): 进入新作用域如{...} self.scopes.append({}) def exit_scope(self): 退出当前作用域 if len(self.scopes) 1: self.scopes.pop() else: raise RuntimeError(Cannot exit global scope) def insert(self, name, var_info): 插入符号检查重复声明 current_scope self.scopes[-1] if name in current_scope: line var_info.get(line, ?) raise SemanticError(fRedeclaration of {name} at line {line}) current_scope[name] var_info def lookup(self, name): 从内向外查找符号 for scope in reversed(self.scopes): if name in scope: return scope[name] return None def get_current_scope_level(self): return len(self.scopes) - 1 # semantic_error.py class SemanticError(Exception): pass4.2 在语法分析中注入符号表操作广工实验十三虽不强制语义分析但老师会问“如果int a;后出现a 5;你怎么知道a已声明”——答案就在parse_assign_stmt()中# parser_with_symtab.py from symbol_table import SymbolTable from semantic_error import SemanticError class ParserWithSymtab: def __init__(self, lexer): self.lexer lexer self.current_token self.lexer.next_token() self.symtab SymbolTable() def parse_assign_stmt(self): 赋值语句 → ID 表达式 ; # 解析左值ID if self.current_token[0] ! ID: raise SyntaxError(fExpected ID before , got {self.current_token}) var_name self.current_token[1] line self.current_token[2] self.eat(ID) # 检查是否已声明广工实验要求未声明变量赋值报错 if self.symtab.lookup(var_name) is None: raise SemanticError(fUndeclared variable {var_name} at line {line}) # 匹配 self.eat(OP) # if self.current_token[1] ! : raise SyntaxError(fExpected , got {self.current_token[1]}) # 解析右值表达式 expr self.parse_expression() self.eat(;) return {type: assign, var: var_name, expr: expr} def parse_decl_stmt(self): 声明语句 → int ID ; 广工实验十三扩展 self.eat(KEYWORD) # int if self.current_token[0] ! ID: raise SyntaxError(fExpected ID after int, got {self.current_token}) var_name self.current_token[1] line self.current_token[2] self.eat(ID) self.eat(;) # 插入符号表 self.symtab.insert(var_name, { type: int, scope_level: self.symtab.get_current_scope_level(), line: line }) return {type: decl, var: var_name, type: int} # 修改parse_stmt以支持声明 def parse_stmt(self): if self.current_token[0] KEYWORD: if self.current_token[1] int: return self.parse_decl_stmt() elif self.current_token[1] if: return self.parse_if_stmt() elif self.current_token[1] while: return self.parse_while_stmt() elif self.current_token[0] ID: # 可能是赋值或函数调用此处简化为赋值 return self.parse_assign_stmt() else: raise SyntaxError(fUnexpected token {self.current_token})关键设计点enter_scope()/exit_scope()对应{和}的语法节点——在parse_if_stmt()中then后的{应触发enter_scope()}触发exit_scope()。lookup()从栈顶向下查确保内层变量屏蔽外层同名变量{int a;} a5;中第二个a查不到。insert()在插入前检查name in current_scope这是广工实验报告“语义检查”章节的硬性得分点。5. 广工编译原理实验避坑指南那些让90%同学在验收时翻车的5个致命细节广工编译原理实验的验收不是“跑出结果就行”而是逐行检查你的设计文档、状态图、文法改造过程、错误信息格式。以下是我在广工机房帮学弟学妹debug三年总结的5个高频翻车点每一条都对应老师当场扣分的瞬间5.1 状态图没标接收态DFA转移表漏填-1导致无限循环现象词法分析器读到a123b时卡死CPU占满。原因DFA转移表中状态S1标识符中遇到非字母数字字符如b后的b时trans_table[1][10]OTHER列未设为-1而是默认0导致状态在S0→S1→S0→S1间震荡。解决所有转移表末尾必须显式初始化为-1并在next_token()中严格检查next_state -1时break。广工实验报告要求表格用LaTeX绘制务必补全所有-1。5.2识别时忘记回退把ab切分成a,,b现象输入if (a5)词法器输出ID:a,OP:,ID:b错误。原因在S3状态读到第一个后未判断下一个字符是否为就直接返回OP:导致第二个被当作新token开头。解决在next_token()中当state3即刚读到时必须peek下一个字符if self.pos len(self.code) and self.code[self.pos] 成立则self.pos - 1回退并设置state3重新进入循环。5.3 递归下降中parse_expression()未处理左结合123解析成1(23)而非(12)3现象AST中binop节点的left是原子节点right是另一个binop导致运算顺序错误。原因教材消除左递归后的文法表达式 → 项 表达式天然支持左结合但代码中parse_expression()的while循环写成了右递归结构。解决确保node初始为parse_term()结果每次while迭代都用node {left: node, op: op, right: right}更新这样123的node始终是(12)再与3组合。5.4 符号表作用域嵌套时{int a;} int a;未报错现象全局声明a后在{}内再声明a程序不报错。原因insert()方法只检查当前作用域self.scopes[-1]未禁止在全局作用域重复声明。但广工实验要求“全局变量不可重声明”。解决在insert()中增加判断if len(self.scopes) 1 and name in self.scopes[0]即全局作用域已存在则报错。或者更严谨scope_level 0时全局唯一。5.5 错误信息不带行列号老师说“看不出你定位到了哪一行”现象报错Unexpected token OP但没写明在哪一行。原因eat()方法中raise SyntaxError(...)未传入self.current_token[2]行号和[3]列号。解决所有异常必须包含fat line {self.current_token[2]}, col {self.current_token[3]}。广工实验报告评分细则明确要求“错误提示信息完整”。6. 终极验证技巧用广工真题测试集做回归测试把“能跑”变成“稳跑”广工编译原理实验的终极考验不是你交的代码而是你交的测试报告。老师会给你一份test_cases.txt里面是历年真题输入要求你输出标准token流和AST。我教你一招用Python的difflib做自动化比对把“手动核对”变成“一键验证”这才是广工人该有的工程素养。6.1 构建标准化测试框架创建test_runner.py读取测试用例文件每例以---分隔对每个用例运行词法语法分析并生成.gold标准输出# test_runner.py import sys from lexer import Lexer from parser_with_symtab import ParserWithSymtab from difflib import unified_diff def run_test_case(code): 运行单个测试用例返回token流和AST字符串 lexer Lexer(code) tokens [] while True: tok lexer.next_token() tokens.append(f{tok[0]}: {tok[1]}) if tok[0] EOF: break lexer2 Lexer(code) # 重置lexer parser ParserWithSymtab(lexer2) try: ast parser.parse_program() # 简单AST转字符串实际用json.dumps更稳 ast_str str(ast).replace(, ).replace( , ) except Exception as e: ast_str fERROR: {str(e)} return \n.join(tokens), ast_str def main(): if len(sys.argv) ! 2: print(Usage: python test_runner.py test_cases.txt) return with open(sys.argv[1], r, encodingutf-8) as f: content f.read() test_cases content.strip().split(---) for i, case in enumerate(test_cases): if not case.strip(): continue print(f\n Test Case {i1} ) code case.strip() try: tokens_out, ast_out run_test_case(code) # 生成.gold文件首次运行时手动校验后保存 gold_file ftest_{i1}.gold try: with open(gold_file, r, encodingutf-8) as f: gold_tokens f.readline().strip() gold_ast f.readline().strip() # 比对token流 if tokens_out ! gold_tokens: print(TOKEN MISMATCH:) diff unified_diff( [gold_tokens], [tokens_out], fromfileexpected, tofilegot ) print(.join(diff)) # 比对AST if ast_out ! gold_ast: print(AST MISMATCH:) diff unified_diff( [gold_ast], [ast_out], fromfileexpected, tofilegot ) print(.join(diff)) except FileNotFoundError: # 首次运行生成.gold with open(gold_file, w, encodingutf-8) as f: f.write(tokens_out \n) f.write(ast_out \n) print(fGenerated {gold_file}. Please verify manually.) except Exception as e: print(fRUNTIME ERROR: {e}) if __name__ __main__: main()6.2 广工真题测试集构建示例准备test_cases.txt内容如下广工实验十三典型场景int a; --- if (a 5) then b a 1; --- while (x 0) do { x x - 1; } --- { int a; a 10; } int b; --- if (a 5) then { b 1; } else { b 0; }注意最后一例else分支在基础实验中不支持但老师可能故意放进来测试你的错误处理能力——此时应报SyntaxError: Expected then, got else而非崩溃。6.3 回归测试的三个黄金习惯每次修改代码后必须python test_runner.py test_cases.txt广工实验代码迭代频繁手动测试极易遗漏边界case。.gold文件用Git管理把test_*.gold加入.gitignore但保留test_cases.txt——这是你的“需求规格说明书”。错误信息必须可grep所有raise语句中的错误消息包含唯一关键词如Redeclaration、Undeclared方便grep -r Redeclaration *.py快速定位语义检查逻辑。我在广工带过三届实验课最稳的同学不是本文还有配套的精品资源点击获取
