• Read older messages (October 31, 2008)
  • 3:31pm (February 07, 2008) 26x26mizushima
  • そのせいで、場合によっては線形時間でパーズできなくなるケースもあるけど、そんなケースはあまり無いよ、ということらしい
  • 26x26はやみず
  • ふむ
  • 3:32pm (February 07, 2008) 26x26ujihisa
  • fm
  • 3:33pm (February 07, 2008) 26x26mizushima
  • つーか、もう見てる人なんていないと思っていたんですが、意外だw
  • 3:34pm (February 07, 2008) 26x26はやみず
  • Fxのraderを最近導入しましたw
  • ujihisa has left
  • 3:37pm (February 07, 2008) 26x26mizushima
  • すいません。raderってなんでしたっけ？なんか名前は聞いた覚えがあるんですけど
  • 検索しても変なのしかヒットしない
  • 26x26はやみず
  • http://www.lingr.com/tools
  • 3:40pm (February 07, 2008) 26x26mizushima
  • おー。これは便利そうだ。導入してみよう。
  • 26x26はやみず
  • 名前がうすく表示されている人達は、おそらくみんなRaderな人々ですね
  • 3:41pm (February 07, 2008) 26x26mizushima
  • なるほど。名前がうすく表示されてるのはなんだろ、と疑問に思っていたのですが、そういうことだったのか…
  • はやみず has left
  • mizushima has left
  • nowake has joined
  • nowake has left
  • aho has joined
  • aho has left
  • k.inaba has joined
  • 9:07am (February 22, 2008) 26x26k.inaba
  • みんな
    http://www.cs.vu.nl/~dick/PT2Ed.html
    読もうぜ！！！！　などとつぶやきに来ました
    みんな
http://www.cs.vu.nl/~dick/PT2Ed.html
読もうぜ！！！！　などとつぶやきに来ました
    view paste
  • "Unlike most books, it treats (almost) all parsing methods" ということで、「例え絶滅危惧種パーザの動物園と言われようとも俺はやるぜ！（意訳）」という序文が熱かったです。
  • PEGの話は15.7節あたり
  • ではではー！！
  • k.inaba has left
  • mizushima has joined
  • 2:51pm (February 23, 2008) 26x26mizushima
  • おお。Parsing Techniquesは興味があるのですが、高いのでまだ入手してない…研究にも関係ありそうだし研究室で買ってもらおうかな…
  • 絶滅危惧種(以下略)の部分の意図がよくわからなかったですが、どマイナーな構文解析アルゴリズムも扱うぜ！ということでOK？でしょうか。
  • おー。なんかToC見てがぜん買いたくなってきました。つーか、買う。
  • k.inaba has joined
  • 3:08pm (February 23, 2008) 26x26k.inaba
  • ですです＞意図
  • 3:09pm (February 23, 2008) 26x26mizushima
  • 個人的には、Non-Chomsky Grammars and Their Parsersのところが一番興味ありです。
  • 26x26k.inaba
  • 私もそこが
  • Tree-Adjoining Grammarというのが自分の研究に近いところにあるらしいと最近しったので
  • あとはGLR構文解析とか新しめの話は普通にまったく知らないのでその辺ですねえ。
  • 3:11pm (February 23, 2008) 26x26mizushima
  • あー。GLRは名前だけ知ってるんですけど、結局どういう手法なのかは自分も全然知らなかったり…。
  • とりあえず、情報多謝です。
  • k.inaba has left
  • mizushima has left
  • mizushima has joined
  • 4:24pm (March 05, 2008) 26x26mizushima
  • http://www.kmonos.net/wlog/83.html#_1021080304
  • について
  • > LL(0) は、要するに１文字も見ずに「次絶対if文来るね。マジ。間違いないね」とか予言しないといけないのでつまり絶対無理なので、LL(0) という方法はありません。
  • とのことですけど、「ある１つの文字列しか含まない言語」ならLL(0)で表現できるのではないかと。
  • つまり、こんなの
  • S → "if"
  • 実用上はLL(0)というのは無意味だと思いますが
  • 一応"LL(0)" parsingとかでぐぐってみると
  • それほど多くは無いものの、ヒットする模様。
  • http://www.stanford.edu/class/cs143/handouts/18-Miscellaneous-Parsing.pdf
  • http://www.win.tue.nl/~wsinswan/softwaretools/slides/parsergenerator.pdf
  • k.inabaさんがここ見てるかわからないけど、一応。
  • mizushima has left
  • k.inaba has joined
  • 6:21pm (March 05, 2008) 26x26k.inaba
  • あ、はい、それはもちろんその通りだと思います。
  • 構文木を（１つの文字列しか含まない）文法とみなすという解釈は実用上も使い道があって、そうやってできた文法から再度元の構文木を再構築するアルゴリズムはLL(0)と言えないこともないので、そこまで無意味でもないとも思ったりします。
  • ただ、なんというかあそこで言い切らないとLLの先読みとLRの先読みは違う
  • というのが伝わりにくくなる気がしたのでLL(0)さんには退場してもらいました(^^;
  • あんまり良くない説明だったかな…うーむ
  • 追記中...
  • k.inaba has left
  • mizushima has joined
  • 8:47pm (March 05, 2008) 26x26mizushima
  • あー、なるほど。納得しました。
  • LLの先読みとLRの先読みが違うというのは以前、そのことで悩んだことがあって
  • つい突っ込んでしまいました(^^;
  • mizushima has left
  • nowake has joined
  • 12:38am (March 07, 2008) 26x26nowake
  • どうも、こんばんは。ちょっとだけ突っ込みを。
  • >「ある１つの文字列しか含まない言語」はLL(0)
  • mizushima has joined
  • 12:39am (March 07, 2008) 26x26nowake
  • 正確には「分岐を含まない（先読みする必要のない）」ということですね。
  • 26x26mizushima
  • ああ、はい。そういうことです。
  • 逆に、分岐を含まないなら、一つの文法につき、1通りの文字列しか表現できないので
  • はやみず has joined
  • 12:41am (March 07, 2008) 26x26mizushima
  • LL(0)は正規表現よりも表現力が劣るという…
  • 12:42am (March 07, 2008) 26x26nowake
  • いえいえ、文字そのもの以外に情報のある文法ならば複数の文字列でもLL(0)で処理できますよ。固定長の文字列の塊とか。
  • ですね。>LL(0)は正規表現
  • 26x26mizushima
  • あれ？たとえばどんなのでしょうか＞
  • 26x26nowake
  • 「10文字の塊」とか
  • 「5文字ずつの10グループ」とかですかね。
  • 12:43am (March 07, 2008) 26x26mizushima
  • えーと、それは「１つのLL(0)文法」では表現不可能ですよね？分岐が必要になるような。
  • 「10文字の塊」というのは、何かしらないけど、とにかく10文字の文字列、という意味ですよね
  • 12:44am (March 07, 2008) 26x26nowake
  • そうです。正規表現だと^..........$ですね。
  • 12:45am (March 07, 2008) 26x26mizushima
  • .を展開すると、(a|b|c|...)になるわけで、1文字先読みが必要になりませんか？
  • 12:47am (March 07, 2008) 26x26nowake
  • 文字を必ず取り込む文法（＝失敗がそのまま文法のrejectに繋がる）なら先読みは不要ですよね。
  • あ、“.”は「一文字取り込む」と解釈してください。
  • 12:48am (March 07, 2008) 26x26mizushima
  • はい。それはそうなんですが、LL(k)というのは、どこに分岐するかを「k個のトークンを先読みして」決めるアルゴリズムなので
  • えーと。LL文法(あるいは文脈文法)では、.というのは要素としては存在しないので、(a|b|c|...)の略記法だとするしか無いわけです。
  • 文脈文法→文脈拾文法
  • また間違えた
  • 文脈文法→文脈自由文法
  • 12:52am (March 07, 2008) 26x26nowake
  • 文法として「取り得る任意のトークン」というのはないんでしたっけ？
  • 12:53am (March 07, 2008) 26x26mizushima
  • ええ。そういうのはプリミティブな要素としては存在しないはずです。
  • あったとして、それはtoken ∈ Tokenとしたときに、
  • (token1 | token2 | ... tokenN)
  • の略記法になるという話でｓ
  • です
  • 12:58am (March 07, 2008) 26x26nowake
  • むむむ、そうすると、逆に「全ての１つのトークンを受理する文法」というのを定義した場合、どんなことがおこりそうですかね？LL(k)が破綻するかな？
  • あ、「先読みなしで」という条件を追加してください。
  • 26x26mizushima
  • うーん。
  • 「全ての１つのトークンを受理する文法」というのは、トークン1個で、それがどのようなトークンであっても受理する文法、という意味でしょうか？
  • 1:01am (March 07, 2008) 26x26nowake
  • はい。先読みが発生しないように必ず受理（か拒絶）します。
  • 1:02am (March 07, 2008) 26x26mizushima
  • だとすると、それはそもそもLL(k)の定義に反しているので、無理じゃないかと。
  • 1:03am (March 07, 2008) 26x26nowake
  • むむむむ、「先読みが発生しないように」の言い方を変えて「0個の先読みで受理できるように(LL(0)で)」というのはどうですかね？
  • 1:05am (March 07, 2008) 26x26mizushima
  • それだと、最初の話に戻って、やっぱり無理という結論になるような。
  • ひょっとして、何か解釈の食い違いが生じてるでしょうか。
  • 1:08am (March 07, 2008) 26x26nowake
  • むう……、トークンの扱い方という話になるんですかね？
  • LLの文法で「トークンを数えることができる」ととすると「何でも１つだけトークンを受理する文法」というのが定義できる気がしますが……
  • 1:09am (March 07, 2008) 26x26mizushima
  • あ、はい。LL(k) (k >= 1) ならできるはずです。
  • 方法としては、単純に全種類のトークンを|で並べる
  • (token1|token2|token3|token4|...tokenN)
  • これは、トークン１つ分先読みできれば大丈夫なので
  • あ、ここで前提としてトークンの種類は有限個だと仮定してます。例えば、123,0,1000などのトークンは全部<Integer>という一つのトークンとして切り出されている、と仮定しています。
  • 1:14am (March 07, 2008) 26x26nowake
  • そこで「先読みしようとしている１つ分のトークンを必ず取り込むことにする（＝先読みするのを止めてトークンを消費してしまう）」という文法を定義すれば 「全ての１つのトークンを受理する文法」が定義できると思います。
  • 1:16am (March 07, 2008) 26x26mizushima
  • はい。そういう文法を定義すれば、確かに可能だと思います。ただ、それはLL文法ではない、という話になるかと
  • あー、ちょっとアルゴリズムと文法をごっちゃにして書いたせいでややこしくなった気がしました。整理します。
  • LL(k)「アルゴリズム」は、分岐があるとき、次のk個のトークンを先読みして、その先読みの結果によってどこに分岐するかを決定するアルゴリズムなわけです
  • そして、LL(k)「アルゴリズム」によって解析可能な文法がLL(k)「文法」である、と
  • で、LL(0)について考えると
  • LL(0)アルゴリズムは、分岐があるとき、次の0個のトークンを先読みして、どこに分岐するかを決定しなければならないわけで、
  • つまり、分岐が存在する文法はLL(0)アルゴリズムでは解析できないわけです。
  • そして、.のような要素はプリミティブとして存在しないので、それを１トークンとして、LL(0)で解析できる、というのは変だ、ということです。
  • また、.を分解すると、(a|b|...)のように、分岐が登場する形にしか変換できないので
  • やっぱりLL(0)で解析するのは無理である、というのが自分の結論です。
  • 1:25am (March 07, 2008) 26x26nowake
  • やっぱりトークンの処理の仕方＆プリミティブの定義の仕方ということですかね。何となく判って来たような。ちょっと視点を変えて
  • 前提として「プリミティブではトークンを数えることができない」とした場合（Lexerも解析器に含まれる）、「１つのトークンを受理する文法」というのはすなわちnot 空集合なので、結局のところ(トークン|空集合)の選択が発生している……ということですかね。そうならLL(0)にならないというのも理解できます。
  • 1:32am (March 07, 2008) 26x26mizushima
  • んーと。トークンというのが、(トークンA|トークンB|トークンC...|...トークンZ)の構文糖なので、選択が発生している、と言う解釈の方が
  • 空集合というのは終端記号あるいは非終端記号のどちらでもないので、
  • 文法の中に出現するのは妙かと
  • 思います
  • 1:36am (March 07, 2008) 26x26nowake
  • ふむふむ。終端記号もトークンとすると判りやすいですね。「１つのトークンを受理する文法」というのは正確には「１つの非終端のトークンを受理する文法」ということですか。そうすると
  • 「１つの非終端のトークンを受理する文法」では（終端記号｜非終端記号）という選択が発生している。と。
  • ただ、その時は「終端記号の次のトークンは終端記号」といったように、トークンの判別以外の方法では終端記号を識別できないように定義する必要がありそうですが。
  • 1:39am (March 07, 2008) 26x26mizushima
  • あー、ちょっと混乱されているような。一般に、トークンと言う場合、終端記号として扱うことを暗に意図しています。
  • 非終端記号＝文法の規則の左辺の記号のことです
  • 1:40am (March 07, 2008) 26x26nowake
  • あっと、失礼しました。勘違いです。上の話は「終端記号＝トークン列の終わり（＄）」と読み替えて下さい。
  • でも、勘違いから出て来た「トークン列の終わり（＄）もトークン」の解釈で上手いこと理解できた気がします。
  • 1:45am (March 07, 2008) 26x26mizushima
  • あ、はい。トークン列の終わり($)もトークンとみなすというのは、解釈としては変ではないと思います。
  • 1:47am (March 07, 2008) 26x26nowake
  • 了解しました。そうなら確かにそんな気もします。「複数のトークン列の終わり（＄）の繋がったトークン列」とか変なものが定義できればまた話は別になりそうな気もしますが。
  • はやみず has left
  • 1:49am (March 07, 2008) 26x26nowake
  • あと、蛇足ながらついでに言うと、空集合＝εですので終端記号としては存在しますね。非決定性オートマトンなんかだと普通に使いますし。
  • 1:51am (March 07, 2008) 26x26mizushima
  • 非決定性オートマトンにおけるεはまた別物では？
  • NFAにおけるεは空文字列のことだと解釈してたのですが
  • 非決定性オートマトンだと普通に使う、というのはε遷移のことですよね？
  • 1:54am (March 07, 2008) 26x26nowake
  • あ、そうですね。良く良く考えたらLL(k)は決定的なのに、εで非決定性を入れたら別物になりますね……。boost::spiritでepsがあるのでごっちゃになったみたいです。
  • boost::spritはどちらかというとPEGですね。
  • 1:55am (March 07, 2008) 26x26mizushima
  • boost::spiritは詳しくは知らないけど、PEGに近いということは、バックトラックするわけですね。
  • 1:56am (March 07, 2008) 26x26nowake
  • はい、そうです。バックトラック付きのLL(∞)パーサーです。
  • 2:03am (March 07, 2008) 26x26mizushima
  • そろそろ寝るので落ちます。ではでは。
  • mizushima has left
  • Greatest Lover! has joined
  • 2:05am (March 07, 2008) 26x26Greatest Lover!
  • Hi
  • 26x26nowake
  • お休みなさい。勉強になりました。
  • 私はこれから資料の仕上げですが…………
  • 2:06am (March 07, 2008) 26x26Greatest Lover!
  • ここに何をする所ですか?
  • 2:07am (March 07, 2008) 26x26nowake
  • parserについて話すところです。
  • 26x26Greatest Lover!