The super tiny compiler(超级小的编译器)

党建义
2023-12-01

@[TOC](The super tiny compiler(超级小的编译器))

The super tiny compiler(超级小的编译器)

分别用C、RUST、ZIG实现了三个语言的The super tiny compiler,其中C语言版可以用GCC,TCC,CLANG,ZIG CC编译,目前看TCC编译生成的exe文件最小。
原项目地址: https://github.com/jamiebuilds/the-super-tiny-compiler,原项目使用JS实现。
中文翻译地址:https://github.com/521xueweihan/OneFile/blob/main/src/javascript/the-super-tiny-compiler.js

编译器的简单概念

编译器的简单概念:将源语言翻译成目标语言。
编译过程通常由词法分析器(lexer)、语法分析器(parser)、代码生成器(generater)三部分组成。
词法分析器:将源代码序列化为Token数据结构对象。
语法分析器:将Token数据对象进一步序列化为抽象语法树(AST)数据结构对象。
代码生成器:将抽象语法树数据对象序列化为目标代码。
一分钟图文并茂的编译器原理介绍:https://www.bilibili.com/video/BV1Tc411h7rj?is_story_h5=false&p=1&share_from=ugc&share_medium=ipad&share_plat=ios&share_source=WEIXIN&share_tag=s_i&timestamp=1663335535&unique_k=ztfqvLf&vd_source=06969d50da2a83309a5fc7fd4dcc4d73

项目介绍

项目的目标就是简化编译器的概念,并实现一个将类似 LISP 函数调用的源语言编译成类似 C 函数调用的目标语言的编译器。
项目源码地址:https://github.com/Define2017/the_super_tiny_compiler/tree/main

实现的编译效果如下:

源语言 LISP   =======>    目标语言 C
(add 2 2)                 add(2, 2)
(subtract 4 2)            subtract(4, 2)
(add 2 (subtract 4 2))    add(2, subtract(4, 2))

以(add 2 (subtract 4 2))的编译过程为例,详细编译过程如下:

词法分析器过程:

LISP       ===========>   Token
(add 2 (subtract 4 2))    [
                             { type: 'Parent', value: '('        },
                             { type: 'Name',   value: 'add'      },
                             { type: 'Number', value: '2'        },
                             { type: 'Parent', value: '('        },
                             { type: 'Name',   value: 'subtract' },
                             { type: 'Number', value: '4'        },
                             { type: 'Number', value: '2'        },
                             { type: 'Parent', value: ')'        },
                             { type: 'Parent', value: ')'        },
                          ]

**算法:**就是逐字符的扫描源码,将一组满足设定Token结构的字符放入Token数据对象中。这里将左右括号分别识别为一个Parent类型的token,将add 、subtract识别为Name类型的token,将数字识别为Number类型的token,虽然例子没有涉及到字符和字符串,但是代码实现上也有考虑,将字符、字符串分别识别为Char、Str类型的token。这个规则不是唯一的,可以自己定义Token的结构,然后实现代码。这里Token类型的种类就是对源语言的关键字、标识符、特殊字符、字面量值作分类。

语法分析器过程:

Token          ========================>      AST
[                                             {
   { type: 'Parent', value: '('        },       type: 'Program',
   { type: 'Name',   value: 'add'      },           body: [{
   { type: 'Number', value: '2'        },             type: 'CallExpression',
   { type: 'Parent', value: '('        },             name: 'add',
   { type: 'Name',   value: 'subtract' },             params: [{
   { type: 'Number', value: '4'        },               type: 'NumberLiteral',
   { type: 'Number', value: '2'        },               value: '2',
   { type: 'Parent', value: ')'        },               }, {
   { type: 'Parent', value: ')'        },               type: 'CallExpression',
]                                                       name: 'subtract',
                                                        params: [{
                                                          type: 'NumberLiteral',
                                                          value: '4',
                                                          }, {
                                                          type: 'NumberLiteral',
                                                          value: '2',
                                                        }]
                                                      }]
                                                    }]
                                              }

**算法:**首先增加了一个类型为Program的父节点用来表示程序,程序的主体部分是从Token数据对象中序列化。对Token中类型为Parent的一组左右括号识别为表达式,表达式由类型、名称、参数表组成。参数有两种类型一种是字面量(数值、字符),另一种是表达式。由于表达式中会嵌套表达式作为参数,所以实现时使用了递归方式来解析表达式。递归是常用的方式实现和理解上比较清晰、简单、容易,算法能力强可以考虑循环。

代码生成器过程:

AST         ========================>    destinate code
{                                        add(2, subtract(4, 2))\n
  type: 'Program',
      body: [{
        type: 'CallExpression',
        name: 'add',
        params: [{
          type: 'NumberLiteral',
          value: '2',
          }, {
          type: 'CallExpression',
          name: 'subtract',
          params: [{
            type: 'NumberLiteral',
            value: '4',
            }, {
            type: 'NumberLiteral',
            value: '2',
          }]
        }]
      }]
}

**算法:**代码生成过程与语法解析过程相似,根据抽象语法树的内容逐步生成目标代码字符串,程序主体中多个表达式之间用换行符\n分割。表达式参数之间用逗号分割。由于表达式中会嵌套表达式,所以代码生成器同语法分析器一样使用了递归来生成表达式。

 类似资料: