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

[Kang-min Liu]

https://gugod.org/2022/07/perl-grammar-with-regex/

全文轉貼

----8<----

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 程式碼，等日後再研究看看。