前言

本文由不带任何参考的主观印象构成,主要是宏观上对编译原理及其带来的思想做讨论。

编译器

编译器一般可以分为3个部分:

  • 预处理器
  • 编译器
  • 链接器

通常在实现上把预处理器和编译器放在一起,链接器独立实现的较多。

预处理器的目的是在编译前对源文件的格式及预处理指令做处理,常见的宏等,都在这个阶段进行处理。

编译器则是对预处理后的源文件进行解析,将其翻译为另一种表述形式,既可以是二进制机器码,也可以是某种中间语言的表达形式。

链接器并非必须品,其目的是将多个源码生成出来的中间文件整理到同一个文件中,主要工作是重新分配地址空间,例如对预留的函数地址填充等工作,另外,有时它还会负责将文件转为目标平台支持的可执行文件格式。

这个系列主要聊的还是编译器部分

编译的基本过程

就目前笔者所阅读过的几种实现中,常见有如下两种

  1. 由语法分析器驱动词法分析器
  2. 先生成TOKEN序列,再由语法分析器对序列进行分析

语法分析器部分则一般是生成符号表及抽象语法树,再通过代码生成对语法树解析生成进一步的代码。

一般的语义分析器与代码生成器会放在一起。

也存在有直接把语法分析器语义分析器代码生成器放在一起而不经过抽象语法树,直接生成代码的编译器,例如lua。

无论是作为教学抑或是基础学习目的,建议还是采用生成抽象语法树和符号表的方法进行辅助编译。

词法分析器的工作主要是识别源码中的 保留字 标识符 常量,并跳过空白字符,以提供给语法分析器足够的信息去生成语法树和符号表。

语法分析器主要的目的是根据词法分析器的内容,构建语法树及符号表,以保证语法树符合语法要求,可以理解为一门语言语法的实例化分析工具。

语义分析器则是对一些符合语法却不符合语义的内容进行处理识别,例如 赋值的左右不匹配,改写右值等,这个一般不会独立出来,而是放在代码生成阶段。

代码生成器俗称后端,主要涉及的代码优化和根据语法树进行翻译,关于这一部分,个人学习不深。

逆波兰表达式

聊到语法分析器,就不得不提逆波兰表达式,这是一种后缀表达形式,通过这种形式很容易生成语法树。

1+1*2
112*+

(1+1)*2
11+2*


add()
{
    node->left = mul();
    for(;;){
        switch(next){
        '+':
        '-':
        {
            node->op = next;
            next();
            node->right = mul();
            break;
         }
         default:
             return node;
        }
    }
}

mul()
{
    node->left =  num();
    for(;;){
        switch(next){
        '*':
        '/':
        {
            node->op = next;
            next();
            node->right = num();
            break;
         }
         default:
           return node;
        }
    }
}

上面是一段伪代码,用于表达基础四则运算的解析方式,随手写的,可能并不正确

1+1*2

    +
  /   \
 1      *
      /   \
     1     2

通过后续遍历能得到

1 1 2 * +
此时通过求值栈等方式就很容易生成代码了

push 1
push 1
push 2

pop eax
pop ebx
mul eax, ebx
push eax

pop eax
pop ebx
add eax, ebx
push eax

pop eax
ret

上面也是演示生成结果的伪代码

可以通过扩充运算符,进一步形成表达式 语句等概念。

通过这些概念,又能引出 块 和 函数的概念,最后就能形成源文件。

而对存储表达式的结果上,又能形成变量的概念。

变量名和函数名进一步引出标识符,标识符会存放于符号表,为作用域等提供支持。

对变量包装又能引出结构体等,组合出各种内存存放方式。

最后是流程控制,其也是对上述过程的调整。

至此一门语言的雏形就构建完成。

文法规则

一般来说,在编写语法分析器时是非常依赖文法规则的。

通常有几种表现形式,这里就不一一列举了。

add = mul ("+" mul | "-" mul)*
mul = num ("" num | "/" num)

这是一种表示方法,通过这种表示,很容易就能推出具体怎么去实现。

学习编译原理对实际开发的影响

这种影响主要是对思想上的,一方面在写代码的时候,能更确信自己在干嘛。另一方面,当编译器报错的时候,能更快的定位并修正错误。同时也有助于写出效率更高的代码。

结语

简单聊了一下编译器的基础知识,如果这个系列有时间完成的话,我会拆解开,逐个部分都实现一次。就个人而言,我也一直考虑设计一门语言以帮助我当下更好的工作。

本文仓促而成,有时间会回炉重造。