Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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

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

左再帰

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

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

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

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

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

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ライブラリです。

中置演算子

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のような感じですね。しかし多くの演算子を持つ実用的な言語を実装するときには助けとなるでしょう。

文脈依存パース

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ライブラリの様々な試みを見てみました。この分野での研究はまだ進んでいるようですので、いずれまた調査してみたいと思います。

yhirose
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away