如果你正在啃编译原理的语法分析这一章大概率会被“句型”“句子”“短语”“直接短语”“句柄”“素短语”“最左素短语”这一串名词砸晕。我第一次看到“句柄”这个词时满脑子都是 Windows 报错里那个“句柄无效”心想编译原理怎么还跟操作系统扯上关系了。后来才明白这里的“句柄”完全是一棵树上的概念它不玄乎就是把语法分析树上的某些节点子树按叶子顺序拎出来然后挨个起名字而已。这篇文章我打算把这些概念一次性讲透。我会先讲清楚它们到底在解决什么问题再一个定义一个定义拆开最后用一个完整例子把七个概念同时标在同一棵语法树上再给你一份可以直接照着做的五步操作流程。无论你是期末复习、考研冲刺还是面试前临时抱佛脚这篇文章都能让你少走很多弯路。你要是能静下心读完后面遇到这类题基本就是送分题。1. 先把背景说清楚这些概念到底在解决什么问题1.1 从“一句话怎么被计算机看懂”说起编译原理里语法分析要做的事情本质上就是判断一段程序代码或者一个表达式是否符合文法规则。你写了一个a b * c编译器不会直接说“我看懂了”它会先按照文法规则去匹配这个式子是不是一个合法的表达式如果是它是怎么从开始符号一步步推导出来的这个“一步步推导”的过程就会产生一个树形结构叫语法树或者推导树。树上的每一个节点都对应文法里的一个符号从根节点开始按照产生式不断展开直到所有叶子都是终结符整棵树就完整了。而我们今天要讲的句型、短语、句柄这些概念全部都是在这棵树上做文章的。可以这么说理解了语法树就理解了这七个概念的一大半。我上课的时候经常打一个比方文法就是乐高积木的说明书语法树就是你按说明书拼出来的成品而“短语”就是从成品里拆下来的任何一个能独立成块的积木组合。你拆下来一块它得是“合法”的不能随便掰断一块必须是从某个拼装节点开始、一路往下包含的所有零件。1.2 句型、句子、语言三个容易混的“范围”很多人一上来就把“句型”和“句子”搞混。其实区别很简单从文法的开始符号出发经过一步或若干步推导得到的符号串都叫句型。句型里面可能还有非终结符比如“E T”这种它还不是一个完整的、只由终结符组成的串。如果这个句型里面一个非终结符都没有了全部都是终结符那它就升级成了“句子”。换句话说句子是特殊的句型是“推导到头了”的句型。至于“语言”那就更简单了就是某条文法能产生的所有句子的集合。你不需要把所有句子都列出来只需要用文法规则来描述它们就行。很多教材开篇就会讲这个概念但真正到了语法分析部分反而容易忘。我建议你记住一条线语言是句子的集合句子是只含终结符的句型句型是能从开始符号推导出来的任意符号串。这个层级关系搞清楚了后面读教材会顺畅很多。1.3 为什么要先画语法树你可能已经发现了前面说的句型、句子不画树也能理解。但短语、直接短语、句柄这些概念如果不画语法树几乎是没法讲的。原因是短语的定义是“句型的某个非终结符的子树的所有叶子从左到右拼起来的串”。你光看字符串本身看不出它是从哪个子树冒出来的。比如“abbcBe”这个串哪个部分是短语这得看它对应的语法树长什么样。所以我的建议是拿到任何相关题目第一步就是画语法树不是先想“这个词应该是什么”而是先画树画完树所有概念都自动浮出来了。这个习惯比背十遍定义都管用。2. 逐个拆开七个名词到底都是什么意思2.1 句型与句子从开始符号出发的推导先看严格定义。给定文法 G开始符号为 S。如果 S 经过零步或若干步推导能推出 α也就是 S ⇒* α那么 α 就是文法 G 的一个句型。注意这个“零步”也就是说 S 本身也是句型。这算是一个小细节很多题目会在这里挖坑问“开始符号是不是句型”答案是肯定的。句型里如果只含终结符不含任何非终结符那它就是句子。比如算术表达式文法E → E T | TT → T * F | FF → (E) | i里E T是句型但不是句子因为里面有非终结符 T而i i就是句子因为全是终结符了。这里我补一句经验考试里经常让你判断“某个符号串是不是该文法的句子”。你可以反过来想如果它能从开始符号一路推导出来而且中间能做到全部换成终结符那就是句子。如果推导中途卡住了或者根本推不出来那就不是。2.2 短语与直接短语语法树上一眼看出短语的定义比较绕如果 α 是从某个非终结符 A 经过一步或若干步推导得到的符号串即 A ⇒* α并且 S ⇒* β A γ那么 α 就是句型 β α γ 相对于非终结符 A 的短语。这定义看得人头大我来说人话在一棵语法树里任意一个非叶子节点以它为根的那棵子树所有叶子从左到右拼出来的串就是整个句型的一个短语。就这么简单。直接短语就是更严格一点如果 A ⇒ α 是一步推导也就是说这个节点的孩子刚好就是它的那串叶子中间没有再经过其他非终结符的展开那么这个串就是直接短语。举个例子。文法S → aAcBe推导出句型abbcBe。语法树里 A 节点下面如果挂的是“A → Ab”然后 A 再推出 b那么 A 节点对应的叶子串是“bb”而里面那层 A 节点对应的叶子串是“b”。这时候“bb”是一个短语“b”也是一个短语。但“bb”不是直接短语因为 A 推出 Ab 是一次推导Ab 不是叶子串而“b”是直接短语因为最里层的 A 直接推导出了 b一步到位。再强调一次直接短语一定满足“从某个非终结符一步推出”。凡是需要两步以上才能推出的统统只是短语而不是直接短语。2.3 句柄最左直接短语但要注意它的“右手”句柄的定义很精炼一个句型的最左直接短语叫做这个句型的句柄。注意“最左”这两个字。一个句型里可能有好几个直接短语从左往右看排在最左边的那个才是句柄。别小看这两个字很多做题做错的人都是因为只找了直接短语忘了选最左。在自底向上的语法分析里句柄之所以重要是因为它正好对应“规约”时该先处理的部分。你可以把规约理解成语法树的“倒放”从叶子往上拼积木每次遇到一个能一步拼成父节点的子结构就把它归约掉。那么每次先归约的一定是最左边的可归约串也就是句柄。还有一个小细节句柄是针对“一个右句型”来说的。规范推导最右推导得到的句型叫右句型。在 LR 分析里句柄这个概念基本都出现在右句型中。有些教材说“句柄是活前缀的后缀”这是从状态栈的角度去看的你学到 LR 那一节会体会更深。2.4 素短语与最左素短语至少要含一个终结符素短语这个概念很多人第一次接触都会懵因为它比前面几个多了一堆限制条件。定义是这样如果某个短语 α 满足两个条件第一它至少包含一个终结符第二它自身不再包含更小的素短语那它就叫做素短语。第二句话看起来很绕我换个说法在一个句型的所有短语里找出那些“至少含一个终结符”的然后再从里面筛掉那些“还包含其他素短语”的剩下的就是素短语。最左素短语就是所有素短语里最靠左边的那个。算符优先分析里最左素短语就是每次规约的目标。为什么因为算符优先分析不看非终结符的具体身份只看终结符之间的优先关系所以它只能抓“包含终结符的可归约串”这就是素短语存在的意义。我当年学到这里最大的困惑是句柄和素短语到底什么关系后来明白了两者不一定相同。句柄是“最左直接短语”它可能完全不含终结符——比如某个非终结符直接推出另一个非终结符而素短语要求“至少含一个终结符”。所以你说“句柄就是最左素短语”是不对的只有满足特殊情况时才成立。2.5 概念对照速查表为了方便你后面做题时快速对照我把这七个概念整理成一张表概念核心要求与语法树的关系常见误区句型从开始符号可推导出的符号串整棵语法树的叶子串忘记开始符号自身也是句型句子只含终结符的句型叶子全是终结符的完整树把还含非终结符的串当成句子短语某个非终结符的子树叶子串任意非叶子节点的叶子序列把任意子串都当成短语直接短语从某非终结符一步推出的短语孩子节点直接就是叶子的子树忘了“一步推出”这个条件句柄最左直接短语语法树最左边的一个“成品块”只找直接短语忘加“最左”素短语至少含一个终结符且不含更小素短语短语中满足两条件的子集误以为句柄就是素短语最左素短语最左边的素短语算符优先分析的规约目标和句柄混淆这张表你做题前扫一眼基本就能把方向定住。3. 一个完整例子把七个概念全部标在同一棵树上3.1 例子的文法与推导过程光讲定义太干了我们直接上题。给定文法S → aAcBe A → Ab | b B → d现在请找出句型abbcBe的所有短语、直接短语、句柄、素短语和最左素短语。先别急着看答案我带你一步步推。首先我们要确认这个句型确实能推出来。用最右推导S ⇒ aAcBe ⇒ aAbcBe ⇒ abbcBe第一步S 展开成 a A c B e第二步把 A 展开成 Ab第三步把最左边的 A 展开成 b。搞定abbcBe确实是从开始符号 S 推导出来的它是一个句型而且因为里面还有非终结符 B它不是句子。3.2 画出语法树并找所有子树叶子现在我们画语法树。根是 S孩子从左到右是 a、A、c、B、e。其中 A 不是叶子它下面又挂了 A 和 b这个内层 A 再往下又挂了 b。这棵树我大概给你描述一下你自己画一遍更好S / | | | \ a A c B e / \ A b | b注意看B 下面只有一个 d所以在这个句型里 B 的叶子是 d。但题目里的句型是abbcBe那 B 后面还跟着 e所以句型最后的串是a b b c B e其中的 B 是尚未归约成 d 的非终结符。这里有个容易犯迷糊的点我们求的是“句型”的短语所以语法树里允许还存在非终结符叶子比如这里的 B。它不是终结符但它是这棵推导树当前状态下的一个叶子节点。现在开始找所有非叶子节点S 节点它的子树叶子串是abbcBe这是一个短语。a 节点它是叶子没有子树不算。A 节点外层它下面包含内层 A 和 b内层 A 又包含 b所以它的叶子串是bb这是一个短语。c、B、e 节点这三个是最外层的孩子。但要注意直接挂在 S 下面的 a、c、e它们本身是叶子不是非叶子节点不过它们也是 S 的孩子所以它们各自的叶子串 a、c、e 也是短语严格说短语的定义要求“某个非终结符的子树叶子串”。非终结符 aa 是终结符不是非终结符。所以应该这么说像 a、c、e 这些它们是 S 一步推导出的直接短语因为 S → aAcBe 这一步里a、c、e 就是一步推出来的终结符。更准确的说法a 是 S 的子树中一个叶子节点它对应的是 S 的孩子所以它算短语也属于直接短语。B 节点它的叶子是 d但在当前句型abbcBe里B 还没被推导成 d所以 B 的叶子串应该是 B 自身这里就要特别注意了。按照语法树语义B 是叶子节点因为它没有再向下展开。所以 B 不构成短语因为短语要求“非终结符的子树叶子串”B 本身没有子树。等一下那我刚才说“a、c、e 是短语”对吗它们确实是 S 的孩子但它们不是非终结符的子树。按照教材定义S 的孩子节点 a、c、e 都是叶子它们的“子树”只有自己而自己又是终结符所以它们可以作为“直接短语”出现因为 S ⇒ aAcBe 中终结符 a、c、e 是由 S 一步推出的。对于直接短语的定义我们说的是“如果 α 是一个直接短语那么存在某个非终结符 A使得 A ⇒ α 是一步推导”。对于 a就是 S ⇒ a...所以 a 是直接短语。对于短语的定义由于直接短语必然是短语所以 a、c、e 也都是短语。这类边界情况考试里经常有我给你一个稳妥的判断方法看这个符号是不是某个内部节点的“一步产物”。如果是它就算直接短语如果它是某个内部节点下经过多次推出来的整块叶子序列那就算普通短语。3.3 逐一匹配短语、直接短语、句柄现在我们把这个句型的所有短语列出来abbcBe整体对应 S 的子树叶子串是短语。bb对应外层 A 的子树叶子串是短语。b里层那个对应内层 A 的子树叶子串是短语。b外层 A 右边那个这其实和上面是同一个节点不对外层 A 的右孩子是 b它是一个单独的叶子也是短语。a、c、e它们是 S 一步推导出的终结符是短语。d在这个句型里 B 还是非终结符没有被推导成 d所以 d 不在这个句型里。还需要考虑ab是短语吗不是。虽然 A 的叶子是 bb但 S 的左孩子 a 加 A 的叶子合起来是abb这对应的是 S 从“aA...”整个子树里的一部分但没有一个非终结符的子树恰好是abb。所以不是。abc是吗也不是。它跨过了 S 的几个孩子不是一个完整子树的叶子序列。所以这个句型的短语有abbbbceabbcBe。注意这里有两个b。一个是内层 A 推出的 b一个是外层 A 右孩子那个 b。它们都是短语都叫 b但是对应语法树上不同位置。接下来找直接短语。直接短语要满足“某个非终结符一步推出”aS → aAcBe一步推出 a是直接短语。bbA → Ab这里 A 推出的是 Ab不是 bbA 推出 bb 需要两步A ⇒ Ab ⇒ bb所以bb不是直接短语。外层 A 右孩子b这一步是 A → Ab 的第二次推导也就是内层 A → b 推出来的但外层 A 的右孩子 b是不是由某个非终结符一步推出来的它是内层 A 的右孩子确切地说这个 b 是内层 A → b 的一步产物所以它是直接短语。内层 A 的叶子b同样内层 A → b一步推出是直接短语。c、eS → aAcBe 一步推出是直接短语。abbcBeS 经过三步推出不是直接短语。所以直接短语是a、b、b、c、e。句柄是最左直接短语。从左往右看第一个直接短语是a所以句柄就是a。这一步很关键。很多同学会把句柄答成b因为他从左往右扫描字符串abbcBe先看到一个 a再看到 b以为最左边的直接短语是 b。但实际上 a 也是直接短语而且它比 b 更靠左。所以句柄就是 a。3.4 素短语和最左素短语在这个例子里的特殊情况现在求素短语。素短语要求至少包含一个终结符且自身不再包含更小的素短语。先拿所有短语来看a包含终结符 a它里面没有再小的短语所以是素短语。b两个包含终结符 b自身没有更小素短语所以都是素短语。bb包含终结符但它里面含有素短语b里层那个 b所以bb不是素短语。c是素短语。e是素短语。abbcBe它不是素短语因为它里面包含 a、b、b、c 等多个素短语。所以素短语是a、b、b、c、e。最左素短语就是最左边的那个素短语从左往右找是a。发现没有在这个例子里句柄和最左素短语刚好是同一个都是a。这并不是巧合而是因为这里的句柄a本身就包含终结符。后面我会专门讲两者什么时候相等、什么时候不等。3.5 可复用的五步流程做完这道题我把操作流程抽象出来你以后遇到类似题目直接照做第一步写出推导过程确认给出的串确实是句型。如果不是直接结束后面都谈不上。第二步画出语法树。这一步不能省也别在脑子里空想画在纸上最保险。第三步找出所有非叶子节点分别写下它们各自子树的叶子序列。左边写节点名右边写叶子串列成一张表。第四步根据“叶子序列是否为某个非叶子节点的子树叶子串”筛出短语再根据“是否由某非终结符一步推出”筛出直接短语然后从直接短语里从左往右取第一个得到句柄。第五步从短语里筛出“至少含一个终结符且不含更小素短语”的得到素短语再取最左边的得到最左素短语。这套流程用顺了一道题三分钟就能做完。我自己做题和复习带人都是这个套路还没失手过。4. 特例与易错点句柄和素短语的经典陷阱4.1 句柄一定是直接短语直接短语不一定是句柄这是我觉得最需要敲黑板的地方。句柄是“最左直接短语”所以它首先得是直接短语。但一个句型里往往有多个直接短语只有最左边那个才配叫句柄。比如前面例子里的直接短语有 a、b、b、c、e其中 b 出现了两次c 和 e 也都是直接短语但句柄只有一个 a。做题时如果你只找直接短语不排序或者排序排错就很容易答错。还有更隐蔽的情况某个直接短语恰好是另一个直接短语的前缀。比如直接短语第一个是i第二个是i i这种这时最左直接短语肯定是i。这时候有人会犹豫因为后面的直接短语更长包含前面的是不是应该合并不是。句柄就是最左那个直接短语本身不合并、不取最长。4.2 素短语至少含一个终结符但不是说不能含多个素短语的定义里有“至少包含一个终结符”这个“至少”很关键。一个素短语可以只含一个终结符也可以含多个终结符还可以同时含非终结符和终结符的混合串。看这个例子文法E → E T | TT → T * F | FF → (E) | i句型E T * F里短语T * F包含终结符而且它内部有没有更小的素短语它内部的F是短语但 F 不含终结符F 是非终结符不是终结符所以 F 不能被算作素短语。因此T * F内部没有更小的素短语那T * F本身就是一个素短语尽管它的叶子是“T、、F”混合了非终结符。所以判断素短语时不要想着“素”就是“纯终结符”“素”的意思是“不可再分解的、含终结符的块”。它完全可以是T * F这种样子。4.3 最左素短语和句柄什么时候相等这个问题考试和面试都爱问。我直接给结论如果句柄本身至少包含一个终结符并且这个句柄内部没有任何更小的素短语那么句柄就是最左素短语二者相等。如果句柄完全不含终结符比如某个非终结符直接推出另一个非终结符那它就不是素短语此时最左素短语往往是句柄之后、在扫描过程中第一个遇到的含终结符可归约串。不过在实际语法分析过程中尤其是 LL 分析和 LR 分析里我们更关心句柄而在算符优先分析里因为文法通常不含形如A → B这种“单非终结符到单非终结符”的产生式所以句柄基本都含终结符这时候句柄和最左素短语常常是同一个东西。4.4 算符优先分析中为什么会盯上最左素短语算符优先分析是一种自底向上的语法分析方法它的特点是只看终结符之间的优先关系不关心非终结符的名字。这就导致它没法像 LR 分析那样精确知道当前栈顶的“句柄”是什么它只能根据终结符的优先级关系找到“最左素短语”然后把这一整块归约掉。这就是为什么素短语和最左素短语在算符优先分析里特别重要。你可以把最左素短语理解为“算符优先分析语境下的句柄”。它没有句柄那么强但足够指导规约动作。我之前复习的时候总是搞混 LR 和算符优先的归约目标后来用一个办法记住LR 归约看句柄算符优先归约看最左素短语。一个是精确制导一个是雷达粗扫。这样想就顺了。4.5 活前缀和可归约串的关联学到 LR 分析时你还会遇到“活前缀”这个概念。活前缀是规范句型的一个前缀它不包含句柄之后的任何符号。简单说在从左到右扫描输入串时已经读入的那部分如果还没超出句柄的范围就属于活前缀。这个点和今天的话题关系很深。因为 LR 分析表本质上就是用来识别“当前栈里的串是不是某个句型的一个活前缀”。当栈顶形成完整句柄时就执行归约。所以你看句柄不是孤立的它是整条自底向上分析主线的核心。素短语则是在更粗糙的算符优先分析里的替代品。5. 常见问题排查与避坑清单5.1 常见问题速查表我把这些年学生问得最多的问题整理成一张表你可以对着自查问题原因解决办法把不是短语的子串当成了短语没画语法树靠肉眼从原串里截取强制自己先画树再找子树叶子直接短语漏掉了单个终结符忘了终结符也可以是某非终结符的一步产物检查语法树中每个内部节点的孩子是否全为叶子句柄找错忘了“最左”两个字或者没把所有直接短语都找全先列举所有直接短语再从左到右选第一个素短语找错没排除“包含更小素短语”的情况从最小短语开始筛逐层检查分不清句柄和最左素短语概念混在一起没有先分类先独立求出各自结果再对比不要互相推导句型里含非终结符不知道还能不能有短语可以短语定义没要求必须是终结符串照常画树非终结符是叶子也可以作为边界5.2 我自己踩过的坑别把短语当“任何子串”我当年学这一节时犯过一个很蠢的错。题目给了一个句型abbcBe我脑子里浮现出“短语就是句型里的任意可理解片段”然后兴高采烈地把ab、bc、bb c都写了上去结果被老师画了一堆叉。后来我才意识到短语这个概念有一个隐含前提它必须对应某个非终结符的“完整子树叶子序列”。也就是说你不能从中间切开必须从某个非叶子节点往下把这个节点覆盖到的所有叶子全部取走。少一片叶子都不行。这个坑特别容易踩因为你平时看字符串看习惯了总觉得“看着像一块”就行。实际上语法树说了算树上是完整子树才是短语树上是残片就不是。我还记得当年有个同学问“那为什么abb不是短语它看起来不是挺完整的吗”答案是没有任何一个非终结符的子树叶子序列恰好是abb。S 的子树是abbcBeA 的子树是bba 和 bb 拼起来虽然也是abb但中间没有一个节点正好覆盖 a 和 A所以它不是短语。5.3 面试和考试中怎么答才有区分度如果你是在准备面试面试官问到这些概念千万别只背定义。我建议你按这个思路答先一句话定位这些概念是语法分析中用来确定“规约单位”的。然后快速区分句柄和素短语句柄是最左直接短语服务于 LR 类自底向上分析最左素短语是算符优先分析中真正执行规约的串。然后主动举一个例子不需要多复杂能说明问题就行。比如直接说“考虑文法 S → aAcBe句型 abbcBe 的句柄是 a最左素短语也是 a但在某些文法里二者不同因为它们对终结符的要求不一样。”这样回答既展示了你对定义的掌握又体现了你理解这些概念在什么场景下用、为什么用面试官印象会好很多。另外要提醒一点如果你被问到“句柄在 LR 分析里怎么找”不要说“就是最左直接短语”就完了。你可以补一句“LR 分析器通过状态栈和向前看符号来识别当前栈顶是否形成了句柄形成后就按相应产生式归约。”这能体现出你不仅知道定义还知道工程实现。最后再分享一个我的心得体会我带过的学生里凡是能把这几组概念用自己的话讲清楚、并且能随手举出例子的人基本上语法分析部分的题目都不会失分。反过来那些只背定义、不画树的人十个里有八个会在“直接短语”“句柄”上丢分。我个人实操下来最有效的训练方法就是找五道关于句型短语的练习题每道都严格按照“画树 → 列叶子 → 分类 → 取最左”的流程走做完了再去对答案。一开始可能会慢一道题要十几分钟但做完三道之后基本就能在五分钟内搞定一道。如果你手里暂时没有合适的题目就拿本文的两个例子反复练一个是S → aAcBe的那个一个是算术表达式文法E → E T | T、T → T * F | F、F → (E) | i的那个。你可以试着求一下句型E T * F的短语和直接短语再求一下i i * i的素短语做完你就会发现这些概念真的不难只是需要多动手、多画树。
编译原理语法分析：句型、短语、句柄与素短语全解析
如果你正在啃编译原理的语法分析这一章大概率会被“句型”“句子”“短语”“直接短语”“句柄”“素短语”“最左素短语”这一串名词砸晕。我第一次看到“句柄”这个词时满脑子都是 Windows 报错里那个“句柄无效”心想编译原理怎么还跟操作系统扯上关系了。后来才明白这里的“句柄”完全是一棵树上的概念它不玄乎就是把语法分析树上的某些节点子树按叶子顺序拎出来然后挨个起名字而已。这篇文章我打算把这些概念一次性讲透。我会先讲清楚它们到底在解决什么问题再一个定义一个定义拆开最后用一个完整例子把七个概念同时标在同一棵语法树上再给你一份可以直接照着做的五步操作流程。无论你是期末复习、考研冲刺还是面试前临时抱佛脚这篇文章都能让你少走很多弯路。你要是能静下心读完后面遇到这类题基本就是送分题。1. 先把背景说清楚这些概念到底在解决什么问题1.1 从“一句话怎么被计算机看懂”说起编译原理里语法分析要做的事情本质上就是判断一段程序代码或者一个表达式是否符合文法规则。你写了一个a b * c编译器不会直接说“我看懂了”它会先按照文法规则去匹配这个式子是不是一个合法的表达式如果是它是怎么从开始符号一步步推导出来的这个“一步步推导”的过程就会产生一个树形结构叫语法树或者推导树。树上的每一个节点都对应文法里的一个符号从根节点开始按照产生式不断展开直到所有叶子都是终结符整棵树就完整了。而我们今天要讲的句型、短语、句柄这些概念全部都是在这棵树上做文章的。可以这么说理解了语法树就理解了这七个概念的一大半。我上课的时候经常打一个比方文法就是乐高积木的说明书语法树就是你按说明书拼出来的成品而“短语”就是从成品里拆下来的任何一个能独立成块的积木组合。你拆下来一块它得是“合法”的不能随便掰断一块必须是从某个拼装节点开始、一路往下包含的所有零件。1.2 句型、句子、语言三个容易混的“范围”很多人一上来就把“句型”和“句子”搞混。其实区别很简单从文法的开始符号出发经过一步或若干步推导得到的符号串都叫句型。句型里面可能还有非终结符比如“E T”这种它还不是一个完整的、只由终结符组成的串。如果这个句型里面一个非终结符都没有了全部都是终结符那它就升级成了“句子”。换句话说句子是特殊的句型是“推导到头了”的句型。至于“语言”那就更简单了就是某条文法能产生的所有句子的集合。你不需要把所有句子都列出来只需要用文法规则来描述它们就行。很多教材开篇就会讲这个概念但真正到了语法分析部分反而容易忘。我建议你记住一条线语言是句子的集合句子是只含终结符的句型句型是能从开始符号推导出来的任意符号串。这个层级关系搞清楚了后面读教材会顺畅很多。1.3 为什么要先画语法树你可能已经发现了前面说的句型、句子不画树也能理解。但短语、直接短语、句柄这些概念如果不画语法树几乎是没法讲的。原因是短语的定义是“句型的某个非终结符的子树的所有叶子从左到右拼起来的串”。你光看字符串本身看不出它是从哪个子树冒出来的。比如“abbcBe”这个串哪个部分是短语这得看它对应的语法树长什么样。所以我的建议是拿到任何相关题目第一步就是画语法树不是先想“这个词应该是什么”而是先画树画完树所有概念都自动浮出来了。这个习惯比背十遍定义都管用。2. 逐个拆开七个名词到底都是什么意思2.1 句型与句子从开始符号出发的推导先看严格定义。给定文法 G开始符号为 S。如果 S 经过零步或若干步推导能推出 α也就是 S ⇒* α那么 α 就是文法 G 的一个句型。注意这个“零步”也就是说 S 本身也是句型。这算是一个小细节很多题目会在这里挖坑问“开始符号是不是句型”答案是肯定的。句型里如果只含终结符不含任何非终结符那它就是句子。比如算术表达式文法E → E T | TT → T * F | FF → (E) | i里E T是句型但不是句子因为里面有非终结符 T而i i就是句子因为全是终结符了。这里我补一句经验考试里经常让你判断“某个符号串是不是该文法的句子”。你可以反过来想如果它能从开始符号一路推导出来而且中间能做到全部换成终结符那就是句子。如果推导中途卡住了或者根本推不出来那就不是。2.2 短语与直接短语语法树上一眼看出短语的定义比较绕如果 α 是从某个非终结符 A 经过一步或若干步推导得到的符号串即 A ⇒* α并且 S ⇒* β A γ那么 α 就是句型 β α γ 相对于非终结符 A 的短语。这定义看得人头大我来说人话在一棵语法树里任意一个非叶子节点以它为根的那棵子树所有叶子从左到右拼出来的串就是整个句型的一个短语。就这么简单。直接短语就是更严格一点如果 A ⇒ α 是一步推导也就是说这个节点的孩子刚好就是它的那串叶子中间没有再经过其他非终结符的展开那么这个串就是直接短语。举个例子。文法S → aAcBe推导出句型abbcBe。语法树里 A 节点下面如果挂的是“A → Ab”然后 A 再推出 b那么 A 节点对应的叶子串是“bb”而里面那层 A 节点对应的叶子串是“b”。这时候“bb”是一个短语“b”也是一个短语。但“bb”不是直接短语因为 A 推出 Ab 是一次推导Ab 不是叶子串而“b”是直接短语因为最里层的 A 直接推导出了 b一步到位。再强调一次直接短语一定满足“从某个非终结符一步推出”。凡是需要两步以上才能推出的统统只是短语而不是直接短语。2.3 句柄最左直接短语但要注意它的“右手”句柄的定义很精炼一个句型的最左直接短语叫做这个句型的句柄。注意“最左”这两个字。一个句型里可能有好几个直接短语从左往右看排在最左边的那个才是句柄。别小看这两个字很多做题做错的人都是因为只找了直接短语忘了选最左。在自底向上的语法分析里句柄之所以重要是因为它正好对应“规约”时该先处理的部分。你可以把规约理解成语法树的“倒放”从叶子往上拼积木每次遇到一个能一步拼成父节点的子结构就把它归约掉。那么每次先归约的一定是最左边的可归约串也就是句柄。还有一个小细节句柄是针对“一个右句型”来说的。规范推导最右推导得到的句型叫右句型。在 LR 分析里句柄这个概念基本都出现在右句型中。有些教材说“句柄是活前缀的后缀”这是从状态栈的角度去看的你学到 LR 那一节会体会更深。2.4 素短语与最左素短语至少要含一个终结符素短语这个概念很多人第一次接触都会懵因为它比前面几个多了一堆限制条件。定义是这样如果某个短语 α 满足两个条件第一它至少包含一个终结符第二它自身不再包含更小的素短语那它就叫做素短语。第二句话看起来很绕我换个说法在一个句型的所有短语里找出那些“至少含一个终结符”的然后再从里面筛掉那些“还包含其他素短语”的剩下的就是素短语。最左素短语就是所有素短语里最靠左边的那个。算符优先分析里最左素短语就是每次规约的目标。为什么因为算符优先分析不看非终结符的具体身份只看终结符之间的优先关系所以它只能抓“包含终结符的可归约串”这就是素短语存在的意义。我当年学到这里最大的困惑是句柄和素短语到底什么关系后来明白了两者不一定相同。句柄是“最左直接短语”它可能完全不含终结符——比如某个非终结符直接推出另一个非终结符而素短语要求“至少含一个终结符”。所以你说“句柄就是最左素短语”是不对的只有满足特殊情况时才成立。2.5 概念对照速查表为了方便你后面做题时快速对照我把这七个概念整理成一张表概念核心要求与语法树的关系常见误区句型从开始符号可推导出的符号串整棵语法树的叶子串忘记开始符号自身也是句型句子只含终结符的句型叶子全是终结符的完整树把还含非终结符的串当成句子短语某个非终结符的子树叶子串任意非叶子节点的叶子序列把任意子串都当成短语直接短语从某非终结符一步推出的短语孩子节点直接就是叶子的子树忘了“一步推出”这个条件句柄最左直接短语语法树最左边的一个“成品块”只找直接短语忘加“最左”素短语至少含一个终结符且不含更小素短语短语中满足两条件的子集误以为句柄就是素短语最左素短语最左边的素短语算符优先分析的规约目标和句柄混淆这张表你做题前扫一眼基本就能把方向定住。3. 一个完整例子把七个概念全部标在同一棵树上3.1 例子的文法与推导过程光讲定义太干了我们直接上题。给定文法S → aAcBe A → Ab | b B → d现在请找出句型abbcBe的所有短语、直接短语、句柄、素短语和最左素短语。先别急着看答案我带你一步步推。首先我们要确认这个句型确实能推出来。用最右推导S ⇒ aAcBe ⇒ aAbcBe ⇒ abbcBe第一步S 展开成 a A c B e第二步把 A 展开成 Ab第三步把最左边的 A 展开成 b。搞定abbcBe确实是从开始符号 S 推导出来的它是一个句型而且因为里面还有非终结符 B它不是句子。3.2 画出语法树并找所有子树叶子现在我们画语法树。根是 S孩子从左到右是 a、A、c、B、e。其中 A 不是叶子它下面又挂了 A 和 b这个内层 A 再往下又挂了 b。这棵树我大概给你描述一下你自己画一遍更好S / | | | \ a A c B e / \ A b | b注意看B 下面只有一个 d所以在这个句型里 B 的叶子是 d。但题目里的句型是abbcBe那 B 后面还跟着 e所以句型最后的串是a b b c B e其中的 B 是尚未归约成 d 的非终结符。这里有个容易犯迷糊的点我们求的是“句型”的短语所以语法树里允许还存在非终结符叶子比如这里的 B。它不是终结符但它是这棵推导树当前状态下的一个叶子节点。现在开始找所有非叶子节点S 节点它的子树叶子串是abbcBe这是一个短语。a 节点它是叶子没有子树不算。A 节点外层它下面包含内层 A 和 b内层 A 又包含 b所以它的叶子串是bb这是一个短语。c、B、e 节点这三个是最外层的孩子。但要注意直接挂在 S 下面的 a、c、e它们本身是叶子不是非叶子节点不过它们也是 S 的孩子所以它们各自的叶子串 a、c、e 也是短语严格说短语的定义要求“某个非终结符的子树叶子串”。非终结符 aa 是终结符不是非终结符。所以应该这么说像 a、c、e 这些它们是 S 一步推导出的直接短语因为 S → aAcBe 这一步里a、c、e 就是一步推出来的终结符。更准确的说法a 是 S 的子树中一个叶子节点它对应的是 S 的孩子所以它算短语也属于直接短语。B 节点它的叶子是 d但在当前句型abbcBe里B 还没被推导成 d所以 B 的叶子串应该是 B 自身这里就要特别注意了。按照语法树语义B 是叶子节点因为它没有再向下展开。所以 B 不构成短语因为短语要求“非终结符的子树叶子串”B 本身没有子树。等一下那我刚才说“a、c、e 是短语”对吗它们确实是 S 的孩子但它们不是非终结符的子树。按照教材定义S 的孩子节点 a、c、e 都是叶子它们的“子树”只有自己而自己又是终结符所以它们可以作为“直接短语”出现因为 S ⇒ aAcBe 中终结符 a、c、e 是由 S 一步推出的。对于直接短语的定义我们说的是“如果 α 是一个直接短语那么存在某个非终结符 A使得 A ⇒ α 是一步推导”。对于 a就是 S ⇒ a...所以 a 是直接短语。对于短语的定义由于直接短语必然是短语所以 a、c、e 也都是短语。这类边界情况考试里经常有我给你一个稳妥的判断方法看这个符号是不是某个内部节点的“一步产物”。如果是它就算直接短语如果它是某个内部节点下经过多次推出来的整块叶子序列那就算普通短语。3.3 逐一匹配短语、直接短语、句柄现在我们把这个句型的所有短语列出来abbcBe整体对应 S 的子树叶子串是短语。bb对应外层 A 的子树叶子串是短语。b里层那个对应内层 A 的子树叶子串是短语。b外层 A 右边那个这其实和上面是同一个节点不对外层 A 的右孩子是 b它是一个单独的叶子也是短语。a、c、e它们是 S 一步推导出的终结符是短语。d在这个句型里 B 还是非终结符没有被推导成 d所以 d 不在这个句型里。还需要考虑ab是短语吗不是。虽然 A 的叶子是 bb但 S 的左孩子 a 加 A 的叶子合起来是abb这对应的是 S 从“aA...”整个子树里的一部分但没有一个非终结符的子树恰好是abb。所以不是。abc是吗也不是。它跨过了 S 的几个孩子不是一个完整子树的叶子序列。所以这个句型的短语有abbbbceabbcBe。注意这里有两个b。一个是内层 A 推出的 b一个是外层 A 右孩子那个 b。它们都是短语都叫 b但是对应语法树上不同位置。接下来找直接短语。直接短语要满足“某个非终结符一步推出”aS → aAcBe一步推出 a是直接短语。bbA → Ab这里 A 推出的是 Ab不是 bbA 推出 bb 需要两步A ⇒ Ab ⇒ bb所以bb不是直接短语。外层 A 右孩子b这一步是 A → Ab 的第二次推导也就是内层 A → b 推出来的但外层 A 的右孩子 b是不是由某个非终结符一步推出来的它是内层 A 的右孩子确切地说这个 b 是内层 A → b 的一步产物所以它是直接短语。内层 A 的叶子b同样内层 A → b一步推出是直接短语。c、eS → aAcBe 一步推出是直接短语。abbcBeS 经过三步推出不是直接短语。所以直接短语是a、b、b、c、e。句柄是最左直接短语。从左往右看第一个直接短语是a所以句柄就是a。这一步很关键。很多同学会把句柄答成b因为他从左往右扫描字符串abbcBe先看到一个 a再看到 b以为最左边的直接短语是 b。但实际上 a 也是直接短语而且它比 b 更靠左。所以句柄就是 a。3.4 素短语和最左素短语在这个例子里的特殊情况现在求素短语。素短语要求至少包含一个终结符且自身不再包含更小的素短语。先拿所有短语来看a包含终结符 a它里面没有再小的短语所以是素短语。b两个包含终结符 b自身没有更小素短语所以都是素短语。bb包含终结符但它里面含有素短语b里层那个 b所以bb不是素短语。c是素短语。e是素短语。abbcBe它不是素短语因为它里面包含 a、b、b、c 等多个素短语。所以素短语是a、b、b、c、e。最左素短语就是最左边的那个素短语从左往右找是a。发现没有在这个例子里句柄和最左素短语刚好是同一个都是a。这并不是巧合而是因为这里的句柄a本身就包含终结符。后面我会专门讲两者什么时候相等、什么时候不等。3.5 可复用的五步流程做完这道题我把操作流程抽象出来你以后遇到类似题目直接照做第一步写出推导过程确认给出的串确实是句型。如果不是直接结束后面都谈不上。第二步画出语法树。这一步不能省也别在脑子里空想画在纸上最保险。第三步找出所有非叶子节点分别写下它们各自子树的叶子序列。左边写节点名右边写叶子串列成一张表。第四步根据“叶子序列是否为某个非叶子节点的子树叶子串”筛出短语再根据“是否由某非终结符一步推出”筛出直接短语然后从直接短语里从左往右取第一个得到句柄。第五步从短语里筛出“至少含一个终结符且不含更小素短语”的得到素短语再取最左边的得到最左素短语。这套流程用顺了一道题三分钟就能做完。我自己做题和复习带人都是这个套路还没失手过。4. 特例与易错点句柄和素短语的经典陷阱4.1 句柄一定是直接短语直接短语不一定是句柄这是我觉得最需要敲黑板的地方。句柄是“最左直接短语”所以它首先得是直接短语。但一个句型里往往有多个直接短语只有最左边那个才配叫句柄。比如前面例子里的直接短语有 a、b、b、c、e其中 b 出现了两次c 和 e 也都是直接短语但句柄只有一个 a。做题时如果你只找直接短语不排序或者排序排错就很容易答错。还有更隐蔽的情况某个直接短语恰好是另一个直接短语的前缀。比如直接短语第一个是i第二个是i i这种这时最左直接短语肯定是i。这时候有人会犹豫因为后面的直接短语更长包含前面的是不是应该合并不是。句柄就是最左那个直接短语本身不合并、不取最长。4.2 素短语至少含一个终结符但不是说不能含多个素短语的定义里有“至少包含一个终结符”这个“至少”很关键。一个素短语可以只含一个终结符也可以含多个终结符还可以同时含非终结符和终结符的混合串。看这个例子文法E → E T | TT → T * F | FF → (E) | i句型E T * F里短语T * F包含终结符而且它内部有没有更小的素短语它内部的F是短语但 F 不含终结符F 是非终结符不是终结符所以 F 不能被算作素短语。因此T * F内部没有更小的素短语那T * F本身就是一个素短语尽管它的叶子是“T、、F”混合了非终结符。所以判断素短语时不要想着“素”就是“纯终结符”“素”的意思是“不可再分解的、含终结符的块”。它完全可以是T * F这种样子。4.3 最左素短语和句柄什么时候相等这个问题考试和面试都爱问。我直接给结论如果句柄本身至少包含一个终结符并且这个句柄内部没有任何更小的素短语那么句柄就是最左素短语二者相等。如果句柄完全不含终结符比如某个非终结符直接推出另一个非终结符那它就不是素短语此时最左素短语往往是句柄之后、在扫描过程中第一个遇到的含终结符可归约串。不过在实际语法分析过程中尤其是 LL 分析和 LR 分析里我们更关心句柄而在算符优先分析里因为文法通常不含形如A → B这种“单非终结符到单非终结符”的产生式所以句柄基本都含终结符这时候句柄和最左素短语常常是同一个东西。4.4 算符优先分析中为什么会盯上最左素短语算符优先分析是一种自底向上的语法分析方法它的特点是只看终结符之间的优先关系不关心非终结符的名字。这就导致它没法像 LR 分析那样精确知道当前栈顶的“句柄”是什么它只能根据终结符的优先级关系找到“最左素短语”然后把这一整块归约掉。这就是为什么素短语和最左素短语在算符优先分析里特别重要。你可以把最左素短语理解为“算符优先分析语境下的句柄”。它没有句柄那么强但足够指导规约动作。我之前复习的时候总是搞混 LR 和算符优先的归约目标后来用一个办法记住LR 归约看句柄算符优先归约看最左素短语。一个是精确制导一个是雷达粗扫。这样想就顺了。4.5 活前缀和可归约串的关联学到 LR 分析时你还会遇到“活前缀”这个概念。活前缀是规范句型的一个前缀它不包含句柄之后的任何符号。简单说在从左到右扫描输入串时已经读入的那部分如果还没超出句柄的范围就属于活前缀。这个点和今天的话题关系很深。因为 LR 分析表本质上就是用来识别“当前栈里的串是不是某个句型的一个活前缀”。当栈顶形成完整句柄时就执行归约。所以你看句柄不是孤立的它是整条自底向上分析主线的核心。素短语则是在更粗糙的算符优先分析里的替代品。5. 常见问题排查与避坑清单5.1 常见问题速查表我把这些年学生问得最多的问题整理成一张表你可以对着自查问题原因解决办法把不是短语的子串当成了短语没画语法树靠肉眼从原串里截取强制自己先画树再找子树叶子直接短语漏掉了单个终结符忘了终结符也可以是某非终结符的一步产物检查语法树中每个内部节点的孩子是否全为叶子句柄找错忘了“最左”两个字或者没把所有直接短语都找全先列举所有直接短语再从左到右选第一个素短语找错没排除“包含更小素短语”的情况从最小短语开始筛逐层检查分不清句柄和最左素短语概念混在一起没有先分类先独立求出各自结果再对比不要互相推导句型里含非终结符不知道还能不能有短语可以短语定义没要求必须是终结符串照常画树非终结符是叶子也可以作为边界5.2 我自己踩过的坑别把短语当“任何子串”我当年学这一节时犯过一个很蠢的错。题目给了一个句型abbcBe我脑子里浮现出“短语就是句型里的任意可理解片段”然后兴高采烈地把ab、bc、bb c都写了上去结果被老师画了一堆叉。后来我才意识到短语这个概念有一个隐含前提它必须对应某个非终结符的“完整子树叶子序列”。也就是说你不能从中间切开必须从某个非叶子节点往下把这个节点覆盖到的所有叶子全部取走。少一片叶子都不行。这个坑特别容易踩因为你平时看字符串看习惯了总觉得“看着像一块”就行。实际上语法树说了算树上是完整子树才是短语树上是残片就不是。我还记得当年有个同学问“那为什么abb不是短语它看起来不是挺完整的吗”答案是没有任何一个非终结符的子树叶子序列恰好是abb。S 的子树是abbcBeA 的子树是bba 和 bb 拼起来虽然也是abb但中间没有一个节点正好覆盖 a 和 A所以它不是短语。5.3 面试和考试中怎么答才有区分度如果你是在准备面试面试官问到这些概念千万别只背定义。我建议你按这个思路答先一句话定位这些概念是语法分析中用来确定“规约单位”的。然后快速区分句柄和素短语句柄是最左直接短语服务于 LR 类自底向上分析最左素短语是算符优先分析中真正执行规约的串。然后主动举一个例子不需要多复杂能说明问题就行。比如直接说“考虑文法 S → aAcBe句型 abbcBe 的句柄是 a最左素短语也是 a但在某些文法里二者不同因为它们对终结符的要求不一样。”这样回答既展示了你对定义的掌握又体现了你理解这些概念在什么场景下用、为什么用面试官印象会好很多。另外要提醒一点如果你被问到“句柄在 LR 分析里怎么找”不要说“就是最左直接短语”就完了。你可以补一句“LR 分析器通过状态栈和向前看符号来识别当前栈顶是否形成了句柄形成后就按相应产生式归约。”这能体现出你不仅知道定义还知道工程实现。最后再分享一个我的心得体会我带过的学生里凡是能把这几组概念用自己的话讲清楚、并且能随手举出例子的人基本上语法分析部分的题目都不会失分。反过来那些只背定义、不画树的人十个里有八个会在“直接短语”“句柄”上丢分。我个人实操下来最有效的训练方法就是找五道关于句型短语的练习题每道都严格按照“画树 → 列叶子 → 分类 → 取最左”的流程走做完了再去对答案。一开始可能会慢一道题要十几分钟但做完三道之后基本就能在五分钟内搞定一道。如果你手里暂时没有合适的题目就拿本文的两个例子反复练一个是S → aAcBe的那个一个是算术表达式文法E → E T | T、T → T * F | F、F → (E) | i的那个。你可以试着求一下句型E T * F的短语和直接短语再求一下i i * i的素短语做完你就会发现这些概念真的不难只是需要多动手、多画树。
