Parsing Expression Grammar(PEG)とは何か？

プログラミング言語を記述するプログラミング言語の”ようなもの”。これを文法といいPEGはその一種。プログラミング言語の書き方はこの文法によって作られている。PEGは正規表現の仲間で正規表現より表現力が高く、正規表現が文字列を処理するように、PEGはソースコードを処理する。つまり、PEGが書ければプログラミング言語を作れる！

ここまでだとPEGというものが何なのかつかみづらいと思われる~~（実際に周りの人にも理解されなかった、、、）~~ので例を挙げて説明しよう。

add <- Integer "+" Integer

これは非常に単純な加算を表したPEGの例だが、「addという構文はInteger'+'Integerと書く」という意味の規則ある。BNF記法を知っていれば理解しやすいと思う。左矢印になっているのはPEG特有だが、基本的にはBNFの:=と同じものだと思って問題ない。BNFを知らない人はaddという変数にInteger'+'Integerが入っているとイメージすると分かりやすいかもしれない。
この例のようにPEGによって構文を構文名<-構文本体で定義できる。この時、右辺を非終端記号（後述）、左辺をParsing Expressionという。これでIF構文、while構文、単項演算、代入文.....など欲しい構文の規則を作っていくと、プログラミング言語を作ることが出来る。構文の規則を集めたものを文法という。

PEGの書き方

実際にPEGの書き方について解説する。下の図はPEGの構文規則A<-eにおけるParsing Expressionについて定義している。ここでAやaやbは任意の文字列を表す。

e := a　　　　　　 \\ 終端記号
     A 　　　　　　\\ 非終端記号
     ε            \\ 空文字列
     e e      \\ 連接
     e *          \\ 0以上の繰り返し
     e / e    \\ 優先度付き選択
     ! e           \\ 否定先読み
     e +       \\ 1以上の繰り返し
     e ?       \\　省略可能
     & e        \\ 肯定先読み
     [a-b]      \\ 文字クラス
     .          \\任意の一文字

基本的には正規表現とほとんど変わらない。この定義は「eは右辺のどれかに置き換えられる」という意味になる。例えば、eをe e(連接)に置き換えたとすると、この連接はeから構成されているので上の定義を適用し、他のParsing Expressionに置き換えられる。これにより、どんな解析表現であっても表現できる。規表現が分からない人は関する記事を合わせて読むと分かりやすいかもしれない。終端記号というのは構文規則に出てくる生の文字列のことだ。大抵の場合は構文規則中に"a"のように文字列だと分かるように現れる。非終端記号はその非終端記号に対応する構文規則を適用することを意味する。例えば以下のような文法があるとしよう。

add <- Integer "+" Integer
Integer <- [0-9] +

この時終端記号は"+",[0-9]で、非終端記号はIntegerとaddになる。非終端記号はその非終端記号に対応するものを適用するとあるが、構文解析における変数のようなものである。例えば、上のものと下のものは等価になる。

add <- [0-9] + "+" [0-9] +

PEGでは正規表現と同じように文字列に左から右に規則を適用することで、文字列が規則にマッチしているか確認する。ほぼ正規表現と同じだが、PEGでは優先度無し選択|の代わりに、優先度付き選択/が用意されている。例えば下のような規則があるとしよう。

Expression <- Integer "+" Integer / Integer "-" Integer / Integer"*" integer 
Integer <- [0-9] +

PEGの優先度付き選択では term "+" term > term "-" term > term "*" termのように前から順に規則が選択される。1*1という入力があったとすれば、まず構文解析器はterm "+" term と入力がマッチするか試すが、入力の形と一致しないためマッチしない。マッチしなかったことを"失敗"といい、失敗したら失敗した規則にマッチを試す前に戻って、次の選択肢を試す。そのため次はterm "-" term とマッチするか試す。これも入力の形と違うのでマッチしない。最後にterm "*" termとマッチするか調べると、これはマッチする。入力がInteger "*" Integerの形をしているからである。

実際にPEGを使ってプログラミング言語を作るには

文法をもとにその文法に対する構文解析器を作ってくれるパーザジェネレータという便利なものがある。そのパーザジェネレータの一種であるPEG.jsというものを紹介する。

PEG.jsはPEG.jsの文法にしたがって書かれたpegjsファイルの文法をもとにJavascriptで書かれたパーザを生成してくれる。PEG.jsの文法は基本的にはPEGと同じだが、<-が=である点や後述のSemantic Actionによる拡張など一部違いがある。このPEG.jsはローカルにインストールしなくてもオンラインバージョンがあるので、webブラウザですぐに試すことができる。試して実際に動かしてみたほうが理解しやすいように思う。

最後にPEG.jsにあるPEGの文法には存在しない機能であるSemantic Actionを開設する。これは構文解析中にプログラムを埋め込める機能である。

add = hoge:Integer "+" foo:Integer {return hoge + foo}

変数名:非終端記号名と書くと、非終端記号の解析結果を変数に束縛できる。つまり上の例ではIntegerの結果をそれぞれhogeとfooに束縛し、それを足し算したものをreturnする（つまりaddの解析結果とする）ことになる。これにより、構文解析結果を操作することが出来ることになる。

まとめ

PEGの位置づけと文法について解説した。紹介したPEGの文法を参考にPEG.jsの文法をPEG.jsに食わせることでパーサを得て、文法にしたがった構文解析器を作れる。

Parsing Expression Grammar(PEG)の使い方

目次

Parsing Expression Grammar(PEG)とは何か？

PEGの書き方

実際にPEGを使ってプログラミング言語を作るには

まとめ

関連した記事

参考文献