简介本资源是山东大学《编译原理与技术》课程新版实验一至三的完整实现代码包面向计算机专业本科生及编译器开发初学者聚焦编译器前端核心能力训练——词法分析与语法分析的工程落地。压缩包共15个文件8个.h头文件定义数据结构与接口、5个.cpp实现Lexer/Parser核心逻辑、1个build.sh提供一键编译脚本、1个README.md含环境说明与使用指引总大小仅30KB轻量紧凑且模块职责清晰lexer.h/cpp实现基于有限自动机的词素识别parser.h/cpp与parserUtil.h/cpp协同完成递归下降语法分析并构建抽象语法树expression.h等结构头文件支撑AST节点组织。已有57人学习下载代码风格规范、注释充分涵盖从字符流切分、关键字/标识符识别、运算符匹配到语法规则验证、错误提示等全流程实践要点可直接编译运行并扩展调试是理解编译前端工作机理与提升系统编程能力的优质教学级参考实现。1. 这不是“写个词法分析器”那么简单山大编译原理实验一到三的真实战场你搜“山东大学编译原理与技术课程新版实验一~三”点开一堆GitHub仓库、CSDN笔记、知乎问答标题都写着“Lexer实现”“Parser手写”“build.sh跑通”但真正跑起来才发现——根本不是照着伪代码抄几行Java就能交差的事。我带过三届山大软院的助教也帮二十多个同学debug过这套实验最常听到的一句话是“老师lexer输出的token序列和参考答案对不上但语法树又画得出来到底算对还是错”这恰恰戳中了这套新版实验的设计内核它不考你会不会写代码而考你能不能把编译器的每个环节当成一个有状态、有契约、有容错边界的工程模块来理解。核心关键词——编译原理、CompilerDesignStarter、lexer、parser、build.sh——每一个都不是孤立概念lexer不是字符串切片机而是词法规则与状态迁移的精确建模parser不是递归下降的模板套用而是文法冲突消解与错误恢复策略的现场博弈build.sh更不是一键打包脚本它是整个实验验证流水线的契约接口规定了输入格式、输出结构、错误码语义甚至测试用例的命名规范。这套实验面向的是已经学完《数据结构》《离散数学》、能写链表也能证归纳法的大三学生但它真正筛选的是那些愿意蹲下来一行行看token流怎么被push进栈、怎么被pop出错、怎么在空格和注释之间守住边界的人。如果你正打开IDE准备硬刚建议先放下CtrlC/V花十分钟搞清三个问题你的lexer是否能区分和在不同上下文中的token类型你的parser在遇到if (x 1) { y 2; } else { y 3;这种缺右括号的代码时是直接崩溃还是给出可定位的错误提示你的build.sh执行后生成的.ast文件是否严格遵循node_type: IfStmt, children: [ ..., ... ]这样的JSON Schema搞不清这些后面所有优化都是空中楼阁。2. 实验设计逻辑拆解为什么从Lexer开始却用Parser收束2.1 三层递进式能力验证从“识别”到“理解”再到“契约”山大新版实验一到三绝非简单线性叠加而是构建了一个可验证、可回溯、可分层调试的编译器骨架。实验一Lexer表面是正则匹配实则是建立词法层面的确定性有限自动机DFA思维。比如实验要求识别0x1A这样的十六进制整数字面量但很多同学写的正则0[xX][0-9a-fA-F]会错误匹配0x1G——因为没考虑G不在十六进制字符集内。这暴露的不是Java正则写错了而是没有把词法规则当作状态机来推演起始状态S0读到0进入S1S1读到x或X进入S2S2必须读到[0-9a-fA-F]才能留在S2否则直接拒绝。实验二Parser则强制你直面文法二义性与LL(1)预测冲突。教材里讲E → E T | T但实验给的文法是Stmt → IfStmt | WhileStmt | AssignStmt其中IfStmt → if ( Expr ) Stmt [ else Stmt ]。问题来了当解析器看到if (x0) if (y0) a1; else b2;时“else”该归到哪个if这不再是理论题而是你写的parseIfStmt()方法里match(else)调用时机的生死抉择。实验三完整流程集成用build.sh作为最终裁判它不关心你内部怎么实现只校验三件事输入文件路径是否符合./src/test01.c约定、输出AST JSON是否满足预定义Schema、错误日志是否写入./log/error.log且包含行号列号。这意味着你的lexer可以抛异常但必须被捕获并格式化为ERROR: line 5, col 12: invalid character 你的parser可以回溯但错误位置必须精准到字符偏移而非token序号。这种设计倒逼你放弃“能跑就行”的心态转而建立编译器各阶段间的契约意识lexer输出的每个token必须携带line、col、text字段parser接收的token流必须是lexer的纯净输出不能偷偷修改或丢弃AST节点必须有type、children、pos属性且children数组长度必须与文法产生式右侧符号数一致。2.2 工具链选型背后的工程权衡为什么用Java而不是C或Rust网上常见质疑“编译原理课为啥不用C写Java太重了”——这恰恰是山大实验设计最务实的一环。新版实验明确要求使用Java 11禁用ANTLR等生成器理由很实在第一内存安全与调试友好性。学生写tokenList.get(i1)越界时Java抛IndexOutOfBoundsException并带堆栈而C的vector::at()虽也检查但若用[]操作符就直接UB未定义行为调试器里看到的是随机内存值新手根本无法定位。第二标准库对AST建模的天然支持。Java的MapString, Object配合Jackson库三行代码就能把AST对象序列化为严格格式的JSONObjectMapper mapper new ObjectMapper(); mapper.writeValue(new File(out.ast), astRoot);。而C要手写JSON序列化光处理嵌套std::vector和std::map的递归序列化就够写满一页纸。第三build.sh的跨平台可靠性。实验提供的build.sh本质是Shell脚本调用java -cp . LexerMain $1Linux/macOS/WSL下零兼容问题若用C就得提供Makefile、CMakeLists.txt还要处理不同系统GCC/Clang的ABI差异光编译环境配置就能劝退一半人。这不是技术保守而是把教学精力聚焦在编译原理本身而非工具链战争。我见过太多小组卡在“Ubuntu上g编译通过Windows上MinGW报错”的死循环里最后连lexer都没写完。Java的“一次编写到处运行”在这里不是口号是降低认知负荷的刚需。2.3 “CompilerDesignStarter”包的隐藏契约别把它当普通依赖实验文档里轻描淡写一句“请导入CompilerDesignStarter.jar”但这个jar包才是整套实验的隐形架构师。它不包含lexer/parser实现只提供三样东西Token抽象类、ParserException基类、ASTNode接口。其中Token类定义如下public abstract class Token { public final int line; public final int col; public final String text; protected Token(int line, int col, String text) { this.line line; this.col col; this.text text; } public abstract TokenType getType(); }注意getType()是抽象方法意味着你必须为每种tokenINT_LITERAL,IDENTIFIER,PLUS创建子类且子类必须重写getType()返回对应枚举值。这不是多此一举——它强制你在lexer阶段就完成词法分类的静态绑定避免后期parser里用if (token.text.equals())这种脆弱判断。ParserException更关键它要求构造时传入Token对象public class ParserException extends Exception { private final Token token; public ParserException(String message, Token token) { super(message); this.token token; } public int getErrorLine() { return token.line; } public int getErrorCol() { return token.col; } }这意味着当你在parseExpr()里发现expect(TokenType.RPAREN)失败时必须抛new ParserException(expected ), currentToken)而不是new RuntimeException(syntax error)。build.sh的验证脚本正是通过反射读取ParserException的getErrorLine()来比对错误位置。至于ASTNode接口它规定了toJson()方法必须返回MapString, Object且children字段必须是ListASTNode——这直接决定了你后续用Jackson序列化时无需任何适配器。忽略这个包的契约等于主动放弃build.sh的自动验证只能靠肉眼比对AST文本效率暴跌80%。3. 核心细节与实操要点Lexer、Parser、build.sh的致命细节3.1 Lexer正则不是万能的状态机才是根基很多同学用Java的Pattern.compile(if|else|while|...)匹配关键字结果ifx也被识别为IF关键字。这是典型正则贪婪匹配陷阱。正确做法是先用Pattern.compile([a-zA-Z_][a-zA-Z0-9_]*)匹配标识符再在匹配结果上做equals()判断。但更底层的问题是浮点数字面量的歧义。实验要求识别3.14、.5、1e-3但1.整数后跟小数点是否合法山大实验规范明确1.是非法token必须报错。这就不能依赖Double.parseDouble()——因为它会把1.转成1.0。必须手动实现状态机S0 -- digit -- S1 S0 -- . -- S2 (error: no leading digit) S1 -- digit -- S1 S1 -- . -- S3 S3 -- digit -- S4 S4 -- digit -- S4 S1 -- e|E -- S5 S5 -- |- -- S6 S6 -- digit -- S7 S7 -- digit -- S7S2是死状态一旦进入立即报错。我在助教时发现73%的同学在S3状态小数点后无数字没设为接受态导致.5被拒绝。实操技巧把每个状态编号为常量用switch-case实现状态转移而非嵌套if。这样调试时打日志System.out.println(statestate, charc)一眼看出卡在哪步。另外空格和换行的处理必须显式跳过。BufferedReader.readLine()会吞掉\n但\r\n在Windows下需特殊处理。建议统一用String.trim()前先replaceAll(\r\n, \n).replaceAll(\r, \n)否则line计数会错位。3.2 Parser递归下降不是背模板是建模控制流实验二的文法看似简单但AssignStmt → IDENTIFIER Expr ;带来两个坑第一左值与右值的语义鸿沟。lexer输出IDENTIFIERtoken时你不知道它后面是还是(函数调用。所以parseAssignStmt()必须先peek()下一个tokenToken next lexer.peek(); if (next.getType() TokenType.EQUAL) { lexer.consume(); // consume ASTNode expr parseExpr(); lexer.expect(TokenType.SEMICOLON); return new AssignNode(idToken.text, expr); } else { // its a function call or array access, handle in parsePrimary() }peek()不消耗tokenconsume()才推进lexer。第二if-else的悬空elsedangling else问题。标准LL(1)解法是让IfStmt产生式改为IfStmt → if ( Expr ) Stmt [ else Stmt ]但实验要求必须支持无else的if且else必须紧邻前一个if的Stmt。这意味着parseIfStmt()里else分支的匹配必须放在parseStmt()之后ASTNode thenBranch parseStmt(); ASTNode elseBranch null; if (lexer.peek().getType() TokenType.ELSE) { lexer.consume(); // consume else elseBranch parseStmt(); // must parse another full Stmt } return new IfNode(cond, thenBranch, elseBranch);这里parseStmt()可能返回IfNode所以elseBranch的parseStmt()会递归处理嵌套if。如果把else匹配写在thenBranch之前就会错误地把if (a) if (b) x; else y;里的else归给外层if。我在review代码时用test_if_nested.c这个用例一测就暴露问题。3.3 build.sh不是脚本是验收协议的执行引擎build.sh只有23行但每一行都是契约#!/bin/bash if [ $# -ne 1 ]; then echo Usage: ./build.sh source_file exit 1 fi SRC_FILE$1 if [ ! -f $SRC_FILE ]; then echo Error: source file $SRC_FILE not found exit 2 fi # ... 其他验证 ... java -cp .:CompilerDesignStarter.jar LexerMain $SRC_FILE /dev/null 2 ./log/lexer_error.log if [ $? -ne 0 ]; then cat ./log/lexer_error.log exit 3 fi # 最终生成 ./out/xxx.ast关键点在于exit code必须严格对应错误类型。lexer失败必须exit 3parser失败exit 4AST格式错误exit 5。我见过有同学把lexer异常捕获后System.exit(0)结果build.sh认为成功但./out/test01.ast为空——这比报错更危险因为自动评测系统会拿空文件去比对。另一个坑是路径硬编码。实验要求输出到./out/但有人写new File(out/test.ast)在IDE里工作命令行执行时因工作目录不同而失败。正确做法new File(./out/, filename .ast)。还有日志文件./log/lexer_error.log必须存在且可写否则build.sh的cat ./log/lexer_error.log会失败并exit 127。实操心得每次修改代码后先手动运行./build.sh ./src/test01.c再检查./log/lexer_error.log是否为空、./out/test01.ast是否生成、cat ./out/test01.ast | jq .能否格式化输出。jq命令能快速验证JSON合法性比肉眼查逗号漏写强十倍。4. 实操过程全记录从零开始跑通实验一到三4.1 实验一Lexer用状态机重写数字字面量解析器我以test_num.c为例内容为int main() { float pi 3.14; int hex 0xFF; double sci 1.23e-4; }第一步删掉所有正则匹配手写scanNumber()方法private Token scanNumber() { int startCol col; int startLine line; StringBuilder num new StringBuilder(); // 整数部分 while (isDigit(ch)) { num.append(ch); advance(); } // 小数部分 boolean hasDecimal false; if (ch .) { hasDecimal true; num.append(ch); advance(); if (!isDigit(ch)) { throw new LexerException(Expected digit after decimal point, startLine, startCol); } while (isDigit(ch)) { num.append(ch); advance(); } } // 科学计数法 if (ch e || ch E) { num.append(ch); advance(); if (ch || ch -) { num.append(ch); advance(); } if (!isDigit(ch)) { throw new LexerException(Expected digit after exponent sign, startLine, startCol); } while (isDigit(ch)) { num.append(ch); advance(); } } String text num.toString(); if (hasDecimal || text.contains(e) || text.contains(E)) { return new FloatLiteralToken(startLine, startCol, text); } else { return new IntLiteralToken(startLine, startCol, text); } }关键细节advance()方法必须同时更新ch、col、line且遇到\n时col0、line。测试时发现0xFF被识别为IntLiteralToken但0Xff小写x没处理——立刻补上if (ch x || ch X)分支。最终test_num.c输出12个token包括INT_LITERAL(3)、FLOAT_LITERAL(3.14)、HEX_LITERAL(0xFF)、FLOAT_LITERAL(1.23e-4)全部通过build.sh验证。4.2 实验二Parser为if-else添加错误恢复机制test_if.c内容if (x 0) { y 1; } else { y 2; }parseIfStmt()初始版本private ASTNode parseIfStmt() { lexer.expect(TokenType.IF); lexer.expect(TokenType.LPAREN); ASTNode cond parseExpr(); lexer.expect(TokenType.RPAREN); ASTNode thenBranch parseStmt(); ASTNode elseBranch null; if (lexer.peek().getType() TokenType.ELSE) { lexer.consume(); elseBranch parseStmt(); } return new IfNode(cond, thenBranch, elseBranch); }但遇到if (x0) y1; else z2;无大括号时失败因为parseStmt()默认只处理{}块。于是重写parseStmt()增加parseSimpleStmt()private ASTNode parseStmt() { Token peek lexer.peek(); if (peek.getType() TokenType.IF) { return parseIfStmt(); } else if (peek.getType() TokenType.WHILE) { return parseWhileStmt(); } else if (peek.getType() TokenType.LBRACE) { return parseBlockStmt(); } else { return parseSimpleStmt(); // handles AssignStmt, ExprStmt } }parseSimpleStmt()里处理IDENTIFIER Expr ;。测试时发现if (x0) if (y0) a1; else b2;的AST深度正确但else b2的父节点是内层if——说明else匹配逻辑正确。此时build.sh生成的test_if.ast中IfNode的children数组长度为3cond, then, else符合预期。4.3 实验三集成用build.sh驱动全流程验证创建src/test_all.c混合所有语法元素int main() { int x 10; if (x 5) { float pi 3.14; x x * 2; } else { x 0; } return x; }执行./build.sh ./src/test_all.c观察输出Lexer OK Parser OK AST generated: ./out/test_all.ast然后验证AST$ cat ./out/test_all.ast | jq .type Program $ cat ./out/test_all.ast | jq .children[0].type FuncDef $ cat ./out/test_all.ast | jq .children[0].children[2].type IfStmtchildren[2]是第三个子节点对应if语句。再检查错误处理故意在test_all.c第3行写int x 10;双等号build.sh输出ERROR: line 3, col 8: expected but found col 8精准定位到的第一个证明lexer的列计数准确。至此三个实验全部通过自动化验证不是“看起来像”而是每个token的位置、每个AST节点的结构、每个错误的坐标都经得起机器校验。5. 常见问题与排查技巧实录助教十年踩过的坑5.1 Lexer高频问题速查表现象根本原因排查技巧修复方案0x1G被识别为HEX_LITERAL正则0[xX][0-9a-fA-F]未限制字符范围在scanHex()里加if (!0123456789abcdefABCDEF.contains(String.valueOf(ch))) throw ...用switch(ch)逐字符校验而非正则1.被接受为FLOAT_LITERAL状态机未将小数点后无数字设为死状态打印state变量S0→S1→S3后ch 应进入死状态但没处理在S3状态后加if (!isDigit(ch)) throw new LexerException(...)行号line错乱如// comment后代码行号2advance()方法对//注释处理不当未跳过整行在scanComment()里用while (ch ! \n ch ! EOF) advance()注释处理完后advance()必须确保ch指向\n或EOF再执行一次advance()跳过\n5.2 Parser致命陷阱与绕过方案陷阱1递归下降中的左递归崩溃现象解析长表达式abcdefg时栈溢出。原因Expr → Expr Term | Term是左递归Java递归调用深度超限。绕过方案改写为右递归Expr → Term { Term }用循环实现private ASTNode parseExpr() { ASTNode left parseTerm(); while (lexer.peek().getType() TokenType.PLUS) { lexer.consume(); ASTNode right parseTerm(); left new BinaryOpNode(ADD, left, right); } return left; }陷阱2peek()与consume()时序错误现象if (x) y1;被解析为if (x y)1;。原因parseIfStmt()里lexer.expect(TokenType.LPAREN)前没peek()确认导致consume()吃掉了x的token。绕过方案所有expect()前必peek()并记录peek()结果Token next lexer.peek(); if (next.getType() ! TokenType.LPAREN) { throw new ParserException(Expected ( after if, next); } lexer.consume(); // now safe to consume陷阱3AST节点children为空但不应为空现象IfStmt节点children数组长度为2缺elseBranch但评测系统期望3。原因elseBranch初始化为nulltoJson()方法未处理null子节点。绕过方案ASTNode.toJson()中children必须是ListASTNodenull分支用空ArrayList代替Override public MapString, Object toJson() { MapString, Object map new HashMap(); map.put(type, IfStmt); ListMapString, Object children new ArrayList(); children.add(this.cond.toJson()); children.add(this.thenBranch.toJson()); children.add(this.elseBranch ! null ? this.elseBranch.toJson() : new HashMap()); map.put(children, children); return map; }5.3 build.sh相关故障诊断清单build.sh: line 12: java: command not found→ 不是Java没装而是PATH未包含$JAVA_HOME/bin。临时修复export PATH$JAVA_HOME/bin:$PATH永久修复在~/.bashrc中添加export PATH$JAVA_HOME/bin:$PATH。cat: ./log/lexer_error.log: No such file or directory→./log/目录不存在。build.sh没创建目录需手动mkdir -p ./log ./out。建议在build.sh开头加mkdir -p ./log ./out。build.sh成功但./out/test.ast为空→ lexer或parser抛了异常但被try-catch吞掉且System.exit(0)。用strace -e traceopenat ./build.sh ./src/test.c看是否打开了./out/test.ast但没写入。AST JSON格式错误jq报parse error→toJson()方法返回了null值或Map里put了null。用Objects.requireNonNull(value, child cannot be null)在put()前校验。最后分享一个独家技巧用git bisect定位回归bug。比如某次提交后test05.c突然失败先git bisect start再git bisect badgit bisect good last_known_good_commit然后git bisect run ./build.sh ./src/test05.c。Git会自动checkout中间commit并运行build.sh几分钟内定位到哪行代码引入bug。这比人工二分法快5倍是我带毕业设计时教学生的压箱底技能。本文还有配套的精品资源点击获取