K.Maebashi's BBS

はじめまして。 >ちなみに私は >if() { > ... >} >else { > ... >} >と、そうとう変則的です。 でも、この書き方はたまに見かけると思います。 私も当初、else ifごとにコメントを入れたくて、そういう書き方にしていた頃があります。 if () { ... } /* ほにゃららの場合 */ else if (ほにゃらら) { ... } と書くわけです。でも、当時ソースをプリントアウトしたとき、紙の切れ目で「}」が来ると、 そこでif文が終わりなのか判定しにくいと思いやめました。 >ご挨拶が遅れました。はじめまして。私のところにいらっしゃるときと雰囲気が違うので驚きました。 す、すみません、「酔漢」さんがどなたかわかりませんです。 私が定期的に書き込んでいる掲示板等は、そんなにないと思うのですが…

begin/endか{/}かというページを読んで、昔読んだインデント論争を思い出しました。こちらもbit誌の連載で、その後単行本に収録されたはずですが、実家の両親に捨てられました。 SIGPLAN　NOTICEの読者投稿で行われた「インデントはいかにあるべきや」という論争で、今で言えば、C言語のifに続く{はifの行末か、ifの次の行で同じ深さか、はたまた一段落とすかという話です。最後は編集者が「もういい」と打ち切ったそうです。 ちなみに私は if() { ... } else { ... } と、そうとう変則的です。最近は誰も「宙ぶらりんのelse」の話をしないので寂しいです。 ご挨拶が遅れました。はじめまして。私のところにいらっしゃるときと雰囲気が違うので驚きました。

このところどたばたしてまして返事が遅くなりましてすみません。 >で、思ったんですが、よくよく考えてみればC言語には昔からオブジェクト指向の標準関数がありますね。FILE * を介して行なうファイル入出力です そう思います。以下のページにそんなことを書きました。 http://kmaebashi.com/programmer/c_yota/inherit.html >その他、X Window System の Xlib やそのツールキットもオブジェクト指向です。 それも上記のページに書いています。 「疑り深い～」に書き足すかどうかはちょっと保留にさせてください。 # ていうか今は無理です。

で、思ったんですが、よくよく考えてみればC言語には昔からオブジェクト指向の標準関数がありますね。FILE * を介して行なうファイル入出力です (これだけでもう分かると思いますが、fopen() が新しいインスタンスを作る new のようなもの。fclose() が C++ の delete のようなもの。fprintf()やfgets()などの入出力関数は全て最初に作った FILE 型領域へのポインタを介して行なって、違う FILE * だと違うファイルが対象になります)。 解説にその辺のことも付け加えるといいんじゃないでしょうか。これならよほどの初心者か特殊な環境のプログラマでない限りは使ったことあるでしょうから理解され易いと思います。 p.s. その他、X Window System の Xlib やそのツールキットもオブジェクト指向です。

最近STLを勉強していて、C++の標準にはハッシュはないので 何で実現するかに迷っています。 もちろんアプリや目的が何かが重要ですが、実行速度優先で 考えていて、mapは遅いので使えないです。 ハッシュ関数はint値をテーブルサイズで割った余りを 返すという単純なものを考えています。 候補としては、以下のものを考えているのですが、 もっとうまい方法や常套手段はあるのでしょうか？ 1) VC++のhash_map 2) SGIのhash_map 3) STLportのhash_map 4) templateで自作する .NET2003のVC++を使っているので1)か4)で考えているのですが、 良いサンプルがなかなかなくて、標準に入ってないだけで 結構苦労してます。慣れの問題かもしれないですが。 MSDNにも簡単なサンプルしかないし。

>　私もそう思いますが、「センス・オブ～」でそう書いたところ査読して > くださった方からの反論があり、多少表現を変更した、という経緯も (^^; (^^; Cで単方向リストを書く場合、私も先頭のダミー要素は使いません。 リンクポインタへのポインタを使えば、不要になるからです。 でも、Lisp 文化圏あたりでは、ダミー要素も割と当たり前に使うんじゃ ないでしょうか？ というか、C と C++ 以外の（リンクポインタへの ポインタを使えない) 言語では、わりと使うことが多いような。 あと私は、Cでも双方向リストを書く場合には、ほとんどの場合、環状にして ダミー要素を使います。結構そういう人は多いと思うんですけど、そうでも ないですかねえ。 試しに Java の標準ライブラリ jdk-1_5_0-src-scsl/j2se/src/share/classes/java/util/LinkedList.java を確認してみましたが、やはりダミー要素を使っているようですよ。

>listのsortとアルゴリズムのsortやqsortなら後者の方が速いような気がしますが(気がするだけですが)、 >その話ではないのです。紛らわしくてすみません。 >連結リストを自分で実装した場合の話です。 > >↓の最後の方法のことを言いたかったのです。 >http://www.kouno.jp/home/c_faq/c13.html#10 了解しました。 ありがとうございました。

>先頭に置くなら番兵とは呼ばずにダミー要素と呼ぶべき。 　私自身そう呼びますが(センス･オブ～ではダミーノードと呼んでいた)、774RRさん自身が「それとも最初に作ってる sta は番兵？」と書いておられるので、先頭のダミーノードを番兵と呼ぶ文化圏というのもありなのかなあ、と私は解釈しましたが。 >１方向リンクリストでも使わないほうが自然でしょう。 　私もそう思いますが、「センス・オブ～」でそう書いたところ査読してくださった方からの反論があり、多少表現を変更した、という経緯も (^^;

>自分自身、リストの有用性自体をはっきりわかってないと思っています。 　crowbarのcrowbar.hを見ると、連結リストをかなり使っていますね。 http://kmaebashi.com/programmer/devlang/crowbar_src_0_4/S/6.html 　動的に追加される要素は、ランダムアクセスの必要がない限り、たいてい連結リストにしている、という感じです。 　途中への追加とかがなくても連結リストを使っているのは、単にrealloc()で配列を伸ばすのが面倒だとか、型Tの配列をrealloc()で伸ばすとTのポインタが変わってしまって誰かが指していたときに困るとか(Tへのポインタの配列にすればいいんだけど)、create.cでの解析木の構築はrealloc()できないMEM_storage_malloc()を使っているとか、事情はいろいろありますが、単なる私の「癖」のような気もしないでもないです。

いろいろどたばたしておりまして、返信がずいぶん遅くなりましてすみません。 >私が初めて買ったCの入門書には「if文は入れ子を避けるために二分岐処理に限定してswitch文の使用を検討しろ」というようなことが書いてありました。 　以前の同僚で、「昔はelse ifという書き方が大嫌いだった」というのがいました。 　「昔は」と言っていたのでその後改宗したわけですが、「if～elseは二分岐処理に限定して使うべき」と昔は思っていた、ということでしょう。私には理由がよくわかりませんが、そう思う人はいるらしい、ということで。

>>＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略 > >配列へのコピー時間はなしにしても、list#sortよりも早いのですか？ >qsoってqsort()のことですか？ listのsortとアルゴリズムのsortやqsortなら後者の方が速いような気がしますが(気がするだけですが)、 その話ではないのです。紛らわしくてすみません。 連結リストを自分で実装した場合の話です。 ↓の最後の方法のことを言いたかったのです。 http://www.kouno.jp/home/c_faq/c13.html#10

>う、確かに難しかったかも知れません(書くのはともかく読むのは)。 > >　1.最初の要素をピボットにして、 >　　残りの部分をピボット未満の要素のリスト(left)とピボット以上の要素のリスト(right)に分割する >　2.それぞれをソートする >　3.leftと最初の要素とrightをこの順に繋げる > >ということをやっています。 >＃ それぞれを関数化すべきでしたね。 >＃ ちなみに簡単だと思った理由は(ループが1重は冗談として)分割した後の領域の境界について考える必要がないからです 解説ありがとうございます。 簡単かどうかは置いといて、結局やっていることは アルゴリズム的には、配列と同様なことをやっているようですね。 但し、配列とリンクリストは要素へのアクセス方法(の実装)は 違いますが。 >まあ、クイックソートは最悪の場合 O(n^2) になってしまうわけで、 >ランダムアクセスできないとどうしても、 >それを避けるために書いたコードのせいで定数項が大きくなってしまいそうです。 >＃ gccのSTLの実装ではランダムアクセスイテレータにしかできないことばっかりやってたり > >リンクリストの場合はデータ構造を直接いじってマージソートしてしまった方が速いでしょうしね(std::listは実際にそうなっていますが)。 確かに、std::listは、ソート用の自前のメンバ関数を持っていましたね。 >＃ ちなみに上で説明した方法もデータ構造を直接いじっています >＃ ですから、std::sortでは同じことは出来ません > > >>NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 > >平均(のオーダー)は O(n log n) ですが最悪だと O(n^2)です。 結局、std::listで、std::sortが使えないのは、実装がstd::listだけ 特殊扱いになってしまうのでできないということですね。 containerによって場合分けするなら、配列と同様な計算量で 実装できるから問題ない訳で、std::sortは、 汎用的な実装をしているというだけですね。 汎用的と言っても、配列(系)の実装を想定しているだけだと思いますが。 >＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略 配列へのコピー時間はなしにしても、list#sortよりも早いのですか？ qsoってqsort()のことですか？

勘違いがあったので訂正します。 >>ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 ピボットを選ぶのは関数呼び出し1回につき1度だけなので、頭から順にアクセスしていってもオーダーは変わりませんね。 という訳で「ワーストケースに対応できない」というのはこの意味では嘘でした。 >>実装はリンクリストの方がむしろ簡単だと思います。 > >クイックソートがリンクリストで実装できるのは知りませんでしたが、 >私はNykRさんの実装が難しくて理解できませんでした う、確かに難しかったかも知れません(書くのはともかく読むのは)。 　1.最初の要素をピボットにして、 　　残りの部分をピボット未満の要素のリスト(left)とピボット以上の要素のリスト(right)に分割する 　2.それぞれをソートする 　3.leftと最初の要素とrightをこの順に繋げる ということをやっています。 ＃ それぞれを関数化すべきでしたね。 ＃ ちなみに簡単だと思った理由は(ループが1重は冗談として)分割した後の領域の境界について考える必要がないからです >STLのsort()はランダムアクセスイテレータが必要ですが、 >私のイメージは、listはクイックソートに対して、 >実行効率の面で現実的ではないからできないのだと思っています。 >実装が簡単だというのも重要だと思いますが、 >(STLは)ライブラリなのであくまでもパフォーマンスが問題で、 >やはりリンクリストでは配列と同等のパフォーマンスが >でないのではないでしょうか？ まあ、クイックソートは最悪の場合 O(n^2) になってしまうわけで、 ランダムアクセスできないとどうしても、 それを避けるために書いたコードのせいで定数項が大きくなってしまいそうです。 ＃ gccのSTLの実装ではランダムアクセスイテレータにしかできないことばっかりやってたり リンクリストの場合はデータ構造を直接いじってマージソートしてしまった方が速いでしょうしね(std::listは実際にそうなっていますが)。 ＃ ちなみに上で説明した方法もデータ構造を直接いじっています ＃ ですから、std::sortでは同じことは出来ません >NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 平均(のオーダー)は O(n log n) ですが最悪だと O(n^2)です。 ＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略

>クイックソートは、アルゴリズムそのものにはランダムアクセスは不要です。 >ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 >実装はリンクリストの方がむしろ簡単だと思います。 クイックソートがリンクリストで実装できるのは知りませんでしたが、 私はNykRさんの実装が難しくて理解できませんでした (いやみではありません。能力的な問題です)。 STLのsort()はランダムアクセスイテレータが必要ですが、 私のイメージは、listはクイックソートに対して、 実行効率の面で現実的ではないからできないのだと思っています。 実装が簡単だというのも重要だと思いますが、 (STLは)ライブラリなのであくまでもパフォーマンスが問題で、 やはりリンクリストでは配列と同等のパフォーマンスが でないのではないでしょうか？ NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 クイックソートのアルゴリズムにランダムアクセスがなくても 実装可能だと言うのは了解しました。

>>startは、staをさしている訳で、エラーの原因はstaは >>動的に確保されたオブジェクトではないからです。 >御意なのですが、だからといって最初を除外して free するというのも間違いと思う。 間違いではないと思います(逆に正解だとも言えません)。 ある意味どっちでも良いと思います。 サンプルの例ではauto変数であるstaがリンクリストの先頭な訳で、 これをそのまま(あるいはアドレスを)渡した方が分かりやすいと思った訳です。 free_list(sta.next);やfree_list(start->next);は分かりにくい気がします。 何でリンクリストの先頭(あるいはリンクリストそのものを表すもの)を 渡さないで、nextの要素を渡さないといけないのかという気がします。 確かに関数の汎用性を考えれば最初を除外するのは良くないと思います。 しかし、そういう次元の議論ではありません。 また、そもそもマルチプルインスタンスを考えた実装にはなっていないので マルチプルインスタンスに対応しようとすると破綻するのはしょうがないと 思います。 私ならlist(は名前を変えたい)の上にラッパーの構造体 (仮にllistとしましょう)を作成し、その中にlistの先頭を入れてあげます。 こうすれば、llistの中にダミーのstaも持たせることできますし、 どうにでも実装できます。free用の関数も以下で問題ないです。 free_llist(llist *head); マルチプルインスタンスだって当然できます。 問題は、どこまで実装を抽象化するかであり、今の負け組一号さんの 実装を踏襲するならば774RRさんのご指摘通り、問題点は多いです。 >リンクリストで番兵を使うというのが根底の発想として間違っている気がします。 また、これも間違っているとは断言できないと思います。 あくまで実装の問題で、実装を分かりやすくするために 番兵を入れるのであって、番兵を使うのが間違いではないと思います。 但し、負け組一号さんの番兵(ダミー？)の使い方が適切だとは 私も思っていません。

話の腰を揉んでみるテスト。ふにふに >リンクリストは、要素(サンプルの場合、list)を削除する処理が >配列に比べて早いというのが一般的に言われています。 リストを使う理由としては、配列だと削除された要素の後ろの要素を指すイテレータの扱いに困る、というのもありますね。 STLではそういうイテレータは無効になります。 >また、ソートに関しては基本的にリンクリストより配列の方が早いと思います。 >と言うのも、例えばクイックソートを使うならランダムアクセスが必要になるので >そもそもリンクリストでは(クイックソートは)無理です。 クイックソートは、アルゴリズムそのものにはランダムアクセスは不要です。 ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 実装はリンクリストの方がむしろ簡単だと思います。 void quick_sort(Node ** head_p) { if (*head_p != NULL && (*head_p)->next != NULL) { Node *p; Node *left = NULL, *right = NULL; Node **left_p = &left, **right_p = &right; for (p = (*head_p)->next; p != NULL; p = p->next) { if (p->value < (*head_p)->value) { *left_p = p; left_p = &(*left_p)->next; } else { *right_p = p; right_p = &(*right_p)->next; } } *left_p = *right_p = NULL; quick_sort(&left); quick_sort(&right); for (; *left_p != NULL; left_p = &(*left_p)->next) ; *left_p = *head_p, (*head_p)->next = right; *head_p = left; } } ＃ いや、ループが1重で済んでるし＜簡単

話の腰を折りまくります。 >774RRさんがおっしゃっていたようにstaは番兵ですね。 リンクリストで番兵を使うというのが根底の発想として間違っている気がします。 >startは、staをさしている訳で、エラーの原因はstaは >動的に確保されたオブジェクトではないからです。 御意なのですが、だからといって最初を除外して free するというのも間違いと思う。 tree や環状リストで番兵を使ったりはしません。 １方向リンクリストでも使わないほうが自然でしょう。 もし仮に番兵を配置するならリンクリストの末尾に置くのが適切です。 先頭に置くなら番兵とは呼ばずにダミー要素と呼ぶべき。 そして、仮に番兵/ダミー要素を使うのであれば、その番兵/ダミーも malloc() でとっておくべきです。 [813] で書いたとおり auto な番兵/ダミーを用意するのは大きな間違いです。 マルチプルインスタンスを実現しようとして list* root1=create_list(...); list* root2=create_list(...); 等と直したくなった場合に破綻します。 んで、この程度の話は [813] で紹介した先にて述べられ済みなのですけど。

>なるほど！！ >ありがとうございます >void free_list(list *start)の内容を見て、なっとくっす。 >チェーンをたぐりよせてmalloc()で取った領域を開放を繰り返し >NULLが来て、解放終わりって感じですね。 >すっごいわかりました。本当にありがとうございました。 void free_list(list *start) { list *curr, *temp; for (curr = start->next; curr != NULL;) { temp = curr->next; free(curr); curr = temp; } start->next = NULL; } あとで気がついたのですが、最後の行 start->next = NULL; という一行も入れておいた方が良いです。 これをしておかないと、freeした後に間違えて staのnextの参照や書き込みを行った場合問題となります。 参照をしたタイミングではオブジェクトはなくても ポインタの値は残っていて(ダングリングポインタと言います) 不正なアクセスとなります。 これは、問題の原因があるところと問題の発生位置 (別のところでアクセスバイオレーションになったりする) がずれる可能性があるため、気づきにくいバグとなります。 ここら辺の知識はポインタ関係ですので、(ぱ)さんの 「C言語ポインタ完全制覇」はかなりお勧めです。 私もこの本に早く出会っていればもっと早くレベルアップ できたのにと思っています。 http://www.amazon.co.jp/exec/obidos/ASIN/4774111422/qid=1141917620/br=3-1/br_lfncs_b_1/249-0186723-6715515

> >void free_list(list *start) { > list *curr, *temp; > > for (curr = start->next; curr != NULL;) { > temp = curr->next; > free(curr); > curr = temp; > } >} > >これで、以下のように呼び出せます。 >free_list(start); > >先ほどの例だと、以下のように呼び出さないといけません。 >free_list(start->next); >もしくは、 >free_list(sta.next); なるほど！！ ありがとうございます void free_list(list *start)の内容を見て、なっとくっす。 チェーンをたぐりよせてmalloc()で取った領域を開放を繰り返し NULLが来て、解放終わりって感じですね。 すっごいわかりました。本当にありがとうございました。

すいません。見落としてました。 free(start)はエラーになったということで、 startは、staをさしている訳で、エラーの原因はstaは 動的に確保されたオブジェクトではないからです。 774RRさんがおっしゃっていたようにstaは番兵ですね。 ですので、以下が正解です。 void free_list(list *start) { list *curr, *temp; for (curr = start->next; curr != NULL;) { temp = curr->next; free(curr); curr = temp; } } これで、以下のように呼び出せます。 free_list(start); 先ほどの例だと、以下のように呼び出さないといけません。 free_list(start->next); もしくは、 free_list(sta.next);

>自分自身、リストの有用性自体をはっきりわかってないと思っています。 >せいぜい「線形リストなら、文字を打ち込んで行ってもチェーンのつなぎ換えで >ソートできて便利だな～」という程度の知識です。 リンクリストは、要素(サンプルの場合、list)を削除する処理が 配列に比べて早いというのが一般的に言われています。 ですので、要素の追加や削除を頻繁に行う場合は有用かもしれないですが、 実のところ、データ構造は配列が一番便利ですし、ツリーやキューなど の方が良いケースもありますので、リンクリストが有用な場面は少ない かもしれないです。 私は、Cで動的に要素を追加するのにリンクリストを使ってたり しましたが、C++ならvectorで動的な追加ができるので C++ならlist(リンクリスト)を使う場面は少ないかもしれません。 あとCでハッシュの実装をする場合は、リンクリストはよく使います。 また、ソートに関しては基本的にリンクリストより配列の方が早いと思います。 と言うのも、例えばクイックソートを使うならランダムアクセスが必要になるので そもそもリンクリストでは(クイックソートは)無理です。 ソートする必要があるなら、配列を使うべきだと思います。 >>関数でfreeするなら、引数でstartを渡してあげればOKです >で、free(start)してみたら、エラーになってしまい、ただ >free(start->next)としたら通りました。 >まぁ、free(start)が通らないのは、僕の理解不足からくる見当違いな事をしてるせい >だと思いますが、free(start->next)としたとき、チェーンで繋がった先のNULLに至るまで >にmalloc()で割り当てたそれぞれのメモリ領域も解放してくれるのかが僕の理解不足の >点です。free(start->next)したとき、next側のメモリだけ解放され、後に続く >NULLまでのmalloc()で取った領域は動かされず、残ったままなら これは私の言葉足らずでしたが、例えば、以下のような関数を作成してやれば OKです(テストしてないですが多分OKだと思います)。 void free_list(list *start) { list *curr, *temp; for (curr = start; curr != NULL;) { temp = curr->next; free(curr); curr = temp; } } で、呼び出し側は、free_list(start)とやれば良いので、 startという変数(の管理)が大事だと言った訳です。 >まだ、ちゃんと理解できてないと自分自身思いますので、まだまだ精進精進だと思って >います。 アルゴリズムとデータ構造は奥が深いですが、このぐらいはまだまだ入門です。 C言語でのアルゴリズムの専門的な本を購入されて読むことをお勧めします。 C++では標準ライブラリで基本的なデータ構造は用意されているのですが、 データ構造の基本的な知識がないときちんとした理解ができないので プログラミングの知識と経験はこつこつと積み上げていくしかないと思っています。 仕事レベルですと、「基本」を押さえておくことが非常に重要になりますし。

レスありがとうございます 返信遅くてすいませんでした。 自分自身、リストの有用性自体をはっきりわかってないと思っています。 せいぜい「線形リストなら、文字を打ち込んで行ってもチェーンのつなぎ換えで ソートできて便利だな～」という程度の知識です。 ところで >負け組一号さんのサンプルで、startという変数が重要になります。 >どこかで(例えば関数で)free処理をするのでしょうが、 >start変数は、listの先頭を表していますので、これさえあれば >listにつながっているデータは全てfreeできます。 >関数でfreeするなら、引数でstartを渡してあげればOKです で、free(start)してみたら、エラーになってしまい、ただ free(start->next)としたら通りました。 まぁ、free(start)が通らないのは、僕の理解不足からくる見当違いな事をしてるせい だと思いますが、free(start->next)としたとき、チェーンで繋がった先のNULLに至るまで にmalloc()で割り当てたそれぞれのメモリ領域も解放してくれるのかが僕の理解不足の 点です。free(start->next)したとき、next側のメモリだけ解放され、後に続く NULLまでのmalloc()で取った領域は動かされず、残ったままなら マスタングさんの言う >現在のlistのnextの情報を先にとっておきます。 >そして、現在のlistをfree()します。 >その処理を現在のカーソルがNULLになるまで繰り返します。 >つまり、nextがNULLになるまで繰り返すのです。 という方法になるのか。と納得を得たしだいです。 まだ、ちゃんと理解できてないと自分自身思いますので、まだまだ精進精進だと思って います。

XSLTという言語では、if文にelse節はありません。 以下のようにあくまでif文しか書けないような言語仕様になっています。 <xsl:if test="...."> <!-- 何らかの処理 --> </xsl:if> 多分岐には、choose文（Cで言うところのswitch文）を使えという言語仕様になってますね。 <xsl:choose> <xsl:when test="...."> <!-- 何らかの処理 --> </xsl:when> <xsl:otherwise> <!-- 何らかの処理 --> </xsl:otherwise> </xsl:choose> これはこれですっきりしていて、キレイだと思います。 >>>then節とelse節で書けるものが違う、とか、if文だけ特別扱い、とか >> >>やっぱりこれを汚いと思う人が多いからではないでしょうか。 >> >>汚いかどうかは主観の問題ですけど、私なら、if文だけ特別扱いするくらいなら、 >>elsifを導入します。 > >なるほど。参考になります。 > > >>確かに、Cプログラマで、Cにはelse ifという特別な構文があると思っている人は >>少なくなかったですから、 > >私が初めて買ったCの入門書には「if文は入れ子を避けるために二分岐処理に限定してswitch文の使用を検討しろ」というようなことが書いてありました。 >「else節にif文を直接書く」という発想は知らなければ出てこないものなのかもしれませんね。 > > > >＃つか金返せやｺﾞﾙｧ

奈々氏 さん、(ぱ) さん、マスタング さん　へ ご返信ありがとうございます。 頂いた情報がかなり参考になりそうです。 とにかく感謝します、これから徹夜でサイトや資料を読みます。

>>then節とelse節で書けるものが違う、とか、if文だけ特別扱い、とか > >やっぱりこれを汚いと思う人が多いからではないでしょうか。 > >汚いかどうかは主観の問題ですけど、私なら、if文だけ特別扱いするくらいなら、 >elsifを導入します。 なるほど。参考になります。 >確かに、Cプログラマで、Cにはelse ifという特別な構文があると思っている人は >少なくなかったですから、 私が初めて買ったCの入門書には「if文は入れ子を避けるために二分岐処理に限定してswitch文の使用を検討しろ」というようなことが書いてありました。 「else節にif文を直接書く」という発想は知らなければ出てこないものなのかもしれませんね。 ＃つか金返せやｺﾞﾙｧ

『UNIXプログラミング環境』という本の第8章にhocという簡易プログラミング言語を yaccとlexを用いて徐々に機能を追加して開発する過程が解説されています。 本書の著者の一人はBrian W. Kernighan、あの『プログラミング言語Ｃ』の著者なので、 かなり信用のおける内容だと思います。 ただし、yaccとlexそのものについてはあまり詳しく解説していません。 あと、『コンパイラの理論と実現』という本には、C-というC言語からいくつかの 機能を取り除いた言語のコンパイラの作成方法が解説されていたと思います。 どちらもソースコード付きなので、オススメです。

訂正(?) >昔、「yacc/lex―プログラムジェネレータonUNIX」という本があって、この本には >・変数はA-Zだけ。配列なし。 >・バイトコードコンパイル方式。 >という簡易言語のサンプルが載っていました。 この本は、昔、啓学出版から出てたと思うんですが(小さめの版形で、半透明の カバーがかかってた奴)、今ぐぐるとテクノプレスから出ています。著者は同じだし、 内容も同じじゃないかと思うんですが。 ついでにこんなのも見つかりました。 http://www.watalab.cs.uec.ac.jp/tinyCabs.html

>flexとbissonで言語を作ってみようと思った人ですが。このページを読むと本当に勉強になりました。 どうもです。 >今、crowbarのソースを読んでますが、初心者なので、これよりもっとシンプルのソースあるでしょうか。 単にcrowbarより簡単なソースなら、うちのページにある(マスタングさんも挙げられた) 「電卓を作ってみよう」のcalcなんかがよいかもしれませんけれども。 ただし、作りたいものが「外面がCっぽい言語」なのか、「中の動きがCっぽい言語」で あるかによって、作り方は相当変わってきます。たとえばcrowbarは配列をヒープに 確保しますけど、内部的な動作を含めてCっぽい言語を作りたいのなら、配列もスタックに 確保すべきでしょう。内部的な動作を含めてCっぽい言語を作ったほうが、Cの理解が 深まる、という利点もあります。 >例え、データ型　intしかない、論理演算　if else　while for　＜＞＝　＋－*　/しかできるC言語サブセットのソース例はあるでしょうか。教えてください。よろしくお願いいたします。＾＾ 昔、「yacc/lex―プログラムジェネレータonUNIX」という本があって、この本には ・変数はA-Zだけ。配列なし。 ・バイトコードコンパイル方式。 という簡易言語のサンプルが載っていました。 また、「yaccによるCコンパイラプログラミング」 http://www.context.co.jp/~cond/books/yacc-book.html には、8086で動作する簡単なCコンパイラのソースが載っていました(構造体がない くらいで、ほぼCコンパチだったような気がします)。 でも、今はどちらも入手できないと思います。図書館とか会社の書庫とかで 探してみるのがよいのではないでしょうか。

>if文のぶら下がり文に関してふと思いついたんですが、 >本体にブロックを強制する場合でも >else節にだけ、if文も書けるようにすればelsif(elif, elseif)というようなキーワードを導入しなくても困りませんよね？ なるほど。確かに構文規則を以下のようにいじってbisonにかましてみましたが、 特にconflictは起きませんでした。 if_statement: IF LP expression RP block | IF LP expression RP block ELSE block | IF LP expression RP block ELSE if_statement | IF LP expression RP block elsif_list | IF LP expression RP block elsif_list ELSE block | IF LP expression RP block elsif_list ELSE if_statement >文法が微妙に汚くなるからでしょうか >then節とelse節で書けるものが違う、とか、if文だけ特別扱い、とか やっぱりこれを汚いと思う人が多いからではないでしょうか。 汚いかどうかは主観の問題ですけど、私なら、if文だけ特別扱いするくらいなら、 elsifを導入します。 確かに、Cプログラマで、Cにはelse ifという特別な構文があると思っている人は 少なくなかったですから、elseの後のif文だけ特別扱いしてもさほど混乱はないのかも しれませんけど、「Cにはelse ifという特別な構文があると思っている人」が 周囲にたくさんいた私としては、そういう人への啓蒙もこめてelsifを導入した、 という意図もあったようななかったような。

>flexとbissonで言語を作ってみようと思った人ですが。このページを読むと本当に勉強になりました。 >今、crowbarのソースを読んでますが、初心者なので、これよりもっとシンプルのソースあるでしょうか。 >例え、データ型　intしかない、論理演算　if else　while for　＜＞＝　＋－*　/しかできるC言語サブセットのソース例はあるでしょうか。教えてください。よろしくお願いいたします。＾＾ crowbar 0.1のソースや「プログラミング言語を作る」の"電卓を作ってみよう"は 参考にならないでしょうか？ また、初心者さんが求めている内容とは少し違いますが、 以下のものはどうでしょうか？ 1) yacc入門講座(簡単な説明) http://www.tokumaru.org/yacc/index.htm 2) Bison入門(リファレンス) http://guppy.eng.kagawa-u.ac.jp/~kagawa/2000/SysProg/bison-1.2.8/bison-ja_toc.html 3) Flex（リファレンス) http://www.asahi-net.or.jp/~wg5k-ickw/html/online/flex-2.5.4/flex_toc.html 4) lex&yaccプログラミング（残念ながら日本語版は売り切れなようです） http://www.amazon.co.jp/exec/obidos/ASIN/4756102972/qid=1141565795/br=3-2/br_lfncs_b_2/249-0186723-6715515 5) いまどきのプログラム言語の作り方(Javaで再帰下降型パーサの実装です) http://www.amazon.co.jp/exec/obidos/ASIN/4839919232/qid=1141567196/br=3-1/br_lfncs_b_1/249-0186723-6715515 私も興味ありますので、何か良いサイトや参考書などあれば 逆に教えてください。 あくまでもflexやbison(yaccやlex)にこだわるなら 私は、ドラゴンブックやタイガーブックなどより先に、 yaccやlexをある程度理解しておくことが重要だと思っています。