Zenn
🦔

PEGパーサを布教してみる

2021/02/03に公開
コンパイラ
math
math
言語処理系
PEG
tech

この記事は？

この記事では、文脈自由文法や正規表現とは異なる新興のメタ文法「Parsing Expression Grammar」について書いてあります。正規表現やEBNFについて知識がある方を対象にしています。

Parsing Expression Grammar

Parsing Expression Grammar（PEG） （日本語では解析表現文法と訳されることが多いです。）とは2004年にB.Fordさんが提案した文法です。

古来からある文脈自由文法（Context Free Grammar略してCFG）や正規表現（Regular Expression略してRE）と同じ文法の仲間です。CFGと同じようにプログラミング言語の文法記述に利用できます。PEGがCFGと違うのは以下の点です。

  • 字句解析器がいらない
  • CFGとは違う言語クラスが定義できる
  • 曖昧さがない

１つめはPEGでは字句解析フェーズを飛ばすことができることを意味します。CFGでのLL(1)構文解析は行う前に字句解析が必要です。

２つめはPEGがCFGとは違う言語クラスを表していることを示しています[1]。つまり、従来は書けなかった構造の文法を記述することができます。

3つめはCFGやREに存在する|が存在しないということです。PEGでは|の代わりに/が導入されたことで、ある入力に対して構文木が一意に定まります。/の意味については後述します。

文法

まずは文法の簡単な解説をします。文法とはプログラミング言語を記述するプログラミング言語のようなもので、記号Aをある記号Bに置き換えるルールの集合です。

身近な文法の仲間として正規表現があります。プログラミング言語を記述するのによく使われる、EBNF記法で記述された文脈自由文法（CFG）も仲間です。

PEGの簡単な例ex1から紹介します。

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

これは「記号addは記号Integer'+'Integerに置き換える」と読めます。基本的に<-はEBNFの:=と置き換えて呼んでもらって同じものだと思って問題ありません。

ex1のようにPEGの構文ルールは構文名<-構文内容[2]で定義できます。この時、右辺を非終端記号（後述）、左辺をParsing Expressionと言います。IF文、while文、単項演算、代入文など欲しい構文ルールを作っていくと、プログラミング言語を作ることが出来ます。このような構文ルールの集まりが文法です。

終端記号と非終端記号について少し書いておきます。終端記号というのは構文ルールに出てくる文字列のことです。大抵の場合は構文ルール中に"+"や"("のように現れます。

非終端記号はその非終端記号に対応する構文ルールを適用することを意味しています。もう一度ex1を利用して考えます。

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

この時終端記号は"+",[0-9]で非終端記号はIntegerとaddです。非終端記号は構文解析における変数のようなもので、ex1を展開すると下のようになります。

展開後
add <- [0-9] + "+" [0-9] +

PEGの記法

PEGの正確な定義について解説します。PEGの文法がCFGなどと大きく異なるのは|が/になっていることでした。

まず、下の図はPEGの構文規則A<-eにおける解析表現（Parsing Expression）を再帰的に定義しています。

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

慣例としてAのような大文字は非終端記号、aやbは終端記号です。この定義は 「解析表現eは右辺のどれかに置き換えられる」 という意味になります。

実際に適用してみましょう。まず、解析表現はeから始まります。eから連接を適用します。

e \rightarrow e e

eに優先度付き選択と、終端記号を適用します。

e e \rightarrow a e / e

eに、非終端記号と終端記号を適用します。

a e/e \rightarrow a a / A

このように繰り返し適用していけば、任意の解析表現が表現できます。eが右辺にも登場するような再帰的な定義になっています。

PEGでもCFGやREと同じように文字列に左から右に規則を適用することで、文字列が規則にマッチしているか確認しますがPEGでは優先度無し選択|の代わりに、優先度付き選択/が用意されています。優先度付き選択の意味は、「マッチするかどうか試し、失敗したら次の選択肢を試す」です。例えば下のような規則があるとしましょう。

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

CFGなどの文法では

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

と表現されます。これは実は先読み一つで構文解析できませんが、選択できるとしたら、その優先度は以下のようになります。

Integer + Integer = Integer - Integer = Integer * Integer

一方、PEGの優先度付き選択では

Integer + Integer > Integer - Integer > Integer * Integer

のように前から順に規則が選択されます。1*1という入力があったとしましょう。まず構文解析器はInteger "+" Integer と入力がマッチするか試すが、入力の形と一致しないためマッチしません。

マッチしなかったことを"失敗"といい、失敗したら失敗した規則にマッチを試す前に戻って、次の選択肢を試します。次はInteger "-" Integer とマッチするか試しますが、これも入力の形と違うのでマッチしないので戻って、Integer "*" Integerとマッチするか調べるとマッチするので終了します。

否定または肯定先読みはeを先読みして、マッチしていれば、その選択肢を失敗または成功させます。例えば次のように使います。

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

この例では[a-z]つまり小文字のアルファベットとマッチするかどうか先読みします。マッチしていればInteger "+" Integerが失敗し、していなければ成功します。肯定先読みであればその逆になります。
先読みは空文字を先読みすることによって、EOFの検出等に使われます。

欠点

PEGはすごい！という話をここまで続けてきましたが、PEGには大きな欠点が二つあります。まずひとつは

  • 文法制作者にとって直感的でない振る舞いをすること

です。文法制作者は端的にはプログラミング言語を作る人のことです。次のような文法があるとしましょう。

UnaryExpression <- Integer / Integer　UnaryOperator
UnaryOperator <- "++" / "--"
Integer <- [0-9]+

この文法は``か[0-9]+ "++"か[0-9]+ "--"にマッチしてほしいという思いをこめて作りました。しかし、この文法に問題があります。この文法に対して5++という入力を与えてみると、必ずIntegerの選択肢にマッチして、Integer　UnaryOperatorに到達しません。

これはPrefix Capture(詳しくは参考文献の二番目の論文)などど呼ばれています。このように単純な文法ならば簡単に発見できますが、非終端記号から推移的に辿っていった時にマッチする文法が一つあるだけでPrefix Captureになりえます。

これを避けるテクがあるのですが、筆者が考えたものなので脚注においておきます[3].

もう一つの欠点は

  • 工夫をしないと遅いこと

です。PEGはGreedyに文法を試すため、構文解析に時間がかかります。例えば次のような文法を考えましょう。

Statement <- Expression ";"  / "while" "(" Expression ")" Statement / "{" Statement "}"
Expression <- Additive ("+" Additive | "-" Additive)*
...

CFGでは先読みをしてどの文法にマッチするか選ぶので、Statementの選択肢のうちひとつを構文解析するだけです。

しかし、PEGでは先読みして選択するのではなく失敗を繰り返してマッチする文法に至るため、
"{" Statement "}"にマッチさせるには
Expression ";" / "while" "(" Expression ")" Statement の選択肢を試してからでなければなりません。この問題は文法が大きくなるほど、大きな性能低下に繋がります。

これについてはメモ化を利用して解消する方法があります。解決する手法をPackrat Parsingといいます。

まとめ

Parsing Expression Grammarについてまとめました。PEGは直感的でなかったり、そもそも実装例が少なかったりしてあまり使われていない印象があります。https://www.python.org/dev/peps/pep-0617/ のようにPythonへ導入が検討されている事例もあるので、これからに期待です。

興味がある人はpegjsのようなJavaScriptでpegのパーサを自動生成するパーサジェネレータや、
参考文献のPackrat Parser実装例などを参考に触ってみてください！

参考文献

脚注

  1. CFGとPEGは少なくとも同じ言語クラスではないことがわかっていますが、PEGがCFGを包含しているのかどうかは明らかではなく、CFGで表現できてPEGで表現できないものが存在するようです。 ↩︎

  2. CFGとは違い矢印の方向は<-です。PEGは解析表現であってCFGのような導出規則ではないという学術的な違いがあります。これを区別するかどうかは諸説あるので言及を避けます。 ↩︎

  3. 後の文法の否定先読みを文法の前に追加します。例えばE<-A/B/Cなら、E<-!(B/C)A/!CB/Cとします。これをするとAならAにマッチし、B、CにマッチするならB、Cまで失敗しつづけます。 ↩︎

Discussion