JavaCC硬啃类C编译器：词法、语法、语义一站跑通

简介面向编译原理课程设计与编译器构造学习者提供一套基于Java与JavaCC实现的类C编译器完整方案。内容覆盖词法分析、语法分析递归下降、LL1算法验证、函数调用内存空间可视化等核心模块并配有课程设计报告与多组测试数据适合本科生完成同类课设时参考与复用。词法/语法分析结果准确Basic与Mixed测试均通过人工验证注释可经正则表达式去除不影响程序执行。压缩包共380个文件大小3.02MB主要包含Java源文件、JavaCC文法文件、编译后的class文件、测试样本及输出结果另有Python脚本与Shell脚本可自动执行并整理分析结果目录结构清晰。资源已有857人学习脚本支持自动输出各类分析结果并归档编译与输出文件便于直接运行验证是理解编译器前端设计与自动化测试流程的实用资料。1. 用 JavaCC 硬啃类C编译器词法、语法、语义一站跑通如果是第一次做编译原理课程设计很容易把时间耗在龙书上。龙书当然要读但读完和写出一个能跑的类C编译器之间还隔着“词法分析器怎么写、递归下降怎么落、语义动作挂在哪、结果怎么验证”四道坎。这份来自重庆理工大学课程设计的资源正好把这四道坎一次性趟平用 Java 和 JavaCC 生成词法器与语法器用 JJTree 生成 AST 节点语义分析输出 Basic 与 Mixed 两档结果函数调用栈还能以可视化形式展示。它不是一本说明书而是一套能直接编译运行的完整工程——很适合期末周需要类C编译器骨架的在校生也适合想把 JavaCC 生成器链路彻底看明白的 Java 工程师。我拆这套资源时最直接的感觉是javacc 和 jjtree 的配合方式如果没人点破很容易卡在“多了一个 .jj 文件”这一步上。下面按工程结构、核心实现、语义与可视化、踩坑、自动化验证的顺序把整条链路讲清楚。2. 工程结构与选型jj、jjt 文件在项目里各管哪一段2.1 为什么选 JavaCC 而不是 ANTLR同样是生成器ANTLR 在社区里呼声很高但它默认生成的是自顶向下的 ALL(*) 解析器工程里通常要引入一整套运行时依赖。相比之下JavaCC 更接近“大学编译器课设”的形态它把文法直接翻译成一组递归下降方法生成的代码你翻开就能看懂答辩时老师问“你的语法分析器怎么工作的”你可以指着方法调用链讲清楚而不是把黑匣子推给框架。从形式语言的角度看JavaCC 里的每条产生式就是上下文无关文法的一条规则非终结符之间的调用关系就是 FOLLOW 集合的体现。你在课设里需要先为类C语言写出文法再决定每个非终结符对应的 First 集合是否互不冲突——这个冲突检测过程资源里额外用 Python 写的 LL(1) 脚本就是用来兜底的。第 6 章会专门讲这个脚本怎么用。JavaCC 的入口文件是.jjJJTree 的入口文件是.jjt。两者关系是jjtree 读入.jjt生成 AST 节点类和一个新的.jj文件JavaCC 再读入这个.jj生成词法分析器TokenManager 系列类和语法分析器Parser 类。所以.jjt是上层文法描述.jj是中间产物真正的 Java 代码是最后生成的。2.2 构建顺序与常见目录布局我习惯把课设工程按下面这种结构组织便于把生成物、手写代码和输出结果分开compiler/ ├── hashes.sha1 # 文件哈希指纹用于下载后校验 ├── script/ │ ├── build.sh # 一键构建 │ └── run_all.sh # 一键跑全部测试用例 ├── src/cn/edu/cqut/compiler/ │ ├── CCompiler.jjt # 类C文法 AST 标注 │ ├── parser/ # javacc 从 .jj 生成的词法/语法分析器 │ ├── tree/ # jjtree 生成的 AST 节点 │ ├── semantic/ # 语法制导翻译与符号表 │ └── runtime/ # 函数调用栈模拟与可视化 └── samples/ ├── basic.c # 基础语句测试用例 └── mixed.c # 混合语句测试用例这里的 CCompiler.jjt 是源头文件。构建时严格按下面顺序执行cd src/cn/edu/cqut/compiler # 第 1 步jjtree 读 .jjt生成 AST 节点类 CCompiler.jj jjtree CCompiler.jjt # 第 2 步javacc 读 .jj生成词法分析器与递归下降语法分析器 javacc CCompiler.jj # 第 3 步编译全部 Java 文件统一输出到 bin 目录 cd ../../.. find src -name *.java sources.txt javac -encoding UTF-8 -d bin sources.txt三个步骤的顺序不能乱。有人会把 javacc 和 jjtree 的顺序搞反结果拿着.jj文件直接喂给 jjtree报一堆“非法字符”的错误。第 1 步生成的是第 2 步的输入第 2 步生成的是第 3 步要编译的 Java 源码。第 2 章开头说到的哈希指纹在下载后值得先跑一遍。资源里附带了一串与文件一一对应的哈希值我一般用sha256sum逐文件核对确认拿到的版本和原始提交一致再开始构建。这一步能省掉后续很多“为什么我的报错和别人不一样”的排查时间。3. 核心实现三步走Token 定义、注释清洗与递归下降生成3.1 Token 定义javacc 里的正则和 Java 正则不是一回事词法分析器负责把源码切成 Token 流。在 JavaCC 里这一步写在.jjt文件的 options 和 TOKEN 块里。下面是一段典型的 Token 定义覆盖了类C语言最常用的一批单词options { LOOKAHEAD 2; // 语法分析器默认向前看 2 个 token UNICODE_INPUT false; // 避免 UTF-8 BOM 带来的首个 token 异常 } PARSER_BEGIN(CCompiler) package cn.edu.cqut.compiler.parser; import java.util.*; public class CCompiler { // 符号表等全局对象放在这里 } PARSER_END(CCompiler) SKIP : { | \t | \n | \r } TOKEN : { IF: if | ELSE: else | WHILE: while | RETURN: return | TYPE_INT: int | INT: ([0-9]) | ID: ([a-z,A-Z]) ([a-z,A-Z,0-9,_])* | ASSIGN: | PLUS: | MINUS: - | TIMES: * | DIV: / | LPAREN: ( | RPAREN: ) | LBRACE: { | RBRACE: } }参数说明LOOKAHEAD 2表示语法分析器在面临多个候选产生式时最多向前看两个 token 来做决定。默认值是 1遇到两个候选前缀一样时就会报错所以这里调成 2 是给变量声明和赋值语句这类“开头都是 ID”的情况留余量。注意[a-z,A-Z]是 JavaCC 自己的字符集合写法不是 Java 正则里的[a-zA-Z]。直接把 Java 正则复制进来会编译失败。关键字必须先于 ID 定义因为 JavaCC 的词法匹配规则是最长匹配优先长度相同时先定义者优先。这里if和ID模式长度一样如果把 ID 放前面if会被识别成标识符ID语法分析阶段就再也等不到 IF token 了。3.2 注释清洗不能无脑 replaceAll字符串里的//会被误伤资源说明里特别提了一句“注释通过正则表达式去除注释不影响整个程序”。这句话说起来容易做起来有个经典坑如果直接source.replaceAll(//.*, )字符串常量里的//也会被删掉。正确做法是先保护字符串字面量再剥离注释最后还原字符串。下面的方法是我在这类预处理中最常用的写法import java.util.regex.*; public static String stripComments(String src) { // 匹配 C 语言字符串字面量支持转义字符 Pattern STRING_LITERAL Pattern.compile( \(\\\\.|[^\\\\\])*\ ); // 匹配两种注释// 行注释 与 /* */ 块注释 Pattern COMMENT Pattern.compile(//[^\\n]*|/\\*.*?\\*/, Pattern.DOTALL); // 1) 把字符串字面量换成占位符防止注释正则误删其内部内容 Matcher strMatcher STRING_LITERAL.matcher(src); ListString literals new ArrayList(); StringBuffer tmp new StringBuffer(); while (strMatcher.find()) { strMatcher.appendReplacement(tmp, \u0000 literals.size() \u0000); literals.add(strMatcher.group()); } strMatcher.appendTail(tmp); // 2) 在保护后的文本上安全去除注释 String cleared COMMENT.matcher(tmp.toString()).replaceAll( ); // 3) 把占位符还原为原始字符串字面量 for (int i 0; i literals.size(); i) { cleared cleared.replace(\u0000 i \u0000, literals.get(i)); } return cleared; }逻辑说明占位符用的是\u0000加数字这类控制字符在正常 C 源码里不会出现所以不会和真实内容冲突。替换注释时用空格而不是空字符串是为了避免int a/*注释*/b;这种写法被拼成int ab;。字符串正则里的\\\\.处理转义字符[^\\\\\]匹配普通字符这样a\b这种带引号的字符串也能完整保护。如果你不想在 Java 层做这套替换也可以在 JavaCC 的 SKIP 块里把注释当成空白忽略。但课程设计的要求是“用正则去除”所以预处理脚本或工具类里保留这个stripComments方法更贴合验收口径。3.3 从文法到递归下降类C语法结构怎么映射成方法词法分析完成后语法分析器要把 Token 流组织成 AST。递归下降的核心思想是每个非终结符对应一个方法方法内部按产生式右侧的顺序调用子非终结符方法或匹配终结符。类C语言的文法骨架大致是Program :: (ClassDecl)* ClassDecl :: class ID { (VarDecl | MethodDecl)* } MethodDecl :: Type ID ( ParamList ) Block Statement :: Block | IfStmt | WhileStmt | VarDecl | AssignStmt Expression :: Term (( | - ) Term)* Term :: Factor (( * | / ) Factor)* Factor :: INT | ID | ( Expression )把这段文法写进.jjt后JavaCC 会自动生成对应的解析方法。手写递归下降的人看到的骨架是这个形态void Statement() : {} { LOOKAHEAD(2) TYPE_INT ID ASSIGN Expression() SEMICOLON // 变量声明int i 1; | TYPE_INT ID SEMICOLON // 变量声明int i; | ID ASSIGN Expression() SEMICOLON // 赋值语句i 1 2; | IF LPAREN Expression() RPAREN Statement() | WHILE LPAREN Expression() RPAREN Statement() | LBRACE ( Statement() )* RBRACE }每个|分支就是一个候选产生式JavaCC 生成的解析器会依据前瞻 token 选择分支。这里 LOOKAHEAD(2) 的作用很明显int i 1;和int i;两个候选都是以TYPE_INT开头必须看到第二个 token 才能区分。第一个候选是 ID 后跟 ASSIGN第二个候选是 ID 后跟 SEMICOLON。很多课设翻车翻在表达式优先级上。如果只写一层Expression :: ID ((|-) ID)*那么a b * c会先做加再做乘结果完全错误。解决办法就是上面骨架里的分层Expression 只处理加减Term 处理乘除Factor 负责处理括号和原子项。层级越多优先级越明确这也是递归下降分析法最容易讲解、最容易人工验证的原因。4. Basic/Mixed 两档语义与函数调用栈可视化让编译器的行为看得见4.1 两档测试用例分开跑的意义Basic 与 Mixed 是这套课设里定义的两类测试集。Basic 面向基础语句变量声明、赋值、if、while、简单表达式目的是验证语法分析器和语义动作在最小功能集上不犯错。Mixed 则把函数调用、嵌套作用域、复杂表达式、字符串字面量混在一起模拟真实 C 程序里语句交替出现的场景。测试集覆盖范围人工验证重点Basicint 声明、赋值、if/while、加减乘除Token 序列顺序、AST 结构、作用域内变量收集Mixed函数调用、形参实参绑定、嵌套表达式、字符串注释混排调用栈帧数、参数传递方向、返回后的栈还原为什么要分两档因为课程设计要求“设计多组测试数据测试所实现编译器的功能评价所选工具和局限性”。Basic 全对说明核心机制没坏Mixed 全对说明系统在组合场景下依然稳定。人工验证的方法也很直接先手写出给定 C 代码的预期 Token 流、AST 和运行结果再和程序输出逐行比对。资源说明里提到“Mixed 结果人工验证全部准确无误”指的就是这个比对过程。4.2 语义动作与符号表属性文法怎么挂到产生式上语法分析只负责“句子合不合文法”语义分析要回答“合不合规矩”。比如变量有没有声明、赋值类型对不对、函数调用参数个数是否匹配。在递归下降框架里语义动作就是产生式右侧的 Java 代码块。这里的属性文法思想是每个非终结符可以携带继承属性由上下文传入和综合属性由子节点计算后返回。void VarDecl() : { String type; String name; Object value null; } { type Type() // 声明类型 name MatchID() // 变量名 [ ASSIGN value Expression() ] SEMICOLON { symbolTable.declare(name, value); } // 语义动作登记符号 }符号表就是一张作用域链每个{ }块开启一个新作用域离开块时销毁该层的记录。Basic 和 Mixed 的语义输出本质就是这张符号表在语句执行过程中的变化记录。做这个模块时我个人的经验是先别急着做类型检查优先保证变量声明、引用、作用域三条主线正确再补函数调用和返回值校验。4.3 函数调用栈可视化把运行时内存变化画出来资源里专门做了“函数调用时内存空间变化”的可视化。核心数据结构是一个模拟运行时的栈每个函数调用对应一个活动记录帧。下面这个类就是栈帧的最小实现class ActivityRecord { String funcName; // 当前函数名 MapString, Object locals; // 局部变量表 MapString, Object params; // 形参副本 ActivityRecord(String funcName) { this.funcName funcName; this.locals new HashMap(); this.params new HashMap(); } } public class RuntimeStack { private final DequeActivityRecord stack new ArrayDeque(); private final MapString, Object globals new HashMap(); public void enterFunction(String name, ListString formalParams, ListObject actualArgs) { ActivityRecord frame new ActivityRecord(name); for (int i 0; i formalParams.size(); i) { frame.locals.put(formalParams.get(i), actualArgs.get(i)); } stack.push(frame); // 入栈当前函数成为栈顶 } public void exitFunction() { stack.pop(); // 出栈函数返回后销毁帧 } public void declareVar(String name, Object value) { if (stack.isEmpty()) { globals.put(name, value); // 没有活动帧登记到全局 } else { stack.peek().locals.put(name, value); // 否则放入栈顶帧 } } }逻辑说明Deque的push和pop天然满足后进先出比Stack老类更轻量。enterFunction里把实参拷贝进当前帧的局部变量表模拟的是“形参是局部变量的备份”这一 C 语言运行时行为。declareVar判断当前是否有活动帧有则写入栈顶没有则写入全局符号表。这个分支逻辑本身就是作用域规则的正确体现。可视化时每个ActivityRecord渲染成一个矩形框框内列出函数名和局部变量名。调用enterFunction时往上堆一个框调用exitFunction时删掉最上面的框。人工验证方法是对main调用foo的样例预期栈内出现两个帧主函数帧在下面foo帧在上面foo返回后只剩主函数帧。这个验证做完内存可视化模块的正确性基本就坐实了。5. JavaCC 的避坑手记五个高发坑位与排错顺序5.1 五条真实踩坑记录坑一左递归导致 StackOverflowError。现象语法分析器一跑就栈溢出或者某个非终结符方法无限递归。原因文法里写了典型的左递归比如Expression :: Expression Term。JavaCC 生成的递归下降方法会先调用自身但此时尚未消费任何 token于是无限压栈。解决把左递归改成循环形式。常规做法是Expression :: Term (( | -) Term)*JavaCC 生成的方法会先解析一个 Term再循环匹配 “ Term” 或 “- Term”每轮循环都消费了 token递归终止条件自然满足。坑二Lookahead 不足导致选择冲突。现象运行时报 ParseException提示Encountered x后面跟着Wanted one of ...但手头代码看起来和文法完全一致。原因两个候选产生式前缀相同默认 LOOKAHEAD1 解析器无法区分。比如变量声明int i 1;和int i;第一个 token 都是int必须看第二个 token 才能决定走哪个分支。解决在当前产生式前加LOOKAHEAD(2)或者把最长的一个候选排在前面。JavaCC 会优先尝试先写的分支放一个更具体的候选可以规避冲突。坑三字符串字面量里的//被注释正则误删。现象输入printf(http://example.com);或String s a//b;预处理后字符串后半截消失。原因直接用replaceAll(//.*, )处理源码没有跳过字符串字面量。注释剥离开了字符串上下文就把 URL 和路径当成注释了。解决用第 3.2 节里的stripComments方法先把字符串字面量替换成占位符再剥离注释最后还原。这个坑也提示了一个设计原则注释处理不是纯文本替换必须知道当前是否处于字符串状态。坑四表达式优先级分层不对a b * c被算成(a b) * c。现象语法树生成成功语义输出的计算结果和数学预期不一致。原因文法只写了单层Expression :: ID (( | -) ID)*乘除和加减放在同一优先级。解决拆成 Expression、Term、Factor 三层。乘法产生式放在 Term 层加法和减法放在 Expression 层Factor 只负责原子项和括号。每往下一层优先级就高一级。坑五脚本在 Windows 上跑UTF-8 BOM 或默认编码导致首个 token 报错。现象同一个测试文件在 Linux 上正常在 Windows 上第一个字符解析失败或者中文注释乱码。原因文件带 UTF-8 BOMJavaCC 不认 BOM 头或者 javac 按平台默认编码GBK编译源码文件。解决脚本里统一加-encoding UTF-8并在读入测试文件后用正则把开头的 BOM 去掉。我一般会先看报错的行号是不是第 1 行第 0 列如果是基本就是 BOM 在作祟。5.2 排错顺序从 ParseException 往回走遇到语法分析报错别急着改文法。我的固定排查顺序是先定位异常信息里的行号和列号看是词法层报错还是语法层报错。词法层报错通常是 TokenMgrError问题出在字符不合法或编码语法层报错是 ParseException问题出在产生式分支选择。第二步是打印当前 Token 和期望 Token。在解析方法里临时加一行调试代码void DebugToken() : { Token current; } { current getToken(1); { System.err.println([DEBUG] next token current.image , kind current.kind); } }逻辑说明getToken(1)取的是当前位置后第一个 token不消费它。把它插到产生式开头就能看到解析器每走一步的视野内容。如果解析器停在了上而你期望它处理一个 ID问题基本出在前一个产生式的分支选择上。第三步检查左递归和 LOOKAHEAD这两类问题占了语法层错误的大半。最后再回头看注释预处理因为有些“莫名其妙的 token 错误”其实是注释剥完以后把两个单词拼在了一起。6. 用脚本固化验证批跑四类产物与 LL(1) 复核6.1 一键批跑四类产物课程设计要求脚本能自动执行 Basics 和 Mixed 的测试用例并把词法分析结果、语法分析结果、Basic 结果、Mixed 结果分别落盘。下面是我给这类课设配的一键脚本#!/bin/bash set -euo pipefail SRC./src BIN./bin SAMPLES./samples OUT./output rm -rf $BIN $OUT mkdir -p $BIN $OUT find $SRC -name *.java sources.txt javac -encoding UTF-8 -d $BIN sources.txt for case in Basic Mixed; do echo $case java -cp $BIN cn.edu.cqut.compiler.CCompiler -lex $SAMPLES/$case.c $OUT/$case.lex java -cp $BIN cn.edu.cqut.compiler.CCompiler -parse $SAMPLES/$case.c $OUT/$case.parse java -cp $BIN cn.edu.cqut.compiler.CCompiler -exec $SAMPLES/$case.c $OUT/$case.result done参数说明-lex触发词法分析输出-parse触发语法分析输出-exec执行语义分析并输出最终结果。这三类产物分开写文件便于课程设计报告里直接引用。find $SRC -name *.java替代**/*.java是为了兼容 bash 默认不开 globstar 的环境。如果测试过程需要交互式输入数值用管道喂给程序即可printf 10\n20\n | java -cp $BIN cn.edu.cqut.compiler.CCompiler -exec samples/basic.c这样就能覆盖“自动随过程输入数值”的验收点。产物全部落到output目录后源码目录保持干净答辩现场演示也不会手忙脚乱。6.2 用 Python 复核文法是否为 LL(1)资源里额外用 Python 写了一套 LL(1) 算法验证教材上的例子。这套脚本的价值在于递归下降分析的前提是文法满足 LL(1)但人肉眼判断 First 集合冲突很容易漏。脚本做的事就是自动计算 First 集合并检查同一非终结符的多个候选之间是否存在交集def compute_first(symbol, productions, memoNone): if memo is None: memo {} if symbol in memo: return memo[symbol] if symbol not in productions: # 终结符的 First 集合就是它自己 memo[symbol] {symbol} return memo[symbol] result set() for rhs in productions[symbol]: if rhs [eps]: # 空产生式直接贡献 epsilon result.add(eps) continue for prod_sym in rhs: f compute_first(prod_sym, productions, memo) result.update(f - {eps}) if eps not in f: break else: result.add(eps) memo[symbol] result return result逻辑说明这个函数递归计算每个非终结符的 First 集合memo做记忆化避免重复计算。eps表示空串产生式右侧逐个符号求 First一旦某个符号的 First 里没有 epsilon后续符号就无需继续。最终如果同一个非终结符的两个候选的 First 集合有交集文法就不是 LL(1)JavaCC 就需要更高的 LOOKAHEAD 或改写文法。我在最初拿到这套资源时图快没跑哈希校验就照着一份改过的 Parser.jj 调试被一个隐藏的 token 冲突耗掉两个多小时。从那以后我每次拿到别人的编译器代码第一件事就是把 jj、jjt、java 三类文件先备份一份再按 samples 里的用例逐一核对四类产物最后才动手改自己的功能。希望这个习惯和这整套验证流程也能帮你少走一遍我走过的弯路。本文还有配套的精品资源点击获取