[Perl] 以正規表示式來定義文法規則

Perl 語言中的正規表示式引擎在經過歷年來的擴充與改進，已經變成一種十分驚人的狀態機了，其能力遠超過教科書上所描述的「正規表示式」太多，基本上可以已經可以用來定義文法規則，並且可以直接而拿來定義一個遞歸下降解析器。

在拜讀 perlre 文件、Damian Conway 的 PPR 程式碼以及 Tom Christiansen 在 stackoverflow 上的幾篇文章之後，就想說來隨便找個語言來做個解析器看看。沒想到不太困難。

我用來學習這部分的對象是 JSON -- 是個已經很熟悉的小語言，並且在 json.org 首頁上就直接就有完整的文法規則可用。我不必費心定義，只要翻譯就可以了。

以下這個 $JSON_GRAMMAR 變數，裝的就是可以解析一個 JSON 文件的語法規則。除了有些不太尋常的括號之外，基本上就是與 json.org 上提供的語法規則逐一對應而已。

my $JSON_GRAMMAR = qr{
    (?(DEFINE)
        (?<JSON>       (?&element) )
        (?<object>     (  { (?&ws)  }   |  { (?&members) }) )
        (?<array>      ( \[ (?&ws) \]   | \[ (?&elements) \] ) )
        (?<elements>   ( (?&element) | (?&element) , (?&elements)) )
        (?<members>    ( (?&member)  | (?&member) , (?&members) ) )
        (?<element>    (?&ws) (?&value) (?&ws))
        (?<member>     (?&ws) (?&string) (?&ws) : (?&element) )
        (?<value>      ( (?&object) | (?&array) | (?&string) | (?&number) | true | false | null ) )
        (?<number>     (?&integer) (?&fraction) (?&exponent) )
        (?<integer>    ( (?&digit) | (?&onenine) (?&digits) | - (?&digit) | - (?&onenine) (?&digits) ) )
        (?<digits>     ( (?&digit) | (?&digit) (?&digits) ) )
        (?<fraction>   ( | \. (?&digits) ) )
        (?<exponent>   ( | e (?&sign) (?&digits) | E (?&sign) (?&digits) ) )
        (?<sign>       ( | \+ | - ) )
        (?<digit>      ( 0 | (?&onenine) ) )
        (?<onenine>    [123456789] )
        (?<string>     " (?&characters) " )
        (?<characters> ( | (?&character) (?&characters) ) )
        (?<character>  ( [^\"\\] | \\ (?&escape) ) )
        (?<escape>     ( \\ | ["bfnrt/] | u (?&hex)(?&hex)(?&hex)(?&hex) ) )
        (?<hex>        ( (?&digit) | [abcdef] | [ABCDEF] ))
        (?<ws>         ( | \x{0020} (?&ws) | \x{000A} (?&ws) | \x{000D} (?&ws) | \x{0009} (?&ws) ) )
    )
}x;

可以配合 m// 運算符來使用：

if ($text =~ m/ $JSON_GRAMMAR \A (?&JSON) \z/x) {
    say "Valid JSON!";
} else {
    die "Invalid JSON";
}

可以看到基本上 $JSON_GRAMMAR 內是一個很大的 (?(DEFINE) ... ) 結構。這個 DEFINE 關鍵字，就是用來定義各條可重複利用的語法規則。而且，還可以遞迴。

每條語法規則最左邊 ?<...> 這組括號內的字是這規則的名字，而右側則是這條規則所對應到的正規表示式。其中 (?&...) 這種括號表示參照到某一條規則。可以參照到其他條規則，也可參照到目前這條規則。規則定義的次序似乎不影響結果，只要在同一個 (?(DEFINE) ... ) 結構內就可以。

像是能對應到 JSON 中數字的名爲 number 的這條規則，就是定義爲： integer 後接 fraction，再接 exponent。

(?<number>     (?&integer) (?&fraction) (?&exponent) )

熟悉 yacc 的話可能會覺得這語法真是拖泥帶水，各種環綴符號真是有夠礙眼的。不過仔細閱讀一陣子之後還算可以理解。

但既然這本身是一條正規表示式，其實有不少部分可以直接使用正規表示式與生俱來的咒力(?)來處理。比方說這條規則表示：空字串或加號或減號：

(?<sign>       ( | \+ | - ) )

其實可以簡化成：

(?<sign>       [\+\-]? )

或是這種表示一個以上的 digit 重複出現的規則：

(?<digits>     ( (?&digit) | (?&digit) (?&digits) ) )

其實就等同於於：

(?<digits>     (?&digit)+ )

比起 Raku Grammar 或是 yacc 等能生成解析器產生器的工具而言，要習慣這個語法大概會要多花一點時間。但可以看到 Perl 的正規表示式這個語言真的完全長成另外一支語言，也完全超出了一般教科書上的規格了。而既然可以完整解析一個語言，也就可以做出編譯器，在碰到各條規則時採取相對應的行動。這方面需要在正規表示式中內嵌 Perl 程式碼，等日後再研究看看。