K.Maebashi's BBS

いろいろどたばたしておりまして、返信がずいぶん遅くなりましてすみません。 >私が初めて買った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をある程度理解しておくことが重要だと思っています。

flexとbissonで言語を作ってみようと思った人ですが。このページを読むと本当に勉強になりました。 今、crowbarのソースを読んでますが、初心者なので、これよりもっとシンプルのソースあるでしょうか。 例え、データ型　intしかない、論理演算　if else　while for　＜＞＝　＋－*　/しかできるC言語サブセットのソース例はあるでしょうか。教えてください。よろしくお願いいたします。＾＾

>＃ elseというキーワードはあるのにthen節であることを示すキーワードはない訳で 何を言ってるんだろ？ ええと、ブロックを中括弧で表現する言語でelsifのようなものを使う言語の中には、elseはあるのにthen節を示すキーワードは存在しない、というようなものもある訳で、 と言いたかったんですね。多分(ぉ

if文のぶら下がり文に関してふと思いついたんですが、 本体にブロックを強制する場合でも else節にだけ、if文も書けるようにすればelsif(elif, elseif)というようなキーワードを導入しなくても困りませんよね？ 何で世の中の多くの言語はそうなってないんでしょう？ 文法が微妙に汚くなるからでしょうか then節とelse節で書けるものが違う、とか、if文だけ特別扱い、とか でも、then節とelse節を全く同じにする必要はないと思いますし、 ＃ elseというキーワードはあるのにthen節であることを示すキーワードはない訳で ＃ というのはちょっと苦しいか if文の中でif文を特別扱いするのもそんなに変なこととは思いません ＃ うーん、気付いてないだけで何か他に問題があるんだろうか？ ＃ そこまでして else if と書けるようにするより、elsifを導入した方が簡単・・・でもないよなぁ。 どう思います？

タイガー改めマスタングです。 私なりに思ったことを書いてみます。 まず思ったのは、自分が少しでも複雑だなと感じる処理を考える場合は、 図を書いてみると理解しやすいです。 掲示板では少々書きづらいので自分なりに紙にでも書いてみてください。 >線形リストif(sagyou->num < fo->next->num)が、他の参考書を見ながら打ってた時 >next->next->...->numという感じで全部比較して見てるのか？となぜか思い >それで、逐一アドレス表示させるようにしたりして、自分なりに疑問を解消しつつ >本当に、fo->next->numは、nextだけを見てるのかとまだ疑問だったんですが >実は言いますと、この投稿フォームに、その疑問を考えながら書いてる間に >「あれ、これって、for文で回して、単に比較してチェーン変えてるだけだ」 >と、なぜか、その場で気づいたのですが、やはり確認しておこうと思い書きました。 listが数珠つなぎになっていて、forループの中でのfo変数は、 イメージとして、カーソルを表しています。 カーソルが先頭から末尾まで１つずつ各listを指しながら動く感じです。 これは、例えば、for (i = 0; i < num; i++)の、「i」と似ています。 iは、0から(num - 1)まで値を変えながら進んで行きます。 これは、「処理」としては、同じなので抽象化(同じ扱い)ができ、 一般的に、こういったカーソルをiteratorと言います (若干厳密性はないかもしれないですが、イメージはそんな感じだと思います)。 >free()に関しては、リストでmalloc()を使うのは解るが、それらをfree()にする >タイミングがよくわからなかったんですが、リストにして結果をはき出したら >またチェーンでたどってfree()にするのかなとか、まぁ、その、まだまだ >例題をみながら打ち込みながら理解しつつ、昨日覚えた事を今日忘れるような >日々つれづれとおくっておりまして、、、 負け組一号さんのサンプルで、startという変数が重要になります。 どこかで(例えば関数で)free処理をするのでしょうが、 start変数は、listの先頭を表していますので、これさえあれば listにつながっているデータは全てfreeできます。 関数でfreeするなら、引数でstartを渡してあげればOKです。 つまり、どこでfreeするかはユーザの自由ですが、freeするタイミングまで start変数を管理できていればOKな訳です。 start変数を管理(保持)する方法としては、ある関数内(ローカル)に持ち歩くか、 static変数(あるいは、グローバル変数)などで持っておくかの どちらかになると思います。 もちろん、別のデータ(構造)内に保持していても同じです。 freeするタイミングは重要ではないと思うのですが、 言えることがあるとすれば、いらなくなった時です。 >ただ、nextポインタがNULLになってるポインタを順次free()していけば出来るのかな >と思い、試してみます。 これは、違います。 nextポインタがNULLであろうが、NULLでなかろうが、 現在、カーソルが指しているlistをfree()します。 しかし、現在指しているlistをfree()してしまうと、 listに入っているnextの(ポインタの)情報がとれなくなってしまうので、 現在のlistのnextの情報を先にとっておきます。 そして、現在のlistをfree()します。 その処理を現在のカーソルがNULLになるまで繰り返します。 つまり、nextがNULLになるまで繰り返すのです。 まだ不明な点があればいくらでも聞いてください。

確かに、おっしゃるとおりっす。 自分の文章は、論理的に書けてないですね。 とにかく、もっとソースを体当たりで打ち込んで理解を深めます。 その上で、ポインタ関連で疑問が生じたら書き込みささしてもらいます。

あまり本質的な議論には参加してないくせに言うのもおかしいかもしれませんが少しだけ。 負け組一号さんは、一つの文章を短く切った方が文章の意味がわかりやすくなると思います。 「それが私の文章の味」とか言われちゃうと、それまでなのですが、 技術的な文章は、わかりやすさ重視でしょう。 なんとなく古文の授業を思い出してしまいます。 さて(ぱ)さんへのコメント中に 「どうfree()して行けば良いのかが解らない」とおっしゃってますが、 「どこでfree()というやつで解放してやれば良いのでしょうか」という質問では 求める答えが得られないのはお解かりでしょうか。 「方法」がわからないときに「記述する位置」を質問しても求める答えは得られないのは自明でしょう。 わからないことが「考え方や根拠」「概念」「方法」「動作原理」の どれなのかを分類するといいと思います。 少々きつい言葉で批判めいたことを書きましたが 自分自身の経験から「わからないことが何か」を理解した段階で 自然に「理解できる」場合が多いように思えます。 その一助として 「自分がわからない事柄は『方法』なのか?『考え方』なのか?『動作原理』なのか?」 と自問することは重要だと思っています。

774RRさん、(ぱ)さん、返信ありがとうございます。 線形リストif(sagyou->num < fo->next->num)が、他の参考書を見ながら打ってた時 next->next->...->numという感じで全部比較して見てるのか？となぜか思い それで、逐一アドレス表示させるようにしたりして、自分なりに疑問を解消しつつ 本当に、fo->next->numは、nextだけを見てるのかとまだ疑問だったんですが 実は言いますと、この投稿フォームに、その疑問を考えながら書いてる間に 「あれ、これって、for文で回して、単に比較してチェーン変えてるだけだ」 と、なぜか、その場で気づいたのですが、やはり確認しておこうと思い書きました。 free()に関しては、リストでmalloc()を使うのは解るが、それらをfree()にする タイミングがよくわからなかったんですが、リストにして結果をはき出したら またチェーンでたどってfree()にするのかなとか、まぁ、その、まだまだ 例題をみながら打ち込みながら理解しつつ、昨日覚えた事を今日忘れるような 日々つれづれとおくっておりまして、、、 とりあえず、まだまだ、打ち込んで、理解を深め、この劣化した脳に新たなメモリを 加えたく（脳の細胞は再生しないが、新生はするらしいので）思いつつ、今度は ちゃんと何が解らないのかが解らない状態で質問せず、何が解らないか解るよう 質問（甘え）さしてもらいたいです。 上記の文を書いて、ポインタ完全制覇を読み直した結果、駄目じゃん俺と再認識 >>774Rさん >提示コードは先頭に追加される必要がある場合にうまくない。 >それとも最初に作ってる sta は番兵？ 番兵の意味を聞かれて、持ってる書籍を見て初めて意味を知りました。番兵って奴です。 >一番最初の１個目を作る場合と、末尾に追加する場合とが特殊なわけだ。 >でも、実際には特殊ではなくて、ロジック上真ん中に挿入の場合と同じに扱える >ということが理解できるかどうかが肝 まだまだ、理解は出来るが、「さぁ作れ」と言われたら悩んでしまうレベルです。 >>(ぱ)さん >「どうわからないのか」をもう少し具体的に書いていただけませんか。 わからない部分は線形リストでmalloc()で割り当てて行った領域をどうfree()して行け ば良いのかが解らないといった感じです。 ただ、nextポインタがNULLになってるポインタを順次free()していけば出来るのかな と思い、試してみます。

どうも、(いつものことですが)「何がわからないのか」がわからないので 答えようにも困ってしまうわけですが。 >　　　　if(sagyou->num < fo->next->num ) >の、fo->next->numは、その時点でのfoのnext側のnumを見てる >と捉えて良いのでしょうか。 この質問にYesかNoかで答えれば、(774RRさんが書いておられるように)「Yes」と 答えるしかないわけですが、疑問に思ったからには、何か引っかかるところが あるわけでしょう。 ->は所詮演算子なので、 p = fo->next->num; として「foのnext側のnumを見」る代わりに、 temp = fo->next; p = temp->num; と書いてもよいし、 fo->next->numの代わりに(fo->next)->numと書いても構わないわけですが、 こうやって書き換えると感覚的にわかりやすくなったりしますかね。 >ついで、malloc()で得たメモリは >どこでfree()というやつで解放してやれば良いのでしょうか。 これも、「要らなくなったとき」としか答えようがないのですが、 そんなことは入門書にも書いてあるはずで、それでわからなかったから 質問しているわけでしょう。 「どうわからないのか」をもう少し具体的に書いていただけませんか。

リスト構造自体はそんなに難しいものではなくて、単に数珠つなぎになってるだけ。 例えば http://www9.plala.or.jp/sgwr-t/c/sec15-5.html 演習のほうも見てみませう。 提示コードは先頭に追加される必要がある場合にうまくない。 それとも最初に作ってる sta は番兵？ 番兵にせよなんにせよ今のままでは sta が auto なのでまずいけど。 >fo->next->numは、その時点でのfoのnext側のnumを見てる もちろん >どこでfree()というやつで解放してやれば良いのでしょうか。 要らなくなったとき。 malloc() するってことは、当座しばらくは必要だから保持しとけ、ということ。 例えばワード等で文章を開いたときなんかにこうやって文書データを保持してるわけだ。 free() するのは文章を閉じたときとかワードを終了するときとか。 提示コードであればリストを破棄するのは main 終了直前でしょうな。 こういうのはポインタに関する「文法理解」ではなくてむしろ「アルゴリズム理解」の話。 線形リストの場合「真ん中に挿入」する場合がいちばん簡単で、紹介先の図のとおり。 一番最初の１個目を作る場合と、末尾に追加する場合とが特殊なわけだ。 でも、実際には特殊ではなくて、ロジック上真ん中に挿入の場合と同じに扱える ということが理解できるかどうかが肝。