https://twitter.com/kinaba のログ (twilog の方が便利です。)
| Nested Word/Visibly Pushdown Lang.の構文解析ってそういう方法でやる方がうまくいくことはないだろうか。うまくいくの定義が謎ですが。http://twitter.com/kinaba/status/27944743742 の左再帰回避もその枠組みで | |
| あと深さ優先じゃなく幅優先な感じの文法/構文解析の形式化は要ると思うんだよな。まず括弧の対応だけを取る→それぞれの括弧の中でセミコロンの区切りだけ取る→区切られた中をあとは頑張る、みたいなの。実際C++の構文解析は部分的にこうやるか非決定性パーザ使うかする必要があるわけだし | |
| @kmizu 左2右で読む方が楽な部分ではそちらで、右2左で読む方が楽ならそちらで、適宜勝手にモードが切り替わりながら構文解析が進むようなものを考えてます。昨日読んだ左再帰と右再帰を混ぜられるパーザコンビネータの論文の話を決定性パーザでやろうと思うと終端を縮める操作が欲しいなーと | |
| @kmizu あとフォーマルな興味で、LLやLRや決定性CFLやおそらくPELも、文字列の反転で閉じてない（SがLR(k)言語でも{rev(s)|s∈S}がLRとは限らない）のが気持ち悪いなあと。後ろから読めば１トークン先読みですぐわかるのに前からだと全然わからない文法がありうる | |
| @kmizu はい、その辺り面白そうです。とりあえずLR(k)をベースに、LR(k)表と同時に後ろからRL(k)?表みたいなのも作っておいて、「普段はLR(k)で左から右に進むけどLR(0)コンフリクトがあったらRL(k)で右から進めてみる」的な雰囲気を今30秒くらいで考えてます | |
| @kmizu はい。あるいは逆に、反転で（比較的自明に）閉じてる言語のクラスをまず定義すれば、そこから自然にそのクラスのbidi-parserが得られるのではないかとも。VPA http://www.cs.uiuc.edu/~madhu/vpa/ 辺り確か反転で閉じてるのでヒントになるかなと考えたりしてます | |
| Bidirectional Parsing for Context Free Languages http://bit.ly/dDgTCd まあありますよね。しかしこれdeterministic parserは全部単なるright to leftであってbidiじゃないのでは… | |
| LR(k)∩RL(k) Grammarが左右から読めるのは当たり前なので、LR(k)∪RL(k)というかもっと、左(右)のconflict解消に右(左)の情報を使うようなのが作りたい | |
| "Island Parsing and Bidirectional Charts" これが一番イメージに近いけどこれのdeterminise | |
| まあ何かありそうな気がすることがわかったので寝よう | |
| @fadis_ @SubaruG はい、なので厳密に言ってあれは"ライセンス"ではなく、他のPDS宣言とまったく同様に、public domainへ"のdedication/certification"です、と読んで構いません。それでなにか機能しなくなる部分があるでしょうか | |
| @fadis_ @SubaruG 「＞誰かが著作権を主張してライセンスを変更」って具体例なにかありますか。青空文庫の作品に対して僕が勝手に著作権を主張してライセンスを変更するのが明らかにおかしいのと同じで、おかしい話だと思いますが。 | |
| @fadis_ それは http://www.free-soft.org/gpl_history/ Goslingのコードを取り込んでいたら後でその部分が自由に使えなくなった、という話ではないですか。 | |
| @fadis_ あ、はい、Stallmanの主張がそうであるというのは理解しているつもりです。ただ、@SubaruG さんのお考えはわかりませんが、僕に関しては、彼らの言う自由には反対であるという正にその理由でNYSLを使っているので、適切でないというのは望むところだったり。 | |
| #entcomp2010 というのは http://ec2010.entcomp.org/ これかー。"画像認識と集合知による地球上の人面状構造物の探索" 楽しそう | |
| @mr_konn "The Undecidable" http://www.amazon.co.jp/dp/0486432289 | |
| 適当に張ったけど The Undecidable http://amzn.to/bYmxR1 (Godel,Church,Turing,Post,Kleene,Rosserの論文アンソロ)結構安くないですかこれ。どれもググれば読めそうではあるけど、一応400頁の一冊で2200円 | |
| @tsukuno まず英語がよくわからんのだけど、Parkから出られるエッジの本数に上限があるMST、という理解でOK？ | |
| @tsukuno それだと 20Cs 回MSTをブン回したくなる | |
| @tsukuno 車の乗り捨てあり＆＆一台に何人でも詰め込めるのでMSTじゃないかなあ。 | |
| @tsukuno 20C10の方で？ http://twitter.com/tsukuno/status/28382572065 は間違ってるよ | |
| n C n/2 がどのくらいの大きさかパッと概算できる方法ってあるかな。いつも 「2^n よりは結構それなりに小さいだろう」 くらいしか考えてないんだけど | |
| @uwitenpen 暗算できるくらい簡単な近似式が欲しいカモ…。しかし [2^n/(n+1), 2^n] くらいの評価で満足できる気がしてきました… | |
| @uwitenpen @hos_lyric おお、ほんとだこんな簡単に！ありがとうございます。「2^n/√n よりちょい小さい」で認識しておくことにします | |
| @wand125 ありがとうございます！綺麗な式になるものですねえ | |
| .@ranha 様は本当に http://twitter.com/ranha/status/28382066920 こういう本についてはなんでも知っていらっしゃる… | |
| @tmiya_ @nushio どもどもありがとうございます。係数とっさに思い出すの苦手なのですけど 2^n/√n くらいで大雑把な評価になりそうですね |