当前位置:首页 >> 政史地 >>

类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 = "hello" // string 类型 c = true // bool 类型 d = 1.0 // float 类型 e = 'h' // byte 类型 string 类型 a = "hello, world" string 有如下内置操作: a = "hello" + "world" // + 为字符串连接操作符 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 = ["a", "b", "c"] // 创建一个 string slice d = ["a", 1, 2.3] // 创建一个 var slice (等价于 Go 语言的 []interface{}) e = mkslice("int", len, cap) // 创建一个 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 = {"a": 1, "b": 2, "c": 3} // 得到 map[string]int 类型的对象 b = {"a": 1, "b", 2.3, "c": 3} // 得到 map[string]float64 类型的对象 c = {1: "a", 2: "b", 3: "c"} // 得到 map[int]string 类型的对象 d = {"a": "hello", "b": 2.0, "c": true} // 得到 map[string]interface{} 类型的对象 e = mkmap("string:int") // 创建一个空的 map[string]int 类型的对象 f = mkmap(mapOf("string", type(e))) // 创建一个 map[string]map[string]int 类型的对象 map 类型有如下操作 n = len(a) // 取 a 的元素个数 x = a["b"] // 取 a map 中 key 为 "b" 的元素 x = a.b // 含义同上,但如果 "b" 元素不存在会 panic a["e"], a["f"], a["g"] = 4, 5, 6 // 同 Go 语言 a.e, a.f, a.g = 4, 5, 6 // 含义同 a["e"], a["f"], a["g"] = 4, 5, 6 delete(a, "e") // 删除 a map 中的 "e" 元素 需要注意的是,a["b"] 的行为常见的范式是: x = {"a": 1, "b": 2} a = x["a"] // 结果:a = 1 if a != undefined { // 判断 a 存在的逻辑 ... } c = x["c"] // 结果:c = undefined,注意不是 0,也不是 nil d = x["d"] // 结果:d = undefined,注意不是 0,也不是 nil chan 类型 ch1 = mkchan("bool", 2) // 得到 buffer = 2 的 chan bool ch2 = mkchan("int") // 得到 buffer = 0 的 chan int ch3 = mkchan(mapOf("string", type(ch2))) // 得到 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、"hello" 类似的一个值,只是值的类型是函数类型。 可以在一个函数中引用外层函数的变量。如: 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, "hello") 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, "hello") println(foo.a) // 输出 3 include 语法 一个文件可以通过 include 文法来将另一个文件的内容包含进来。所谓包含,其实际的能力类似 于将代码拷贝粘贴过来。例如,在某个目录下有 a 和 b 两个文件。 其中 a 内容如下: println("in script A") foo = fn() { println("in func foo:", a, b) } 其中 b 内容如下:

a=1 b=2 include "a.ql" println("in script B") foo() 模块及 import 模块(module)是一个目录,该目录下要求有一个名为 main 的文件。模块中的标识(ident)默认都 是私有的。想要导出一个标识(ident),需要用 export 语法。例如: a=1 b=2 println("in script A") f = fn() { println("in func foo:", a, b) } export a, f 这个模块导出了两个标识(ident):整型变量 a 和 函数 f。 要引用这个模块,我们需要用 import 文法: import "foo/bar.v1" import "foo/bar.v1" as bar2 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, "Usage: maxprime <Value>") 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("cos(x) + 1i*sin(x) // Euler") // 初始化 scanner var s scanner.Scanner fset := token.NewFileSet() // 添加到文件集合中 file := fset.AddFile("", fset.Base(), len(src)) // register input "file" // 初始化 scanner s.Init(file, src, nil /* no error handler */, scanner.ScanComments) // 不断获取需要得到的字符记号 for { pos, tok, lit := s.Scan() if tok == token.EOF { break } fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit) } // 不断扫描就能得到如下结果 // 词法分析就是做这样一件事情. // output: // 1:1 IDENT "cos" // 1:4 ( "" // 1:5 IDENT "x" // 1:6 ) "" // 1:8 + "" // 1:10 IMAG "1i" // 1:12 * "" // 1:13 IDENT "sin" // 1:16 ( ""

// 1:17 IDENT "x" // 1:18 ) "" // 1:20 ; "\n" // 1:20 COMMENT "// Euler" } 3.2.1.2 匹配规则 TPL 是独创实现的文本处理引擎,把文本处理分为了两个阶段。和 Yacc 不同的是,实现简 单,生成的代码本身也是自顶向下的递归解析,方便手动改造。 基本独立 token 的匹配规则的表示方式又分为以下几类: * TOKEN:通常以全大些的字母表达,如: IDENT、INT、FLOAT、IMAG、STRING、CHAR、COMMENT 等。 * 单字符操作符:如:'+'、'-'、'*'、'/' 等等。这些其实也可以用上面 TOKEN 形式表达,只 是不那么直观。如 '+' 可以用 `ADD`,'-' 可以用 `SUB` 等等。 * 多字符操作符:如: "++"、"--"、"+="、"<=" 等等。这些其实也可以用上面 TOKEN 形式表 达,只是不那么直观。"++" 可以用 `INC`,"+=" 可以用 `ADD_ASSIGN` 等等。 * 关键字:如:"if"、"return"、"class" 等等。TPL 内建的 AutoKwScanner 可以自动识别语言 的关键字。其原理是,只要在 TPL 文法中出现了满足 `'"' IDENT '"'` 形式的规则,那么就认为里 面 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" '(' ')'` 表示要匹 配的文本去除所有空白和注释后是 `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 ( "qiniupkg.com/text/tpl.v1" ) // 定义要处理的文本内容对应的 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 | "%=" factor/list0 | '/' 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 "a",var a,type a) * 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.mode&DeclarationErrors != 0 { p.error(p.pos, "invalid package name _") } // 作用域开始,标记解释器当前开始一个新的作用域 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, "Statement")) } 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 ( "go/ast" "go/parser" "go/token" ) 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 { 3 . . NamePos: 2:9 4 . . Name: "main" 5 . } 6 . Decls: []ast.Decl (len = 1) { 7 . . 0: *ast.FuncDecl { 8 . . . Name: *ast.Ident { 9 . . . . NamePos: 3:6 10 . . . . Name: "main" 11 . . . . Obj: *ast.Object { 12 . . . . . Kind: func FuncDecl. 13 . . . . . Name: "main" 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 |IDENT token | | |整个构成了顶部的 package main |最上层的申明列表 |func main 的函数申明 |IDENT token | | |Objec 是一个用于表达语法对象的结构 |表示之前存在过,Decl 指向了 7,也就是第 7 行的 | | | | |函数类型,也就是函数签名 |参数和返回值都是空的 | | |

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. } | } | Body: *ast.BlockStmt { . Lbrace: 3:12 . List: []ast.Stmt (len = 2) { . . 0: *ast.AssignStmt { . . . Lhs: []ast.Expr (len = 1) { . . . . 0: *ast.Ident { . . . . . NamePos: 5:2 . . . . . Name: "x" . . . . . Obj: *ast.Object { . . . . . . Kind: var . . . . . . Name: "x" . . . . . . Decl: *(obj @ 27) . . . . . } . . . . } . . . } . . . TokPos: 5:3 . . . Tok: := . . . Rhs: []ast.Expr (len = 1) { . . . . 0: *ast.BasicLit { . . . . . ValuePos: 5:5 . . . . . Kind: INT . . . . . Value: "1" . . . . } . . . } . . } . . 1: *ast.GoStmt { . . . Go: 6:2 . . . Call: *ast.CallExpr { . . . . Fun: *ast.Ident { . . . . . NamePos: 6:5 . . . . . Name: "println" . . . . } . . . . Lparen: 6:12 . . . . Args: []ast.Expr (len = 1) { . . . . . 0: *ast.Ident { . . . . . . NamePos: 6:13 . . . . . . Name: "x" . . . . . . Obj: *(obj @ 32) . . . . . } . . . . } . . . . Ellipsis: . . . . Rparen: 6:14 . . . } . . } . }

|块语句,也就是 main 的 body | |语句列表 |赋值语句 |左值是 x | | | | | | | | | |:=和它的位置 |右边是一个数字类型的 token

|接下来是 go 语句 |一个调用表达式 |IDENT token 是 println

|左括号的位置 |参数列表 |是一个符号 INDENT,并且指向的是 32 行的 x

|右括号的位置

69 . . . . Rbrace: 8:1 70 . . . } 71 . . } 72 . } 73 . Scope: *ast.Scope { |最顶级的作用域 74 . . Objects: map[string]*ast.Object (len = 1) { 75 . . . "main": *(obj @ 11) 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: "// comments" 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 <stdio.h> int f(int x) { switch(x)

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

movl $.LC0, %edi // 让如.LC0,也就是字符串"default"的地址放入 edi 作为 printf 的参数 movl $0, %eax call printf .L6: leave ret .size .globl .type main: pushq movq movl call f popq ret .size .ident .section f, .-f main main, @function %rbp %rsp, %rbp $3, %edi %rbp main, .-main "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4" .note.GNU-stack,"",@progbits

从汇编可以看出`switch case`其实本身其实是可以通过`goto`实现的,`switch case`只是`goto` 的一个高级封装的实现技巧而已。如何放到虚拟机中,其实就是提供类似的`goto`机制来满足跳 转的需求。 在实验中,switch 解析的时候首先注册了`$switch`的回调函数,如果匹配了 `"switch"/_mute! ?(~'{' expr)/_code '{' swbody '}'/_unmute/switch`就会调用`Compiler.Switch 函数进 行处理`。

swith body 是按照如下定义的: `swbody = *("case"! expr/_code ':' doc/_code)/_ARITY ?("default"! ':' doc/_code)/_ARITY` `_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, "expr", switchCode); err != nil { panic(err) } // 解析 switchCode 完毕,添加一行代码 p.CodeLine(switchCode) for i := 0; i < caseArity; i++ { caseCode := casebr[i<<1] // 解析表达式 if err := e.EvalCode(p, "expr", caseCode); err != nil { 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/Backus%E2%80%93Naur_Form 致谢 本次毕业设计工作延续了很长的时间。从论文选题到 理论探讨,从论文审校到最终定稿, 无不凝聚着大量心血。 毕业设计是大学期间最重要的环节之一,是对大学四年理论学习的一次 总结和应用。从论文的课题研究到实验,再到论文的撰写过程中遇到了无数的困难与坎坷,查 阅了 无数的文献资料,唯有不断地思考和尝试,脚踏实地,才是一名本科生追求知识的正确方

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


相关文章:
类C微小编译器的设计与实现-2016-5-20
类C微小编译器的设计与实现-2016-5-20_政史地_高中教育_教育专区。类 C 微小编译器的设计与实现 摘要 随着计算机的广泛应用,计算机编程语言从早期的机器语言到...
《用经济学智慧解读中国》课后题答案2016-5
《用经济学智慧解读中国》课后题答案2016-5_经济学...C 得分: 0.0 分 3 机制的优化设计可以促进资源...A、两层次市场 B、两类产品 C、配置的差异 D、...
C语言编译器设计与实现毕业论文设计
C 语言语法及语法特点; 4.深入分析编译器编写语言(C++) ; 5.设计实现编译...C 编译器的各个阶段以的形式表示,最后以项目文件为单位来编译生成 C 编译器...
网站设计与实现2016上半年作业答案
复查测验提交: 2016 年上半年《网络设计与实现》第...答案 所选答案: C. 伪类 active . 问题 20 .得...[1]中实现了对商品大类的增加、修改和删除三大功能...
注册会计师(十)企业所得税法单项选择题(2016-02-20)
注册会计师(十)企业所得税法单项选择题(2016-02-20)_教学计划_教学研究_教育...A.不得 B.可以 C.必须 D.应当 5 下列关于企业重组业务的企业所得税处理...
《考古发现与探索》(20)期末试题满分答案2016-5
《考古发现与探索》(20)期末试题满分答案2016-5_...? ? ? A、《先秦古器图碑》 B、《考古图》 C...脑袋 我的答案:D 21 秦始皇的兵马俑是谁设计的 1...
5-2016施工组织设计
5-2016施工组织设计_建筑/土木_工程科技_专业资料。附件 1 山东建筑大学毕业...工程款拨付: 1)工程合同价 C=工程报价; 2)开工前拨付工程备料款 A=20% C...
编译原理-课程设计报告-简单编译器实现
3 1.3 其它通过实现一个可以把类似 c 语言的源...编译原理词法语法语义分析器设计.2013-07-23:5 页...栈类定义 { private: int top; string *stacka;...
TINY-C编译器的设计与实现-词法分析器的设计与实现
TINY-C编译器的设计与实现-词法分析器的设计与实现...(pgm,"r"); 20 if (source==NULL) { fprintf...表 5-1 黑盒测试输入 期望结果 词法错误 标示符...
C-编译器设计报告
C-编译器设计报告_工学_高等教育_教育专区。课程实验...两个类: 词法分析包括两个类: 包括两个类(1)...与编译课程设计 S07102114 张洁坤 line: 5 Token ...
更多相关标签:
2016微小企业免税政策 | matlab2016a 编译器 | matlab 2016 编译器 | matlab2016b编译器 | java编译器 2016 | 易语言编译器vs2016 | c 编译器2016 | 高级编译器设计与实现 |