在程序员的备考之旅中，编译原理是一个重要的板块。今天我们聚焦于考前3天需要重点掌握的内容，包括四种文法类型（0型/1型/2型/3型）的包含关系、词法分析器（Lex）与语法分析器（Yacc）协同工作流程以及中间代码优化（常量传播/死代码消除）的核心思路。
一、四种文法类型的包含关系
- 0型文法（短语文法）
- 知识点内容：0型文法是最宽泛的文法类型。它的产生式形式为$A→\alpha$，其中$A$是非终结符，$\alpha$是终结符和非终结符组成的任意字符串，甚至可以是空串。
- 学习方法：理解0型文法的定义时，可以通过一些简单的例子来加深印象。比如对于一个只包含字母和数字的字符串集合，我们可以定义一个非终结符$S$，它的产生式可以是$S→aS$（表示可以有多个$a$后面跟着$S$自身），$S→b$（表示也可以是单独的$b$）等，这只是一些简单的示例，0型文法可以有非常复杂的产生式组合。
- 1型文法（上下文有关文法）
- 知识点内容：1型文法在0型文法的基础上增加了限制条件。它的产生式$A→\alpha$要满足$\vert\alpha\vert\leqslant\vert A\vert$（除了$S→\epsilon$这种特殊情况，其中$S$是开始符号），也就是产生式右边的长度不能小于左边非终结符的长度（除了开始符号推导出空串的情况）。
- 学习方法：可以通过对比0型文法来学习。例如对于一个描述数学表达式的文法，如果是0型文法可能允许比较随意的产生式，但如果要满足1型文法的规则，在定义数字和运算符的关系时就要遵循长度的限制条件。
- 2型文法（上下文无关文法）
- 知识点内容：2型文法的产生式形式为$A→\alpha$，其中$A$是非终结符，$\alpha$是终结符或非终结符组成的字符串，并且产生式的左边必须是一个单独的非终结符。
- 学习方法：这是我们经常遇到的一种文法类型。可以通过编写一些简单的语法规则来掌握，比如定义一个描述简单句子结构的文法，主语 + 谓语 + 宾语的形式，主语可以用名词表示（非终结符），谓语用动词表示（非终结符）等。
- 3型文法（正规文法）
- 知识点内容：3型文法又分为右线性文法和左线性文法。右线性文法的形式为$A→aB$或者$A→a$，左线性文法的形式为$A→Ba$或者$A→a$，其中$A,B$是非终结符，$a$是终结符。
- 学习方法：可以通过识别一些正则表达式对应的正规文法来学习。例如对于匹配以$a$开头后面跟着若干个$b$的字符串，可以定义一个正规文法$S→aS$和$S→b$。
四种文法的包含关系是：3型文法⊆2型文法⊆1型文法⊆0型文法。
二、词法分析器（Lex）与语法分析器（Yacc）协同工作流程
- 词法分析器（Lex）的工作
- 知识点内容：Lex主要负责将输入的源程序字符流分解成一个个的单词符号（token）。它会根据预先定义好的规则模式来识别不同的单词，比如识别关键字、标识符、常量、运算符等。
- 学习方法：要熟悉Lex的语法规则文件的编写。例如定义一个标识符的规则可能是$[a - z_][a - z0 - 9_]*$，这就表示以字母或下划线开头后面跟着字母、数字或下划线的字符串为标识符。
- 语法分析器（Yacc）的工作
- 知识点内容：Yacc根据给定的语法规则对词法分析器输出的单词符号序列进行语法分析，构建出语法树。它会按照语法规则来判断单词符号的组合是否合法，并且确定它们之间的结构关系。
- 学习方法：需要理解Yacc的语法文件的结构，包括定义终结符和非终结符、产生式规则以及语义动作等部分。
- 协同工作流程
- 首先，词法分析器Lex对源程序进行扫描，将输入流分解成单词符号，并将这些单词符号传递给语法分析器Yacc。然后，语法分析器Yacc根据语法规则对这些单词符号进行处理，如果语法正确就构建出语法树，如果语法错误则报错。
三、中间代码优化（常量传播/死代码消除）核心思路
- 常量传播
- 知识点内容：常量传播就是在进行中间代码优化时，如果一个变量在某处被赋值为一个常量，并且之后这个变量的值没有被改变，那么在后续的计算中就可以直接使用这个常量代替变量。例如，有中间代码$x = 5;y = x+3$，经过常量传播后可以变为$y = 5+3$。
- 学习方法：可以通过分析一些简单的中间代码示例来掌握。在实际操作中，需要遍历中间代码的控制流图，找到可以进行常量传播的地方。
- 死代码消除
- 知识点内容：死代码是指那些在任何情况下都不会被执行的代码。比如在一个条件判断中，如果某个分支永远不会被执行，那么这个分支中的代码就是死代码。消除死代码可以提高程序的执行效率。
- 学习方法：要能够识别出程序中的不可达路径。可以通过控制流分析等手段来确定哪些代码是死代码，然后将其从程序中删除。
总之，在考前3天，重点复习这些编译原理的核心知识点，能够让我们在考试中更加从容应对相关题目。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
