正式上课前注意点梳理

关于编译原理学习

编译本身是一个超级算法，其中分成两大部分：理论和技术。

编译原理的学习不同于离散数学，离散数学的各个部分是相对而言分离的，各部分没有直接的前后因果关系，但是编译原理作为一个“算法”，是一个整体，前后贯通和呼应，因此，在学习编译原理的过程中，必须把前面的基础学懂了才能应对后面的内容。

根据教材，《编译原理》第一章到第五章侧重于理论，第六章和第七章是理论与技术结合，再后面的章节主要是计数方法介绍。

《编译原理》学习的要点在形式语言和自动机，所有的一切最终都是归结到自动机的理论和应用。

巩固好前驱课程，如数据结构、高级语言程序设计、汇编语言等专业课程有助于编译原理课程的学习。

关于数学的客观来源与表现形式

编译原理学习中提到的形式语言与自动机。

形式语言和自动机，是从两个角度、使用两种建模方式对相同客观对象描述的两个“等价”的数学模型，各有其在不同的环境下的用途。

数学的形式是主观的，但来源是客观的，都是对客观世界的抽象。主观性表现在抽象的形态是“随心所欲”的，同一个对象可被抽象为不同的数学表示方式和运算方式，但其根本性是客观的，离开了物化的或具体化意义的数学是不存在的，如果存在，也是毫无价值的。

初识“自动机”

话放在前面，不是严格意义上的自动机，而是为了方便初学者理解的“简化版自动机”

为了方便理解，先行介绍“简化”的自动机，我们当下可以认为自动机是由\(n\)个状态组成的状态集合，\(S= \{ s_1,s_2, \cdots ,s_n \}\)和\(m\)个字符组成的输入字符集合，\(\Sigma = \{ a_1,a_2, \cdots , a_m \}\)构成的二元组，即\(自动机 = <S,\Sigma>\)

但是真正的自动机不是二元组，而是五元组。作为初学者，可以先从理解这个二元组形式的来入门，更容易从本质上理解什么是自动机。

核查正确性，很容易联想到构造一个“字典”一样的存在，但是不可能用一个标准的字典来穷尽所有正确的单词（单词可能是无穷的）。那么自动机就起到了这个包含了无穷个单词的字典的作用（核查）。

要完整地弄懂自动机概念，需要四个方面的基础知识：集合，笛卡尔乘积，关系，函数。

当然，掌握了自动机理论，离使用这套理论构造程序语言的编译程序还有一段距离，即理论到应用的距离。应用辨识能力，需要慢慢学习。

所谓“语言”

科学和数学的定义，一是要普世、二是要精确。

回顾“关系”，关系的数学定义是：A 集合到 B 集合的笛卡尔乘积的子集。

那么，语言的数学定义是什么？

语言的数学定义：语言就是字符串的集合。

广义的“语言”，科学和数学方式定义的语言意义重大。最大直接好处是：这些概念所表的东西可以被以数学方式进行处理，比如，列出方程并求解方程，列出逻辑公式并推理，等等。

既然语言是字符串的集合，我们可以进一步用一个公式产生某些字符串的集合，遗憾的是，有些字符串的集合是找不到公式来产生的。言下之意，有些肯定是可以用公式产生的。我们编译原理关心的是这些可以由数学公式产生的字符串的集合（即语言）

形式语言的数学定义：可以由数学公式产生的语言就叫做形式语言。

1.png

人类的自然语言是不可以用数学公式表达出来的，否则，自然语言识别就是 100%准确并且 100%听懂人类语言的机器人也能被制造出来。

尽管人类语言无法用数学公式统一表达，但是程学设计语言是可以的。实际上，是先数学公式做好，再产生出对应的程序设计语言。

这个“数学公式”叫做文法或语法。

例：G 文法形式是：\(S \rightarrow aS|b\) ,其中\(S\)叫做非终止符，在这里也做开始符号，整个公式叫做产生式集合。

其推出的语言 \(L = \{ ab,aab,aaab, \cdots \}\)。

用数学公式（文法）表示的语言可以很方便的被处理，因为这个语言的特征都通过文法集中体现了，我们只要针对文法进行处理，就等价于对整个语言进行了处理。通过掌控有线而驾驭了无限。

《编译原理》可以告诉你如何分析程序设计语言的文法来驾驭这个语言。

人类语言的变化多端和本身造句的模糊性以及其本身不断地发展变化（包括规则本身的变化），使不可能被一个或一组数学公式（形式语法）完全表达。

程序设计语言不是实践的结果，而是先规定了数学公式，然后再要求用数学公式的法则来写程序。

语言是字符串的集合，所以语言就会有子集的概念，其实，我们也可以将人类语言中的一些子集用形式语法表达出来，从而实现自动化。比如语音售票机等等。

经典名句：“买一张济南到长沙的火车票”，和“我要独自一人乘着钢铁巨龙回到梦开始的地方、湘江之滨的湖南省会”，人类能理解意思相同，不过呢，售票机恐怕就不行了。

再谈“形式语言的文法”和“自动机”的关系

任何一个语言的文法都有一个等价的自动机，反之亦然。也就是说：文法和自动机本质上就是同一个东西，或者说是同一个东西的不同数学形式（在前面已经提到过对同一客观存在的不同刻画）。

而刻画的事物，实际上就是形式语言。

形式语言和自动机本质上是一个东西的不同数学表示，因此，再很多需要区别的情况下，无论是使用“文法”、“语法”、还是“自动机”，都没有区别，其混合使用的时候我们更应理解它们指的是同一事物（形式语言）。

文法分类问题

文法的分类是个需要专门花大量时间来讲述的事情，《计算理论》中由四分之一到三分之一的内容实际上实在讲述文法的分类，可见，这不是一个几句话就能说清楚的问题（文法分类的专业深度很深）。

词法是关于单词的构成方法，单词是程序语言中最简单的字符串，比如，用户取得变量名称，但是要将一个个单词连成更长的字符串，法则就会难度大很多，显然不单单是检查单词那么简单，这个时候得文法就叫做“句法”（在我们学习的课程中，习惯句法叫做语法）

教材的编写也符合从易到难的原则，第三章是词法，第四第五章是句法。

词法，难度低

句法，难度高

它们都是文法

但是，需要提醒的是：从形式语言的角度看，单词和句子本质上是一个东西，毫无区别（都是字符串），只是相对长短不同而已。

专门针对单词的自动机（文法）肯定是文法中最简单的一种，或者说是一个完整语言中的一部分，我们把这部分专门描述单词组成规则的部分叫做“词法”。

For example，C 语言的单词拼写是否正确就是靠 C 语言的词法（自动机）来判定的，把源程序输入自动机，自动机将逐一检查单词，如果有错误就会报警，指出错误。如果全部正确，那就输入这些单词，以备后面使用。

当然，只检查单词拼写规范是远远不够的，所以 C 语言词法（自动机）仅仅是其中的一部分，还得有检测句法的（人为分类）如 if else 这样的结构是否合法。

再说语言

再次强调核心概念：语言是字符串的集合。

关于问题及其求解的思考，其实也跟“语言”有密切关系。

（下面基本上原封不动搬运徐老师的讲解）

首先给你一个论断：凡是能用字符串表达出来的问题就都是一个语言。很吃惊是吧？按照这个说法，世界上的问题就没有不是语言了（因为你总要用字符串的集合，即语言，把问题表述出来）。

确实是这样，有了“语言是字符串的集合”这个定义后，世界上的任何问题都是一种语言，对于任何问题的解决，本质上就是看这个问题（即语言）是否能够用数学公式（文法）表达出来，更专业的说法是，世界上所有的问题都是语言，问题是否可解等价于该语言是否可计算，“可计算”的基础就是这个问题（即语言）是否可以用形式文法表示出来，如果能用形式语法表示出来，也就等价于存在一个自动机，它可以接受这个问题，即解决这个问题。

比如，我要你计算一个题目，题目是这样出的：“请计算 2+3=”，这个问题不就是个字符串吗，答案就是自动机（假设存在）输入问题字符串后的最终状态。

总结：世界上所有的问题都是语言

那么，把世界上所有的问题都归结为语言，这有什么意义呢？

意义很大，要理解这个问题一定要系统学习《计算理论》才能知道。

举一个语言被广义化后的意义，这是我们计算机学科特别关心的意义。计算机学科的基本问题之一：什么问题是计算机可以解决的，大致等价的问题是：什么问题是计算机不能解决的

答案是：凡是能够用形式语法（自动机）表达的问题都是可以用计算机解决的，否则就是不可解的。

计算机不是万能的，有些问题（即语言）已经被证明是不能用形式文法表达的，对这些语言（即问题 ），你就不要试图用计算机去解决它们了。

如果理论上不可解，那就彻底不可解。理论上可解，现实中也不一定可解。用逻辑术语来表达，理论上可解是现实可解的必要条件，但不是充分条件。

语义分析和中间代码生成

为什么需要语义分析

诸如类型匹配等检查仅通过词法和语法是难以实现的，类型不匹配这种语义分析要扫描前后文字，这就是“语义分析”也叫作“上下文相关分析”的原因。

按照分治的思想，设计出中间代码，介于源代码和目标代码（汇编语言代码或者机器码）的一种代码方式。

中间代码形式举例

逆波兰式

逆波兰表达式也叫做后缀表达式

要是中缀表达式复杂了，可能就不容易凭经验和概念很快写成等价的后缀式，中缀表达式转换为逆波兰式是可以用程序来完成的，这样，无论多么复杂的中缀表达式，机器都能迅速地转换为后缀式。具体的算法微信上很难写，你们先记住有这么个算法，上课时就有准备了。

三地址码形式

三地址码形式的主要特点是：一个等式中只能出现三个地址（变量）。

三地址码的具体写法又可以有三元式、四元式等等，这些形式中，一个表达式中只会出现三个地址。