编译原理学习笔记02文法与语言为什么说“形式化”是一切的起点如果你正在啃编译原理或者刚被词法分析实验折磨过那么“文法”和“语言”这两个词你一定不陌生。很多同学在这块就开始犯迷糊文法不就是一堆产生式嘛语言不就是字符串集合嘛这有什么好学的但恰恰是这两章决定了你后面看语法分析、LL(1)、LR(1)的时候是“懂”还是“背”。我当年学到这里时也没太当回事结果到预测分析表构建那节课直接听天书回头补了三天文法基础才缓过来。这篇笔记就把“文法和语言”这块掰开揉碎讲清楚结合我教学和做实验过程中的一些体会希望能帮你把地基打牢。这篇文章适合正在学编译原理的本科生、准备考研复试的计算机学生以及想自底向上把编译原理吃透的入门开发者。不需要你有很深的数学基础但要有耐心因为形式化这个东西就是慢工出细活。1. 先搞懂一个关键问题为什么语言需要“文法”来描述大家学习计算机这么久肯定接触过C语言、Java、Python这些高级语言。你有没有想过一个问题同样是字母和符号组成的字符序列为什么int a 1;是一句合法的C语言代码而int int 1;在某些语境下就报错为什么你写的代码能被编译器识别成“正确的程序”这里面的底层机制就是文法。1.1 自然语言与形式语言语感的“直觉” vs 规则的“精确”我们先来做个类比。你学中文、学英语靠的是语感——听多了、读多了自然就能判断“我今天吃了饭”是通顺的“饭吃今天了我”不通顺。这种判断是概率性的是模糊的没人能给出100%精确的规则集因为自然语言本身就在不断演化例外太多。但计算机不一样。编译器看不懂“语感”它必须有一套精确的、无歧义的规则来判定哪些字符序列是合法的程序、哪些不是。这套精确规则就是形式文法。形式文法与其描述出来的语言合称形式语言它和自然语言最大的区别就是没有例外规则说了算。1.2 为什么不能靠“关键字列表”来识别语言可能有人会问程序语言结构不都是规定的吗我直接枚举所有合法形式不就行了比如C语言的for循环是for(;;)我拿模板去匹配不就可以了这种思路在简单场景下勉强可行但程序语言是无穷的。变量名可以无限取表达式可以无限嵌套例如下面的代码a b c * d - (e f) / g;你能枚举出所有可能的赋值表达式吗不可能。你需要的是用有限的规则去描述无限的合法句子集合。这正是文法的核心价值用有限的产生式规则递归地定义出无穷多个合法的符号串。递归赋予了文法“以有限描述无限”的能力这是语言能被机械识别和生成的基础。从本质上说编译原理中的所有内容——从词法到语法到语义——都是在“形式语言”这个框架下展开的。文法就是给“语言的集合”画的一条边界线属于这条线内的就是合法程序线外的就不是。2. 文法的五大基本构件终结符、非终结符、产生式、开始符号、推导正式的定义我不绕弯子文法G是一个四元组G (V_N, V_T, P, S)其中V_N是非终结符集合V_T是终结符集合P是产生式集合S是开始符号。加上产生式推导的过程我们展开说。2.1 终结符与非终结符一个是原子一个是变量终结符Terminal是语言中不可再分割的最小单位。在C语言里关键字int、运算符、分号;、标识符abc、数字常量123这些都是终结符。它们是词法分析器Lexer输出的“单词”类型也是语法树叶子节点上挂的内容。非终结符Nonterminal则是语法成分的“占位符”或者“变量”它代表一类语法结构。比如“表达式”、“赋值语句”、“循环语句”这些都不是具体的字符而是抽象的语法范畴。非终结符必须由产生式进一步展开直到全部展开为终结符为止。初学者最容易混淆的就是终结符是“形式语言”这个集合里的字母非终结符只是推导过程的中间标记。一个符号串如果还含有非终结符那它就不是“语言中的句子”只是“句型”。2.2 产生式文法最核心的灵魂产生式又叫重写规则形如α - β读作“α定义为β”。注意这里α和β都是符号串可以是终结符和非终结符的混合。产生式的本质是“替换”在任何出现α的地方都可以用β来替换。举一个最简单的算术表达式文法例子E - E T | E - T | T T - T * F | T / F | F F - (E) | id这里E代表表达式ExpressionT代表项TermF代表因子Factorid代表任意标识符或数字。竖线|是或的意思相当于多条产生式的简写。这个文法的奥妙在于它用优先级层次E - T - F巧妙地规定了、*、括号在运算中的优先级和结合性。为什么E T而不是E E因为如果写成E - E E会产生二义性1 2 * 3可以被理解为(12)*3也可以理解为1(2*3)编译器就不知道听谁的了。这个“分层降级”的技巧几乎贯穿所有高级语言的文法定义中后面我会再提。2.3 推导与规约一个从抽象到具体一个从具体到抽象给定文法G如果符号串v中的某个非终结符用某条产生式的右部替换后得到w就记作v w读作“v直接推导出w”。从开始符号S出发连续进行多次替换最终得到一个只含终结符的串这个过程就叫做推导Derivation。反之从终结符串出发不断用产生式左部替换右部最终归约到开始符号S这个过程叫做规约Reduction。推导是自顶向下的规约是自底向上的。这两条路线分别对应编译器的两种核心分析方法LL分析自顶向下和LR分析自底向上。很多同学学到语法分析时觉得“推导好懂规约绕”但只要你理解了“推导是规约的逆过程”再学LR分析时会轻松很多。后面做自底向上语法分析实验的时候你会反复体会到这种逆过程的思维。2.4 句型、句子和语言三者的净化过程从开始符号S出发每经过一步推导得到的中间串可能含非终结符叫句型Sentential Form如果这个句型全部由终结符组成就叫句子Sentence。所有句子构成的集合就是该文法定义的语言L(G)。所以你看从S到句子的过程就像是一个“净化”过程开始时全是抽象的非终结符不断替换最终变成纯终结符组成的句子。反过来说判断一个字符串是否为某个文法的句子就是看能否从S出发推出该字符串或能否将其规约到S。实际编译器做词法分析时实际上就是在判断“字符流是否是语言的句子”的局部问题语法分析则是在判断“Token串是不是语法范畴定义的句子”。3. 文法的分类乔姆斯基体系和各类型的特点形式文法理论中乔姆斯基Chomsky体系按产生式限制的严格程度把文法分成了4类。这个分类在考试中几乎必考面试也常问一定要做到能默写、能举例子。3.1 0型文法短语结构文法与1型文法上下文有关文法0型文法对产生式没有任何限制α - β只要α至少含一个非终结符即可。它定义的语言类也叫递归可枚举语言对应图灵机。1型文法限制产生式α - β必须满足|α| |β|也就是右部不能比左部短且替换时需要考虑上下文环境。所以名字叫“上下文有关”β是否能替换α取决于α周围是什么字符。1型文法的典型例子aA - ab意思是只有当前面是a时A才能替换成b。这种文法在描述自然语言时很有用但实际程序设计语言几乎不用因为它的分析复杂度太高。3.2 2型文法上下文无关文法高级语言的骨架2型文法要求产生式左部必须是一个单一的非终结符即A - β。因为左部只有一个非终结符替换它时不依赖周围环境所以称为“上下文无关”。这个性质太好了——它允许我们用递归下降或者自底向上移进规约等高效算法进行语法分析复杂度是多项式的。绝大多数程序设计语言的核心语法结构都用上下文无关文法描述。比如前面那个算术表达式文法就是一个标准的2型文法。到了词法层面标识符、数字等token也常用正则文法描述但语法层面基本就是上下文无关文法的天下。注意一个常见误区2型文法不是“与上下文无关的语言”而是“规则本身不需要上下文”。语言本身可能有上下文相关的约束比如C语言中“变量必须先声明后使用”这属于语义阶段符号表检查的范畴不完全由文法来描述。很多教材会提及“C语言不是完全的上下文无关语言”也是这个道理。3.3 3型文法正规文法与正则表达式的关系3型文法又叫正规文法分为右线性和左线性两种。右线性文法形式为A - aB或A - a即产生式右部最多一个非终结符且在最右侧。3型文法定义的语言正好是正则语言与正则表达式、有限自动机等价。这就是为什么词法分析可以用正则表达式实现因为词法规则标识符、关键字、无符号数基本都是3型文法描述的。我也在实验里让学生用Flex去写词法规则本质上就是在用一种“正则文法”的变体。四种文法的包含关系3型 ⊂ 2型 ⊂ 1型 ⊂ 0型每种文法的识别能力对应不同的自动机。一句话记忆0图灵机、1线性有界自动机、2下推自动机、3有限自动机。这个对应关系在考试中经常考简答题。4. 二义性文法的“歧义”问题以及为什么要消除它二义性Ambiguity是文法理论中一个十分重要的考点也是实际操作中必须避开的坑。如果一个文法存在某个句子可以对应两棵不同的语法树或者说两个不同的最左推导就称该文法是二义性的。4.1 为什么会产生二义性两个经典例子第一个经典例子就是E - E E | E * E | id。对于id id * id你可以先展开左边的E为E * E也可以先展开为E E结果就是同一个句子能推导出两种不同结构的语法树。在编译器里这种歧义直接导致无法确定和*谁先算、如何结合。这显然是不能接受的。第二个经典例子是if语句。假如文法定义如下S - if E then S | if E then S else S | other那么对if E then if E then S else Selse既可以匹配内层if也可以匹配外层if形成经典的“悬空elsedangling else”问题。C语言中约定else匹配最近的未匹配if这就是一种消除二义性的策略。4.2 消除二义性改写文法 vs 附加规则消除二义性主要有两条路。一条是改写文法让每个产生式都天然没有歧义比如用优先级分层的表达式文法替代E - E E | E * E。这种方法的好处是不改变语法树的结构含义坏处是文法可能变复杂。另一条是附加外部规则比如规定优先级、结合性或者像C语言那样规定else的匹配规则。这种方法不改变文法而是在分析器中加入额外的逻辑来解决冲突。实际编译器往往两种方法混用文法尽量清晰再配合优先级声明和特殊规则。我在实际做语法分析实验时比如用Yacc/Bison定义表达式时一般就直接用%left和%right来说明运算符结合性比费心改写文法快得多。但考试和面试时经常要求你能手写消除二义性的文法改写方案所以两层功夫都要练。这里说一下我做教学时候的血泪教训很多学生一遇到二义性文法就问“是不是这个语言本身有问题”其实文法二义性与语言本身的二义性不是一个概念。一个语言可能存在二义性文法也可以存在无二义性文法。只有当一个语言不论怎么定义文法都有二义性时才叫做“固有二义性语言”。判断一个语言是否固有二义性是不可判定的这是停机问题的推论。考试中让你判断“某文法是否有二义性”通常只需要找一个句子能画出两棵不同的语法树即可。4.3 语法树与二义性的直觉理解语法树Parse Tree是推导过程的可视化表示根节点是开始符号叶子节点是终结符内部节点是非终结符。如果有两个不同的推导对应不同的语法树那就是二义性。这里有个小细节如果两种推导只是调整了同层非终结符的展开顺序但语法树形态相同则不算二义性。比如最左推导和最右推导可以得到同一棵树这种情况是正常的。判定二义性的标准永远落在“是否存在两棵不同的语法树”上。5. 从文法到语言的关系这部分的习题与面试题思路学完基本概念接下来得会做题、会用。考试和面试常出几类题我帮你梳理一下解题思路。5.1 给定文法求该文法描述的语言这类题通常给你一组产生式让你写出它定义的语言集合。方法是从S开始把所有可能的推导都列举出来找规律。举一个非常经典的例子S - aS | ε这里ε表示空串。反复套用S - aS最后再套用S - ε你会得到ε, a, aa, aaa, ...所以语言是L { a^n | n 0 }——注意n可以是0因为可以直接用S - ε推导出空串。再复杂一点的例子S - 0S1 | ε这个文法定义的语言是{ 0^n 1^n | n 0 }。它的巧妙之处在于每套用一次S - 0S1就在左边多一个0、右边多一个1从而保证0和1数量相等且0在左、1在右。这类题目要多做题找感觉重点是掌握“利用递归产生成对符号”的套路。如果你发现一个文法能同时控制多个位置的符号数量那么这个字符串就有“上下文有关”的味道了只不过这里是用上下文无关文法“递归生成”实现的。5.2 给定语言设计一个文法反向题更考验构造能力。比如让你设计文法描述L { a^n b^m | n 1, m 1 }你可以拆成两步先要一个或多个a再要一个或多个b。可以构造S - AB A - aA | a B - bB | b再如语言L { a^n b^n | n 0 }这就要用“成对生成”的思路S - aSb | ε总结一下设计文法的常用招数外层拆分多个部分的连接就用多个非终结符拼接、递归生成同形串用于成对或重复的结构、终结符保证数量如A - aA | a表示至少一个a。多练几道题之后你会发现文法设计其实很像做拼图规则有限但组合方式无穷。5.3 近些年的考研与面试趋势现在很多高校的编译原理考试不仅考计算还考理解。比如“请解释为什么程序设计语言用上下文无关文法而不是上下文有关文法来描述”“什么是二义性日常开发中如何避免”这类问题背后考察的是对编译全流程的理解。因为编译器的语法分析器倾向于基于上下文无关文法构建若文法过于复杂如上下文有关语法分析效率会很差很难做到线性时间。这个取舍思维在工程里特别常见不是把所有信息都塞进文法而是把语义规则放到后续阶段处理。实际公司在招聘时如果问编译原理也常围绕着“你如何设计一个DSL领域特定语言的词法和语法”来展开。这时候文法和语言的基本功就决定了你能否设计出“既好用又不会让解析器炸掉”的语法。我自己用Yacc/Bison写小工具时就经常先把语法用文法草稿写出来再转换成工具代码这样可以提前发现很多二义性和冲突问题省去大量调错时间。6. 学习文法时的常见误区与避坑笔记作为过来人我想把踩过的一些坑摆在明面上希望大家能少走弯路。6.1 误区一把“终结符”和“关键字”划等号终结符不只是关键字还包括运算符、分隔符、标识符、数字常量等。在语法分析层面终结符通常就是token类型的集合。更抽象地说终结符就是该语言字母表上的符号。哪怕你自创一门语言定义foo为一个特殊符号那它也可以是终结符。对应地词法分析器的任务就是从字符流中识别这些“终结符实例”而语法分析器不再关心“字符本身”只关心token类型。所以理解“终结符属于语法层、字符属于词法层”是打通两章的要点。6.2 误区二把“推导”和“展开”混为一谈推导是“根据产生式将某个非终结符替换为另一串符号”而很多人理解成“把顶层符号拆开”就够了忽略了推导顺序的概念。最左推导每次替换最左边的非终结符和最右推导每次替换最右边不只是做题术语它们分别和自顶向下分析与自底向上分析相关。比如LR分析器实质上是在模拟“最右推导的逆过程”理解这一点之后你就会发现shift-reduce冲突、reduce-reduce冲突这些概念不再抽象。6.3 做实验的碎碎念从文法到代码如果你正在做词法分析或语法分析实验我的建议是先写好文法再写代码。很多同学一上来就用if-else硬写状态机写着写着就晕了。但如果你先把token的正规文法列出来再将状态转换图画出来代码的逻辑会清晰很多。语法分析实验更是如此先用纸笔把表达式文法写清楚带优先级分层的那种再用递归下降程序一步一步翻译成代码。编译原理的实验核心是“从形式化定义到程序实现的映射”而不是比拼谁的状态机写得漂亮。6.4 教材和配套资料怎么用经典的教材比如陈火旺的《编译原理》那本蓝色封面对文法和语言的讲解非常系统。但教材偏理论有些地方比较晦涩。建议配合网课比如哈工大、国防科大的编译原理课程一起看老师会画语法树、演示推导过程直观很多。另外强烈推荐用一个小工具辅助理解可以用Python写一个简单的文法推导生成器或者直接在Bison/Yacc里写一个小计算器试试亲手改一改文法看它报什么冲突会大大加深记忆。7. 这一章和后续章节的衔接你的编译器学习地图文法与语言的部分就像是编译原理的“底层操作系统”后面所有章节都建立在这套形式化体系上。简单串一下词法分析器是有限自动机正规文法语法分析器是下推自动机上下文无关文法语义分析基于语法树和属性文法中间代码生成也依赖语法树结构。你越早把文法和语言搞懂后面学起来就越通透。举个例子很多同学学到LL(1)文法和LR(1)文法时又要回头翻教材看FIRST集和FOLLOW集的定义。但实际上这两个集合的概念就来自“文法推导产生式右部能推出的终结符集合”本质上还是在跟终结符、非终结符、推导打交道。所以这一步基础扎实后面不过是通过算法自动化地判断“某文法是否是某类可解析的文法对象”。我个人非常喜欢一句话编译原理是一门“精确描述与机械实现”的学科。文法给了你精确描述的手段而编译器就是机械实现的产物。理解这句话学编译原理的整个心态就不一样了——你不是在背算法你是在理解一门语言“如何从文本变成机器可执行的指令”。这一篇就写到这里。下一篇我会继续整理词法分析和正规文法的实战经验包括如何快速写出一个支持多种token的扫描器以及我实测踩过的一些坑。如果你正在啃编译原理欢迎在评论区分享你遇到的看不懂的知识点我来帮你拆。