预测分析表与过程表：从手算填表到代码实现)
把LL(1)预测分析表和预测分析过程表搞混,是学编译原理时最典型的一种以为自己会了。很多人能把FIRST集、FOLLOW集背得滚瓜烂熟,一到纸上填表就开始犹豫:某个格子到底该写哪条产生式?分析栈里那一串符号为什么是这个顺序?输入指针什么时候往前走?我第一次做课程设计那会儿,把E那一行的加号填成了E→TE,结果整个输入串在第三步就崩了,查了两个小时才发现是SELECT集算错了一个字。后来带过几届学弟学妹,发现大家踩的坑出奇地一致,于是把这两张表的来龙去脉、手算细节和代码落地整理成这一篇,从为什么要查表一直讲到怎么把表写成能跑的程序。不管你是正在准备期末手算题,还是要交一个能演示的分析器,下面这些内容基本能覆盖你九成以上的疑问。1. 从试错回溯到查表直推:预测分析表到底解决了什么1.1 自顶向下分析为什么非要看一眼就定自顶向下分析的基本思路,是从文法的开始符号出发,不断把当前句型里的非终结符替换成某条产生式的右部,试图一步步长出目标输入串。问题在于,当一个非终结符对应多条产生式时,机器并不知道该选哪一条。最朴素的做法是挨个试:先试第一条,推不下去就退回来换第二条,这就是带回溯的递归下降分析。回溯的代价很大。假设一个非终结符有k条候选产生式,每层递归都要试k次,嵌套几层之后,最坏情况下要枚举的组合数会呈指数级膨胀。更麻烦的是,回溯需要保存大量的现场状态,实现起来啰嗦,调试起来更是噩梦——你很难说清楚到底在哪一层、因为什么原因退回来的。LL(1)分析法给出的答案是:与其事后试错,不如事前把当前非终结符遇到当前输入符号时该用哪条产生式全部枚举出来,做成一张二维表。分析时只看栈顶非终结符和当前输入符号这两个信息,直接查表,查到什么就执行什么,一次也不回头。这张表就是LL(1)预测分析表,通常记作M[A, a],其中A是非终结符,a是终结符或输入结束符。注意:预测分析表之所以叫预测,是因为它在真正匹配之前就预判了该走哪条路,属于一种确定性的、无回溯的分析策略。它成立的前提是文法本身足够规矩,这一点后面会用SELECT集来严格判定。1.2 一张二维表背后其实是一台下推自动机理解预测分析表最有效的方式,是把它和一台下推自动机对应起来。这台机器只有三样东西:一个符号栈、一个输入指针、一张控制表也就是预测分析表。栈里一开始压着结束符# 开始符号,栈顶在右侧;输入串末尾也补一个#,指针指向第一个待处理符号。每一步机器只做四件事之一:如果栈顶是终结符且和当前输入符号相同,两边一起消掉,指针后移,这叫匹配;如果栈顶是非终结符,就拿(栈顶, 当前输入符号)去查表,用查到的产生式右部替换栈顶,这叫推导;如果栈顶和输入同时到达#,说明整串分析成功,这叫接受;其余情况一律是出错,说明输入串不属于该文法。把这四类动作按时间顺序记录下来,就是预测分析过程表。它和分析表的关系,有点像规则手册和执行日志:预测分析表是静态的、分析之前就固化下来的决策依据;预测分析过程表是动态的、针对某一个具体输入串逐步推演出来的轨迹。两张表经常一起考,但它们的生成时机和用途完全不同,混为一谈是很多错误的源头。1.3 LL(1)这三个字符各自对应的约束LL(1)这个名字拆开看,每个字符都是一条约束。第一个L表示从左到右扫描输入串,这是所有常规分析器的共同前提;第二个L表示构造的是最左推导,也就是每次总是替换当前句型中最左边的那个非终结符,这决定了栈的操作顺序和栈顶优先的处理逻辑;括号里的1表示向前看一个输入符号,也就是查表时只用当前这一个符号做决策,不需要预读第二个。那个1是关键。它既是LL(1)分析高效的原因——决策成本极低,也是它能力受限的原因——有些文法光靠一个符号无法区分两条产生式,就会在表里出现同一个格子填了两条产生式的情况,称为冲突。一旦出现冲突,这个文法就不是LL(1)文法,要么改写文法,要么换用更强的分析方法。所以判断一个文法能不能用LL(1),本质上就是判断只看一个符号够不够用。2. FIRST集与FOLLOW集:表能不能填对,八成看这两步2.1 FIRST集的递推求解与能推出空串的传染性FIRST(α)的定义是:从符号串α出发,能够推导出的所有可能串的第一个终结符组成的集合。如果α本身能推出空串ε,那么ε也算作FIRST(α)的成员,这个规定非常重要,后面填表时会直接决定ε产生式往哪里落。手算FIRST集有一套固定的递推规则。对单个终结符a,FIRST(a) {a};对单个非终结符A,看它的每条产生式A→X₁X₂…Xₙ,从左往右扫描右部:把FIRST(X₁)里除ε以外的符号全部加进FIRST(A);如果X₁能推出ε,就继续看X₂,把FIRST(X₂)里除ε以外的符号加进来,以此类推;如果一路扫到Xₙ都能推出ε,说明整条右部可以推出ε,于是把ε加进FIRST(A)。对所有非终结符反复执行这套规则,直到集合不再变化为止,这叫求不动点。拿一个去掉了左递归的算术表达式文法做例子:E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id按规则算下来,FIRST(F) { (, id };因为T→FT且F不能推ε,所以FIRST(T) { (, id };同理FIRST(E) { (, id }。E的两条产生式分别给出FIRST(E)包含和ε;T同理包含*和ε。这套结果看起来简单,但手工算的时候最容易漏的是传染:如果某个非终结符的所有产生式都能推出ε,它自己就要带上ε,而这个ε会继续向上传染给用到它的那些产生式。漏掉这一步,后面整张表都会塌。2.2 FOLLOW集为什么必须把开始符和后继符号都算进去FOLLOW(A)的定义是:在所有可能的句型中,紧跟在非终结符A后面的终结符组成的集合。如果A可能出现在句子的最末尾,那么输入结束符#也要算进去。它回答的问题是:当A推导出空串之后,下一个该期待什么符号?计算FOLLOW集有三条核心规则。第一,文法的开始符号E,把#加入FOLLOW(E)。第二,对每条形如A→αBβ的产生式,把FIRST(β)中除ε以外的符号全部加入FOLLOW(B)。第三,如果β能推出ε,或者产生式形如A→αB,那么把FOLLOW(A)整体加入FOLLOW(B)——因为B后面没有东西了,原本跟在A后面的符号自然就跟在B后面了。还是上面那个文法:FOLLOW(E)先放进#;又因为F→(E),E后面是),所以把)也加进去,得到{ ), # }。E出现在E→TE的末尾,所以FOLLOW(E) FOLLOW(E) { ), # }。T在E→TE中后面跟着E,而FIRST(E)去掉ε是{},所以进入FOLLOW(T);同时E能推出ε,FOLLOW(E)也整体并入,得到{ , ), # }。T在T→FT末尾,直接继承FOLLOW(T)。F出现在T→FT和T→FT中,后面都是T,FIRST(T)去掉ε是{},再加上FOLLOW(T)的继承,最终FOLLOW(F) { *, , ), # }。注意:FOLLOW集只对非终结符有定义,不要给终结符算FOLLOW。另外很多同学会把FOLLOW和FIRST的传染方向搞反:FIRST是自下而上从右部往左部传,FOLLOW是自上而下从左部往右部传,画个箭头记一下就清楚了。2.3 手算时用表格反复扫到不动点最稳纯靠脑子推FIRST和FOLLOW,符号一多必然出错。我的习惯是画一张三列表:非终结符、FIRST、FOLLOW,先全部置空,然后一遍一遍地扫产生式,每扫一遍就把新发现的符号补进去,直到某一遍扫完所有格子都没变化为止。这个过程虽然笨,但可验证、可复查,考试时还能当草稿留下痕迹,万一结果错了也方便回溯是哪一遍加错了。以这套文法为例,扫完之后得到的结果如下表:非终结符FIRSTFOLLOWE{ (, id }{ ), # }E{ , ε }{ ), # }T{ (, id }{ , ), # }T{ *, ε }{ , ), # }F{ (, id }{ *, , ), # }这张表就是后面一切工作的地基。填预测分析表时,几乎每一个格子都要回头查这两列;推导过程表时,遇到ε产生式也要靠FOLLOW判断合法性。可以说FIRST和FOLLOW算错一个符号,后面的两张表都会连带出错,而且错得很隐蔽——你可能算到最后一步才发现对不上。3. SELECT集:判断这个文法到底能不能用LL(1)的硬门槛3.1 产生式右部含不含ε,SELECT集算法分两路SELECT集是针对某一条产生式而言的,它回答的是:在什么输入符号下,我应该选这条产生式? 定义上它把FIRST和FOLLOW缝在了一起,算法分两种情况。第一种,产生式形如A→α且α不能推出ε。这时SELECT(A→α) FIRST(α),因为右部第一个符号就能确定该不该走这条路。第二种,产生式形如A→α且α能推出ε,包括最直接的A→ε。这时右部本身可能什么都不产生,能选它的时机就变成了α后面可能跟什么,也就是SELECT(A→α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。拿上面的文法逐条算:E→TE的右部不能推ε,SELECT就是FIRST(TE) { (, id };E→TE给出{};E→ε属于第二种情况,SELECT FOLLOW(E) { ), # };T→FT给出{ (, id };T→FT给出{};T→ε给出FOLLOW(T) { , ), # };F→(E)给出{(};F→id给出{id}。3.2 同一左部产生式的SELECT集必须两两不交LL(1)文法的判定条件非常干净:对于同一个非终结符A的任意两条不同产生式,它们的SELECT集交集必须为空。道理很直白——查表时机器只知道当前输入符号,如果两条产生式的SELECT集有重叠,那么遇到重叠的那个符号时机器就无法决定该选哪条,这就是冲突。检查一下:E的两条产生式SELECT分别是{}和{ ), # },不相交;T的两条是{*}和{ , ), # },也不相交;E、T、F各自只有一条或两条互不相交的产生式。所以这个文法是LL(1)文法,可以放心构造无冲突的预测分析表。注意:判断LL(1)时只看同一个左部的产生式之间有没有交集,不同左部的SELECT集重叠是正常的,不构成冲突。这一点新手经常搞混,看到两个集合都有(就以为文法不行了。3.3 冲突出现了怎么办:消左递归、提左公因子、改写文法如果检查发现SELECT集相交,说明原文法不是LL(1)文法,常见的有两类病因,对应的处方也不一样。第一类是左递归。形如A→Aα的产生式会让自顶向下分析陷入无限循环,因为机器会不停地用A替换A,栈永远清不空。消除左递归的标准做法是引入新非终结符A,把A→Aα | β改写成A→βA、A→αA | ε。直接左递归用这个公式一套就行,间接左递归需要先通过代入把环拆开,再逐条处理。改写之后文法语言不变,但推导结构变了,需要重新算FIRST和FOLLOW。第二类是公共左因子。形如A→αβ | αγ的两条产生式,前几个符号完全一样,只看一个输入符号当然分不开。处理办法是把公共前缀提出来:A→αA、A→β | γ。提取之后,原本要靠预读多个符号才能区分的情况,被压缩成了一个新非终结符的决策,一个符号就够了。这两步做完,大部分看起来不能用LL(1)的表达式类文法都能救回来。但也要有心理准备:有些文法无论怎么改写都不是LL(1)的,比如需要向前看两个符号才能区分的情形,这时候要么上LL(k),要么改用LR类分析方法。硬凑是凑不出来的,改写只是在保持语言等价的前提下调整结构,不会凭空增加文法的分辨能力。4. 预测分析表M[A,a]的逐格填写与冲突标记4.1 填表的三条硬规则有了SELECT集,填预测分析表就变成纯粹的机械劳动了。表的行是非终结符,列是终结符加上结束符#,每个格子的内容是该用哪条产生式。规则只有三条:对每一条产生式A→α,遍历SELECT(A→α)中的每一个终结符a,在M[A,a]格里填入A→α。如果SELECT集里含有#,就填在#那一列,这通常出现在能推出ε且FOLLOW含#的产生式上。所有没被填到的格子留空,表示遇到这个符号就是语法错误。第三条经常被忽略。空格不是没用的,它恰恰是错误检测的依据:分析过程中一旦查到一个空格子,就能立刻断定输入串不合法,而不需要等到最后才发现推不下去。4.2 把算术表达式文法的整张表填出来按上面的规则,把每条产生式往对应格子里填,得到下表(行是非终结符,列是输入符号):非终结符()*id#EE→TEE→TEEE→εE→TEE→εTT→FTT→FTTT→εT→εT→*FTT→εFF→(E)F→id可以看到,E那一行的加号格子里是E→TE,而不是E→ε,这就是开头提到的那个错误点。判断依据很简单:加号属于SELECT(E→TE) {},所以这一格填带加号的那条产生式;右括号和#属于SELECT(E→ε),才填ε产生式。填表的时候先在心里默念一遍这个符号落在哪条产生式的SELECT里,基本就不会错。4.3 表里冒出多值格子意味着什么如果填完之后发现某个格子里出现了两条甚至更多产生式,这就叫多重定义项,是文法不是LL(1)的直接证据,也等价于前面说的SELECT集相交。这时候不要急着改表,先回头查SELECT集,看是哪两条产生式在这个符号上撞了,再判断是左递归没消干净、左公因子没提完,还是文法本身就需要更强的分析能力。还有一种隐蔽的情况:表本身没有多值,但存在该填却没填的格子,导致某些合法输入走到中途查不到产生式。这通常是因为FOLLOW集算漏了符号,尤其是忘了把#加进开始符的FOLLOW。我的建议是填完表之后做个反向检查,把表里所有非空格子和SELECT集逐条对一遍,数量对得上才算过关。5. 预测分析过程表:栈、输入指针、产生式三列怎么联动5.1 分析栈的初始状态与结束条件预测分析表的驱动核心是一符号栈。初始化时,栈底放结束符#,上面压入文法开始符号,写成#E的形式,约定栈顶在右侧;输入串末尾补上#,指针指向第一个符号。整个过程一直循环到栈和输入同时只剩#,此时分析成功接受。这里有两个新手高频出错点。第一是栈的书写方向,不同教材约定不完全一样,有把栈顶写在左边的,也有写在右边的。手算时一定要和自己的约定保持一致,并且整份答卷统一,否则改卷人看不懂你在干什么。我一般按栈底在左、栈顶在右来写,因为替换产生式时弹出栈顶、右部逆序压栈这个操作写成从左到右的字符串最直观。第二是结束符#的位置,它必须同时出现在栈底和输入串末尾,少一个都结束不了。5.2 每一步只有替换、匹配、接受、报错四种动作循环体的逻辑可以用一段伪代码概括,每一步先看栈顶符号X和当前输入符号a:若X是终结符:比较X和a是否相同。相同则弹出X、指针后移,记为匹配X;不同则报错。若X是非终结符:查M[X,a]。查到产生式X→α,弹出X,把α逆序压栈(若α是ε则什么都不压),记为用X→α推导;查不到则报错。若X是#:此时若a也是#,接受;否则报错。这里逆序压栈是理解栈变化的关键。因为栈是后进先出,而产生式右部是从左往右匹配的,所以要让右部最左边的符号先出栈被处理,就必须把它压在最上面,也就是把右部倒着压进去。比如栈顶是E,用E→TE替换,先压E再压T,栈变成#TE,栈顶是T。很多人手算时忘了倒序,导致后面符号全反了,分析到一半就崩。5.3 拿idid*id#完整走一遍理论讲完,还是要落到具体串上。以输入串idid*id#为例,分析过程表如下:步骤分析栈剩余输入串动作/所用产生式0#Eidid*id#初始化1#ETidid*id#E→TE2#ETFidid*id#T→FT3#ETididid*id#F→id4#ETid*id#匹配id5#Eid*id#T→ε6#ETid*id#E→TE7#ETid*id#匹配8#ETFid*id#T→FT9#ETidid*id#F→id10#ET*id#匹配id11#ETF**id#T→*FT12#ETFid#匹配*13#ETidid#F→id14#ET#匹配id15#E#T→ε16##E→ε,接受逐步核对可以发现几个规律。凡是遇到栈顶和输入符号相同的步骤,都是匹配,栈和输入同步消耗一个符号;凡是压入产生式右部的步骤,栈长度会变化,但输入指针纹丝不动;而ε产生式(如第5步T→ε、第15步T→ε、第16步E→ε)只弹栈不压栈,输入也不动,看起来像白走一步,实际上是文法结构使然。这套推演一旦跑顺,你会发现每一步的决策依据都能在预测分析表里找到对应格子。第1步用E→TE,是因为M[E, id]格里填的就是这条;第5步用T→ε,是因为M[T, ]格里填的是T→ε。过程表本质上就是按图索骥把表里的内容一条条兑现出来。6. 手算时最容易翻车的几个细节6.1 栈顶方向不统一,整张过程表全反这是最最常见、也最冤的错误。有人习惯栈顶在左,有人习惯栈顶在右,单看某一行的栈内容好像都对,但一旦和剩余输入串对照着看,就会发现被处理的符号根本不在栈顶。避免办法只有一个:动笔之前在草稿纸角上写一句约定,全篇统一。个人建议采用栈顶在右的写法,因为右部逆序压栈这个操作在这种书写下最符合直觉,生成的过程表也更容易检查。6.2 ε产生式填表落在FOLLOW集,而不是FIRST集只要产生式右部能推出ε,它的SELECT集就要并上左部的FOLLOW集,填表时也要填在FOLLOW集对应的那些列上,而不是填在第一符号所在的列。比如E→ε,它的落脚点是右括号列和#列,而不是加号列。这个规则衍生出很多变体题,比如问M[E, ]该填什么,答案就是E→TE而不是E→ε。记法很简单:能推导出空串的产生式,它负责的是空串之后那些符号。6.3 左递归没消干净,程序跑起来死循环如果文法里还残留形如A→Aα的产生式,预测分析表里A那一行很可能会出现自我指向的格子,分析驱动会不停地把A替换成A开头的右部,栈永远清不掉。手算时表现为过程表里同一步骤反复出现,程序里表现为CPU打满。检查方法:扫一遍所有产生式,看有没有右部第一个符号就是左部自己的;有就按标准公式改写,再重算FIRST和FOLLOW。6.4 终结符和非终结符命名撞车用字母做符号时很容易撞名,比如既把E当非终结符,又在某个地方用小写e当终结符,或者用id、num这类多字符终结符时忘了它们整体是一个符号。手算时建议先把终结符集合和非终结符集合各自列一行,确认没有交集,再开始算集合。多字符终结符在过程表里要整体对待,id是一个符号,不能拆成i和d两步匹配。注意:输入串末尾的#是约定俗成的结束符,它不属于原文法的终结符集合,但在预测分析表里必须单独占一列,在过程表里也必须出现在输入串末尾。漏掉这一列,所有含ε的格子都会失去落脚点。6.5 输入串不合法时报错点在哪过程表还有一个容易被忽视的用途:定位错误。当查表查到空格子,或者栈顶终结符和输入符号对不上,分析就会停下来,此时剩余输入串的第一个符号就是错误被发现的位置。很多教材进一步要求做错误恢复,最简单的策略是恐慌模式:既然当前符号处理不了,就把它从输入里丢掉继续往后看,或者跳过栈顶符号,直到能重新同步。更精细一点的做法是利用FOLLOW集,当栈顶非终结符A出错时,如果当前输入符号在FOLLOW(A)里,可以直接让A推导出ε把它弹掉,相当于假装这个结构为空,从而继续分析后面的内容。这种策略在构造分析器时非常实用,能让报错信息更友好。6.6 用一张对照表检查自己的答案手算完两张表,别急着交卷,用下面这张清单过一遍,能拦住大部分低级错误:检查项正确表现常见错误表列是否含#有独立的#列漏掉#列ε产生式落脚点落在FOLLOW集对应列落在FIRST集对应列同一格是否多值每格至多一条产生式出现两条,说明有冲突栈的书写方向全篇统一混用左右栈顶右部压栈顺序逆序压入正序压入导致符号反结束条件栈和输入同时为#只看其中一个这套检查做熟了之后,手算速度会明显上来,而且基本能做到一次就对。7. 把两张表落成代码:一个最小可跑的LL(1)驱动7.1 数据结构:嵌套字典加列表就够用预测分析表在代码里最自然的表示是以(非终结符, 输入符号)为键、以产生式右部为值的字典。产生式右部用列表存,空串用特殊标记表示。栈直接用Python列表,栈顶取stack[-1],压栈时用reversed保证顺序正确。这样既贴近手工推导的过程,又方便打印出和过程表完全一致的轨迹。# 预测分析表:键是(非终结符, 当前输入符号),值是产生式右部列表 table { (E, id): [T, E], (E, (): [T, E], (E, ): [, T, E], (E, )): [], (E, #): [], (T, id): [F, T], (T, (): [F, T], (T, *): [*, F, T], (T, ): [], (T, )): [], (T, #): [], (F, id): [id], (F, (): [(, E, )], } terminals {id, , *, (, ), #}这里把ε产生式的右部直接写成空列表,推导时弹出栈顶、不压任何东西,和手工推导里ε只弹不压的操作完全对应。7.2 驱动循环写清楚,错误处理别偷懒驱动部分就是把5.2节的伪代码翻译成实际代码,重点是四种动作分清楚,以及每一步都把当前栈和剩余输入记录下来,方便和手算结果对拍。def parse(tokens, table, startE): stack [#, start] i 0 trace [] while True: top stack[-1] cur tokens[i] remain .join(tokens[i:]) if top # and cur #: trace.append((stack[:], remain, 接受)) return True, trace if top in terminals: if top cur: stack.pop() i 1 trace.append((stack[:], remain, f匹配 {top})) else: trace.append((stack[:], remain, f错误:期待 {top},遇到 {cur})) return False, trace else: rule table.get((top, cur)) if rule is None: trace.append((stack[:], remain, f错误:无产生式 M[{top},{cur}])) return False, trace stack.pop() for sym in reversed(rule): stack.append(sym) rhs .join(rule) if rule else ε trace.append((stack[:], remain, f{top}→{rhs}))注意reversed(rule)这一步,它就是确保右部最左符号压在栈顶的关键。如果写成正序,分析会在第二步就出现终结符错位的假报错,这类问题在调试时非常有迷惑性。7.3 手算和程序对拍,才算真正掌握程序跑通之后,最有效的验证方式就是拿几组输入做对拍:先用idid*id#跑一遍,把输出的轨迹和上面第5节手算的过程表逐行对照,看每一步的栈内容、剩余输入和动作是否完全一致;再换(idid)*id#这种带括号的串,检查嵌套结构是否处理正确;最后故意构造一个非法输入,比如idid#,看程序是不是在你预期的位置报错。我个人的体会是,手算和代码对拍这一步的价值远超刷十道题。手算时你容易想当然,代码不会惯着你,栈里多压一个符号、少弹一次,输出立刻就不一样。改完一处再对拍一次,来回三五轮,LL(1)这套东西基本就长在脑子里了。至于再往后,把FOLLOW集用于错误恢复、把分析表自动生成而不是手工敲,都是很自然的延伸方向,前者能让报错信息更有针对性,后者可以把FIRST、FOLLOW、SELECT的计算也全部程序化,真正做到给出文法就能跑。 
长河君 · 2026/10/26 4:48:12 · 阅读 1.2k LL(1)预测分析表与过程表：从手算填表到代码实现
把LL(1)预测分析表和预测分析过程表搞混,是学编译原理时最典型的一种以为自己会了。很多人能把FIRST集、FOLLOW集背得滚瓜烂熟,一到纸上填表就开始犹豫:某个格子到底该写哪条产生式?分析栈里那一串符号为什么是这个顺序?输入指针什么时候往前走?我第一次做课程设计那会儿,把E那一行的加号填成了E→TE,结果整个输入串在第三步就崩了,查了两个小时才发现是SELECT集算错了一个字。后来带过几届学弟学妹,发现大家踩的坑出奇地一致,于是把这两张表的来龙去脉、手算细节和代码落地整理成这一篇,从为什么要查表一直讲到怎么把表写成能跑的程序。不管你是正在准备期末手算题,还是要交一个能演示的分析器,下面这些内容基本能覆盖你九成以上的疑问。1. 从试错回溯到查表直推:预测分析表到底解决了什么1.1 自顶向下分析为什么非要看一眼就定自顶向下分析的基本思路,是从文法的开始符号出发,不断把当前句型里的非终结符替换成某条产生式的右部,试图一步步长出目标输入串。问题在于,当一个非终结符对应多条产生式时,机器并不知道该选哪一条。最朴素的做法是挨个试:先试第一条,推不下去就退回来换第二条,这就是带回溯的递归下降分析。回溯的代价很大。假设一个非终结符有k条候选产生式,每层递归都要试k次,嵌套几层之后,最坏情况下要枚举的组合数会呈指数级膨胀。更麻烦的是,回溯需要保存大量的现场状态,实现起来啰嗦,调试起来更是噩梦——你很难说清楚到底在哪一层、因为什么原因退回来的。LL(1)分析法给出的答案是:与其事后试错,不如事前把当前非终结符遇到当前输入符号时该用哪条产生式全部枚举出来,做成一张二维表。分析时只看栈顶非终结符和当前输入符号这两个信息,直接查表,查到什么就执行什么,一次也不回头。这张表就是LL(1)预测分析表,通常记作M[A, a],其中A是非终结符,a是终结符或输入结束符。注意:预测分析表之所以叫预测,是因为它在真正匹配之前就预判了该走哪条路,属于一种确定性的、无回溯的分析策略。它成立的前提是文法本身足够规矩,这一点后面会用SELECT集来严格判定。1.2 一张二维表背后其实是一台下推自动机理解预测分析表最有效的方式,是把它和一台下推自动机对应起来。这台机器只有三样东西:一个符号栈、一个输入指针、一张控制表也就是预测分析表。栈里一开始压着结束符# 开始符号,栈顶在右侧;输入串末尾也补一个#,指针指向第一个待处理符号。每一步机器只做四件事之一:如果栈顶是终结符且和当前输入符号相同,两边一起消掉,指针后移,这叫匹配;如果栈顶是非终结符,就拿(栈顶, 当前输入符号)去查表,用查到的产生式右部替换栈顶,这叫推导;如果栈顶和输入同时到达#,说明整串分析成功,这叫接受;其余情况一律是出错,说明输入串不属于该文法。把这四类动作按时间顺序记录下来,就是预测分析过程表。它和分析表的关系,有点像规则手册和执行日志:预测分析表是静态的、分析之前就固化下来的决策依据;预测分析过程表是动态的、针对某一个具体输入串逐步推演出来的轨迹。两张表经常一起考,但它们的生成时机和用途完全不同,混为一谈是很多错误的源头。1.3 LL(1)这三个字符各自对应的约束LL(1)这个名字拆开看,每个字符都是一条约束。第一个L表示从左到右扫描输入串,这是所有常规分析器的共同前提;第二个L表示构造的是最左推导,也就是每次总是替换当前句型中最左边的那个非终结符,这决定了栈的操作顺序和栈顶优先的处理逻辑;括号里的1表示向前看一个输入符号,也就是查表时只用当前这一个符号做决策,不需要预读第二个。那个1是关键。它既是LL(1)分析高效的原因——决策成本极低,也是它能力受限的原因——有些文法光靠一个符号无法区分两条产生式,就会在表里出现同一个格子填了两条产生式的情况,称为冲突。一旦出现冲突,这个文法就不是LL(1)文法,要么改写文法,要么换用更强的分析方法。所以判断一个文法能不能用LL(1),本质上就是判断只看一个符号够不够用。2. FIRST集与FOLLOW集:表能不能填对,八成看这两步2.1 FIRST集的递推求解与能推出空串的传染性FIRST(α)的定义是:从符号串α出发,能够推导出的所有可能串的第一个终结符组成的集合。如果α本身能推出空串ε,那么ε也算作FIRST(α)的成员,这个规定非常重要,后面填表时会直接决定ε产生式往哪里落。手算FIRST集有一套固定的递推规则。对单个终结符a,FIRST(a) {a};对单个非终结符A,看它的每条产生式A→X₁X₂…Xₙ,从左往右扫描右部:把FIRST(X₁)里除ε以外的符号全部加进FIRST(A);如果X₁能推出ε,就继续看X₂,把FIRST(X₂)里除ε以外的符号加进来,以此类推;如果一路扫到Xₙ都能推出ε,说明整条右部可以推出ε,于是把ε加进FIRST(A)。对所有非终结符反复执行这套规则,直到集合不再变化为止,这叫求不动点。拿一个去掉了左递归的算术表达式文法做例子:E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id按规则算下来,FIRST(F) { (, id };因为T→FT且F不能推ε,所以FIRST(T) { (, id };同理FIRST(E) { (, id }。E的两条产生式分别给出FIRST(E)包含和ε;T同理包含*和ε。这套结果看起来简单,但手工算的时候最容易漏的是传染:如果某个非终结符的所有产生式都能推出ε,它自己就要带上ε,而这个ε会继续向上传染给用到它的那些产生式。漏掉这一步,后面整张表都会塌。2.2 FOLLOW集为什么必须把开始符和后继符号都算进去FOLLOW(A)的定义是:在所有可能的句型中,紧跟在非终结符A后面的终结符组成的集合。如果A可能出现在句子的最末尾,那么输入结束符#也要算进去。它回答的问题是:当A推导出空串之后,下一个该期待什么符号?计算FOLLOW集有三条核心规则。第一,文法的开始符号E,把#加入FOLLOW(E)。第二,对每条形如A→αBβ的产生式,把FIRST(β)中除ε以外的符号全部加入FOLLOW(B)。第三,如果β能推出ε,或者产生式形如A→αB,那么把FOLLOW(A)整体加入FOLLOW(B)——因为B后面没有东西了,原本跟在A后面的符号自然就跟在B后面了。还是上面那个文法:FOLLOW(E)先放进#;又因为F→(E),E后面是),所以把)也加进去,得到{ ), # }。E出现在E→TE的末尾,所以FOLLOW(E) FOLLOW(E) { ), # }。T在E→TE中后面跟着E,而FIRST(E)去掉ε是{},所以进入FOLLOW(T);同时E能推出ε,FOLLOW(E)也整体并入,得到{ , ), # }。T在T→FT末尾,直接继承FOLLOW(T)。F出现在T→FT和T→FT中,后面都是T,FIRST(T)去掉ε是{},再加上FOLLOW(T)的继承,最终FOLLOW(F) { *, , ), # }。注意:FOLLOW集只对非终结符有定义,不要给终结符算FOLLOW。另外很多同学会把FOLLOW和FIRST的传染方向搞反:FIRST是自下而上从右部往左部传,FOLLOW是自上而下从左部往右部传,画个箭头记一下就清楚了。2.3 手算时用表格反复扫到不动点最稳纯靠脑子推FIRST和FOLLOW,符号一多必然出错。我的习惯是画一张三列表:非终结符、FIRST、FOLLOW,先全部置空,然后一遍一遍地扫产生式,每扫一遍就把新发现的符号补进去,直到某一遍扫完所有格子都没变化为止。这个过程虽然笨,但可验证、可复查,考试时还能当草稿留下痕迹,万一结果错了也方便回溯是哪一遍加错了。以这套文法为例,扫完之后得到的结果如下表:非终结符FIRSTFOLLOWE{ (, id }{ ), # }E{ , ε }{ ), # }T{ (, id }{ , ), # }T{ *, ε }{ , ), # }F{ (, id }{ *, , ), # }这张表就是后面一切工作的地基。填预测分析表时,几乎每一个格子都要回头查这两列;推导过程表时,遇到ε产生式也要靠FOLLOW判断合法性。可以说FIRST和FOLLOW算错一个符号,后面的两张表都会连带出错,而且错得很隐蔽——你可能算到最后一步才发现对不上。3. SELECT集:判断这个文法到底能不能用LL(1)的硬门槛3.1 产生式右部含不含ε,SELECT集算法分两路SELECT集是针对某一条产生式而言的,它回答的是:在什么输入符号下,我应该选这条产生式? 定义上它把FIRST和FOLLOW缝在了一起,算法分两种情况。第一种,产生式形如A→α且α不能推出ε。这时SELECT(A→α) FIRST(α),因为右部第一个符号就能确定该不该走这条路。第二种,产生式形如A→α且α能推出ε,包括最直接的A→ε。这时右部本身可能什么都不产生,能选它的时机就变成了α后面可能跟什么,也就是SELECT(A→α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。拿上面的文法逐条算:E→TE的右部不能推ε,SELECT就是FIRST(TE) { (, id };E→TE给出{};E→ε属于第二种情况,SELECT FOLLOW(E) { ), # };T→FT给出{ (, id };T→FT给出{};T→ε给出FOLLOW(T) { , ), # };F→(E)给出{(};F→id给出{id}。3.2 同一左部产生式的SELECT集必须两两不交LL(1)文法的判定条件非常干净:对于同一个非终结符A的任意两条不同产生式,它们的SELECT集交集必须为空。道理很直白——查表时机器只知道当前输入符号,如果两条产生式的SELECT集有重叠,那么遇到重叠的那个符号时机器就无法决定该选哪条,这就是冲突。检查一下:E的两条产生式SELECT分别是{}和{ ), # },不相交;T的两条是{*}和{ , ), # },也不相交;E、T、F各自只有一条或两条互不相交的产生式。所以这个文法是LL(1)文法,可以放心构造无冲突的预测分析表。注意:判断LL(1)时只看同一个左部的产生式之间有没有交集,不同左部的SELECT集重叠是正常的,不构成冲突。这一点新手经常搞混,看到两个集合都有(就以为文法不行了。3.3 冲突出现了怎么办:消左递归、提左公因子、改写文法如果检查发现SELECT集相交,说明原文法不是LL(1)文法,常见的有两类病因,对应的处方也不一样。第一类是左递归。形如A→Aα的产生式会让自顶向下分析陷入无限循环,因为机器会不停地用A替换A,栈永远清不空。消除左递归的标准做法是引入新非终结符A,把A→Aα | β改写成A→βA、A→αA | ε。直接左递归用这个公式一套就行,间接左递归需要先通过代入把环拆开,再逐条处理。改写之后文法语言不变,但推导结构变了,需要重新算FIRST和FOLLOW。第二类是公共左因子。形如A→αβ | αγ的两条产生式,前几个符号完全一样,只看一个输入符号当然分不开。处理办法是把公共前缀提出来:A→αA、A→β | γ。提取之后,原本要靠预读多个符号才能区分的情况,被压缩成了一个新非终结符的决策,一个符号就够了。这两步做完,大部分看起来不能用LL(1)的表达式类文法都能救回来。但也要有心理准备:有些文法无论怎么改写都不是LL(1)的,比如需要向前看两个符号才能区分的情形,这时候要么上LL(k),要么改用LR类分析方法。硬凑是凑不出来的,改写只是在保持语言等价的前提下调整结构,不会凭空增加文法的分辨能力。4. 预测分析表M[A,a]的逐格填写与冲突标记4.1 填表的三条硬规则有了SELECT集,填预测分析表就变成纯粹的机械劳动了。表的行是非终结符,列是终结符加上结束符#,每个格子的内容是该用哪条产生式。规则只有三条:对每一条产生式A→α,遍历SELECT(A→α)中的每一个终结符a,在M[A,a]格里填入A→α。如果SELECT集里含有#,就填在#那一列,这通常出现在能推出ε且FOLLOW含#的产生式上。所有没被填到的格子留空,表示遇到这个符号就是语法错误。第三条经常被忽略。空格不是没用的,它恰恰是错误检测的依据:分析过程中一旦查到一个空格子,就能立刻断定输入串不合法,而不需要等到最后才发现推不下去。4.2 把算术表达式文法的整张表填出来按上面的规则,把每条产生式往对应格子里填,得到下表(行是非终结符,列是输入符号):非终结符()*id#EE→TEE→TEEE→εE→TEE→εTT→FTT→FTTT→εT→εT→*FTT→εFF→(E)F→id可以看到,E那一行的加号格子里是E→TE,而不是E→ε,这就是开头提到的那个错误点。判断依据很简单:加号属于SELECT(E→TE) {},所以这一格填带加号的那条产生式;右括号和#属于SELECT(E→ε),才填ε产生式。填表的时候先在心里默念一遍这个符号落在哪条产生式的SELECT里,基本就不会错。4.3 表里冒出多值格子意味着什么如果填完之后发现某个格子里出现了两条甚至更多产生式,这就叫多重定义项,是文法不是LL(1)的直接证据,也等价于前面说的SELECT集相交。这时候不要急着改表,先回头查SELECT集,看是哪两条产生式在这个符号上撞了,再判断是左递归没消干净、左公因子没提完,还是文法本身就需要更强的分析能力。还有一种隐蔽的情况:表本身没有多值,但存在该填却没填的格子,导致某些合法输入走到中途查不到产生式。这通常是因为FOLLOW集算漏了符号,尤其是忘了把#加进开始符的FOLLOW。我的建议是填完表之后做个反向检查,把表里所有非空格子和SELECT集逐条对一遍,数量对得上才算过关。5. 预测分析过程表:栈、输入指针、产生式三列怎么联动5.1 分析栈的初始状态与结束条件预测分析表的驱动核心是一符号栈。初始化时,栈底放结束符#,上面压入文法开始符号,写成#E的形式,约定栈顶在右侧;输入串末尾补上#,指针指向第一个符号。整个过程一直循环到栈和输入同时只剩#,此时分析成功接受。这里有两个新手高频出错点。第一是栈的书写方向,不同教材约定不完全一样,有把栈顶写在左边的,也有写在右边的。手算时一定要和自己的约定保持一致,并且整份答卷统一,否则改卷人看不懂你在干什么。我一般按栈底在左、栈顶在右来写,因为替换产生式时弹出栈顶、右部逆序压栈这个操作写成从左到右的字符串最直观。第二是结束符#的位置,它必须同时出现在栈底和输入串末尾,少一个都结束不了。5.2 每一步只有替换、匹配、接受、报错四种动作循环体的逻辑可以用一段伪代码概括,每一步先看栈顶符号X和当前输入符号a:若X是终结符:比较X和a是否相同。相同则弹出X、指针后移,记为匹配X;不同则报错。若X是非终结符:查M[X,a]。查到产生式X→α,弹出X,把α逆序压栈(若α是ε则什么都不压),记为用X→α推导;查不到则报错。若X是#:此时若a也是#,接受;否则报错。这里逆序压栈是理解栈变化的关键。因为栈是后进先出,而产生式右部是从左往右匹配的,所以要让右部最左边的符号先出栈被处理,就必须把它压在最上面,也就是把右部倒着压进去。比如栈顶是E,用E→TE替换,先压E再压T,栈变成#TE,栈顶是T。很多人手算时忘了倒序,导致后面符号全反了,分析到一半就崩。5.3 拿idid*id#完整走一遍理论讲完,还是要落到具体串上。以输入串idid*id#为例,分析过程表如下:步骤分析栈剩余输入串动作/所用产生式0#Eidid*id#初始化1#ETidid*id#E→TE2#ETFidid*id#T→FT3#ETididid*id#F→id4#ETid*id#匹配id5#Eid*id#T→ε6#ETid*id#E→TE7#ETid*id#匹配8#ETFid*id#T→FT9#ETidid*id#F→id10#ET*id#匹配id11#ETF**id#T→*FT12#ETFid#匹配*13#ETidid#F→id14#ET#匹配id15#E#T→ε16##E→ε,接受逐步核对可以发现几个规律。凡是遇到栈顶和输入符号相同的步骤,都是匹配,栈和输入同步消耗一个符号;凡是压入产生式右部的步骤,栈长度会变化,但输入指针纹丝不动;而ε产生式(如第5步T→ε、第15步T→ε、第16步E→ε)只弹栈不压栈,输入也不动,看起来像白走一步,实际上是文法结构使然。这套推演一旦跑顺,你会发现每一步的决策依据都能在预测分析表里找到对应格子。第1步用E→TE,是因为M[E, id]格里填的就是这条;第5步用T→ε,是因为M[T, ]格里填的是T→ε。过程表本质上就是按图索骥把表里的内容一条条兑现出来。6. 手算时最容易翻车的几个细节6.1 栈顶方向不统一,整张过程表全反这是最最常见、也最冤的错误。有人习惯栈顶在左,有人习惯栈顶在右,单看某一行的栈内容好像都对,但一旦和剩余输入串对照着看,就会发现被处理的符号根本不在栈顶。避免办法只有一个:动笔之前在草稿纸角上写一句约定,全篇统一。个人建议采用栈顶在右的写法,因为右部逆序压栈这个操作在这种书写下最符合直觉,生成的过程表也更容易检查。6.2 ε产生式填表落在FOLLOW集,而不是FIRST集只要产生式右部能推出ε,它的SELECT集就要并上左部的FOLLOW集,填表时也要填在FOLLOW集对应的那些列上,而不是填在第一符号所在的列。比如E→ε,它的落脚点是右括号列和#列,而不是加号列。这个规则衍生出很多变体题,比如问M[E, ]该填什么,答案就是E→TE而不是E→ε。记法很简单:能推导出空串的产生式,它负责的是空串之后那些符号。6.3 左递归没消干净,程序跑起来死循环如果文法里还残留形如A→Aα的产生式,预测分析表里A那一行很可能会出现自我指向的格子,分析驱动会不停地把A替换成A开头的右部,栈永远清不掉。手算时表现为过程表里同一步骤反复出现,程序里表现为CPU打满。检查方法:扫一遍所有产生式,看有没有右部第一个符号就是左部自己的;有就按标准公式改写,再重算FIRST和FOLLOW。6.4 终结符和非终结符命名撞车用字母做符号时很容易撞名,比如既把E当非终结符,又在某个地方用小写e当终结符,或者用id、num这类多字符终结符时忘了它们整体是一个符号。手算时建议先把终结符集合和非终结符集合各自列一行,确认没有交集,再开始算集合。多字符终结符在过程表里要整体对待,id是一个符号,不能拆成i和d两步匹配。注意:输入串末尾的#是约定俗成的结束符,它不属于原文法的终结符集合,但在预测分析表里必须单独占一列,在过程表里也必须出现在输入串末尾。漏掉这一列,所有含ε的格子都会失去落脚点。6.5 输入串不合法时报错点在哪过程表还有一个容易被忽视的用途:定位错误。当查表查到空格子,或者栈顶终结符和输入符号对不上,分析就会停下来,此时剩余输入串的第一个符号就是错误被发现的位置。很多教材进一步要求做错误恢复,最简单的策略是恐慌模式:既然当前符号处理不了,就把它从输入里丢掉继续往后看,或者跳过栈顶符号,直到能重新同步。更精细一点的做法是利用FOLLOW集,当栈顶非终结符A出错时,如果当前输入符号在FOLLOW(A)里,可以直接让A推导出ε把它弹掉,相当于假装这个结构为空,从而继续分析后面的内容。这种策略在构造分析器时非常实用,能让报错信息更友好。6.6 用一张对照表检查自己的答案手算完两张表,别急着交卷,用下面这张清单过一遍,能拦住大部分低级错误:检查项正确表现常见错误表列是否含#有独立的#列漏掉#列ε产生式落脚点落在FOLLOW集对应列落在FIRST集对应列同一格是否多值每格至多一条产生式出现两条,说明有冲突栈的书写方向全篇统一混用左右栈顶右部压栈顺序逆序压入正序压入导致符号反结束条件栈和输入同时为#只看其中一个这套检查做熟了之后,手算速度会明显上来,而且基本能做到一次就对。7. 把两张表落成代码:一个最小可跑的LL(1)驱动7.1 数据结构:嵌套字典加列表就够用预测分析表在代码里最自然的表示是以(非终结符, 输入符号)为键、以产生式右部为值的字典。产生式右部用列表存,空串用特殊标记表示。栈直接用Python列表,栈顶取stack[-1],压栈时用reversed保证顺序正确。这样既贴近手工推导的过程,又方便打印出和过程表完全一致的轨迹。# 预测分析表:键是(非终结符, 当前输入符号),值是产生式右部列表 table { (E, id): [T, E], (E, (): [T, E], (E, ): [, T, E], (E, )): [], (E, #): [], (T, id): [F, T], (T, (): [F, T], (T, *): [*, F, T], (T, ): [], (T, )): [], (T, #): [], (F, id): [id], (F, (): [(, E, )], } terminals {id, , *, (, ), #}这里把ε产生式的右部直接写成空列表,推导时弹出栈顶、不压任何东西,和手工推导里ε只弹不压的操作完全对应。7.2 驱动循环写清楚,错误处理别偷懒驱动部分就是把5.2节的伪代码翻译成实际代码,重点是四种动作分清楚,以及每一步都把当前栈和剩余输入记录下来,方便和手算结果对拍。def parse(tokens, table, startE): stack [#, start] i 0 trace [] while True: top stack[-1] cur tokens[i] remain .join(tokens[i:]) if top # and cur #: trace.append((stack[:], remain, 接受)) return True, trace if top in terminals: if top cur: stack.pop() i 1 trace.append((stack[:], remain, f匹配 {top})) else: trace.append((stack[:], remain, f错误:期待 {top},遇到 {cur})) return False, trace else: rule table.get((top, cur)) if rule is None: trace.append((stack[:], remain, f错误:无产生式 M[{top},{cur}])) return False, trace stack.pop() for sym in reversed(rule): stack.append(sym) rhs .join(rule) if rule else ε trace.append((stack[:], remain, f{top}→{rhs}))注意reversed(rule)这一步,它就是确保右部最左符号压在栈顶的关键。如果写成正序,分析会在第二步就出现终结符错位的假报错,这类问题在调试时非常有迷惑性。7.3 手算和程序对拍,才算真正掌握程序跑通之后,最有效的验证方式就是拿几组输入做对拍:先用idid*id#跑一遍,把输出的轨迹和上面第5节手算的过程表逐行对照,看每一步的栈内容、剩余输入和动作是否完全一致;再换(idid)*id#这种带括号的串,检查嵌套结构是否处理正确;最后故意构造一个非法输入,比如idid#,看程序是不是在你预期的位置报错。我个人的体会是,手算和代码对拍这一步的价值远超刷十道题。手算时你容易想当然,代码不会惯着你,栈里多压一个符号、少弹一次,输出立刻就不一样。改完一处再对拍一次,来回三五轮,LL(1)这套东西基本就长在脑子里了。至于再往后,把FOLLOW集用于错误恢复、把分析表自动生成而不是手工敲,都是很自然的延伸方向,前者能让报错信息更有针对性,后者可以把FIRST、FOLLOW、SELECT的计算也全部程序化,真正做到给出文法就能跑。