 ６．インタプリタ |
|||||||||||||
|
|
|||||||||||||
| 項 | 内 容 |
| （１） | インタプリタの処理 |
| （２） | バインディングの方法 |
| （３） | インタプリタのプログラム |
（１）インタプリタの処理
逆ポーランド記法をインタプリートするには，
（a） 変数や値のときスタックにプッシュする。
（b） 演算子のときスタックをポップして演算し，結果をスタックにプッシュする。
という簡単な手続きで可能となります。
代入の処理も，先にポップした値を，後からポップした変数名に
値を代入するという処理で可能になります。
（２）バインディングの方法
ユーザ定義関数の呼出しでは次のように処理します。
@リターン位置（現在のプログラムカウンタ）および
仮引数に対応する変数名とその値を，
プログラム用のスタックにプッシュします。
A実引数の値を仮引数に設定します。
ただし，実引数が変数のとき，仮引数をReferタイプにして，
同変数名を仮引数に設定します。
実引数もReferタイプのときは，順にリンクをたどり，
最も大元の変数名を設定します。
これは単に効率化のためだけでなく，
リターン時に変数値を元に戻してしまいますので，
値を変更したとき，最も上位の変数値を変更しておく必要があるからです。
B関数の実行（これは通常の処理です）
Cリターン時には，リターン値を演算スタックにプッシュし，
仮引数に対応する変数値は
プログラムスタックからポップすることで，
元に戻します。
プログラムカウンタも元に戻します。
この方法は，シャドウ・バインディングと呼ばれ，
インタプリタでは効率のよい方法として知られています。
この他，スタック上に変数名を割り当てる
ディープ・バインディングという方法もありますが，
処理の複雑さに比べ，それほど効率のよい方法ではありませんので，
ここでは，シャドウ・バインディングを用いることにします。
（３）インタプリタのプログラム
[データの宣言]
public struct NameData // 変数名の構造体
{
public string Name;
public string Text;
public double Val;
public string Type;
public NameData(string name, double val)
{ Name=name; Val=val; Text=val.ToString(); Type="Number"; }
public NameData(string name, string val)
{ Name=name; Val=0.0; Text=val; Type="String"; }
public NameData(string name)
{ Name=name; Val=0.0; Text="" Type="Name"; }
}
public struct FunctionName // 関数名データ
{ public string name; public int ptr; }
public FunctionName [] FunctionNameTable =new FunctionName[200];
public int numberOfFunction=0;
public NameData[] argData =new NameData[200];
public int numArg=0;
public int ptrArg=0;
public int nextIP;
public NameData [] NameTable = new NameData[200];
public int ptrNameTable=0;
public NameData [] EvalStack = new NameData[200];
public int ptrEvalStack=0;
public NameData[] ProgStack=new NameData[2000];
public int ptrProgStack=0 ;
[インタプリタメイン処理]
private void button3_Click(object sender, System.EventArgs e)
{ ptrProgStack=0;Eval();Eval_Display_Result(numStatement+1);}
private void Eval()
{
NameData P1,P2; int i=0;
pushEvalStack(new NameData("*Function*"));
while(i<numStatement)
{
if(checkBox1.Checked)debugEval(i);
nextIP =i+1;
if (AllStatement[i].operation=="end")
{
MessageBox.Show("プログラムの終了です。カウンタ=" + i.ToString());
break;
}
switch (AllStatement[i].operation)
{
case "+" :Eval_add();break;
case "-" :Eval_sub();break;
case "%" :Eval_mod();break;
case "*" :Eval_mult();break;
case "mod" :Eval_mod();break;
case "/" :Eval_dev();break;
case "^" :Eval_exp();break;
case "=" :Eval_set();break;
case "++" :Eval_PPset();break;
case "--" :Eval_MMset();break;
case "++$" :Eval_BeforPPset();break;
case "--$" :Eval_BeforMMset();break;
case "-$" :Eval_minus();break;
case "+$" :Eval_plus();break;
case "+=" :Eval_AsignPset();break;
case "-=" :Eval_AsignMset();break;
case "*=" :Eval_AsignMultset();break;
case "/=" :Eval_AsignDivset();break;
case "==" :Eval_equal();break;
case "!=" :Eval_not_equal();break;
case ">" :Eval_greater_than();break;
case ">=" :Eval_greater_than_equal();break;
case "<" :Eval_less_than();break;
case "<=" :Eval_less_than_equal();break;
case "||" :Eval_or();break;
case "&&" :Eval_and();break;
case "%%" :Eval_exclusive_or();break;
case "!" :Eval_not();break;
case "ArgEnd" :Eval_Arg();break;
case "Func" :Eval_func(AllStatement[i].str);break;
case "*dimStart" :Eval_dimStart(AllStatement[i].str);break;
case "dim" :Eval_dim();break;
case "*PStart*" :Eval_PStart();break;
case "*Parm*" :Eval_Param(AllStatement[i].str);break;
case "return" :Eval_return();break;
case "StNo" :
StatementNo=int.Parse(AllStatement[i].str);
if(checkBox1.Checked)
MessageBox.Show("Statement No = "+AllStatement[i].str);
ptrEvalStack=0;break;
case "goto" :P1=Eval(popEvalStack());
nextIP=(int)P1.Val; break;
case "then" :
P2=Eval(popEvalStack());
P1=Eval(popEvalStack());
if(P1.Type=="Number" && P2.Type=="Number" )
{ if(P1.Val ==0) nextIP=(int)P2.Val; }
else MessageBox.Show("評価エラーです"); break;
default :pushEvalStack(AllStatement[i]);break;
}
i=nextIP; Eval_Display_Result(i);
}
}
[トレースルーチン]
private void debugEval(int i)
{
string S1=AllStatement[i].operation;
string S2=AllStatement[i].str;
if(S1!=S2)
{
if(S1=="String") S1 += ("\"" + S2+"\"");
else S1 += ("(" + S2+")");
}
string S="*Operation " +S1 + "\n\n*PC=" + i + " StNo=" +
StatementNo.ToString();
int k; S += "\n\n*Name Table\n";
for(k=0; k<ptrNameTable; k++)
{
S +=NameTable[k].Name+"\t";
if(NameTable[k].Type=="Number")
S +="Number[" + NameTable[k].Val+"]\n";
else S +=NameTable[k].Type+"[" + NameTable[k].Text+"]\n";
}
S += "\n*Eval Stack\n";
for(k=ptrEvalStack-1; k>=0; k--)
{
S +=EvalStack[k].Name+"\t";
if (EvalStack[k].Type=="Name") S += "Name\n";
else if(EvalStack[k].Type=="Number")
S +="Number[" + EvalStack[k].Val+"]\n";
else S +=EvalStack[k].Type+"\"" + EvalStack[k].Text+"\"\n";
}
DialogResult result = MessageBox.Show
(S,"評価",MessageBoxButtons.OKCancel);
if(result==DialogResult.Cancel) checkBox1.Checked=false;
}
[ 実行用メソッド]
private void pushEvalStack(TokenData TK) // TokenのPush
{
switch (TK.operation)
{
case "String" : EvalStack[ptrEvalStack]
= new NameData("",TK.str);break;
case "Number" : EvalStack[ptrEvalStack]
=new NameData("",double.Parse(TK.str));break;
case "Name" : EvalStack[ptrEvalStack]
=new NameData(TK.str);break;
default : EvalStack[ptrEvalStack]=new NameData("",0.0);
break;
}
ptrEvalStack++;
}
private void pushEvalStack(NameData NM) // 変数名のPush
{ EvalStack[ptrEvalStack]=NM; ptrEvalStack++; }
private void Eval_dimStart(String S) // dim 文の開始
{
EvalStack[ptrEvalStack]=new NameData(S);
EvalStack[ptrEvalStack].Type="*dimStart";
ptrEvalStack++;
}
private void Eval_Array_gen
(string nameDT,NameData[] P,int N,string S)
// 配列生成
{
if(N<0) NameTable[ptrNameTable++]
=new NameData(nameDT+"("+S+")");
else for(int i=1;i<=P[N].Val;i++)
Eval_Array_gen(nameDT,P,N-1,S +","+i.ToString());
}
private void Eval_dim() // dim文の実行
{
NameData[] P =new NameData[200];
NameData P1=popEvalStack();
if(P1.Type=="=*dimStart")
NameTable[ptrNameTable++]=new NameData(P1.Name);
else
{
int numArg=0;
while(ptrEvalStack>=0 && P1.Type!="ARGEND")
{P[numArg++]=P1; P1 =popEvalStack();}
P1=popEvalStack();
if(P1.Type!="*dimStart")
MessageBox.Show("**System Error(Dim文)");
else
{
int N=numArg-1;
if( N>=0) for(int i=0;i<=P[N].Val-1;i++)
Eval_Array_gen(P1.Name,P,N-1,i.ToString());
}} }
private void Eval_Arg() // 引数終了
{
EvalStack[ptrEvalStack]=new NameData("ARGEND");
EvalStack[ptrEvalStack].Type="ARGEND";
ptrEvalStack++;
}
private NameData popEvalStack() // ポップ
{
NameData P=new NameData("$$Undefined$$");
if(ptrEvalStack>0)
{ ptrEvalStack--; P=EvalStack[ptrEvalStack]; }
return P;
}
private NameData Eval(NameData NM) // 変数値を求める
{
switch (NM.Type)
{
case "String": return NM;
case "Number": return NM;
case "Refer" : return Eval(NameTable[(int)NM.Val]);
default :
if(NM.Name=="$$Undefined$$") return new NameData("",0.0);
NameTable[ptrNameTable]=NM; // 変数名テーブルの探索
int ID=-1;
for(int i=ptrNameTable-1;i>=0;i--)
if(NameTable[i].Name==NM.Name){ ID=i;break;}
if(ID<0) // 変数名テーブルになければ変数を登録する
{
NameTable[ptrNameTable]=NM;
ptrNameTable++;
return new NameData(NM.Name,0.0);
}
else // 変数名スコープでReferなら上位を参照
{
while (NameTable[ID].Type=="Refer")
ID=(int)NameTable[ID].Val;
return NameTable[ID];
} } }
[各処理]
一部省略しますので，全関数を参照するには，
ソースプログラムをダウンロードしてください。
private void Eval_add()
{
NameData P2=Eval(popEvalStack());
NameData P1=Eval(popEvalStack());
if(P1.Type=="Number" && P2.Type=="Number")
pushEvalStack(new NameData("",P1.Val + P2.Val));
else if(P1.Type=="String" && P2.Type=="String")
pushEvalStack(new NameData("",P1.Text + P2.Text));
else if(P1.Type=="String" && P2.Type=="Number")
pushEvalStack(new NameData("",P1.Text + P2.Val.ToString()));
else if(P1.Type=="Number" && P2.Type=="String")
pushEvalStack(new NameData("",P1.Val.ToString() + P2.Text));
else pushEvalStack(new NameData("",0));
}
private void Eval_sub()
{
NameData P2=Eval(popEvalStack());
NameData P1=Eval(popEvalStack());
if(P1.Type=="Number" && P2.Type=="Number")
pushEvalStack(new NameData("",P1.Val - P2.Val));
else pushEvalStack(new NameData("","計算できません"));
}
private void Eval_mult()
{
NameData P2=Eval(popEvalStack());
NameData P1=Eval(popEvalStack());
if(P1.Type=="Number" && P2.Type=="Number")
pushEvalStack(new NameData("",P1.Val * P2.Val));
else pushEvalStack(new NameData("","計算できません"));
}
private void Eval_dev()
{
NameData P2=Eval(popEvalStack());
NameData P1=Eval(popEvalStack());
if(P1.Type=="Number" && P2.Type=="Number")
pushEvalStack(new NameData("",P1.Val / P2.Val));
else pushEvalStack(new NameData("","計算できません"));
}
・
・
・（中略：全文を参照するには，ソースプログラムをダウンロードしてください）
・
・
・
private void Eval_AsignPset() // +=
{
NameData P2=Eval(popEvalStack());
NameData P1=popEvalStack();
int i=Eval_set_pointer(P1);
if(NameTable[i].Type=="Number" && P2.Type=="Number")
NameTable[i].Val += P2.Val;
else if(NameTable[i].Type=="Number" && P2.Type=="String")
{
NameTable[i].Type= "String";
NameTable[i].Text= NameTable[i].Val.ToString() + P2.Text;
}
else if(NameTable[i].Type=="String" && P2.Type=="Number")
{
NameTable[i].Type= "String";
NameTable[i].Text= NameTable[i].Text + P2.Val;
}
else
{
NameTable[i].Type= "String";
NameTable[i].Text= NameTable[i].Text + P2.Text;
}
pushEvalStack(Eval(P1));
}
目 次
１．言語プロセッサの処理
２．文の識別
３．語彙解析
４．逆ポーランド記法
５．構文解析とコード生成
６．インタプリタ
ダウンロード
（以下をクリックするとダウンロードできます）
| 逆ポーランド記法への変換 |
| 本記事で示すソースプログラム例 |