トップ «前の日記(2006-09-08) 最新 次の日記(2006-09-10)» 月表示 編集

日々の流転


2006-09-09 [長年日記]

λ. Parsing expression grammar (PEG)

Matzにっき(2006-09-08) - Parsing expression grammar より。なかなか便利で扱いやすそうな形式化だと思った。

  • 曖昧性が無い。
  • 無制限の先読みが可能なのでレキサとパーサを分ける必要はない。
  • Packrat Parser として実装することで、文字列長に対して線形の計算量に。

しかし、 {an bn cn | n≧1} のPEGはだいぶトリッキーだと思った。 こんなの普通書けないって。

S ← &(A !b) a+ B !c
A ← a A? b
B ← b B? c

それから、以下の部分がよくわからなかった。

It is also possible to build LL parsers and LR parsers from parsing expression grammars, but the unlimited lookahead capability of the grammar formalism is lost in this case.

PEGはCFGでない言語を表現可能なのにLLやLRで扱えるのか? LLやLRってCFGじゃない言語を扱えたっけ? それから、「the unlimited lookahead capability of the grammar formalism is lost in this case.」というのは、必要な先読みの上限を変換時に静的に決定可能だから LL(k) や LR(k) になるということか? いや、上の例を考えてみても先読みの上限は静的に決定することは出来ないか。

Haskell用のパーサジェネレータもあるみたいだし、今度試してみるか。

追記

そういえば、言語の差分やintersectionをとることが可能なパーサコンビネータについて、暖めていたアイディアが一つあったのだけど、PEG + Packrat Parser があれば不要だということに気づいた。しょぼーん。

λ. 『τになるまで待って』 森 博嗣

τになるまで待って (講談社ノベルス)(森 博嗣) を読んだ。 Amazonの書評では散々だけど、それなりに楽しめた。 トリックを強引と思う人もいるだろうけど、犯人の行動としてそこまで変だとは思わないしね。だいたい、犯人がミステリー受けするような行動を取らなくてはいけないという理屈はないわけで。

Quotation (p.209)

「そういった、何故そうしたのか、という理由に立ち入ると、最初から数々の可能性が否定されてしまうことになるんじゃないかな」山吹が言う。「そうじゃなくて、物理的にどんな方法が現実にありうるのか、をまず問うべきだよ。理由というのは人間の気持ちの問題であって、そんな心理まで考慮していたら、結局は論理に曖昧性を持ち込むだけで、目標が霞んじゃうと思う」
Tags:
本日のツッコミ(全4件) [ツッコミを入れる]
ψ みずしま (2006-09-10 19:42)

「PEGをLLやLRパーザに落とすことはできるけど、その場合<br>無制限の先読みはできないよ」という意味に取ったのですが、<br>どうなのでしょう。あんまし自信無いので間違ってるかも<br>しれませんが。

ψ さかい (2006-09-11 03:50)

みずしまさんの言っているのは「全てのPEGではなく、無制限の先読みを必要としないPEGだけがLLやLRパーザに変換可能」という話でしょうか?<br>それなら納得できますが……

ψ みずしま (2006-09-11 09:19)

はい。そういう意図で書きました。PEGの元論文をざっとながめた<br>限りでは、純粋なLLやLRパーザに変換できるという話は見当たらなかったので、そうなのではないかと思いました。

ψ さかい (2006-09-12 03:36)

ありがとうございます。<br>やっぱりそういうことなんでしょうね。<br>これでスッキリしました。