学习编译器原理：从解析器看程序设计

---

提到编程，我们会马上想到一些通用的编程语言，比如C、C++、Java、Python、Go等。但是，对于绝大部分软件开发人员来说，不会从零开始设计一门通用的编程语言；更多的情况是设计一门在某一个业务领域使用的语言，也就是我们通常所说的DSL（领域特定语言，Domain Specific Language）。

麻雀虽小，五脏俱全。虽然DSL范围受限，实现相对简单，但是其原理跟通用的编程语言并无本质上的差异。学习编程语言的设计原理，可以帮助我们更好地设计一门DSL，用于解决某个特定领域的问题。

本文尝试介绍语言设计的基本原理，尤其是与Parser相关的内容。利用这些知识，可以帮助我们解决DSL设计过程中的 识别 问题，为后续的 解释、执行 等环节做好准备。

语言设计的全貌

一门编程语言，就是所有合法的语句的集合。使用编程语言编写的程序，在形式上是一连串的字符序列；语言设计的工作，就是将这些字符串最终转化为可以在某一平台上执行的二进制文件，或者是将字符串转为一种中间格式，再通过解释器对其解释执行。

下图是一个编程语言实现中，从输入到输出所涉及的几个的主要环节。

image.png

根据应用场景和使用技术的不同，编程语言可以分为解析器、解释器、翻译器、生成器等多种不同的应用。

例如，对于静态编译型的语言来说，我们需要构造编译器来完成从语法解析、语义分析，到生成机器代码等多个环节，最终实现在某一硬件平台上执行的目标。

同时，对于某些特定领域，我们只需要打造一种专门的语法，通过解析其语法生成一种中间表示（IR, Intermediate representation），而这种中间表示的具体使用则由该领域的应用程序内部来决定。这种类型的应用，往往只会涉及到上图中所示的前面几个阶段，类似于通常编译器设计中的前端（Front End）。我们通常使用XML、JSON作为配置文件，使用正则表达式进行模式匹配；在这些应用场景中，应用程序仅需要解析用这些“语言”编写的“程序”，生成内部使用的中间表示。

解析器（Parser）

编程语言的解析(parsing)，就是通过计算机程序来扫描和识别一系列语句的过程。Parser对字符序列进行扫描，按照语言所定义的规则，生成某一种中间形式的数据结构。

识别短语结构

如同人类处理自然语言时识别出语句中的动词和名词一样，计算机在处理程序时，也会识别出一系列扮演不同角色的语法符号（token），如变量、关键字、操作符等。符号的序列组成表达式（expression），表达式的序列组成语句（statement）。

编译器将文本序列解析为解析树（parse tree）的形式。例如，对于这一条语句：

if  x < 0 then x = 0;

其解析之后的解析树的结果为下图所示：

parse tree

从上面生成解析树的过程可以看出，解析（parsing）的过程就是由扁平的符号序列构建二维解析树的过程。

构建递归下降解析器

在对字符序列解析过程中使用一个游标来指示字符的当前位置，在初始时它指向第一个符号。
解析过程中，根据当前游标所指的token类型执行不同的操作。例如，如果是return，则表示这是一个return语句；如果是一个标识符，则表示这是一个赋值语句。这个用于判断语句类型的token，被称为lookahead token。
用代码描述就是这样的：

void stat() {
    if ( «lookahead token is return» ) returnstat();
    else if ( «lookahead token is identifier» ) assign(); 
    else if ( «lookahead token is if» ) ifstat(); 
    else «parse error»;
}

如果从parse tree的角度来看，上述解析的过程就是从根节点从上向下，不断递归，识别根节点的过程。因此，这个解析的过程也被称为递归下降解析器。

LL(1)、LL(2)与LL(k)

上面构建的递归下降解析器，也被称为LL解析器。第一个L是指读取输入的字符序列从左往右，第二个L指递归访问解析树时，对孩子节点的访问顺序是从左往右。根据使用 lookahead token 的多少，可以分为LL(1)、LL(2)以及LL(k)，括号中的数字就是向前看的、用于判断语句类型的符号的个数。
在上面的例子中，根据一个符号就可以判断出return、identifer、if等不同的类型，所以是一个 LL(1) parser。

Case Study: JSON解析器

JSON（JavaScript Object Notation，JavaScript对象表示法）是一种轻量级的数据交换语言，该语言以易于让人阅读的文字为基础，用来传输由属性值或者序列性的值组成的数据对象。虽然脱胎于 JavaScript，但JSON 数据格式与编程语言无关，很多编程语言都支持 JSON 格式数据的生成和解析。

在JSON中，一共有以下这么几种基本数据类型，以及它们的任意组合：

• 字符串：以""括起来的一串字符。
• 数值：一系列0-9的数字组合，可以为负数或者小数。还可以用e或者E表示为指数形式。
• 布尔值：表示为true 或者false。
• 值的有序列表（array）：一个或者多个值用,分割后，使用[，]括起来就形成了这样的列表，形如：[value, value]。
• 对象（object）：一个对象包含一系列非排序的 名称/值对 (pair)，一个对象以{开始，并以}结束。每个 名称/值 对之间使用:分割。
• 数组 (array)：一个数组是一个值(value)的集合，一个数组以[开始，并以]结束。数组成员之间使用,分割。
• 名称/值（pair）：名称和值之间使用 : 隔开，一般的形式是：{name:value}。一个名称是一个字符串， 一个值(value)可以是一个字符串(string)，一个数值(number)，一个对象(object)，一个布尔值(bool)，一个有序列表(array)，或者一个null值。

Jansson解析示例

Jansson是一个用于编码、解析和操作JSON数据的C语言库。下面这段代码是其中JSON字符串解析的核心逻辑。
其中的第一个参数lex是一个词法分析器，完成对JSON字符串的扫描，识别出其中的符号(token)序列。

static json_t *parse_value(lex_t *lex, size_t flags, json_error_t *error)
{
    json_t *json;
    
    //...
    switch(lex->token) {
        case TOKEN_STRING: {
            const char *value = lex->value.string.val;
            size_t len = lex->value.string.len;

            if(!(flags & JSON_ALLOW_NUL)) {
                if(memchr(value, '\0', len)) {
                    error_set(error, lex, json_error_null_character, "\\u0000 is not allowed without JSON_ALLOW_NUL");
                    return NULL;
                }
            }

            json = jsonp_stringn_nocheck_own(value, len);
            lex->value.string.val = NULL;
            lex->value.string.len = 0;
            break;
        }

        case TOKEN_INTEGER: {
            json = json_integer(lex->value.integer);
            break;
        }

        case TOKEN_REAL: {
            json = json_real(lex->value.real);
            break;
        }

        case TOKEN_TRUE:
            json = json_true();
            break;

        case TOKEN_FALSE:
            json = json_false();
            break;

        case TOKEN_NULL:
            json = json_null();
            break;

        case '{':
            json = parse_object(lex, flags, error);
            break;

        case '[':
            json = parse_array(lex, flags, error);
            break;

        case TOKEN_INVALID:
            error_set(error, lex, json_error_invalid_syntax, "invalid token");
            return NULL;

        default:
            error_set(error, lex, json_error_invalid_syntax, "unexpected token");
            return NULL;
    }
    //....
    return json;
}

以上解析的过程，就是根据当前token的类型，识别出相应的“语句”。
例如：根据符号的类型为TOKEN_STRING、TOKEN_INTEGER、TOKEN_REAL、TOKEN_TRUE、TOKEN_FALSE、TOKEN_NULL等值，分别识别出字符串、实数、布尔值、NULL等语句；如果当前符号是{，则表示一个object的开始；符号}则表示一个object的结束。

以上根据当前所指的1个token来识别和解析“语言”的过程，可以看做是一个LL(1)解析器。

小结

本文介绍了编译器设计中的基本原理，尤其是跟解析器相关的技术和方法，并以Jansson库中JSON字符串的解析为例进行了说明。
编译器设计号称是程序设计领域中的皇冠。学习和了解其中的方法和技术，也可以帮助我们更好地进行应用程序的设计和开发。

扩展阅读

• Language Implementation Patterns
  

• Engineering a Compiler
  image.png