如何手寫一個簡單的parser

NO IMAGE

前一陣子,收到燁兄的私聊,他突然要解決這樣一個任務:

做如下格式的表達式轉換:

  • Multi(a, Multi(b, c)) --> a * (b * c)
  • Divide(a, Sub(b, c)) --> a / (b - c)

支持的運算符有:

  • Add: +
  • Sub: –
  • Multi: *
  • Divide: /

而且好死不死的需要用他沒怎麼用過的 C++ 來寫。我發現這是一個 parser 的問題,第一反應是推薦他用 flex/bison,但想到為了這麼大點任務大費周章不太合適,又開始想手寫這樣一個表達式的 parser 難不難。最後得出的結論是,不難。

瞭解編譯原理的人都知道什麼是 parser。Parser 中文名(語法)分析器,是每個編譯器的前端都會有的一個東西。不過,從編譯原理的視角來看,“語言”的範疇要比我們理解的編程語言要廣義得多,任何有一定規則的字符串構成方式,都可以看成是語言,例如上面的那個任務裡用 AddSub 這樣的函數描述的表達式。

那麼,要解決上面這個任務,只需要對表達式的字符串進行語法分析,得到一箇中間表示(一般是分析樹或抽象語法樹),再將中間表示輸出為所需的格式即可。也就是說我們需要為表達式提供一個 parser,這個任務的任何解決方式,本質上都可以看成是寫了一個 parser。

在平時,我們完全沒有任何必要去手寫一個 parser,因為這東西已經有工具可以為我們生成。感謝幾十年前偉大的程序員就已經發明瞭這樣的工具。我用過的有 C/C++ 的 flex/bison,以及 Java 的 ANTLR。你只需要提供一個文法描述,這些工具就可以為你自動生成對應的語法分析器。如果要手寫分析器,會很複雜,也很容易出錯,不是一個明智的選擇。

不過,面對上面舉例的這種小任務,使用自動生成 parser 的工具有時候顯得太重了,這時候也許手寫一個 parser 是更好的選擇。而且在這樣的任務場景下,我們的 parser 有兩個地方起碼是可以得到大大簡化的:

第一,我們要處理的語言應該不會像通用編程語言那樣,有很複雜的狀態轉移。通常情況下,應該能看到當前的字符串就知道下面要分析什麼類型的內容。一般標記語言都會是這種風格的,比如:

  • XML/HTML:看到 <tag> 就知道是一個標籤的開始,直到 </tag> 為止
  • CSS:選擇器後的聲明,總是用花括號括起來,每一條聲明以 ; 分隔
  • Markdown:一行以 # 開頭就是標題,以 1. 開頭就是有序列表項

第二,我們不需要進行復雜的語法錯誤處理,只需要報“語法錯誤”就好了,而不需要費力說明到底發生了什麼錯誤。

有了這兩個前提,我們開始思考如何手寫一個語法分析器。當然,我已經思考好了,下面是我給出的一個簡單的分析器的實現。我是用 Java 實現的,用到了一點 lambda 表達式的語法,不過不難理解。因為 parser 的主要工作是做字符串比較,所以用任何語言都差不多。後面我會考慮再用其他語言實現。

在實現上我們再做一點簡化:我們把要分析的字符串作為字符數組保存下來,而不是從所謂“字符流”中讀入。這樣我們不必考慮讀 (get) 了字符卻不用掉 (consume) 的情況下,這些是輸入模塊要考慮的部分,我們專注於 parser 本身。

首先,我們的 SimpleParser 是這樣定義的:

public class SimpleParser {

    private char[] input;
    private int pos;

    public SimpleParser(String source) {
        this.input = source.toCharArray();
        this.pos = 0;
    }
}

我們將輸入保存為字符數組,pos 是一個指向待讀取的下一個字符的指針。將 pos 加一,就相當於從讀入了一個字符。

下面,我們添加一些腳手架函數:

private void consumeWhitespace() {
    consumeWhile(Character::isWhitespace);
}

private String consumeWhile(Predicate<Character> test) {
    StringBuilder sb = new StringBuilder();
    while (!eof() && test.test(nextChar())) {
        sb.append(consumeChar());
    }
    return sb.toString();
}

private char consumeChar() {
    return input[pos++];
}

private boolean startsWith(String s) {
    return new String(input, pos, input.length - pos).startsWith(s);
}

private char nextChar() {
    return input[pos];
}

private boolean eof() {
    return pos >= input.length;
}

這些函數的來源於我之前看過的一個系列文章:Let’s build a browser engine!(原文是用 Rust 語言的)。我們來看一下這幾個函數:

其中,nextChar, startsWith 這兩個函數是用來“向後看”,判斷後面輸入的狀態。這實際上已經和編譯原理中說的語法分析不太一樣了(回憶一下,編譯原理中說的語法分析方法只會向後看一個字符),但是因為我們只是判斷是不是等於一個固定的字符串,所以也不是太大的問題。

consume... 開頭的幾個函數就是真正的讀取輸入的函數了。其中,consumeWhile 是一個通用的函數,consumeWhitespace 也是基於其實現的。類似地,我們還可以基於其實現解析變量名的函數:

private String parseVariableName() {
    return consumeWhile(Character::isAlphabetic);
}

注意到這實際上就是在解析我們任務中的變量名了,以此為思路,後面的實現其實很簡單。我們一上來會覺得手寫 parser 會很複雜,實際上是因為沒找到入手點。所以這幾個腳手架函數特別重要,先有了他們,後面就可以一步一步寫出整個 parser 的功能了。

那麼我們接下來可以這麼寫:

// 解析由單個變量組成的表達式
private VariableExpression parseVariableExpression() {
    String name = parseVariableName();
    // VariableExpression 的定義略
    return new VariableExpression(name);
}
// 解析加減乘除表達式
private CompoundExpression parseCompoundExpression(String name) {
    for (char c : name.toCharArray()) {
        checkState(c == consumeChar());
    }
    checkState('(' == consumeChar());
    // 遞歸解析
    Expression left = parseExpression();
    checkState(',' == consumeChar());
    consumeWhitespace();
    Expression right = parseExpression();
    checkState(')' == consumeChar());
    // CompoundExpression 的定義略
    return new CompoundExpression(name, left, right);
}

// VariableExpression 和 CompoundExpression 都是 Expression
private Expression parseExpression() {
    if (startsWith("Add")) {
        return parseCompoundExpression("Add");
    } else if (startsWith("Sub")) {
        return parseCompoundExpression("Sub");
    } else if (startsWith("Multi")) {
        return parseCompoundExpression("Multi");
    } else if (startsWith("Divide")) {
        return parseCompoundExpression("Divide");
    } else {
        return parseVariableExpression();
    }
}

寫到這裡,我們 parser 的主要工作已經做完了,接下來的任務就非常簡單了。似乎我們的任務有點太簡單了?在這種場景下,手寫 parser 確實不難,接下來可以手寫一個 Markdown 的 parser 練習一下了😜。

P.S. 燁兄後來並沒有做這個任務,我也是到現在才想起來把這個 parser 實現出來,只是我自己覺得好玩想了這件事。

文章中的 parser 的完整代碼,可以到我的 GitHub 上查看:simpleparser

相關文章

RxJS實踐,Vue如何集成RxJS

React使用新版Context構建組件樹工具注入

如何在Koa集成Bigpipe首屏渲染服務

基於webpack工程化的思考