Paser
*****

Parser の構成
==========

Configuration of the parser
===========================

parser は Asir 言語で書かれた文字列を中間言語に変換する. paser は次のものから構成される.

  * 文法定義

     Asir 言語の文法は yacc のソースファイルとして定義されている. このファイルは yacc により parser プログラムに変換される.

  * 字句解析

     yacc で生成される parser プログラムは, 入力文字列の先頭から順に, 属性毎に文字列を切り分ける関数 yylex() を呼び出しながら, 文法定義に従って中間言語 tree を構成していく. 字句解析定義ファイルから yylex() を生成するプログラム lex もあるが, Asir では歴史的な理由から C 言語により直接記述している.

  * 名前管理

     yylex() によって切り分けられる文字列として, あらかじめ定義された keyword (if, for など) の他に, 変数名, 関数名など動的に生成される名前がある. これらは属性毎にリスト, 配列などの形で管理され, parser の実行中に参照, 追加などが行われる.

中間言語
====

Intermediate language
=====================

     typedef struct oFNODE {   式を表すノード
         fid id;               識別子
         pointer arg[1];       引数配列 (長さ可変)
     } oFNODE *FNODE;

     typedef struct oSNODE {   文を表すノード
         sid id;               識別子
         int ln;               行番号
         pointer arg[1];       引数配列 (長さ可変)
     } oSNODE *SNODE;

     typedef struct oFNODE {
         fid id;
         pointer arg[1];
     } oFNODE *FNODE;

     typedef struct oSNODE {
         sid id;
         int ln;
         pointer arg[1];
     } oSNODE *SNODE;

interpreter の入力となる中間言語の構成は極めて単純である. 中間言語の構成要素は 文 および 式 である. Asir 言語による入力文字列は, 文の並びとして parse され, SNODE 構造体のリストに変換される. 文の種類は識別子 id により示される. 引数配列は文の種類に応じて長さ, およびその各要素の意味(役割)が決まる. 以下で S_ で始まるのは識別子の名前で, 実際には相異なる整数が割り当てられている. | は, 識別子および引数の仕切りを示す.

S_SINGLE | expr

     exprを実行する.

S_BREAK

     最も内側のループ (S_FOR, S_DO) を抜ける.

S_CONTINUE

     最も内側のループの先頭に飛ぶ.

S_RETURN | expr

     関数から抜けて, expr の値を返す.

S_IFELSE | dummy | expr | stat1 | stat2

     \JPexpr の値が 0 でないなら stat 1 を実行, 0 なら stat 2 を実行.

S_FOR | dummy | expr1 | expr | stat | expr2

     まず expr1 を実行したあと, expr の値が 0 でない間, stat と expr2 の計算を繰り返す.

S_DO | dummy | stat | expr

     stat を実行したあと expr を計算し, その値が 0 でない間繰り返す.

SNODE は行番号を示すメンバ ln を持つ. 各行がファイルから読まれた場合に, そのファイルにおける行番号を格納しておく. これはデバッグ時に行番号から文を特定するためなどに用いられる.

文に対する中間言語定義で分かるように, 文は最終的には式から構成されている. 文中に現れた式は, parser によって解析され, FNODE 構造体のリストに変換される. 式の種類は識別子 idにより示される. 引数配列は式の種類に応じて長さ, およびその各要素の意味(役割)が決まる. 以下で I_ で始まるのは識別子の名前で, 実際には相異なる整数が割り当てられている. | は, 識別子および引数の仕切りを示す.

I_STR | string

     文字列

I_FORMULA | object

     既に Risa object に変換されている \codeobject

I_ANS | index

     index 番目の計算結果

I_GF2NGEN

     標数 2 有限体の生成元

I_EV | node

     node を指数ベクトルとみて, 係数 1 の単項式を生成する.

I_FUNC | function | argument list

     関数呼び出し

I_CAR | list

     list の先頭要素

I_CDR | list

     list から先頭要素を除いたリスト

I_PVAR | index

     index 番目のプログラム変数の値

I_ASSPVAR | expr1 | expr2

     expr1 で示されるプログラム変数に expr2 を代入

I_INDEX | expr | index

     expr を配列またはリストと見て, indexで指定される要素を取り出す.

I_POSTSELF | function | expr

     expr の値を取り出したあと, function が加算なら expr を 1 増やし, function が減算なら expr を 1 減らす.

I_PRESELF | function | expr

     function が加算なら expr を 1 増やし, function が減算なら式 を 1 減らす. その後 expr の値を取り出す.

I_LIST | node

     nodeからリストを生成する.

I_NOP | expr

     expr が 0 でないなら 0, 0 なら 1.

I_OR | expr1 | expr2

     expr1, expr2 がともに 0 なら 0, それ以外は 1.

I_AND | expr1 | expr2

     expr1, expr2 がともに 0 でないなら 1, それ以外は 0.

I_CE | expr | expr1 | expr2

     expr が 0 でないとき expr1 の値, 0 のとき expr2 の値.

I_BOP | bop_id | expr1 | expr2

     bop_id で指定される二項演算子 (加減乗除など) に従って, expr1, expr2 を引数として演算.

I_COP | cop_id | expr1 | expr2

     cop_id で指定される比較演算子に従って, expr1, expr2 を比較. 結果は 0, 1, -1.

I_LOP | lop_id | expr1 | expr2

     lop_id で指定される論理演算子により, expr1, expr2 を引数として論理式を生成.

字句解析
====

Lexical analysis
================

字句解析部では, 空白, タブ, 改行をスキップしたあとの最初の文字によって最初の分類を行う.

  * 0

     続く 0 をスキップして, 数字が来たら 10 進数, b が来たら 2 進数, x が来たら 16 進数として, あとに続く valid な文字をバッファに読み込み, 2^32 進数に変換する.

  * 0 以外の数字

     以下に続く数字をバッファに読み込み, 10 進数として 2^32 進数に変換する.

  * 英小文字

     以下に続く, アルファベット, 数字, _ をバッファに読み込み, keyword の場合にはその識別子, そうでない場合には 小文字で始まる文字列 を意味する識別子を返す.

  * 英大文字

     以下に続く, アルファベット, 数字, _ をバッファに読み込み, 大文字で始まる文字列 を意味する識別子を返す.

  * @

     @ はその後に来る文字列によりさまざまな対象を表す.

       - @@

          直前の計算結果

       - @pi

          円周率を表す不定元

       - @e

          自然対数の底を表す不定元

       - @i

          虚数単位

       - @p

          奇標数有限体の拡大体の生成元

       - @true, @false, @impl, @repl, @equiv

          論理演算子

     これ以外の場合 @ は標数 2 の有限体の生成元を表す.

  * "

     次の " の直前の文字までを文字列 Risa object とみなす.

  * '

     次の ' の直前の文字までを 小文字で始まる文字列 とみなす. これは, 任意文字列を名前とする不定元を生成する必要がある場合などに用いる.

  * その他の記号

     記号に応じてさまざまに扱われる. 多くは演算子として扱われるが, {, }, [, ], (, ) など, 一対で間にある対象に作用するものもある.

  * 0

     続く 0 をスキップして, 数字が来たら 10 進数, b が来たら 2 進数, x が来たら 16 進数として, あとに続く valid な文字をバッファに読み込み, 2^32 進数に変換する.

  * 0 以外の数字

     以下に続く数字をバッファに読み込み, 10 進数として 2^32 進数に変換する.

  * 英小文字

     以下に続く, アルファベット, 数字, _ をバッファに読み込み, keyword の場合にはその識別子, そうでない場合には 小文字で始まる文字列 を意味する識別子を返す.

  * 英大文字

     以下に続く, アルファベット, 数字, _ をバッファに読み込み, 大文字で始まる文字列 を意味する識別子を返す.

  * @

     @ はその後に来る文字列によりさまざまな対象を表す.

       - @@

          直前の計算結果

       - @pi

          円周率を表す不定元

       - @e

          自然対数の底を表す不定元

       - @i

          虚数単位

       - @p

          奇標数有限体の拡大体の生成元

       - @true, @false, @impl, @repl, @equiv

          論理演算子

     これ以外の場合 @ は標数 2 の有限体の生成元を表す.

  * "

     次の " の直前の文字までを文字列 Risa object とみなす.

  * '

     次の ' の直前の文字までを 小文字で始まる文字列 とみなす. これは, 任意文字列を名前とする不定元を生成する必要がある場合などに用いる.

  * その他の記号

     記号に応じてさまざまに扱われる. 多くは演算子として扱われるが, {, }, [, ], (, ) など, 一対で間にある対象に作用するものもある.

名前管理
====

Names
=====

Asir においては, 不定元, 関数, プログラム変数という 3 つのカテゴリ別に名前が管理されている.

不定元
---

Indeterminates
--------------

不定元は変数リスト CO (Current variable Order) で管理される. 不定元と認識される文字列が字句解析部から与えられた場合, CO に登録されている不定元の名前とその文字列を順に比較し, 一致した場合にはその不定元構造体ポインタを対応する変数として用いる. 一致する名前がない場合には新たに不定元構造体を生成し, 与えられた文字列を名前として登録し, CO の末尾に追加する.

関数
--

Functions
---------

     typedef struct oFUNC {    Asir 関数
       char *name;             関数名
       int argc;               引数の個数
       int type;               PARI 関数型
       aid id;                 型 (未定義, 組み込み, ユーザ, 純, PARI)
       union {
         void (*binf)();       組み込み関数
         struct oUSRF *usrf;   ユーザ定義関数構造体
         struct oPF *puref;    純関数
       } f;
     } *FUNC;

     typedef struct oUSRF {    ユーザ定義関数
       char *fname;            関数名
       short vol;              未使用
       int startl,endl;        ファイル内での開始, 終了位置
       NODE args;              仮引数リスト
       VS pvs;                 局所プログラム変数配列
       char *desc;             関数の説明
       struct oSNODE *body;    文リスト(関数本体)
     } *USRF;

     typedef struct oPF {      純関数
       char *name;             関数名
       int argc;               引数の個数
       Obj body;               ユーザ定義純関数の本体
       V *args;                引数配列
       Obj *deriv;             偏導関数配列
       NODE ins;               関数インスタンスリスト
       int (*pari)();          PARI 呼び出し関数
       double (*libm)();       C 数学関数
       int (*simplify)();      simplifier
     } *PF;

     struct oV {               不定元(再掲)
         char *name;
         pointer attr;         属性
         pointer priv;
     };

     extern NODE sysf,noargsysf;  組み込み関数リスト
     extern NODE usrf;            ユーザ定義関数リスト
     extern NODE parif;           PARI 関数リスト
     extern NODE pflist;          純関数リスト

     typedef struct oFUNC {    Asir 関数
       char *name;             関数名
       int argc;               引数の個数
       int type;               PARI 関数型
       aid id;                 型 (未定義, 組み込み, ユーザ, 純, PARI)
       union {
         void (*binf)();       組み込み関数
         struct oUSRF *usrf;   ユーザ定義関数構造体
         struct oPF *puref;    純関数
       } f;
     } *FUNC;

     typedef struct oUSRF {    ユーザ定義関数
       char *fname;            関数名
       short vol;              未使用
       int startl,endl;        ファイル内での開始, 終了位置
       NODE args;              仮引数リスト
       VS pvs;                 局所プログラム変数配列
       char *desc;             関数の説明
       struct oSNODE *body;    文リスト(関数本体)
     } *USRF;

     typedef struct oPF {      純関数
       char *name;             関数名
       int argc;               引数の個数
       Obj body;               ユーザ定義純関数の本体
       V *args;                引数配列
       Obj *deriv;             偏導関数配列
       NODE ins;               関数インスタンスリスト
       int (*pari)();          PARI 呼び出し関数
       double (*libm)();       C 数学関数
       int (*simplify)();      simplifier
     } *PF;

     struct oV {               不定元(再掲)
         char *name;
         pointer attr;         属性
         pointer priv;
     };

     extern NODE sysf,noargsysf;  組み込み関数リスト
     extern NODE usrf;            ユーザ定義関数リスト
     extern NODE parif;           PARI 関数リスト
     extern NODE pflist;          純関数リスト

関数には, 組み込み関数, ユーザ定義関数, PARI 関数および純関数がある. いずれも 関数構造体 FUNC として登録されリストとして保持される. 組み込み関数のうち, 引数を持つものは, sysf に, 持たないものは noargsysf に登録される.

ユーザ定義関数は, 呼び出し時あるいは関数定義時に, usrf を検索し, リスト中にその名の関数がない場合に FUNC 構造体が生成され, リストに追加される. 関数定義が行われる前に呼び出しが行われた場合, FUNC 構造体のメンバ id には, 未定義を意味する識別子がセットされる. 後に実際に関数定義が行われた際に, このメンバはユーザ定義関数を意味する識別子で上書きされ, その他のメンバも然るべくセットされる. 既に定義されている場合には, これらのメンバは上書きされる. 即ち, 同一関数名では最新の定義が用いられる.

PARI 関数は, 実際の計算に PARI ライブラリを用いるという点を除けば, 組み込み関数と同等である. ただし, PARI ライブラリは PARI bigfloat を結果として返すので, double float の結果を得たい場合のために, C の libm ライブラリの同等の関数ポインタを保持している.

組み込み, ユーザ定義, PARI 関数は, 引数を用いて計算を行い, Risa object を結果として返す, 通常のプログラミング言語の意味での関数だが, 純関数は, 引数のみが評価されて, その引数を持つ関数呼び出しそのものを返す. Asir の実行例を示す.

     [0] A=sin(x);
     sin(x);
     [1] type(A);

     2                     <--- 純関数は多項式

     2                     <---

     [2] vtype(A);

     2                     <--- 属性は純関数

     2                     <---

     [3] args(A);

     [x]                   <--- 引数リスト

     [x]                   <---

     [4] B=functor(A);

     sin                   <--- 関数子

     sin                   <---

     [5] type(B);

     2                     <--- 関数子も多項式

     2                     <---

     [4] vtype(B);

     3                     <--- 属性は関数子

     3                     <---

この例では, sin(x) なる純関数が生成されているが, Risa object としては, sin(x) 自身が不定元, 即ち多項式となる. しかし V 構造体としての属性 (メンバ attr) の値が異なる. この値が純関数を意味するとき, メンバ priv にはこの純関数に関するさまざまな情報が格納され, args, functor により取得される. 関数子自身も, Risa object としては不定元として存在する. この場合も属性により関数子であることが示される.

プログラム変数
-------

Program variables
-----------------

     typedef struct oVS {   プログラム変数配列
       unsigned int n;      現在含まれる変数の個数
       unsigned int asize;  割り当てられた配列の長さ
       unsigned int at;
       unsigned int level;
       struct oFUNC *usrf;
       struct oPV *va;      配列本体
       NODE opt;            未使用
     } *VS;

     typedef struct oPV {   プログラム変数
       char *name;          変数名
       sort attr,type;
       pointer priv;
     } *PV;

     extern VS GPVS;  大域変数配列
     extern VS CPVS;  現在の変数配列
     extern VS EPVS;  extern 宣言された変数配列
     extern VS APVS;  計算結果を格納する配列

     typedef struct oVS {
       unsigned int n;
       unsigned int asize;
       unsigned int at;
       unsigned int level;
       struct oFUNC *usrf;
       struct oPV *va;
       NODE opt;
     } *VS;

     typedef struct oPV {
       char *name;
       sort attr,type;
       pointer priv;
     } *PV;

     extern VS GPVS;
     extern VS CPVS;
     extern VS EPVS;
     extern VS APVS;

Asir においては, プログラム変数のスコープは, 大域変数と, プログラム内での局所変数の 2 レベルに単純化されている. 変数は, 現れた時点でいずれかのプログラム変数として登録される. 関数の外で現れたプログラム変数は, 大域変数配列に登録される. 関数定義内で現れたプログラム変数は, 関数定義固有の局所変数配列に登録され, USRF 構造体のメンバ pvsとして登録される. 関数が実行される場合に, 登録された局所変数配列をテンプレートとして, スタックに相当する変数配列が生成され, 実行時の変数の値はこの配列に格納される.

中間言語において, プログラム変数参照はインデックスにより行われる.  関数内での変数参照は, 通常は局所変数配列内の変数に対するインデックスが用いられるが, extern 宣言されている変数に関しては, 同名の大域変数配列の変数に対するインデックスが用いられる. この場合, 実際にはこの区別はインデックスの最上位ビットを 1 にすることで行っている.