编译原理实验：LR分析器从文法到分析表的完整实现与踩坑指南

1. 从"能跑就行"到"知道为什么能跑"：LR分析到底在解决什么问题

如果你正在做编译原理的实验，大概率已经写完了词法分析器，手里攥着一串Token，然后卡在了语法分析这一关。递归下降法你可能已经试过了，写起来直观，但遇到左递归文法就得吭哧吭哧改写成右递归，改完发现语义变了，又得绕回来。更别提回溯带来的性能问题——一个稍微复杂点的表达式文法，递归下降跑起来就像在迷宫里瞎撞。

LR分析就是来终结这种痛苦的。它的全称是Left-to-right scan, Rightmost derivation in reverse，翻译成人话就是：从左到右扫描输入串，构造最右推导的逆过程。听起来很绕对吧？换个说法你就明白了——LR分析器本质上是在模拟一个"移进-归约"的过程，它一边读入Token，一边维护一个状态栈，当栈顶的符号串匹配某条产生式的右部时，就把它归约成左部的非终结符。整个过程不需要回溯，每个Token只扫描一遍，时间复杂度是线性的。

我第一次接触LR分析的时候，最大的困惑是：它怎么知道什么时候该移进、什么时候该归约？答案藏在分析表里。这张表是LR分析器的灵魂，它由两部分组成：ACTION表和GOTO表。ACTION表告诉你在某个状态下遇到某个终结符该做什么（移进、归约、接受还是报错），GOTO表告诉你在某个状态下归约完某个非终结符后该跳到哪个状态。这两张表合起来，就是一个确定性的有限自动机，驱动着整个分析过程。

那这张表怎么来的？这就是LR分析的核心难点。根据构造方法的不同，LR分析分为几个层级：LR(0)、SLR(1)、LALR(1)和LR(1)。它们的能力从弱到强，构造复杂度也从低到高。LR(0)最简单，但冲突多；SLR(1)用Follow集解决了部分冲突；LALR(1)通过合并同心项目集进一步压缩表的大小，同时保持了大部分分析能力；LR(1)最精确，但状态数可能爆炸。实际工程中，LALR(1)是使用最广泛的，Yacc和Bison默认生成的就是LALR(1)分析表。

这个实验的价值在于，它逼着你亲手走一遍从文法到分析表的完整流程。你会真正理解什么是项目集闭包、什么是有效项目、什么是移进-归约冲突和归约-归约冲突，以及为什么有些文法天生就不适合LR分析。这些概念在课堂上听老师讲是一回事，自己动手实现一遍完全是另一回事。我见过太多人考试能默写LR分析表的构造步骤，但真让他写代码实现，连First集和Follow集都算不对。

所以这篇内容适合谁？如果你正在做编译原理实验，需要实现一个LR分析器，那这篇就是为你写的。如果你已经实现了但跑不通，想搞清楚哪里出了问题，这篇也能帮你排查。如果你只是想把LR分析的理论搞扎实，为后续的课程设计或面试做准备，同样可以跟着走一遍。我会从文法预处理开始，一步步带你构造项目集规范族、生成分析表、实现驱动程序，最后用几个典型文法做测试验证。过程中会重点讲那些"教科书上不会写但实际一定会踩"的坑。

2. 文法预处理：为什么你的First集和Follow集总是算错

2.1 文法读入与数据结构设计

在动手构造分析表之前，第一件事是把文法读进来，并且用一种方便后续操作的数据结构存起来。很多同学在这一步就埋下了隐患——用字符串直接存产生式，后面每次要用的时候再解析，结果代码里到处是split和substring，不仅容易出错，调试起来也痛苦。

我的建议是，读入阶段就做好结构化解析。每条产生式存成一个对象，包含左部非终结符和右部符号序列。右部用列表存，每个元素是一个符号对象，标记它是终结符还是非终结符。这样后续计算First集、求闭包、做归约的时候，直接遍历列表就行，不需要反复解析字符串。

具体来说，你可以定义一个Symbol类，包含name和isTerminal两个属性。再定义一个Production类，包含lhs（左部）和rhs（右部符号列表）。整个文法就是一个Production的列表，外加一个开始符号。开始符号通常是文法的第一条产生式的左部，但为了统一处理，建议人为增广文法——引入一个新的开始符号S'，添加产生式S' -> S。这一步非常关键，后面判断"接受"动作就靠它。

增广文法还有一个好处：它保证了开始符号不会出现在任何产生式的右部，这样在构造项目集的时候，初始项目[S' -> .S]的闭包就是整个规范族的起点，逻辑上干净很多。

读入的时候还要注意处理空产生式（ε产生式）。有些文法的产生式右部是空的，比如A -> ε。在数据结构里，空右部就是一个空列表。计算First集的时候，空产生式意味着First(A)要包含ε，这个逻辑要单独处理，否则后面算Follow集的时候会漏掉。

注意：文法的输入格式最好统一约定，比如用"->"分隔左右部，用空格分隔右部符号，用"|"表示或。写一个简单的解析器就行，不要在这个环节花太多时间，但一定要保证解析结果是结构化的。

2.2 First集计算：递归与迭代的取舍

First集的定义很直白：First(α)是α能推导出的所有可能的开头终结符的集合，如果α能推导出空串，那ε也在First(α)里。但实现的时候，很多同学会写成递归，然后遇到左递归就栈溢出了。

正确的做法是用迭代法。先把所有非终结符的First集初始化为空集，然后反复扫描所有产生式，根据右部不断更新左部的First集，直到整个集合不再变化为止。这个过程一定会收敛，因为First集的大小有上界（就是所有终结符加上ε）。

具体算法是这样的：对于每条产生式A -> X1 X2 ... Xn，从左到右扫描右部。对于每个Xi，如果Xi是终结符，把Xi加入First(A)，然后停止扫描；如果Xi是非终结符，把First(Xi)中除了ε之外的所有元素加入First(A)，如果ε不在First(Xi)中，停止扫描，否则继续看下一个符号。如果所有符号都能推导出ε，那把ε也加入First(A)。

这个逻辑看起来简单，但有一个容易忽略的点：当Xi是非终结符且First(Xi)包含ε时，你要继续看下一个符号，而不是直接停止。很多同学在这里写错，导致First集算出来偏小，后面构造分析表的时候就会出现莫名其妙的冲突。

还有一个细节：如果右部第一个符号就是非终结符，而且它的First集还没算完，那这一轮就不能得到最终结果。所以必须反复迭代，直到某一轮没有任何First集发生变化。我一般会用一个changed标志位来控制循环，每轮开始设为false，只要有更新就设为true，一轮下来如果还是false就退出。

2.3 Follow集计算：那些年我们漏掉的$符号

Follow集的定义是：Follow(A)是在某个句型中紧跟在A后面的终结符的集合。如果A是某个句型的最右符号，那结束符$也在Follow(A)里。Follow集在SLR(1)分析表的构造中用来解决归约冲突——当我们要把栈顶归约成A的时候，只有当前输入符号在Follow(A)里，才能确认这个归约是合法的。

计算Follow集的算法也是迭代的。首先把$加入Follow(开始符号)。然后对于每条产生式A -> αBβ，把First(β)中除了ε之外的所有元素加入Follow(B)。如果β能推导出ε（或者β本身就是空的），那把Follow(A)也加入Follow(B)。

这里最容易出错的地方有两个。第一个是忘记处理β为空的情况。当B是产生式右部的最后一个符号时，β就是空串，这时候要直接把Follow(A)加入Follow(B)。很多同学只考虑了β非空的情况，导致Follow集偏小，归约的时候该归约的地方不归约，分析器直接报错。

第二个容易错的地方是First(β)包含ε时的处理。如果First(β)里有ε，说明β可以推导出空串，那B后面实际上跟的就是A后面的符号，所以Follow(A)也要加入Follow(B)。这个逻辑和First集计算中"继续看下一个符号"是类似的，但很多人在Follow集这里就忘了。

我建议在实现的时候，把"计算First(β)并判断是否包含ε"封装成一个函数，这样在Follow集计算中直接调用，逻辑清晰，也不容易漏。

2.4 用表格验证你的First和Follow集

算完First和Follow集之后，不要急着往下走。先用手算几个简单文法验证一下，确保你的程序输出和手算结果一致。我推荐用经典的表达式文法做测试：

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

这个文法的First和Follow集是：

如果你算出来的结果和这个不一致，那后面构造分析表一定会出问题。特别是Follow集，很多同学算出来会漏掉某些符号，比如T的Follow集里漏掉*，或者F的Follow集里漏掉+。这些错误在构造SLR分析表的时候会直接导致归约动作缺失，分析器遇到某些输入就卡住了。

提示：如果你的文法包含ε产生式，验证的时候要特别注意。比如文法S -> A B, A -> ε | a, B -> b，那First(A) = {ε, a}，First(S) = {a, b}，Follow(A) = {b}，Follow(S) = {$}。把这些边界情况都测一遍，确保你的实现是健壮的。

3. 项目集规范族构造：闭包和GOTO到底在干什么

3.1 LR(0)项目与项目集闭包

LR分析的核心概念是"项目"。一个项目就是在产生式右部的某个位置加一个点，表示"我们已经看到了这个位置之前的符号"。比如产生式E -> E + T，对应的项目有四个：E -> .E + T、E -> E. + T、E -> E + .T、E -> E + T.。点在最左边表示还没开始匹配，点在最右边表示已经匹配完了，可以做归约了。

项目集就是一组项目的集合。闭包运算的作用是：如果项目集里有一个项目A -> α.Bβ，那所有以B为左部的产生式对应的初始项目（点在最左边的）都应该加入这个项目集。因为当你在等待B出现的时候，B可能由任何一条以B为左部的产生式推导出来，所以这些可能性都要考虑进去。

闭包的计算是一个递归过程。先把当前项目集里的所有项目加入结果集，然后反复扫描结果集，对于每个点后面是非终结符的项目，把该非终结符的所有产生式的初始项目加入结果集，直到结果集不再变化。这个过程和计算First集类似，也是迭代到不动点。

我见过很多同学在实现闭包的时候，用递归函数，然后遇到递归文法就无限递归了。比如E -> E + T，闭包里会有E -> .E + T，然后又会触发E -> .E + T的闭包，无限循环。正确的做法是用一个visited集合记录已经处理过的项目，或者用迭代法，每次只处理新加入的项目。

3.2 GOTO函数：状态转移的驱动力

GOTO函数的作用是：给定一个项目集I和一个文法符号X，返回所有形如A -> αX.β的项目组成的闭包，其中A -> α.Xβ在I中。说白了，就是"如果当前状态在等待X，那读完X之后应该转到哪个状态"。

计算GOTO的步骤很清晰：先找出I中所有点后面是X的项目，把这些项目的点向右移动一位，得到一个新的项目集（还没算闭包），然后对这个新项目集求闭包，结果就是GOTO(I, X)。

这里有一个细节：点向右移动一位之后，如果点已经在最右边了，那这个项目就是归约项目，不需要再求闭包了。但为了统一处理，你可以先把所有移动后的项目收集起来，再统一求闭包。闭包函数里对于归约项目不做任何额外处理，这样逻辑上更简洁。

构造项目集规范族的算法就是一个广度优先搜索。从初始项目集closure({S' -> .S})开始，对于每个已发现的项目集I，对每个文法符号X（包括终结符和非终结符），计算GOTO(I, X)。如果结果非空且不在已发现的项目集列表中，就加入列表，继续处理。直到所有项目集都处理完毕。

3.3 项目集规范族的可视化与调试

构造出来的项目集规范族可能有几十个状态，光看数字很难理解它们之间的关系。我强烈建议在实现的时候，把每个项目集的内容打印出来，并且给每个状态编号。这样在调试分析表的时候，你能清楚地看到每个状态包含哪些项目，为什么某个动作会被填成移进或归约。

一个典型的LR(0)项目集规范族输出大概长这样：

State 0: S' -> .E E -> .E + T E -> .T T -> .T * F T -> .F F -> .( E ) F -> .id State 1: S' -> E. E -> E. + T State 2: E -> T. T -> T. * F ...

通过这种输出，你可以直观地看到状态之间的转移关系。比如State 0遇到E转到State 1，遇到T转到State 2，遇到F转到State 3，遇到(转到State 4，遇到id转到State 5。这些转移关系就是GOTO表的内容。

调试的时候，重点检查两类状态：一类是包含归约项目的状态，另一类是同时包含移进项目和归约项目的状态（这就是冲突状态）。对于归约项目，你要确认它的Follow集计算是否正确；对于冲突状态，你要分析冲突的类型和原因。

3.4 冲突的识别与分类

在构造项目集规范族的过程中，冲突会自然浮现出来。冲突主要有两种：

移进-归约冲突：一个项目集里既有移进项目（点后面是终结符），又有归约项目（点在最后）。这意味着分析器在当前状态下，既可以移进下一个符号，也可以把栈顶符号归约。经典的例子是悬空else问题：if E then S | if E then S else S。在某个状态下，遇到else时，既可以移进else（匹配最近的if），也可以归约已经看到的if-then-S（匹配更早的if）。

归约-归约冲突：一个项目集里有两个不同的归约项目。这意味着分析器不知道该按哪条产生式归约。这种冲突通常说明文法有二义性，或者不是LR文法。

识别冲突之后，你需要判断这个文法属于哪一类LR文法。如果没有任何冲突，那它是LR(0)文法。如果有移进-归约冲突，但通过SLR(1)的Follow集能解决，那它是SLR(1)文法。如果SLR(1)解决不了但LALR(1)能解决，那它是LALR(1)文法。如果都不行，那它就不是LR文法，需要改写文法或者换用其他分析方法。

注意：冲突不一定是坏事。有些冲突可以通过优先级和结合性规则来解决，Yacc和Bison就支持这种机制。但在实验里，我建议先老老实实按照SLR(1)或LALR(1)的标准流程走一遍，理解冲突的本质，再考虑用优先级规则来简化。

4. 分析表构造：ACTION表和GOTO表的填充逻辑

4.1 SLR(1)分析表的构造规则

SLR(1)分析表的构造比LR(0)多了一个Follow集的判断，正是这个判断解决了很多移进-归约冲突。具体规则如下：

对于每个项目集Ii：

• 如果项目A -> α.aβ在Ii中，且GOTO(Ii, a) = Ij，其中a是终结符，那ACTION[i, a] = shift j。
• 如果项目A -> α.在Ii中，那对于所有a属于Follow(A)，ACTION[i, a] = reduce A -> α。这里A不能是增广文法的开始符号S'。
• 如果项目S' -> S.在Ii中，那ACTION[i, $] = accept。

对于GOTO表：

• 如果GOTO(Ii, A) = Ij，其中A是非终结符，那GOTO[i, A] = j。

这里的关键点是：归约动作只填在Follow(A)对应的列上，而不是整行都填。这就是SLR(1)比LR(0)强的地方——LR(0)不管当前输入是什么，只要栈顶匹配就归约，容易产生冲突；SLR(1)多看了一眼输入符号，只有输入符号在Follow(A)里才归约，大大减少了冲突。

但SLR(1)也不是万能的。有些冲突是因为Follow集太大导致的，明明某个输入符号在Follow(A)里，但在当前上下文中它不应该触发归约。这时候就需要LALR(1)或LR(1)了，它们用更精确的展望符集合来替代Follow集。

4.2 冲突解决：优先级与结合性的实战应用

在实际实现中，你可能会遇到SLR(1)解决不了的冲突。这时候有两个选择：一是改写文法，二是用优先级和结合性规则。

改写文法是最彻底的办法，但往往会让文法变得面目全非，可读性急剧下降。比如表达式文法，为了消除二义性，你需要引入多个非终结符来区分不同优先级的运算符，产生式数量会翻倍。

用优先级和结合性规则则简单得多。你只需要给每个终结符指定优先级和结合性，然后在遇到移进-归约冲突时，比较栈顶归约项目的优先级和当前输入符号的优先级：如果输入符号优先级高，就移进；如果归约项目优先级高，就归约；如果优先级相同，根据结合性决定（左结合归约，右结合移进）。

具体实现的时候，你可以在分析表构造阶段就解决冲突，把决定好的动作直接填入表中。这样驱动程序就不需要再做判断了，运行效率更高。我一般会在文法定义的时候，用一个map存储每个终结符的优先级和结合性，然后在填表的时候查这个map。

4.3 分析表的存储与压缩

分析表可能很大，特别是对于复杂的文法。一个状态数上百、终结符和非终结符各几十个的文法，分析表可能有几千个条目。如果直接用二维数组存，内存占用会比较大。实际工程中，通常会用稀疏矩阵或者行压缩的方式来存储。

但在实验里，我建议先用二维数组或哈希表存，把逻辑跑通再说。二维数组的优点是访问快，调试方便，你可以直接打印整个表来看。哈希表的优点是节省空间，但调试的时候需要遍历，稍微麻烦一点。

如果你用的是Python，可以用字典嵌套字典的方式：action[state][symbol] = ('shift', next_state)或('reduce', production_id)。这样查表的时候直接两层索引就行，代码很简洁。如果你用的是C++或Java，可以用vector<vector >或者unordered_map来存。

不管用什么方式，建议在填表的时候加一些断言检查，比如同一个格子不能被填两次（除非是冲突解决后的覆盖），归约动作的Follow集判断是否正确，等等。这些检查能帮你在早期发现逻辑错误。

4.4 用表达式文法验证分析表

构造完分析表之后，用经典的表达式文法验证一下。输入id + id * id，手动模拟一下分析过程，看看分析表给出的动作序列是否正确。

正确的动作序列应该是这样的：

如果你模拟出来的动作序列和这个不一致，那说明分析表构造有问题。重点检查Follow集的计算和归约动作的填充。特别是第9步，遇到的时候应该移进而不是归约，因为的优先级比+高，而且*在Follow(T)里但不在Follow(E)里，SLR(1)应该能正确区分。

5. 驱动程序实现：移进-归约的完整流程

5.1 驱动程序的核心循环

驱动程序是整个LR分析器的执行引擎，它的逻辑其实很简单：维护一个状态栈和一个符号栈，每次看栈顶状态和当前输入符号，查ACTION表决定下一步动作。如果是移进，把输入符号和下一个状态压栈，输入指针后移；如果是归约，按产生式右部的长度弹出相应数量的符号和状态，然后查GOTO表决定新状态压栈；如果是接受，分析成功；如果是报错，分析失败。

这个循环看起来简单，但实现的时候有几个细节容易出错。

第一个细节是归约时的弹栈数量。如果产生式是A -> ε，右部长度为0，那不需要弹栈，直接查GOTO表压入新状态。很多同学在实现的时候，用for i in range(len(rhs))来弹栈，当rhs为空时循环不执行，这是对的。但符号栈和状态栈要同步弹出，不能只弹一个。

第二个细节是GOTO表的查询。归约完之后，你需要用归约后的非终结符A和当前栈顶状态去查GOTO表。注意，弹栈之后栈顶状态已经变了，要用新的栈顶状态去查，而不是归约前的状态。

第三个细节是接受动作的判断。接受动作只在ACTION表中出现一次，就是当状态栈顶是包含S' -> S.的状态，且输入符号是$的时候。这时候直接返回成功，不需要再做任何操作。

5.2 错误恢复：不要一报错就退出

很多同学实现的LR分析器，一遇到ACTION表里没有对应动作就直接报错退出。这在实验里勉强能用，但实际工程中，错误恢复是非常重要的。一个健壮的语法分析器应该能在发现错误后，尝试恢复并继续分析，尽可能多地发现后续的错误。

最简单的错误恢复策略是"恐慌模式"：当发现错误时，不断弹出状态栈，直到找到一个能接受当前输入符号的状态，然后继续分析。这种策略实现简单，但可能会跳过很多正确的输入。

更精细的策略是"短语级恢复"：在分析表里预留一些错误处理条目，当遇到特定错误时，执行预定义的动作，比如插入一个缺失的符号、删除一个多余的符号、或者替换一个错误的符号。这种策略需要你在构造分析表的时候额外处理，实验里可以不要求，但了解一下思路是好的。

我建议在实验里至少实现一个简单的错误提示，告诉用户在第几个Token处发现了什么错误，当前状态是什么，期望的输入是什么。这样调试的时候会方便很多。

5.3 分析过程的日志输出

调试LR分析器的时候，最有效的手段就是打印完整的分析过程。每一步的状态栈、符号栈、剩余输入、执行的动作，都打印出来。这样一旦结果不对，你可以逐步对比，找到出错的步骤。

日志的格式可以设计成表格形式，每列对齐，方便阅读。比如：

Step State Stack Symbol Stack Input Action 1 0 id + id * id $ shift 5 2 0 5 id + id * id $ reduce F -> id 3 0 3 F + id * id $ reduce T -> F ...

这种日志不仅能帮你调试，还能作为实验报告的一部分，展示你对LR分析过程的理解。我当年做实验的时候，就是靠这种日志发现了一个Follow集计算的bug——在某个状态下，本该归约的地方没有归约，对比日志才发现是Follow集漏了一个符号。

5.4 用多个文法测试驱动程序的健壮性

不要只用一个表达式文法测试。我建议至少准备三组测试用例：

第一组是经典的表达式文法，测试基本的移进-归约逻辑和优先级处理。输入可以包括id、id + id、id * id、( id + id ) * id等，覆盖各种组合。

第二组是包含ε产生式的文法，测试空串的处理。比如S -> A B, A -> ε | a, B -> b，输入b应该能正确分析（A推导出ε），输入a b也应该能正确分析。

第三组是包含冲突的文法，测试冲突解决机制。比如悬空else文法，输入if E then if E then S else S，看看你的分析器是把else匹配给最近的if还是最远的if。如果实现了优先级规则，还可以测试不同优先级下的行为。

每换一个文法，都要重新检查First集、Follow集、项目集规范族和分析表。这个过程很繁琐，但能帮你发现很多隐藏的bug。我当年就是换了三组文法之后，才发现自己的闭包函数在处理递归文法时有无限递归的问题。

6. 那些实验指导书不会告诉你的踩坑经验

6.1 闭包计算中的无限递归陷阱

闭包计算是LR分析器实现中最容易出bug的地方。问题的根源在于递归文法：当项目集里有一个项目A -> .Bβ，而B又能推导出以A开头的串时，闭包计算就会无限展开。

比如文法A -> B a, B -> A b | c，初始项目A -> .B a，闭包里会有B -> .A b，然后又会触发A -> .B a的闭包，如此循环。如果你用朴素的递归实现，程序直接栈溢出。

正确的做法是用一个visited集合记录已经加入闭包的项目。每次准备加入一个新项目之前，先检查它是否已经在集合里。如果已经在，就跳过；如果不在，加入并继续处理。这样每个项目最多被处理一次，闭包计算一定终止。

这个坑我踩过两次。第一次是写递归的时候没加visited，第二次是加了visited但用错了地方——我在递归调用之后才检查visited，结果还是无限递归。正确的顺序是：进入函数先检查visited，如果已访问直接返回；否则标记visited，然后处理。

6.2 Follow集计算中遗漏$符号的连锁反应

Follow集里忘记加$符号，是一个看似很小但影响很大的错误。$符号是输入串的结束标记，如果Follow集里没有$，那在分析到输入末尾的时候，本该归约的动作就不会被执行，分析器会报错说遇到了意外的$。

更隐蔽的是，这个错误可能不会在所有测试用例上暴露。比如输入id + id，分析到最后一步归约E -> E + T的时候，如果Follow(E)里没有$，那ACTION表里对应$的那一列就是空的，分析器会报错。但如果你只测试了id，可能不会触发这个路径，因为id在更早的阶段就被归约完了。

所以我的建议是：在计算Follow集的时候，第一件事就是把$加入开始符号的Follow集。然后在每次迭代更新的时候，都检查一下$是否还在。如果发现$丢了，那一定是某次更新的时候覆盖了整个集合，而不是追加。

6.3 分析表冲突的调试方法论

遇到分析表冲突的时候，不要慌。先打印出冲突的状态和项目集，看看是哪种冲突。如果是移进-归约冲突，检查一下归约项目的Follow集，看看冲突的输入符号是否真的在Follow集里。如果在，那说明SLR(1)解决不了，需要考虑LALR(1)或者用优先级规则。如果不在，那说明你的Follow集算错了。

如果是归约-归约冲突，那通常意味着文法有二义性，或者你的项目集构造有问题。检查一下是否有两个不同的产生式在同一个状态下都完成了匹配。如果是文法本身的问题，可能需要改写文法；如果是实现的问题，重点检查闭包和GOTO的计算。

我一般会用二分法来定位冲突的来源。先把文法简化到最小，看看冲突是否还存在。如果不存在了，逐步加回产生式，直到冲突重新出现。这样就能定位到是哪条产生式导致的冲突。

6.4 性能优化：从能跑到跑得快

实验里的文法通常不大，性能不是问题。但如果你想把LR分析器用到实际项目中，性能就很重要了。分析表的查询是热点操作，每次移进或归约都要查表。用二维数组查表是O(1)的，但内存占用大；用哈希表省内存，但查询有常数开销。

一个常用的优化技巧是把ACTION表和GOTO表合并成一个表，用整数编码动作类型和参数。比如用正数表示移进状态，负数表示归约产生式编号，0表示接受，特殊值表示报错。这样只需要一个二维数组就能存下所有信息，查表的时候一次索引就行。

另一个优化是预计算归约产生式的右部长度。每次归约都要弹栈，弹栈数量就是右部长度。如果在构造分析表的时候就把这个长度存下来，归约的时候直接查，不需要再遍历产生式。

这些优化在实验里不是必须的，但如果你想让自己的实现更专业，可以尝试一下。我当年做完实验之后，花了一个下午把分析表压缩成了两个一维数组加一个偏移数组，查询速度提升了将近一倍，虽然实验评分不会因此更高，但自己心里很爽。

6.5 从LR分析器到实际编译器的距离

最后说一点个人体会。LR分析器是编译原理实验里最核心也最难的部分，但把它跑通只是第一步。实际的编译器里，语法分析器还需要和词法分析器紧密配合，处理符号表、类型检查、错误恢复、代码生成等一系列问题。LR分析器只是其中的一个组件，虽然重要，但不是全部。

如果你对编译原理真的感兴趣，我建议在完成LR分析器之后，尝试把它和一个简单的词法分析器、一个简单的语义分析器串起来，做一个能处理小型语言的完整编译器。这个过程会让你对编译的整个流程有更深刻的理解，也会让你发现LR分析器在实际使用中的局限性——比如它很难处理需要上下文信息的语法结构，这时候就需要属性文法或者语法制导翻译来补充。

LR分析这个知识点，面试的时候也经常被问到。面试官不会让你现场构造分析表，但会问你LR(0)、SLR(1)、LALR(1)的区别，移进-归约冲突怎么解决，为什么LALR(1)比SLR(1)强。如果你亲手实现过一遍，这些问题回答起来会非常有底气，因为你知道每个概念背后的具体操作和实际效果，而不是死记硬背定义。