深究——编译器是如何进行编程语言转换的？

[复制链接]

eefishing 发布时间：2020-1-8 23:01

技术帖
文章封面:	-
文章简介:	-

对于每天奋斗在一线，用Java，C++，C#，Python等高级编程语言写程序的程序员们来说，理解编译器是如何将高级语言编译成汇编语言，有助于我们更好的理解计算机编程。

编译器将高级语言转化成汇编语言主要经过三个步骤：词法分析、语法分析、语法树解析。

本文用简洁易懂的方式描述了这一过程，相信不需要很深的计算机背景知识，也能轻松读懂本文。

第一步：词法分析

最开始的时候，高级语言编写的程序对编译器来说只是一连串的单个字符组成的字符串。为了让编译器识别这一连串的字符串，需要逐个字符的读取源程序，然后将其切分成有意义的单词，这些被切分后的单词在编译器眼里是以

<标识，语义值>对的形式存在。

为了从源程序字符串中依次找出单词，编译器需要具有扫描功能，通常这种扫描器可以用一组有限状态机来实现。为了说明有限状态机是怎么一回事，下面给出一个实例。

下图为一个识别数字的有限状态机，数字由整数部分和可选的小数部分组成。因此，根据这个有限状态机，250和3.14159都能被识别成一个有效的数字。

图一：有限状态机

绿色的结点用环形标志，表示他们是“可接受”的状态，也就是说，只要我们的状态达到了绿色的结点，就表示我们之前读取到的数据是一个有效的数字。例如，从图中的start处开始，如果我们读到的数字是42.15，那么依次经历的状态是（1,2,2,3,3,3），由于这一系列状态最终以“可接受”的状态结束(也就是图中的状态3)，因此我们就读取到了一个有效的数字。而且读取到的数字42.15用<标识，值>对的形式表示成<NUMBER,42.15>。这里的NUMBER是用于标识我们读取到的内容是一个数字，而文本“42.15”是标识对应的语义元素值。

我们可以用为不同类型的单词定义不同的类似上述的小状态机，例如变量名可以由字母、下划线组成，操作符可以取+=、->，关键字则可以是“if”“while”等单词，类型则可以是“int”“char”等等单词。为每一类单词构造一个小的有限状态机，最终组成一个可以接受不同类型单词的大状态机。可以用表的形式存放我们得到的大状态机。至此，我们通过构造一个大状态机得到一个能识别各类单词的自动扫描器。

至此，第一步大功告成，这一步我们通常称之为“语法分析”阶段。

高级源程序通过语法分析后，我们得到的结果是<标识，值>对，以方便后续处理。

为方便理解，这里举个简单的例子。

比如，我们程序语句：

if ( x == 2 ) { x = a + b; }

通过词法分析后，得到<标识，值>对如下：

(KEYWORD,”if”),

(IDENTIFIER,”x”), (OPERATOR,”==”), (NUMBER,”2″), (DELIMITER, “{“),

(IDENTIFIER,”x”), (OPERATOR,”=”), (IDENTIFIER,”a”), (OPERATOR,”+”),

(IDENTIFIER,”b”), (DELIMITER,”;”), (DELIMITER,”}”).

第二步：语法分析

完成了“词法分析”后，接下来就是激动人心的“语法分析”阶段。通过语法分析得到语法树。