编译原理的流程及各阶段的任务

在编译原理中,我们将一个编译过程分成以下六个阶段来讨论:

  • 词法分析
  • 语法分析
  • 语义分析
  • 中间代码生成
  • 优化
  • 目标代码生成

在第一个阶段,我们的工作是将输入的源程序识别为token流,所谓token,就是单词,即语法所规定的有意义的语言单位。
例如,在编程语言的文法中,id 常常作为一个最末端的符号出现,也就是说,在语法分析中只能识别id 这个符号,而并不知道一个字母的组合到底是何含义。中间需要一个转换,这就是词法分析所做的。它要将变量名转换为<id, info>这种形式,从而可以应用于语法识别。当然,去除多余空格等额外的工作也不在话下了。

在第二个阶段,我们将token流作为输入,构造语法分析树,借此分析句子是否符合文法的规定。

在第三个阶段,我们利用已经构造好的语法分析树,给每个结点附上属性值,并在遍历树的过程中计算这些属性值,或者说只是单纯地执行特定计算,从而实现我们需要的计算任务。这一步称为语义分析,什么是语义?语法分析树已经给出了各个语法单元之间的关系,语义就是这些关系中所隐藏的信息,具体来说就是我们所关心的属性。在树中各个结点间属性的继承、传递、综合的过程,就是语法分析的过程。这个过程常常由树的遍历来实现,但其实可以在构建语法树的过程中来进行,这两者是一样的。

在第四个阶段,我们开始着手考虑我们作为语言翻译器的目标,也就是将源程序转化为目标代码。考虑到目标代码的多样性和不确定性,我们设立一个中转站,旨在为源代码和目标代码提供一种双方均能方便理解的沟通方式,它就是这一阶段的主角——中间代码。中间代码是通过语法分析得到的一种抽象的语义表示,我们可以用抽象语法树、DAG图、三地址代码来描述。在表示编程语言这方面,三地址代码是最合适的。因此,我们这一阶段的目标就是利用语法分析提供的工具生成三地址代码。

在第五个阶段,需要在将三地址代码转化到目标代码之前做一些优化,主要包括去除冗余,削弱计算强度等方面。优化的目的无非是使代码转化更有效和使目标程序的执行效率更高。

在第六个阶段,就是面对具体的平台所做的工作了。这一步和计算机硬件联系较为密切,暂时先不予讨论。

以上只是做一个简单的区分,实际上我们可以看出,各个阶段不是各自独立、分着先后进行的。我们可以在词法分析的同时进行语法分析,在建立语法分析树的同时执行语义计算,而语义分析的过程也就是中间代码生成的过程,因为前者只是工具,后者才是具体的应用。区分是为了更明白地理清思路,从而一步一步达到我们的目标。

有两个一直贯穿整个过程的事项,就是符号表的组织管理与出错处理。符号表提供了关于变量、过程的相关信息,而出错也是编译过程中不可避免的问题。两者都是必不可少的工具,在设计程序时可根据需求进行实现和完善。

前人已经为我们奠定了理论基础,思路和流程已经明晰,可以试着动手,编写自己的第一个编译程序了。遵循快速迭代的原则,不断前进并解决问题,从成形到精致打磨,从实践中收获真知。