2011-07-01から1ヶ月間の記事一覧
古流記法なFORTRANプログラム。 x-y直交座標系において原点を中心とする単位円と曲線のにおける交点を求める。 曲線のy座標は負の値をとらないので、単位円（の半分）はと書ける。 求めるべきはとなるxである。 普通にニュートン・ラフソン法を使う。 微分係…
ちなみにint_tのサンプルコードと同様に、 #include <gmp.h> int main(void) { mpz_t x, y; mpz_init_set_str(x, "123", 10); *y = *x; gmp_printf("%Zd %Zd\n", x, y); mpz_clear(x); return 0; } のようなコードが書けるが、 yはxのシャロウコピーなので、 mpz_in</gmp.h>…
YYSTYPEをdefineするのではなく%union宣言をわざわざ使っているのは、 defineでは字句定義のヘッダファイルにYYSTYPEの定義が挿入されないことにもある。 「にもある」と書いたように理由は他にもある。 #include <stdio.h> typedef int int_t[1]; int main(void) { i</stdio.h>…
0除算の処理を忘れていた。さらに修正パッチ。 --- calc.y # +++ # # @@ -26,7 +26,7 @@ | expr '+' expr { mpz_init($$); mpz_add($$, $1, $3); mpz_clears($1, $3, NULL); } | expr '-' expr { mpz_init($$); mpz_sub($$, $1, $3); mpz_clears($1, $3, NUL…
ということで、引き算や割り算や括弧が使える版のcalc.y用の修正パッチ。 --- calc.y # +++ # # @@ -12,8 +12,8 @@ %left '+' '-' %left '*' '/' %left NEG -%type <val> expr -%destructor { mpz_clear($$); } <val> +%type <val> expr uint +%destructor { mpz_clear($$);</val></val></val>…
yylvalむき出しの解決法がスマートでないという考え方もあると思う。 構文解析の生成規則上で回避するなら、 デバグプリント版であれば、 ...snip %type <val> expr uint %destructor { CHECK_MPZ("error_recovery_clear", $$); mpz_clear($$); } expr %% ...snip</val>…
これを回避する素朴な方法は%destructor宣言で後始末をしようとする対象がyylvalであればそれを行わないこと。 デバグプリント版であれば、 ...snip %destructor { if (! isyylval($$)) { CHECK_MPZ("error_recovery_clear", $$); mpz_clear($$); } } <val> %% ..</val>…
%destructor宣言でエラー時に残る解析用スタック内のシンボルの後始末ができるようになった。 しかし、 $ ./calc [lexer] init(003E24D0) 1 2 [lexer] set(003E24D0) [parser] init(003E2540) [parser] set(003E2540) [lexer] set(003E24D0) syntax error [p…
引き算や割り算や括弧も使えるように。 割り算は0方向への丸め。0除算でこける。 calc.y %{ #include <stdio.h> #include <gmp.h> int yylex(void); void yyerror(char *s); %} %union { mpz_t val; } %token <val> UINT %left '+' '-' %left '*' '/' %left NEG %type <val> expr %dest</val></val></gmp.h></stdio.h>…
$ ./calc [lexer] init(003E24D0) 100000000000000000000 [lexer] set(003E2540) [parser] init(003E24D0) [parser] set(003E2558) 100000000000000000000 [parser] clear(003E2558) [lexer] clear(003E2540) $ のようにinitとclearのアドレスの対が無くなっ…
エラー回復時に機械的にシンボルが捨てられることによってメモリリークが発生していた。 Bison宣言には%destructor宣言がありエラー回復時のこの動作が行われる時に、 シンボルを1個破棄するごとに自動実行されるコードを指定できる。 --- calc.y # +++ # # …
実際、デバグプリント付きで見てみると、 calc.l %{ #include <gmp.h> #include "calc.tab.h" #define YY_USER_INIT init_yylval() void init_yylval(void); int yylex(void); #define CHECK_MPZ(s,p) gmp_printf("[lexer] "s"(%p)\n",(p)->_mp_d); void init_yylva</gmp.h>…
少し考えたら文法に則った入力が与えられている限りは大丈夫そう。 mpz_initされたyyvalは意味値スタックのトップyyvspにコピーされて、 その後の還元でmpz_clearされるので基本的に問題ない。 最終的に、 stmt: stmt expr '\n' { gmp_printf("%Zd\n", $2); …
実際のところ原始的にやる気がなければいくらでも便利な道具はある。 激減するわけではないがそれなりに少ない作業量で済ませるなら、 解析器は定番のyacc/lex（実際に使用したのはbison/flex）で作成すればいい。 また、多倍長精度演算はGMPに任せた。 まず…
さらにいくつかの操作を追加するパッチ。 --- # # +++ # # @@ -12,18 +12,22 @@ }; typedef enum { - CMD_INVALID, CMD_TOOLONG, CMD_PUSH, CMD_POP, CMD_PRINT, CMD_QUIT + CMD_INVALID, CMD_TOOLONG, CMD_PUSH, CMD_POP, CMD_PRINT, CMD_DELETE, CMD_APPEN…
'\0'を含めて最大32バイトの文字列をデータに持つ線形リストに修正するパッチ。 --- # # +++ # # @@ -2,10 +2,12 @@ #include <stdlib.h> #include <string.h> +#define NAME_SIZE 32 + typedef struct tagNode Node; struct tagNode { - int data; + char data[NAME_SIZE]; Node</string.h></stdlib.h>…
intをデータに持つ単方向連結の線形リストで実装するスタック。 先頭要素の追加と削除でpush/pop操作を実現する。 文字列から整数への変換にはatoiよりエラーを認識できるstrtolを用いた方がいいだろうと思う。 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struc</string.h></stdlib.h></stdio.h>…
非負整数の足し算と掛け算の入った数式を評価する。 この文法の性質上、字句スタックは最大4個、被演算子スタックは最大3個の要素を入れられればいいはず。 混同することはないので字句スタックの最初の要素である先頭記号は末尾記号で代替する。 見返さずに…
演算子順位構文解析は解析器用の字句スタックのトップ要素と入力の最新字句との間の順位関係を見て、 入力字句を字句スタックへ移動するか、字句スタックのトップ要素を還元して消化するかの処理を行う。 最終的に字句スタックに先頭記号のみ、入力の最新字…
入力の解析には演算子順位構文解析を使うことにする。 正当な字句の種類は、非負整数、'+'、'*'、'\n'であり、 さらにこれ以上入力が無いことを示す末尾記号と、 全ての字句に先立って入力に現れる先頭記号が加わる。 これらの字句の間の順位関係を文法に則…
数式の構成要素として加法演算子'+'と乗法演算子'*'を考える。 正当な入力とは、0個以上の数式文の連接である。 数式文とは、数式に改行'\n'を連接したものである。 数式とは、非負整数であるか、数式に'+'と数式を順に連接したものか、数式に'*'と数式を順…
Mpiに関わるデータの定義が桁数ndigitと各桁の値を格納する配列digitしかないことから分かるように、 Mpiの内容を初期化によって定められたものから変更する意図はない。 桁数が変わらないことが確定している操作ならば変更は簡単だが。 typedef struct { si…
乗算を行う関数も。 特に工夫もなく素朴に実装。 ...snip void mpi_mul(Mpi *a, Mpi *b, Mpi*c); ...snip void mpi_mul(Mpi *a, Mpi *b, Mpi*c) { size_t i, j, n; unsigned int carry; n = a->ndigit + b->ndigit; c->digit = malloc(n); for (i = 0; i < n…
加算を行う関数を実装する。 これは第一引数に対して加算操作を行って結果をそれに反映するのでなく、 第一引数と第二引数を加算して第三引数をその結果で初期化する。 第三引数は初期化前または後始末後でないとメモリリークする。 ...snip void mpi_add(Mp…
任意長非負整数から10進数表記の文字列表現を得る関数も。 基本的な骨格は10->256変換も256->10変換も変わりない。 ...snip char *mpi_make_decimal_expr(Mpi *mpi); ...snip char *mpi_make_decimal_expr(Mpi *mpi) { char *expr = malloc((size_t)(2.40823…
任意長非負整数に関する実装をする。 まず、数字列による10進数表記で任意長非負整数を初期化する関数と後始末する関数から。 #include <stdlib.h> #include <string.h> typedef struct { size_t ndigit; unsigned char *digit; } Mpi; void mpi_init_with_decimal_expr(Mpi *mpi</string.h></stdlib.h>…
10進数表記の非負整数をプログラム内部では256進数として扱うことにする。 10進数 n 桁は256進数 [n/log(256)]+1 桁以下で表せる。 ここで[ ]は床関数、log()は常用対数。 1/log(256)=0.41524101186...なので、 256進数の桁情報を保持する領域は多めに見積も…
字句とは、1個以上の数字列（非負整数）か、数字と' 'と'\t'以外の1個の文字か、入力の終端か、である。 入力の終端は文字そのものではなく、これ以上入力がないことを示すためのシンボルである。 この字句の定義に合わせてTokenの定義を変更する。 #define …
思わずこう書きそうに。 ...snip int main(int argc, char *argv[]) { Lexer lexer; Token *token; size_t i; if (argc > 1) { Reader reader; strreader_init(&reader, argv[1]); lexer_init_with_reader(&lexer, &reader); } else { ...snip if節を抜けた…
Readerを使って字句の切り出し関数を変更してみる。 切り出し関数そのものよりそれ以外の部分の変更の方が多いような。 ...definitions and implementations of Reader ...snip typedef struct { size_t length; char *value; } Token; #define LEXER_BUFFER…
