Derive Your Dreams

Twitter: @kinaba

16:46 08/03/30

YZ1.DLL

0.30 リリース しました。 具体的には、ヘッダの格納ファイル数フィールドに実際より大きい値が入ってると変なとこ読もうとして落ちるバグ修正。 GreenPad の修正は来週くらいには…。

Booooooost

Boost 1.35.0 来てました。 Asio と Fusion と GIL の三枚看板がでかいですが、Bimap が地味に便利だ。

あと、mbさんのEgg のレビューが明日からでしょうか。(また スケジュール から消えてますが…Protoが入る前までロールバックしてる?) 他人事ながらドキドキ。

17:36 08/03/28

ケース

十年来の疑問なんですが、"case" に単独で対応する日本語ってなんになるんですかね。 "case-insensitive" や "lowercase" の "case"。単に "case-insensitive" だけなら「大文字小文字を区別しない」 みたいに訳せばいいんですけど、"You must use the same case as it was declared." とかそんなんだと、 文全体の構造をグローバルに書き換えるしか思いつかなくて。

ミリオン

「百万ゴールドの男」を読んで面白いと思った人は、 過去作品 一気読みに走るといいよ! 「創作テキストサイト過去ログ」あたり! …などと信者の俺が述べております。

17:05 08/03/25

Road Coloring

The road coloring problem を読んでました。 問題自体知らなかったのですけど、abstract にオートマトンと書いてあったので、ついふらふらと。

この記事 の説明はちょっと変だな。スタート地点がどこであっても「青赤赤青赤赤青赤赤」のぴったり9歩 動くと必ず黄色の地点にいる、というのがこの色分けのポイント。 今どこにいるのか、どこで止まればいいのかすらわからなくても目的地に到着できるのです。 記事にあるような「目的地をいつかは通りがかるような色の列」なら40マイクロ秒くらいで 解かれてると思う。

論文に乗ってた具体的な構成法は、(1) "Spanning Subgraph" を適当に1個作る。 Spanning Subgraph とは、"元のグラフの頂点を全部含む" && "それぞれの頂点について、 それを始点とする辺を1個だけ含む" グラフ。Spanning Subgraph は必ず、「ループとループにぶら下がったツリー」 が何個か並んだ形をしていることに注意。 (2) 作った Spanning Subgraph の「ぶら下がったツリー」部分の高さに注目。 一番高いツリーが1個だけだったらOK、3に進む。同じ高さのツリーが2個以上あったら、 この問題の前提とするグラフでは、どっちかのツリーを変形して「もっと高く」できるのでそうする。 (3) そうしてできた Spanning Subgraph に属する辺を全て同じ色(例えば )で塗る。 残りの辺は他の色で適当に塗る。

…という感じ。これが求める色塗りになってることの証明は背理法なので、 具体的にどう色をたどれば一カ所に集合できるのかは、証明からは直接読み切れてないですが、 直感的には、「赤をたどりまくってループの上に合流して、時々別の色で別のツリーにジャンプ」 を何回か繰り返したら一カ所に集まる感じかな?

"The solution is not that complicated. It's hard, but it is not that complicated," Trahtman said in heavily accented Hebrew. "Some people think they need to be complicated. I think they need to be nice and simple."

After 38 Years, Israeli Solves Math Code

DM2

当然 トーハム・セリ・サロス・アンダース なんですけど相変わらず4人パーティきついな…。

22:12 08/03/23

観光

もっと早くから連休に気づいてたら遠出したんだけどなー、と思いながら ブルーマウンテンズ に行ってきました。 シドニーの街から電車で西に2時間くらい。 東京で言うと 青山 高尾山みたいな感覚です、たぶん。

ここんとこ雨続きだったので山道がデロデロで難儀しましたが、 そのデロデロの土が赤茶くなくて白っぽいというか灰色っぽいのがなんだか新鮮な風景でした。

17:21 08/03/22

言語仕様の大きさ

言語名 Lang Lib
Smalltalk 49 255
Scheme 50 -
Clean 128 -
Standard ML 128 -
Haskell 177 100
ECMAScript 188 -
Eiffel 194 -
C 316 238
C++ 428 358
Ada 461 330
C# 553 -
Fortran 585 -
Java 684 -
Common Lisp 1358 -

PDFのページ数で数えました。 Smalltalk と CommonLisp は正式な規格書を持っていないのでドラフトで数えています。 仕様でライブラリまで定義されている場合、その部分のページ数を「Lib」、 残りを「Lang」と分けています。 Common Lisp と ECMAScript 辺りは、他の言語でなら「ライブラリ」と呼ばれそうな機能まで 「Lang」に入ってるような感じがして微妙ですが、その他の「Lib」のない言語については、 上記の仕様では文字通りライブラリが定義されていない感じです。

もちろんページ数なんてものはレイアウトにも、どのくらい詳細に書くかにも、 どんな表記法を用いるかにも思いっきり依存するわけなので、この表が何か直ちに 意味を持つと言うことはありません。 が、自分の実感にはわりと合っているような気がしたので、その。

本題

つまり、C++ の言語仕様は、 (Java とか C# とかと比べたら)だいぶ個人の手に負える範囲 にあるのではないかと思ったのでした (コンパイラ作る的な意味 で)。今コンパイラ間のポータビリティが怪しいのは、仕様が

  1. 名前のルックアップ規則を正確に把握するのが難しい
  2. 名前のルックアップ規則を正確に把握するのが難しい
  3. 名前のルックアップ規則を正確に把握するのが難しい

などの理由でアレなせいで、これは別に実装にマンパワーがいるとか凄いアルゴリズムが 必須とか言う類の難しさではないですし… あ、export は見なかったことに… まさか C++0xに残る とは。 でも実際、「分割コンパイルはサポートしない」くらいの制限で現実的な目標にならないかな。

まあ、俺はここでgdgd言ってないで作ってみればいいんだよねぇ。ううむ。

12:55 08/03/21

四連休

なんか今日から 四連休 らしい ということを昨日知りました。どっか出かけようかと思ったらいきなり天気が最悪。

とりあえずロードカオスが鬼だった。

C++の本

C++の勉強ですが っていう話題。

私はいつも 「Exceptional C++ は全プログラマ(C++を一切使わない人でも)が読むべき本。 あとはどうでもいい」 などと言ってますが、どうなんでしょうね。 cf. ”技術者”の解放

「C++ 再考」は面白そうなんだけど、噂のほしい物リストに積んだまま全然読んでないや。「Effective C++」の第2版は…17年前なら違ったのだろうけれど、 正直、今では "読むべきでない" 部分すらいくつかあるように思ってしまう。例えば 「コンストラクタでの例外は禁じ手」 なんていう迷信の遠因は Effective C++ の「デストラクタでポインタメンバにdelete を使うのを 忘れないようにしよう」じゃなかろうか、など。 第3版はしっかり改訂されているので (違いをまとめてる方がいらした)、 読むなら絶対に第3版です。ただ、Exceptional C++ 読めば既にほとんどカバーできてるんじゃないかなーとか。

ところで

自分がC++を最初に勉強したのは… 「Visual C++ 4.0 のアカデミック版についてきたC++の解説冊子」 だなぁ。同じ頃 Windows プログラミング始めた人には同じ境遇の人がいたりするかも。 こういうの最近の Visual Stduio には無いよね。ちょっと残念。

11:27 08/03/19

A. C. Clarke

おくやみ:作家 アーサー C. クラーク、90歳

なんと…。自分がはじめて読んだハードSFはクラークの作品だったように思う。 ついでによく考えたら、一番最近読んだSFも「イルカの島」だ。 確か「2010年」だったと思うけど、高度に発達した生命がどのような形に"進化"しうるかの描写、 And now, out among the stars... 以下の数段落はずっと記憶に残っています。凍てついた光の格子の中で。

18:12 08/03/18

MegaTokyo

MegaTokyo にハマっている今日この頃です。

なんか英語でマンガ読むぞーと思ってコミック買ってみたのだけど、これウェブマンガだったのか。 でも作者コメントが面白いので買って良かった。 62 の辺りで4コママンガがギャグばかりだと思うなよ的論争があったらしく、 そこから今の方向にじわじわスイッチしていく流れとかが。 要するに大変ベタベタなラブコメなんだけど、まあそういうのは好きなので仕方ない。 といってもまだ2巻までしか読んでないのでこの先どうなるのかな。はてさて。

Flapjax

チュートリアル日本語版! おおお!

17:39 08/03/17

論文実装レース

SIGGRAPH に対する SBR採択論文が公開されると同時にスタートし、 ゴールをその実装とする人類史上初の公開論文実装レースであるッ!!!』 みたいなのすっごい楽しそうだなーと思うのですよ。

プログラミング言語系でも同じようなイベントは可能だろうか。…てなことを

という過程をたどった結果考えました。 あまりに理論的だったり、大規模な実装や事例紹介的な研究は対象とするのが難しいと思う。 OOPSLAとその併設イベント、とか、ICFPとその併設イベント、とかで結構何とかなったりしないかな。 しかしそれ以前に、 自分が実装したいと思うのは大抵プログラミング言語系というよりデータ構造/アルゴリズム系の話な気がする。 「Haskellを新しい型システムで拡張しました!」とか実装する気にならないし。うーむむむ。

どうでもいい

DWT 使いたいんだけど Tango とか D 1.x とか使う気にならない人の数→ (1)

22:59 08/03/15

ReaJ / Reactive JavaScript

すごいダメダメな完成度ですが一応晒しておきます。

えーとあれです、要するに var x = mouseX + mouseY って書くとマウスの動きに合わせて勝手に x の値が変化する感じの言語です。document.createTextNode("ねずみ @ "+mouseX+","+mouseY") とか書くと勝手に値が変わるテキストノードができます。 この方向性でちゃんとした言語としては FrTimeFlapjax などなど。 追記: Mathematicaすげー!

現状

再計算する範囲を最小限にする実装のなかで一番単純なもの(一つ一つの演算子単位でバラバラに 値を変えられるようなノードにしてそれを繋ぐ実装)から始めて定数畳み込み+α的に最適化しようと 思っていたんですが全然そんなとこまで行っていないのであった。これなら、上の実験ページの見た目を 再現するくらいなら普通に埋め込みテンプレート単位で再計算した方が1000倍マシだ。 実装もきっと1000倍くらい楽だし。まあ、でも

var x = 10;
var y = x + 100;
x = 20;
x = 30;
print( y );

これが 130 になる言語ができたので満足です! Functional Reactive Programming 的にこうなる物なのかどうかは知らないけど、 絶対こんな風になった方が面白くていいと思う。y は x に 100 を足したもので x は 30 なんだから、 y は 130 に決まってるではないか。 いや、わりとマジメにこれ便利だと思うのだ。

で、破壊的代入という副作用はそれでいいとして、環境の操作の方の副作用はいかんともし難くて、 何も手をつけられませんでした。今の実装だと(たぶん)

document.getElementById("hoge").appendChild( document.createTextNode(mouseX) )

って書くとマウスを動かすたびにノードが増えて行くんですけど、これは果たして正しいのだろうか、と。 この例くらいなら「hogeの末尾に、値がマウス座標に合わせて変わるテキストノードを1つだけ挿入」という 動作をさせる実装もすぐにできるんですが、もっときわどい例として

(mouseX%2 == 1
  ? document.getElementById("foo")
  : document.getElementById("bar")).appendChild( document.createTextNode(mouseX) )

を、どうしたものか。制御フローが変わる時に影響範囲全体にundoかけるしかないのかな。 実装していざ突き当たってみるまで全然この辺考えたことなかったや。 Flapjax はこの辺りどうしてるんだろう。

あとそういえば、JavaScript パーザは Top Down Operator Precedence のを使わせてもらいました via h_sakuraiさん。 デモ用に用意されてる構文定義が色々自分の趣味に合わなかったりしたのですが、そういうときでも 確かにこれは読みやすい&&手で弄りやすくていいですね。

12:25 08/03/14

DMRTC

Wizard Eye が強すぎて笑えてきた。視認できない距離から遠距離魔法飛ばしてきて 二発当たると確実にパーティー全滅級のダメージとかもうね。素晴らしいですね。 おかげでPhobosの翻訳もGreenPadの修正もProject Eulerの新問題もEarley Parser実装祭も 1ミリたりとも進まないのが問題ですね。

Reactive!

新山さんメモ で Flapjax の話が出てたのを見て、ふと、これの真似っ子実装してみようと思い立ちました。 「世の中に色々なパラダイムはあるけれど、その中で Reactive Programming だけが世界を変える可能性がある」 などと、実装したことすらないのに思っている自分は滑稽であるので一度作ってみないといけない。 てなわけで明日やる。12時間勝負。

15:47 08/03/11

DM

唐突に ダンジョンマスターRTC を始めてみました。

ゲームは一度もやったことなかったんだけど 小説 は昔すごい好きだったので ヒッサー、ゴスモグ、ウーツェ、シラ のパーティでGo。 操作方法よくわからずに手探りでやってるせいもあって今のところ 戦士、松明、薬草、薬草 みたいな、 ヒッサー以外存在意義がわからん状態なんですけど、こんなもんなんだろうか。 今地下3階(2階?2回階段降りたとこ)。

auto

この辺のvar/autoに関する議論 を読んでて。

感覚的に、変数には「オブジェクトに名前を付けるもの」として使う場面と「式に名前を付けるもの」として 使う場面があって、 要するに 箱モデル と 名札モデル ね。 ちょっと違うかな。まあいいや。 で、(言語の実行モデルがどうであるかとは関係なく、)前者の感覚で使う変数もあれば 後者の感覚で使う変数もあって、みんな、基本的には前者なら型を書くし後者なら auto/var で省ける、 というところまでは一致していると思うのだ。

違いはどっちの感覚で使う変数の割合がどのくらいか、という個人差。要するにNyaRuRuさんのおっしゃっている "仮名漢字変換を単文節でぶつ切り変換するのが好きか,長文で一気に変換するのが好きかみたいなもので, もはや好みの問題かなぁという気もします." という話で、 「なんでもvarにすると変数に込めた意図が失われる」人とそうでない人とでは、そもそも「意図」の時点で 違うっていう、ただそれだけの話なのではないかと。

で、そういう意図の持ち方は良い/悪いの議論は大いに盛り上がると楽しいと思うんだけど、 ただこれは、純粋に個人の好みの差違であって言語の差違ではないと思うのだよね。つまりどうも自分には "C++畑の人は""C++プログラマ達にとっては""C#とC++は違う言語だから" みたいな一般化が納得いかない。確かにC++の変数は箱モデルかもしれないけれど、それは関係ない。 あれは必要ならいくらでも名札的に振る舞わせることができるし、実際、モダンなライブラリには 名札的なものが多い(と自分は感じる)。 型名を公開したら負け みたいな作りを見ると(自分の場合は)そう思う。

10:02 08/03/09

締め切り

おわた!

"最もタメになる「初心者用言語」はR" を読んでマジメに R 格好いい!! と思ったりして最近 R で遊んでます。 example いいね example。しかしひととおり触ってから思うに、特に分析したいデータもないので なかなかそういうRっぽいところに慣れる機会がないな。しばらく分析したいビューで世の中を見ることにしよう。

Uniqueness Typing Simplified の中で引用されてた説明 in linear logic, "linear" means "will not be duplicated" whereas in uniqueness typing, "unique" means "has not been duplicated というのがなるほどなーと思った。

10:15 08/03/06

それはそうと

今日から ^Z 才です。うわー。

10:21 08/03/05

構文解析の話をしよう

LL(1) とか LALR(1) って要するに何? っていうのを、思いっきり大ざっぱに紹介してみたいと思います。 細かい具体的な実装方法は本なりWebなり探せばいくらでも見つかると思いますので、全部省きます。

まず構文解析ってなに

単語の列を、文法と照らし合わせて解釈する作業のことです。 プログラミング言語の場合、要するに、ソースのこっからここまでがif文で、こっからここまでが 1個の関数定義で、この部分はクラス定義で、ここからここは足し算してる式で…みたいな、 ソースコードの構造を完全に判定する作業です。

プログラミング言語的には「単語」のことを「トークン」といいます。「if」とか「else」とか 「+」とか「<=」とかがトークン。

d & d

プログラミング言語の構文解析には、"directional" で "deterministic" な手法が好まれます。 "directional" というのは左から右に順番にトークンを読みながら順番に構造を判定する、ということ。 「ちょっと突然一番最後のトークンが知りたくなった」とか言ってジャンプしたりしない。 "deterministic" というのは、一度判定した構造を絶対取り消さないこと。「ここif文っぽいから とりあえずif文と思って解析続けてみてダメだったら取り消し」とか軟弱なこと言わない。 好まれるのは何でかというと、速いから。あとメモリもあんまり喰わない。

で、"directional" で "deterministic" な手法は、大きく分けて2つあります。 LLLR です。

LL

LL(1) 法というのは、構文のはじめの 1 トークンで構造を決定していく方法。

if

っていうトークンを見たら即「ここからif文がはじまる!」と判定する。 もう即座に new IfStatement() とか言って構文木作っちゃう。

def

っていうトークンを見たら「関数定義キタコレ!」と決めつけちゃう(RubyとかPythonの場合ですね)。

LL(2) 法なら、はじめの2トークンまで見て決める。LL(3) なら、はじめの3トークン。以下略。 LL(0) は、要するに1文字も見ずに「次絶対if文来るね。マジ。間違いないね」とか予言しないと いけないのでつまり絶対無理なので、LL(0) という方法はありません。

LL(k)法は、構文の開始よりkトークン先まで読んで構文を予測するので、 「k トークン予測先読み (prediction look-ahead) する」などと言います。 あんまり言わないかもしれない。

逆に、LL(1) じゃない文法も見てみよう。C言語。

foo

って先頭のトークン見ても、これから foo = 100; っていう代入文が始まるのか、 foo myfunc(); っていう関数宣言が始まるのか、はたまた foo[1]("hello"); という配列アクセスした上に関数呼び出しという怪しげな文が 始まるのか、まったく予測できない。こういうのは LL(1) じゃない。

実際のところ、四則演算の数式の文法が LL(1) で書けるとか、はじめの1トークンで「予測できる」 「予測できない」っていうのはそのままの直感とは外れるところもあるかとは思うんですけど、 基本的には、「最初の1トークンで何の文かわかるようになってる言語/文法」はLL(1)っぽいといえる。

LR

LR(0) 法は、構文のおわりのタイミングで 「あ今if文終わったちょっとストップ」とかいう雰囲気で構文を判定する手法。

(foo bar buz)

の閉じ括弧を読んだそのタイミングで、「はいはいS式S式」って言って、「前の括弧から今の括弧までがS式でした」 と構造をひとつ決定する。

while(...) { ... }

の閉じ中括弧を見た時点で、「whileオワタ」って言って、「バランスする中括弧の手前のwhileから 今の中括弧までwhile文でした」と決める。

一応構文をおわりまで読んでから決定するので、LL系の方法よりもLR系の方法の方が、何かと 判定能力は高かったりします。が、LR(0) はやっぱりちょっと弱いので、ここでも「先読み」 が活躍します。

SLR(1) 法は、構文のおわりのさらに次の1トークンまで見て決断を下します。 LR(0) は先読みできないので例えば

if(...) { ... }

ここまで読んだ時点で、「今elseなしif文終わったよ!」と宣言しちゃってよいものか、 それとも、次elseが来る可能性があるのでここはスルーして

if(...) { ... } else { ... }

になるのを待ってから「これぞif文!if文完成!」と叫ぶべきなのかわからない。 ちなみに「今○○文終わったよ!」と宣言することを専門用語で「reduce」といい、 スルーして次のトークンを読み込むことを「shift」といいます。 reduce すべきか shift すべきかわからなくて困ることを「shift/reduce conflict」と言います。

って、そうだ、SLR(1) の話をしてたんだった。SLR(1) の場合は、

if(...) { ... }

この時点で、その次のトークンまでチラ見してから判定します。次が例えば「while」だったら、 「else無しif文でした!」って宣言しちゃっていいし、次が「else」だったら、 「else無しif文の後ろにelseが来るとか常識的に考えてあり得ない」ので、ここはスルーして良い。 このように、チラ見した次のトークンを使って、「○○文の後ろに△△が来ることがあり得るかどうか」 を考えて判定するのが SLR(1) です。

SLR(2) なら構文の後ろの2トークンを見て判定するし、SLR(3) なら3トークンを見て判定する。 構文のおわりのタイミングで判定するので、1トークンも先を読まないで判定する LR(0) はあり得ます。 LL(0) があり得ないのと対照的です。

SLR(k) の先読みは LL(k) と先読むところが違って、構文のおわったその後のトークンを読んで、 reduceするかしないか決めるものです。なので違う名前もついていて、 「還元先読み reduction look-ahead」などと言う。

LALR(1) は、SLR(1) をちょっと賢くした感じ。 同じ○○文でも、「後ろに来ることがあり得るトークン」は、場所によって違うのですよ。

struct foo { int x; ★
void foo() { int x; ☆

こんな感じで、同じ変数宣言 "int x;" の構文でも、構造体の中でやったときと、 関数の中でやった時では、後ろに来れるトークンは違う。例えば "for" は☆には来れるけど ★には来れない。まあこれはあんまりいい例ではないですが(実際のCの変数宣言の文法は そもそも構造体内と関数内で完全に別物ですし)、まあそんな感じで、とにかく 「後ろに来ることがあり得るトークン」は場所によって違う。

というわけで、「○○文の後ろに△△が来ることは一見ありえるのでここはreduceすべき かもしれないが、今まで読んだトークン列をみる限りこの○○文は□□文の中の○○文なので その場合は△△は絶対後ろに続かないから正解はスルーだ。shiftだ。」みたいに 大変インテリジェントなのがLALR(1)です。

以上

たぶん間違いだらけなので突っ込み期待しています!

細かい補足

  1. "directional" で "deterministic" な手法では絶対に解析できないことが証明されている文法、 などというのも存在します。つまりLL(k)やLALR(k)は万能ではありません。
  2. CYK法、Earley法、GLR法、などの "directional / deterministic" ではないけれど万能な手法、 も知られています。ただ、遅いのでプログラミング言語に対してはあまり使われません。 設計者が文法自分で決められるんだから、"directional / deterministic" に収まるように 文法作ればいいじゃないみたいな。GLRは最近使われてるのかな。どうなんだろ。
  3. 逆に、人間が話す自然言語の構文解析では、文法を自分で決められない、比較的遅くてもいい (ひとつの文はせいぜい数十単語。日常的に数十KBのソースが飛んでくるプログラミング言語とは 桁が違う)などの理由で、万能な手法の方がよく使われるらしいです。知らんけど。
  4. LR系の、「今の○○文だった!」判定は、正規表現とかと同じ「オートマトン」を使って、 非常に効率よく判定できます。中括弧が来たときに"これwhile文だっけif文だっけ…?"とか 毎回今まで読んだ文字列を戻って見直したりしなくていい。というかそこがまさにLR(0)の アルゴリズム的なポイントなんですが説明めんどいので略
  5. SLR(1) や LALR(1) は、それぞれ S(1)LR(0) とか LA(1)LR(0) とでも呼ぶべき物で、 基本はLR(0)です。これに対して LR(1) という手法もあって、最後に説明した LALR(1) に非常に近い「後ろに来ることがあり得るトークンは場所によって違う」原理に基づく方法です。 LALR(1) よりも更に抜本的改革を施して、今の「場所」がどこなのかをより精密に区別するのがLR(1)。
  6. ただ、そこまで頑張らなくてもLR(0)にちょっと工夫すれば実用的に精度十分じゃね? っていうのがLALR(1)で、実際精度十分だしメモリ喰わなくて素晴らしいので、 今やみんなLALR(1)を使ってます。ということでLR(1)は説明しない主義。
  7. 「今まで読んだトークン列からして今いる場所は○○文の中だ」的な情報は、LALR(1)やLR(1)だけでなく LR(0)やSLR(1)でも使っています。○○の中に来ることがありえない様な構文に関するreduceはしない、とかは 考える。その位置情報を先読みの可能性にまで反映するのがLALR(1)。しないのがSLR(1)。
  8. shift/reduce の他にもう一つ考えられる conflict が、reduce/reduce conflict。 「今掛け算式が終わったようにも見えるが、ポインタ外しの式が終わったようにも見える。 どっちが終わったって宣言していいのかわからん!」てのがreduce/reduce conflict。 x = (foo)*bar とかですね。
  9. 一応念のため、shift/shift conflict はあり得ない。スルーしていいのかスルーしていいのかわからないって、 スルーしろよ!
  10. 「LLっぽさ」は直感的にすぐわかるのですが、「LRっぽさ」はあまり明らかではないと思う。 「LR(1)とLALR(1)の違いを直感的に把握したい!」とか無理だと思うのであんまり 深く考えない方がいいような気がする。
  11. 追記:LLとLRという名前ですが、どっちも一文字目のLは「左(Left)からソースコードを読んでいく」の意味です。 二文字目は、LLは「構文の左端/はじめで判断するのでL」、LRは「構文の右端/おわりで判断するのでR」。 (…本当の意味はちょっと微妙に違うんですが、そんなに激しくは違わないので、 まあ、覚えるときはそう覚えると楽)
  12. 追記2:みずしまさんに突っ込みいただきました感謝。 実用的意味はともかく LL(0) は「1つの文字列しか含まない言語」を構文解析できる(1つしか 可能性がなければ予言も100%当たりますよね)ので、"ない" と言い切るのはどうか、という。まさにその通りです。
  13. 追記3:ついでだから自分で書き方悪いなーと思ってる点を全部追記しちゃえ。 LR(1)はLL(1)より完全に強力なのですが、LR(0)やSLR(1)やLALR(1)は、終わりまで読むからと 言ってLL(1)より全ての場合で判別力が上とは限りません。一長一短あります。 そうは読めない書き方をしてしまった気がして反省。
  14. 追記4:あとなんかあるかな。
  15. 追記5:yuizumi氏から、 自然言語の構文解析で決定的ではない手法が使われる背景には、 本質的に「そもそも文に対する(文法的な)解釈が一通りとは限らない」 というのがあるだろう、という突っ込み。確かにその通りだ。ありがとうございます。

15:06 08/03/03

続D言語BOF

てことで動画upされてるみたいです。わーい。 itouh2さんの発表を中継で見られなかったので今からチェックせねば。 みんな見るべし見るべし。私の部分40秒くらいしか撮れてなかったみたいなので、 前半の様子を知りたい人は各自妄想で補完すべし。

パーサ

手書きでパーサ書くなら文法をLL(1)にして再帰下降、というのが一般的だと思うのですけど、 LR(0) や SLR(1) も適当でよければ手書きできて、結構それなりにわかりやすかったり 使いやすかったりするのではないかという気が昨日からしています。適当というのは reduce判定をオートマトンでやるのではなくて毎回スタックを覗く感じの実装で。

どうなんだろう。適当に検索したら comp.compilersの記事 がなんか出た。

22:55 08/03/01

D言語BOF

でした。 なにもたいしたことしゃべってないけど一応 プレゼン資料 です。 遠隔プレゼンは思ったよりだいぶ大変だった…。 企画たてて下さったberoさん、楽しい発表を聴かせてくださった発表者のみなさま、 集まって盛り上がったDゲンガーのみなさま、 そして録画配信スペシャリストのcojiさん、 感謝感謝であります。

Haskell Hackathon

で、終わってから Haskell Hackathon にひっそり参加。こんな感じになりました。結局Dでトライ。

遅延評価とパターンマッチの実装に目標を絞って行きました。 型とかインデントとかIOとかは考えない。たらい回し関数が速くて 無限リスト[0,1,2,...]が作れてifを関数で実装できたので、まあいいんじゃないでしょうか。 IO は shinh さんが FizzBuzz 言ってたのを見てそうか FizzBuzz しなきゃと思って print と >>= だけ足してみた。 翌日追記:どうみても >> です修正。

presented by k.inaba (kiki .a.t. kmonos.net) under CC0