@comment $OpenXM: OpenXM/src/asir-doc/int-parts/parser.texi,v 1.3 2005/04/07 10:59:50 noro Exp $ @chapter Parser \JP @section Parser の構成 \EG @section Configuration of the parser \BJP parser は Asir 言語で書かれた文字列を中間言語に変換する. parser は 次のものから構成される. \E \BEG \E \BJP @itemize @item 文法定義 Asir 言語の文法は @code{yacc} のソースファイルとして定義されている. この ファイルは @code{yacc} により parser プログラムに変換される. @item 字句解析 yacc で生成される parser プログラムは, 入力文字列の先頭から順に, 属性毎 に文字列を切り分ける関数 @code{yylex()} を呼び出しながら, 文法定義に従っ て中間言語 tree を構成していく. 字句解析定義ファイルから @code{yylex()} を生成するプログラム @code{lex} もあるが, Asir では歴史的な理由から C 言語により直接記述している. @item 名前管理 @code{yylex()} によって切り分けられる文字列として, あらかじめ定義された keyword (@samp{if}, @samp{for} など) の他に, 変数名, 関数名など動的に 生成される名前がある. これらは属性毎にリスト, 配列などの形で管理され, parser の実行中に参照, 追加などが行われる. @end itemize \E \BEG @itemize @item @item @item @end itemize \E \JP @section 中間言語 \EG @section Intermediate language \BJP @example typedef struct oFNODE @{ 式を表すノード fid id; 識別子 pointer arg[1]; 引数配列 (長さ可変) @} oFNODE *FNODE; typedef struct oSNODE @{ 文を表すノード sid id; 識別子 int ln; 行番号 pointer arg[1]; 引数配列 (長さ可変) @} oSNODE *SNODE; @end example \E \BEG @example typedef struct oFNODE @{ fid id; pointer arg[1]; @} oFNODE *FNODE; typedef struct oSNODE @{ sid id; int ln; pointer arg[1]; @} oSNODE *SNODE; @end example \E \BJP interpreter の入力となる中間言語の構成は極めて単純である. 中間言語の構成要素は @b{文} および @b{式} である. Asir 言語による入力文字列は, 文の並びとして parse され, @code{SNODE} 構造体のリストに変換される. 文の種類は識別子 @code{id} により示される. 引数配列は文の種類に応じて長さ, およびその各要素の 意味(役割)が決まる. 以下で @code{S_} で始まるのは識別子の名前で, 実際には相異なる整数が割り当てられている. @samp{|} は, 識別子および引数の仕切りを示す. \E @table @code @item S_SINGLE | expr \JP @samp{expr}を実行する. \EG @item S_BREAK \JP 最も内側のループ (@code{S_FOR}, @code{S_DO}) を抜ける. \EG @item S_CONTINUE \JP 最も内側のループの先頭に飛ぶ. \EG @item S_RETURN | expr \JP 関数から抜けて, @samp{expr} の値を返す. \EG @item S_IFELSE | dummy | expr | stat1 | stat2 \JP@samp{expr} の値が 0 でないなら @samp{stat 1} を実行, 0 なら @samp{stat 2} を 実行. \EG @item S_FOR | dummy | expr1 | expr | stat | expr2 \BJP まず @samp{expr1} を実行したあと, @samp{expr} の値が 0 でない間, @samp{stat} と @samp{expr2} の計算を繰り返す. \E \BEG \E @item S_DO | dummy | stat | expr \JP @samp{stat} を実行したあと @samp{expr} を計算し, その値が 0 でない間繰り返す. \EG @end table \BJP @code{SNODE} は行番号を示すメンバ @code{ln} を持つ. 各行がファイルから読まれた 場合に, そのファイルにおける行番号を格納しておく. これはデバッグ時に行番号 から文を特定するためなどに用いられる. 文に対する中間言語定義で分かるように, 文は最終的には式から構成されている. 文中に現れた式は, parser によって解析され, @code{FNODE} 構造体のリストに 変換される. 式の種類は識別子 @code{id}により示される. 引数配列は式の種類 に応じて長さ, およびその各要素の意味(役割)が決まる. 以下で @code{I_} で 始まるのは識別子の名前で, 実際には相異なる整数が割り当てられてい る. @samp{|} は, 識別子および引数の仕切りを示す. \E \BEG \E @table @code @item I_STR | string \JP 文字列 \EG @item I_FORMULA | object \JP 既に Risa object に変換されている \code{object} \EG @item I_ANS | index \JP @samp{index} 番目の計算結果 \EG @item I_GF2NGEN \JP 標数 2 有限体の生成元 \EG @item I_EV | node \JP @samp{node} を指数ベクトルとみて, 係数 1 の単項式を生成する. \EG @item I_FUNC | function | argument list \JP 関数呼び出し \EG @item I_CAR | list \JP @code{list} の先頭要素 \EG @item I_CDR | list \JP @code{list} から先頭要素を除いたリスト \EG @item I_PVAR | index \JP @code{index} 番目のプログラム変数の値 \EG @item I_ASSPVAR | expr1 | expr2 \JP @samp{expr1} で示されるプログラム変数に @samp{expr2} を代入 \EG @item I_INDEX | expr | index \JP @samp{expr} を配列またはリストと見て, @samp{index}で指定される要素を取り出す. \EG @item I_POSTSELF | function | expr \BJP @samp{expr} の値を取り出したあと, @samp{function} が加算なら @samp{expr} を 1 増やし, @samp{function} が減算なら @samp{expr} を 1 減らす. \E \BEG \E @item I_PRESELF | function | expr \BJP @samp{function} が加算なら @samp{expr} を 1 増やし, @samp{function} が減算なら @samp{式} を 1 減らす. その後 @samp{expr} の値を取り出す. \E \BEG \E @item I_LIST | node \JP @samp{node}からリストを生成する. \EG @item I_NOP | expr \JP @samp{expr} が 0 でないなら 0, 0 なら 1. \EG @item I_OR | expr1 | expr2 \JP @samp{expr1}, @samp{expr2} がともに 0 なら 0, それ以外は 1. \EG @item I_AND | expr1 | expr2 \JP @samp{expr1}, @samp{expr2} がともに 0 でないなら 1, それ以外は 0. \EG @item I_CE | expr | expr1 | expr2 \JP @samp{expr} が 0 でないとき @samp{expr1} の値, 0 のとき @samp{expr2} の値. \EG @item I_BOP | bop_id | expr1 | expr2 \BJP @samp{bop_id} で指定される二項演算子 (加減乗除など) に従って, @samp{expr1}, @samp{expr2} を引数として演算. \E \BEG \E @item I_COP | cop_id | expr1 | expr2 \BJP @samp{cop_id} で指定される比較演算子に従って, @samp{expr1}, @samp{expr2} を比較. 結果は 0, 1, -1. \E \BEG \E @item I_LOP | lop_id | expr1 | expr2 \BJP @samp{lop_id} で指定される論理演算子により, @samp{expr1}, @samp{expr2} を引数として論理式を生成. \E \BEG \E @end table \JP @section 字句解析 \EG @section Lexical analysis \BJP 字句解析部では, 空白, タブ, 改行をスキップしたあとの最初の文字によって 最初の分類を行う. \E \BEG \E @itemize @bullet \BJP @item 0 続く 0 をスキップして, 数字が来たら 10 進数, b が来たら 2 進数, x が来たら 16 進数として, あとに続く valid な文字をバッファに読み込み, 2^32 進数に 変換する. @item 0 以外の数字 以下に続く数字をバッファに読み込み, 10 進数として 2^32 進数に変換する. @item 英小文字 以下に続く, アルファベット, 数字, @samp{_} をバッファに読み込み, keyword の場合にはその識別子, そうでない場合には @samp{小文字で始まる文字列} を意味 する識別子を返す. @item 英大文字 以下に続く, アルファベット, 数字, @samp{_} をバッファに読み込み, @samp{大文字で始まる文字列} を意味する識別子を返す. @item @code{@@} @code{@@} はその後に来る文字列によりさまざまな対象を表す. @itemize @code{-} @item @code{@@@@} 直前の計算結果 @item @code{@@pi} 円周率を表す不定元 @item @code{@@e} 自然対数の底を表す不定元 @item @code{@@i} 虚数単位 @item @code{@@p} 奇標数有限体の拡大体の生成元 @item @code{@@true}, @code{@@false}, @code{@@impl}, @code{@@repl}, @code{@@equiv} 論理演算子 @end itemize これ以外の場合 @code{@@} は標数 2 の有限体の生成元を表す. @item @samp{"} 次の @samp{"} の直前の文字までを文字列 Risa object とみなす. @item @samp{'} 次の @samp{'} の直前の文字までを @samp{小文字で始まる文字列} とみなす. これは, 任意文字列を名前とする不定元を生成する必要がある場合などに 用いる. @item その他の記号 記号に応じてさまざまに扱われる. 多くは演算子として扱われるが, @samp{@{}, @samp{@}}, @samp{[}, @samp{]}, @samp{(}, @samp{)} など, 一対で間にある対象に作用するものもある. \E \BEG @item 0 続く 0 をスキップして, 数字が来たら 10 進数, b が来たら 2 進数, x が来たら 16 進数として, あとに続く valid な文字をバッファに読み込み, 2^32 進数に 変換する. @item 0 以外の数字 以下に続く数字をバッファに読み込み, 10 進数として 2^32 進数に変換する. @item 英小文字 以下に続く, アルファベット, 数字, @samp{_} をバッファに読み込み, keyword の場合にはその識別子, そうでない場合には @samp{小文字で始まる文字列} を意味 する識別子を返す. @item 英大文字 以下に続く, アルファベット, 数字, @samp{_} をバッファに読み込み, @samp{大文字で始まる文字列} を意味する識別子を返す. @item @code{@@} @code{@@} はその後に来る文字列によりさまざまな対象を表す. @itemize @code{-} @item @code{@@@@} 直前の計算結果 @item @code{@@pi} 円周率を表す不定元 @item @code{@@e} 自然対数の底を表す不定元 @item @code{@@i} 虚数単位 @item @code{@@p} 奇標数有限体の拡大体の生成元 @item @code{@@true}, @code{@@false}, @code{@@impl}, @code{@@repl}, @code{@@equiv} 論理演算子 @end itemize これ以外の場合 @code{@@} は標数 2 の有限体の生成元を表す. @item @samp{"} 次の @samp{"} の直前の文字までを文字列 Risa object とみなす. @item @samp{'} 次の @samp{'} の直前の文字までを @samp{小文字で始まる文字列} とみなす. これは, 任意文字列を名前とする不定元を生成する必要がある場合などに 用いる. @item その他の記号 記号に応じてさまざまに扱われる. 多くは演算子として扱われるが, @samp{@{}, @samp{@}}, @samp{[}, @samp{]}, @samp{(}, @samp{)} など, 一対で間にある対象に作用するものもある. \E @end itemize \JP @section 名前管理 \EG @section Names \BJP Asir においては, 不定元, 関数, プログラム変数という 3 つのカテゴリ別に 名前が管理されている. \E \BEG \E \JP @subsection 不定元 \EG @subsection Indeterminates \BJP 不定元は変数リスト @code{CO} (Current variable Order) で管理される. 不定 元と認識される文字列が字句解析部から与えられた場合, @code{CO} に登録され ている不定元の名前とその文字列を順に比較し, 一致した場合にはその不定元構 造体ポインタを対応する変数として用いる. 一致する名前がない場合には新たに 不定元構造体を生成し, 与えられた文字列を名前として登録し, @code{CO} の 末尾に追加する. \E \BEG \E \JP @subsection 関数 \EG @subsection Functions @example \BJP 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; 純関数リスト \E \BEG 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; 純関数リスト \E @end example \BJP 関数には, 組み込み関数, ユーザ定義関数, PARI 関数および純関数がある. い ずれも 関数構造体 @code{FUNC} として登録されリストとして保持される. 組み 込み関数のうち, 引数を持つものは, @code{sysf} に, 持たないものは @code{noargsysf} に登録される. ユーザ定義関数は, 呼び出し時あるいは関数定義時に, @code{usrf} を検索し, リスト中にその名の関数がない場合に @code{FUNC} 構造体が生成され, リストに 追加される. 関数定義が行われる前に呼び出しが行われた場合, @code{FUNC} 構造体のメンバ @code{id} には, 未定義を意味する識別子がセットされる. 後に実際に関数定義が行われた際に, このメンバはユーザ定義関数を意味する 識別子で上書きされ, その他のメンバも然るべくセットされる. 既に定義 されている場合には, これらのメンバは上書きされる. 即ち, 同一関数名 では最新の定義が用いられる. PARI 関数は, 実際の計算に PARI ライブラリを用いるという点を除けば, 組み込み関数と同等である. ただし, PARI ライブラリは PARI bigfloat を結果として返すので, double float の結果を得たい場合のために, C の @code{libm} ライブラリの同等の関数ポインタを保持している. 組み込み, ユーザ定義, PARI 関数は, 引数を用いて計算を行い, Risa object を結果として返す, 通常のプログラミング言語の意味での関数だが, 純関数は, 引数のみが評価されて, その引数を持つ関数呼び出しそのものを返す. Asir の実行例を示す. \E \BEG \E @example [0] A=sin(x); sin(x); [1] type(A); \JP 2 <--- 純関数は多項式 \EG 2 <--- [2] vtype(A); \JP 2 <--- 属性は純関数 \EG 2 <--- [3] args(A); \JP [x] <--- 引数リスト \EG [x] <--- [4] B=functor(A); \JP sin <--- 関数子 \EG sin <--- [5] type(B); \JP 2 <--- 関数子も多項式 \EG 2 <--- [4] vtype(B); \JP 3 <--- 属性は関数子 \EG 3 <--- @end example \BJP この例では, @code{sin(x)} なる純関数が生成されているが, Risa object とし ては, @code{sin(x)} 自身が不定元, 即ち多項式となる. しかし @code{V} 構造 体としての属性 (メンバ @code{attr}) の値が異なる. この値が純関数を意味す るとき, メンバ @code{priv} にはこの純関数に関するさまざまな情報が格納さ れ, @code{args}, @code{functor} により取得される. 関数子自身も, Risa object としては不定元として存在する. この場合も属性により関数子である ことが示される. \E \BEG \E \JP @subsection プログラム変数 \EG @subsection Program variables @example \BJP 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; 計算結果を格納する配列 \E \BEG 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; \E @end example \BJP Asir においては, プログラム変数のスコープは, 大域変数と, プログラム内で の局所変数の 2 レベルに単純化されている. 変数は, 現れた時点でいずれかの プログラム変数として登録される. 関数の外で現れたプログラム変数は, 大域変 数配列に登録される. 関数定義内で現れたプログラム変数は, 関数定義固有の局 所変数配列に登録され, @code{USRF} 構造体のメンバ @code{pvs}として登録さ れる. 関数が実行される場合に, 登録された局所変数配列をテンプレートとして, スタックに相当する変数配列が生成され, 実行時の変数の値はこの配列に格納 される. 中間言語において, プログラム変数参照はインデックスにより行われる. 関数 内での変数参照は, 通常は局所変数配列内の変数に対するインデックスが用いら れるが, extern 宣言されている変数に関しては, 同名の大域変数配列の変数に 対するインデックスが用いられる. この場合, 実際にはこの区別はインデックス の最上位ビットを 1 にすることで行っている. \E \BEG \E