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

麻雀雖小，五臟俱全。雖然DSL范圍受限，實現(xiàn)相對簡單，但是其原理跟通用的編程語言并無本質上的差異。學習編程語言的設計原理，可以幫助我們更好地設計一門DSL，用于解決某個特定領域的問題。

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

語言設計的全貌

一門編程語言，就是所有合法的語句的集合。使用編程語言編寫的程序，在形式上是一連串的字符序列；語言設計的工作，就是將這些字符串最終轉化為可以在某一平臺上執(zhí)行的二進制文件，或者是將字符串轉為一種中間格式，再通過解釋器對其解釋執(zhí)行。

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

image.png

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

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

同時，對于某些特定領域，我們只需要打造一種專門的語法，通過解析其語法生成一種中間表示（IR, Intermediate representation），而這種中間表示的具體使用則由該領域的應用程序內部來決定。這種類型的應用，往往只會涉及到上圖中所示的前面幾個階段，類似于通常編譯器設計中的前端（Front End）。我們通常使用XML、JSON作為配置文件，使用正則表達式進行模式匹配；在這些應用場景中，應用程序僅需要解析用這些“語言”編寫的“程序”，生成內部使用的中間表示。

解析器（Parser）

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

識別短語結構

如同人類處理自然語言時識別出語句中的動詞和名詞一樣，計算機在處理程序時，也會識別出一系列扮演不同角色的語法符號（token），如變量、關鍵字、操作符等。符號的序列組成表達式（expression），表達式的序列組成語句（statement）。

編譯器將文本序列解析為解析樹（parse tree）的形式。例如，對于這一條語句：

if  x < 0 then x = 0;

其解析之后的解析樹的結果為下圖所示：

parse tree

從上面生成解析樹的過程可以看出，解析（parsing）的過程就是由扁平的符號序列構建二維解析樹的過程。

構建遞歸下降解析器

在對字符序列解析過程中使用一個游標來指示字符的當前位置，在初始時它指向第一個符號。
解析過程中，根據(jù)當前游標所指的token類型執(zhí)行不同的操作。例如，如果是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的角度來看，上述解析的過程就是從根節(jié)點從上向下，不斷遞歸，識別根節(jié)點的過程。因此，這個解析的過程也被稱為遞歸下降解析器。

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

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

Case Study: JSON解析器

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

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

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

Jansson解析示例

Jansson是一個用于編碼、解析和操作JSON數(shù)據(jù)的C語言庫。下面這段代碼是其中JSON字符串解析的核心邏輯。
其中的第一個參數(shù)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;
}

以上解析的過程，就是根據(jù)當前token的類型，識別出相應的“語句”。
例如：根據(jù)符號的類型為TOKEN_STRING、TOKEN_INTEGER、TOKEN_REAL、TOKEN_TRUE、TOKEN_FALSE、TOKEN_NULL等值，分別識別出字符串、實數(shù)、布爾值、NULL等語句；如果當前符號是{，則表示一個object的開始；符號}則表示一個object的結束。

以上根據(jù)當前所指的1個token來識別和解析“語言”的過程，可以看做是一個LL(1)解析器。

小結

本文介紹了編譯器設計中的基本原理，尤其是跟解析器相關的技術和方法，并以Jansson庫中JSON字符串的解析為例進行了說明。
編譯器設計號稱是程序設計領域中的皇冠。學習和了解其中的方法和技術，也可以幫助我們更好地進行應用程序的設計和開發(fā)。

擴展閱讀

• Language Implementation Patterns
  

• Engineering a Compiler
  
  image.png