PEGのボキャブラリー

Parser

前回に引き続き、解析表現文法（PEG）を見ていきたいと思います。あいまい性が無かったり、再帰降下型パーサーと相性が良いなどの特徴があるPEGなんですが、どうゆう中身になっているのでしょうか。

PEGは次のような要素で構成されます。各要素の英語名の後にここで使っている表記法を書いておきます：

  • 空文字(empty/())：入力ストリームから一文字も消費することなくパースを成功します。
  • 終端(terminal/小文字英数)：物々しい名前がついてますが、要は実際にマッチしたい文字のことです。マッチしたときは対応した入力を消費して成功します。
  • 非終端(non-terminal/大文字英数)：これは終端に対応するもので、パースしたいパターンにつけるレーベルのようなものです。
  • 順序(sequence/(e1,e2,e3,e4))：複数の要素を特定の順番にマッチさせるものです。全ての要素がマッチした場合は対応する入力を消費して成功します。そうでなければ一文字も消費せずに失敗します。
  • 選択（ordered choice/(e1/e2/e3/e4)）:複数の要素の中から一つマッチするときに全体を成功させます。マッチに対応する入力は消費されます。PEGの選択で特徴的なことは必ず最初の要素から試行されることです。選択内の複数の要素がマッチする可能性があるときは最初のマッチが優先されます。
  • 繰り返し(Greedy Repetition/e*):これは指定された要素の0回以上の繰り返しです。つまりまったく出現しなくても成功することになります。PEGでの定義では繰り返しはマッチする全てを消費するということです。
  • 1回以上の繰り返し（Greedy Positive Repetition/e+）:繰り返しとほぼ同じなのですが、最低1回はマッチしないと失敗を返します。sequenceとGreedy　Repetitionを組み合わせれば
  • e+ = (e, e*)
  • と書くことができるわけですね。
  • 省略可能（optional/e?）:マッチした場合は対応部分を消費して成功、マッチしなかった場合は入力を消費せずに成功します。
  • Followed By/&(e)：うまい日本語が思いつかないのですが、後続の要素によってパターン全体を失敗させることができます。成功しても失敗しても入力は先読みされるだけで消費されません。
  • Not Followed By/!(e): これはFollowed Byの否定形ですね。


文献によるとPEGは正規表現の拡張版という位置づけとも捕らえられるようで、繰り返しや選択などは正規表現などにもありますね…しかしながら繰り返しや選択については振る舞いが厳格に定義されています。正規表現に無いものがFollowed ByやNot Followed Byあたりでしょうか…(正規表現をあまりちゃんと知っているわけではないのですが…）
シロート目にはPEGはLL(n)パーサーで解析可能な文法なように見えます。ｎがいくつかなるかはPEGで定義されている文法に依存しそうです。

試しにPEGで整数をパースするパターンを定義してみると：

NUMBER  =  (0/NONZERO)
NONZERO = (DIGIT, DIGIT0*)
DIGIT = (1/2/3/4/5/6/7/8/9)
DIGIT0 = (0/DIGIT)

といった感じでしょうか。CFGでは普通なようですが、正規表現とは違ってnon-terminalをつかってパターンを分割して定義できるのが便利ですね。

しかしながら、このパターンでは０１などの文字列に対して最初の0だけとってパースを終了してしまいます。このような文字列をはじきたい場合はどうしたらよいでしょう？

NUMBER = (ZERO/NONZERO)
ZERO = 0!(DIGIT0)

のようにしてやれば、ZEROは０単独の場合にのみパースを成功するようになります。０１などの場合は一文字も消費することなくパースは失敗します。

負の数をパースできるようにするためには、Optionalを使って：
NONZERO=-?(DIGIT,DIGIT0*)
とやってやればオッケイですね…

比較のためにCFGでやってみると：

NUMBER = (ZERO|NONZERO)
ZERO = 0
NONZERO=-,POSITIVE|POSITIVE
POSITIVE=DIGIT, DIGIT0S
DIGIT = 1|2|3|4|5|6|7|8|9
DIGIT0S = DIGIT0|DIGIT0, DIGIT0S
DIGIT0 = 0|DIGIT

特筆べき違いといえば、０１をパースするときにCFG版のほうは失敗しないですね…０だけとって終了してしまいます。強制失敗させるような方策も無いので、CFGで０１をはじく方法は無いのでしょうか？あとは、CFGがもともと生成文法であることが理由なのか、どこまでパースすれば終了なのかということに関する定義がはっきりしないような気がします。極端な話、1000をパースするのに1だけパースして止まってもCFGの定義からすれば何も契約違反をしていないような気がします。PEGでは文法の定義によって、1000の全ての桁をパースすることが保障されていますね…もっとも、CFGにも追加ルールを付け足して対処することはできそうですが…
もう一つ挙げるとすれば、CFGではパターンの繰り返しは再帰で表現されていますが、これはPEGの＊や＋と比べると、文法全体の見通しが悪くなるような気がします…再帰はPEGでも使われますが、あまり多用されると読みづらいですね…

次回はもうちょっと踏み込んで整数の四則演算をPEGパターンをやってみたいと思います。

ではでは。

解析表現文法のこと

Parser PEG Memoize

パーサーにかかわることについて勉強していて引っかかったのがPEG（解析表現文法）という文法です。CFG（文脈自由文法）やCSG(文脈依存文法）は生成文法、つまり文章を生成するときに使いやすい表記であるのに対し、PEGは解析、つまりパース時に使いやすい表記になっているという特徴があります。

Packrat Parsing: a Practical Linear-Time Algorithm with Backtrackingという論文を読んでいるのですが、これはPEGの一種であるところのTDPL:Top down parsing languageという種類の文法で表現された言語をパースするパーサーを生成するPappyというパーサージェネレーターライブラリをHaskellで実装する論文です。

まだ消化し切れてはいないのですが、TDPLという文法は再帰降下型パーサーの動作にとても近い形で文法を表現できるという特徴があり、さらに、CFGとは違いAmbiguityを文法表現に含むことができないという特徴を持っているようです。ちなみにある文法がAmbiguousであるというのはどういうことかというと、それはつまり一つの文章の解釈が2通り以上あるということです。
前回も書いた受け売りですが、あるCFGで記述された言語があるときに、それがAmbiguousであるかどうかというのは一般的にはundecidableなので、Amibiguityを取り扱いたくない場合にはPEGは有利ですね。(逆に言うとAmbiguityが当然のようにある自然言語などはPEGは不適ということになりますね。)

更に、CFGで記述された言語を解析するパーサーの計算コストはO(n^2)からO(n^3)の間で、CFGがAmbiguousでない言語を解析するパーサーの中にはO(n^2)の計算コストのものが存在するようです。これに対して今回の論文で取り上げられているパーサーはPEGな文法で表現された言語をO(n)でパースすることができるようです。計算コストを抑えるためにpackratという呼び名の由来であるメモ化をして、メモリ消費を増やして計算コストを抑えるという戦略をとっているようです。

CFGといえば代表的なものの一つとしてBNFがあるわけですが、プログラミング言語がBNFで表記されたものを見ると、大体トークン単位で、変数名や関数名の定義などの部分では文字単位まで踏み込んでいたりすることもありますが、いわゆる予約語、Haskellで言うところのimportとかmoduleとかnewtypeなどはトークン単位であって、実際パーサーを書くときには文字レベルでパースする段階で予約語と変数名などを判別するためのCFGを書こうとすると相当複雑になってしまうようです。それ以前にソースコード内のタブ、改行、スペースなどからなる空白を適切に扱うことすらかなり面倒なことをしなくてはいけないようで、実情として、CやC++のソースコードを文字列で読み込んで、じかに構文木を吐き出すパーサーというのは存在しないとまでは言いませんが（何分不勉強ですので）、かなり珍しい&難しいもののようです。だいたいが多段式のパーサーになっているようです。

振り返って、PEGのほうでは、予約語や空白などの処理も文法表記に割りと自然に組み込むことができて更に構文木を出力するのもCFGベースのパーサーに比べてずいぶんと楽なようです。

こうなってくるとCFGとはおさらばしてPEGでやったほうが全然よさそうですね。

なんと言うか、概要の概要になってしまって、あんまり実がないのですが、今日はとりあえずこの辺で…

ではでは。

パーサーのこと

Parser

id:kazu-yamamotoさんのとりとめのないパーサー談義に刺激されて
パーサーのことを勉強しているところです。yamamotoさんは｢パーサーに詳しい人に答えていただけるととても嬉しい」といわれていますが、勉強がてら自分なりの答えを書いてみようと思います。

疑問1) GLR法は、文脈依存文法(CSG)(の一部)も解析できるのか？

はなから、怪しい解答になってしまうのですが、WikiPediaの文脈自由文法(CFG)の解説によると、ある文脈依存文法により生成される言語が文脈自由言語かどうかを判断することはundecidable (判別不能？）だそうです。これはつまり、文脈依存文法での全体集合の中には文脈自由言語しか生成しない部分集合もあると言うことらしく、そういった意味では文脈自由文法を解析する能力があるGLR法は文脈依存文法の一部を解析する能力があるということはできるでしょう。

さらに、Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers – Principles, Techniques and Tools.　によると、CやJavaなどの言語の多くは文脈依存な部分があるけれど、コンパイラ内でSyntactic解析を行うコンポーネントとしてのパーサーは多くの場合パーサーの複雑性を抑えるために文脈依存性に起因するエラーは無視してしまうようです。

C＋＋などでの文脈依存性としての例として挙げられてるのが変数や関数などの宣言と参照(宣言せずに参照するとエラーになる）や、関数のパラメタ（同様に宣言と呼び出しのミスマッチはエラーになるべき)などが挙げられています。

C++コンパイラ内のパーサーの単純化についてはテンプレートをネストするときの表現が思い出されます：

TFoo< TBar> a;

みたいなことをやりたかったら、＞＞の部分にスペースを入れてやらないとコンパイルできなかったりしますよね…素人考えですが、これは文脈依存性で表現できるような気もするし、あるいはGLRでちゃんとカバーできる問題なような気もしないでもありません。

疑問2) C++ は GLR で解析できますが、文脈依存文法でしょうか？

ということで、C++は文脈依存文法であるということはできると思います。ただし、文脈依存言語を解析するパーサーが文脈依存性を解析しなくてはいけないかというと、それは必ずしもそうではないようです。要はどんな解析をさせたいかというところにかかっていて、例えば、ソースファイル内のカッコの対応がちゃんと取れているか調べるだけだったら、LL(n<∞)でも十分な気がします。そして、C++をとことんまで解析しているはずのコンパイラでさえ、パーサーの部分では文脈依存性に関する解析は行わないこともよくあるようです…
もっとも、この回答は少しあざといですね。というか、パーサをあんまり使ったことがない人がちょっと勉強しただけで出す答えかもしれません。もっと有用な問題の解釈はC++は構文木を生成させるパーサーが理解しなくてはいけない部分において文脈依存的な文法があるか？ということになるかと思うのですが、これは今の僕にはまだ理解が足らなくて答えられません。この場合は宣言と参照の違いを無視してもよいことになるので、それ以外の部分で文脈依存性があるかどうかということになります…
Wikipediaの文脈依存文法の項に出てくる文脈依存言語の例は
{a^nb^nc^n : (n >= 1)}
というもので、要は何を言っているかというと、a, b, cの3文字がそれぞれ同じ回数だけ繰り返す文字列、つまり、

abc
aabbcc
aaabbbccc
ただし
aaacccbbb
abcabcabc
などのような文字列は含まれない

なわけで、C＋＋でもカッコなどの対応はこれと似たようなパターンをとりますね。確かにファイルの先頭に｝を書くことはできないので、これは立派な文脈依存性といえるのかもしれません。あとはコメントとかも当てはまりそうですね…

疑問3) Perl も、LALR ではなく GLR を使わないと解析でないと聞きましたが本当でしょうか？ 簡単な例はありますか？
疑問4) Ruby の << や BASIC の = も GLR を使わないと解析できませんか？

PerlとRubyは知識不足で、BASICも細かいところを忘れちゃったのでスキップです…

疑問5)BNFは、文脈自由文法全体を表現する能力があるか？

WikipediaのBNFの項によると、BNFは文脈自由文法を表現するためにデザインされたようなことが書いてあります。なので、答えは「ある」ということになるような気がします。文脈自由文法の定義の一つとして、
「一つの非終端記号を任意の長さの終端と非終端記号の混ざった記号列に置き換える置き換えルールの集合で表せる文法」
というのがあるようなので、BNFでCFGが表現できるというのは妥当な気がします…

疑問6)このパーサーは、文脈自由文法全体を解析する能力があるか？

ちょっと長くなっちゃったので、これはまたの機会に…(汗)


パーサーのことを少し勉強してみてわかったのは、チョムスキーはすごいなーということ、今日この頃はブッシュ批判とか、色々政治的な活動をしているようですが、昔はこんなことやってたんですね…あとは、CFGやCSGなどは定義がずいぶんと明確なんですが、実際の言語となると、プログラミング言語も含めて「ほぼCFG」みたいな感じで結構ファジーになっちゃうんだなーということです…

ではでは。

スクラップ・ユア・ボイラープレート

Haskell Generics

Scrap Your Boilerplate:A Practical Design Pattern for Generic Programmingという論文を勉強中です。

以前リストの自由度で話した内容と関連しているのですが、

Haskellのリストは長さは可変な代わりに要素の型が全て同一でなくてはいけなくて、タプルは要素型が同一でなくてはよいけれども長さは固定、つまり

リストでは
[1, 2] :: [Integer]
[1, 2, 3, 4] :: [Integer]
のように長さの違うリストでも同じ型で表現できるけど、
[1, 'a']
のようなことは許されない。

タプルでは
(1, 'a') :: (Integer, Char)
は許されても
(1, 2) :: (Integer, Integer)
(1, 2, 'a') :: (Integer, Integer, Char)
といった感じで、長さの違うものは別の方になってしまう。

これでは可変長で要素型が単一でないデータはどうやって表現したらいいのかという問題が出てきます。

そこで出てくるのが、dataなどで複数の型の情報を保持する型を定義する方法：

data Variant = Int Int | Char Char | String String | …

こうやってやると、タイプコンストラクタのオーバーヘッドはありますが、リストの中に複数の型の値を混在させることができるわけですね…

[Int 3, Char 'a', String "hello"] :: [Variant]

こういった型の異なる値を保持できるデータ型はライブラリ内にもいくつかあって、Language.Haskell.Parserなどを見るとさまざまなデータ型を含むツリー構造がHsModuleという型として定義されています。

リストに色々な型の値を突っ込むことができた後にやりたくなることはといえば、そのデータをアクセスすることですよね…

例えば、リスト中にある数字を全て合計したかったら：

addIfInt :: Int -> Variant -> Int
addIfInt i (Int j) = i + j
addIfInt i _ = i

foldr (addIfInt) 0 ([Int 3, Char 'a', String "hello"] :: [Variant])
=>3

なんて感じのことをやるわけですよね…でもこれをHsModuleのように深いデータ構造に対してやろうと思ったらaddIfIntのようなコードを大量に書かなくてはいけないですね…まぁ、不可能ではないのですが、コードが大量化しがちです。そうなってくると後でデータ構造に変更を入れたくなってもなかなかできませんね…

最初にあげた論文ではこのようにコードに繰り返し現れる、ほとんど同じだけど微妙に違うだけになかなか取り除けないコード断片のことを｢ボイラープレート｣と呼んでいます。そして、Data.Genericsの力によって、ボイラープレートを書かずに同等のことができるという話です。

すばらしいですね…

ちなみに上のaddIfIntの例は：

everything (+) (mkQ (0::Int) id)  
　　([Int 3, Char 'a', String "hello"] :: [Variant])

と書くことができます。（Variant宣言にderiving (Data, Typeable)を付け足す必要があるはずです。）addIfIntは完全に省くことができちゃうわけですね…すばらしい…

さらにリストもタプル(2プルから7プルまで)もDataとTypeableのインスタンスになっているので、Variantがリストやタプルの中に入っていても上記のコードは中にもぐっていってIntだけを見つけて合計を計算してくれます。強力ですね…

[Variant]なデータ内のIntの部分にだけ関数を適用することもできます：

everywhere (mkT (+(1::Int))) 
　　([Int 3, Char 'a', String "hello"] :: [Variant])
=> [Int 4,Char 'a',String "hello"]

これは[Variant]内のIntな部分だけ(+1)を適用してくれます…

これは確かにボイラープレートを書く気がなくなっちゃいますね…

Data.Genericsの中身の解説はもうちょっと理解が深まってから…今回は利用例のみということで…
ではでは。

遅延IOは可能か

unsafe Monad Haskell

PyTestさんの記事を読んで考え込んでいました。取り上げられていた問題は、ディレクトリを深さ優先探索するコードなわけですが、これをpay as you goでやりたいときにはHaskellではどう書けばよいかというものです。
pay as you goで何がいいたいかというと、ディレクトリの探索はデータが必要になるまで遅らせたいということです。まさにHaskellのリストなんかで有効な遅延評価そのものですね…

ただ引っかかってくるのはディレクトリの内容を取得する関数も含めてファイルシステム関係の関数は全てIOな関数なことです。最初に僕が思ったことは次のとおりでした：

walk :: Path -> IO [Path]のシグネチャでコードを書くと遅延評価はできない。

unsafePerformIOを使えばできるだろうけど、何せunsafeなんだからできたら使わないで行きたい。

walkmapM_:: (Path -> IO a) -> Path -> IO ()みたいな風にして探索中にマップしてしまう関数にすれば遅延評価ではないまでも、pay as you goにはなる…けど、探索の中断をサポートするには関数パラメタに少し工夫をするか例外を使うかしなくてはならなさそう。

ひょっとしたらリストとIOを合成したモナドを作ればなんかうまくいくかも？なんていうのも思ったのですが、色々やってみて得た結論は、内部でどんなことをやろうとしても提供する関数のシグネチャがPath -> IO [Path]になっている時点で遅延評価はしないと宣言しているようなものだということです。
Path -> IO [Path]を翻訳すると、この関数はPathをとってIO [Path]を返す関数で、関数の帰り値は[Path]ではなくて、[Path]が帰ってくるIOな｢計算｣なわけです。そして、そのIOな｢計算｣をした後に残るのは[Path]、つまりそれはその関数が返せる全ての値を含んだリストでなくてはいけないわけです。

あきらめてunsafePerformIOで書いたのがこれ：

childDir :: FilePath -> IO [FilePath]
childDir path = getDirectoryContents path >>= 
　　filterM (cur) >>= 
　　mapM (return.absolute) >>= 
　　filterM (isDir)
　　where
　　　　cur "." = return False
　　　　cur ".." = return False
　　　　cur _ = return True
　　　　absolute :: FilePath -> FilePath
　　　　absolute child = path  child

isDir :: FilePath -> IO Bool
isDir "."   = return False
isDir ".."  = return False
isDir child = doesDirectoryExist child

dirWalk :: FilePath -> [FilePath]
dirWalk path = path : (concatMap (dirWalk) 
　　(unsafePerformIO $ childDir path))

ということで、dirWalkのシグネチャからはIOが消えました。動かしてみるとあっさり遅延モードで動きます。PyTestさんが言うようにこうゆうコードが普通にかけないと言語としてちょっとつらいものがありますね…こんなことを考えながら思い出されたのがPrelude.getContentsやSystem.IO.hGetContentsです。ライブラリの記述を見るとこの関数はファイルの中身をリストとして取り出すわけですが、シグネチャは
hGetContents :: Handle -> IO String
なくせに、ファイルアクセスは遅延だと書いてあります。しかしながら更に読み進んでいくと,
なにやらハンドルがsemi-closed状態になるだとか、なんだかとても怪しいことが書いてあります。コードを眺めてみると、このひとも、unsafeInterleaveIOなる関数を使っています。なんと…

どうやらunsafeInterleaveIOはIOな計算を遅延するためにある関数のようです。今回の用途にも使えそうです…

ここでunsafeな関数を使うことのunsafeさは一体どんなものがあるのでしょう？

IOモナドが必要になった根源的な理由は、僕の理解する範囲ではコードの実行順序に関係するものです。純粋関数型言語では値が必要になるまではその値を求める計算をしないわけですから、実行順序を強制したいときには何か特別なことをしてやらなくてはなりません。それを成し遂げるために導入されたのがモナドだったわけです…概念的にはIOは｢外界」をパラメタに取る計算という説明もできるわけですが、実際に｢外界｣がパラメタとして関数に渡されているかというと、現実問題そうゆうこともないわけで…

実行順序に関して言えば、前々から思っていたのですが、IOな関数でなくてもリストに関する処理にも実行順序が決定しているものがあります。リストはその構造から言って、先頭からたどっていくしかないわけですから、例えば：

 map (+1) [1..5]

なんていうコードは、リストを先頭からトラバースしていきますね…最も(+1)がリストの各要素に適用される順序はもうちょっとあやふやですが…リストもモナドな型なわけなのですが、リストのモナドメソッドの振る舞いはこのリストの生成順序決定性とは関係ないことを記述しているように思います。

hGetContentsにしても、今回のdirWalkにしてもIOなコードをリストに埋め込んでいるので、関数の実行をして得られるリストの要素順に影響が出るようなコードを書くことはできなさそうです。

dirWalkの場合はトラバース中にディレクトリが削除されたり、新しいディレクトリができたりすると混乱するわけですが、これはファイルシステムをロックすることができない限り、遅延評価でなくても直面する問題ですね…

僕の今の理解では手が届かないのですが、Haskellでdo文がモナドに直結しているというところに多少の不自由さを感じます。ここは新しい型クラスSequentialを定義して、モナドは全てSequentialになるようにして、do文はSequentialとつなげるとかやるとかっこいい気もします。僕のイメージの中での話ですが…そすることで、モナドではないけど順序性が定義される型に対してdo文を使うことができるようになったらいいなと…まぁ、自分でも何言ってんだかわからないわけですが…

この辺のことがわかるまでは、unsafeは気をつけて使ったほうがいいけど、使うときは割り切って使うということが今回の教訓かもしれません…つまり、

遅延IOは可能かと聞かれれば、今のところの答えは「unsafeな関数を使えば」という答えになります。

あと、Windowsの空白文字を名前に含むディレクトリがあるとこのコードが動かないのがどうやったら解決できるのかがわかりませんでした…


ではでは。

fixと無限リストの相性

Haskell

昨日のポストは単なるいかさまだったわけですが、これに懲りずに、また何か展開があったら懲りずにデータ再帰についてポストしていきたいと思います。(泣)

それとは別に、fixで無限リストを生成するコードが書けたのでそれについて簡単に書いておきたいと思います。

a -> aな関数fをパラメタにとるときにfixで値を返す方法の一つはこんなやつでした：

fix (\_ -> 1)
=> 
1

fixで無限再帰がいつ起きるかというと関数fがそのパラメタを評価したときです。だから、パラメタを見る前に値を返さなくてはいけないわけですね…更に、fixの特徴として、fix fが返した値はfへのパラメタがとしてそのままわたってくるわけです。こんなのはどうでしょう？

fix (\x -> 1 : x)

これはrepeat 1と同じ結果で無限個の1を含むリストができます…無限リストを返す関数ならば、無限再帰になっても使い道はありますね…

take 5 $ fix (\x -> 1 : x)
=>
[1, 1, 1, 1, 1]

となるわけです。

ちょっとひねって：

take 5 $ fix (\x -> 1 : map (+1) x)
=>
[1, 2, 3, 4, 5]

なんていうのもできます…

フィボナッチ数列をやってみました。i番目の値は：

fib i = if i > 1 then
	fib(i - 1) + fib(i - 2)
	else i

という数式で求められます。つまり、自分の直前2つの要素の和なわけですね…（最初の2つは１ですね。)
こうゆう再帰はf:: (a->a)->a->aなfixで書けば：

fib = fix (\f i -> if i <= 2 
	then 1 else (f $ i - 1) + (f $ i - 2))

とかけます。これをf::a->aなfixでやるのはどうも無理そうです。何せfにfixの外側からパラメタiを与えて、それを再帰が深くなるごとにi-1とやったりする方法がないからです。でも、最初にあげた無限リストを使った方法ならこうかけます：

fib = fix $ \x -> [1, 1] ++ (zipWith (+) x $ tail x)

(print.(take10)) fib
=>
[1,1,2,3,5,8,13,21,34,55]

みたいな感じですね…

なんとなくfixの使い方がわかってきた気がします。
ただ、できなかったのはf::a->aなfixで階乗を書くことです…

今日はこの辺で。
ではでは。