您当前的位置:首页 > 计算机 > 编程开发 > 编译原理

编译原理之编译器的前端技术

时间:05-17来源:作者:点击数:

学习编译原理能让你从前端的语法维度、代码优化的维度、与硬件结合的维度几个方面,加深对计算机技术的理解,提升自己的竞争力。

编译器的前端技术

前端”指的是编译器对程序代码的分析和理解过程。它通常只跟语言的语法有关,跟目标机器无关。“后端”则是生成目标代码的过程,跟目标机器有关。

在这里插入图片描述

词法分析

词法分析是把程序分割成一个个Token的过程,可以通过构造有限自动机来实现。

下面这段代码,如果我们要读懂它,首先要怎么做呢?

#include <stdio.h>
int main(int argc, char* argv[]){
    int age = 45;
    if (age >= 17+8+20) {
        printf("Hello old man!\\n");
    }
    else{
        printf("Hello young man!\\n");
    }
    return 0;
}
  • 首先会识别出 if、else、int 这样的关键字,main、printf、age 这样的标识符,+、-、= 这样的操作符号,还有花括号、圆括号、分号这样的符号,以及数字字面量字符串字面量等。这些都是Token

如何写一个程序来识别 Token 呢?

  • 可以通过制定一些规则来区分每个不同的 Token
    • 识别 age 这样的标识符。它以字母开头,后面可以是字母或数字,直到遇到第一个既不是字母又不是数字的字符时结束。
    • 识别 >= 这样的操作符。 当扫描到一个 > 字符的时候,就要注意,它可能是一个 GT(Greater Than,大于)操作符。但由于 GE(Greater Equal,大于等于)也是以 > 开头的,所以再往下再看一位,如果是 =,那么这个 Token 就是 GE,否则就是 GT。
    • 识别 45 这样的数字字面量。当扫描到一个数字字符的时候,就开始把它看做数字,直到遇到非数字的字符。

这些规则可以通过手写程序来实现,也可以用词法分析器的生成工具来生成,比如 Lex(或其 GNU 版本,Flex)。这些生成工具是基于一些规则来工作的,这些规则用“正则文法”表达,符合正则文法的表达式称为“正则表达式”。生成工具可以读入正则表达式,生成一种叫“有限自动机”的算法,来完成具体的词法分析工作。

  • 正则文法是一种最普通、最常见的规则,写正则表达式的时候用的就是正则文法。
  • 有限自动机(英语:deterministic finite automaton, DFA)是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表 E 的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。

词法分析器也是一样,它分析整个程序的字符串,当遇到不同的字符时,会驱使它迁移到不同的状态。例如,词法分析程序在扫描 age 的时候,处于“标识符”状态,等它遇到一个 > 符号,就切换到“比较操作符”的状态。词法分析过程,就是这样一个个状态迁移的过程。

在这里插入图片描述
  • 我们在编程过程中经常用正则表达式来做用户输入的校验,例如是否输入了一个正确的电子邮件地址,这其实就是在做词法分析

语法分析

语法分析是把程序的结构识别出来,并形成一棵便于由计算机处理的抽象语法树。可以用递归下降的算法来实现。

  • 词法分析是识别一个个的单词,而语法分析就是在词法分析的基础上识别出程序的语法结构。这个结构是一个树状结构,是计算机容易理解和执行的。
  • 自然语言有定义良好的语法结构,比如,“我喜欢又聪明又勇敢的你”这个句子包含了“主、谓、宾”三个部分。主语是“我”,谓语是“喜欢”,宾语部分是“又聪明又勇敢的你”。其中宾语部分又可以拆成两部分,“又聪明又勇敢”是定语部分,用来修饰“你”。定语部分又可以分成“聪明”和“勇敢”两个最小的单位。这样拆下来,会构造一棵树,里面的每个子树都有一定的结构,而这个结构要符合语法。
    在这里插入图片描述

程序也有定义良好的语法结构,它的语法分析过程,就是构造这么一棵树。一个程序就是一棵树,这棵树叫做抽象语法树(Abstract Syntax Tree,AST)。树的每个节点(子树)是一个语法单元,这个单元的构成规则就叫“语法”。每个节点还可以有下级节点。

  • 层层嵌套的树状结构,是我们对计算机程序的直观理解。计算机语言总是一个结构套着另一个结构,大的程序套着子程序,子程序又可以包含子程序。
var a = 42;
var b = 5;
function addA(d) {
    return a + d;
}
var c = addA(2) + b;
        

下图是这段JavaScript 语言编写的代码的 AST

在这里插入图片描述

怎样写程序构造AST呢?

  • 一种非常直观的构造思路是自上而下进行分析。首先构造根节点,代表整个程序,之后向下扫描 Token 串,构建它的子节点。当它看到一个 int 类型的 Token 时,知道这儿遇到了一个变量声明语句,于是建立一个“变量声明”节点;接着遇到 age,建立一个子节点,这是第一个变量;之后遇到 =,意味着这个变量有初始化值,那么建立一个初始化的子节点;最后,遇到“字面量”,其值是 45。
    在这里插入图片描述
  • 这个算法就是非常常用的递归下降算法

递归下降算法是一种自顶向下的算法,与之对应的,还有自底向上的算法。这个算法会先将最下面的叶子节点识别出来,然后再组装上一级节点。有点儿像搭积木,我们总是先构造出小的单元,然后再组装成更大的单元。

  • 这些规则可以通过手写程序来实现,也可以通过现成的工具,比如 Yacc(或 GNU 的版本,Bison)、Antlr、JavaCC 等。
  • 编写一个自定义公式的功能,对公式的解析就是语法分析过程。另一个例子是分析日志文件等文本文件,对每行日志的解析,本质上也是语法分析过程。解析用 XML、JSON 写的各种配置文件、模型定义文件的过程,其实本质也是语法分析过程,甚至还包含了语义分析工作。

语义分析

语义分析是消除语义模糊,生成一些属性信息,让计算机能够依据这些信息生成目标代码。

  • 计算机语言的语义一般可以表达为一些规则,只要检查是否符合这些规则就行了。比如:
    • 某个表达式的计算结果是什么数据类型?如果有数据类型不匹配的情况,是否要做自动转换?
    • 如果在一个代码块的内部和外部有相同名称的变量,我在执行的时候到底用哪个?
    • 在同一个作用域内,不允许有两个名称相同的变量,这是唯一性检查。
  • 语义分析基本上就是做这样的事情,也就是根据语义规则进行分析判断
  • 语义分析工作的某些成果,会作为属性标注在抽象语法树上,比如在 age 这个标识符节点和 45 这个字面量节点上,都会标识它的数据类型是 int 型的。在这个树上还可以标记很多属性,有些属性是在之前的两个阶段就被标注上了,比如所处的源代码行号,这一行的第几个字符。这样,在编译程序报错的时候,就可以比较清楚地了解出错的位置。

DSL 其实是 Domain Specific Language 的缩写,中文翻译为领域特定语言

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门