/*&generate-prologue */ $Id: tr.oxt,v 1.3 2005/04/01 11:33:16 taka Exp $ $OpenXM: OpenXM/src/asir-contrib/testing/tr-ja.oxt,v 1.2 2005/04/01 11:34:21 takayama Exp $ 注意: testing/tr.rr では quote を quotetolist で list に変換して扱うため, 下の仕様とはことなり, list 型でデータを戻す場合も多い. ユーザ言語で書いている関係上 pn(x) を pn("x") としている. 他にも同様な関数があり. @c -------------------------------------------------------------------- @section quote に対する基本関数 /*&usage begin: qt_node(Q) quote データ {Q} の node を取り出す. example: qt_node(quote(1+2*3)) end: */ /*&usage begin: qt_nchild(Q) quote データ {Q} の 子供の数を戻す. example: qt_nchild(quote(1+2*3)) 2 を戻す. end: */ /*&usage begin: qt_child(Q,K) quote データ {Q} の {K} 番目の子供を戻す. example: qt_child(quote(1+2*3),1) quote(2*3) を戻す. end: */ @c -------------------------------------------------------------------- @subsection quote に対する述語 /*&usage begin: qt_is_integer(Q) quote データ {Q} が整数なら 1 example: qt_is_integer(quote(0)) end: */ /*&usage begin: qt_depend(Q,x) quote データ {Q} が不定元 {x} を含むと 1, 含まないと 0. example: qt_depend(quote(1+1/x),x) end: */ @c -------------------------------------------------------------------- @subsection quote に対するコンストラクタ /*&usage begin: qt_zero() quote 0 を戻す. end: */ /*&usage begin: qt_id(Qobj) quote object {Qobj} をそのまま戻す. end: */ /*&usage begin: qt_replace(Qobj,[[x,Valuex],[y,Valuey],...]) quote object {Qobj} の中の x を Valuex, y を Valuey, ... に置き換えた quote object を戻す. end: */ /*&usage begin: qt_parenthesis(Qobj) quote object {Qobj} の中の括弧が足りないときには補い, 多いときには取り去った quote object を作る. +, *, /, ^, - 等についての asir の文法での演算子の強さを仮定する. end: */ /*&usage begin: qt_eval(Qobj,type) Qobj を asir の他の object に変換. end: */ /*&usage begin: qt_(Obj) asir の Obj を quote 型に変換. end: */ その他 qt_expand, qt_sort, qt_ht, qt_rest, qt_mtov も基礎関数として欲しい. @c -------------------------------------------------------------------- @section tr (term rewriting) のトップレベルの関数 /*&usage begin: tr_match0(Qobj,P) quote データ {Qobj} が パターン {P} に適合すれば 1 を戻し, そうでなければ 0 を戻す. example: tr_match0(quote(1+2*3),quote(pn(x)+pn(y))) tr_match0(quote(1+2*3),quote(pn(x)+pn(y,qt_is_integer,x))) end: */ pn(x) は任意の quote object にマッチし, 名前 x をつける. tr_match0(quote(1+2*3),quote(pn(x)+pn(y))) は 1 を戻すが, tr_match0(quote(1+2*3),quote(pn(x)+pn(y,tr_is_integer,x))) は 0 をもどす. 2*3 は integer から作られた fnode ではあるが integer ではないので qt_is_integer が 0 を戻すため. /*&usage begin: tr_match1(Qobj,P,Act) quote データ {Qobj} が パターン {P} に適合すれば {Act} を呼び出しその値を戻す. パターン {P} にマッチしないときは 0. example: tr_match1(quote(1+2*3),quote(pn(x)+pn(y)),[myadd,x,y]) end: */ /*&usage begin: tr_or_match1(Qobj,Rules) end: */ /*&usage begin: tr_apply_rule1(Qobj,P,Act) quote データ {Qobj} の木を幅優先探索し, パターン {P} に適合するものがあるときは {Act} を呼び出しその値を戻す. つまり top node が {P} に適合するか調べ, 適合しない場合はその子供に tr_apply_rule1 を適用する (ここが tr_match1 とは異なる). マッチしない場合は Qobj をそのまま戻す (これが再帰的に適用される). example: tr_apply_rule1(quote(1+sin(2*@pi)),quote(sin(pn(x)*@pi)),[sin_int,x]) end: */ 深さ優先で書き換えをするには 関数 sin_int の中でまた tr_apply_rule1 を呼び出せば よい. /*&usage begin: tr_apply_or_rules(Qobj,Rules) end: */ @subsection 内部関数 /*&usage begin: tr_apply_function0(Qobj,Arg1,...) end: */ /*&usage begin: tr_rp(Qobj,P,A) end: */ /*&usage begin: tr_make_binding(Qobj,P) end: */ @c --------------------------------------------------------- @section 変数パターンと関数パターン 例: pn(x) 任意のものにマッチ. マッチしたものを x に bind. pn(x,qt_is_integer(x)) fn(f) 任意の関数にマッチ. マッチした関数名を f に bind. fn(f,pn(x),pn(y)) 任意の関数にマッチ. マッチした関数名を f に bind. f の引数を x, y に bind @c --------------------------------------------------------- @section パターン パターンは quote で与える. 予約語 tr_and, tr_or, tr_not はパターンのマッチに関して論理演算をおこなう. たとえば quote(tr_and(pn(x,qt_is_integer),pn(x,qt_is_non_negative))) は x が 整数で - が先頭についていない場合マッチする. @c --------------------------------------------------------- @section 例題 sin(整数*@pi) を 0 に. /* 準備 */ extern P,A; P=quote(sin(pn(x)*@pi)); /* パターン */ A=[sin_int,x] /* action, action 関数 */ def sin_int(X) { X = tr_apply_rule1(X,P,A); /* 子供に [P,A] を再帰的に適用 */ if (qt_is_integer(X)) return qt_zero(); else qt_replace(sin(y*@pi),[[y,X]]); /* sin(x*@pi) をそのまま戻す.*/ } /* 計算 */ Qobj=quote(1+sin(sin(2*@pi)*@pi)*sin((1/2)*@pi)); tr_apply_rule1(Qobj,P,A); @c --------------------------------------------------------- @section 例題 不定積分 /* integral(f+g) => integral(f)+integral(g) */ S1=[quote(integral(pn(f)+pn(g))), [int_linear1,f,g]]; def int_linear1(X,Y) { return qt_replace(quote(integral(f)+integral(g)),[[f,X],[g,Y]]); } /* integral(c*f) => c*integral(f) */ def qt_independent(F,X) { return !qt_dependent(F,X); } S2=[quote(integral(pn(c,qt_independent(c,x))*f)), [int_linear2,c,f]]; def int_linear2(X,Y) { return qt_replace(quote(c*integral(f)),[[c,X],[f,Y]]); } apply_or_rules(quote(integral(a*x^2+x+2/x)),[S1,S2]); これをこれ以上書き換えが起きないまで繰り返す. このルールの場合答えは a*integral(x^2)+integral(x)+integral(2/x); quote(integral(x^pn(n))) --> x^(n+1)/(n+1) or log(x) を書く. @c --------------------------------------------------------- @section 例題 簡単な構文解析 式(expression) は 式+式 | 式*式 | (式) | 整数 extern R1,R2,R3,R4,S1,S2,S3,S4; /* 文法を満たすかどうかの check 用. Action 部は 1 か 0 */ R1=[quote(pn(x,is_expression(x))+pn(y,is_expression(y))), 1]; R2=[quote(pn(x,is_expression(x))*pn(y,is_expression(y))), 1]; R3=[quote((pn(x,is_expression(x)))), 1]; R4=[quote(pn(x,qt_is_integer(x))), 1]; def is_expression(Qobj) { R = [R1,R2,R3,R4]; A = apply_or_match0(Qobj,R); if (A == 0) return 0; else return 1; } /* 計算用. R1,R2,R3,R4 と左は共通. */ S1=[quote(pn(x,is_expression(x))+pn(y,is_expression(y))), [myadd,x,y]]; S2=[quote(pn(x,is_expression(x))*pn(y,is_expression(y))), [mymul,x,y]]; S3=[quote((pn(x,is_expression(x)))), [qt_id,x]]; S4=[quote(pn(x,qt_is_integer(x))), [qt_id,x]]; def eval_expression(Qobj) { S = [S1,S2,S3,S4]; return apply_or_rules(Qobj,S); } def myadd(X,Y) { return qt_(qt_eval(X,1)+qt_eval(Y,1)); } def mymul(X,Y) { return qt_(qt_eval(X,1)*qt_eval(Y,1)); } /* 計算 */ tr_eval_expression(quote(1+2*(3+15))); @c --------------------------------------------------------- @section 例題 非可換環の簡単な構文解析 /*&generate-epilogue */