PEGを書きやすくする拡張構文の調査（構文ルール編）

字句ルール編からかなり日が空いてしまいましたが、続いて構文ルールについても調査してみました。

• 左再帰
• Metaルール
• 中置演算子
• 文脈依存パース

左再帰

オリジナルのPEGは、以下のような左再帰文法を扱うことができません。パース時に無限ループに陥ってしまいます。

// 直接左再帰（Aの再帰）
A <- A "a"

// 間接左再帰 (Bの再帰)
A <- B "a"
B <- C "b"
C <- B / A / "c"

左再帰文法を扱えるようにするアルゴリズムがいろいろと研究されています。

• Packrat Parsers Can Support Left Recursion
• Hacker News (上記のアルゴリズムが正しく動作しない実例)
• 左再帰に対応する Packrat Parser の実装
• Left Recursion in Parsing Expression Grammars

しかしシンプルな実装が難しいためか、PEG.js、rust-peg、parboiled2などの人気のあるライブラリでも、左再帰文法をサポートしない、さらにはサポートするつもりはないとしています。

左再帰をサポートすると表明するライブラリもあります。

• Peggy (Support left recursion)
• Rats! (Left-Recursive Productions)
• ScanRat (Direct and mutual left recursion)
• Rattler
• IronMeta

Metaルール

ライブラリによって、マクロ、テンプレート、パラメタライズド・ルールなど様々な呼ばれ方をします。
この拡張によって、似たようなルールの重複をなくすことができます。文法の規模が大きくなるにつれて、とても役立つ機能です。

rust-pegの例ですが、keyword<E>Metaルールに空白処理を含めています。

keyword<E> = E !identifierChar whitespace*

STRUCT = keyword<"struct">
ENUM = keyword<"enum">

もしこのMetaルールを使用しない場合、以下のように各キーワード毎に空白処理を含めなければなくなります。

STRUCT = "struct" !identifierChar whitespace*
ENUM = "enum" !identifierChar whitespace*

以下はPeggedのドキュメントに載せられていた、Listルールの例です。

List(Elem, Sep) <  Elem (Sep Elem)*
ArgList <- '(' List(Identifier, ',') ')'

Elem (Sep Elem)*がListと簡潔に名前付けされて、文法が読みやすくなります。

現段階でMetaルールをサポートするPEGライブラリです。

• Pegged (Parameterized Rules)
• Parpoiled2 (Meta-Rules)
• rust-peg (Template rules)
• Macro PEG (PEG with macro-like rules)

中置演算子

1*(2+3)*4のような優先順位が関係する中置記法を扱う場合、通常以下のように演算子レベルことにネストさせてルールを定義します。

Additive    <- Multitive [-+] Additive / Multitive
Multitive   <- Primary [/*] Multitive / Primary
Primary     <- '(' Additive ')' / Number
Number      <- < [0-9]+ >

特に問題ないように見えます。しかしこの方法は、演算子レベルが増加するに連れてネストが深くなり、CやJavaScriptのような相当数の演算子を持つ言語を定義しようとなると、文法はすぐに肥大化してしまいます。また演算子によっては、結合順序が右結合のものもあり、頭を悩ませます。

PEGライブラリの中には、中置演算子の文法を簡潔に記述できるようにしているものがあります。

例えばrust-pegでは、以下のような表記が可能です。（使用しているアルゴリズムは Precedence Climbing Algorithmです。）

pub arithmetic -> i64 = #infix<number> {
    #L x "+" y { x + y }
       x "-" y { x - y }
    #L x "*" y { x * y }
       x "/" y { x / y }
    #R x "^" y { x.pow(y as u32) }
}

ここまで来ると、単なるPEGの拡張というよりも、中置構文DSLのような感じですね。しかし多くの演算子を持つ実用的な言語を実装するときには助けとなるでしょう。

• rust-peg (Infix expressions)

文脈依存パース

PEGでは、<A><B><C>...</C></B></A>のようなXMLタグの文法を記述する場合、次のように書くかもしれません。（見やすさのために簡略化しています。）

Element = '<' Name '>'  (Element / Content) '</' Name '>'

これでタグは正しく解析できますが、開始タグと終了タグのタグ名の整合性まではチェックしてくれません。通常このような文脈依存の解析は、後段の意味解析フェーズに任せます。

しかし、こうした文脈情報をルール上に記述する試みもあります。例えばNezライブラリでは、文法上に文脈依存情報を記述可能です。

Element = <block '<' $key(<symbol Name>) '>' (Element / Content) '</' ~(<is Name>) '>' >

少々複雑に見えますが、block, $Key(...), isなどの拡張キーワードを使って、ネストされたXMLの開始タグ名と終了タグ名の整合性まで、パース時に正しくチェックしてくれます。
これにより、パース後の処理が非常に楽になります。強力な機能ですね。

AutumnというKotlinで書かれたパーサーコンビネータライブラリも、こうした文脈情報を扱えるそうです。

まとめ

オリジナルのPEGはシンプルで扱いやすいですが、実用的な文法を定義するためには力不足なところもあります。それを解決するための、PEGライブラリの様々な試みを見てみました。この分野での研究はまだ進んでいるようですので、いずれまた調査してみたいと思います。