企业官网建设流程全解析

简介：编译原理实验配套资源，面向正在完成词法分析、语法分析课程设计的高校学生。压缩包内含词法分析器、LL(1)语法分析器、LR(1)语法分析器三部分实现，覆盖从底层分词到两种语法分析策略的完整流程，词法部分可识别关键字、标记符、运算符、分界符、无符号数，还额外支持字符/字符串与行间注释，并配有图形界面展示分析结果。包体共52个文件，以C++源文件（.cpp/.h）和HTML前端界面为主，同时附有测试输入（.in）、期望输出（.out）、实验报告PDF、演示动图及makefile构建脚本，便于对照学习与重新编译运行。资源整体6.88MB，目录结构清晰，适合作为实验参考或功能扩展基础。目前已有1089人学习下载，若正在编写编译原理实验或需要可运行的示例代码，这份资料能节省不少调试时间。

1. 编译原理实验三件套：这门课最该自己手写的一次作业

很多同学把编译原理实验当成“填空式”的课程设计，拿着学长学姐的 zip 改改变量名就交差。但词法分析器、LL(1) 语法分析器、LR(1) 语法分析器这三个模块，恰恰是整门课最值得亲手推一遍的线段：从字符流到 token 流，从 token 流到语法树，每一步都在验证离散数学、文法和自动机理论到底怎么落地。哪怕你不打算写编译器，这三块代码也直接影响你理解 JSON 解析器、SQL 解释器、表达式引擎这些日常工具的内部逻辑。这篇笔记会按“词法 → LL(1) → LR(1)”的顺序，把每个模块的构造步骤、参数选择和典型翻车点讲清楚，包含可以直接改用的代码框架。适合正在做编译原理实验、或者想从零手写一个小型前端分析器的读者。

2. 词法分析器：从字符流到 token 流，最长匹配和状态表是核心

编译原理实验里，词法分析器最容易被低估，因为多数人第一反应是“用正则不就完了”。但实验要求往往卡在两点：一是禁止调用现成词法生成器，二是要求处理错误恢复和最长匹配语义。自己手写时，我建议用显式的状态转换表而不是散落一地的 if/else，这样后续加注释、加字符串字面量、加运算符都不会把 main 函数变成意大利面。

2.1 为什么手工构造 DFA 比直接写正则更靠谱

正则表达式底层会编译成 NFA 再转 DFA，但你在实验里直接re.match会踩两个坑：第一，Python 的re模块是 Perl 风格正则，它对“贪心/非贪心”和“边界”有自己的规则，和编译原理教材里的正则代数不完全一致；第二，多个正则并联时，匹配顺序完全由代码书写顺序决定，你想实现“标识符优先于关键字”还得额外排序。手工构造 DFA 的好处是状态迁移完全显式，遇到不匹配字符能立刻进入错误状态，并且可以方便地配合最长匹配策略——读入尽可能多的字符，直到下一个字符无法迁移为止，然后把当前状态对应的 token 返回。

我在实验里一般维护一个二维数组state_table[state][char_class]，行是状态编号，列是字符类别（字母、数字、运算符、分隔符、其他）。每一步读一个字符，查数组得到下一个状态；如果查不到，就回退到上次接受状态。这样“接受状态集合”和“状态类别”都变成数据，调试时打印状态编号就知道卡在哪。

2.2 一个可复用的词法分析器框架：表驱动 + 最长匹配

下面这个 Python 实现没有依赖任何正则库，只用了str的基本方法。它演示了最核心的表驱动骨架：用while循环配合last_accept记住最后一次可接受位置，实现最长匹配回退。

class Lexer: def __init__(self, text): self.text = text self.pos = 0 self.line = 1 TOKEN_KINDS = { 'ID': 'IDENTIFIER', 'NUM': 'NUMBER', 'PLUS': '+', 'MINUS': '-', 'STAR': '*', 'SLASH': '/', 'LPAREN': '(', 'RPAREN': ')', 'SEMI': ';', 'EQ': '=', } KEYWORDS = {'if', 'else', 'while', 'return'} def _is_alpha(self, c): return c.isalpha() or c == '_' def _is_alnum(self, c): return c.isalnum() or c == '_' def _error(self, msg, line): raise RuntimeError(f'line {line}: {msg}') def next_token(self): while self.pos < len(self.text): c = self.text[self.pos] if c.isspace(): if c == '\n': self.line += 1 self.pos += 1 continue # 标识符和关键字：字母开头，后跟字母/数字/下划线 if self._is_alpha(c): start_pos = self.pos while self.pos < len(self.text) and self._is_alnum(self.text[self.pos]): self.pos += 1 word = self.text[start_pos:self.pos] kind = 'keyword' if word in self.KEYWORDS else 'identifier' return (kind, word, self.line) # 数字：支持整数和简单小数，注意最长匹配到非数字为止 if c.isdigit(): start_pos = self.pos while self.pos < len(self.text) and self.text[self.pos].isdigit(): self.pos += 1 if self.pos < len(self.text) and self.text[self.pos] == '.': self.pos += 1 while self.pos < len(self.text) and self.text[self.pos].isdigit(): self.pos += 1 return ('number', self.text[start_pos:self.pos], self.line) # 单字符运算符，这里预留双字符运算符扩展点 two_char = self.text[self.pos:self.pos + 2] if two_char in ('==', '!=', '>=', '<='): self.pos += 2 return ('op', two_char, self.line) if c in '+-*/()=;': self.pos += 1 return ('op', c, self.line) self._error(f'非法字符: {c!r}', self.line) return ('eof', None, self.line) def tokenize(self): tokens = [] while True: tok = self.next_token() tokens.append(tok) if tok[0] == 'eof': break return tokens

这段代码的关键逻辑在“最长匹配”：标识符循环里，只要下一个字符是字母数字就继续读，直到读不进为止；数字同理。如果直接用if c.isalpha()只读一个字符，那么intVar会被切成长度和词，实验一跑就崩。参数上要注意三个地方：一是KEYWORDS是集合，查找是 O(1)，别用列表；二是关键字判断必须发生在读完整个单词之后，不能看到第一个字母是i就认为是if；三是运算符部分我预留了双字符判断，因为==和=在后续语法分析里可能是不同的 token。如果你要支持字符串，需要再增加一个'\"的迁移状态，并且在字符串内部识别转义符。

2.3 词法分析器的三个必调参数：状态表、关键字表、缓冲大小

很多实验报告把词法分析器写成“能用就好”，但验收时会问三个参数：最大标识符长度、缓冲区分块大小、错误恢复策略。第一个参数影响符号表设计，比如某些语言限制标识符前 63 个字符有效，那你需要在循环里加长度上限，超过后可以报错或截断并继续。第二个参数影响读文件方式，如果文本文件很大，不要read()全部载入内存，而是用read(4096)分块，但要注意跨块时 token 会被截断。常见做法是维护一个环形缓冲区或者至少保留上次未消费完的尾部，我的经验是直接读整行再逐行 tokenize，实验规模下简单且不容易出 bug。第三个参数直接决定你有没有输出“line 3: unexpected character '@'”这样的诊断能力。我在错误恢复上采用“丢弃当前字符，行号不变，继续扫描”的策略，虽然会跳过一些 token，但至少整个文件能被扫完，比一遇到非法字符就终止整个程序更适合后续语法分析阶段报错定位。

3. LL(1) 语法分析器：FIRST/FOLLOW 集、预测分析表与栈驱动的完整实现

LL(1) 是“从左到右扫描、产生最左推导、向前看 1 个 token”的缩写，也是实验里最容易讲清楚、又最容易写错的部分。多数教科书会先给 FIRST/FOLLOW 定义，然后让你手工构造预测分析表。实验的验收点通常有三处：FIRST/FOLLOW 集算得对不对、预测分析表有没有冲突、栈驱动程序能否在处理语法错误时不死循环。

3.1 消除左递归与提取左公因子：LL(1) 文法的前提

不是所有上下文无关文法都能用 LL(1)。直接左递归E -> E + T会让预测分析表在E这一行、+这一列填两个产生式，形成冲突。实验前必须先把文法改写成 LL(1) 可用的形式。以经典算术表达式文法为例，原始版本是左递归的，需要改写为右递归形式：

原文法：

E -> E + T | T T -> T * F | F F -> ( E ) | num

改写后：

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

改写过程还藏着一个实验常考的细节：提取左公因子。比如文法S -> if E then S else S | if E then S必须先合并成S -> if E then S S'，S' -> else S | ε，否则预测表会在S遇到if时不知道选哪条产生式。我在实验里会把“改写前的冲突表”和“改写后的表”都打印出来，报告里写“验证了 LL(1) 文法的充分性”，这比单纯贴代码得分高。

3.2 用 Python 计算 FIRST 和 FOLLOW 集：代码与参数说明

下面这份代码可以直接跑，输入是产生式列表，输出是每个非终结符的 FIRST 集和 FOLLOW 集。

def compute_first(productions): # productions 形如: {'E': [['T', 'E\'']], 'E\'': [['+', 'T', 'E\''], []]} # 空列表 [] 表示 epsilon first = {nt: set() for nt in productions} changed = True while changed: changed = False for lhs, rhs_list in productions.items(): for rhs in rhs_list: if not rhs: # epsilon if 'epsilon' not in first[lhs]: first[lhs].add('epsilon') changed = True else: before = len(first[lhs]) for symbol in rhs: if symbol in productions: # 非终结符 first[lhs] |= (first[symbol] - {'epsilon'}) if 'epsilon' not in first[symbol]: break else: # 终结符 first[lhs].add(symbol) break else: # 所有符号都能推出 epsilon first[lhs].add('epsilon') if len(first[lhs]) != before: changed = True return first def compute_follow(productions, first, start_symbol): follow = {nt: set() for nt in productions} follow[start_symbol].add('$') # 输入结束符 changed = True while changed: changed = False for lhs, rhs_list in productions.items(): for rhs in rhs_list: for i, symbol in enumerate(rhs): if i == 0 and not symbol: continue if symbol not in productions: continue # 终结符跳过 rest = rhs[i + 1:] if not rest: before = len(follow[symbol]) follow[symbol] |= follow[lhs] if len(follow[symbol]) != before: changed = True else: first_rest = set() can_epsilon = True for s in rest: if s in productions: first_rest |= (first[s] - {'epsilon'}) if 'epsilon' not in first[s]: can_epsilon = False break else: first_rest.add(s) can_epsilon = False break before = len(follow[symbol]) follow[symbol] |= first_rest if can_epsilon: follow[symbol] |= follow[lhs] if len(follow[symbol]) != before: changed = True return follow

逻辑说明：FIRST 集计算用不动点迭代，每一轮如果某个非终结符的集合发生了变化，就继续下一轮。参数上最需要注意的是rhs为空的产生式要显式表示成空列表[]，不要用['epsilon']字符串，不然你在symbol in productions判断时会把'epsilon'当成非终结符。FOLLOW 集计算时，$是输入结束标记，只加入开始符号的 FOLLOW 集；当遇到A -> α B且 B 后面没有符号时，FOLLOW[B] 并入 FOLLOW[A]，这是最容易漏的一条规则。另外，first_rest的can_epsilon标志很关键，如果 B 后面的符号串能推出 epsilon，那么 FOLLOW[A] 也要并进 FOLLOW[B]，教科书上叫“β 能推导出 ε 的情况”。

实践提示：如果实验把 FIRST 和 FOLLOW 作为硬性输出，建议把非终结符按字母序排序打印，避免无顺序的结果被验收同学认为不对。

3.3 预测分析表驱动过程与同步 token 选择

预测分析表是一个二维表，行是非终结符，列是终结符。构造规则是：对于产生式A -> α，把α填入table[A][b]，其中b ∈ FIRST(α)；如果α能推出 epsilon，则把α填入table[A][c]，其中c ∈ FOLLOW(A)。这张表本身就是最好的调试输出，实验报告里可以直接检查是否有单元格内多于一个产生式。

栈驱动程序用 Python 写短小清晰：

def ll1_parse(table, start, token_list): stack = ['$', start] index = 0 while stack: top = stack[-1] token = token_list[index] token_type = token[0] # 假设 token 是 (type, value, line) if top == token_type: stack.pop() index += 1 elif top == '$': print("非法输入") return False elif top in table and token_type in table[top]: stack.pop() production = table[top][token_type] # 逆序压栈，因为栈顶先出 for symbol in reversed(production): if symbol != '': stack.append(symbol) else: # 错误恢复：弹出栈顶，但不消费 token print(f"跳过非期待符号 {token_type}, 期望 {top}") stack.pop() return index == len(token_list)

这里同步 token 的选择是避坑重点：当栈顶终结符与输入 token 不匹配时，最稳妥的方式是“弹出栈顶终结符”，而不是“跳过输入 token”。因为如果输入少了一个分号，跳过 token 会让分母不断后移，错误恢复会连续报错；弹出栈顶则回到上层非终结符继续分析，错误恢复更稳。如果栈顶是非终结符且表项为空，则“跳过所有不在 FOLLOW(top) 中的输入 token”——这个操作在实验里几乎必考。

4. LR(1) 语法分析器：从项目集规范族到 action/goto 表，冲突处理是唯一难点

LR(1) 是自底向上分析的代表，它比 LL(1) 处理更多文法，但构造过程也更难：状态多、表大、冲突判断绕。实验里多数同学抄代码能跑，但被问“你的状态 I0 为什么有三个项目”就答不上来。这里把构造过程拆开。

4.1 为什么要 LR(1)：它能处理的文法比 LL(1) 宽多少

LL(1) 需要每个产生式的选择凭一个向前看 token 决定，而 LR(1) 是在“移进/归约”过程中利用最右推导的逆过程，向前看信息来自上下文状态。经典对比是：LL(1) 无法处理“悬空 else”的原始文法，但 LR(1) 可以；更典型的例子是文法S -> a A d | b A e这类需要看非终结符后面跟什么的文法，LL(1) 经常冲突，LR(1) 的向前看符号会把d和e记在状态里。实验里如果老师给了一个明显不是 LL(1) 的文法让你用 LR(1) 实现，就是在暗示你能接受更多状态。代价是 LR(1) 的状态数量可能比 LR(0) 多几倍，所以在实验报告里，我一般把状态表的行数、action 表大小列出来，说明“状态膨胀”是正常现象。

4.2 构造 LR(1) 项目集规范族：核心步骤拆解

LR(1) 项目是[A -> α·β, a]，其中a是向前看终结符。项目集闭包计算是第一步，也是最容易被忽略的一步。下面伪代码展示了closure和goto的核心逻辑：

def closure(I, grammar): J = set(I) changed = True while changed: changed = False for item in list(J): dot_rhs = item.rhs[item.dot:] if not dot_rhs: continue # 规约项目 next_symbol = dot_rhs[0] if next_symbol not in grammar.nonterminals: continue # 计算 beta a: β 是点后剩余，a 是向前看 beta_a = dot_rhs[1:] + [item.lookahead] first_beta = compute_first_of_string(beta_a, grammar) for prod in grammar.productions_for[next_symbol]: for lookahead in first_beta: new_item = Item(prod.lhs, prod.rhs, 0, lookahead) if new_item not in J: J.add(new_item) changed = True return J def goto(I, X): J = set() for item in I: if item.dot < len(item.rhs) and item.rhs[item.dot] == X: J.add(Item(item.lhs, item.rhs, item.dot + 1, item.lookahead)) return closure(J)

闭包计算的逻辑：如果项目点后面是非终结符B，则需要把所有B -> .γ项目加入当前项目集，这些新项目的向前看符号是FIRST(βa)，其中β是点后剩余符号串，a是原项目的向前看。这个FIRST(βa)的计算必须包含“β 可推出 epsilon”这条传递路径，否则你的 LR(1) 实际上退化成 LR(0)，冲突处理全错。我在实现时踩过一个坑：把beta_a写成了dot_rhs[1:] + [item.lookahead]，但忘记处理dot_rhs为空的情况，导致闭包运算永远收敛不了。所以第一行一定要判断dot_rhs是否为空，空项目没有可扩展的符号。

4.3 action 与 goto 表驱动：shift/reduce 冲突怎么处理

当所有项目集构造完成后，填表规则是：如果项目[A -> α·aβ, b]且a是终结符，则action[I][a] = shift(I_after_goto)；如果项目[A -> α·, a]且A不是开始符号，则action[I][a] = reduce(A -> α)；如果项目[S' -> S·, $]，则action[I][$] = accept。goto[I][A]用于非终结符转移。

冲突处理是 LR(1) 实验的验收核心。shift/reduce 冲突通常来自二义性文法，比如表达式文法的E -> E + E；reduce/reduce 冲突通常来自文法本身设计失误，比如两个产生式能归约成同一个非终结符且向前看集合重叠。处理办法有三个层面：第一是改写文法消除二义性，用优先级和结合性声明是最常见的做法，实验里老师往往允许你用“优先级最高的是乘除，最低的是赋值”这样的规则来解决；第二是默认移进优先，这符合大多数语言的“悬空 else”偏好；第三是打印冲突现场，输出冲突所在状态、栈上的符号序列和当前输入 token，这份冲突报告比任何代码都能让验收老师相信你是真懂的。我在处理表达式文法时，会直接给+、*标数字优先级，然后在填表冲突时比较当前终结符优先级与产生式右侧最后一个终结符的优先级，决定 shift 还是 reduce——这是 yacc/bison 内部做的事，实验里手写也能用。

5. 实验联调与避坑：从词法到语法的手写链路常见翻车点

三个模块单独写都能跑，一拼起来就崩，这是编译原理实验的最大玄学。很多同学把时间花在 debug 词法分析器上，结果问题出在模块之间的接口约定。这里列四个我每次带实验都会让学生先自查的坑。

5.1 token 流与语法分析器之间那层缓冲：为什么总是差一个字符

现象：LL(1) 分析器刚启动就报错，提示第一个 token 不对，但单独调用词法分析器却输出正常。原因：语法分析器需要“向前看一个 token”，但词法分析器已经按next_token()一次性读完整个文件并返回 token 列表，那个“超前读”的字符在列表里已经存在，可你忘了处理 eof。解决：在 LL(1) 栈驱动里，初始化时应把第一个 token 预读到lookahead变量，而不是直接token_list[index]。我的习惯是让词法分析器提供一个peek_token()接口，内部保存一个_pendingtoken，这样语法分析器可以从容实现“仅当匹配成功时消费 token”的语义。如果你没有 peek 接口，就用token_list[index]也行，但每次index += 1之后要立刻检查index是否越界，否则eof处理会漏掉。

5.2 终结符与 token 类型命名不一致的坑

现象：预测分析表里明明写了num，词法分析器返回的 token 类型是NUMBER，表驱动函数里token_type == top永远不成立。原因：实验报告里定义了 token 枚举，但词法分析器返回字符串时大小写、命名规则没有统一。解决：在项目里建立一个TokenType枚举或常量字典，词法分析器、FIRST/FOLLOW 计算、预测分析表三处都引用同一组定义。我见过最惨的情况是词法里用小写keyword，语法里文法符号用大写ID，最后排查两小时发现是大小写不一致。更隐蔽的问题是，某些实验模板里把关键字单独作为 token 类型，而文法里写if作为终结符，那么if到底是KEYWORD还是IF？我的经验是：关键字一律保留为原值终结符，比如'if'，这样文法产生式里直接写if，不需要额外映射。

5.3 空产生式处理：epsilon 到底要不要进 FOLLOW

现象：LL(1) 表构造后出现单元格冲突，比如E'遇到+同时有E' -> + T E'和E' -> ε两个产生式。原因：在计算 FOLLOW 时，没把能推出 epsilon 的非终结符的 FOLLOW 传播给左边的非终结符。比如E' -> ε时，FOLLOW(E') 应该并入 FOLLOW(T)，如果你只在A -> α B β且β为空时才传播，就漏了。解决：检查你的 FOLLOW 算法是否有两层新集合传播——一层是对A -> α B的简单并入，另一层是当 β 可空时继续向 B 之前的所有非终结符传播。更直接的办法是在 FIRST/FOLLOW 输出里，手动验证一个众所周知的结论：对文法E -> T E'，FOLLOW(E) == FOLLOW(E')；如果不相等，算法一定有漏。

5.4 递归下降与表驱动别混用：LL(1) 的预测表不是递归函数

现象：实验代码里既有predict_table又用parseE()parseT()递归函数，然后某些分支递归调用不按表来。原因：很多同学先写了递归下降风格，后来改成表驱动时只改了外层循环，内部的递归调用还残留。后果是递归下降通常不需要显式$栈，而表驱动需要；两种风格混在一起导致栈顶和调用栈不同步，程序可能死循环。解决：选一种风格做到低。如果老师要求“用预测分析表”，那么在访问表之前，所有递归函数都要禁止；如果老师只是要求 LL(1) 思想，那么递归下降里可以直接用lookahead做分支判断，不需要构造二维表。我的血泪经验是：实验验收时最怕听到“这个函数为什么自己调用自己”，因为混用代码一眼就能看出来。纯表驱动版本里除了ll1_parse没有任何函数递归，这是硬性自查标准。

6. 把三个模块串成一条命令链：trace 开关与三层验证

三个分析器都完成后，不要急着提交 zip。先做一件事：给每个模块加一个-t或verbose参数，让它们把中间过程打印出来。词法分析器打印每个 token 和行号；LL(1) 分析器打印分析栈、当前输入 token 和使用的产生式；LR(1) 分析器打印状态栈、符号栈和 shift/reduce 动作。这个 trace 开关平时关了，调试时打开，能省下大量“到底是哪一层错了”的时间。

验证方法用一个小而全的输入，我一般用下面的算术语句：

while (x + 3) * y <= 10 { x = x + 1; }

首先用词法分析器 tokenize，确认输出了while关键字、标识符x、数字3、运算符+、括号、比较运算符<=、赋值号=、分号等。然后把 token 列表分别喂给 LL(1) 分析器和 LR(1) 分析器，两者都应该返回成功。如果 LL(1) 失败，先检查是否因为<=在词法里被拆成了<和=；如果 LR(1) 失败，先检查赋值语句的语法规则是否与产生式完全一致。我最终的实验习惯是：写一个run_all.py调用三个模块，并把所有 trace 输出到debug.log，交报告时只展示正常模式的结果，但附上debug.log的部分截图证明调试过程真实。这种“可追溯”的完成方式，比只给一个能跑的黑匣子更能扛住验收提问。希望帮到你。

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