.. _chapter-1:

***************************
第一章 教程简介与词法分析器
***************************

:原文: `Tutorial Introduction and the Lexer <http://llvm.org/docs/tutorial/LangImpl1.html>`_

教程介绍
========

欢迎走进“LLVM开发新语言”教程。本教程详细介绍了一门简单语言的实现过程；你将会看到，这个过程既轻松又有趣。本教程将伴你一起搭建一套框架，它可以成为你今后实现其他语言的基础。教程中的代码就是供你把玩LLVM的各种功能的试验田。

本教程的目标是循序渐进地描绘一门语言，并详述它的开发过程。在这一过程中，我们将针对语言设计以及LLVM的用法等问题展开讨论。与此同时，我们会给出代码并进行讲解，你免各种细节把你弄得晕头转向。

需要提前说明的是，这一教程讲授的是编译器技术和LLVM，\ **不是**\ 四平八稳的现代化软件工程准则。换言之，方便起见，我们会采用一些不太正规的手法。譬如对内存泄漏孰视无睹、滥用全局变量、无视\ `visitor`__\ 等成熟设计模式等等……一切从简。如果你有意深究，并打算把这些代码用作今后项目的基础，这些毛病也不难修。

__ http://en.wikipedia.org/wiki/Visitor_pattern

.. compound::

    我试着编排了本教程的各个章节，碰到熟悉的或是不感兴趣的章节，你大可直接跳过。本教程的结构如下：

    -   :doc:`第一章 <chapter-1>`\ ：\ **Kaleidoscope语言及其词法解析器简介**

        阐明我们的目的，并明确新语言应该具备哪些基本功能。为了让这份教程尽量易于理解、易于入手，我们决定不采用任何词法分析器和语法分析器的生成器\ [#]_\ ，而是直接用C++实现所有功能。当然，LLVM与这些工具配合使用也完全没问题，如果愿意，你大可放手一试。

    -   :doc:`第二章 <chapter-2>`\ ：\ **实现语法分析器和AST**

        完成词法分析器之后，我们就开始讨论语法解析技术，进而开始构造基本的AST。这份教程共介绍了递归下降解析和运算符优先级解析两种解析技术。\ :doc:`第一章 <chapter-1>`\ 和\ :doc:`第二章 <chapter-2>`\ 的内容与LLVM完全无关，至此，我们的代码甚至都不需要链接LLVM库。 :-)

    -   :doc:`第三章 <chapter-3>`\ ：\ **LLVM IR代码生成**

        搞定AST之后，我们忍不住要炫耀一番，让你看看LLVM IR的生成过程是多么的简单。

    -   :doc:`第四章 <chapter-4>`\ ：\ **添加JIT和优化支持**

        很多人都有意将LLVM用作JIT，有鉴于此，我们打算在此深入一下，让你见识一下区区三行代码搞定JIT支持。尽管LLVM在其他方面也应用广泛，但说到炫技，还是这三行代码最简单、最“惊艳”。

    -   :doc:`第五章 <chapter-5>`\ ：\ **语言扩展：流程控制**

        我们的语言已经可以运行了，现在来看看如何为它添加流程控制能力（即\ ``if``/``then``/``else``\ 和“\ ``for``\ ”循环）。在此我们还将借机介绍一下简单的\ `SSA`__\ 构造和流程控制。

    -   :doc:`第六章 <chapter-6>`\ ：\ **语言扩展：用户自定义运算符**

        这一章用处不大，但却很有意思。我们再次对语言进行了扩展，赋予了用户在程序中自行定义任意一元和二元运算符的能力（还可以设置优先级！）。这一机制使得我们得以将该“语言”的很大一部分实现成库函数。

    -   :doc:`第七章 <chapter-7>`\ ：\ **语言扩展：可变变量**

        本章介绍的是用户自定义局部变量和赋值运算符的实现。最有意思的地方在于，在LLVM中构造SSA form简单至极：不，实际上LLVM压根儿就\ **不**\ 要求你在前端\ [#]_\ 构造SSA form！

    -   :doc:`第八章 <chapter-8>`\ ：\ **结论以及其他和LLVM有关的内容**

        本章对整个系列教程作出了总结，不仅讨论了多种潜在的语言扩展方向，还针对一系列“专题”给出了参考资料，例如垃圾回收支持、异常、调试、“\ `麻花栈`__\ [#]_\ ”支持等，此外，还提到了很多其他的窍门和技巧。

__ http://en.wikipedia.org/wiki/Static_single_assignment_form
__ http://en.wikipedia.org/wiki/Spaghetti_stack

截至本教程末尾为止，不算注释和空行，我们总共只需编写不到700行代码。面对这样一门相对复杂的语言，只用了这么点儿代码就我们实现了一款颇为像样的编译器，其中包括手工打造的词法分析器、语法分析器、AST，还实现了带JIT编译器的代码生成。我想，相对于其他系统给出的那些“hello world”级别的教程，这篇教程的广度足以诠释LLVM的强大；如果你对语言和编译器设计感兴趣，它应该能够说服你认真考虑LLVM。

最后说一句：我们希望你能够进一步扩展这一语言，好好玩味一番。拿着代码疯狂地hack去吧，编译器并非令人恐惧的怪兽——把玩程序语言，奇乐无穷！

初级语言
========

本教程介绍了一门玩具语言，名叫“\ `Kaleidoscope`__\ ”（取“美仑美奂、形态万千、多姿多彩”之意）\ [#]_\ 。Kaleidoscope是一个过程式语言，用户可以定义函数、使用条件语句、执行数学运算等等。随着教程的深入，我们将逐步扩展Kaleidoscope，为它增加\ ``if``/``then``/``else``\ 结构、\ ``for``\ 循环、用户自定义运算符，以及带有简单命令行界面的JIT编译器等等。

__ http://en.wikipedia.org/wiki/Kaleidoscope

简单起见，Kaleidoscope只支持一种数据类型，即64位浮点数（也就是C中的“double”）。这样一来，所有的值都是双精度浮点数，类型申明也省了，语言的语法简洁明快。以下是一个用于计算\ `斐波那契数`__\ 的简单示例：

.. literalinclude:: _includes/chapter-1_1.kaleido

__ http://en.wikipedia.org/wiki/Fibonacci_number

Kaleidoscope还能调用标准库函数（有了LLVM JIT，实现这一点简单至极）。不过，在调用函数之前需要先用“\ ``extern``\ ”关键字对函数进行申明\ [#]_\ （碰到相互递归调用的函数\ [#]_\ 时也需要这么做）。例如：

.. literalinclude:: _includes/chapter-1_2.kaleido

:doc:`第六章 <chapter-6>`\ 的例子更有意思：我们用Kaleidoscope编写了一个小应用，可以按不同尺度\ :ref:`显示Mandelbrot集合 <kicking-the-tires>`\ 。

让我们来细细品味一下这门语言的实现过程吧！

词法分析器
==========

.. compound::

    要实现一门语言，第一要务就是要能够处理文本文件，搞明白其中究竟写了些什么。传统上，我们会先利用“\ `词法分析器`__\ ”（也称为“扫描器”）将输入切成“语元（token）”，然后再做处理。词法分析器返回的每个语元都带有一个语元编号，此外可能还会附带一些元数据（比如某个数值）。首先，我们把所有可能出现的语元都定义出来：

    .. literalinclude:: _includes/chapter-2_full.cpp
        :lines: 7-24
        :language: cpp

    我们的词法分析器返回的语元，要么是上述若干个语元枚举值之一，要么是诸如“\ ``+``\ ”这样的“未知”字符。对于后一种情况，词法分析器返回的是这些字符的ASCII值。如果当前语元是标识符，其名称将被存入全局变量\ ``IdentifierStr``\ 。如果当前语元是数值常量（比如\ ``1.0``\ ），其值将被存入\ ``NumVal``\ 。注意，简单起见，我们动用了全局变量，在真正的语言实现中这可不是最佳选择 :-) 。

__ http://en.wikipedia.org/wiki/Lexical_analysis

.. compound::

    Kaleidoscope的词法分析器由一个名为\ ``gettok``\ 的函数实现。调用该函数，就可以得到标准输入中的下一个语元。它的开头是这样的：

    .. literalinclude:: _includes/chapter-2_full.cpp
        :lines: 26-32
        :language: cpp

    ``gettok``\ 通过C标准库的\ ``getchar()``\ 函数从标准输入中逐个读入字符。它一边识别读取的字符，一边将最后读入的字符存入\ ``LastChar``\ ，留待后续处理。这个函数干的第一件事就是利用上面的循环剔除语元之间的空白符。

.. compound::

    接下来，\ ``gettok``\ 开始识别标识符和“\ ``def``\ ”、“\ ``extern``\ ”等关键字。这个任务由下面的循环负责，很简单：

    .. literalinclude:: _includes/chapter-2_full.cpp
        :lines: 34-42
        :language: cpp

    注意，标识符一被识别出来就被存入全局变量\ ``IdentifierStr``\ 。此外，语言中的关键字也由这个循环负责识别，在此处一并处理。数值的识别过程与此类似：

    .. literalinclude:: _includes/chapter-2_full.cpp
        :lines: 44-53
        :language: cpp

    处理输入字符的代码简单明了。只要碰到代表数值的字符串，就用C标准库中的\ ``strtod``\ 函数将之转换为数值并存入\ ``NumVal``\ 。注意，这里的错误检测并不完备：这段代码会将“1.23.45.67”错误地识别成“1.23”。改还是不改，那就随你的便了 :-) 。下面我们来处理注释：

    .. literalinclude:: _includes/chapter-2_full.cpp
        :lines: 55-62
        :language: cpp

    注释的处理很简单：直接跳过注释所在的那一行，然后返回下一个语元即可。最后，如果碰到上述情况都处理不了的字符，那么只有两种可能：要么碰到了表示运算符的字符（比如“\ ``+``\ ”），要么就是已经读到了文件末尾。这两种情况由以下代码负责处理：

    .. literalinclude:: _includes/chapter-2_full.cpp
        :lines: 64-72
        :language: cpp

    至此，完整的Kaleidoscope词法分析器就完成了（\ :ref:`完整源码 <chapter-2_full-code>`\ 参见本教程的\ :doc:`下一章 <chapter-2>`\ ）。接下来，我们将\ :doc:`编写一个简单的语法分析器并利用它来构建抽象语法树 <chapter-2>`\ 。届时，我们还会再加上一段引导代码，让词法分析器和语法分析器珠联璧合、天衣无缝。

.. rubric:: 脚注

.. [#] 例如lex/yacc或flex/bison——译者注。
.. [#] 这里指的是编译器或解释器的前端——译者注。
.. [#] Spaghetti Stack，spaghetti的本意是意大利面——译者注。
.. [#] Kaleidoscope意即“万花筒”——译者注。
.. [#] 原文中用的是define；但从上下文来看此处应该是函数原型声明，而非函数定义，故改译作“声明”——译者注。
.. [#] 指函数A调用函数B，函数B又反过来调用函数A，从而形成递归调用的情况——译者注。

.. vim:ft=rst ts=4 sw=4 et wrap
        本章对整个系列教程作出了总结，不仅讨论了多种潜在的语言扩展方向，还针对一系列“专题”给出了参考资料，例如垃圾回收支持、异常、调试、“\ `麻花栈`__\ [#]_\ ”支持等，此外，还提到了很多其他的窍门和技巧。