提到編程，我們會(huì)馬上想到一些通用的編程語(yǔ)言，比如C、C++、Java、Python、Go等。但是，對(duì)于絕大部分軟件開(kāi)發(fā)人員來(lái)說(shuō)，不會(huì)從零開(kāi)始設(shè)計(jì)一門(mén)通用的編程語(yǔ)言；更多的情況是設(shè)計(jì)一門(mén)在某一個(gè)業(yè)務(wù)領(lǐng)域使用的語(yǔ)言，也就是我們通常所說(shuō)的DSL（領(lǐng)域特定語(yǔ)言，Domain Specific Language）。

麻雀雖小，五臟俱全。雖然DSL范圍受限，實(shí)現(xiàn)相對(duì)簡(jiǎn)單，但是其原理跟通用的編程語(yǔ)言并無(wú)本質(zhì)上的差異。學(xué)習(xí)編程語(yǔ)言的設(shè)計(jì)原理，可以幫助我們更好地設(shè)計(jì)一門(mén)DSL，用于解決某個(gè)特定領(lǐng)域的問(wèn)題。

本文嘗試介紹語(yǔ)言設(shè)計(jì)的基本原理，尤其是與Parser相關(guān)的內(nèi)容。利用這些知識(shí)，可以幫助我們解決DSL設(shè)計(jì)過(guò)程中的 識(shí)別 問(wèn)題，為后續(xù)的 解釋、執(zhí)行 等環(huán)節(jié)做好準(zhǔn)備。

語(yǔ)言設(shè)計(jì)的全貌

一門(mén)編程語(yǔ)言，就是所有合法的語(yǔ)句的集合。使用編程語(yǔ)言編寫(xiě)的程序，在形式上是一連串的字符序列；語(yǔ)言設(shè)計(jì)的工作，就是將這些字符串最終轉(zhuǎn)化為可以在某一平臺(tái)上執(zhí)行的二進(jìn)制文件，或者是將字符串轉(zhuǎn)為一種中間格式，再通過(guò)解釋器對(duì)其解釋執(zhí)行。

下圖是一個(gè)編程語(yǔ)言實(shí)現(xiàn)中，從輸入到輸出所涉及的幾個(gè)的主要環(huán)節(jié)。

image.png

根據(jù)應(yīng)用場(chǎng)景和使用技術(shù)的不同，編程語(yǔ)言可以分為解析器、解釋器、翻譯器、生成器等多種不同的應(yīng)用。

例如，對(duì)于靜態(tài)編譯型的語(yǔ)言來(lái)說(shuō)，我們需要構(gòu)造編譯器來(lái)完成從語(yǔ)法解析、語(yǔ)義分析，到生成機(jī)器代碼等多個(gè)環(huán)節(jié)，最終實(shí)現(xiàn)在某一硬件平臺(tái)上執(zhí)行的目標(biāo)。

同時(shí)，對(duì)于某些特定領(lǐng)域，我們只需要打造一種專(zhuān)門(mén)的語(yǔ)法，通過(guò)解析其語(yǔ)法生成一種中間表示（IR, Intermediate representation），而這種中間表示的具體使用則由該領(lǐng)域的應(yīng)用程序內(nèi)部來(lái)決定。這種類(lèi)型的應(yīng)用，往往只會(huì)涉及到上圖中所示的前面幾個(gè)階段，類(lèi)似于通常編譯器設(shè)計(jì)中的前端（Front End）。我們通常使用XML、JSON作為配置文件，使用正則表達(dá)式進(jìn)行模式匹配；在這些應(yīng)用場(chǎng)景中，應(yīng)用程序僅需要解析用這些“語(yǔ)言”編寫(xiě)的“程序”，生成內(nèi)部使用的中間表示。

解析器（Parser）

編程語(yǔ)言的解析(parsing)，就是通過(guò)計(jì)算機(jī)程序來(lái)掃描和識(shí)別一系列語(yǔ)句的過(guò)程。Parser對(duì)字符序列進(jìn)行掃描，按照語(yǔ)言所定義的規(guī)則，生成某一種中間形式的數(shù)據(jù)結(jié)構(gòu)。

識(shí)別短語(yǔ)結(jié)構(gòu)

如同人類(lèi)處理自然語(yǔ)言時(shí)識(shí)別出語(yǔ)句中的動(dòng)詞和名詞一樣，計(jì)算機(jī)在處理程序時(shí)，也會(huì)識(shí)別出一系列扮演不同角色的語(yǔ)法符號(hào)（token），如變量、關(guān)鍵字、操作符等。符號(hào)的序列組成表達(dá)式（expression），表達(dá)式的序列組成語(yǔ)句（statement）。

編譯器將文本序列解析為解析樹(shù)（parse tree）的形式。例如，對(duì)于這一條語(yǔ)句：

if  x < 0 then x = 0;

其解析之后的解析樹(shù)的結(jié)果為下圖所示：

parse tree

從上面生成解析樹(shù)的過(guò)程可以看出，解析（parsing）的過(guò)程就是由扁平的符號(hào)序列構(gòu)建二維解析樹(shù)的過(guò)程。

構(gòu)建遞歸下降解析器

在對(duì)字符序列解析過(guò)程中使用一個(gè)游標(biāo)來(lái)指示字符的當(dāng)前位置，在初始時(shí)它指向第一個(gè)符號(hào)。
解析過(guò)程中，根據(jù)當(dāng)前游標(biāo)所指的token類(lèi)型執(zhí)行不同的操作。例如，如果是return，則表示這是一個(gè)return語(yǔ)句；如果是一個(gè)標(biāo)識(shí)符，則表示這是一個(gè)賦值語(yǔ)句。這個(gè)用于判斷語(yǔ)句類(lèi)型的token，被稱(chēng)為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的角度來(lái)看，上述解析的過(guò)程就是從根節(jié)點(diǎn)從上向下，不斷遞歸，識(shí)別根節(jié)點(diǎn)的過(guò)程。因此，這個(gè)解析的過(guò)程也被稱(chēng)為遞歸下降解析器。

LL(1)、LL(2)與LL(k)

上面構(gòu)建的遞歸下降解析器，也被稱(chēng)為L(zhǎng)L解析器。第一個(gè)L是指讀取輸入的字符序列從左往右，第二個(gè)L指遞歸訪問(wèn)解析樹(shù)時(shí)，對(duì)孩子節(jié)點(diǎn)的訪問(wèn)順序是從左往右。根據(jù)使用 lookahead token 的多少，可以分為LL(1)、LL(2)以及LL(k)，括號(hào)中的數(shù)字就是向前看的、用于判斷語(yǔ)句類(lèi)型的符號(hào)的個(gè)數(shù)。
在上面的例子中，根據(jù)一個(gè)符號(hào)就可以判斷出return、identifer、if等不同的類(lèi)型，所以是一個(gè) LL(1) parser。

Case Study: JSON解析器

JSON（JavaScript Object Notation，JavaScript對(duì)象表示法）是一種輕量級(jí)的數(shù)據(jù)交換語(yǔ)言，該語(yǔ)言以易于讓人閱讀的文字為基礎(chǔ)，用來(lái)傳輸由屬性值或者序列性的值組成的數(shù)據(jù)對(duì)象。雖然脫胎于 JavaScript，但JSON 數(shù)據(jù)格式與編程語(yǔ)言無(wú)關(guān)，很多編程語(yǔ)言都支持 JSON 格式數(shù)據(jù)的生成和解析。

在JSON中，一共有以下這么幾種基本數(shù)據(jù)類(lèi)型，以及它們的任意組合：

• 字符串：以""括起來(lái)的一串字符。
• 數(shù)值：一系列0-9的數(shù)字組合，可以為負(fù)數(shù)或者小數(shù)。還可以用e或者E表示為指數(shù)形式。
• 布爾值：表示為true 或者false。
• 值的有序列表（array）：一個(gè)或者多個(gè)值用,分割后，使用[，]括起來(lái)就形成了這樣的列表，形如：[value, value]。
• 對(duì)象（object）：一個(gè)對(duì)象包含一系列非排序的 名稱(chēng)/值對(duì) (pair)，一個(gè)對(duì)象以{開(kāi)始，并以}結(jié)束。每個(gè) 名稱(chēng)/值 對(duì)之間使用:分割。
• 數(shù)組 (array)：一個(gè)數(shù)組是一個(gè)值(value)的集合，一個(gè)數(shù)組以[開(kāi)始，并以]結(jié)束。數(shù)組成員之間使用,分割。
• 名稱(chēng)/值（pair）：名稱(chēng)和值之間使用 : 隔開(kāi)，一般的形式是：{name:value}。一個(gè)名稱(chēng)是一個(gè)字符串， 一個(gè)值(value)可以是一個(gè)字符串(string)，一個(gè)數(shù)值(number)，一個(gè)對(duì)象(object)，一個(gè)布爾值(bool)，一個(gè)有序列表(array)，或者一個(gè)null值。

Jansson解析示例

Jansson是一個(gè)用于編碼、解析和操作JSON數(shù)據(jù)的C語(yǔ)言庫(kù)。下面這段代碼是其中JSON字符串解析的核心邏輯。
其中的第一個(gè)參數(shù)lex是一個(gè)詞法分析器，完成對(duì)JSON字符串的掃描，識(shí)別出其中的符號(hào)(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;
}

以上解析的過(guò)程，就是根據(jù)當(dāng)前token的類(lèi)型，識(shí)別出相應(yīng)的“語(yǔ)句”。
例如：根據(jù)符號(hào)的類(lèi)型為TOKEN_STRING、TOKEN_INTEGER、TOKEN_REAL、TOKEN_TRUE、TOKEN_FALSE、TOKEN_NULL等值，分別識(shí)別出字符串、實(shí)數(shù)、布爾值、NULL等語(yǔ)句；如果當(dāng)前符號(hào)是{，則表示一個(gè)object的開(kāi)始；符號(hào)}則表示一個(gè)object的結(jié)束。

以上根據(jù)當(dāng)前所指的1個(gè)token來(lái)識(shí)別和解析“語(yǔ)言”的過(guò)程，可以看做是一個(gè)LL(1)解析器。

小結(jié)

本文介紹了編譯器設(shè)計(jì)中的基本原理，尤其是跟解析器相關(guān)的技術(shù)和方法，并以Jansson庫(kù)中JSON字符串的解析為例進(jìn)行了說(shuō)明。
編譯器設(shè)計(jì)號(hào)稱(chēng)是程序設(shè)計(jì)領(lǐng)域中的皇冠。學(xué)習(xí)和了解其中的方法和技術(shù)，也可以幫助我們更好地進(jìn)行應(yīng)用程序的設(shè)計(jì)和開(kāi)發(fā)。

擴(kuò)展閱讀

• Language Implementation Patterns
  

• Engineering a Compiler
  
  image.png