「わたし、気になります」 前日のtest_nodeの実行例から整列前のリストの状態を抜粋した。 ...snip $ ./test_node 711 938 807 302 893 ...snip $ ./test_node 732 ...snip $ ./test_node 738 669 ...snip $ ./test_node 744 958 630 ...snip $ ./test_node …

隣接交換法での要素の比較と交換の様子を表示してみる。 test_node.c ...snip #include <time.h> ...snip static int index(node_t *first_node, node_t *node) { int i = 0; node_t *p; for (p = first_node; p != NULL && p != node; p = p->next) i++; if (p == N</time.h>…

本題。 単連結リストを要素の持つ値の昇順に整列する処理を実装する。 せっかくの連結リストなので基本挿入法を使ってもいいが、 とりあえず基本中の基本の隣接交換法を用いてみる。 ここまで積み上げてきているので実装するのは簡単だ。 test_node.c ...sni…

変更箇所はほとんどないのに前回の変更でバグを作りこんでいた。 実験的コードだからといってシステマティックなテストはやらないと駄目ということか。関数node_printにNULLをfirst_nodeとして渡すとこける。 前回の変更前はpをfirst_nodeで初期化した直後、…

次に、関数node_swapが先頭要素とその次の要素とを交換できないという仕様を何とかしたい。 node_swapのこの制限の理由は既述のように交換したい二つの要素の一つ手前の要素が交換に必要だからである。 このことをもう少し詳細に考察してみる。交換したい二…

関数node_swapに与えた要素がリストの末尾近辺の場合のバグの修正は簡単である。 test_node.c ...snip static void node_swap(node_t *current) { node_t *p, *q; if (current == NULL || (p = current->next) == NULL || (q = p->next) == NULL) return; cu…

リストの要素を整列するためには要素の並びを変更できなければならない。 隣り合う要素の順序を入れ替えられれば、 その処理の組み合わせで任意の要素間の交換が可能となる。 そこで、ある要素とその次の要素の順序を入れ替える関数を書いてみる。 test_node…

単連結リストをin-placeっぽい感じの方法でソートする。 まず、単連結リスト自体を実装することから始めよう。 素朴だがむき出しの、そして効率の悪い実装で実験的コードを書いてみる。 test_node.c #include <stdio.h> #include <stdlib.h> typedef struct tag_node node_t; st</stdlib.h></stdio.h>…

前回のコードには、正当な入力にも関わらず、例えば不等号記号などが入っていると、 誤った形式のXMLを出力してしまうバグがあることに気が付いた。 入力に含まれている文字のうち事前定義された実体がある5種類の文字については、 それが出力すべき文字列に…

解析結果の出力をもう少し実用的（？）なものにしてみる。 とりあえずマークアップ言語界の雄XMLで出力してみよう。 translator.y ...snip %% xmltext : { fputs("<text>", stdout); } text { fputs("</text>", stdout); } text : string_headed | marked_string_headed ;…

parserに入力する文字のエンコードをUTF-8にすればシフトJISで起きるような問題は起きないと前述した。 だが、問題がないわけではない。いや、問題にならないかもしれない。 メタ文字変更シーケンスの3文字目はcharの範囲で表現できること前提だが、 例えばU…

前回示した例のうち、 $ echo -n "((@@出鼻)を挫く" | iconv -t Shift_JIS | ./parser | iconv -f Shift_JIS marked-string [出呆挫] string [ｭ]が、文字は化けているもののmarked-stringとstringの連接という構造を正しく抽出していることが気になった。 解…

元々charで表現できる文字だけで構成された文字列にマーク付けしたものを解析することを目的にしているわけで、 ASCIIだろうとEBCDICだろうとそれが前提の環境上でコンパイル、実行できると思うが、 charの範囲で表現できないような文字が使われている場合に…

mclex_test2.cはyylex関数の骨格をそのままにmclexに適応させたものなので、 parser.yのyylex関数をmclex_test2.cの形に書き直す。 二つ目の%%より前にあるソースの宣言部と構文規則部については元のparser.yから一切変更していない。 が、元のソースは今ま…

よく考えてみるとyylexからmclexを分離したからといって可搬性の問題は解消されてなかった。 例えば、 $ echo -n "a(b" | ./mclex_test2 NORMAL_STRING [a] START_MARK NORMAL_STRING [b]の場合、 (1) main(): mclex()を呼び出す。 (2) mclex(): getchar()か…

mclexを使うように今までのyylexを書き直すための原型を書いてみた。 といってもyylexの骨格はそのままで、 文字の取得をmclexによるトークンの取得に置き換えただけである。 mclex_test2.c #include <stdio.h> #include "mclex.h" #include "y.tab.h" int main(void)</stdio.h>…

mclexをgetcharのように使う分には簡単に書ける。 mclex_test.c #include <stdio.h> #include "mclex.h" #include "y.tab.h" int main(void) { int eof = 0; do { int c = mclex(); switch (c) { case EOF: eof = 1; break; case START_MARK: printf("START_MARK\n");</stdio.h>…

無計画に弄っている付けが回って来た。 コードが酷くごちゃごちゃしてきて読みにくいし、似たようなコードがあちこちに散らばっている。 メタ文字変更シーケンスを加えたのが変わり目か（その前から混沌とはしていたが）。 いろいろ整理が必要だ。 まず、関…

もう一つ問題点になりそうなものがあった。 コマンドラインオプションでは複数のメタ文字を同じ文字に設定することを禁じているが、 入力文字列中のメタ文字変更シーケンスではこれを禁じていない。 これが原因でうまく解析できなくなるのは入力データ側の責…

unget.cを利用するように書き換えてみた。 といっても、getchar()とungetc()の置き換えだけで済むはずであり、単に、 #include "unget.h" を追加し、 getchar()をgetchar_()に変更し、 ungetc(..., stdin)をungetchar_(...)に変更しただけで済んだ。 変更後…

示したコードに問題点があった。 ...snip while (1) { ...snip c = getchar(); if (c == current_start_mark_char) { do { int c2 = getchar(); if (c2 == current_start_mark_char) { ...snip } else { ungetc(c2, stdin); /* ++++++ (2) ++++++ */ break; …

とりあえず書いてみた。 前述したように、コマンドラインオプションでメタ文字を変更する版の記事の#5のparser.yの末尾に、 以下の字句解析関数yylexのコードを追加しているだけである。 ...snip static char *estrdup(const char *s); #ifndef YYTEXT_INIT_…

今更だが、GTK+-2.24.10においてgtk/gtk.hをインクルードしたソースを、 gccに-Wstrict-prototypesオプションを付けてコンパイルした場合、 ...snip In file included from /.../gtk.h:234:0, from foo.c:1: /.../gtk/gtkitemfactory.h:47:1: error: functio…

今日は寒かった。満開の桜でまさに花冷え。 そういえば一日遅いが4月6日は花冷えの特異日らしい。

コマンドラインオプションでメタ文字を指定する版のflex用ソースのみで記述した字句解析器を基に変更を加えようと考えていた。 ところがこれが案外面倒そうなのだ。 元のソースはマーク外またはマーク付け部分の文字列の一塊をパターンで一気に検出している…

考えてみると、解析する側がこの入力のメタ文字はこれ、というように指定するよりも、 入力する文字列自体が自分自身用のメタ文字を指定する方がずっと自然だろう。 適切なメタ文字を指定する責任は入力データを用意する側にあるべきである。 何をメタ文字と…

基本的に前回のコードで動作しているのだが、違和感のある部分を見つけた。 といっても、エラー表示の文言なので本質的な動作には関係ない。 $ echo -n "(b()" | ./parser error: illegal left parenthesisのようなエラーメッセージはデフォルトのメタ文字に…

変な策とはいえflexに字句解析器の生成を任せられるようになった。 つまり記述量や簡潔さ等については置いておくとしても、 このことはflexだけで解析器全体を書ける可能性があるということになる。注釈入りマーク付け文字列の解析の#13で作成した字句解析器…

方針にしたがって変更してみた。 まず、構文解析器。 parser.y %{ ...snip static char *estrdupcat(const char *s1, const char *s2); %} ...snip %% ...snip %% int current_start_mark_char = '('; int current_end_mark_char = ')'; int current_start_a…

やっぱり関数yylexを手書きするのは面倒だ、という考えはあっても当然だろう。 だが前に述べたように固定パターンスキャナを作成するlex/flexで生成するのは難しそうだ。 と思ったが、とりあえず効率は無視して、変な方法を思いついた。 以下はお試しプログ…