简介本资源是广东工业大学编译原理课程配套实验项目面向计算机专业本科生及编译技术初学者聚焦PL/0教学编译器的深度改造实践。实验要求在原PL/0基础上扩充保留字ELSE、FOR、TO、DOWNTO、RETURN、新增复合赋值与自增运算符、-、、--并实现ELSE子句语法与语义支持同时将不等号由#统一改为切实锻炼词法分析、语法扩展与语义处理能力。压缩包共24个文件含4个核心源码文件.cpp、.h、1个实验报告文档.doc、2个可执行程序.exe及调试相关文件.pdb、.obj、.ilk等整体644KB结构完整便于编译调试与代码比对。已有789人学习下载提供可直接运行的修改版PL/0工程含.dsw/.dsp工程文件、测试用例及清晰目录组织助读者快速理解教学编译器架构、掌握语法扩展关键路径与常见排错要点。1. PL/0 编译器为什么一个只有 22 个保留字的玩具语言能卡住 90% 的编译原理初学者你写完词法分析以为过了最难一关结果语法分析器一跑ELSE总是报错——不是“unexpected token”就是“shift/reduce conflict”手动画完 LL(1) 分析表发现ELSE和END在同一列里撞车更玄学的是把ELSE前面的IF多加一对括号错误反而消失了……这不是你代码写错了而是 PL/0 这个被教科书反复引用的“教学用编译器”从设计第一天起就把悬空 elsedangling else问题当成了默认行为来建模。它不解决歧义它直接定义歧义——用一套精巧但反直觉的文法约束让ELSE必须紧贴最近未配对的IF且禁止嵌套IF-ELSE中出现无ELSE的中间分支。广工这份《编译原理实验》资源之所以值得深挖正因为它没给你封装好的 parser generator而是逼你亲手在递归下降框架里硬编码condition → expression (relop expression)?、手动维护level和dx栈、在gen函数里一行行填入四元式操作码。这不是为了让你“会做实验”而是让你在ELSE报错的第 7 次重试中突然看清所谓“语法正确”从来不是字符串匹配而是符号栈与语义动作在某个时刻的精确咬合。2. 保留字机制为什么 PL/0 只有 22 个关键字却要单独建一张静态哈希表而非用 if-else 链PL/0 的保留字列表看似极简BEGIN,END,IF,THEN,ELSE,WHILE,DO,CALL,CONST,VAR,PROCEDURE,ODD,WRITE,READ,PLUS,MINUS,TIMES,SLASH,EQL,NEQ,LSS,LEQ,GTR,GEQ—— 实际共 24 个但教学实现常合并ODD与NOT、或剔除ODD后剩 22 个。关键不在数量而在它们的双重身份既是词法单元token又是语法驱动信号grammar trigger。比如IF出现时词法分析器必须立刻返回SYM_IF类型而语法分析器收到该符号后必须无条件进入condition_statement()分支并同步检查后续是否为THEN。若用链式if (s IF) return SYM_IF; else if (s THEN) ...在 C 风格实现中虽可行但存在三处硬伤一是字符串比较开销随保留字数线性增长22 次strcmp二是无法做编译期校验比如拼错BEGN不报错三是破坏了“符号即指令”的抽象——SYM_IF应该像汇编助记符一样直接映射到语义动作入口。2.1 静态哈希表用 32 位整数实现 O(1) 查找广工实验采用的经典方案是预计算每个保留字的哈希值存入固定大小数组冲突时用线性探测// symtab.h: 保留字哈希表定义 #define KW_HASH_SIZE 32 typedef struct { char *word; int sym; } keyword_t; static const keyword_t kw_table[KW_HASH_SIZE] { {, SYM_NULL}, // 空槽 {IF, SYM_IF}, {THEN, SYM_THEN}, {ELSE, SYM_ELSE}, {BEGIN, SYM_BEGIN}, {END, SYM_END}, {WHILE, SYM_WHILE}, {DO, SYM_DO}, {CALL, SYM_CALL}, {CONST, SYM_CONST}, {VAR, SYM_VAR}, {PROCEDURE, SYM_PROCEDURE}, {ODD, SYM_ODD}, {WRITE, SYM_WRITE}, {READ, SYM_READ}, {PLUS, SYM_PLUS}, {MINUS, SYM_MINUS}, {TIMES, SYM_TIMES}, {SLASH, SYM_SLASH}, {EQL, SYM_EQL}, {NEQ, SYM_NEQ}, {LSS, SYM_LSS}, {LEQ, SYM_LEQ}, {GTR, SYM_GTR}, {GEQ, SYM_GEQ}, // 其余槽位填 };提示哈希函数通常取hash (s[0] * 31 s[1]) % KW_HASH_SIZE但 PL/0 实现中更常见的是直接按字面量查表——因为保留字集合完全静态无需运行时哈希计算。上述数组本质是“带键名的枚举映射”。2.2 词法分析器如何联动getch()→getsym()→sym全局变量真正的机制闭环发生在getsym()函数中。它不返回字符串而是修改全局sym当前符号类型、id标识符名、num数字值三个变量// scanner.c void getsym() { int i; skip_white(); if (isdigit(ch)) { num 0; while (isdigit(ch)) { num num * 10 (ch - 0); getch(); } sym SYM_NUMBER; } else if (isalpha(ch)) { i 0; while (isalnum(ch) i ID_MAX_LEN) { id[i] ch; getch(); } id[i] \0; // 关键查保留字表 sym lookup_keyword(id); if (sym SYM_NULL) { sym SYM_IDENTIFIER; // 未命中则为普通标识符 } } else { // 处理运算符和分隔符 switch(ch) { case : sym SYM_PLUS; getch(); break; case -: sym SYM_MINUS; getch(); break; case *: sym SYM_TIMES; getch(); break; case /: sym SYM_SLASH; getch(); break; case : getch(); sym (ch ) ? SYM_EQL : SYM_ASSIGN; break; case : getch(); sym (ch ) ? SYM_LEQ : (ch ) ? SYM_NEQ : SYM_LSS; if (ch ! ) getch(); break; // ... 其他 } } }这段代码揭示了一个常被忽略的设计动机sym是语法分析器的唯一输入源。parse_program()不关心id是什么只根据sym SYM_IF就调用parse_if_statement()parse_if_statement()内部再调用getsym()获取下一个符号形成“符号流驱动”的控制流。这种解耦让语法分析器彻底摆脱字符串处理专注文法规则——而这正是编译原理课想让你建立的第一层心智模型词法层输出符号语法层消费符号二者通过sym变量契约耦合。2.3 为什么不能用 C map 或 Python dict——教学实现的底层约束有学生尝试用 STLmapstring, int替换静态表结果编译失败或运行异常。原因有三第一PL/0 实验要求纯 C 实现广工实验指导书明确限定gcc -stdc99禁用 C 标准库第二map构造需动态内存分配而 PL/0 运行时环境模拟的是裸机内存模型仅 500 行代码管理code[]和stack[]无 malloc/free第三也是最关键的一点教学目标是让你看见“符号如何变成控制流”。map封装了哈希、红黑树、迭代器等抽象你永远看不到SYM_IF如何在parse_if_statement()开头被if (sym SYM_IF)精确捕获。而静态表强制你写出#define SYM_IF 12并在switch(sym)中逐条列出分支——这恰恰复现了真实编译器前端中token_type枚举与parser_state转移的原始形态。3. ELSE 语句的语法建模为什么 PL/0 文法不写成if_stmt → IF condition THEN statement (ELSE statement)?这是最常引发崩溃的问题。初学者照着龙书《Compilers: Principles, Techniques, and Tools》的通用文法自然写出if-stmt :: IF condition THEN statement [ELSE statement]然后用递归下降实现def parse_if_stmt(): expect(SYM_IF) parse_condition() expect(SYM_THEN) parse_statement() if sym SYM_ELSE: getch() # consume ELSE parse_statement()但 PL/0 的标准文法N. Wirth 原始论文却是statement :: | IF condition THEN statement | IF condition THEN statement ELSE statement注意它没有[ELSE ...]的可选标记而是将IF-THEN和IF-THEN-ELSE视为两个互斥产生式。这意味着任何IF-THEN后面若紧跟ELSE必须属于同一个IF不能是外层IF的ELSE。这直接封死了悬空 else 的语法空间。3.1 悬空 else 的本质LL(1) 文法的 FIRST/FOLLOW 冲突我们来推导冲突根源。设文法为S → if C then S | if C then S else S | other对S → if C then SFIRST {if}对S → if C then S else SFIRST {if}两者 FIRST 集完全重叠LL(1) 分析器在看到if时无法决定选哪个产生式——这就是 shift/reduce conflict 的源头。PL/0 的解法是放弃 LL(1)改用递归下降 手动前瞻。其parse_if_statement()实际逻辑是void parse_if_statement() { expect(SYM_IF); parse_condition(); expect(SYM_THEN); parse_statement(); // 解析 THEN 后的 statement // 关键此处不检查 sym SYM_ELSE而是检查下一个符号 if (lookahead() SYM_ELSE) { // lookahead() 预读下一个符号不消耗 getch(); // 确认是 ELSE才真正消耗 parse_statement(); // 解析 ELSE 后的 statement } }lookahead()的实现通常是维护一个next_sym缓冲区int next_sym SYM_NULL; void getch() { if (next_sym ! SYM_NULL) { sym next_sym; next_sym SYM_NULL; } else { // 真正读取字符并转换为符号 ... } } int lookahead() { if (next_sym SYM_NULL) { next_sym sym; // 保存当前 sym getsym(); // 读取下一个 } return next_sym; }注意这个lookahead()不是现代 parser generator 的LA(k)而是手工维护的 1 符号预读缓冲。它让 PL/0 绕开了 LL(1) 的理论限制用工程手段实现了“看到ELSE才决定是否展开第二个statement”。3.2 语义动作如何绑定gen(LOD, level, addr)与gen(JPC, 0, 0)的时序陷阱ELSE不只是语法结构更是控制流跳转的锚点。PL/0 目标代码是四元式op, arg1, arg2, result其中JPCJump on Condition用于条件跳转。IF-THEN-ELSE的代码生成逻辑必须满足THEN分支执行完后必须无条件跳过ELSE分支ELSE分支入口地址必须在生成JPC时“留空”待ELSE分析完成后回填。广工实验的典型实现如下void parse_if_statement() { int else_addr, end_addr; expect(SYM_IF); parse_condition(); // 生成条件判断代码最后一条是 JPCresult 为占位符 expect(SYM_THEN); else_addr cx; // 记录 JPC 指令地址准备回填 gen(JPC, 0, 0); // 生成 JPC 0 0跳转地址待填 parse_statement(); // 解析 THEN 分支 if (lookahead() SYM_ELSE) { getch(); end_addr cx; // 记录 THEN 分支结束地址用于跳过 ELSE gen(JMP, 0, 0); // 生成无条件跳转跳过 ELSE 分支 // 回填 THEN 分支的 JPC 地址跳转到 ELSE 分支开头 code[else_addr].a cx; // 此时 cx 指向 ELSE 分支第一条指令 parse_statement(); // 解析 ELSE 分支 // 回填 JMP 地址跳转到整个 IF 语句之后 code[end_addr].a cx; } else { // 无 ELSEJPC 直接跳到 IF 语句之后 code[else_addr].a cx; } }这段代码暴露了教学编译器的核心难点指令地址是动态生成的而跳转目标必须在生成时未知。else_addr和end_addr是cxcode index的快照code[addr].a cx是典型的“回填backpatching”技术。没有这一步生成的代码要么跳转到错误位置要么因地址未初始化导致段错误——这也是为什么学生常看到“生成代码执行时栈溢出”实则是JPC跳到了code[0]导致无限循环。3.3 常见问题排查ELSE 相关的 4 类翻车现场现象 1IF x 0 THEN y : 1 ELSE y : 2编译通过但IF x 0 THEN IF y 0 THEN z : 1 ELSE z : 2报syntax error→ 原因ELSE被错误地绑定到外层IF而 PL/0 文法要求它必须绑定到最近的IF你的parse_if_statement()没有正确实现lookahead()导致在解析内层IF后sym已变为SYM_ELSE外层IF的expect(SYM_THEN)失败→ 解决确保lookahead()独立于sym且getch()调用前必须清空next_sym现象 2生成的代码中JPC指令的a字段始终为 0程序运行时逻辑恒为假→ 原因code[else_addr].a cx执行时cx未更新或else_addr记录的是错误指令索引如记成了gen(LOD...)而非gen(JPC...)→ 解决在gen(JPC,0,0)后立即else_addr cx-1因cx在gen内自增现象 3嵌套IF中ELSE执行后程序继续执行THEN分支末尾代码→ 原因JMP指令未生成或end_addr回填错误导致JMP跳转地址指向THEN分支内部而非外部→ 解决用调试器单步cx变化在gen(JMP,0,0)后检查cx值并确认code[end_addr].a被赋值为该值现象 4ELSE后跟BEGIN...END块时报unexpected BEGIN→ 原因parse_statement()函数未支持BEGIN作为statement的首符号PL/0 文法中statement产生式包含begin_statement → BEGIN statement_list END但你的实现可能只写了if_statement | assignment→ 解决检查parse_statement()的switch(sym)是否覆盖SYM_BEGIN并调用parse_compound_statement()4. 递归下降的栈帧管理为什么level和dx比cx更难理解却决定语义正确性PL/0 的运行时环境极度精简一个stack[STACK_SIZE]数组一个code[CODE_SIZE]指令数组以及三个核心指针spstack pointer、bpbase pointer、pcprogram counter。但真正承载作用域语义的是level嵌套深度和dxdata index当前过程的数据区偏移。当你写下VAR x, y;x的地址不是stack[0]而是stack[bp dx]其中dx从 3 开始因前 3 个位置固定存放return address,dynamic link,static link。4.1level如何编码作用域嵌套从main到proc p1再到proc p2PL/0 支持过程嵌套但不支持闭包。level是一个整数表示当前过程相对于主程序的嵌套层数主程序level 0主程序内定义的过程p1level 1p1内定义的过程p2level 2level不是运行时动态计算的而是在语法分析阶段由parse_procedure()递归调用时传入void parse_procedure(int current_level) { expect(SYM_PROCEDURE); strcpy(name, id); // 记录过程名 expect(SYM_IDENTIFIER); expect(SYM_SEMICOLON); // 过程体以新的 level 开始 enter_scope(current_level 1); // 创建新作用域level1 parse_block(current_level 1); // 解析过程体 exit_scope(); expect(SYM_SEMICOLON); }enter_scope(level)的作用是为该level初始化符号表条目并设置dx 3预留栈帧头部。这样p1中声明的VAR a地址为stack[bp 3]p2中声明的VAR b地址为stack[bp 3]——但它们的bp不同因为p2的bp指向p1的栈帧基址形成嵌套栈帧。4.2dx的累加机制为什么VAR x, y, z;会让z的地址是bp 5dx是一个过程级变量在parse_block()中维护void parse_block(int level) { int dx 3; // 数据区起始偏移3 个控制字 int tx 0; // 符号表索引 // 解析 CONST 声明 if (sym SYM_CONST) { do { expect(SYM_CONST); expect(SYM_IDENTIFIER); expect(SYM_ASSIGN); expect(SYM_NUMBER); // 将常量插入符号表不占用 dx } while (sym SYM_COMMA); expect(SYM_SEMICOLON); } // 解析 VAR 声明 if (sym SYM_VAR) { do { expect(SYM_VAR); expect(SYM_IDENTIFIER); // 插入符号表name, kindVAR, level, dx enter_var(name, level, dx); dx; // 每个 VAR 占用一个栈位置 } while (sym SYM_COMMA); expect(SYM_SEMICOLON); } // 解析 PROCEDURE 声明 while (sym SYM_PROCEDURE) { parse_procedure(level); // 递归传入 level1 } // 解析语句部分 expect(SYM_BEGIN); parse_statement_list(); expect(SYM_END); // 生成过程入口代码设置 bp, sp gen(INT, 0, dx); // 分配 dx 个局部变量空间 }关键点在于dx每声明一个VARdx自增 1因此VAR x, y, z;实际被拆成三次expect(SYM_IDENTIFIER)每次dx加 1。最终gen(INT,0,dx)生成的指令告诉运行时“为本过程分配dx个整数空间”。x地址 bp 3ybp 4zbp 5。这个看似简单的累加实则是静态作用域分配的全部秘密——没有堆分配没有垃圾回收所有变量地址在编译期确定。4.3level与dx如何协同生成LOD指令gen(LOD, level, dx)的参数含义LODLoad指令格式为LOD l, a含义是从层级l的栈帧中加载地址a处的值到栈顶。例如gen(LOD, 1, 3); // 加载 level1p1栈帧中偏移 3 的变量即 p1 的 x gen(LOD, 0, 5); // 加载 level0main栈帧中偏移 5 的变量main 的第 3 个 VARlevel参数决定了如何查找bp若l current_level直接stack[bp a]若l current_level需沿static link链向上跳转current_level - l层PL/0 运行时的static link是一个指针指向定义该过程的外层过程的bp。LOD指令的执行逻辑伪代码int find_base(int level) { int b bp; while (level current_level) { b stack[b 1]; // stack[b1] 存储 static link level; } return b; } // LOD l, a 执行 int base find_base(l); push(stack[base a]);这就是为什么level必须在编译期确定它决定了find_base()的跳转次数。若你在p2中访问p1的变量l1current_level2只需跳 1 次若访问main的变量l0需跳 2 次。dx则确保base a指向正确的变量槽位。5. 从 PL/0 到真实编译器为什么广工实验坚持手写递归下降而非用 Bison/Yacc这个问题的答案藏在 PL/0 的 22 个保留字、3 层嵌套、无指针无数组的“残缺”设计里。它不是为了教你如何构建工业级编译器而是为了让你亲手触摸语法分析与语义动作的耦合边界。当你在parse_if_statement()里为ELSE写出第 5 个if (lookahead() SYM_ELSE)你会突然意识到Yacc 生成的 LALR(1) 表不过是把这 5 个判断压缩进一个二维数组Bison 的%left声明本质是人工指定ELSE的优先级高于THEN从而解决悬空 else——而 PL/0 选择用lookahead()显式编码这一规则正是为了让你看见“优先级”如何落地为一行 C 代码。5.1 递归下降 vs. 自动生成控制流所有权的根本差异Yacc/Bison 的核心契约是语法分析器全权控制控制流语义动作是被动回调。你写if_stmt: IF condition THEN statement | IF condition THEN statement ELSE statement ;Yacc 生成的状态机自动处理IF后的移进/规约决策你只能在{ $$ ... }中填充语义值。但 PL/0 要求你写if (sym SYM_IF) { parse_if_statement(); } else if (sym SYM_BEGIN) { parse_compound_statement(); } else ...这里if-else链本身就是语法分析器的主循环。你拥有对sym的绝对控制权可以随时getch()、lookahead()、甚至ungetch()回退。这种“控制流即语法”的设计迫使你思考ELSE为什么必须出现在THEN之后因为parse_if_statement()的代码顺序决定了它VAR为什么不能出现在BEGIN之后因为parse_block()的if (sym SYM_VAR)分支在expect(SYM_BEGIN)之前。5.2 教学价值验证用三行代码测出你的理解深度真正的掌握不在于能否跑通实验而在于能否回答这三个问题如果我把parse_if_statement()中if (lookahead() SYM_ELSE)改成if (sym SYM_ELSE)会发生什么→ 答sym此时仍是SYM_THEN因expect(SYM_THEN)后未调用getch()条件恒假ELSE永远不被识别。gen(INT, 0, dx)中的dx如果在parse_procedure()中被重置为 0会发生什么→ 答所有过程的局部变量都挤在stack[bp0]相互覆盖x和y变成同一个内存地址。LOD 1, 3和LOD 0, 3生成的机器码完全相同运行时如何区分→ 答LOD指令本身不编码levellevel参数被编译进指令的l字段code[cx].l lfind_base()函数读取该字段决定跳转次数。这三个问题每一个都对应 PL/0 实验报告中最常被扣分的“原理阐述”部分。它们不考代码而考你是否把level、dx、lookahead()从变量名真正读成了运行时环境的拓扑结构。5.3 我的血泪经验从 PL/0 到 LLVM IR 的思维断层如何弥合我第一次用 LLVM 写后端时在if-then-else的IRBuilder::CreateCondBr上卡了三天。原因很简单PL/0 的JPC是“跳转到地址”而 LLVM 的BranchInst是“跳转到 BasicBlock 指针”。我下意识地试图计算BasicBlock*的内存地址直到导师指着 IR 输出说“br i1 %cond, label %then, label %else——then和else是标签名不是地址。” 那一刻我才懂PL/0 教我的不是“怎么编译”而是“抽象层次的切换成本”。JPC的a字段是物理地址抽象BasicBlock是控制流图抽象AST是语法树抽象——每一层抽象都封装了下一层的复杂性而 PL/0 强迫你站在最底层亲手把ELSE变成JPC的a字段。从那以后我每次写 parser都会先画一张表列出符号词法层输出语法层动作目标代码指令运行时效果ELSESYM_ELSEparse_statement()JMPJPC回填修改pc跳过THEN分支这张表让我不再把ELSE当作关键字而看作一个跨四层抽象的契约点词法承诺它存在语法承诺它绑定代码生成承诺它跳转运行时承诺它生效。希望帮到你。本文还有配套的精品资源点击获取
