这学期被编译原理折磨的人举个手。我之前的进度是词法分析啃了将近两周正则表达式、NFA、DFA、子集构造法这些虽然绕但还是能算明白甚至写了个小工具专门输出Token序列。结果一进语法分析章节整个人就不太好了。FIRST集、FOLLOW集、LL(1)、LR(0)、SLR、LR(1)、LALR这些词单独拎出来都认识凑在一起直接变成天书。后来我花了半个学期把教材第三版的课后习题从头到尾刷了两遍又借了哈工大和吉林大学的公开课件讲义来对照才慢慢从“背步骤”变成“看得懂为什么”。这篇帖子算是我整理的“语法分析课后习题笔记”的完整复盘把最容易混淆的概念、最常考的题型、以及我自己踩过的坑都写出来。如果你正在准备期末考、考研复试或者刷编译原理的面试题这份东西应该能给你当一张地图用。1. 为什么语法分析这么折磨人先把主线捋清楚1.1 词法分析和语法分析的分工边界很多人学语法分析卡住第一个原因就是没有搞明白它和词法分析的分工。词法分析解决的问题是“把字符串切成Token”它面对的是正则语言用有限自动机就能处理。我们可以把正则表达式想象成一个只能走直线的探测仪它能感知固定模式但记不住“嵌套了多少层”这种状态。语法分析面对的是上下文无关文法输入是词法分析产出的Token序列输出是语法树同时要负责报出语法错误。这里的关键是它需要处理嵌套结构。比如括号配对、if和else的配对、表达式运算符的优先级这些都不是正则语言能轻松描述的东西必须引入“栈”这类能记住历史的机制。很多同学在词法阶段顺手了到了语法阶段还在试图用正则去匹配括号方向直接跑偏后面越学越吃力。从课程安排来看词法分析只是前菜语法分析才是真正的分水岭。词法分析考的是“算法翻译能力”你只要记住几个固定套路比如子集构造法、最小化DFA就能拿分。语法分析考的是“建模思维”你需要理解文法、推导、归约、分析树这些抽象概念并且能在不同分析算法之间切换。如果你在词法分析实验上花了很多时间但没想明白它和语法分析的边界后面学LL(1)、LR(1)的时候就会经常把Token匹配和语法规则混在一起做题自然错。1.2 语法分析要解决的两个核心问题语法分析表面上是判断“输入串是否符合文法”本质上是在做两件事推导和归约。自顶向下分析关注推导从开始符号出发不断用产生式右侧替换左侧尝试匹配输入串自下而上分析关注归约从输入串出发不断把产生式右侧归约成左侧最终回到开始符号。LL(1)属于前者LR家族属于后者。一定要把这两条路线分开学否则递归下降法和LR分析表会混成一锅粥。另外我还想强调一点学习语法分析不只是为了应付考试。你日常用的JSON解析器、XML解析器、数据库SQL引擎、IDE里的语法高亮都和LR/LALR有关。很多Java后端面试会问“怎么手写一个四则运算解析器”这就是递归下降分析法的实际场景。所以我的学习路径是先建立一个总框架文法 - 分析表 - 驱动算法 - 错误处理。一旦框架清楚再去看课后题就会觉得每一道题都在问“这个框架的某个环节怎么构造”。我刷题的时候会在每道题旁边标注它考察的是框架里的哪一层这个习惯帮我省了大量复习时间。2. FIRST、FOLLOW和LL(1)自顶向下分析的命门2.1 FIRST集合的求法别把ε忘了求FIRST集是自顶向下分析的第一步也是整个LL(1)部分最容易丢分的地方。FIRST集通俗理解就是一个非终结符可能推导出的所有句型中排在最前面的那个终结符的集合。如果发现一个非终结符能推导出空串ε那ε也要放进FIRST集但不能和普通终结符混在一起因为它在预测分析表构造时的作用完全不同。具体算法很多人都会背但实际做题容易忽略两个细节。第一当产生式右侧以非终结符开头时要把这个非终结符的FIRST集去掉ε加入左侧FIRST集同时如果这个非终结符能推出ε还要继续看下一个符号。第二循环不是一遍就结束的要不断迭代直到所有集合都不再变化。我用一个经典文法来演示。哪个消除左递归后的表达式文法非常典型E → T EE → T E | εT → F TT → * F T | εF → ( E ) | id求FIRST先从最底层看。F只有两个候选所以FIRST(F) { ( , id }。T右边有两种可能* F T 和 ε所以FIRST(T) { * , ε }。T以F开头所以FIRST(T) FIRST(F) { ( , id }注意这里不包含ε因为F推不出ε。E以开头或者推出ε所以FIRST(E) { , ε }。最后E以T开头所以FIRST(E) FIRST(T) { ( , id }。这个例子里因为F、T、E都不含ε所以不用往下传递比较简单。真正难的是混合了“多个非终结符都能推ε”的文法那时候必须一个一个符号往后扫特别容易漏。2.2 FOLLOW集合的求法三步走FOLLOW集比FIRST更容易让人崩溃因为它依赖别的非终结符还要反复迭代。FOLLOW集通俗理解就是在所有可能的句型中紧跟在某个非终结符后面的终结符集合包括结束符$。我总结了一个三步法照着做不太容易错。第一步对于开始符号S先把$加入FOLLOW(S)。第二步看所有形如 A → α B β 的产生式把FIRST(β)中除ε之外的所有符号都加入FOLLOW(B)。第三步看所有形如 A → α B 的产生式以及 A → α B β 但 β 可能推出ε的情况把FOLLOW(A)全部加入FOLLOW(B)。然后循环执行第二、三步直到集合不再变化。还是用刚才那个文法我把结果列出来然后解释几个容易看漏的地方FOLLOW(E) { $ , ) }FOLLOW(E) FOLLOW(E) { $ , ) }FOLLOW(T) { , $ , ) }FOLLOW(T) FOLLOW(T) { , $ , ) }FOLLOW(F) { * , , $ , ) }容易漏的是FOLLOW(T)里的右括号)。它怎么来的因为E → T E 中T后面跟着E而E可以推出ε所以FOLLOW(E)会加到FOLLOW(T)里。FOLLOW(E)又包含) 所以FOLLOW(T)也要包含) 。这就是典型的“跨层传递”。刷题时我建议每求完一轮就画一个传递关系图比如A的FOLLOW传给BB的FOLLOW又传给C避免漏掉循环依赖。2.3 预测分析表构造和LL(1)判断有了FIRST和FOLLOW就可以判断一个文法是不是LL(1)并且构造预测分析表。LL(1)文法的核心要求有三个没有左递归没有公共左因子并且对任意产生式 A → α | β都要满足FIRST(α) ∩ FIRST(β) 为空如果其中一个候选式能推出ε那么FIRST(另一个) ∩ FOLLOW(A) 也要为空。这个条件看起来抽象其实就是保证给定当前非终结符和当前输入符号程序员能唯一确定该选哪个候选式不会出现“二选一”的情况。预测分析表的构造也很机械。对每个产生式 A → α先看FIRST(α)把FIRST(α)里的每个终结符a对应的表格位置[A, a]填入这条产生式。如果FIRST(α)里有ε还要把FOLLOW(A)里的每个终结符b对应的位置[A, b]也填入这条产生式。如果一个格子被填了两条产生式那这个文法就不是LL(1)。很多选择题会故意给你一个左递归文法让你判断为什么不是LL(1)。这时候不用辛辛苦苦求集合一看到有直接或间接左递归直接排除就行。但如果是简答题还是要按“左递归、公共左因子、FIRST相交”这三条逐一说明。我复习LL(1)时还有一个体会不要只背“LL(1)代表什么”要理解它为什么叫LL(1)。第一个L表示从左到右扫描输入串第二个L表示产生最左推导1表示向前看1个Token。能说清楚这三个含义面试时才算真正过关。3. LR分析家族从LR(0)到LALR一次讲明白3.1 项目、活前缀、项目集规范族LR分析是自下而上分析的重头戏也是很多人从“能跟上”变成“彻底放弃”的地方。我在刷题时发现只要把三个概念吃透后面的SLR、LR(1)都是延展。这三个概念分别是项目、活前缀、项目集规范族。项目就是在产生式右侧某个位置加一个圆点比如 A → α·β。圆点左边表示已经读入的符号右边表示接下来期望看到的符号。活前缀是指规范句型的一个前缀它右边不包含句柄之后的任何符号。通俗理解活前缀就是“分析过程中已经读入但还没到归约时机的那些符号”。项目集规范族就是由所有可能项目组成的集合的集合。构造LR(0)自动机的步骤很固定先给原文法加一个增广产生式比如 S → S然后构造初始项目集I0从[S → ·S]开始做闭包再不断用goto函数生成新状态。closure规则是如果项目 A → α·Bβ 在项目集中那么对每个产生式 B → γ把 B → ·γ 也加入项目集。goto规则是如果项目 A → α·Xβ 在当前项目集那么把圆点向右移动一位得到 A → αX·β然后对这个新集合再做闭包。这个过程很像词法分析里从NFA构造DFA只要做过子集构造法应该不会陌生。我在学的时候就把LR(0)自动机当成一种“DFA”状态就是项目集转移就是goto只不过状态里包含的是产生式而不是NFA节点。用这个类比很多问题立刻豁然开朗。3.2 SLR分析表怎么构造以及它为什么不够用SLR是“简单LR”它在LR(0)项目集基础上用FOLLOW集来决定归约动作。为什么要加这一步因为LR(0)项目集只靠圆点判断如果遇到“某个状态里既有一个移进项目又有一个归约项目”LR(0)就没办法决定该移进还是归约。SLR的改进是如果当前状态有归约项目 A → α·那么只有当下一个输入符号 a 属于FOLLOW(A)时才执行归约。这样能消除一部分冲突。SLR分析表的构造分成两块。ACTION表和GOTO表。ACTION表看当前状态和终结符如果项目 A → α·aβ 在当前状态且输入为a就做移进如果项目 A → α· 在当前状态且输入a ∈ FOLLOW(A)就做归约如果有 S → S· 且输入为$则接受。GOTO表看当前状态和非终结符如果goto(I, A)有值就把对应状态填入。我强烈建议不要死记这些规则而是对照一个已构造好的分析表用一小段输入串走一遍比如输入id id * id每一步查表、压栈、移进、归约走完三次就会明白SLR在干什么。那SLR为什么还不够用因为它只用FOLLOW集来粗粒度判断后续字符没有考虑当前分析上下文。一个经典例子是S → L RS → RL → * RL → idR → L这个文法在某个状态下有项目[R → L·]和[S → L·R]。按SLR的规则当输入是时因为属于FOLLOW(R)所以应该对R → L做归约但同时S → L·R又要求移进。这就产生了移进-归约冲突。可是从语法上看在这个上下文中后面需要紧跟R而R归约成L的合法场景并不包含。说明SLR的前瞻信息还是太少必须引入更精确的展望符。3.3 LR(1)和LALR更精确的“往前看”LR(1)项目比LR(0)项目多一个展望符形式是[A → α·β, a]。这里的a表示当这个归约完成后下一个期待的终结符是什么。构造闭包时对项目[A → α·Bβ, a]每个B → γ产生的项目是【B → ·γ, b】其中b取FIRST(βa)里的终结符。如果β能推出ε那b就是a。看起来只是多了一个小尾巴但这个尾巴让分析器能在更准确的位置做归约从而解决SLR的冲突。LALR可以看成LR(1)的压缩版。它将所有“心相同”的项目合并也就是把[A → α·β, a]和[A → α·β, b]合并成[A → α·β, a/b]从而大幅度减少状态数。很多工具比如Yacc和Bison默认采用LALR(1)。考试里常问LALR和LR(1)的区别我总结一句话LALR不增加移进-归约冲突但可能引入归约-归约冲突。如果合并后出现归约-归约冲突那这个文法的LALR表就不存在。这个点几乎每年笔试都会考务必记住。学LR这一章我的建议是先用笔把LR(0)自动机完整画一遍再试着给每个状态标出有没有冲突接着尝试用SLR规则消除冲突最后再看LR(1)如何用展望符收拾残局。这个递进是整章最好的主线比单纯背定义有用十倍。4. 几道课后习题的完整拆解把答案变成思路4.1 习题1一个典型的LL(1)文法改造课后习题最常见的题型是“判断一个文法是不是LL(1)如果不是请消除左递归、提取左公因子后再构造预测分析表”。我拿一道经典题来讲这个文法有间接左递归很多答案第一步就把人看懵。S → Q c | cQ → R b | bR → S a | a先判断它没有直接左递归但存在间接左递归因为S - Q c - R b c - S a b c绕了一圈S又回到开头。这一步如果看不出来说明推导练习不够我当时的笨办法是把每个非终结符可能展开的路径写两三层发现“S开头最终还是会出现S”就算左递归。消除间接左递归的套路是把非终结符排序然后用后面的产生式反复代入把它转化成直接左递归再消。按顺序S、Q、R来。先把R产生式代入Q再把Q代入S最后得到S → S a b c | a b c | b c | c这就有直接左递归了。设α a b c候选β分别是a b c、b c、c。消除后得到S → a b c S | b c S | c SS → a b c S | ε到这一步公共左因子也要检查一下。三个候选的开头分别是a、b、c没有公共前缀所以不需要提取。接着求FIRST和FOLLOW就能构造预测分析表。我在答案里看到很多人直接跳过去求表其实最好把S的产生式写出来再求否则容易把S漏掉。这道题考得是“间接左递归的消除”和“LL(1)条件”的综合应用面试也爱问。4.2 习题2构造SLR分析表的完整过程我挑了一个必考文法带加法和乘法的表达式文法它的SLR分析表构造过程非常标准也很适合手把手过一遍。文法如下E → E T | TT → T * F | FF → ( E ) | id先加上增广产生式 E → E然后构造LR(0)自动机。状态0里包含E→·E和所有E、T、F的初始项目。我从状态0开始列几个关键状态状态1是E→E·和E→E·T状态2是E→T·和T→T·*F状态4是F→(·E)以及E和T、F的全部项目状态6是E→E·T以及T、F的项目状态8是F→(E·)和E→E·T状态9是E→ET·和T→T·*F。把这些画出来再计算FOLLOW集FOLLOW(E) { $ , , ) }FOLLOW(T) { , * , ) , $ }FOLLOW(F) { , * , ) , $ }然后构造SLR分析表。我这里只列关键几行作为示范。状态0遇到(移进到4遇到id移进到5非终结符E去1、T去2、F去3。状态1遇到移进到6遇到$接受。状态2遇到*移进到7遇到、)、$归约E → T。状态4遇到(移进到4遇到id移进到5非终结符E去8、T去2、F去3。状态8遇到移进到6遇到)移进到11。状态9遇到*移进到7遇到、)、$归约E → E T。状态10遇到所有FOLLOW(T)里的终结符都归约T → T * F。走一遍id id * id的移进归约过程会发现SLR表就像是给每个状态配了一张指令卡驱动算法本身简单得让人惊讶。这里要特别提醒不要在求FOLLOW集时丢掉*。FOLLOW(T)之所以包含*是因为T后面可能跟着T * F中的*。很多人算到最后把*落了结果分析表里状态9遇到*不知道该移进还是归约直接报废。4.3 习题3二义性文法的判断题判断二义性也是高频大题。最经典的二义文法就是E → E E | E * E | ( E ) | id为什么是二义性因为id id * id可以有两棵不同的语法树。如果先算语法树左边是(EE)*E我这里说清楚一种解读是id (id * id)另一种是(id id) * id这两棵树的根不同说明同一个句子对应两种不同的最左推导于是文法就是二义性的。二义性文法一定不是LL(1)也不是LR(1)因为分析表某个格子一定会有冲突。判断一个文法是否二义性没有固定算法只能靠构造反例。我刷题时的经验是优先找那种可以“先结合左边”也可以“先结合右边”的句子比如有连续两个同优先级运算符或者一个句子能同时用两种方式归约。解决二义性的通用手段是改写文法引入优先级层次。比如把上面的文法改写成E → E T | TT → T * F | FF → (E) | id本质就是把和*拆到不同层级让优先级高的*先被归约。如果是在Yacc这类工具中也可以用%left和%right声明优先级和结合性但考试通常要求改写文法。5. 刷题和复习中的高频错误与排查技巧5.1 集合运算和ε处理最常见的翻车点我见过大量同学在FIRST和FOLLOW上翻车翻车点高度集中在ε处理。比如求FIRST(α)时有人直接把ε写进FIRST(E)导致后面预测分析表里出现“空串列”求FOLLOW时有人忘记对“β可能推出ε”的情况传递FOLLOW。我建议每次求完FOLLOW后做一个自我检查所有非终结符的FOLLOW集合一定包含$吗不一定只有开始符号以及能到达开始符号位置的符号才包含。但开始符号的FOLLOW一定有$。如果求出来开始符号没有$不用想肯定错了。还有一个隐蔽坑是“迭代求不动点”。很多课后题答案会省略迭代步骤直接写最终集合但你自己刷题时一定要保留每一轮变化。比如有文法A → B a | εB → A b求FOLLOW的时候A的FOLLOW要传给BB的FOLLOW又反过来影响A必须来回跑两三轮才能稳定。我刷这类型题目时会把每个集合用表格记录像解方程一样不断更新这样既不容易漏也对得起步骤分。5.2 移进归约冲突怎么判断、怎么解决分析表里的冲突分成两类移进-归约冲突和归约-归约冲突。看到“冲突”这个词先别慌判断方法是找一个状态看里面是否存在至少一个移进项目和一个归约项目并且当前输入符号既能触发移进又能触发归约。如果存在就是移进-归约冲突如果存在两个归约项目且它们的FOLLOW集有交集就是归约-归约冲突。解决冲突的方向有三个。第一改写文法这是最根本的办法。第二利用优先级和结合性比如算符优先分析中定义优先级关系Yacc里用%left、%right。第三增加向前看的信息从LR(0)升级到SLR或者从SLR升级到LR(1)。做题时要注意题目问的是“用SLR能否解决”还是“该文法是否为LR(1)”因为同一个文法的答案可能不一样。比如前面那个S → L R例子SLR处理不了但LR(1)能处理。这类题目从“为什么不行”出发去理解比死记“哪个文法是不是SLR”要牢靠得多。5.3 选择题和面试题的套路总结我复习时把选择题和面试题归成几个固定套路这里直接分享一张速查表考试前扫一眼特别有用。LL(1)中“1”表示每次决策向前看1个输入符号。LR(1)则表示从左到右扫描、最右推导逆过程、向前看1个符号。哪个分析器适合递归下降手写LL(1)。哪个分析器是Yacc默认LALR(1)。判断一个文法不是LL(1)最快的线索有哪些左递归、公共左因子、FIRST集相交。LR(0)和SLR最大的区别是什么SLR在归约时检查FOLLOW集。为什么LR(1)比SLR更精确因为展望符从FOLLOW集合细化到具体上下文。LALR合并状态后一定会减少状态数吗是但不一定还能保持无冲突如果引入归约-归约冲突就不是LALR。面试题则更喜欢让你现场设计一个小语言的Parser。比如“用Java手写一个支持加减乘除和括号的解析器”这就是典型的递归下降流程是定义Token类型写parseExpression、parseTerm、parseFactor三个方法利用方法调用顺序体现优先级。如果你能顺带说清楚“左递归会导致递归下降死循环所以要消除左递归”面试官通常就会点头。这部分我把热词“java编译原理”也串进来了把语法分析的手工实现和算法原理结合着理解对笔试和面试都有奇效。6. 我的笔记整理方法和复习节奏个人经验6.1 一套可以复用的语法分析笔记长什么样我不喜欢抄书式笔记抄完再看就像看目录没有任何信息增量。我最后形成的笔记结构是四张卡片。第一张叫“概念卡”记录FIRST、FOLLOW、活前缀、项目、展望符这些名词每个名词旁边用自己的话写一句解释。比如FIRST集是“一个非终结符开口第一句话可能出现的词”FOLLOW集是“别人在它后面可能会接的词”活前缀是“还没凑成句柄的那半句话”。这种口语化翻译对我帮助很大。第二张叫“算法卡”记录每个算法的输入、输出和步骤不写大段原理只写关键操作。比如“求FOLLOW三步先$、再FIRST、再传递”。第三张叫“易错卡”把我在课后习题里错过的点都记下来比如“FOLLOW(F)漏了*”“预测分析表里没有填ε”“LALR合并后可能产生归约-归约冲突”。第四张叫“例题卡”每个类型挑一道最经典的题步骤写完整旁边标注“如果改掉哪个条件会变成什么”。我就是用Markdown表格把这些卡片拼起来的复习时只看自己的版本效率比重新翻书高很多。哈工大和吉林大学的课件讲义我也借来对照过它们的好处是会给很多例题变体但里面有些内容偏研究型不适合期末冲刺。我建议把它们当成“题源”而不是“教材”。6.2 课后习题到底怎么刷才算有效课后习题不是“会做”就够而是要做到“能讲给别人听”。我的刷法分三轮。第一轮按章节顺序把每道题都当成大题做即使答案只有一句话我也要写出完整推导过程。比如选择题问“哪个文法不是LL(1)”我也要在旁边写出消除左递归后的样子或者标出FIRST集合哪里冲突。第一轮不求速度求覆盖所有题型。第二轮把相同类型题放在一起做体会出题人是怎么换参数的。比如今天做“LL(1)判断”明天做“LR(0)自动机构造”你会发现很多题目只是同一个核心算法换了件马甲。第三轮只刷错题并且给自己计时模拟考场的紧张感。很多同学喜欢直接对着教材第三版答案抄我特别不推荐。正确做法是先把答案盖上自己在草稿纸上写满一整页再去核对答案。重点看“步骤”而不是“结果”。如果结果对了但步骤不对将来遇到变体题还是会错。还有一个小技巧每道课后题做完后我会顺手编一道反向题目。比如这道题让判断LL(1)我就把文法加一个公共左因子让它变成非LL(1)然后重新做一遍。这个办法一开始很慢但坚持下来之后遇到新题基本不会慌。最后再分享一个小习惯。我复习语法分析时给每个算法都画了一张“输入 - 过程 - 输出”的小卡片。比如LL(1)预测分析输入是文法、输出是预测分析表LR(0)自动机构造输入是文法、输出是项目集规范族和goto表。每学一个新算法就把这张卡片贴在墙上学完一章看一眼整个结构在脑子里自然就立住了。这个方法我在考研复试前帮了大忙虽然听起来土但真的比反复看课件管用。