はてなキーワード: バッカスとは
http://tradenote.info/blog-entry-3.html
一般に、バッカスナウア記法は正規表現では処理できないネストの階層を記憶できるなどの根本的な差があります。
これは正規表現が有限決定性オートマトン(DFA)ないしε遷移と不特定の同種記号の遷移を用いる非決定性オートマトン(NFA)に基づいているのに対し、BNF記法での解析は必然的にスタックを内部状態に持つからです。
https://ja.wikipedia.org/wiki/LL%E6%B3%95
これは左からトークンを走査して、導出する非終端記号を左から決定していくアルゴリズムです。
例えばA→A Bという構文規則があった場合に、Aの還元内でAを還元できるかどうか判定し続けて無限ループに陥ってしまい、いつまで経ってもBの判定に辿り着けません。これを左再帰といい、LLでは左再帰を直接扱う事ができません。
非終端記号の間接的還元を考慮したはじめに現れる終端記号の集合(FIRST集合)を構築して上手く左再帰を回避しなければなりません。
マッチングに用いる規則をベタに関数内部に再帰させながら順番に書いていくだけなので実装は容易です。
https://ja.wikipedia.org/wiki/LR%E6%B3%95
https://ja.wikipedia.org/wiki/LALR%E6%B3%95
こちらは左からトークンを走査して、導出する非終端記号を右から構築するアルゴリズムです。
BNF構文規則から走査に相応するDFAを構築し、DFAの遷移を記憶しながらスタックに状態をpush/popし構文解析を行います。
なのでLL法にあるような左再帰を直接扱えないという欠点がなく、むしろスタックが簡潔になるため積極的に左再帰のBNF記述を行った方が効率よく処理を進められます。
LR法はDFAの大きさが巨大になるため、実用的ではないようです。
LALR法はLR法を改良したアルゴリズムで、扱える構文クラスの範囲はLRよりも少し小さくなりますが現実的な計算資源で構文解析を行う事ができます。
バッカス「ついにきたか ゆうしゃよ
やくそくはおぼえているな?
さあ わしのさけをのむのだ!
1番目「なぜ あなたの
さけをのまねば ならないんだ!
おしえてくれ!
バッカス「さけをのんだら
おしえてやろう さあ のめ!
2番目「あんたを やっつけたら
さけがらみのしっぱいを なかったことにできなく なるんだろう?
そんなばかなこと できないよ
バッカス「ふっ
わたしに かてるきでいるのか?
てかげんは せんぞ!!
飲み会終了後
ひほう
さけのマギ を てにいれた!
ひほう
さけのマギ を てにいれた!
ひほう
さけのマギ を てにいれた!
ひほう
さけのマギ を てにいれた!
ひほう
さけのマギ を てにいれた!
ひほう
さけのマギ を てにいれた!
ひほう
さけのマギ を てにいれた!
ひほう
キクマサムネ を てにいれた!
バッカス「よくやったぞ ゆうしゃよ
わしは さけのちからで
おおくのせんしたちに
さけを むりじいしてきた
だが わしは ながくのみすぎた
さいきょうの せんしとさけをくみかわし
おおしく いきをひきとるのが
わしののぞみであった
1番目「バッカス‥‥
バッカス「まるで げこたちに
かこまれておるようだ‥‥
わしが しんだら
もう さけのせきでのぶちょうほうを なかったことにすることは
できない! こころして すすめ!
‥‥さらばだ‥‥
腰は痛いし、頭からは痛い妄想が飛び出してくるし…
なんか、今日ひさしぶりに「トーマの心臓」の1巻を読んだら、あたまの中に妄想がひろがるんだ。それも酷い話でユリスモールが居なくなってから、彼を失ったこころのすき間に苦しんでいたバッカスとオスカーが、親密になることでそのすき間を埋めようとする、っていう下らない話。少し秋の見えてきた季節に二人は結局自分達がユリスモールになにもしてあげられなかった事とか、そしてなにもしてあげられなかったのに、ユリスモールがトーマとかエーリケとかの力で勝手に立ち上がっちゃった事とか、そのプロセスにあんまり噛めなかった事とか、全てを知りながらみているしかかなかった事とかを悔やみながら、親密になるんだ。で、見せ場のシーンは足元がだんだん紅葉してきた草っぱらで二人してタバコをすっていると、バッカスが突然オスカーの手を握るんだ。そして、オスカーはその手をそっと握りかえす。握りあった手をアップでうつして、背後にバロック音楽掛がBGMに流れて終わり。ってくだらねー。これがエンドレスで繰り返す。っていうか、なんで今「トーマの心臓」なの?