企业官网建设流程全解析

1. 语法分析的核心定位与自底向上思路拆解

语法分析在编译流程里处在词法分析之后、语义分析之前，任务是把词法分析产出的记号流（Token Stream）按照语言的文法规则组装成语法树或语法结构。词法分析负责识别“单词”，语法分析负责判断“句子”是否合法，并给出结构。很多初学者在这一步会卡住，因为词法分析的结果是一串线性记号，而语法分析要把它还原成层次结构，这中间的思维跨度不小。

自底向上的分析思路和自顶向下正好相反。自顶向下是从文法的开始符号出发，试图推导出输入串；自底向上则是从输入串出发，试图归约到文法的开始符号。你可以把它想象成搭积木：自顶向下是先画图纸再找零件，自底向上是先拿到一堆零件，然后不断把能拼在一起的小零件合并成大零件，直到拼出完整模型。移入-归约分析就是自底向上分析最主流的实现方式，LR(0)分析法又是移入-归约分析里最基础、最容易理解的一种。

为什么先学LR(0)？因为它是LR系列分析法的起点。LR(0)的“0”表示在做出归约决策时不需要向前看任何输入符号，只看当前栈顶状态就能决定动作。这个限制让LR(0)的能力比较弱，很多实际语言的文法它处理不了，但它的构造过程清晰、自动机模型直观，是理解SLR(1)、LALR(1)、LR(1)的必经之路。你把LR(0)的自动机构造和冲突分析搞明白了，后面加向前看符号只是在这个骨架上做增量修改。

这篇文章适合正在学编译原理的在校学生、准备考试需要梳理知识点的同学，以及工作中需要自己写解析器但没系统学过形式语言与自动机的开发者。我会从移入-归约的基本动作讲起，把LR(0)自动机的构造过程一步步拆开，重点讲清楚项目集闭包怎么算、GOTO函数怎么求、分析表怎么填，最后给出一个可以手算复现的完整例子。所有步骤都按我实际做题和写代码时的操作顺序来，不跳步。

2. 移入-归约分析的基本动作与栈式结构

2.1 四个核心动作：移入、归约、接受、报错

移入-归约分析器维护一个栈和一个输入缓冲区。栈里放的是已经处理过的文法符号和状态，输入缓冲区里是还没处理的记号流。分析器根据当前栈顶状态和输入符号决定下一步做什么，一共有四种动作。

移入（Shift）就是把输入缓冲区最左边的记号压入栈，同时把该记号对应的状态也压入栈。归约（Reduce）是发现栈顶的若干个符号正好匹配某个产生式的右部时，把这些符号弹出，然后把产生式左部的非终结符压入栈，同时根据GOTO表压入新状态。接受（Accept）是当栈里只剩下开始符号且输入缓冲区为空时，宣布分析成功。报错（Error）是遇到无法处理的情况，说明输入串不符合文法。

这四个动作里，归约是最容易出问题的地方。因为栈顶可能有多个候选的可归约串，选错了就会导致分析失败。LR(0)分析法通过构造确定的有穷自动机来保证在任何一个状态下，归约动作是唯一确定的，或者至少能检测出冲突。

2.2 为什么用栈而不是递归

自顶向下分析通常用递归下降，因为推导过程天然是递归的。自底向上分析用栈，因为归约过程是“后进先出”的。你想想，最内层的短语总是最后被识别，但最先被归约。比如表达式a + b * c，乘法优先级高，所以b * c先归约成E，然后a + E再归约。这个顺序正好和栈的后进先出一致。

用栈还有一个好处是状态可以显式地存在栈里，不需要靠函数调用栈隐式维护。这样分析表的驱动循环就是一个简单的while循环，每次读栈顶状态和输入符号，查表，执行动作。代码写起来很直接，调试也方便，你可以把每一步的栈内容和输入位置打出来看。

2.3 句柄的概念与归约时机的判断

自底向上分析的核心问题是：什么时候该归约，归约哪一段。形式语言里用“句柄”（Handle）来定义这个时机。一个右句型的句柄是这样一个子串：它和某个产生式的右部匹配，并且把它归约成左部之后，得到的仍然是右句型。

句柄的形式化定义有点绕，但你可以这样理解：句柄就是当前最应该被归约的那一段，归约它不会破坏后续分析的可能性。在LR(0)分析里，句柄的识别不是靠扫描整个栈去找，而是靠自动机的状态来隐式标记。当自动机走到某个状态，该状态对应的项目集里有一个项目是“归约项目”（圆点在最右边），并且没有移入冲突，那就执行归约。

这里有个关键点：LR(0)只看状态，不看输入符号。所以如果同一个状态里既有归约项目又有移入项目，就产生了移入-归约冲突。如果同一个状态里有两个不同的归约项目，就产生了归约-归约冲突。冲突是LR(0)能力不足的直接体现，也是后面SLR(1)要解决的问题。

3. LR(0)项目与自动机构造的核心细节

3.1 LR(0)项目的定义与四种形态

LR(0)项目就是在产生式右部的某个位置加一个圆点，表示分析进行到了哪里。比如产生式A -> XYZ，对应的项目有四个：A -> ·XYZ、A -> X·YZ、A -> XY·Z、A -> XYZ·。圆点左边的部分表示已经识别并压入栈的符号，圆点右边的部分表示还期待看到的符号。

根据圆点的位置，项目分为四类。移入项目是圆点后面还有终结符的项目，比如A -> X·aY，表示下一步应该移入a。待约项目是圆点后面是非终结符的项目，比如A -> X·BY，表示下一步应该先处理B的产生式。归约项目是圆点在最右边的项目，比如A -> XYZ·，表示这个产生式的右部已经完整识别，可以归约了。接受项目是特殊项目S' -> S·，其中S'是增广文法的开始符号。

增广文法是在原文法基础上加一个产生式S' -> S，其中S是原文法的开始符号。加这个产生式是为了让接受动作有唯一的标志，避免和普通归约混淆。这个技巧在所有LR分析法的构造里都会用到。

3.2 项目集闭包的计算方法

闭包（Closure）是LR(0)自动机构造里最核心的操作。给定一个项目集I，它的闭包CLOSURE(I)是这样算的：先把I本身放进去，然后对于I里每一个待约项目A -> α·Bβ，把B的所有产生式对应的初始项目B -> ·γ加进去。重复这个过程直到没有新项目可以加。

我实际手算的时候会这样做：先列出初始项目，然后找圆点后面是非终结符的项目，把这些非终结符的产生式全部展开，圆点放在最左边。展开之后再看新加进来的项目里有没有圆点后面还是非终结符的，有就继续展开。这个过程有点像广度优先搜索，一层一层往外扩。

举个例子，假设文法有产生式E -> E + T | T，T -> T * F | F，F -> ( E ) | id。初始项目是S' -> ·E。闭包里先有S' -> ·E，圆点后面是E，所以把E -> ·E + T和E -> ·T加进去。然后E -> ·T圆点后面是T，把T -> ·T * F和T -> ·F加进去。再然后T -> ·F圆点后面是F，把F -> ·( E )和F -> ·id加进去。最后没有新的待约项目了，闭包计算结束。

注意：闭包计算时不要重复添加已经存在的项目。手算时建议用集合的写法，每加一个项目就检查是否已经在集合里。写代码时用哈希集合去重。

3.3 GOTO函数与状态转移的确定

GOTO函数描述的是：从项目集I出发，遇到文法符号X之后，圆点越过X形成的新项目集。具体操作是：找出I里所有圆点后面是X的项目，把圆点向右移动一位，得到一批新项目，然后对这批新项目求闭包，结果就是GOTO(I, X)。

这个操作对应自动机里的状态转移。你可以把每个项目集看作自动机的一个状态，GOTO函数就是状态之间的边。边的标签是文法符号，可能是终结符也可能是非终结符。终结符上的转移对应移入动作，非终结符上的转移对应归约之后的状态跳转。

构造自动机的完整流程是：从初始项目集的闭包开始，把它作为状态0。然后对状态0里的每个文法符号X，计算GOTO(0, X)，如果结果非空且不在已有状态集合里，就作为新状态加进去。然后对新状态重复这个过程，直到没有新状态产生。这个过程和子集构造法把NFA转DFA非常像，本质上都是在做状态集的幂集构造。

3.4 项目集规范族的完整构造流程

项目集规范族就是所有状态的集合。我手算的时候会用一个表格来跟踪，列是状态编号，行是文法符号，表格里填GOTO的结果。具体步骤是这样的：

1. 写出增广文法，给每个产生式编号。
2. 计算初始项目集I0 = CLOSURE({S' -> ·S})。
3. 对I0里的每个文法符号X，计算GOTO(I0, X)，非空的作为新状态。
4. 对每个新状态重复步骤3，直到不再产生新状态。
5. 把所有状态和转移整理成自动机图或表格。

这里有个经验：文法符号的处理顺序会影响你手算时状态的编号，但不影响最终结果。我习惯先处理终结符再处理非终结符，因为终结符上的转移通常对应移入动作，比较直观。另外，如果某个GOTO结果和已有状态的项目集完全相同，就复用那个状态，不要新建。

4. LR(0)分析表的构建与冲突处理

4.1 分析表的行列结构与ACTION/GOTO分区

LR(0)分析表是一个二维表，行是状态编号，列分为两部分：ACTION列对应终结符和结束符$，GOTO列对应非终结符。ACTION表里填的是移入、归约、接受或报错动作，GOTO表里填的是状态编号。

ACTION表的填写规则是这样的：对于状态i，如果GOTO(i, a) = j且a是终结符，那么ACTION[i, a] = shift j。如果状态i里有归约项目A -> α·，那么对于所有终结符a（包括$），ACTION[i, a] = reduce A -> α。如果状态i里有接受项目S' -> S·，那么ACTION[i, $] = accept。

GOTO表的填写规则是：如果GOTO(i, A) = j且A是非终结符，那么GOTO[i, A] = j。GOTO表里不需要填报错，因为非终结符上的转移只在归约之后发生，如果归约后的状态跳转不存在，说明文法有问题。

4.2 移入-归约冲突与归约-归约冲突的识别

冲突发生在同一个表项被要求填多个动作的时候。移入-归约冲突是某个状态里既有移入项目又有归约项目，导致ACTION[i, a]既要填移入又要填归约。归约-归约冲突是某个状态里有两个不同的归约项目，导致ACTION[i, a]要填两个不同的归约动作。

LR(0)分析法对冲突的处理策略是：如果发生冲突，说明这个文法不是LR(0)文法，需要换用更强的分析方法。但在实际构造中，你可以通过检查冲突来理解文法的哪些地方导致了不确定性。比如表达式文法里，E -> E + T和T -> T * F在某个状态下可能同时要求归约和移入，这就是优先级和结合性需要解决的问题。

我踩过的一个坑是：手算时容易漏掉某些归约项目，导致冲突没被发现，最后分析表填错了。避免的方法是每次填ACTION表之前，先把每个状态里的项目分类列出来，移入项目、待约项目、归约项目分别有哪些，然后对照规则填。填完之后再检查一遍有没有表项被覆盖。

4.3 基于自动机填表的完整操作步骤

填表的操作顺序我建议这样：先画自动机，标出所有状态和转移。然后对每个状态，列出它的项目集。接着先填GOTO表，因为GOTO表只依赖非终结符上的转移，不容易冲突。再填ACTION表的移入部分，对应终结符上的转移。最后填ACTION表的归约部分，对应归约项目。

填归约部分的时候要特别小心：LR(0)的归约项目对应该行所有终结符列都要填归约动作，包括$。如果某个列已经被移入动作占了，就产生了移入-归约冲突。这时候你要判断这个冲突是否可以通过其他方式解决，比如调整文法或者换用SLR(1)。

提示：实际写代码构造分析表时，可以用一个二维数组或字典来存表。每个表项是一个动作对象，包含动作类型和参数。填表时如果发现表项已经被占用且新动作不同，就记录冲突。

4.4 一个完整文法的LR(0)分析表构建实例

我用一个简单的文法来完整走一遍。文法如下：

(0) S' -> S (1) S -> a A (2) A -> b

增广文法有产生式0、1、2。初始项目集I0 = CLOSURE({S' -> ·S})。计算闭包：S' -> ·S圆点后是S，加入S -> ·a A。没有其他待约项目了。所以I0 = {S' -> ·S, S -> ·a A}。

计算GOTO：GOTO(I0, S) = CLOSURE({S' -> S·}) = {S' -> S·}，记为I1。GOTO(I0, a) = CLOSURE({S -> a·A})，圆点后是A，加入A -> ·b，所以I2 = {S -> a·A, A -> ·b}。GOTO(I0, b)为空，因为I0里没有圆点后是b的项目。

继续算I2的GOTO：GOTO(I2, A) = CLOSURE({S -> a A·}) = {S -> a A·}，记为I3。GOTO(I2, b) = CLOSURE({A -> b·}) = {A -> b·}，记为I4。

I3和I4里都是归约项目，没有圆点后还有符号的项目，所以GOTO都为空。状态集合是{I0, I1, I2, I3, I4}。

填ACTION表：I0里S -> ·a A是移入项目，GOTO(I0, a) = I2，所以ACTION[0, a] = shift 2。I1里S' -> S·是接受项目，ACTION[1, $] = accept。I2里S -> a·A是待约项目，A -> ·b是移入项目，GOTO(I2, b) = I4，所以ACTION[2, b] = shift 4。I3里S -> a A·是归约项目，对$填reduce S -> a A。I4里A -> b·是归约项目，对$填reduce A -> b。

填GOTO表：GOTO[0, S] = 1，GOTO[2, A] = 3。其他非终结符列没有转移。

这个文法没有冲突，是LR(0)文法。分析输入串a b $的过程是：初始栈[0]，输入a b $。查ACTION[0, a] = shift 2，栈变[0, a, 2]，输入变b $。查ACTION[2, b] = shift 4，栈变[0, a, 2, b, 4]，输入变$。查ACTION[4, $] = reduce A -> b，弹出b和状态4，栈变[0, a, 2]，查GOTO[2, A] = 3，压入A和状态3，栈变[0, a, 2, A, 3]。查ACTION[3, $] = reduce S -> a A，弹出a, A和状态2、3，栈变[0]，查GOTO[0, S] = 1，压入S和状态1，栈变[0, S, 1]。查ACTION[1, $] = accept，分析成功。

5. 常见问题与排查技巧实录

5.1 闭包计算遗漏项目怎么办

闭包计算遗漏是手算时最常见的问题。我自己的经验是：每次加完一批项目后，重新扫描一遍整个项目集，看有没有圆点后面是非终结符但该非终结符的产生式还没展开的。如果有，就继续展开。这个过程要反复做，直到扫描一遍没有任何新项目加入为止。

另一个技巧是用颜色标记。把初始项目用一种颜色，第一次展开的用另一种颜色，第二次展开的再用一种。这样你能清楚地看到展开的层次，不容易漏。写代码时可以用一个队列来存待展开的项目，每次从队列取一个，展开后把新项目入队，直到队列为空。

5.2 GOTO函数计算结果为空的情况分析

GOTO结果为空说明当前项目集里没有任何项目的圆点后面是指定的文法符号。这在构造自动机时是正常的，不需要为空的GOTO建新状态。但如果你发现某个本该有转移的地方GOTO为空，可能是闭包算错了，导致某些项目没被加进来。

比如在表达式文法里，GOTO(I, E)应该非空，因为I里应该有S' -> ·E或者E -> ·E + T这样的项目。如果算出来为空，回去检查闭包是不是漏了E的产生式。我排查这类问题时，会把项目集里所有项目的圆点位置和后面的符号列出来，对照文法产生式看有没有遗漏。

5.3 分析表冲突的定位与文法调整思路

发现冲突后，第一步是定位冲突发生在哪个状态、哪个表项、涉及哪些项目。把冲突的项目列出来，分析它们为什么会在同一个状态里。移入-归约冲突通常是因为文法有优先级或结合性没有显式表达，比如E -> E + E这种二义性文法。归约-归约冲突通常是因为两个产生式的右部有公共前缀，导致在某个状态下无法区分该用哪个归约。

LR(0)解决不了这些冲突，但你可以通过改写文法来消除一些冲突。比如把E -> E + E | E * E | id改写成分层文法E -> E + T | T，T -> T * F | F，F -> id，这样优先级就通过层次体现出来了。改写之后再用LR(0)构造，冲突通常会减少或消失。如果还有冲突，就需要上SLR(1)或LALR(1)。

5.4 手算与代码实现结果不一致的排查

手算和代码算出来的分析表不一致，通常是以下几个原因：一是闭包计算时项目集的顺序不同导致状态编号不同，这个不影响正确性，只要转移关系一致就行。二是归约项目的处理范围不同，LR(0)要求归约项目对整行所有终结符填归约，如果代码只对部分列填了，就会不一致。三是增广文法的开始符号命名不同，导致接受项目的位置不同。

排查时建议把两边的项目集规范族都打印出来，逐个状态对比项目集内容。如果项目集内容一致但状态编号不同，就对比转移关系。如果项目集内容不一致，就重点检查闭包计算和GOTO计算。我一般会在代码里加日志，把每个状态的闭包计算过程打出来，和手算的草稿对照。

5.5 常见问题速查表

注意：LR(0)分析表构造过程中，归约项目要对该行所有终结符列填归约动作，包括结束符$。这一点和SLR(1)不同，SLR(1)只对FOLLOW集中的符号填归约。

6. 从LR(0)到更强分析法的演进逻辑

LR(0)的局限性在于它做归约决策时不看输入符号，只看状态。这导致很多实际语言的文法无法用LR(0)处理。SLR(1)的改进是在归约时检查输入符号是否在归约产生式左部非终结符的FOLLOW集里。如果是，才执行归约；否则报错。这样就把归约动作的范围从整行缩小到了FOLLOW集对应的列，减少了冲突。

LALR(1)进一步改进，它把LR(1)项目集里同心（核心项目相同）的状态合并，既保持了较强的分析能力，又控制了状态数量。LR(1)则是最精确的，它在每个项目里携带一个向前看符号，归约时只在该符号匹配时才执行。LR(1)的状态数比LALR(1)多很多，实际编译器里用LALR(1)的比较多。

理解这个演进链条的关键是抓住“向前看符号”这个变量。LR(0)向前看0个符号，SLR(1)向前看1个符号但用的是FOLLOW集（全局信息），LR(1)向前看1个符号但用的是项目自带的局部信息，LALR(1)在LR(1)的基础上合并同心状态。你如果把LR(0)的自动机构造和填表搞透了，后面加向前看符号只是在归约动作的填法上做修改，骨架不变。

我在实际写解析器时，如果文法比较简单，会先用LR(0)试试，看看有没有冲突。如果没有冲突，LR(0)的分析表最小、分析速度最快。如果有冲突，再逐步升级到SLR(1)或LALR(1)。这个渐进的过程比一上来就用最复杂的分析法更高效，也更容易调试。