为什么编译原理被称为龙书? (2)

我们上面大概了解了一下语言的处理过程,下面我们就来了解一下编译器的内部结构,编译器内部其实具有两种结构:分析(analysis)部分和 整合(synthesis) 部分。

分析过程相当于是把源程序分成多个结构,每个结构都有特定的语法格式进行校验,在经由每个校验后,如果不满足指定的语法格式则进行提醒,使用户进行修改。分析部分还会收集有关源程序的信息,会把收集到的信息存放在一个被称为 符号表(symbol table) 的数据结构中。符号表和中间表示形式一起传给整合部分。

整合过程是根据分析过程传递的信息来构造用户期待的目标程序。分析和整合统称为 前端(front end) 和 后端(back end) ,哈哈哈哈。

这里你需要知道符号表(Symbol Table) 的概念:符号表是编译器使用和维护的数据结构,由标识符和类型组成。符号表的主要作用是帮助编译器快速定位。

下面是一个编译器的典型结构

为什么编译原理被称为龙书?

下面我们就针对编译器结构的每一层进行描述和讨论

词法分析

词法分析(Lexical Analyzer)是编译器的第一个步骤,它也被称为 扫描(scanning)。词法分析器通过读入外部的字符流对其进行扫描,并且把它们组成有意义的词素(lexeme)序列,对于每个词素,词法分析器都会产生词法单元(token) 作为输出。这个词法单元会传递给下一个步骤,也就是语法分析。

这里需要解释一下 Token 、词素和词法分析器的概念

我们常用的编程语言就是具有词素的单词和符号的集合,比如 C 语言中有 (),-> 等等。关键字 if...while...,变量或函数名称以及数字和字符串常量也被视为词素。并不是所有的自负都属于词素,例如空格和注释就不属于。

词法分析器用来分析词素有两个规则

跳过不能以字母开头的字符

然后找到剩余的最长前缀,也就是词素

这两句话比较抽象,举个例子来说明一下

比如 C 语言中有这么一个语句

ifx = 20*30;

那么第一个词素就是 ifx,为什么不是 if 呢?因为 if 不是最长的前缀。然后后面的词素依次是 =,20,*,30和;。

词素、词法分析器、token 的关系如下

为什么编译原理被称为龙书?

词素是 Token 的实例,词法分析器的主要任务就是从源程序中读取字符并产生 token。token 也是有结构的,一般结构如下

为什么编译原理被称为龙书?

在词法分析生成的 token 中,第一个词 token-name 是语法分析期间使用的抽象符号,第二个词 attribute-value 指向的是符号表中关于这个词法单元的条目数。

我们举个例子来看一下词法分析的拆解过程。

比如现在源程序中有一个赋值语句

income = mainjob + sideline // 收入 = 主业 + 副业

这个赋值语句中的字符可以组合成如下词素,并转换成为 token,并传递给语法分析阶段。

首先,income 是一个词素,它会被映射为 <id,1>,其中 id 是表示的 标识符(identifier) 的抽象符号,而 1 指的是符号表中 income 在符号表中的条数。

然后是赋值符号 = ,它也是一个词素,被映射称为 token 中的 < = >。这个 token 不需要属性值,所以没有第二个词。

mainjob 是一个词素,它被映射成为 token 中的 <id,2>,2 是 mainjob 对应的符号表条目

+也是一个词素,它被映射称为 < + >,没有条目数

sideline 是一个词素,它被映射称为 token 中的 <id,3>,3 是 sideline 对应的符号表条目

所以,经过词法分析后,上面的源程序会变为

<id,1> < = > <id,2> < + > <id,3>

在上面的表达式中, = 和 + 分别表示赋值和加法运算符的抽象符号。用图来表示的话就是

为什么编译原理被称为龙书?

语法分析

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpfjzf.html