简介一份面向编译原理课程实验二的语法分析程序设计与实现文档适合计算机专业学生及需要完成词法/语法分析综合实验的初学者。文档以算术表达式简化子集为分析对象给出原始BNF定义及改写后的LL(1)文法完整涵盖实验目的、程序流程图、预测分析表构建、C源程序实现以及RIGHT/ERROR输出等测试要求并附有LL1分析表填充和关键数据结构定义。资源为单个doc文档共1个文件压缩包大小127KB内容以可运行的LL(1)预测分析程序为核心。已有143人学习下载适合作为编译原理课设、实验报告撰写或复习参考。文档对预测分析过程、产生式结构体、分析栈与剩余串输出等关键细节均做了说明读者可以据此理解自顶向下语法分析方法并能直接参考或调试代码快速完成同类实验。1. 为什么都到实验二了还有人对着黑框里的一堆报错发呆语法分析程序设计与实现是几乎每门编译原理课里最劝退的一道坎。实验一写完词法分析器你手里好歹还有一堆token流可以打出来看到了实验二要面对的是文法、FIRST集合、FOLLOW集合、预测分析表、递归下降、LR(0)、SLR(1)这些名词程序跑起来不是死循环就是满屏syntax error连错在哪儿都看不出来。这个标题看起来只是个课程文档里的章节名实际背后是一整套「从文法到可运行分析器」的落地路径理解了这条路后面做语义分析、中间代码生成都是顺着同一套思路往下走。这篇文章不聊理论书上的定义直接说清楚你拿到题目后该怎么选方案、怎么把文法变成能跑的代码、参数的坑在哪以及不同写法之间差在哪里。2. 先把两类分析路线看清楚自顶向下与自底向上的取舍依据2.1 输入、输出与中间产物别急着写代码先画这条数据流语法分析器的输入是词法分析器产出的token流输出是两类东西一棵语法树或者至少是一个能证明输入合法的推导序列以及一个清晰可读的错误报告。很多同学一上来就对着文法写函数写着写着发现token流里混进了空白符、注释符或者词法接口返回的是字符串而不是类别编码整个分析器瞬间失控。我一般会先把接口定死token至少包含两个字段一个是类别编号用枚举常量一个是语义值数字的值或者标识符的字符串。语法分析器只认类别编号不直接碰源代码字符这是第一条纪律。常见做法是让词法分析器暴露一个函数比如next_token()每次返回一个token语法分析器内部再维护一个「当前token」的缓存叫做lookahead。所有判断都基于lookahead的类别编号去分支而不是去读词法缓冲区的原始内容。这样设计的好处是语法分析的逻辑完全与具体语言的关键字、标点符号的字面值解耦你想换成另一种词法实现语法层代码一行都不用改。另一个容易被忽略的中间产物是推导序列。如果你做的是自顶向下分析每次用哪个产生式展开记录下来就是最左推导自底向上分析每次规约哪个句柄倒过来就是最右推导。实验报告里要求的「分析过程输出」本质就是把这两个序列打印出来。很多人把分析器和语法树混成一件事其实在递归下降里你完全可以在匹配成功时不建树只打印产生式编号在LR分析器里也可以只打印移进/规约动作表。先跑通这个最小路径再谈建AST调试成本会低很多。2.2 手写递归下降与生成器选哪种看题目给了什么文法不看你喜欢什么自顶向下和自底向上不是风格问题是文法的约束条件决定的。递归下降要求文法不能有左递归最好还能通过提取公共因子避免回溯LR分析对文法的要求更宽很多左递归文法比如expression: expression term是天然适合LR的因为LR用移进规约的方式天然处理了左递归不会像递归下降那样无限递归栈溢出。如果你的题目给了一堆BNF里面还有大量左递归产生式你硬改成递归下降就得先做文法改写引入非终结符E之类这一步是纯机械操作但出错率极高。我的选型标准很朴素如果题目只要求识别一个表达式语言加减乘除、括号、赋值递归下降完全够用代码量小调试直观出问题看函数调用栈就能定位如果题目要求识别一个含有if-else、while、函数调用、声明列表的真实语言片段或者明确要求用LR(1)/SLR(1)方法那别头铁直接用Bison或Yacc这类生成器。生成器能自动处理冲突检测还会告诉你哪里有shift/reduce冲突帮你把文法里的二义性揪出来——这是手写分析器永远做不到的。参数和工具链上也有差别。递归下降是纯C/C代码跟着你的词法器一起编译链接毫无额外依赖生成器路线需要装bison、flex这类工具生成出来的.c文件再和你手写的词法接口拼到一起。很多人在这一步翻车bison生成的.c文件在Windows上用MinGW编译要加-D__USE_MINGW_ANSI_STDIO之类的宏定义或者flex生成的词法器在C工程里会报yywrap未定义。这些坑不是你的分析器写错了是工具链配置问题提前确认总没错。2.3 FIRST集合与FOLLOW集合是选路的地图算错一个就全盘走偏无论你走哪条路FIRST和FOLLOW集合都是绕不过去的地基。自顶向下构造预测分析表要用这两个集合决定在某个非终结符面对某个输入符号时选哪条产生式自底向上的SLR(1)自动机构造也要用FOLLOW集合来填规约项的lookahead。很多同学拿现成工具算这两个集合结果手算文法题时算错连带着把程序里的硬编码表也写错跑起来表现成「词法没问题、文法也简单但就是某些合法输入被误报」。建议的做法是先针对题目给的文法手工把FIRST和FOLLOW集合算一遍然后写一个很小的脚本去校验或者用已知正确的公开实现跑一遍对照。我给一个最小文法做示范E - E T | T T - T * F | F F - ( E ) | id这是典型的左递归算术表达式文法。先消除左递归得到E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id这时再算FIRST集合就不容易漏了。比如FIRST(E)里的εFOLLOW(E)里的和)这些细节就是后面判断「空产生式什么时候启用」的直接依据。如果题目允许你用LL(1)分析法那还需要把每个非终结符对每个终结符的预测表项逐一填出来冲突出现的地方就是文法还没改造干净。这些计算步骤别偷懒实验报告里这部分占了大量分值而且它直接决定了你的代码里查表逻辑怎么设计。3. 手写递归下降分析器从文法到可运行代码的全过程3.1 先做文法改写消除左递归与提取公共因子这一步决定后面少改多少代码递归下降要求每个非终结符对应一个函数函数主体按产生式的右部顺序匹配终结符或调用其他非终结符。如果文法里有左递归比如E - E T函数parse_E的第一行就去调用parse_E无限循环程序直接栈溢出。所以第一步是改写文法上面那个算术表达式文法改写后的结果就可以直接用。提取公共因子的场景也很典型比如statement - if (expr) stmt | if (expr) stmt else stmt两个产生式前缀完全相同直接写函数就会出现不确定选哪条的情况。改写成statement - if (expr) stmt else_part把公共前缀提出来else_part允许为空问题就解决了。改写文法最重要的是保持语言不变就是新旧文法接受的语言集合必须等价。你别把运算符的结合性改反了——消除左递归后E - T E | ε表达的是左结合因为递归发生在号右边对应的是外层如果你改成E - T E那表达式的含义就变成了右结合234会解析成2(34)虽然结果数值一样但语义上错了到了实验三语义分析阶段就会埋雷。做完改写我习惯先把几个典型输入比如ididid、id(idid)用手推导一遍确认推导序列符合预期再开始写代码。3.2 核心代码框架match、next_token、parse_E三个函数的写法与参数含义下面给一个最精简的递归下降分析器骨架词法接口假定为get_token()返回一个Token结构体字段type是枚举类型编号value是整数值或字符串指针。为节省篇幅我用一个简化的枚举常量示例实际项目中你按自己实验一的定义替换即可。#include stdio.h #include stdlib.h // 假定这是实验一里定义的token类别 enum TokenType { TOKEN_ID, TOKEN_NUM, TOKEN_PLUS, TOKEN_MUL, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_ASSIGN, TOKEN_SEMI, TOKEN_EOF }; typedef struct { int type; int value; // 数字的值或标识符的符号表下标 char *lexeme; // 原始字符串调试用 } Token; // 词法分析器接口每次返回下一个token extern Token get_token(void); // 全局当前token作为向前看符号 static Token lookahead; // 错误计数超过阈值可以提前终止 static int error_count 0; static void next_token(void) { lookahead get_token(); } static void report_error(const char *msg) { fprintf(stderr, syntax error: %s, near %s\n, msg, lookahead.lexeme); error_count; } // match函数期望一个指定类型匹配则消费否则报错 static void match(int expected) { if (lookahead.type expected) { next_token(); } else { report_error(unexpected token); // 这里不做恢复后续函数会继续用当前token判断 } }这段代码里lookahead这个全局变量是整个分析器的状态核心所有parse函数读取它做分支判断。match函数是唯一的token消费入口你只要保证所有终结符都通过match去消费就不会出现token流错位的问题。error_count是错误恢复的基础参数你可以设定一个上限比如超过10个错误就终止分析避免错误级联导致程序输出几千行无效报错。接下来是表达式文法对应的三个解析函数。文法规则是E - T EE - T E | εT - F TT - * F T | εF - ( E ) | id。注意这里的T和E每个对应一个函数连空产生式也要写成一个分支static void parse_E(void); static void parse_E_prime(void); static void parse_T(void); static void parse_T_prime(void); static void parse_F(void); static void parse_E(void) { // E - T E parse_T(); parse_E_prime(); } static void parse_E_prime(void) { // E - T E | ε if (lookahead.type TOKEN_PLUS) { match(TOKEN_PLUS); parse_T(); parse_E_prime(); // 递归调用处理连续加号 } // 否则产生式选择空串直接返回 } static void parse_T(void) { // T - F T parse_F(); parse_T_prime(); } static void parse_T_prime(void) { // T - * F T | ε if (lookahead.type TOKEN_MUL) { match(TOKEN_MUL); parse_F(); parse_T_prime(); } } static void parse_F(void) { // F - ( E ) | id if (lookahead.type TOKEN_LPAREN) { match(TOKEN_LPAREN); parse_E(); match(TOKEN_RPAREN); } else if (lookahead.type TOKEN_ID) { match(TOKEN_ID); } else { report_error(expected factor); } }逻辑说明整个分析过程是对输入串的最左推导模拟parse_E调用parse_Tparse_T调用parse_F遇到数字或括号就匹配终结符加号和乘号分别由E和T函数处理递归的写法天然支持任意长度的运算链。这个结构的巧妙之处在于E的递归调用产生的是循环效果但不用写循环语句回溯栈由函数调用栈自然承载。参数说明如果你要支持减法、除法只需增加对应的终结符类型和分支如果题目要求负号一元减需要给F增加一个分支match(TOKEN_MINUS)后接parse_F。但有一个关键参数你必须注意parse_E_prime里只有遇到PLUS才匹配遇到别的符号就返回这意味着如果输入是id id这种缺运算符的表达式分析会在parse_E_prime直接返回后由更高层去发现token没消费完。所以你的入口函数在parse_E之后必须检查lookahead.type TOKEN_EOF否则一个id 的错误输入也可能被误判为合法。3.3 三个必调的参数前瞻符号、错误上限、恢复点第一个是向前看符号的数量。上面这个文法只用了一个lookahead属于LL(1)。如果题目给出的语言无法在1个前瞻符号下做决定比如C语言的类型声明和表达式语句冲突就必须增加前瞻或者改写文法。在递归下降里增加前瞻的写法是再提前拿一个token缓存起来比如lookahead2分支判断时两个联合判断代码复杂度会明显上升。我的建议是优先改文法而不是加前瞻因为前瞻数量一多出错的组合呈指数级增长。第二个是错误计数上限。error_count这个变量不只是用来统计它应该参与控制流程。常见做法是在每次report_error后检查error_count超过比如5次就直接exit(1)因为此时已经基本确定输入不合法继续跑只会浪费时间和打出一堆不可信的报错。有的同学觉得多报几个错显得「分析器很努力」实际上老师在验收时看到满屏报错反而会怀疑你的错误恢复逻辑没做。第三个是错误恢复点。最简单的panic mode是当match失败时跳过当前token直到遇到一个同步符号通常是分号或右括号再继续分析。这个同步符号集合怎么选直觉上是选FOLLOW集合里的符号。比如在分析语句时分号是同步点在分析表达式时右括号和分号都是同步点。代码实现就是在report_error后加一个while循环判断lookahead.type不在同步集合里就next_token。注意这会造成一些合法token被跳过但作为实验二的要求已经足够了你要是追求更高端的错误恢复参考最后一章的做法。4. 用生成器Bison/Yacc实现语法分析文件格式与联编细节4.1 生成器文件的三段式结构声明段、规则段、程序段各自写什么如果题目明确要求用Yacc/Bison或者文法里有很多左递归产生式让你改写得很痛苦直接用生成器是明智选择。一个.y文件由四段组成用%%分隔。第一段是声明段写%token定义、%left/%right优先级声明、头文件包含第二段是规则段写各非终结符的产生式每个产生式后面可以跟一段C动作代码第三段是程序段写主函数、词法分析器的调用、错误处理函数yyerror等。一个典型计算器语法文件的声明段长这样%{ #include stdio.h #include stdlib.h int yylex(void); void yyerror(const char *s); %} %token TOKEN_NUM %token TOKEN_ID %left TOKEN_PLUS %left TOKEN_MUL %%%left声明运算符的结合性和优先级是很关键的一个参数。这里的顺序是越靠下的声明优先级越高TOKEN_MUL写在TOKEN_PLUS的下面所以乘法的优先级高于加法。同一行的%left表示左结合。如果你的文法里还有取负号这种一元运算符需要写%right或者用%prec指令指定一个虚拟token来标记优先级否则容易出现一元负号和二元减法的冲突。规则段的写法相比手写递归下降最大的区别是产生式直接写不需要手动消除左递归。因为Bison生成的是LR分析器天然支持左递归。比如算术表达式可以直接写expr: expr TOKEN_PLUS term { $$ $1 $3; } | term { $$ $1; } ; term: term TOKEN_MUL factor { $$ $1 * $3; } | factor { $$ $1; } ; factor: TOKEN_NUM { $$ $1; } | TOKEN_LPAREN expr TOKEN_RPAREN { $$ $2; } ;注意每一个产生式后面的{ $$ ...; }是语义动作$$表示这条规则归约后得到的值$1、$3表示引用右部第1个、第3个符号的值。这里的值类型由声明段的%union和%type指令决定。如果只做语法分析不建AST你可以把这些动作留空或者只打印一条规约信息一旦要建语法树就在动作里创建节点、把子节点指针用$$传上去。4.2 生成、编译与联调的最小命令序列写完.y文件后下一步是生成C源码并编译。以Bison为例最小命令链是bison -d parser.y # 生成 parser.tab.c 和 parser.tab.h gcc -c parser.tab.c -o parser.tab.o gcc -c lexer.c -o lexer.o # 自己实现的词法函数 gcc parser.tab.o lexer.o -o parser-d参数要求生成头文件parser.tab.h里面定义了每个token的编号宏词法分析器必须包含这个头文件并返回与之一致的宏值。比如说你在.y里声明了%token TOKEN_NUMBison就会在parser.tab.h里定义#define TOKEN_NUM 258之类的宏词法函数返回这个宏值语法层的匹配才能对上。不包含头文件的典型症状是编译没问题运行时报warning或者所有token被配成0导致永远走第一条产生式。联调时最容易踩的坑是yylex函数和yyparse函数的交互。yyparse是Bison生成的入口它每需要一个token就调用一次yylex()你的词法函数必须至少实现一个全局变量yytextBison的c语言模式下它是当前token的词素字符串。如果你的词法函数返回数字类型时还应该把数字值赋给yylval否则语义动作里$1取到的是垃圾值。我见过很多次这样的场景语法分析完全正确优先级也对但算出来的结果全是乱码原因就是词法器里忘了写yylval atoi(yytext)。4.3 冲突报告怎么看shift/reduce与reduce/reduce的处理策略Bison生成时会输出冲突警告比如State 12 conflicts: 1 shift/reduce。这两个词很有迷惑性很多同学以为程序跑起来没问题就可以忽略。实际上凡是报告里出现conflicts就说明你的文法是二义的或者有边界条件没写清楚Bison在冲突点默认选择了shift这不一定符合题目语义。比如经典的悬空else问题就是shift/reduce冲突Bison默认选择shift恰好匹配了「else就近匹配」的预期所以很多人误打误撞觉得没问题。但如果冲突发生在运算符优先级上比如一个文法既没有声明%left也没有写%prec那默认shift会让表达式变成右结合算出来的结果就是错的。处理冲突的标准步骤是先用bison -v生成.output文件里面能看到每个状态的详细项目集找到冲突的具体项目和lookahead集合再回到文法去找是哪两个产生式在同一个状态里相遇了。然后决定要么调整优先级声明要么改写文法消除冲突。reduce/reduce冲突更麻烦它通常表示两个产生式能规约到同一个非终结符的同一个状态原因是文法有重复路径往往是提取公共因子没做干净。我的经验是只要你看到reduce/reduce冲突基本可以断定文法设计有问题修文法比在代码里绕更快。5. 实验二避坑指南这些坑我踩过你直接绕开5.1 递归下降跑出无限递归栈溢出左递归没清理干净现象程序一跑就崩溃报错信息大量Stack overflow或者进程卡死不动CPU占用百分之百。这种问题在第一轮调试里出现频率最高。原因写递归下降时直接用了题目原文法里面包含E - E T这种左递归产生式parse_E函数第一行就调用parse_Tparse_T走完又回到parse_E形成一个永不退出的循环。解决先做文法改写——把左递归转成右递归引入新的非终结符E改写完再多读几遍确认没有漏改。另外一个隐藏入口是「间接左递归」比如A - B xB - A y这种也需要整体改写不能只看每条产生式本身。5.2 简单的合法表达式被判非法FIRST集合里的空串没处理现象输入id(id)能过但输入idid却报错或者反过来。原因大多出在parse_E_prime这类函数对空产生式的处理上当lookahead既不是也不是*时代表选择空串直接返回。可如果你的判断条件写成了if (lookahead.type TOKEN_PLUS) { ... } else { report_error(...); }那就把合法的结束情况也当成错误了。解决先手工列出每个非终结符的FIRST集合看看ε在不在里面然后检查代码里对应的函数是不是「遇到不在FIRST集中的token就静默返回」。注意别把错误分支和空串分支混在一起写至少要在注释里区分这两种情况。5.3 匹配完所有token后没有检查EOF非法输入漏判现象输入idid然后后面随便黏一个非法字符比如idid分析器居然报告成功。原因入口函数只调用了parse_E匹配完E对应的token就返回了后面的字符根本没人管。解决在入口函数里parse_E()之后再match(TOKEN_EOF)确保整个token流被完整消费。这招虽然简单却是验收时最容易被扣分的地方因为测试用例里往往会混入这类「前缀合法、整体非法」的输入。另一个相关习惯是在match里对TOKEN_EOF也要做检查避免分析器越过缓冲区末尾继续读。5.4 Bison动作代码里$n引用错位导致语义值错乱现象语法分析全部通过程序输出结果不对比如12*3算出9而不是7。这跟优先级冲突一样会造成错误优先级行为。原因一种情况是%left声明顺序写反乘法写在加法上面导致乘法优先级反而低另一种情况是动作代码里$N数字写错比如expr: expr TOKEN_PLUS term动作里想引用第三个符号却写成了$2拿到的就是加号token对应的值而token本身的值类型往往是NULL或者0。解决先把所有动作里的$$打印出来调试用printf(%d\n, $1); 逐层追踪确认类型声明没问题的前提下检查$N下标是1开始计数的而不是0。Bison不对$N做类型检查写错下标编译照样过运行才炸这是最坑的地方。5.5 错误处理后状态机不同步连续报一堆假错误现象输入第一个错误时比如缺了一个分号程序报错后就开始乱套原本合法的后续语句也全被报错最后错误计数爆炸式增长。原因match失败后没有做任何恢复动作当前lookahead还停留在错误位置后续函数基于这个错误的token继续推导自然全线崩溃。解决加上panic mode恢复。给每个主要分析函数定义一个同步符号集合通常是分号、右括号、EOF在report_error之后循环跳过token直到遇到同步符号然后再回到正常的分析流程。注意同步之后要调用next_token把同步符号也消费掉否则会卡在同一个位置死循环。5.6 中文路径或文件名编码导致bison生成失败现象在Windows上把.y文件放在带中文或空格的路径下运行bison指令后生成的是乱码文件或者干脆提示无法创建文件。原因老版本bison对非ASCII路径支持很差flex同样有这个问题。解决把整个工作目录改成纯英文路径比如D:\compiler\lab2文件命名也别带空格。还有一个连带问题如果代码文件里用了中文字符串作为错误提示在MinGW编译时可能因为编码格式不对导致编译警告最好统一用英文提示或者代码文件用UTF-8 without BOM保存。6. 进阶技巧在语法分析的同时直接构建AST以及让错误恢复更体面到这里你已经能跑通一个语法分析器了。但实验二如果只满足于「判断合法/非法」和「打印推导序列」拿到高分很难因为你没跟后面的语义分析实验接上。我通常会建议在语法动作里直接构建抽象语法树AST。递归下降的写法是在每个parse函数里返回一个节点指针把子节点的指针拼成父节点Bison的写法就是我在4.1节里写的每个产生式的动作里用malloc建节点子节点指针赋给$1、$3这类占位符父节点通过$$传递。以四则运算表达式为例AST节点定义可以长这样typedef struct ASTNode { char op; // 运算符、*、n表示数字i表示id int value; // 数字节点的值 char *name; // id节点的名字 struct ASTNode *left; struct ASTNode *right; } ASTNode;在parse_E_prime里原来只是匹配加号后递归现在改成ASTNode *left parse_T(); if (lookahead.type TOKEN_PLUS) { match(TOKEN_PLUS); ASTNode *right parse_T(); ASTNode *node malloc(sizeof(ASTNode)); node-op ; node-left left; node-right right; // 还要接着处理 E 里的剩余部分这时的当前节点不是上面的node // 而是需要向下传递所以最好把parse_E_prime的参数改成传入左子树 }这里有个编程细节因为E是递归调用递归处理剩余的加号链时新建的加号节点要把之前已构建的左子树作为left当前解析出来的term作为right。换句话说parse_E_prime的签名应该改成parse_E_prime(ASTNode *left_so_far)返回值是处理完后续所有加号的最终根节点。你如果沿用无参数的版本就会丢掉中间节点最后建出的树是扁平的而不是左子树嵌套的形态。错误恢复方面除了同步符号恢复你还可以做第二个级别的设计记录错误发生的位置行号列号和期望的token集合。这部分做好了实验报告的「错误处理机制」栏目就能写得比别人厚实。做法是在match失败时除了打印unexpected token再遍历一个预定义的「期望集合」把当前状态下合法期望的所有token类型列出来拼进报错信息里比如在表达式开头期望的是数字或左括号。最后说一个我自己的习惯每次写完分析器我除了跑老师给的测试样例还会专门写一个生成合法/非法输入的小脚本合法与非法各备二十来条把边界情况覆盖一下——空输入、只有一个数字、嵌套括号十层、连续的加号、运算符后缺操作数、表达式后跟垃圾字符。这些测试看着不起眼但它们帮我挡下了至少一半以上的验收翻车。走到这一步你会发现语法分析的设计与实现真正考验的是「把一棵树从文字里长出来」的思维方式代码本身倒不是瓶颈。希望这篇笔记能帮你把实验二这关过得顺利一些。本文还有配套的精品资源点击获取
