企业官网建设流程全解析

简介：针对语法分析程序设计与实现的完整实验文档，适合编译原理课程学习者及需要完成类似实验的高校学生，可帮助掌握LL(1)分析法、预测分析表构建和语法分析程序整体调试流程。包内含1个Word文档，大小仅127KB，内容集中，便于直接阅读或打印对照。文档从实验目的入手，以算术表达式简化子集为分析对象，先给出BNF定义并将其改写为LL(1)文法，随后详细说明预测分析表的数据结构定义、核心类与全局变量的作用，以及C++源程序中分析栈和剩余串输出等关键函数的实现方式；针对输入串为合法句子或存在语法错误的情况，文档也给出了明确的输出设计、错误信息提示和测试用例安排，能够帮助读者将词法分析与语法分析衔接成完整程序。目前已有143人学习使用，对正在完成实验二或复习编译原理重点内容的学生具有实用参考价值。

1. 语法分析程序设计与实现：这场实验课真正卡人的三个点

刚送走词法分析实验，紧接着的“实验二——语法分析程序设计与实现”往往会在三处把人卡住：一是 First 与 Follow 集合算得不够细，构造预测分析表时冒出冲突；二是词法接口想当然，把 Token 当成黑匣子，排错时只能对着满屏打印数下标；三是完全不设计报错恢复，拿到一个故意写错的输入串，程序直接死循环或者只回一句“Error”。这三个点单拎出来都不难，叠在一次实验里就会让人反复翻车。

这个实验的目标并不复杂：给定一条上下文无关文法，把它写成可执行的程序，让程序对输入串判断是否符合文法，并把推导过程或语法树打印出来。它服务的对象很明确——在校正啃编译原理的学生，以及需要给内部 DSL 或配置文件写手写解析器、又不想一上来就接 ANTLR 这类大工具的工程师。做完这一轮，后面接 AST、符号表、中间代码的实验才能站得住脚。下面按“先定模型、再写代码、最后排错”的顺序，把整条路走一遍。

2. 先定文法模型：LL(1) 还是递归下降，决定了代码量和查错难度

2.1 为什么实验二通常不选 LR，而是落在 LL(1) 或递归下降

先说结论：主流编译原理课程的实验二，验收点基本固定在三件事——文法改造、First/Follow 计算、分析程序能正确处理合法与非法输入串。实现路线最稳的是在 LL(1) 表驱动和递归下降之间二选一。LR 家族不是不能做，而是对刚写完词法分析的学生来说，状态集构造和 action/goto 表的调试成本太高，实验课时通常撑不住。

LL(1) 表驱动的核心是维护一个栈和一张预测分析表，每一步根据栈顶符号和当前输入符号查表，决定是展开某个产生式还是报错。递归下降则把每个非终结符写成一个函数，函数体内手工安排“先匹配哪个终结符、再调用哪个子函数”，代码读起来几乎就是文法本身。从工作量看，LL(1) 要多写表结构和驱动循环，但冲突看得见；递归下降代码量少，遇到复杂分支时直接写 if-else，但左递归等问题要提前在文法层规避。

从调试体验看，这两种路线的差别更实际。递归下降运行时，函数调用栈本身就带着上下文，出错时能直接看出是哪层非终结符在处理哪个位置；LL(1) 表驱动则要自己打印栈内容、剩余输入和表项，心智负担重一点。我一般建议优先写递归下降，实验报告里也好解释：每个函数对应一条产生式，推导过程天然就是最左推导。

这里说的“程序设计实践”课程意义就在取舍：并不是 LL(1) 更接近真实编译器就一定更好，而是这个阶段你得调试得动它。选一个自己能一眼看穿行为的方案，比选一个理论上更完美的方案更重要。

2.2 消除左递归与提取左公因子：动手写代码前必须做的两个文法加工

LL(1) 和递归下降都不允许同一个非终结符以左递归形态出现在产生式右部开头。最经典的例子是教科书里的简单算术表达式：

E -> E + T | T

写成递归下降时，parse_E 的第一行就会调用 parse_E 自己，输入指针还没动，调用栈已经无限叠加，程序直接栈溢出。所以标准做法是把左递归转成右递归。用模板化写法：如果文法中有

A -> A α | β

等价改写成：

A -> β A' A' -> α A' | ε

对应到上面的算术表达式：

E -> T E' E' -> + T E' | ε

这里容易混的点是：改写后的 E' 不是新的运算优先级，它只是“跟在 E 之后的那段尾巴”。加号出现在 E' 产生式的开头，而不是嵌在中间，这正是为了满足 LL(1) 对“每个非终结符按当前输入符号唯一选择产生式”的要求。

另一个必修加工是提取左公因子。典型例子是条件语句：

if_stmt -> if ( E ) S | if ( E ) S else S

两个产生式都以if ( E ) S开头，在预测分析表里，if_stmt 行对应if这个终结符的格子会出现两个产生式，一个格子两个动作，这张表就不再是确定性的。提取公因子后：

if_stmt -> if ( E ) S else_part else_part -> else S | ε

注意 else_part 的空分支，它还会带来悬空 else 的经典二义性问题，但至少预测表不再冲突。做这两个加工时，我习惯先把原始文法抄在一张纸上，标出每个非终结符的出现位置，再动手改，比直接对着代码改可靠得多。

2.3 手算 First 与 Follow 的三个易错点，然后填预测分析表

First 与 Follow 的教科书定义不需要背，但要会用。对每个非终结符 X，First(X) 是 X 经过多步推导能推出的所有终结符开头；如果 X 能推出空串，ε 也属于 First(X)。Follow(X) 是所有句型中紧跟 X 之后的终结符集合，对开始符号，$ 默认属于 Follow。关键规则只有一条：当某个产生式右部能推空时，产生式左部非终结符的 Follow 要往后传递。

我见过多数同学算错，集中在三处。第一，把 ε 当成普通终结符写进了 Follow 集合，其实 Follow 里永远不应该出现 ε，它是给分析器“什么时候该走空分支”用的信号。第二，算E' -> + T E' | ε时，E' 的 Follow 必须并入 E 的 Follow，因为 E' 能推空，跟在 E' 后面的东西本质上就是跟在 E 后面的东西，这个传递漏掉，后面填表一定错。第三，构造预测分析表时，对每个产生式A -> α，要把 First(α) 里的每个终结符填入M[A, a]；如果 α 能推空，还要把 Follow(A) 里的每个终结符填入M[A, b]。这一步叫做“ε 传递”，最容易漏。

用表达式文法做例子：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

手算结果如下：

这张表填完，用“每个产生式右部的 First 填入，能推空则 Follow 也填”的规则，就能得到一张 5 行 4 列的预测分析表。如果你写的是表驱动分析器，这张表就是程序的灵魂；如果你写递归下降，这张表的作用变成验证——每个非终结符函数的分支选择必须和表里的内容一致。做完这步再编码，后面基本不会因为文法问题返工。

3. 把递归下降分析器写出来：从 Token 约定到错误恢复的可运行代码

3.1 先做一个简单的 Token 接口，别把词法层的脏活带进分析层

课程实验通常允许复用实验一的词法分析器，但两段代码拼到一起时，很多“语法分析 bug”其实是 Token 接口没定义好导致的。我给自己定的规矩是：语法分析器只认 Token 的 kind，不关心原始字符串长什么样。Token 类这样定义就够了：

class Token: __slots__ = ["kind", "value", "line", "col"] def __init__(self, kind, value, line, col): self.kind = kind # 符号类型，例如 "ID"、"INT"、"PLUS" self.value = value # 原始子串，例如 "abc"、"123"、"+" self.line = line self.col = col def __repr__(self): return f"Token({self.kind}, {self.value!r}, line={self.line}, col={self.col})"

kind 是语法分析器唯一关心的字段，value 用于出错信息或后续构造 AST 叶节点，line 和 col 用于报错定位。很多实验报告写的“第 3 行出现语法错误”，靠的就是这两个字段。

配套的词法接口，我建议一次性把整份输入解析成 Token 列表，而不是边读边推。原因是递归下降偶尔要向前多看一两个符号，出错恢复时也要回看，list 能随时通过下标回到之前的位置。边读边推省内存，但课程实验的输入文件撑死几千个 Token，内存根本不是瓶颈，可调试性才是：

def tokenize(source: str): tokens = [] i = 0 n = len(source) while i < n: c = source[i] if c.isspace(): i += 1 continue if c.isdigit(): j = i while j < n and (source[j].isdigit() or source[j] == "_"): j += 1 tokens.append(Token("INT", source[i:j], 1, i + 1)) i = j continue if c.isalpha(): j = i while j < n and (source[j].isalnum() or source[j] == "_"): j += 1 tokens.append(Token("ID", source[i:j], 1, i + 1)) i = j continue two = source[i : i + 2] if two in ("==", ">=", "<=", "!="): kind = {"==": "EQ", ">=": "GE", "<=": "LE", "!=": "NE"}[two] tokens.append(Token(kind, two, 1, i + 1)) i += 2 continue single_map = { "+": "PLUS", "-": "MINUS", "*": "MUL", "/": "DIV", "(": "LPAREN", ")": "RPAREN", "{": "LBRACE", "}": "RBRACE", } if c in single_map: tokens.append(Token(single_map[c], c, 1, i + 1)) i += 1 else: tokens.append(Token("SYM_" + c, c, 1, i + 1)) i += 1 tokens.append(Token("EOF", "$", 1, n + 1)) return tokens

这段代码的逻辑说明：空白直接跳过；数字串归为 INT；字母开头的串归为 ID；双字符运算符必须先于单字符运算符判断，否则==会拆成两个=，这是最常见的词法边界坑；未识别字符不直接抛异常，而是生成一个SYM_@之类的 Token，把错误留给语法分析器统一报，方便在一条输入里同时排查多个问题。

把 tokenize 和语法分析器分开还有一个好处：调试语法分析时，可以先打印一遍全部 Token，肉眼确认输入切分正确，再去分析语法问题。两个层混在一起，出了问题你根本不知道是词法切错还是语法匹配错。这是高级语言程序设计课里反复强调的分层思想，实验二里正是最容易偷懒的地方。

3.2 每个非终结符一个函数：把文法直接写进代码，最简单也最直观

递归下降写起来几乎没有设计感：非终结符就是函数，产生式右部就是函数体里的调用顺序。以表达式文法为例，2.3 节那张表直接变成如下代码：

class RecursiveDescentParser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): return self.tokens[self.pos] def match(self, kind): if self.peek().kind == kind: print(f"match {kind}: {self.peek().value}") self.pos += 1 else: raise SyntaxError( f"line {self.peek().line}, col {self.peek().col}: " f"expect {kind}, got {self.peek().kind}" ) # E -> T E' def parse_E(self): self.parse_T() self.parse_E_prime() # E' -> + T E' | ε def parse_E_prime(self): if self.peek().kind == "PLUS": self.match("PLUS") self.parse_T() self.parse_E_prime() # 否则不作任何操作，对应 ε 分支 # T -> F T' def parse_T(self): self.parse_F() self.parse_T_prime() # T' -> * F T' | ε def parse_T_prime(self): if self.peek().kind == "MUL": self.match("MUL") self.parse_F() self.parse_T_prime() # 否则，ε # F -> ( E ) | id | int def parse_F(self): if self.peek().kind == "LPAREN": self.match("LPAREN") self.parse_E() self.match("RPAREN") elif self.peek().kind in ("ID", "INT"): self.match(self.peek().kind) else: raise SyntaxError( f"line {self.peek().line}, col {self.peek().col}: " f"unexpected token {self.peek()}" )

逻辑说明：parse_E 就是产生式E -> T E'，先调 T 再调 E'；parse_E_prime 当前符号是+时选择第一条产生式，否则直接返回，对应 ε 分支。parse_F 只接受左括号开头或 ID/INT 开头，遇到其它符号就抛 SyntaxError，异常信息里带着行列号。

这里最容易被忽略的一条原则是：任何非终结符函数返回前，必须保证该消耗的 Token 已全部消耗完。比如 parse_T 必须完整调用 parse_T_prime，不能只调 parse_F 就返回，否则输入里带*的表达式会在后面直接报错。很多同学写T -> F T'时误以为 parse_T 就是“解析一个因子”，结果把2 * 3解析成2和* 3两段，分析器就会说意外的*。

驱动调用长这样：

def main(): src = "1 + 2 * 3" tokens = tokenize(src) parser = RecursiveDescentParser(tokens) try: parser.parse_E() if parser.peek().kind != "EOF": raise SyntaxError(f"unexpected trailing tokens: {parser.peek()}") print("ACCEPT") except SyntaxError as e: print("REJECT:", e) if __name__ == "__main__": main()

末尾的 EOF 检查至关重要。表达式文法要求整个输入串完全匹配才算接受，如果 parse_E 消费完1 + 2 * 3后还残留+ 4，说明输入不属于该文法定义的语言。漏掉这个检查，任何“解析成功了但没解析完”的输入都会被误判成 ACCEPT，这在实验评分里属于严重错误。

3.3 报错恢复：拒绝一个坏串之后，还要能继续查出下一个错误

课程实验对非法输入的要求通常是“报错并指出位置”，但更讲究一点的验收会希望程序在一条输入里报出多个错误，而不是第一个错误就退出。这里常见做法是给递归下降加一个轻量同步恢复：出错时扔掉若干 Token，直到撞上同步符号（通常是当前非终结符的 Follow 集合成员），然后从上层函数继续。

代码只加两样东西。一个是同步函数：

def synchronize(self, sync_set): while self.peek().kind not in sync_set and self.peek().kind != "EOF": self.pos += 1

另一个是在可能出错的非终结符函数里包一层：

def parse_E_prime(self): if self.peek().kind == "PLUS": self.match("PLUS") self.parse_T() self.parse_E_prime() elif self.peek().kind in ("EOF", "RPAREN"): return # 对应的 ε 分支合法 else: self.synchronize({"EOF", "RPAREN", "PLUS", "MUL"})

注意：同步集合不要设得太大。同步符号越多，跳过量越大，越容易掩盖真正的错误位置。我一般只拿当前非终结符的 Follow 集合当作同步集，对 E' 来说就是{EOF, RPAREN}，最多加上一两个明显的恢复点。这种机制能保证输入1 + * 2在*处报一次错后，不会因为剩下的2再连环报一串无意义的错。

4. 常见问题与避坑：预测表冲突、空产生式崩溃、栈溢出与 Token 错位

4.1 预测分析表出现一个格子两个产生式，代码从“确定”变成“猜”

现象：手动构造的预测分析表里，某个非终结符行和某个终结符列的交点出现两条产生式，表驱动程序中不知道该选哪条，程序行为要么固定选第一条、要么抛“table conflict”。

原因：绝大多数情况是 First/Follow 计算时遗漏了 ε 传递，少数情况是文法本身有二义性或没有完全提取左公因子。还有一种隐蔽的可能是：你在代码里用二维数组建表，默认值用了 0，结果“这个格子根本没填”和“冲突”用同一个状态表示，排错时根本分不清。

解决：先回到 2.3 节手算一遍 First 和 Follow，重点检查每个能推空产生式的 Follow 传递；然后在建表代码里加断言，同一个格子被第二次写入时直接抛异常并打印冲突的产生式编号。这一步能把“运行时行为诡异”变成“加载时直接报错”，查错范围一下子缩小很多。

4.2 空产生式让递归下降陷入死循环，程序没报错但也没结束

现象：程序跑起来没有任何输出，像卡住了一样。用调试器看调用栈，发现某个函数被反复调用，但输入指针始终没动。

原因：递归下降遇到 ε 分支时应该“什么也不做直接返回”，但如果你把 ε 分支错写成一个递归调用自身或者调用了另一个最终又会调回自己的函数，就会形成零消费循环。典型错误是把E' -> ε直接写成一个空 return 之外的递归调用。

解决：在每个非终结符函数入口加一行日志，打印当前 pos 和函数名。如果连续 N 层调用输入指针都不前进，基本可以断定某个 ε 分支写成了递归。还有一种更稳的写法：在函数开头做断言，进入函数时和返回时都检查 pos 是否变化，如果没变化且调用了下一层，就抛异常提示“空循环”。经验做法是先跑一条只有一个数字的最短输入，比如3，它对所有非终结符分支的压力最小，能从第一层开始验证是否存在零消费递归。

4.3 C/C++ 递归下降遇到深层嵌套表达式时栈溢出

现象：测试(((((...)))))上百层嵌套括号时，程序崩溃，报错信息里有 stack overflow，或者直接非法退出。在 Dev-C++、Visual Studio 的默认设置下，主线程栈大约只有 1MB，递归深度几万层就会碰顶。

原因：递归下降的函数调用深度和输入嵌套深度成正比。每个左括号都会让 parse_F 调 parse_E 再调 parse_T 再调 parse_F，一层括号对应至少三层函数调用，100 层括号就是几百层栈帧，加上每个函数调用占用的栈空间，很快就越界。

解决：课程实验正常测试用例不会到上万层嵌套，但如果你把递归下降写成纯函数递归又确实担心这个问题，有两个方向。第一，限制输入复杂度，在报告里说明该分析器面向普通表达式，不处理极端嵌套；第二，把递归下降改成显式栈的迭代版本，用一个栈保存“待处理的非终结符”，用循环替代函数递归。显式栈版本在 C++ 里只占堆空间，基本不会溢出，代价是代码可读性下降，谨慎选择。

4.4 Token 错位导致合法表达式被拒绝，报错位置还非常诡异

现象：输入a == b报错说“意外的 =”，而且连续报两次。明明从语义上==是一个整体，程序却把它当成两个独立符号处理。

原因：词法分析器按单字符判断，每看到=就输出一个 EQ Token，没有先检查双字符运算符。这类问题在词法分析实验里可能没暴露，因为实验一只是单独验证词法；一旦接上语法分析，==、<=、>=这类双字符运算符全部错位，语法分析器当然一脸茫然。

解决：回到 tokenize，把双字符运算符的判断放在单字符判断之前，也就是 3.1 节代码里的顺序。还有一个实用习惯：写语法分析前先打印一次 Token 列表，肉眼扫一遍确认==是否被切成一个 Token。不要省这一步，它比任何调试器都直观。

4.5 同步恢复后连续报一串假错误，信息看着像代码全是坏的

现象：输入里只有一个错误，但程序报出七八条 SyntaxError，而且后面的报错位置毫无规律，像是分析器已经处于“半疯”状态。

原因：同步恢复执行后，跳过 Token 是跳到了同步集合里的某个符号，但函数调用栈没有恢复到合理的状态。上层函数在错误的上下文里继续调下一层的非终结符函数，每一个都发现当前 Token 不匹配，于是连环报错。

解决：两个约束。一是同步集合严格限定为当前非终结符的 Follow 集合，不要顺手把什么符号都加进去。二是同步后要“放弃当前正在解析的子树”，也就是让当前非终结符函数直接返回成功状态给上层，由上层判断当前 Token 是否合法。常见的错误实现是同步后继续执行本函数后面的逻辑，那只会制造更多失败。我习惯给 parse 函数增加一个返回“是否成功”的控制流，而不仅仅是抛异常——这样做后续做错误恢复和语义分析都更顺。

5. 验证实验二成果的三种方法，以及把语法树接给语义分析

5.1 准备一张“正向与反向”测试用例表，别只跑老师给的样例

实验做完最容易犯的错是只测试1 + 2 * 3这类教科书样例，结果多头运算符、空产生式、错误恢复全是盲区。我一般给实验二准备四组用例：单符号输入、复合运算、嵌套括号、非法 Token。每组至少五条，比如：

3 1 + 2 * 3 (1 + 2) * 3 ((1 + 2) * (3 + 4)) 1 + * 2

把每条输入和预期结果写成一个断言函数，每次改完代码跑一遍全量回归。这个习惯能帮你省掉大量“改了一处、坏了另一处”的排查时间。

5.2 打印最左推导过程，既是自查工具也是实验报告素材

递归下降的调用顺序天然就是最左推导：每进入一个非终结符函数，就在输出里追加一步当前推导结果。实验报告要求“给出推导过程”时，这一串输出就是现成的截图素材。做法很简单，在 parse_E 入口打印当前已匹配 Token 的序列，在每次 match 成功后再打印一遍。别小看这个输出，它能让老师一眼看清你的程序确实在按文法展开，而不只是二分硬编码了几个表达式。

5.3 往前一步：把每个非终结符函数的返回从“无”改成 AST 节点

语法分析做完，下一步实验大概率是语义分析。现在就把 parse 函数的返回值改成 AST 节点，后面能省一整轮重构：

class Node: def __init__(self, name, children=None, value=None): self.name = name self.children = children if children else [] self.value = value def __repr__(self): return f"Node({self.name}, value={self.value!r})"

parse_F 里原来是self.match(...)，改成构造叶子节点；parse_E 和 parse_T 则把子节点的结果组装成内部节点。这样语法分析器的产出就从“接受/拒绝”升级成语法树，直接对接第三个实验的符号表和中间代码生成。整套实验做完，再回头看这个实验二，会发现它真正训练的并不是“背会自顶向下分析”，而是“把一个形式化定义一步一步变成可调试的程序”。

我自己当初在实验二上花时间最多的地方，不是递归下降本身，而是错误恢复和用例设计。后来做解释器项目时，那些在课程里养成的“Token 接口先打印一遍、每个函数只干一件事、报错必须带行列号”的习惯，几乎原封不动用到了生产代码里。先把这个实验彻底跑通，后面每一步都会省力不少，希望帮到你。

本文还有配套的精品资源，点击获取