★ FEATURED ARTICLE 1. 项目概述语言的定义是整个编译原理的起点也是最容易被初学者一带而过的部分。很多人学编译原理一上来就啃词法分析、语法分析结果看到自动机、文法推导就懵了根子就在于没有真正理解“语言”到底是个什么东西。哈工大这套课程把语言的定义放在最前面讲不是没有道理的——它是后续所有章节的地基。我最早接触编译原理的时候也犯过同样的毛病。当时觉得“语言不就是一段字符串吗有什么好定义的”结果学到上下文无关文法的时候才发现自己对“文法产生语言”这个过程根本没建立直觉。后来回过头来重新啃语言的定义才把整条线理顺了。简单说语言就是某个字母表上所有符合特定规则的字符串构成的集合而编译器的任务就是判断一段输入字符串是否属于这个集合并把它翻译成目标代码。这篇文章会把语言的定义拆开揉碎了讲清楚覆盖字母表与字符串、文法与推导、乔姆斯基文法体系这些核心概念同时结合哈工大课程的讲解思路说说为什么这些概念是编译器设计的理论根基。无论你是正在准备期末考试的学生还是想系统补编译原理基础的开发者都能从中获得可以直接消化的干货。文章里还会穿插一些我实际学习和应用这些概念时的经验和踩坑记录帮助你把抽象的理论跟真实的编译器设计联系起来。2. 语言定义的三个基本构件2.1 字母表与字符串语言的“字母”和“单词”形式语言理论里一切讨论都从字母表开始。字母表Alphabet是一个非空有穷集合通常记作 Σ集合里的元素称为符号Symbol。这个定义听起来简单但有个容易被忽略的关键点字母表必须是有穷的。为什么因为如果字母表是无穷的我们根本无法用有限的手段去描述它编译器也就无从实现了。比如 C 语言源代码的字母表大约就是 ASCII 字符集加上扩展字符撑死了也就是几百个符号这就是它的 Σ。字符串String是字母表上符号的有穷序列。注意“有穷”两个字因为编译器处理的是实际存在的程序文件文件长度必然是有限的。字符串的长度记作 |ω|也就是它包含的符号个数。还有一个特殊字符串叫空串记作 ε长度为 0。很多初学者搞不懂空串的意义其实它在文法推导中特别重要——它表示“什么都不产生”。比如某些产生式右部可以为 ε指这个非终结符可以推导出空串。这里我补充一个自己踩过的坑处理语言定义时一定要区分“空串 ε”和“空集 ∅”。ε 是字符串长度为 0它是集合中的一个元素而 ∅ 是集合里面什么都没有。比如 {ε} 这个语言包含一个长度为 0 的字符串而 ∅ 这个语言不包含任何字符串。两者完全不同但在考试和实际讨论中特别容易被混淆。字符串之间的运算主要有连接Concatenation和幂运算。ω 和 ν 的连接记作 ων就是把 ν 接在 ω 后面。这个操作虽然简单但它是后面讨论文法推导的基础——推导本质上就是不断做字符串的替换和连接。字符串的幂运算 ωⁿ 表示 n 个 ω 连接在一起特殊地定义 ω⁰ ε。这几个概念看起来不起眼但如果理解不透后面看推导过程就会觉得像看天书。2.2 语言的集合化定义为什么说语言是“集合”有了字符串的概念语言就可以定义了某个字母表 Σ 上的语言就是 Σ 上所有字符串组成的集合的子集。这句话有点绕拆开说就是先把字母表上所有可能的字符串都收集起来记作 Σ*这个集合你们以后会大量见到它被称为 Σ 的闭包Kleene Star包括所有长度的字符串包括空串然后语言 L 就是 Σ* 的任意一个子集。用数学符号表达就是 L⊆Σ*。比如字母表 Σ{a,b}那么 Σ* 里包含 ε、a、b、aa、ab、ba、bb、aaa……等等无数个字符串。而一个语言可以是 {a, b, aa, ab, ba, bb}也可以是一个判定条件定义的子集比如“所有 a 和 b 个数相等的字符串”。关键点在于语言不一定是有限的它可以是无限集。这个认知很反直觉但又是编译原理里绕不开的事实。例如 L{aⁿbⁿ | n≥0} 就是一个无限语言包含 ε、ab、aabb、aaabbb……特征是 a 的个数和 b 的个数必须相等。理解了“语言是集合”再看编译器的角色就清晰了编译器本质上就是一个判定器输入一个字符串源代码判断它是否属于某种语言该语言的合法程序集合。同时编译器还要把它翻译成等价的目标代码。这个判断过程的基础就是文法而文法本身也是一种描述语言的方式。注意文法描述的是语言的定义方式而不是语言的判定算法。同一个语言可以被不同的文法描述也可以由不同类型的自动机来识别这两个维度在编译原理中是要分开思考的。2.3 文法语言生成的“配方”文法是生成语言的核心工具。形式化地文法 G 是一个四元组 G(V, T, P, S)。其中 V 是非终结符变量的集合T 是终结符的集合V 和 T 不相交它们的并集就是推导中出现的所有符号P 是产生式的集合每个产生式形如 α→β表示把 α 替换成 βS 是开始符号属于 V是推导的起点。用做饭来类比终结符就像最终的食材成品比如一道菜的摆盘非终结符就像菜谱里的中间状态比如“切好的土豆丝”“调好的酱汁”产生式就是操作步骤“把土豆切成丝”开始符号就是“做一道鱼香肉丝”这个总目标。你要得到最终的菜就从总目标出发按步骤一步步操作直到所有中间状态都变成成品。文法生成语言的过程称为推导Derivation。推导从开始符号 S 出发反复选择产生式把某个非终结符替换成对应的右部直到结果中不再含有任何非终结符得到的字符串就是该文法生成的一个句子。所有能由该文法推导出来的终结符串的集合就是文法 G 定义的语言记作 L(G)。推导过程中每一步的替换都是独立的——你可以选择任意一个非终结符进行替换也可以选择该非终结符的任意一个产生式。这就引出了推导的两种典型策略最左推导Always replace the leftmost nonterminal和最右推导Always replace the rightmost nonterminal。在后面的语法分析章节这两种策略分别对应自顶向下分析和自底向上分析所以现在打好基础非常关键。3. 文法的分类与形式语法体系3.1 形式语法体系从 0 型到 3 型的层级关系形式语法分类体系对产生式加了不同的限制条件从宽到严分成 4 型文法。这里先直接给出完整分类表再逐个拆解。文法类型产生式限制对应自动机典型应用0型文法短语文法无限制α→βα含非终结符图灵机通用计算模型递归可枚举语言1型文法上下文有关文法α长度≤β长度A替换时依赖上下文线性有界自动机自然语言某些结构理论层面2型文法上下文无关文法A→βA为非终结符下推自动机程序设计语言语法定义最常用3型文法正规文法A→aB 或 A→a即右线性形式有穷自动机词法规则、正则表达式、模式匹配这个分类体系是层层包含的每种文法都是前一型的子集。实际上这 4 层构成了一个真正的层级每一层对产生式的限制逐级加强表达能力逐级减弱。编译器设计中最核心的是 2 型和 3 型词法分析器用 3 型文法对应正则表达式语法分析器用 2 型文法。至于 0 型和 1 型更多是计算理论讨论的范畴编译器实践中基本不碰。3.2 上下文无关文法程序语言定义的基石上下文无关文法Context-Free GrammarCFG是程序设计语言定义的标准工具。它的产生式左部只允许有一个非终结符形如 A→β。这个限制的含义是替换 A 的时候不需要考虑它在什么上下文中出现A 在任意位置都可以被替换成 β。正是这种“上下文无关”的特性让程序语言的语法分析成为可能——我们可以独立地分析语法结构的每个组成部分。举个例子一个简单算术表达式的文法可以写为E → E E E → E * E E → (E) E → id这个文法能推导出 id、idid、id*(idid) 这样的表达式。它的特点是有递归性——E 的定义里又出现了 E 自己。递归是上下文无关文法最重要的性质它让有限个产生式能描述无限种可能的句子。没有递归文法就只能描述有限的语言就失去了表达程序设计语言的价值。CFG 的应用不限于编译原理。比如 JSON 的语法、HTML 的标签嵌套结构、Markdown 的段落结构本质上都可以用 CFG 来描述。理解了 CFG 的递归思想你看很多结构化文本的解析器源码时就会豁然开朗。上下文有关文法在编译器实践中几乎用不到但我还是想提醒一句不要因为用不上就完全忽略它的存在。理解“上下文有关”意味着什么比如某些语言结构如“变量先声明后使用”其实是上下文有关的性质能让你意识到编译器中符号表和类型检查的存在价值——这些功能恰好在处理 CFG 无法表达、需要“上下文有关”信息才能判定的语言性质。这一点也是哈工大课程中反复强调的“语法分析只解决结构问题语义分析解决意义问题”这个观点的理论基础。3.3 正规文法与正则表达式的等价性正规文法Regular Grammar是限制最严格的文法类型产生式形如 A→aB 或 A→a右线性也可以写成 A→Ba 或 A→a左线性。它描述的语言正好是正则语言类与正则表达式、有穷自动机三方等价。这个等价关系是词法分析的理论基础。编译器词法分析器的工作是把源代码拆成一个个词素Token比如关键字、标识符、数字常量、运算符等。这些词素的结构通常比较规则用正则表达式描述起来非常自然。例如C 语言中的标识符可以描述为“字母或下划线开头后跟字母、数字或下划线的零个或多个”。这个规则用正则表达式写就是[A-Za-z_][A-Za-z0-9_]*。正规文法表达能力的局限性也很重要——它无法描述“匹配的括号结构”这类需要嵌套计数的语言。比如 L{aⁿbⁿ | n≥0} 就不是正则语言无法用有限个状态来识别。这正是程序语言需要两层结构词法和语法的原因词法层面的结构相对简单用正则就能搞定但语法层面的嵌套结构如 if 语句里嵌套 if 语句、表达式里嵌套括号必须用 CFG 才能描述。有穷自动机与正规文法的等价证明是形式语言理论中很优美也很重要的一个结论。它的证明思路是通过构造的方式给定一个正规文法可以构造一个有穷自动机来识别它生成的语言反过来给定一个有穷自动机也可以构造出正规文法。这个等价性给了我们极大的设计自由度——需要描述语言结构时用文法需要实现识别算法时用自动机两者之间可以自由转换。4. 推导、语法树与二义性4.1 推导过程与语法分析树的构造推导是文法的执行过程。从开始符号出发每一步用一个产生式的右部替换掉当前句型中的一个非终结符直到得到只含终结符的句子。这个过程中产生的一个中间结构叫句型Sentential Form含有非终结符。如果句型只含终结符就叫句子Sentence。举一个具体的例子。考虑文法S → aB | bA A → a | aS | bAA B → b | bS | aBB要对输入串aabb进行推导可以从 S 出发逐步应用产生式S aB 用 S→aB aaBB 用 B→aBB aabB 用 B→b aabb 用 B→b这个过程得到的aabb就是文法生成的句子。推导过程可以直观地用推导树语法分析树Parse Tree表示根节点是开始符号每个内部节点是一个非终结符它的子节点从左到右对应它使用的那条产生式的右部符号叶子节点从左到右就是最终生成的句子。语法树对编译器设计非常重要因为它在结构上捕捉了“输入串为什么属于这个语言”的完整证据。后面的语义分析、中间代码生成都需要基于语法树来工作。比如一个表达式的求值顺序、运算符优先级在语法树的结构中已经暗含了树的高度、左递归或右递归的选择甚至会影响到解释器或编译器的栈深度。我在学习推导时有一个重要的经验先画树再看推导序列会比直接凭空推导更直观。因为树形结构让你一眼看到哪一步替换了哪个节点推导序列只是树的深度优先遍历罢了。4.2 最左推导与最右推导以及规范推导推导的策略不是唯一的。每步可以选择任意一个非终结符来替换。如果每次都选择最左边的非终结符进行替换就是最左推导如果每次都选择最右边的一个就是最右推导。注意这里说的“最左/最右”在树形结构里不一定是最左/最右叶子的位置而是先序/后序访问的顺序问题。但在上下文无关文法中两种推导得到的句子集合是相同的区别在于推导的结构文法分析树的形态。最右推导在语法分析中有一个特殊地位任何最右推导都可以反过来成为自底向上分析如 LR 分析的基础。自底向上分析是从输入串出发不断归约把产生式右部替换回左部最终归约为开始符号。这个反向过程如果用最右推导的逆过程来思考会使问题简洁许多。举个最左推导的例子。还是上面的文法推导aabbS aB 最左非终结符 S 替换 aaBB 最左非终结符 B 替换 aabB 最左非终结符 B 替换 aabb 最左非终结符 B 替换整个过程里每个句型中的最左非终结符都被优先替换了。如果选择其它非终结符替换虽然最终句子可能相同但推导步骤的次序不同对应的语法树形态可能相同也可能不同。4.3 二义性一个结构对应多棵语法树二义性是上下文无关文法中一个非常重要又非常微妙的问题。如果一个文法能为同一个句子生成两棵不同的语法分析树那么这个文法是二义性的Ambiguous。二义性意味着语法分析器无法确定输入串的“正确”结构这会直接影响后续语义分析。一个经典的二义性例子是E → E E | E * E | (E) | id这个文法能推导idid*id但可以有两种不同的语法树一种是先算加法即(idid)*id的结构另一种是先算乘法即id(id*id)的结构。显然这两种结构计算的优先级不同对于表达式求值的结果会产生歧义。编译器如果允许这种歧义同一个程序在不同的编译器下可能行为不同这是绝对不可接受的。解决二义性的常见方法有重写文法通过引入新的非终结符来消除二义性。比如把表达式文法重写成包含术语Term和因子Factor的层次结构强制先算乘除后算加减并规定左结合顺序。在语法分析时引入优先级和结合性规则让分析器根据规则选择其中一种最合理分析树。很多工具如 Yacc/Bison就是通过声明优先级来解决二义性的。注意二义性不等于语言本身是二义性的。同一个语言可以存在某些二义性文法也存在某些无二义性文法。而且语言本身不存在所谓“二义性”这个性质只有“文法”有二义性。存在一些语言任何生成它的上下文无关文法都是二义性的这种语言被称为固有二义性语言不过在实际程序语言设计中我们关心的语法基本都是可以消除二义性的。实操提示设计文法时务必测试是否存在二义性。一个简单的方法是用不同推导路径最左、最右尝试得到同一个句子看看是否产生不同的语法树。即使你的文法能正确描述语言只要存在一棵无用的分析树调试时你会非常头疼。5. 课程重点与实践应用5.1 核心概念的关联与整体框架语言的定义这一章核心概念都围绕一个中心议题如何用形式化工具精确地描述和识别语言。整章的知识框架可以分为三层最底层是字符串它是语言的“素材”。字母表、闭包、连接这些运算决定了能形成哪些字符串。中间层是文法它用递归的产生式规则描述“哪些字符串属于这个语言”。不同的文法0型到3型对应不同的表达能力。最顶层是语言本身它是所有能被文法生成的字符串的集合。这三个层面相互关联语言 L(G) 是从文法 G 产生的文法规定了语言的生成规则字符串是语言中的元素。理解了这三层的递进关系后面学词法分析识别单词和语法分析识别句子结构时就能清楚知道编译器在每个阶段采用哪种文法、哪种自动化工具。我建议学习时把这张框架图牢牢记住每次学新知识点都往里面塞。比如学到有穷自动机你就知道它是 3 型文法的“识别器”学到下推自动机你就知道它是 2 型文法的“识别器”学到语法制导翻译你就知道它是基于语法树来做语义动作的机制。整个编译原理的知识体系是一张网语言的定义就是网的中心节点。5.2 从理论到实践文法在编译器各阶段中的应用文法不只是书上的数学符号它在真实编译器中贯穿始终。这里梳理一下实际编译器的各个阶段如何应用这些理论词法分析阶段正规文法/正则表达式 → 有穷自动机 → Token 流。实际工具是 Lex/Flex用于生成词法分析器的代码。词法规则如关键字、运算符、标识符的匹配全部用正则表达式的形式编写。语法分析阶段上下文无关文法CFG → 下推自动机/递归下降分析 → 语法分析树或抽象语法树AST。实际工具是 Yacc/Bison 或手写递归下降分析器。语法分析器检查 Token 序列是否符合 CFG 规则并建立结构表示。语义分析阶段基于 AST 做类型检查、符号表管理等。这一部分不再依赖文法的生成能力而是需要“上下文有关”的信息比如标识符的类型、作用域因此用属性文法属性文法和语法制导翻译来增强 CFG 的能力。中间代码生成阶段根据 AST 生成三地址码、LLVM IR 等中间表示。这里用到的主要是遍历 AST 并输出对应中间表示文法的结构就是遍历的指南。有一个很好的实践练习写一个小的 JSON 解析器或者计算器。用 CFG 写出它的语法再用手写递归下降的方法实现你会直观体会文法设计对代码结构的决定性影响。我当年就是这样练出来的——写计算器时最初把优先级硬编码进递归函数里后来发现其实可以直接把文法中的优先级层次翻译成递归函数的调用层次两者完全对应。5.3 结合哈工大课程的学习思路哈工大这门课讲解语言的定义一条明显的主线是“由浅入深、由形式化定义到计算模型”。如果你正在自学我强烈建议按这个顺序听课或读书先理解字母表、字符串、语言的关系这决定了后面所有的符号表示。再掌握文法四元组 G(V,T,P,S)学会“给定文法推导句子”的基本操作做 10 道以上的手推题直到不再需要看答案。掌握文法的分类逻辑0 到 3 型的限制条件并把每种文法对应到相应的自动机。开始练习“判断一个文法属于哪一型”“判断给定的语言能否由某型文法生成”。这一步开始考验对性质的深度理解。最后做到“自己设计一个简单语言的文法”比如设计一个简单的循环语句的文法、一个四则运算表达式的文法并消除二义性。练习时特别要重视手推过程千万别只看视频。编译原理是一门动手学科眼睛会了手不会的情况太常见了。我推荐把每个文法的例子从头到尾推导三遍第一遍按视频里的步骤照抄第二遍不看视频自己推第三遍换一个输入串推。三遍之后你会对“文法产生语言”这个过程建立牢靠的直觉。还有一点小经验哈工大课程里经常用到一些经典文法例题如算术表达式文法、括号匹配文法、回文字符串文法这些例题值得背下来并反复推导。它们不仅出现在考试的填空选择里更重要的是它们覆盖了上下文无关文法最具代表性的表达能力。掌握了这些看其它应用中的文法都会觉得眼熟。6. 常见问题与易错点剖析6.1 空串 ε 与空语言混淆这是我身边同学踩得最多、也是考试中最常见的陷阱。ε 是一个字符串长度为 0∅ 是一个集合里面没有元素。表现在符号上{ε} 和 ∅ 完全是两个概念。例如语言 {ε} 包含一个句子即空串。文法 S→ε 定义的语言就是 {ε}。语言 ∅ 不包含任何句子。文法的开始符号如果没有任何产生式或者存在产生式但永远无法推导出终结符串那么 L(G)∅。有人会混淆 ε 和 ∅还有人会把 {ε} 写成 ε这些都是低级但致命的错误。要检验自己是否真懂可以想一想如果文法 S→εS→a那么 L(G) 是什么答案是 {ε, a}。这里 ε 是合法句子。再想一想如果文法 S→a而 a 无法推出空串那么 ε 不在 L(G) 里。理解这个区别对后面构造自动机、理解正规文法的空串处理非常有帮助。6.2 文法类型判定时的边界条件判断文法属于哪一型看起来简单看产生式左部长度和右部限制但边界情况非常容易出错0 型文法允许产生式左部不是单个非终结符比如 AB→BA。但要求左部至少包含一个非终结符。1 型文法要求 α→β其中 |α| ≤ |β|且 α 含非终结符。这意味着产生式不会缩短字符串除了可能单独存在 S→ε 的情况。注意上下文有关文法的产生式可以写成 uAv→uwv 的形式其中 A 是单个非终结符。2 型文法要求左部必须是单个非终结符。右部没有长度限制可以是任意终结符和非终结符的混合。3 型文法要求右部为 A→aB 或 A→a右线性或者 A→Ba 或 A→a左线性。注意左线性和右线性不能混用如果混用了产生的语言可能不是正规语言。一个常见的混淆点是形如 A→aB 且 A→Ba 的文法我们还要检查它是否“左右混合”。正规文法严格限制了方向所以判断时要一项项核对。哈工大的习题里这种题非常多我建议把每道题的文法先归类再试着构造对应的自动机以验证判断是否正确。6.3 推导与归约视角的转换很多初学者会混淆推导Derivation和归约Reduction。推导是从开始符号出发正向地应用产生式最终得到句子归约是从句子出发反向应用产生式最终归约到开始符号。它们是互逆的过程。语法分析器的核心操作其实就是归约自底向上或推导自顶向下的过程。具体做题时碰到“给定输入串和文法验证它是否是该文法的句子”你可以用推导的方法从头构建也可以用归约的方法从尾倒推。我个人的经验是归约方式更难出错因为它是从目标出发每一步选择当前句型中能匹配产生式右部的子串将其替换回左部。这种“向前看”的目标导向策略在实际语法分析中也是 LR 分析器的思想。6.4 二义性的判断与消除判断文法是否二义性最常见的错误是用“最左推导和最右推导结果是否相同”来判断。这个方法是误的。正确的方法是看是否存在某个句子它能生成两棵或更多不同的语法分析树。你可以对某个句子穷举所有可能的推导包括最左和最右看是否会生成多棵不同的树。如果存在第二个不同的最左推导序列或第二棵不同的语法树那么文法就是二义性的。例如一个文法S → if E then S | if E then S else S | 其他是经典二义性文法因为嵌套 if 语句会产生经典“悬挂 else”问题。消除的方法是引入语法规则或重写文法让 else 匹配最近的未匹配 if。这是编译原理教材的经典案例读者要重视它因为很多实际语言的 if 语句都避免不了这类问题编译器在实现时一般通过优先级或特设规则来解决。实操心得在设计语言的文法时第一时间就要想二义性。与其写了大量产生式再回头排查不如在文法初稿时对每个产生式问三个问题是否存在两种解析方式是否会出现循环定义左递归是否有优先级不明的情况这三个问题排查完了二义性风险就小很多。7. 工具选型与参考资料7.1 理论学习阶段的资源推荐哈工大这门课是国内编译原理教学中的口碑之作它把理论讲得比较严谨同时配合了足够多的例题和实验。如果你不只满足于看视频想系统化学习语言的定义我还推荐结合以下资源交叉使用经典教材理论部分可以参考《编译原理》俗称“龙书”的前两章它对形式语言和文法分类的讲解非常系统逻辑严密。形式语言与自动机如果对文法分类、自动机理论想深入可以看看形式语言与自动机理论的专门教材重点看上下文无关文法和下推自动机的对应关系。在线练习平台不少大学的编译原理课程网站提供了文法的在线推导练习和自动判题系统可以让你快速获得反馈。注意我不建议一上来就啃龙书因为它内容厚、符号多很容易劝退。最好以哈工大视频为主线辅以龙书查阅特定概念的定义。遇到看不懂的数学符号先跳过等理解了整体框架再回头关细节。7.2 实践工具链推荐如果你想在学完语言定义后立即动手实践我给你推荐一套投入产出比最高的工具链Flex/Lex生成词法分析器的工具。用正则表达式定义词法规则自动生成 C 代码。体验“正规文法 → 有穷自动机 → 代码”的魔法。Bison/Yacc生成语法分析器的工具。用 CFG 定义语法自动生成语法分析器代码。它支持用优先级声明来解决二义性可以直观体会消除二义性的工程手段。ANTLR一个更现代、跨平台的语法分析器生成器适合用 Java、Python、C# 编写语法。它生成的代码可读性更好社区活跃还有图形化语法树可视化功能。如果只是验证小文法、看看语法树长什么样也可以直接用一些在线的语法分析器模拟器比如可以输入文法和输入串自动生成推导过程和分析树。比起手写推导可视化工具对建立直觉帮助巨大。7.3 做一个手写递归下降分析器的小项目这里强烈推荐一个适合初学者的项目用 Python 手写一个递归下降分析器解析四则运算表达式支持括号、加、减、乘、除。这个项目虽然小但把语言定义章节的几乎所有概念都用上了流程是先设计一个无二义性的算术表达式文法把优先级体现在文法的层级结构里再根据文法写成一组递归函数每个非终结符对应一个函数每个产生式对应函数内部的判断分支。最后输入字符串如(12)*(34)输出计算值或语法错误。做完这个项目你就能体会“上下文无关文法不是说说的它能精确指导代码结构”这件事。很多写解释器、编译器的开发者第一步都是从这里练起的。跟单纯看视频相比动手写一个能跑起来的分析器学习的深度完全不同。8. 总结与个人心得语言的定义这一章内容量看着不多但它是整个编译原理体系里最关键的概念基石。我在学习过程中最大的感受是一旦你真正理解了“语言 字符串集合 文法生成规则 识别器判定”这三者之间的关系后面学词法分析、语法分析、语义分析其实就是不断往这框架里加细节。反过来如果地基没打牢后面学得再多始终像是空中楼阁碰到具体问题就发慌。对于刚开始接触这门课的朋友我的建议是不要图快语法的形式化定义部分可以放慢速度多推导几遍多画几棵分析树多做一些判定类题目。形式化思维是一种需要“练”才能建立的直觉光看书是无法内化的。等你能自己独立设计一个简单语言的 CFG 并完成推导时你就能明显感觉到自己“入门”了。另外还有个小技巧学语言的定义时把每个概念都用自己的话解释一遍给自己听。比如“上下文无关文法就是在替换一个非终结符时不需要考虑它在句中的上下文”能用自己的话讲清楚的人才是真的理解了。这个方法我试了很多年每次学新理论都用效果好得出奇。最后如果你准备继续深入编译原理那么现在学的内容会在语法分析章节、语义分析章节反复出现。尤其是文法分类和自动机对应关系在词法分析器、语法分析器的自动生成工具中都是直接的理论依据。这门课学好了你以后看任何语言的编译器源码、写自己的 DSL领域专用语言都会觉得底气十足。
阅读完成 · 觉得有帮助？
