Scala基礎文法最速マスターを書こうか迷っていたら、既にyuroyoroさんに書かれてしまったので、ちょっと違う方向で。BNFを既に知っている人は、これを読めばPEGの基礎をマスターしてPEGを書くことができるようになるでしょう(ほんとか？)。
基本
Parsing Expression Grammar(PEG)はBNFに似ているけど、ちょっと(かなり？)違う文法の表記法です。BNFはその文法がどのような言語を表現しているかを定めるのに対して、PEGは入力がどのように解析されるかを定めます。PEGとBNFの一番大きな違いは、PEGには曖昧さが無いことです。たとえば、プログラミング言語のif文を表現する次の擬似BNFには曖昧さがあります。
statement ::= if_statement | ...;
if_statement ::= IF LPAREN expr RPAREN statement ELSE statement
| IF LPAREN expr RPAREN statement;このようなBNFに対して、次のような入力があった場合、
if(cond1) stmt1 else if(cond2) stmt2 else stmt3
if(cond1) stmt1 else (if(cond2) stmt2 else stmt3)
と解釈すべきなのか、
(if(cond1) stmt1 else if(cond2) stmt2) else stmt3
と解釈すべきなのかは一意には定まりません*1。
一方、これに相当するPEG
statement <- if_statement / ...
if_statement <- IF LPAREN expr RPAREN statement ELSE statement
/ IF LPAREN expr RPAREN statementには曖昧さがありません。PEGでは、複数の選択肢があった場合、常に前から順に試し、失敗したらバックトラックして別に選択肢を試行する、という動作を行うため、上記のif文は常に
if(cond1) stmt1 else (if(cond2) stmt2 else stmt3)
のように解釈されます。また、PEGでは局所的な失敗をバックトラックによって回復することができるため、LL(k)やLALR(1)パーザのように、先読みを行うために入力を字句解析器によってトークンに切り分けておく必要がありません。この特性は、Rubyの式を埋め込み可能な文字列リテラルのように、トークンが構文要素を含む可能性がある場合に特に便利です。
ツール
JavaのPEGパーサを生成するツールとしてRats!、Mouse、RubyのPEGパーサを生成するツールとして、TreeTopなどがあります。他にも多数の実装がありますが、詳しくはWikipedia(en)のParsing expression grammarの項目をご覧ください。PEGのアルゴリズムは極めて単純なため、自前でPEGパーザジェネレータを作成することも比較的容易です。
コメント
オリジナルのPEGでは、#から行末までがコメントです。ただし、PEGにはいくつかの変種があり、場合によって/*から*/までがコメントだったり、//から行末までコメントだったりするかもしれません。この辺りは、利用するツールのマニュアルを読んでください。
# これはコメントです
規則
PEGはN <- eという形の規則*2の集まりからなっています。これは、BNFがN ::= eという形の規則の集まりからなっているのと似ています。eの部分はPEGではparsing expressionと呼ばれます。
parsing expression(基本)
parsing expressionの内、プリミティブなものは次の3つです。
文字列リテラル ""
特定の文字列にマッチするかどうかを検査します。たとえば、"hoge"のように書くと、入力が"hoge"にマッチするかどうかを検査します。
文字クラス []
特定の文字集合にマッチするかどうかを検査します。たとえば、[abc]はa,b,cいずれか１文字にマッチするかどうかを検査します。また、[a-z]のように書くことである範囲の文字にマッチするかどうかを検査することができます。
parsing expression(演算子)
既存のparsing expressionを次の演算子で組み合わせてさらに複雑なparsing expressionを組み立てることができます。
連接 e1 e2
入力がe1にマッチした後、e2にマッチするかどうかを検査します。たとえば、
a [a-z]は、aa, ab, ac,..., azにマッチします。
選択 e1 / e2
入力がe1にマッチするかを検査し、失敗した場合にのみ、e2にマッチするかどうかを検査します。これは、BNFの|とは異なることに注意してください。たとえば、"ab" / "a"は、ab,aに対して成功しますが、"a" / "ab"は常にaに対してのみ成功します。
繰り返し e*
eの0回以上の繰り返しにマッチします。たとえば、"a"*は、"",a,aa,aaa,...にマッチします。正規表現にある同様の繰り返し演算子と異なり、"a"* "a"はいかなる文字列に対してもマッチしないことに注意してください。これは、"a"*がいったん成功した場合、後続の"a"が失敗してもバックトラックを行わないことに因ります。
1回以上の繰り返し e+
eの1回以上の繰り返しにマッチします。たとえば、"a"+は,a,aa,aaa,...にマッチします。これは、e e*のシンタックスシュガーです。
0回または1回 e?
eの0回または1回の出現に対してマッチします。たとえば、"a"?は"",aに対してマッチします。これは、e / ""のシンタックスシュガーです。
肯定先読み &e
入力がeにマッチするかどうかを検査し、マッチする場合に成功します。ただし、成功しても、入力を先に進めない点が単なるeと異なります。たとえば、&"a" "a"は、aaではなく、aにマッチします。
否定先読み !e
入力がeにマッチするかどうかを検査し、マッチしない場合に成功します。成功しても、入力を&eと同様に入力を先に進めません。たとえば、!"a" .は、a以外の任意の1文字にマッチします。
非終端記号 N
Nという名前の非終端記号にマッチするかどうかを検査します。たとえば、次のような規則が存在している場合にXと書いた場合、ab,acにマッチします。
X <- "ab" / "ac"
また再帰呼び出しを行うこともできます。たとえば、次の規則に対して、Xは、"",a,aa,aaa,...にマッチします。
X <- "a" X / ""
付録
左再帰
PEGは再帰下降パーザの一種なので、左再帰をサポートしていません(左再帰をすると無限ループになります)。そのため、左再帰は明示的に繰り返しなどに変換してやる必要があります。たとえば、以下のような左再帰を使ったBNFは、
A ::= A "a"
| 繰り返しを使って、"a"*と書くことができます。
文脈依存言語
PEGは文脈自由でない言語の一部を扱うことができます。たとえば、a^n b^n c^n(n≧1)は文脈自由でない言語のよくある例ですが、これはPEGを使うことで以下のように書くことができます。
S <- &(A !"b") "a"+ B !. A <- "a" A? "b" B <- "b" B? "c"
算術式パーザ
四則演算を含む算術式のパーザはPEGで次のように書くことができます。見ればわかるように、基本的には、LL(k)パーザ用のBNFを書くときと同様の感覚で書くことができます。一方で、spacingのような、任意の長さの文字列になり得る式が選択肢の最初に出てくる場合でも、いちいち先読みが可能なように式をくくり出さなくても良い点はLL(k)パーザとは異なります。
expression <- additive
additive <-
multitive
( spacing "+" spacing multitive
/ spacing "-" spacing multitive
)*
multitive <-
primary
( spacing "*" spacing primary
/ spacing "/" spacing primary
/ spacing "%" spacing primary
)*
primary <- "(" spacing expression spacing ")" / number
number <- digit+
digit <-
( "0" / "1" / "2" / "3" / "4"
/ "5" / "6" / "7" / "8" / "9"
)
spacing <- space*
space <- " " / "\t" / "\r" / "\n"
受理言語のクラス
先に述べたように、PEGは一部の文脈依存言語を扱うことができますが、PEGがどの程度の範囲の言語を表現できるのかは実はよくわかっていません。少なくとも、任意の決定的LR(k)言語と一部の文脈依存言語を扱うことができるのは確かですが、曖昧でない任意の文脈自由言語を扱うことができるかどうかは未解決問題です。任意の文脈自由言語を線形時間で解析できるアルゴリズムは今のところ知られていませんが、任意のPEGによって表現できる言語はPackrat Parsingによって線形時間で解析できることが知られているので、PEGで表現できないが、文脈自由言語であるような言語が存在するのではないかと考えられています*3。
