企业官网建设流程全解析

简介：这是一份编译原理课程实验文档，围绕语法分析程序的设计与实现展开，面向计算机及相关专业学习编译原理的学生。文档完整呈现了实验目的、基本内容与要求，并以算术表达式简化子集为分析对象，采用LL(1)文法进行文法改写，给出了预测分析表及相应的C++源程序，帮助读者理解自顶向下语法分析的流程与实现要点。资源为单个doc文件，大小127KB，包含实验步骤、问题分析、源程序和结论等完整内容，目前已有143人学习浏览，可作为课程设计或实验报告的参考模板。文档中不仅包含LL(1)文法的定义与预测分析表构造过程，还涉及词法分析结果衔接、错误处理等细节，实验要求中的合法与非法测试用例、分析栈和剩余串输出等也有呈现，对掌握语法分析程序的编制与调试具有实用价值。

1. 看到“语法分析程序设计与实现”先想清楚：这份实验考的是哪一层

看到“实验二--语法分析程序设计与实现.doc”这个标题，你基本能预判这个实验要做什么：课程给出一份文法，你写一个程序，输入是源代码文本或表达式，输出是“合法”或“第几行第几个词法单元处出错”。语法分析是高级语言程序设计和编译原理课程里最不容易划水的实验，它不像词法分析那样可以用正则凑过去，更不是背概念就能交差。它的核心是一道翻译题：把纸面上的产生式，翻译成一段能运行、能判定、能报错的逻辑。这篇笔记把两条主流实现路线拆开讲：自顶向下的递归下降，和自底向上的LR表驱动。如果你正在赶这个实验、想重写一份老代码，或者第一次接触语法分析器，这篇就是照着能用的那类。

2. 递归下降还是LR表驱动：先给两个选型理由和一个文法预处理清单

2.1 词法分析做完只是“单词表”，语法分析才是句子判定

很多第一次做这个实验的人，第一步就卡在“为什么词法都对了，还要写一个这么长的东西”。词法分析把1 + 2 * (3 - 4)切成 token 序列后，程序眼里只有一个线性数组：num('1')、op('+')、num('2')、op('*')、lparen('(')、num('3')、op('-')、num('4')、rparen(')')。这只是一个单词表，并没有回答“这个句子在文法上成不成立”的问题。num op num到底该先算哪个，是语法分析器决定的；(后面必须跟一个表达式，也是语法分析器决定的。

语法分析器的输入就是 token 数组，输出可以是“通过/不通过”，也可以带语法树和错误位置。实验里判定“通过/不通过”是最低要求，但要做得有说服力，必须在报错信息里给出当前 token 的行号、期望的非终结符和实际看到的 token。数据结构上，递归下降方案需要一个位置指针和一个当前 token；LR 方案需要状态栈、符号栈和一张动作表。

2.2 两个主流方案的选型对比：实验场景下我为什么默认先选递归下降

语法分析有两条路。自顶向下从起始符号开始，按产生式展开，遇到终结符就匹配；自底向上从输入 token 开始，不断把右部归约成左部，直到归约成起始符号。落在代码上就是递归下降法和 LR 表驱动法。两者不是“谁更好”，而是“谁更适合当前约束”。我做这类实验时默认先选递归下降，理由只有一个：错误定位直观。哪个非终结符的哪个位置匹配失败，调用栈就是现场，打断点就能看到。

如果实验题目只写“语法分析程序设计与实现”，没有点名要 LR，我会用递归下降；如果题目要求“构造 LR 分析表并给出驱动算法”，那就老老实实走表驱动。还有一种中间做法：用现成的 lex/yacc 风格工具输出一个分析器，再包一层自己的 main——这在程序设计实践里算捷径，但实验汇报时你得能解释生成的表从哪来。

2.3 拿到文法先做三步预处理：消左递归、提左因子、算FIRST/FOLLOW

选型定了还不能直接写代码。课程给的文法大多是教材里的标准形式，比如：

expr -> expr + term | term term -> term * factor | factor factor -> id | num | ( expr )

这份文法人看着顺眼，机器也有定义，但它带了左递归。左递归对 LR 系方法没有影响，对递归下降就是死路：parse_expr第一步又调用parse_expr，token 没推进，栈直接打满。所以如果走递归下降，先把左递归消掉，变成右递归加空产生式：

expr -> term expr' expr' -> + term expr' | ε term -> factor term' term' -> * factor term' | ε factor -> id | num | ( expr )

第二步是提左因子。出现factor -> id | num | ( expr )这种“分支开头 token 各不相同”的情况还好说，一旦遇到stmt -> if E then S | if E then S else S这种悬空 else 文法，预测分支会重叠。这时候要么把公共前缀提出来变成stmt -> if E then S else_tail，要么在实现层用贪婪策略默认匹配 else，后者其实就是“移进优先”。

第三步是算 FIRST 和 FOLLOW 集合。算它不是为了交作业，而是为了发现自己写的预测函数在哪些 token 上会产生冲突。比如expr' -> + term expr' | ε，只有遇到+时才走第一个分支，遇到)或$才走 ε 分支；如果两个集合交叠，就是文法还有问题。手算三个集合也就是十来分钟的事，别偷懒。

注意：算 FOLLOW 集合时，初始符号的 FOLLOW 里必定包含$。这条漏了，LR 或 LL 分析表的接受动作会直接找不到入口。

3. 手写递归下降语法分析器：一个用Python就能跑通的最小实现

3.1 先定token接口：语法分析器不要依赖词法内部实现

写语法分析器之前，先把词法接口固定下来。很多翻车现场都是因为语法分析函数里还残留着正则匹配和字符串切割，导致改一个空白符处理方式就崩一片。常见的做法是定义一个 Token 对象，只暴露 kind、value、line 三个字段，语法分析器只看 kind 和 line，不看 value 之外的东西。

import re from dataclasses import dataclass @dataclass class Token: kind: str # id / num / op / lparen / rparen / eof value: str line: int token_specs = [ ('num', r'\d+(\.\d+)?'), ('id', r'[A-Za-z_]\w*'), ('op', r'[+\-*/]'), ('lparen', r'\('), ('rparen', r'\)'), ('ws', r'\s+'), ] token_re = re.compile('|'.join(f'(?P<{name}>{pattern})' for name, pattern in token_specs)) def tokenize(text): tokens = [] line = 1 for match in token_re.finditer(text): kind = match.lastgroup value = match.group() if kind == 'ws': line += value.count('\n') continue tokens.append(Token(kind, value, line)) tokens.append(Token('eof', '<EOF>', line)) return tokens

(?P<name>pattern)这种方式给每个正则命名，match.lastgroup直接返回匹配到的类别名，省去自己记分组编号。空白符被统一吃掉，并统计换行来推进行号。语法分析器拿到的是一个已经排除了空白和注释的干净序列，逻辑上只需要advance()和expect(kind)两个操作。

3.2 expr、term、factor三层递降：一个能跑的最小骨架

把上一节消掉左递归后的文法转成函数，就是三层递降：parse_expr处理加减，parse_term处理乘除，parse_factor处理原子和括号。关键点在于：产生式里的expr'我不会真的写成一个递归函数，而是用 while 循环消化同层运算符。长表达式下不撑栈，还天然实现了左结合。

class Parser: def __init__(self, tokens, debug=False): self.tokens = tokens self.pos = 0 self.cur = tokens[0] self.debug = debug self.depth = 0 def advance(self): # 停在最后一个eof上，不越界 if self.pos < len(self.tokens) - 1: self.pos += 1 self.cur = self.tokens[self.pos] def _enter(self, rule): if self.debug: print(' ' * self.depth + f"{rule}: {self.cur.kind} '{self.cur.value}'") self.depth += 1 def _leave(self): self.depth -= 1 def expect(self, kind): if self.cur.kind != kind: raise SyntaxError( f"line {self.cur.line}: expected {kind}, got '{self.cur.value}'") self.advance() def parse_expr(self): self._enter('expr') self.parse_term() while self.cur.kind == 'op' and self.cur.value in ('+', '-'): self.advance() self.parse_term() self._leave() def parse_term(self): self._enter('term') self.parse_factor() while self.cur.kind == 'op' and self.cur.value in ('*', '/'): self.advance() self.parse_factor() self._leave() def parse_factor(self): self._enter('factor') if self.cur.kind in ('id', 'num'): self.advance() elif self.cur.kind == 'lparen': self.advance() self.parse_expr() self.expect('rparen') else: raise SyntaxError( f"line {self.cur.line}: unexpected token '{self.cur.value}'") self._leave() def main(): text = "1 + 2 * (3 - 4)" tokens = tokenize(text) parser = Parser(tokens, debug=True) try: parser.parse_expr() parser.expect('eof') print('ACCEPT') except SyntaxError as e: print('REJECT:', e) if __name__ == '__main__': main()

逻辑说明：parse_expr先调parse_term是必须的，保证1 + 2 * 3里的乘法先归组。+和-被 while 连续消化，所以1 - 2 - 3会按(1-2)-3处理。parse_factor是底层，只负责数字、变量和括号内的整个表达式。运行时把debug=True打开，能看到每一步在哪条规则里停了，把函数名后的缩进当深度用——这是整个实验里最省事的验证手段。

3.3 错误信息和对齐：报错位置差一行都算没做完

主函数里的 try/except 只做了最简陋的“打印错误”。课程实验一般会要求定位到行，条件允许的话再给列号。行号已经在 Token 里带好了，列号需要额外在每个 Token 里存 offset 字段，词法匹配时用match.start()记下位置。语法分析器里有一个原则：任何报错信息必须用“当前正在看的这个 token”的行号，而不是用刚消费掉的那个 token 的行号。

什么时候会踩这个坑，第五章会展开讲。这里先记住一个结论：expect在匹配失败时一定不要先调用advance()再抛异常，因为那样抛出去的是下一个 token 的位置，排查问题的人会拿着错误行号去查完全无关的代码。

4. 手工构造LR分析表和驱动循环：把状态栈讲透

4.1 一张小SLR分析表长什么样：文法、动作表和GOTO

如果实验题目强制要求 LR 路线，你就得动手算状态族并填两张表。以最精简的一个文法为例：

(1) E -> E + T (2) E -> T (3) T -> id

这里把加法符号在词法里标记成PLUS。手工构造 SLR 表时，先写增广文法S -> E，然后逐个状态求闭包和转移。上面这个文法的结果如下，状态 0 是初始状态，动作表里的s 3表示移进并转状态 3，r 2表示用第 2 条产生式归约，acc表示接受。

这张表就是整个 LR 分析器的核心。把它翻译成 Python 字典，注意键是(状态, 符号)二元组，动作值用('s', n)或('r', n)或('acc',)三种形态。

ACTION = { (0, 'id'): ('s', 3), (1, 'PLUS'): ('s', 4), (1, '$'): ('acc',), (2, 'PLUS'): ('r', 2), (2, '$'): ('r', 2), (3, 'PLUS'): ('r', 3), (3, '$'): ('r', 3), (4, 'id'): ('s', 3), (5, 'PLUS'): ('r', 1), (5, '$'): ('r', 1), } GOTO = { (0, 'E'): 1, (0, 'T'): 2, (4, 'T'): 5, } PRODUCTIONS = { 1: ('E', ['E', 'PLUS', 'T']), 2: ('E', ['T']), 3: ('T', ['id']), }

这里有个容易看晕的点：状态编号同时出现在 ACTION 和 GOTO 里，但它们代表的是同一个状态机的不同跳转渠道——移进时跳转到 ACTION 指定的状态，归约后跳转到 GOTO 指定的状态。表格里的r 2和状态 2 没有必然联系，规则编号是另起炉灶的。

4.2 驱动循环：状态栈、符号栈、查表的顺序决定成败

有了表，驱动函数大概 30 行。核心不变式是：状态栈和符号栈永远等长，状态栈顶对应符号栈顶那个文法符号的分析状态。

def lr_parse(tokens): state_stack = [0] sym_stack = [] idx = 0 while True: state = state_stack[-1] key = tokens[idx].kind act = ACTION.get((state, key)) if act is None: raise SyntaxError(f"state {state}, token {key} 下无可用动作") if act[0] == 's': state_stack.append(act[1]) sym_stack.append(key) idx += 1 elif act[0] == 'r': lhs, rhs = PRODUCTIONS[act[1]] for _ in rhs: # 右部多长就弹多少层 state_stack.pop() sym_stack.pop() ns = GOTO.get((state_stack[-1], lhs)) if ns is None: raise SyntaxError(f"state {state_stack[-1]} 对 {lhs} 无GOTO") state_stack.append(ns) sym_stack.append(lhs) print(f"reduce: {lhs} -> {' '.join(rhs)}") elif act[0] == 'acc': return True

拿输入id PLUS id $走一遍：状态 0 看到 id 移进到状态 3，状态 3 对 PLUS 归约出 T；回到状态 0 后 GOTO 到状态 2，状态 2 对 PLUS 归约出 E；接着状态 1 移进 PLUS 到状态 4，读第二个 id 到状态 3，状态 3 对$归约出 T，查 GOTO(4, T)=5，状态 5 再对$归约出 E，最后状态 1 遇到$接受。整个过程中输入指针是移动、归约、再移动，和递归下降最大的区别就在这。

4.3 冲突出现时先别急着改表：先确认是文法的锅还是FOLLOW集的锅

手工构造 LR 表最常见的绊脚石是表格里出现冲突。同一状态下同一个输入符号既允许移进又允许归约，就叫移进-归约冲突；同时有两个归约项，叫归约-归约冲突。遇到冲突，我的处理顺序是这样的：第一，先算一下 FOLLOW 集，看是不是把 FOLLOW 算宽了；第二，再查文法是不是有二义性，比如悬空 else 那种经典情况；第三，才考虑用优先级或默认移进策略消解冲突。

拿悬空 else 举例，if E then S | if E then S else S在else处天然冲突。教材会告诉你“通常选择移进”，这句不是玄学，它的效果是让 else 与最近的 if 配对，也就是 C 语言的行为。如果你在实验里想简化，干脆把 else 分支从文法里拿掉，先跑通主体逻辑再补。

4.4 用工具生成分析器时也要做的三件事

实验不让从零写表的时候，也可以用 lex/yacc 风格的工具生成。生成器不是逃避“理解原理”的借口，有个经验值得记一下：生成器帮的是算表和查表，帮不了你定义错误恢复策略。用工具时我会盯三件事。一是终结符声明和词法 token 名必须一一对应，少一个声明生成的表就会少一列。二是别去改生成文件里的状态表，要改文法就回源文件改，再重新生成；手改状态表是这个实验里最差的返工。三是生成的代码通常自带一个 main，你要把自己包一层，先跑最小的合法输入确认入口是自己的那层，再跑错误输入看报错格式。

5. 语法分析实验避坑记录：死循环、错位报错与优先级翻车

5.1 死循环或栈溢出：左递归没消干净，ε分支没推进

现象比较典型：输入1+2+3+...这种连续加法的表达式，程序要么卡死，要么报栈溢出，要么在递归下降过程里反复进入同一个函数名。

原因通常是两个：一是左递归没有消除干净，parse_expr第一行调用parse_expr，token 从头到尾没动过；二是消除左递归后的空产生式分支忘了让advance()推进 token，导致 ε 分支一直重试。递归下降里有一条纪律：任何一次递归调用或循环迭代，要么消耗一个 token，要么明确走空分支结束。反例和正解对比很直接：

# 反例：parse_expr 开头又调 parse_expr，token 不推进 def parse_expr(self): self.parse_expr() # 无限递归 self.parse_term() # 正解：先处理下一层，再用 while 消化同一优先级的运算符 def parse_expr(self): self.parse_term() while self.cur.kind == 'op' and self.cur.value in ('+', '-'): self.advance() self.parse_term()

检查的办法也很简单：开 debug 开关看调用轨迹，如果同一个规则名连续出现三次以上且当前 token 没变，基本就是这里出了事。

5.2 报错位置永远偏后一位：expect失败时先advance再抛出

现象是输入明显在第二行出错，错误信息却指向第三行甚至文件末尾。拿1 + 2 *来说，缺的是操作数，程序却报“在$处遇到 eof”。

原因是expect这类匹配函数写成了“先advance()再判断”。一旦 cur 是$（文件末尾），语法分析器的 pos 已经越界，行号连锁出错。解决方法是让expect在匹配失败时立刻用当前 token 抛异常，不要先消耗它。这也是第 3.3 节强调的原则，这里再看一遍实际代码：

def expect(self, kind): if self.cur.kind != kind: raise SyntaxError( f"line {self.cur.line}: expected {kind}, got '{self.cur.value}'") self.advance()

如果坚持在函数开头就advance()，那报错信息里至少要保存前一个 token 的 line 和 column，实现起来不是不行，是没必要。

5.3 优先级悄然改变：3+4*5 结果对不上

现象是语法树长得怪，或者计算后结果和预期不一致，比如把3+4*5算成了 35 而不是 23。原因是函数调用层级写反了——parse_expr里先直接处理了*，或者parse_term里没调parse_factor，导致乘法和加法被当成同一层。

正确层级必须保证：加法层只消化加减，它调乘法层；乘法层只消化乘除，它调 factor 层；factor 层只消化数字、变量、括号。括号里的内容再重新回到加法层。一句话检查：看你的代码里parse_expr的第一步是不是parse_term()，parse_term的第一步是不是parse_factor()，如果出现parse_expr里直接parse_factor，优先级的骨架就塌了。早点把调试输出打开，能省后面一整轮测试。

5.4 Windows换行和全角空格导致的灵异报错

现象是同样的代码在 Linux 上跑得好好的，从 Windows 拷来的测试文件一运行就报unexpected token '\r'，或者遇到全角空格时 id 被切成两段。

原因是词法层把不可见字符漏了。Windows 的换行是\r\n，\r不是空白匹配的默认目标；全角空格也不在\s范围内。解决要在 tokenize 里统一过滤，而不是在语法分析器里补判断。我在 tokenize 开头会先做一次文本清洗：

def tokenize(text): text = text.replace('\r', '').replace('\ufeff', '') tokens = [] line = 1 for match in token_re.finditer(text): kind = match.lastgroup value = match.group() if kind == 'ws': line += value.count('\n') continue tokens.append(Token(kind, value, line)) tokens.append(Token('eof', '<EOF>', line)) return tokens

\ufeff是带 BOM 的文本开头常带的可选字符，不扒掉的话第一个 token 会变成一个不可见字符，后面所有关于第一行的报错全错位。全角空格这类问题，更稳的做法是在清洗时也替换成半角。

5.5 手工分析表坐标写反：能用但偶尔错

现象是 LR 模式跑部分用例通过、部分用例在某个状态反复归约或漏归约，看起来像随机翻车。原因是 ACTION 和 GOTO 表作图时状态号写着写着就错位了，比如把GOTO (0, 'E')错写成GOTO (0, 'id')，或者把状态 2 里应该归约的规则编号填成了状态 1 的。

这属于表格数据问题，肉眼排查困难，我一般写个一句话自检脚本：

terminals = {'id', 'PLUS', '$'} nonterminals = {'E', 'T'} def check_tables(): for (state, sym), act in ACTION.items(): assert sym in terminals, f"ACTION 键混入了非终结符: {sym}" for (state, sym), ns in GOTO.items(): assert sym in nonterminals, f"GOTO 键混入了终结符: {sym}" print("table layout ok")

这个脚本不验证归约正确性，但能挡住最傻的坐标错误。再往深排查，把一个带1+1的用例跟着状态栈手推一遍，推到哪一步表和手推不一致，错就定位在哪一格。

6. 一个能省下大量查错时间的偷懒技巧：顺手把语法树建出来

我见过很多人的语法分析器只返回True / False，交实验没问题，但每次改文法都要重新对着输入和报错猜结构。一个投入很小、收益很大的做法是：别让你的每个 parse 函数只返回布尔值，让它们返回 AST 节点。判定通过与否只是遍历这棵树有没有异常，而树本身会告诉你优先级和结合性有没有摆对。

class ASTNode: def __init__(self, name, children=None): self.name = name self.children = children or [] def print_tree(node, indent=0): print(' ' * indent + node.name) for child in node.children: print_tree(child, indent + 1)

改造parse_expr只需要替换 return 部分。原来每层函数在消费 token 后把信息拼成节点，父层按操作符组装子节点：

def parse_expr(self): node = ASTNode('expr', [self.parse_term()]) while self.cur.kind == 'op' and self.cur.value in ('+', '-'): op = self.cur.value self.advance() node.children.append(ASTNode(op, [self.parse_term()])) return node

注意顺序：先记录运算符值，再advance()，最后解析右操作数。如果反过来，当前 token 已经被消耗，右操作数会把下一个运算符吞掉。打印出来以后，3 + 4 * 5的树应该长这样：

expr + 3 * 4 5

*挂在+的子节点上，说明乘号先结合。看到这棵树比跑一百个用例都安心。我自己的习惯是从第一个能跑的版本起就带 AST，后面加变量声明、赋值语句、函数调用时，每个新语法结构的树形长什么样一目了然。这个习惯让语法分析实验从“能不能过”变成了“能看清楚自己在做的东西”。如果你手头已经有跑通的布尔版 parser，改动也就是声明一个 Node 类、把 return None 改成 return node 的事，半天内能完成。希望帮到你。

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