日々の流転

λ. Parsing expression grammar (PEG)

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

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

しかし、 {aⁿ bⁿ cⁿ | 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)

「そういった、何故そうしたのか、という理由に立ち入ると、最初から数々の可能性が否定されてしまうことになるんじゃないかな」山吹が言う。「そうじゃなくて、物理的にどんな方法が現実にありうるのか、をまず問うべきだよ。理由というのは人間の気持ちの問題であって、そんな心理まで考慮していたら、結局は論理に曖昧性を持ち込むだけで、目標が霞んじゃうと思う」