类C微小编译器的设计与实现-2016-5-20

类C微小编译器的设计与实现

摘要

随着计算机的广泛应用，计算机编程语言从早期的机器语言到汇编语言进行不断地演进，以及到现在的各种高级语言的形态。

编译器技术是计算机技术发展的基石，同时也是进展速度最快的计算机科学，这个分支已经进行了几十年的研究，形成了非常成熟的体系，编译器的设计集中体现了计算机的本质和发展的成果。

其核心思想是在机器语言和算法的逻辑结构转换从一种基础到另一种代表语言的过程。最终形成高级别语言，甚至在高级语言上的虚拟平台上运行的机器语言，并且以硬件的机器指令实现，以上所述的改造涉及到的编译器技术的应用。本系统采用Go作为编程语言。介绍了开发的相关内容，完成的功能，以及实现的记录。着重解释了一些编写编译器的关键点和技术要点和理论。

关键词: 编译技术，编程程序，高级语言

第一节 绪论

1.1 开发背景

在计算机技术与科学的迅猛发展下, 计算技术应用在了非常广泛的领域当中, 相当的计算机应用层出不穷，极大地丰富了我们的生活，学习和工作。与此同时, 也有许多用于编写高级应用的编程语言作为支撑，才得以构建非常复杂的系统和架构。

程序设计是一门艺术，设计者通过特定语言的编译器将源代码翻译为体系结构相关的目标程序,，从而能够最终达到程序执行的目的,，一个好的程序语言要满足工程的需要也要搭配良好的语法设计。从 20 世纪 60 年代开始，编译器的设计就是计算机科学技术发展和研发中的一个热门主题。虽然编译器设计的历史很长,作为计算机技术来说相对成熟，编译器还是一个由高级抽象的源代码向计算机机器指令转换的高效映射工具，随着电脑软硬件水平的不断提高，编译器的设计也在不断地变化，目标机体系结构也在不断地改进，软件越来越复杂，其规模也越来越大。编译器设计问题在高级层次上大致稳定，例如面向对象语言，面向过程语言，函数语言都在各自的领域发挥着重要的作用，并且每个领域的研究都有着非常积极的意义，不同领域相互学习，相互弥补，并且结合工业界的积累，不断自我完善，从一个抽象的计算机科学问题，逐渐变成了一个计算机工业界不断追求和寻找优化的目标，大公司对于编程语言的要求非常高，因为一个良好的编程语言能很大的提高程序员的工作效率，良好的程序组织结构也能保证项目的可重用性，这样实际生产中的工程能够保证高效和稳定。当我们深入其内部研究编译器时会不断明白，编译器的内部结构同样也在顺应着需求一直在变化。此外，由于我们能够提供给编译器本身的计算资源，例如内存等，也在不断增加。所以，现代编译器可以采用比以前更加复杂的算法，却又不会损失过多的时间。除此之外，编译器前后端分离，能够提供一种更加合理的方式，把编程过程解耦，比如在编辑时就主动触发前端语法分析的过程，检查语法错误，而不需要等到最后编译的时候进行，或者通过解析条件自动生成代码，减少开发的工作量，很多编译“前端”技术,如文法、正则表达式、语法分析器以及语法制导翻译器等，仍然被广泛使用。

1.2 开发的目标和意义

GCC的复杂程度基本上可以和Linux操作系统比肩，代码量，工程量非常之大，是世界各地的优秀工程师合力通过版本控制系统贡献开发的，单凭一个人很难做到这样规模的编译器，所以编写甚至读懂这样的一个GCC的编译器是一件非常困难的事情。很多的计算机专业的同学从来没有编写过一个完整的编译器，但是，几乎任何程序都和编译器有关，而且任何一个软件工程师都应该知晓编译技术的基本结构和原理。编译设计的原理和技术还可以用于编译器设计之外的众多领域。因此,这些原理和技术会在工程实践中被反复使用。研究编译器的实现和设计程序语言、体系结构、算法和软件工程。编译器的设计从本质上来说是一项工程，它所使用的方法必须很好地解决现实中出现的各种解释逻辑(即用真实的语言编译且在真实的机器上能够执行的程序)。在一般情况下，开发编译器的人必须面对机器结构，很少能够去改善设计。在开发过程中做什么样的分析和转换，以及什么时候去做，这些都是工程上的选择，但正是这些选择决定了一个编译器的性能高低。本实验就建立在一个自主开发的微型编译器基础之上的，该编译器虽然功能类似于C语言这样的经典编译器，但是缺少必要的标准库和完整的实现，但也已经完全具备了一个编译器应有的所有特征。虽然本实验只是一个规模很小的微型编译器的开发，作为一次较为完整的编译开发实践，它已经足够透彻地了解一个编译器开发过程，又能更深刻地理解和运用编译开发过程中的众多技术和方法，并能在此基础上针对编译器的优化展开深入的讨论，这些对于自己以后的研究和发展方向将起到非常大的推动作用。

1.3 编译原理的发展情况

在编译器原理的进化历程里，提高编译的效率始终是编译器专家挖掘的领域之一，编译效率指的是根据编译器产生的目标代码的时间指标和空间指标的代价决定的效率，所以编译优化要围绕时间和空间这两个方面来实施。在编译时针对过程进行优化的技术有很多，它们通常是通过搜集源代码或中间代码的特定信息，然后利用这些元素对代码中的源代码组织结构或算法模型等实施等价的改进变换，从而致力于在时间效率和空间效率上达到一个比较理想的效果。编译器的设计者们一直想要能够将各种代码优化技术充分地运用在自己的语言设计中，但往往并不是尽如人意。本编译器开发过程中，虽然没有运用到非常优化的代码，但通过本实验的进行，在现有开发的编译器基础之上，能够在后续的开发中逐渐地提高程序的编译效率，对于自己以后的研究和发展方向将起到充分的促进效果。这正是本实验的研究意义所在。本实验是以微型编译器的项目开发为基础，该项目的开发目标是自定义一种高级语言，然后编码实现出语言的编译器，完成将语言源程序翻译为基于虚拟机的目标代码的任务，这是这个实验的应用目标。编程语言的开发具有极高的工程价值和应用意义，高级语言编译器的性能决定了基于该语言应用所能表现的质量。所以国际上很多的科研和技术人员也在积极地开展这方面的技术探索和项目实践。大多是以特定的工程项目为前提来进行一些与编程语言设计相关或类似的项目分析，研究目标大多是基于某种实验型高级语言的编译器开发和优化改进，然后把有价值的研究成果移植或运用到工业级级的编译器开发中，最近十年以来,国外关于编译器设计的发展动态主要体现在：编译器采用了更加复杂的算法，主要用于推演或压缩程序中的元信息，这又与更为复杂的程序设计语言的发展结合在一起，其中典型的有用于函数语言编译的 Hindley-Milner 类型检查的统一算法 (!!这里有个引用原文2的引用) 。

在九十年代,作为GNU项目或其它开放源代码项目的子项目GCC为基础，许多开源的编译器或构造工具被发布了。这些工具可用来编译程序语言的源程序。它们中的一些项目被认为是非常优秀的，而且对现代编译理论感兴趣的人都可以轻松地得到它们的免费源代码。比如

Clang[2]设计时比GCC编译过程中保留更多的信息，保留原始代码的整体形式。这样做的目的是使其更容易将映射误差引入原始源。通过Clang提供的错误报告的目的还在于要更加详细和具体的错误提示，所以可以在IDE编译参数的输出中体现。编译器的模块化设计可以提供源代码索引，语法检查，以及其他功能通常与快速应用开发系统相关。解析树也更适合于自动化配套代码重构，因为它直接代表着原始的源代码。

第二节 理论基础

2.1.1 编译器系统概述

编译器是一个计算机程序（或一组程序），从编写的编程语言（源语言）到另一个计算机语言（目标语言）的源代码的转化程序，而后者往往具有称为对象代码二进制形式。“编译”主要用于从一个高级语言到较低水平的语言翻译源代码的程序（例如，汇编语言或机器代码）。如果编译程序可以在不同CPU或操作系统上编译运行，则编译器被称为跨平台的编译。编译器从某种程度上说是一种翻译器。虽然这个过程这需要一套编程规范，并翻译它们，即所有程序创建的目标来执行这些中准则，在技术上“编译”意味着，从编译器生成一个独立的可执行程序（即可能需要运行时间库或子系统来支持的程序），如果仅执行原规格编译器通常被称作“解释器”，因为不同的分析对于编译和解释之间是有区别的，在这两个词之间有一些重叠的方法，但是编译更倾向于生成二进制文件而解析则仅仅是对源代码进行翻译并且进行动态执行。

从低水平的语言向更高一级翻译的程序是反汇编。高层次的语言之间转换的程序通常被称为一个源到源的编译器。语言重写通常是翻译表达的形式。编译器编译有时用来指一个解析器生成器，经常被用来帮助创建词法和语法分析器的工具。编译器很可能要进行以下操作：词法分析，预处理，解析，语义分析（语法制导翻译），代码生成和代码优化。

2.1.2 编译器的产生历史

早期计算机的软件主要是用汇编语言编写。虽然第一个高级语言产生时用着几乎一样古老的电脑，导致了在设计编译器时最大的技术挑战是早期的计算机有限的内存容量。第一个高级语言（Plankalkül）于1943年提出，是康拉德楚泽发明，在1952年，则为A-0编程语言;在A-0运作更象是一个装载机或连接器，不太接近现代的编译器。第一个编译器被阿利克Glennie于1952年实现了，当时在曼彻斯特大学的一台电脑上，被一些人认为是第一个编译的编程语言。IBM由约翰·巴科斯领导的FORTRAN团队一般被作为在1957年诞生的COBOL的第一个完整的编译器的作者，该编译器能够在多个架构上进行编译，在1960年在许多应用领域使用更高级别语言的想法很快就流行起来。因为新的编程语言支持的扩展功能和计算机体系结构的日益复杂，编译器变得更加复杂。早期的编译器是用汇编语言编写。第一个自举的编译器 - 能够编译自己的源代码的语言 - 是在1962年由蒂姆·哈特和麦克·莱文在麻省理工学院，用Lisp创建的。自1970年以来这已成为实现编译器一个常见的做法。虽然两者Pascal和C一直是实现语言流行的选择的语言。构建自举的编译器是一个非常重要的问题，第一个这样的编译器的语言必须通过用其他语言实现最初版本的编译器。

2.2 编译器的结构

高级语言编译器是源程序与底层硬件交互的桥梁。编译器验证代码语法，生成高效的目标代码，运行时的组织，并格式化根据汇编器和链接约定的输出。编译器包括：

前端：验证的语法和语义，以及由中间端产生用于处理的源代码的中间表示。执行信息收集对类型进行检查，产生错误和警告。前端的方面包括词法分析，语法分析和语义分析。 中间端：进行优化，包括去除无用的或无法访问的代码，发现常量传播，计算迁移不太频繁执行的地方（例如，跳出了一条循环）。

后端：生成汇编代码，在执行过程中进行寄存器分配。梳理如何并行执行以及整理执行单元，优化硬件的目标代码的应用（对于程序变量在可能的情况下分配处理器寄存器）。

2.3.1 编译器的组织

在早期，编译器采取的设计方法复杂性受过往经验和消耗资源的影响。这种通过一个人写一个比较简单的语言编译器可能是一个单一的，整体的软件。当源语言变得庞大而复杂后，高品质的输出是必需的，该设计可被分成若干相对独立的模块。具有单独的阶段意味着开发任务可以被分配成小部分，并给予不同的人来完成。通过改进替换的独立的模块也变得容易得多。编译过程阶段的划分是由生产质量编译器编译器项目（PQCC）在卡内基 - 梅隆大学的拥护。该项目推出了前端，中端和后端的划分。一般之后有前后端。然而，中间端通常被认为是前端或后端的一部分。在这两个平衡点之间取舍是公开议题。前端通常被认为在句法和语义处理发生时进行的处理，与翻译一起表示的较低的水平（低于源代码）。

中间端通常被设计为比源代码或机器代码以外的形式执行并优化。与源代码/机器代码独立，目的是使能够支持不同的语言和目标处理器的编译器版本之间共享通用的优化。后端需要从中间端输出。它可以执行的是针对特定计算机进行的更多的分析，转换和优化。然后，它为特定的处理器和操作系统生成代码。该前端/中间/后端的方法使得有可能结合用于与不同语言前端为不同的CPU绑定特定汇编语言。这种方法的实际例子是GNU编译器，LLVM[3]，其中有多个前端和多种后端。

通过分遍次数分类的编译器有其计算机的硬件资源有限的原因。编译涉及执行大量的工作和早期计算机没有足够的内存来包含所有做这项工作的一个程序。所以编译器被分裂成执行某些独立子功能的分析和翻译的方案，其中每个由前一个传过来的源（或它的某种表示）作为输入。在单次通过编译的能力已被看作是一个有益的过程，简化了的编译器和一个通用编译器通常执行编译比多遍编译器更快的工作。因此，在早期系统的资源限制带动下，许多早期的语言是专门设计，使他们能够在同一路径上进行编译。在一些情况下，语言功能的设计可能需要编译器执行一个以上的传过来的源。例如，声明出现在其引用出现的后面。在这种情况下，语句的翻译源代码，第一遍需要收集有关报表后出现的申明信息，他们的影响，与实际发生的翻译在随后的遍历中通过。单次通过编译的缺点是它不可能执行许多高质量的代码所需要的复杂的优化。它难以控制优化编译器。举例来说，优化的不同阶段可以分析一个表达很多次，但只有一次分析生成另一种表达。拆分编译成小的程序是生产可证明正确的编译器研究人员使用的技术。证明了一组小程序的正确性往往需要比证明一个更大的，单一的程序的正确性更省力。而典型的多遍编译器从它的最终道输出机器代码，还有其他几种类型：“源到源的编译器”是一种编译器，需要一个高级语言作为其输入和输出语言。例如，自动并行化编译器会经常把一个高级语言程序作为输入，然后转换代码和并行代码的注释或语言结构对其进行批注。编译器编译为一个理论机器的汇编语言，像一些虚拟机的实现，针对Java，Python和更多的字节码编译器也都是这样的类型。应用程序在字节码上的编译是编译为机器码在执行之前的隔离层。

2.3.2 编译器前端

编译器前端通过分析源代码来构建程序，称为中间表示。它还管理符号表，数据结构在源

代码相关的映射信息，如位置，类型和符号。而前端可以是一个单一的整体功能或程序，如在无扫描的解析器中，只要主要实现分析的几个阶段，其可以顺序地或并发执行。特别是对于良好的工程来说：模块化和关注点分离。

词法上，语法分析和语义分析。文法的解析包括句法分析（分别为记号的语法和表达式的语法），并在一半情况下，这些模块（词法分析器和解析器）可从该语言语法自动生成，但在更复杂的情况下，这些需要手动修改或手写。词法文法和短语语法通常上下文无关文法，能显著简化分析，在语义分析阶段处理上下文的灵敏度上更有优势。语义分析阶段一般是更复杂的，并用手写的，但可使用语法被部分或完全自动化。这些阶段本身可以进一步细分 - 词法扫描和评估，作为解析首先建立一个具体语法树（解析树），然后将其转变成一个抽象语法树。

在一些情况下有附加的阶段被使用，特别是线性重建和预处理的时候，但这些比较少见的。可能的阶段的详细清单，包括：

行改造，关键字或允许任意空间内标识需要分析的预处理阶段，输入字符序列转换为规范的形式准备提供给解析器语言。自上而下，递归下降，在20世纪60年代使用的表驱动的解析器通常一次读取源一个字符，并不需要一个单独的标记化阶段。

词法分析分割了源代码文本并切成独立的词法记号。每个记号是语言的单个原子单位，比如关键字，标识符或符号名称。记号语法是典型的常规语言，所以来自正则表达式构成的有限状态自动机可以被用来识别它。此阶段也被称为词法分析或扫描过程，而软件操作的词法分析被称为词分器或扫描器。这可能不是一个单独的步骤 - 它可以在解析步骤中无扫描解析，在这种情况下的解析是在字符级别，而不是记号级别进行组合的。

有些语言，像C一样需要支持宏替换和条件编译预处理阶段。通常情况下，预处理阶段之前，语法和语义分析就会发生，预处理器操纵词法标记，而不是语法形式。然而，有些语言，支持基于语法形式宏替换。

语法分析包括解析词法记号序列来识别程序的语法结构。此阶段通常生成解析树，根据一个正式的语法限定的语言规则建立的树结构替换记号的线性序列。解析树通常由以后的阶段改变。

语义分析是编译器增加了语义信息来解析解析树并建立符号表的位置。此阶段进行语义检查，如类型检查（检查类型错误），或对象绑定（变量和函数引用与他们的定义关联），或明确赋值（要求所有本地变量在使用前进行初始化），拒绝不正确的代码或发出警告。语义分析通常需要一个完整的分析树，这意味着该逻辑下解析阶段的过程中，在逻辑上早于代码生成阶段，虽然它通常可以将多个过程折叠成一个通过在一编译器实现的代码。

2.3.3 编译器后端

编译器后端这个术语常常和生成汇编代码的功能重叠，有时与代码生成器混淆。所以使用中端区分通用的分析和优化阶段和机器相关的代码生成器的后端。

后端的主要阶段包括如下几点：

分析：这是根据从输入的中间表示信息进行收集的过程，数据流分析是用来建立定义的工具链的，具有相关性分析，别名分析，指针分析，逃逸分析等精确分析，为编译器优化的基础。调用图和控制流图也常常在分析阶段建成。

优化：中间语言表示被变换成功，并转化成速度更快的形式。大多数优化是内联展开，无效代码消除，常量传播，循环转换，寄存器分配，甚至自动并行化等。

代码生成：转化的中间语言被翻译成输出语言，通常是该系统的本机语言。这涉及到资源和存储决策，比如决定以适合哪些变量及其相关寻址模式以及寄存器和适当的机器指令和内存的选择和调度。调试数据也可能需要产生。

编译器分析为任何编译器优化的前提，之间紧密地进行工作。例如，相关分析是循环转换的关键。此外，编译器分析优化的范围相差很大，从小到基本块的程序/功能水平，甚至在整个程序（间优化）。编译器可能会做用更广阔的工作。但是，丰富的功能是不是无条件的：大范围的分析和优化是在编译时间和存储空间方面造成昂贵的开销，分析和优化尤其如此。

2.3.4 编译器错误处理

编译器错误处理单独提出的一个很重要的原因是，在编译器设计的过程中，错误处理是一个很容易忽视的过程，因为大部分编程语言的错误提示并不友好。编译器的正确性是软件工程与一个编译器语言规范行为的一个分支。包括使用形式化方法开发编译器和使用现有的编译器进行严格的测试（通常被称为编译器验证）。

第三节 编译器的实现

3.1 语言定义标准

运算符

基本上的操作符都支持，且操作符优先级相同。包括：

* '+'、'-'、'*'、'/'、'%'、'=' * '^'、'&'、'&^'、'|'、'<<'、'>>'

* '+='、'-='、'*='、'/='、'%='、'++'、'--' * '^='、'&='、'&^='、'|='、'<<='、'>>='

* '!'、'>='、'<='、'>'、'<'、'=='、'!='、'&&'、'||' * '<-'

类型

原理上支持所有的类型。典型的有：

* 基本类型：int、float、string、byte、bool、var（类似于C的union）。 * 复合类型：slice、map、chan

* 用户自定义：函数（闭包）、类成员函数、类

常量

* 布尔类型：true、false（由 builtin 模块支持） * var 类型：nil（由 builtin 模块支持）

* 浮点类型：pi、e、phi （由 math 模块支持）

变量及初始化

基本的有

a = 1 // 创建一个 int 类型变量，并初始化为 1 b = \类型 c = true // bool 类型 d = 1.0 // float 类型 e = 'h' // byte 类型

string 类型

a = \

string有如下内置操作：

a = \为字符串连接操作符 n = len(a) // 取 a 字符串的长度

b = a[1] // 取 a 字符串的某个字符，得到的 b 是 byte 类型 c = a[1:4] // 取子字符串

slice 类型

a = [1, 2, 3] // 创建一个 int slice，并初始化为 [1, 2, 3] b = [1, 2.3, 5] // 创建一个 float slice c = [\创建一个 string slice

d = [\创建一个 var slice (等价于 Go 语言的 []interface{})

e = mkslice(\创建一个 int slice，并将长度设置为 len，容量设置为 cap f = mkslice(type(e), len, cap) // 创建一个 int slice 的 slice，也就是 Go 语言里面的 [][]int

slice有如下内置的操作：

a = append(a, 4, 5, 6) // 含义与 Go 语言完全一致 n = len(a) // 取 a 的元素个数 m = cap(a) // 取 slice a 的容量

b1 = b[2] // 取 b 这个 slice 中 index=2 的元素

b[2] = 888 // 设置 b 这个 slice 中 index=2 的元素值为 888

b[1], b[2], b[3] = 777, 888, 999 // 设置 b 这个 slice 中 index=1, 2, 3 的三个元素值 b2 = b[1:4] // 取子slice

特别地，可以这样赋值：

x, y, z = [1, 2, 3]

结果是 x = 1, y = 2, z = 3。这是基础设计导致的：

map 类型

a = {\得到 map[string]int 类型的对象

b = {\得到 map[string]float64 类型的对象 c = {1: \得到 map[int]string 类型的对象

d = {\得到 map[string]interface{} 类型的对象 e = mkmap(\创建一个空的 map[string]int 类型的对象

f = mkmap(mapOf(\创建一个 map[string]map[string]int 类型的对象

map类型有如下操作

n = len(a) // 取 a 的元素个数

x = a[\取 a map 中 key 为 \的元素

x = a.b // 含义同上，但如果 \元素不存在会 panic a[\同 Go 语言

a.e, a.f, a.g = 4, 5, 6 // 含义同 a[\delete(a, \删除 a map 中的 \元素

需要注意的是，a[\的行为常见的范式是：

x = {\

a = x[\结果：a = 1

if a != undefined { // 判断a存在的逻辑 ... }

c = x[\结果：c = undefined，注意不是0，也不是nil d = x[\结果：d = undefined，注意不是0，也不是nil

chan 类型

ch1 = mkchan(\得到 buffer = 2 的 chan bool ch2 = mkchan(\得到 buffer = 0 的 chan int

ch3 = mkchan(mapOf(\得到 buffer = 0 的 chan map[string]chan int

chan 有如下内置的操作：

n = len(ch1) // 取得chan当前的元素个数 m = cap(ch1) // 取得chan的容量 ch1 <- true // 向chan发送一个值 v = <-ch1 // 从chan取出一个值

close(ch1) // 关闭chan，被关闭的chan是不能写，但是还可以读(直到已经写入的值全部被取完

为止)

需要注意的是，在 chan 被关闭后，<-ch 取得 undefined 值。所以应该这样：

v = <-ch1

if v != undefined { // 判断chan没有被关闭的逻辑 ... }

类型转换

自动类型转换

大部分情况下，不会自动类型转换。一些例外是：

* 如果一个函数接受的是 float，但是传入的是 int，会进行自动类型转换。

强制类型转换

a = int('a') // 强制将 byte 类型转为 int 类型 b = float(b) // 强制将 int 类型转为 float 类型 c = string('a') // 强制将 byte 类型转为 string 类型

流程控制

if 语句

if booleanExpr1 { // ...

} elif booleanExpr2 { // ...

} elif booleanExpr3 { // ... } else { // ... }

switch 语句

switch expr { case expr1: // ... case expr2: // ... default: // ... }

或者：

switch {

case booleanExpr1: // ...

case booleanExpr2: // ... default: // ... }

for 语句

for { // 无限循环，需要在中间 break 或 return 结束 ... }

for booleanExpr { // 类似很多语言的 while 循环 ... }

for initExpr; conditionExpr; stepExpr { ... }

典型例子：

for i = 0; i < 10; i++ { ... }

另外也支持 for..range 语法：

for range collectionExpr { // 其中 collectionExpr 可以是 slice, map 或 chan ... }

for index = range collectionExpr { ... }

for index, value = range collectionExpr { ... }

函数

函数和闭包

基本语法：

funcName = fn(arg1, arg2, argN) { //... return expr }

这就定义了一个名为 funcName 的函数。

本质上来说，函数只是和 1、\类似的一个值，只是值的类型是函数类型。

可以在一个函数中引用外层函数的变量。如：

x = fn(a) { b = 1 y = fn(t) { return b + t } return y(a) }

println(x(3)) // 结果为 4

但是如果你直接修改外层变量会报错：

x = fn(a) { b = 1 y = fn(t) { b = t // 这里会抛出异常，因为不能确定你是想定义一个新的 b 变量，还是要修改外层 x 函数的 b 变量 } y(a) return b }

如果你想修改外层变量，需要先引用它，如下：

x = fn(a) { b = 1 y = fn(t) { b; b = t // 现在正常了，我们知道你要修改外层的 b 变量 } y(a) return b }

println(x(3)) // 输出 3

不定参数

a = max(1.2, 3, 5, 6) // a 的值为 float 类型的 6 b = max(1, 3, 5, 6) // b 的值为 int 类型的 6

也可以自定义一个不定参数的函数，如：

x = fn(fmt, args...) { printf(fmt, args...) }

这样就得到了一个 x 函数，功能和内建的 printf 函数一模一样。

多赋值

x, y, z = [1, 2, 3.5] a, b, c = fn() { return [1, 2, 3.5] // 返回的是 float slice }()

需要注意的是，带上[]进行多赋值和不带[]进行多赋值在语义上有一点点不同。下面是例子：

x1, y1, z1 = 1, 2, 3.5 x2, y2, z2 = [1, 2, 3.5] println(type(x1), type(x2))

x1 的类型为 int，而 x2 的类型是 float。

defer

这在处理系统资源（如文件、锁等）释放场景非常有用。一个典型场景：

f, err = os.open(fname) if err != nil { // 做些出错处理 return }

defer f.close()

// 正常操作这个 f 文件 类

一个用户自定义类型的基本语法如下：

Foo = class { fn setAB(a, b) { this.a, this.b = a, b } fn getA() { return this.a } }

有了这个 class Foo，我们就可以创建 Foo 类型的 object 了：

foo = new Foo

foo.setAB(3, \a = foo.getA() println(a) // 输出 3

构造函数

构造函数只是一个名为 _init 的成员方法（method）：

Foo = class { fn _init(a, b) { this.a, this.b = a, b } }

有了这个 class Foo 后，我们 new Foo 时就必须携带2个构造参数了：

foo = new Foo(3, \println(foo.a) // 输出 3

include语法

一个文件可以通过 include 文法来将另一个文件的内容包含进来。所谓包含，其实际的能力类似于将代码拷贝粘贴过来。例如，在某个目录下有 a 和 b 两个文件。

其中 a 内容如下：

println(\

foo = fn() { println(\}

其中 b 内容如下：

a = 1 b = 2

include \

println(\foo()

模块及 import

模块(module)是一个目录，该目录下要求有一个名为 main 的文件。模块中的标识(ident)默认都是私有的。想要导出一个标识(ident)，需要用 export 语法。例如：

a = 1 b = 2

println(\

f = fn() { println(\}

export a, f

这个模块导出了两个标识(ident)：整型变量 a 和 函数 f。

要引用这个模块，我们需要用 import 文法：

import \

import \

bar.a = 100 // 将 bar.a 值设置为 100

println(bar.a, bar2.a) // bar.a, bar2.a 的值现在都是 100

bar.f()

将一个模块 import 多次并不会出现什么问题，事实上第二次导入不会发生什么，只是增加了一个别名。

include 和 import 的区别

include 是拷贝粘贴，比较适合用于模块内的内容组织。比如一个模块比较复杂，则可以用 include 语句分解到多个文件中。它永远基于 `__dir__`(即 include 代码所在脚本的目录) 来定位文件。

import 是模块引用，适合用于作为业务分解的主要方式。

反射

在任何时候，你都可以用 type 函数来查看一个变量的实际类型，如：

t1 = type(1)

t2 = type(fn() {})

我们得到了 *Function。这说明尽管用户自定义的函数原型多样,即使定义多种多样但是类型是一致的。

我们也可以看看用户自定义的类型：

Foo = class { fn f() {} } t1 = type(Foo) t2 = type(Foo.f)

foo = new Foo t3 = type(foo) t4 = type(foo.f)

可以看到，class Foo 的类型是 *Class，而 object foo 的类型是 *Object。而 Foo.f 和普通用户自定义函数一致，也是 *Function，但 foo.f 不一样，它是 *Method 类型。

样例代码,求最大素数

输入 n，求 < n 的最大素数。用法：

primes = [2, 3] n = 1 limit = 9

isPrime = fn(v) { for i = 0; i < n; i++ { if v % primes[i] == 0 { return false } } return true }

listPrimes = fn(max) { v = 5

for { for v < limit { if isPrime(v) { primes = append(primes, v) if v * v >= max { return } } v += 2 } v += 2 n; n++ limit = primes[n] * primes[n] } }

maxPrimeOf = fn(max) { if max % 2 == 0 { max-- } listPrimes(max) n; n = len(primes) for { if isPrime(max) { return max } max -= 2 } } //

if len(os.args) < 2 { fprintln(os.stderr, \ return }

max, err = strconv.parseInt(os.args[1], 10, 64) if err != nil { fprintln(os.stderr, err) return 1 } max--

v = maxPrimeOf(max) println(v)

3.2 词法分析

在计算机科学中，词法分析是字符（如在计算机程序或网页）的序列变换为标记（具有确定的字符串）序列的过程。这样的词法通常与一个分析器相关，它们分析的编程语言，网页的语法，等等结合。词法分析一般是编译器的第一部分，而且词法分析很简单,就是一个有限状态机。

开始词法分析的过程就是把源文件转换成一组预先定义好的token的过程。这一组被统一表现的token之后会被送入语法分析器进行语法解析，这里我们主要关注如何进行词法分析。

做词法分析就几种方法: 1. 直接使用工具比如lex。

2. 使用更低一层的正则表达式。 3. 使用状态动作,构造一个状态机。

而真正实现一个语言的话，使用工具没有什么错，但是问题是，很难获得正确的错误提示。工具生成的错误处理很弱，而且需要学习另一门规则或特定的语法，生成的代码可能性能不好，难以优化，但是用工具可以非常简单实现词法分析。早期编译器的设计阶段都会使用lex来做词法分析器，比如gcc就是这么做的，但是到了后期一个真正生产化的语言可能不能依赖生成的代码，而需要做自己特定的修改和优化，所以自己实现一个词法分析器就显得比较重要了。

正则表达被人诟病的一个话题就是效率问题，比如perl拥有功能最强大的正则表达式，但是整个正则表达式引擎的效率却很低，C在这方面牺牲了一些正则表达式的特性来保证正则表达式的效率不至于过低，但是正则表达式对于大量文本处理体现的弱势却是很明显的。因为可能我们要处理的状态其实不需要一个繁重的正则表达来解决。其实实现一个词法分析器很简单,而且这种技能是基本不会变的，如果写过一次，以后都是同样的实现方式。

词法记号是代表一个语义明确且表示其分类的结构。词法记号的类别的实例可以包括“识别符”和“整数文字”等，词法记号类别不同的编程语言会不同。从字符输入流形成记号的过程被称为记号化。比如说语句“sum = 3 + 2;”可以表示为，标识符sum+赋值符+整数3+符号\整数2+分号的一个记号流。

本项目中使用的词法分析器是tpl，类似于yacc的一个词法分析器。TPL 全称是Text Processing Language（文本处理语言）。

3.2.1 TPL实现原理

3.2.1.1 token化

首先要定义`token`

type Token int

其实就是个枚举类型，对于每种类型的字面值都有对应的token。实际上这个只能算是一个token的类型。

首先枚举所有可以碰到的token类型，然后是关于token位置的定义。

// Position 表示的是源文件当中某个记号的位置 type Position struct {

Filename string // filename, if any Offset int // offset, starting at 0

Line int // line number, starting at 1

Column int // column number, starting at 1 (byte count) } ```

这个很简单就是标示在文件中的位置,Pos的定义 type Pos int 是位置标示的紧凑表示.接下来看看Pos和Position之间是如何转换的.

首先定义了一个 FileSet，可以理解为把 File 的内容字节按顺序存放的一个大数组，而某个文件则属于数组的一个区间[base,base+size]中，base是文件的第一个字节在大数组中的位置，size是这个文件的大小，某个文件中的 Pos 是在[base,base+size]这个区间里的一个下标。

最后 Pos 能够压缩成一个整数来表示一个文件当中的位置，当需要使用的使用再从 FileSet 中转换出完整的 Position 对象。

所以整个token包只是对token的一些定义和转化，词法分析的部分在scanner当中。

scan的主流程如下，主体是一个switch case表示的状态机，比如碰到字符那么扫描到不为字符为止，就作为一个标识符，比如碰到数字那么可能按照扫描数字，然后向后看一次小数字再扫描数字，直到没有数字为止。

scan每次会返回一个被扫描的token，压缩表示的位置，和字面值的字符串,这样就能够把一个源文件转化成一个token的记号流，也就是tokenize或者lexical analysis的过程。下面是scan的主体：

func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string) { scanAgain:

s.skipWhitespace() // current token start pos = s.file.Pos(s.offset) // determine token value insertSemi := false switch ch := s.ch; { /* 字符开头,开始扫描标识符 */ case isLetter(ch):

lit = s.scanIdentifier() if len(lit) > 1 {

// keywords are longer than one letter - avoid lookup otherwise tok = token.Lookup(lit) switch tok {

case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:

insertSemi = true } } else {

insertSemi = true tok = token.IDENT } /* 数字开头,扫描数字 */ case '0' <= ch && ch <= '9': insertSemi = true

tok, lit = s.scanNumber(false) default: // 省略

看一下的例子

func ExampleScanner_Scan() { // 需要记号化的源文件

src := []byte(\

// 初始化scanner var s scanner.Scanner

fset := token.NewFileSet() // 添加到文件集合中

file := fset.AddFile(\ // 初始化scanner

s.Init(file, src, nil /* no error handler */, scanner.ScanComments) // 不断获取需要得到的字符记号 for {

pos, tok, lit := s.Scan() if tok == token.EOF { break }

fmt.Printf(\ } // 不断扫描就能得到如下结果 // 词法分析就是做这样一件事情. // output:

// 1:1 IDENT \ // 1:4 ( \

// 1:5 IDENT \ // 1:6 ) \ // 1:8 + \

// 1:10 IMAG \ // 1:12 * \

// 1:13 IDENT \ // 1:16 ( \

// 1:17 IDENT \ // 1:18 ) \ // 1:20 ; \

// 1:20 COMMENT \}

3.2.1.2 匹配规则

TPL 是独创实现的文本处理引擎，把文本处理分为了两个阶段。和Yacc不同的是，实现简单，生成的代码本身也是自顶向下的递归解析，方便手动改造。

基本独立token的匹配规则的表示方式又分为以下几类：

* TOKEN：通常以全大些的字母表达，如：

IDENT、INT、FLOAT、IMAG、STRING、CHAR、COMMENT 等。

* 单字符操作符：如：'+'、'-'、'*'、'/' 等等。这些其实也可以用上面 TOKEN 形式表达，只是不那么直观。如 '+' 可以用 `ADD`，'-' 可以用 `SUB` 等等。

* 多字符操作符：如: \、\、\、\等等。这些其实也可以用上面 TOKEN 形式表达，只是不那么直观。\可以用 `INC`，\可以用 `ADD_ASSIGN` 等等。

* 关键字：如：\、\、\等等。TPL 内建的 AutoKwScanner 可以自动识别语言的关键字。其原理是，只要在 TPL 文法中出现了满足 `'\形式的规则，那么就认为里面 IDENT 就是一个关键字。

特殊token 的匹配规则

* `EOF`：即 tpl 中的 `GrEOF` 规则。不匹配任何内容，但是可用于判断当前是否已经匹配完整个 token 序列。

* `1`：即 tpl 中的 `GrTrue` 规则。不匹配任何内容，无论如何永远匹配成功。

复合规则

* `*G`: 反复匹配规则 G，直到无法成功匹配为止。

* `+G`: 反复匹配规则 G，直到无法成功匹配为止。要求至少匹配成功1次。 * `?G`: 匹配规则 G 1次或0次。

* `@G`: 要求其后的文本满足规则 G。如果要匹配的文本满足规则 G，则匹配成功，但是不真匹配任何内容（相当于只是 peek 下后续的 token 序列，要匹配的文本的当前匹配位置不前进）。例如：`@'{'` 这样一段规则表示的含义是要求要匹配的后续文本应该以 { 开头。

* `~G`: 要求其后的文本不满足规则 G。如果要匹配的文本满足规则 G，则匹配失败；如果不满足 G，则匹配成功，但不匹配任何内容（相当于只是 peek 下后续的 token 序列，要匹配的文本的当前匹配位置不前进）。例如: `~'{'` 这样一段规则表示的含义是要求要匹配的后续文本不能以 { 开头。

* `G1 G2 ... Gn`: 要求要匹配的文本满足规则序列 G1 G2 ... Gn。例如：`\表示要匹配的文本去除所有空白和注释后是 `fn()` 这样的文本。

* `G1 G2! ... Gn`: 可以在 G1 G2 ... Gn 中间的任何地方插入 ! 操纵符。它表示的意思是不可

回退，或者说快速失败（fail fast）。例如 `G1 G2! ... Gn` 表达的含义是，如果 G1 G2 匹配成功了，那么后续的 G3 ... Gn 必须匹配成功，如果不成功则直接结束整个匹配报告失败。善用 ! 操作符可以改善错误提示信息，因为通常这时候提示的错误更为准确。

* `G1 | G2 | ... | Gn` 要求要匹配的文本满足规则 G1 G2 ... Gn 中的任意一个。

* `G1 % G2`: 列表运算。从规则上来说等价于 `G1 *(G2 G1)`。比如 `IDENT % ','` 可以匹配 `abc`, `abc, defg, fhi` 这样的文本。

* `G1 %= G2`: 可选列表运算。从规则上来说等价于 `?(G1 % G2)`。和列表运算唯一差别是允许匹配的内容为空。

* `(G)`: 从规则上来说就是 G，只是改变运算的次序。详细见下“运算符优先级”。

运算符按优先次序，从高到低排序如下：

* `(G)`

* `*G`, `+G`, `?G`, `@G`, `~G`: 这些操作遵循右结合律，在最右边的运算优先。如：`~+G` 表示 `~(+G)`

* `G1 % G2`, `G1 %= G2` * `G1 G2! ... Gn` * `G1 | G2 | ... | Gn`

3.2.1.3动作和标记

动作(action) 是指规则匹配成功的情况下执行的代码。如下：

tpl.Action(G, func(tokens []tpl.Token, g tpl.Grammar) { ... })

这里的 func 就是动作(action)，整个表达式得到一个带动作的规则，使用上和一般的规则无异。

但在 TPL 文法的回调方式是标记(mark)。

标记的文法是这样的：

G/mark

这里 G 代表一个规则，而 mark 是一个合法的符号(IDENT)。在 TPL 文法中遇到标记(mark)时，TPL 编译器会产生一个回调(Marker)，交给业务方来处理这个标记。如下：

Marker := func(g tpl.Grammar, mark string) tpl.Grammar { ... }

Maker 概念上并不是动作。但是可以在 Maker 回调中生成相应的动作，并且通常你都在这样做。所以一般我们在沟通惯例上，会简单把标记(mark)和执行动作(action)等同起来。

通过定制 Marker，业务方就可以完成自己期望的业务逻辑。我们也有一些内建的 Marker 实

现，进一步简化大家的文本处理过程。例如，我们接下来要介绍的“解释器(interpreter)”。

使用 TPL 的范式如下：

import ( \)

// 定义要处理的文本内容对应的TPL文法 //

const grammar = ` ... `

func eval(text []byte, fname string) (..., err error) { defer func() { if e := recover(); e != nil { // 错误处理 return } }() marker := func(g tpl.Grammar, mark string) tpl.Grammar { ... } compiler := &tpl.Compiler{ Grammar: grammar, Marker: marker, } m, err := compiler.Cl() if err != nil { // 错误处理 return } err = m.MatchExactly(texr, fname) if err != nil { // 错误处理 return } // ... return } ```

TPL包含一系列的内置标记

_mute

`_mute` 是一个内建的标记(mark)。顾名思义，它有禁止发言(禁止执行动作)的意思。展开来说：

* 在第一次遇到 `_mute` 时，会禁用后续普通 mark 的执行，但 '_' 开头的 mark 不受影响。 * 后续如果再遇到 `_mute` 时，mute 引用计数++，当 mute 计数 > 1 时，所有非内建的 mark 都会禁止执行（包括 '_' 开头的）。

_unmute

`_unmute` 是一个内建的标记(mark)。它是 _mute 的反操作，执行 mute 引用计数-- 的行为。当 mute 计数减少到 0 时，所有 mark 回到正常执行状态。 _tr

_tr 是一个内建的标记(mark)。它是一个调试用的标记，它在规则匹配成功时，将规则所匹配的文本打印出来。

用户定义标记

解释器(interpreter) 在遇到用户定义标记时，会查找 fntable 得到对应的函数。例如，假设用户自定义标记叫 `add`，那么我们会到 fntable 中查找名为 `$add` 的函数。如果找到，则：

先通过反射查看函数的第一个参数。这分为 3 种情况：

1) 第一个参数是 interpreter.Stack 类型。会自动传入 interpreter 的 stack 实例。

2) 第一个参数是 interpreter.Interface 类型。会自动传入用户实现的 interpreter 实例。

3) 第一个参数是其他类型。

对于情形1和2，我们要求函数的参数只能是1个或2个，返回值要么没有，要么error类型。对于函数只有1个参数的情形，我们传入 stack 或 interpreter 实例然后调用之；对于函数有2个参数的情形，我们依据参数的类型分为如下几种情况：

* 参数为 interface{} 类型。这表示这个函数希望传入规则匹配到的 tokens 序列（tokens []tpl.Token）。

* 参数为 interpreter.Engine 类型。这表示这个函数希望传入解释器引擎(interpreter engine)。 * 参数为其他类型，这时也有两种情形。一种是 mark 以大写字母开头（或者以 _ + 大写字母开头开头），则表示函数接受的是 Grammar.Len()，通常是当规则为 *G、+G、?G、G1 % G2、G1 %= G2 时告知你准确的成功匹配次数，此时函数第二个参数必须是 int 类型。另一种情况是小写开头（或者以 _ + 小写字母开头），表示函数希望传入规则匹配到的 tokens 序列的第一个，也就是 tokens[0] 对应的值（可能会依据类型的不同进行自动的类型转换，比如如果参数为 float64，那么我们会自动调用 strconv.ParseFloat 完成转换）。

对于情形3，会自动根据所需的参数个数，从 stack 中弹出参数列表（通过调用 PopArgs），然

后调用该函数，把返回的结果压回 stack（通过调用 PushRet）。

TPL的处理本身也要符合TPL的文法，也就是说TPL本身是自举的，TPL本身的处理过程等价于

term = factor *( '%' factor/list | \ '/' IDENT/mark )

expr = +(term | '!'/nil)/and grammar = expr % '|'/or

doc = +((IDENT '=' grammar ';')/assign) factor = IDENT/ident | CHAR/gr | STRING/gr | INT/true | '*' factor/repeat0 | '+' factor/repeat1 | '?' factor/repeat01 | '~' factor/not | '@' factor/peek | '(' grammar ')'

3.3 语法分析

根据之前定义的词法分析器，我们定义了语言本身的词法规则生成语法。首先规定语法的特性就是微内核：语言的核心只有 1200 行代码。所有功能以可插拔的 module 方式提供。

每一种语言都会有一个定义良好的语法结构，函数是由申明和语句构成的，而语句又是由表达式构成的.经常用来描述语法的是BNF[5]。一门语言的设计其实就在这份描述当中，这是一门语言的语法和规则的定义，是应用程序员可以接触到的部分，而运行时却可以改变，这相当于和程序员约定的接口，只要按照这个接口编写源代码，就能产生正常可以编译的二进制文件，但是最后的二进制文件如何运行，对于每条语法转换成了什么，有什么优化都是编译器优化和运行时的工作。所以一门语言必须有一个详尽的描述，这和一个网络协议一样，是非常重要的部分。

语法分析的parser接受的输入是源文件，内嵌了一个scanner，最后把scanner生成的token变成一颗抽象语法树(AST)。

编译时的错误也是在这个时候报告的，但是大部分编译器编译时的错误系统并不是很完美，有时候报的错误文不对题，这主要是因为写对的方式有几种，但是写错的方式有很多种，编译器只能把一些错误进行归类，并且指出当前认为可疑的地方，并不能完完全全的知道到底是什么语法错误。这个需要结合给出的错误进行判断。

语法有三个主体，表达式(expression)，语句(statement)，声明(declaration)，Node是基类，

用于标记该节点的位置的开始和结束。

了解了这个设计,再来看整个内容其实就是定义了源文件中可能出现的语法结构.列表如下:

1. 普通Node，不是特定语法结构，属于某个语法结构的一部分。 * Comment 表示一行注释 // 或者 /* */ * CommentGroup 表示多行注释

* Field 表示结构体中的一个定义或者变量,或者函数签名当中的参数或者返回值 * FieldList 表示以\或者\包围的Filed列表 2. Expression & Types (都划分成Expr接口) * BadExpr 用来表示错误表达式的占位符 * Ident 比如报名,函数名,变量名

* Ellipsis 省略号表达式,比如参数列表的最后一个可以写成`arg...` * BasicLit 基本字面值,数字或者字符串 * FuncLit 函数定义

* CompositeLit 构造类型,比如{1,2,3,4}

* ParenExpr 括号表达式,被括号包裹的表达式 * SelectorExpr 选择结构,类似于a.b的结构

* IndexExpr 下标结构,类似这样的结构 expr[expr] * SliceExpr 切片表达式,类似这样 expr[low:mid:high] * TypeAssertExpr 类型断言类似于 X.(type) * CallExpr 调用类型,类似于 expr() * StarExpr *表达式,类似于 *X * UnaryExpr 一元表达式 * BinaryExpr 二元表达式

* KeyValueExp 键值表达式 key:value * ArrayType 数组类型 * StructType 结构体类型 * FuncType 函数类型 * InterfaceType 接口类型 * MapType map类型 * ChanType 管道类型 3. Statements

* BadStmt 错误的语句

* DeclStmt 在语句列表里的申明 * EmptyStmt 空语句

* LabeledStmt 标签语句类似于 indent:stmt * ExprStmt 包含单独的表达式语句 * SendStmt chan发送语句

* IncDecStmt 自增或者自减语句 * AssignStmt 赋值语句 * GoStmt Go语句 * DeferStmt 延迟语句 * ReturnStmt return 语句

* BranchStmt 分支语句 例如break continue * BlockStmt 块语句 {} 包裹 * IfStmt If 语句

* CaseClause case 语句 * SwitchStmt switch 语句

* TypeSwitchStmt 类型switch 语句 switch x:=y.(type)

* CommClause 发送或者接受的case语句,类似于 case x <-: * SelectStmt select 语句 * ForStmt for 语句

* RangeStmt range 语句 4. Declarations * Spec type

* Import 导入包的语句 * Value 值语句 * Type 类型语句 * BadDecl 错误申明

* GenDecl 一般申明(和Spec相关,比如 import \ * FuncDecl 函数申明 5. Files and Packages

* File 代表一个源文件节点,包含了顶级元素. * Package 代表一个包,包含了很多文件.

上面就是整个源代码的所有组成元素，接下来就来看一下语法分析是如何进行的，也就是最后的AST是如何构建出来的。

`parser`结构体的定义,parser是以file为单位的.

type parser struct { file *token.File

errors scanner.ErrorList // 解析过程中遇到的错误列表 scanner scanner.Scanner // 词法分析器.

mode Mode // parsing mode // 解析模式 trace bool // == (mode & Trace != 0)

indent int // indentation used for tracing output

// Comments 列表

comments []*ast.CommentGroup

leadComment *ast.CommentGroup // last lead comment lineComment *ast.CommentGroup // last line comment

// Next token

pos token.Pos // token position

tok token.Token // one token look-ahead lit string // token literal

// Error recovery

// (used to limit the number of calls to syncXXX functions // w/o making scanning progress - avoids potential endless // loops across multiple parser functions during error recovery)

syncPos token.Pos // last synchronization position 解析错误的同步点. syncCnt int // number of calls to syncXXX without progress

// Non-syntactic parser control // 非语法性的控制

// <0 在控制语句中, >= 在表达式中.

exprLev int // < 0: in control clause, >= 0: in expression // 正在解析右值表达式

inRhs bool // if set, the parser is parsing a rhs expression

// Ordinary identifier scopes

pkgScope *ast.Scope // pkgScope.Outer == nil

topScope *ast.Scope // top-most scope; may be pkgScope unresolved []*ast.Ident // unresolved identifiers imports []*ast.ImportSpec // list of imports

// Label scopes

// (maintained by open/close LabelScope)

labelScope *ast.Scope // label scope for current function targetStack [][]*ast.Ident // stack of unresolved labels }

解析的入口是 ParseFile ,首先调用 init ，再调用 parseFile 进行解析.

通过 init 初始化 scanner 等。

func (p *parser) init(fset *token.FileSet, filename string, src []byte, mode Mode) { p.file = fset.AddFile(filename, -1, len(src)) var m scanner.Mode

if mode&ParseComments != 0 { m = scanner.ScanComments }

// 错误处理函数是在错误列表中添加错误.

eh := func(pos token.Position, msg string) { p.errors.Add(pos, msg) } p.scanner.Init(p.file, src, eh, m)

p.mode = mode

p.trace = mode&Trace != 0 // for convenience (p.trace is used frequently)

p.next() }

parseFile 的简化流程:

// package clause

// 获取源文件开头的doc注释,从这里递归向下的解析开始了 doc := p.leadComment

// expect 从scanner获取一个token,并且返回位置pos. pos := p.expect(token.PACKAGE)

// parseIdent 获取一个token并且转化为indent,如果不是报错. ident := p.parseIdent()

if ident.Name == \ p.error(p.pos, \ }

// 作用域开始,标记解释器当前开始一个新的作用域 p.openScope()

// pkgScope 就是现在进入的作用域 p.pkgScope = p.topScope // 解析 import 申明

for p.tok == token.IMPORT { // parseGenDecl解析的是 // import ( // ) // 这样的结构,如果有括号就用parseImportSpec解析列表 // 没有就单独解析. // 而parseImportSpec解析的是 一个可选的indent token和一个字符串token. // 并且加入到imports列表中.

decls = append(decls, p.parseGenDecl(token.IMPORT, p.parseImportSpec)) } // 解析全局的申明,包括函数申明 if p.mode&ImportsOnly == 0 { // rest of package body for p.tok != token.EOF {

decls = append(decls, p.parseDecl(syncDecl)) } } // 标记从当前作用域离开. p.closeScope() // 最后返回ast.File文件对象. return &ast.File{ Doc: doc, Package: pos, Name: ident, Decls: decls,

Scope: p.pkgScope, Imports: p.imports,

Unresolved: p.unresolved[0:i], Comments: p.comments, }

parseDecl 主要是根据类型的不同调用不同的解析函数， parseValueSpec 解析Value类型， parseTypeSpec 解析Type类型，parseFuncDecl 解析函数。

解析定义和解析类型的都是解析了，类似于 var|type ( ident valueSpec|typeSpec) 的token结构。因为parseFuncDecl里面也会解析这些内容，所以直接从函数解析来看也可以。因为外一层的top scope其实就是相当于一个抽象的函数作用域而已，这样是为什么`len`和`new`这样的内嵌函数在函数内是可以做变量名的原因，因为可以在子作用域覆盖top作用域。整个解析过程简化过程如下。 // 解析一个func.

pos := p.expect(token.FUNC) // 开一个新的作用域,topScope作为父Scope.

scope := ast.NewScope(p.topScope) // function scope // 解析一个ident作为函数名 ident := p.parseIdent() // 解析函数签名,也就是参数和返回值 params, results := p.parseSignature(scope) // 再解析body body = p.parseBody(scope) // 最后返回函数申明. decl := &ast.FuncDecl{ Doc: doc, Recv: recv, Name: ident,

Type: &ast.FuncType{ Func: pos, Params: params, Results: results, },

Body: body, }

解析参数和返回值就是解析(filed,filed)这样的格式,每个filed是 indent type 的token，最后构造成函数签名。然后来到`parseBody`，这个函数其实就是解析了左右花括号，然后向下开始解析Statement列表,类似于body -> { stmt_list }，然后进入stmt_list的解析，不断地解析statement。

for p.tok != token.CASE && p.tok != token.DEFAULT && p.tok != token.RBRACE && p.tok != token.EOF {

list = append(list, p.parseStmt()) }

parseStmt 最后会进入到语句的解析，然后根据不同的token选择进入不同的解析流程。比如看到?var?，?type?，?const?就是申明，碰到标识符和数字等等可能就是单独的表达式，如果看到defer和return都能判断出相应的语句并按规则解析，看到?break?等条件关键字就解析条件语句，看到?{?就解析块语句，都是可以递归去解析的。

func (p *parser) parseStmt() (s ast.Stmt) { if p.trace {

defer un(trace(p, \ }

switch p.tok {

case token.CONST, token.TYPE, token.VAR:

s = &ast.DeclStmt{Decl: p.parseDecl(syncStmt)} case

// tokens that may start an expression

token.IDENT, token.INT, token.FLOAT, token.IMAG, token.CHAR, token.STRING, token.FUNC, token.LPAREN, // operands

token.LBRACK, token.STRUCT, token.MAP, token.CHAN, token.INTERFACE, // composite types

token.ADD, token.SUB, token.MUL, token.AND, token.XOR, token.ARROW, token.NOT: // unary operators

s, _ = p.parseSimpleStmt(labelOk)

// because of the required look-ahead, labeled statements are // parsed by parseSimpleStmt - don't expect a semicolon after // them

if _, isLabeledStmt := s.(*ast.LabeledStmt); !isLabeledStmt { p.expectSemi() }

case token.GO:

s = p.parseGoStmt() case token.DEFER:

s = p.parseDeferStmt() case token.RETURN:

s = p.parseReturnStmt()

case token.BREAK, token.CONTINUE, token.GOTO, token.FALLTHROUGH: s = p.parseBranchStmt(p.tok) case token.LBRACE:

s = p.parseBlockStmt() ...省略

举个例子看一下`parseSimpleStmt()`的简化流程

// 解析左列表 一般是 l := r 或者 l1,l2 = r1,r2 或者 l <- r 或者 l++ x := p.parseLhsList() switch p.tok { case

token.DEFINE, token.ASSIGN, token.ADD_ASSIGN,

token.SUB_ASSIGN, token.MUL_ASSIGN, token.QUO_ASSIGN, token.REM_ASSIGN, token.AND_ASSIGN, token.OR_ASSIGN, token.XOR_ASSIGN, token.SHL_ASSIGN, token.SHR_ASSIGN, token.AND_NOT_ASSIGN: // 如果看到range,range作为一种运算符按照range rhs来解析 // 如果没看到就按正常赋值语句解析 lhs op rhs 来解析op可以是上面那些token中的一

种.

pos, tok := p.pos, p.tok p.next()

var y []ast.Expr isRange := false

if mode == rangeOk && p.tok == token.RANGE && (tok == token.DEFINE || tok == token.ASSIGN) {

pos := p.pos p.next()

y = []ast.Expr{&ast.UnaryExpr{OpPos: pos, Op: token.RANGE, X: p.parseRhs()}} isRange = true } else {

y = p.parseRhsList() }

as := &ast.AssignStmt{Lhs: x, TokPos: pos, Tok: tok, Rhs: y} // 碰到\找一个ident, 构成 goto: indent 之类的语句. case token.COLON: colon := p.pos p.next()

if label, isIdent := x[0].(*ast.Ident); mode == labelOk && isIdent { // Go spec: The scope of a label is the body of the function // in which it is declared and excludes the body of any nested // function.

stmt := &ast.LabeledStmt{Label: label, Colon: colon, Stmt: p.parseStmt()} p.declare(stmt, nil, p.labelScope, ast.Lbl, label) return stmt, false } // 碰到\就构成 <- rhs 这样的语句. case token.ARROW: // send statement arrow := p.pos p.next()

y := p.parseRhs()

return &ast.SendStmt{Chan: x[0], Arrow: arrow, Value: y}, false // 碰到\或者\就构成一个单独的自增语句. case token.INC, token.DEC: // increment or decrement

s := &ast.IncDecStmt{X: x[0], TokPos: p.pos, Tok: p.tok} p.next()

return s, false } ```

这里举个例子，比如如下的源文件：

package main

import ( \ \ \)

main() {

fset := token.NewFileSet()

f, err := parser.ParseFile(fset, \package main func main(){ // comments x:=1

go println(x) if err != nil { panic(err) }

ast.Print(fset, f) }

产生的结果是

0 *ast.File {

1 . Package: 2:1 2 . Name: *ast.Ident { |IDENT token 3 . . NamePos: 2:9 4 . . Name: \ 5 . } | 6 . Decls: []ast.Decl (len = 1) { | 7 . . 0: *ast.FuncDecl { 8 . . . Name: *ast.Ident { 9 . . . . NamePos: 3:6 10 . . . . Name: \ 11 . . . . Obj: *ast.Object { 12 . . . . . Kind: func FuncDecl.

13 . . . . . Name: \ 14 . . . . . Decl: *(obj @ 7) 15 . . . . } | 16 . . . } | 17 . . . Type: *ast.FuncType { 18 . . . . Func: 3:1 19 . . . . Params: *ast.FieldList { 20 . . . . . Opening: 3:10 21 . . . . . Closing: 3:11 |PACKAGE token | | 整个构成了顶部的 package main 最上层的申明列表 |func main的函数申明 |IDENT token | | |Objec是一个用于表达语法对象的结构 |表示之前存在过,Decl指向了7,也就是第7行的| | |函数类型,也就是函数签名 |参数和返回值都是空的 | | |

22 . . . . } | 23 . . . } | 24 . . . Body: *ast.BlockStmt { |块语句,也就是main的body 25 . . . . Lbrace: 3:12 | 26 . . . . List: []ast.Stmt (len = 2) { |语句列表 27 . . . . . 0: *ast.AssignStmt { |赋值语句 28 . . . . . . Lhs: []ast.Expr (len = 1) { |左值是x 29 . . . . . . . 0: *ast.Ident { | 30 . . . . . . . . NamePos: 5:2 | 31 . . . . . . . . Name: \ | 32 . . . . . . . . Obj: *ast.Object { | 33 . . . . . . . . . Kind: var | 34 . . . . . . . . . Name: \ | 35 . . . . . . . . . Decl: *(obj @ 27) | 36 . . . . . . . . } | 37 . . . . . . . } | 38 . . . . . . }

39 . . . . . . TokPos: 5:3 |:=和它的位置 40 . . . . . . Tok: :=

41 . . . . . . Rhs: []ast.Expr (len = 1) { |右边是一个数字类型的token 42 . . . . . . . 0: *ast.BasicLit { 43 . . . . . . . . ValuePos: 5:5 44 . . . . . . . . Kind: INT 45 . . . . . . . . Value: \ 46 . . . . . . . } 47 . . . . . . } 48 . . . . . }

49 . . . . . 1: *ast.GoStmt { |接下来是go语句 50 . . . . . . Go: 6:2

51 . . . . . . Call: *ast.CallExpr { |一个调用表达式 52 . . . . . . . Fun: *ast.Ident { |IDENT token是println 53 . . . . . . . . NamePos: 6:5 54 . . . . . . . . Name: \ 55 . . . . . . . }

56 . . . . . . . Lparen: 6:12 |左括号的位置 57 . . . . . . . Args: []ast.Expr (len = 1) { |参数列表 58 . . . . . . . . 0: *ast.Ident { |是一个符号INDENT,并且指向的是32行的x 59 . . . . . . . . . NamePos: 6:13 60 . . . . . . . . . Name: \

61 . . . . . . . . . Obj: *(obj @ 32) 62 . . . . . . . . } 63 . . . . . . . }

64 . . . . . . . Ellipsis: -

65 . . . . . . . Rparen: 6:14 |右括号的位置 66 . . . . . . } 67 . . . . . } 68 . . . . }

69 . . . . Rbrace: 8:1 70 . . . } 71 . . } 72 . }

73 . Scope: *ast.Scope { |最顶级的作用域 74 . . Objects: map[string]*ast.Object (len = 1) { 75 . . . \ 76 . . } 77 . }

78 . Unresolved: []*ast.Ident (len = 1) { |这里有个没有定义的符号println，是因为是内置符号，会另外处理。 79 . . 0: *(obj @ 52) |从源文件上是表现不出来的。 80 . }

81 . Comments: []*ast.CommentGroup (len = 1) { |注释列表，以及位置和内容。 82 . . 0: *ast.CommentGroup {

83 . . . List: []*ast.Comment (len = 1) { 84 . . . . 0: *ast.Comment { 85 . . . . . Slash: 4:2

86 . . . . . Text: \ 87 . . . . } 88 . . . } 89 . . } 90 . } 91 } 这就是整个语法分析和最后产生的语法树的结构。 早期语言设计不是很固定的。都是慢慢尝试不断改进的过程，最早的一次spec文档其实和现在差了很多很多。就是把TOKEN记号流从左至右匹配规则(可能会向前看几个token)，然后递归解析语法树，最后得到AST。 错误处理的同步问题，寄希望于能够向使用者提供更多的错误。主要是parser当中的两个结构

syncPos token.Pos // last synchronization position

syncCnt int // number of calls to syncXXX without progress syncPos是错误的同步位置，也就类似于游戏的存档点，如果发生错误那就从这个地方开始跳过(BadStmt|BadExpr)继续解析，在每次完成语句，申明或者表达式的解析之后就会保存一个同步点。虽然这种继续解析的行为不一定能够给出很精确的错误提示，但的确够用了。当然如果错误实在太多了，从同步点恢复也没有太大意义，就会主动放弃，所以记录了没有成功解析而同步的次数。

3.4 编写VM实现后端

语句主要支持的是赋值表达式，例如if语句，switch语句，for语句，return语句，break语

句，continue语句，include语句，import语句，export语句，defer语句，go语句和单表达式构成的语句。

if语句类似于`if expr body elif expr else body`。

switch语句类似于`switch expr { swbody }`，swbody的定义又是类似于`case expr: body default: body`的形式。

for语句类似于`for stmt;stmt;stmt body`的形式。 retur语句比较简答,对应的是`return expr`。 break,continue语句只有`continue`和`break。

include，import语句则是`include STRING`和`import STRING`的形式。 defer语句是`defer expr`的形式。

但是目前的实现没有定义中间状态的字节码，而是以一个库的形式，用接口的形式作为字节码执行的接口。

任何字节码的定义都要满足这样的接口，第一个参数是当前的栈，第二个参数是执行的上下文。 type Instr interface {

Exec(stk *Stack, ctx *Context) }

对应的实现者以i开头表示是字节码指令，分别为`Class`，`iAnonymFn`(匿名函数)，`iAs`，`iAssign`(赋值)，`iCall`(调用)，`iDefer`，isExport`，`iForRange`，`iFunc`，`iGo`，`iMacro`，`iMemberRef`,`iModule`，`iMultiAssign`，`iMultiAssingFromSlice`，`iOp1Assign`，`iOp3`，

`iOpAssign`，`iPush`,`iRef`，`iRem`，`iUnSet`，`iAnd`，`iCallFn`，`iCallFnv`，`iCase`，`iGo`，`iChanIn`，`iClear`，`iJmp`，`iJmpIfFalse`，`iNew`，`iOr`，`iPop`，`iPopEx`，`iRecover`，`iReturn`，等等这些字节码都是通过构造函数变作为`Insrt`接口返回的。 其实编程语言的虚拟机说白了就是一种提供字节码的运行环境，比如我定义`add x1,x2`和`sub x1,x2`两条指令作为我的虚拟机的集合，那么我的虚拟寄字节码就支持加法和乘法，也就

可以完成一个简易计算器的算式到字节码的转化，再把得到的字节码按照我们的需要进行转换。 LLVM就是把自己定义的一套字节码(也就是类似于平台无关的虚拟汇编，其实这种汇编要稍微好用一点，因为里面的寄存器是无限多个的，不需要自己考虑寄存器不够的情况)，然后把这些字节码转化成平台相关的汇编，最后变成二进制文件。所以实现一套编程语言虚拟机就是要定义一套字节码的集合和对应的实现方式。 这里我们用Go实现虚拟机是通过Go来运行的，所以没有静态语言的性质，只是跑在Go的运行时上的虚拟机。这里我们举个例子看一下具体的实现。

现在以`switch`语法为例说一下运行流程

在C转汇编的过程中,`switch case`是通过跳转表来实现的,比如下面的C代码

#include

int f(int x) { switch(x)

{ case 1: printf(\ break; case 2: printf(\ break; default: printf(\ } }

int main() { f(3); }

转成汇编的话就是如下代码,f为`switch case`的部分的实现. .file \ .section .rodata .LC0: .string \ .text .globl f .type f, @function f: pushq %rbp // 保存栈base指针 movq %rsp, %rbp // 移动栈指针到rbp subq $16, %rsp // 因为leaf function,可以开辟red zone[3] 128个字节 movl íi, -4(%rbp) // 栈指针开始第4个字节,也就是第一个参数,0(%rbp)是callee保留的rbp. movl -4(%rbp), êx // 移动到eax中 cmpl $1, êx //和1比较跳到L3 je .L3 cmpl $2, êx //和2比较跳到L4 je .L4 jmp .L7 // default跳到L7 .L3: movl $49, íi // 放入参数'1'调用putchar,这里只打印一个字符,被优化成了putchar. call putchar jmp .L6 .L4: movl $50, íi // 放入参数'2' call putchar jmp .L6 .L7:

movl $.LC0, íi // 让如.LC0,也就是字符串\的地址放入edi作为printf的参数 movl $0, êx call printf .L6: leave ret .size f, .-f .globl main .type main, @function main: pushq %rbp movq %rsp, %rbp movl $3, íi call f popq %rbp ret .size main, .-main .ident \ .section .note.GNU-stack,\ 从汇编可以看出`switch case`其实本身其实是可以通过`goto`实现的，`switch case`只是`goto`的一个高级封装的实现技巧而已。如何放到虚拟机中，其实就是提供类似的`goto`机制来满足跳转的需求。 在实验中，switch解析的时候首先注册了`$switch`的回调函数，如果匹配了

`\就会调用`Compiler.Switch函数进行处理`。

swith body 是按照如下定义的:

`swbody = *(\

`_ARITY`获取的是语法匹配的次数,分别记录了`case`和`default`匹配的次数,`case`可以匹配`*`次,`default`可以匹配`?`次.

然后可以看下Switch如何处理的.

func (p *Compiler) Switch(e interpreter.Engine) { var defaultCode interface{} // 之前push了一个 ? 的匹配次数, 如果是1那么就有default的代码, 所以把defaultCode pop出来. defaultArity := p.popArity() if defaultArity == 1 { defaultCode, _ = p.gstk.Pop()

}

// 获取case的匹配次数 caseArity := p.popArity()

// case 中有个expression,case:后面有一个statment,所以乘2 casebr := p.gstk.PopNArgs(caseArity << 1) // 2 * caseArity // 这switch:后面跟着的expression的代码取出 switchCode, _ := p.gstk.Pop() // 保存老的块上下文 old := p.bctx

p.bctx = blockCtx{}

// switchCode有两种 , 一种是 switch , 一种是 switch expr.

// 这里处理的是switch {}的形式,每个case中都是条件表达式,就变成了if语句. if switchCode == nil { // 执行case branch,和default branch p.doIf(e, casebr, defaultCode, caseArity) p.bctx.MergeSw(&old, p.code.Len()) return }

// 转换switchCode

// reserved2 是一组空的指令,用于最后填充跳转指令跳到switch body的末尾. reserved2 := make([]exec.ReservedInstr, caseArity) if err := e.EvalCode(p, \ panic(err) }

// 解析switchCode完毕,添加一行代码 p.CodeLine(switchCode) for i := 0; i < caseArity; i++ { caseCode := casebr[i<<1] // 解析表达式 if err := e.EvalCode(p, \ panic(err) } // 记录解析过的一行代码 p.CodeLine(caseCode) // 保留指令一行空指令留待插入 case的跳转指令 reserved1 := p.code.Reserve() bodyCode := casebr[(i<<1)+1] // 解析块代码 bctx := evalDocCode(e, p, bodyCode) // 把当前作用域中break,continue指令加入到p.bctx中 // 等最后到解析末尾再把跳转距离计算出来 bctx.MergeTo(&p.bctx) // 把当前位置留空. // 解析到了case :{}结尾作为跳转到结尾的指令的插入位置. reserved2[i] = p.code.Reserve()

// 把reserved1保留的位置插入跳转到reserved2的保留的地址的地方. // 相当于 Case delta,如果case 成功那么就跳到body的末尾,reserved2[i] reserved1.Set(exec.Case(reserved2[i].Delta(reserved1))) } // 类似的解析default的case p.code.Block(exec.Default) bctx := evalDocCode(e, p, defaultCode) bctx.MergeTo(&p.bctx) end := p.code.Len() for i := 0; i < caseArity; i++ { // 设置跳转到末尾的指令 reserved2[i].Set(exec.Jmp(end - reserved2[i].Next())) } // 设置break指令的跳转地址. // 并把旧bctx换回来,也就是说break,continue // 跳转范围就终止在 switch 的作用域内. p.bctx.MergeSw(&old, end) }

比如下面的代码进行转化的话 x=1

switch(x){ case 1: x=4 break case 2: x=2 break case 3: x=3 break } ```

就跳到执行块的末尾,最后的翻译结果就是下面这样

==> 0000: Var &{x} // 变量x ==> 0001: Push &{1} // 压入1 ==> 0002: AssignEx 0 // x=1 ==> 0003: Ref &{x} // 引用x ==> 0004: Push &{1} // 压入1

==> 0005: Case 5 // case是自己定义的字节码,等于pop 1 再和当前栈顶的x比较,如果成功向下跳转5

==> 0006: Var &{x} // 引用x

==> 0007: Push &{4} // 压入4 ==> 0008: AssignEx 0 // x=4

==> 0009: Jmp 16 // break 跳到结尾

==> 0010: Jmp 15 // case 不会继续执行,也是跳到结尾 ==> 0011: Push &{2} // 后面是类似的 ==> 0012: Case 5 ==> 0013: Var &{x} ==> 0014: Push &{2} ==> 0015: AssignEx 0 ==> 0016: Jmp 9 ==> 0017: Jmp 8

==> 0018: Push &{3} ==> 0019: Case 5 ==> 0020: Var &{x} ==> 0021: Push &{3} ==> 0022: AssignEx 0 ==> 0023: Jmp 2 ==> 0024: Jmp 1 ==> 0025: Pop 0 比起汇编，我们定义的字节码稍微高级一点不需要构造跳转表，而是用Case指令替代，和栈顶的值比较，如果为true就顺序执行，不然就会跳转相对距离的位置，到这里为止，我们的转换就结束了。整个代码结构大致如此。

第四节 总结

本实验主要讨论了这个微小型编译器的实现，其中涵盖了大部分的设计细节和理论基础，这实践都于以后的工程生活和生产实践都有非常重要的指导意义。 本文提出了编译器的概念，并给出了编译的定义，旨在体验传统的编译器的设计与实现 ，源码到语法记号到语法树到虚拟机字节直到最后可运行的程序的实现过程，涵盖了很多编译领域重要的工程经验。 主要实现的内容包括：词法分析器，语法解析器，后端虚拟机。并最终以一款完整，功能较完全的编译器的形式体现出来。 引用：

2: https://en.wikipedia.org/wiki/Clang 3: https://en.wikipedia.org/wiki/LLVM 4: https://en.wikipedia.org/wiki/Yacc

5: https://en.wikipedia.org/wiki/Backusa??Naur_Form

致谢

本次毕业设计工作延续了很长的时间。从论文选题到 理论探讨，从论文审校到最终定稿，无不凝聚着大量心血。 毕业设计是大学期间最重要的环节之一，是对大学四年理论学习的一次总结和应用。从论文的课题研究到实验，再到论文的撰写过程中遇到了无数的困难与坎坷，查阅了 无数的文献资料，唯有不断地思考和尝试，脚踏实地，才是一名本科生追求知识的正确方

向。大学四年的生活已接近尾声，回首奋斗于毕业的三个月里，感觉十分充实，随着本次 论文的完成,也将要给本科生涯划下完美的句号。 我能够完 成本次编译器的设计与实现，这一对我来说是全新领域的题目，感到收益匪浅。 四年的大学生活马上就要过去。在这过去的四年学习生活中，我受到了学校、老师以及同学的 大力帮助、关心和爱护。在此，我谨向我的指导老师以及在这四年中帮助和教育过我的全体老师敬 上我深深的谢意和祝福。同时我也要感谢这四年中和我风雨与共，互相帮助，互相扶持的许许多多 的同学、朋友们。还要感谢我的父母，虽然这四年来他们不是很懂我在干什么，但是还是义无反顾提供对我的支持，照顾我的生活，我的顺利毕业他们也应该居功至伟。

向。大学四年的生活已接近尾声，回首奋斗于毕业的三个月里，感觉十分充实，随着本次 论文的完成,也将要给本科生涯划下完美的句号。 我能够完 成本次编译器的设计与实现，这一对我来说是全新领域的题目，感到收益匪浅。 四年的大学生活马上就要过去。在这过去的四年学习生活中，我受到了学校、老师以及同学的 大力帮助、关心和爱护。在此，我谨向我的指导老师以及在这四年中帮助和教育过我的全体老师敬 上我深深的谢意和祝福。同时我也要感谢这四年中和我风雨与共，互相帮助，互相扶持的许许多多 的同学、朋友们。还要感谢我的父母，虽然这四年来他们不是很懂我在干什么，但是还是义无反顾提供对我的支持，照顾我的生活，我的顺利毕业他们也应该居功至伟。

本文来源：https://www.bwwdw.com/article/0phw.html