パーソナル

５．構文解析とコード生成

項	内　　容
（１）	構文解析の処理
（２）	中間コードの展開形式
（３）	中間コード展開のプログラム

（１）構文解析の処理

文種別ごとに，
式部分を分離し，逆ポーランド変換を行い，文ごとの解釈を行います。

文の中には，IfブロックやWhileブロックのように，
離れた部分にジャンプしたり，
後から前の部分を参照するような処理が必要となります。

またこれらのブロック中に，同様のブロックを挿入できます。
すなわち，制御構造をネストさせることができます。

これらを処理するためのスタックを用意します。

　　public struct BlockData　// ブロックコントロールデータ
　　{
　　　　public string Type;
　　　　public int BP;
　　　　public int IfP;
　　　　public int ThenP;
　　}
　　public BlockData [] IfStack=new BlockData[200];
　　public int IfStackP=0;
　　public BlockData [] DoStack=new BlockData[200];
　　public int DoStackP=0;
　　public int[] numBreak=new int[200];　// Break処理用テーブル
　　public int[,] BreakP=new int[200,200];

トレース用ルーチン

　　private void debugSA(int i)
　　{
　　　　listBox2.Items.Clear();string S="";
　　　　for(int k=0;k<numPolish;k++)
　　　　{
　　　　　　string X=Polish[k].operation+ "\t" + Polish[k].str; 　　 S="\n"+X;
　　　　　　listBox2.Items.Add(X);
　　　　}
　　　　DialogResult result =
　　　　　　　MessageBox.Show(S,"構文解析途中経過2",MessageBoxButtons.OKCancel);
　　　　if(result==DialogResult.Cancel) checkBox1.Checked=false;
　　}

（２）中間コードの展開形式

デバッグでソースプログラムの文番号を表示可能とするために，

　　　　StNo　　文番号
　　　　　　　　　（文の中間コード群）

の形式で出力します。

代入文では，逆ポーランド記法そのものを中間コード群とします。
その他の文は，以下のとおりとします。

(a) if文

　　　　　　　　　　　　　　（論理式の逆ポーランド記法）
　　　　IfP:　　　　L1 push　　　　　　　　　（elseでL1を設定）
　　　　　　　　　　then

　　　　　　　　　　（then以降のオブジェクト）

　　　　ThenP:　　L2 push　　　　　　　　　（elseでThenP設定，endifでL2を設定）
　　　　　　　　　　goto
　　　　L1:　
　　　　　　　　　　(Else以降のオブジェクト)
　　　　L2:

　　　または，ThenPがないとき，すなわちelseがなかったとき

　　　　　　　　　　（論理式の逆ポーランド記法）
　　　　IfP:　　　　L2 push　　　　　　　　（endifでL2を設定）
　　　　　　　　　　then

　　　　　　　　　　（then以降のオブジェクト）
　　　　L2:

　　なお，「then」という命令は，
　　スタック上の２つデータをポップし，後からポップした値が偽であれば，
　　先にポップした値をプログラムカウンタの値にする（ジャンプする）命令と
　　とします。

　　「goto」という命令は，ポップした値を
　　プログラムカウンタの値にする（ジャンプする）命令とします。
　　
(b) while文

　　　　 Bp:
　　　　　　　　　　（論理式の逆ポーランド記法）
　　　　IfP:　　　　L1 push　　　　　　　　(wendでL1を設定）
　　　　　　　　　　then

　　　　　　　　　　（while以降のオブジェクト）

　　　　ThenP:　　Bp push
　　　　　　　　　　 goto
　　　　L1:　
　　　　（wendでL1をbreakに設定）

(c) repeat文

　　　　Bp:

　　　　　　　　　　（repeat以降のオブジェクト）

　　　　　　　　　　（論理式の逆ポーランド記法）
　　　　ThenP:　　Bp push
　　　　　　　　　　 then
　　　　L1:
　　　　（untilでL1をbreakに設定）

(d) for文

　　　　　　　　　　（初期化式の逆ポーランド記法）
　　　　　　　　　　L1 push
　　　　　　　　　　goto
　　　　Bp:　　　　（増分式の逆ポーランド記法）
　　　　L1:　　　　（判定式の逆ポーランド記法）
　　　　　　　　　　L2 push　　　　　　(nextでL2を設定）
　　　　　　　　　　then

　　　　　　　　　　（for以降のオブジェクト）

　　　　　　　　　　Bp push
　　　　　　　　　　goto Bp
　　　　L2:
　　　　（nextでL2をbreakに設定）

(e) function文（関数名テーブルに登録）

　　　　　　　　　　*Pstart*
　　　　　　　　　　*Parm 引数名１
　　　　　　　　　　*Parm 引数名２
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　*Pend

　　　　（return）
　　　　　　　　　　（リターン値の逆ポーランド記法）
　　　　　　　　　　return

(f) 関数呼出し
　　　　　　　　　　*ArgEnd　関数名
　　　　　　　　　　(引数１の逆ポーランド記法）
　　　　　　　　　　(引数２の逆ポーランド記法）
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　Func 配列名

(f) dim文

　　　　　　　　　　*dimStart 配列名
　　　　　　　　　　*ArgEnd 配列名
　　　　　　　　　　(添え字１の逆ポーランド記法）
　　　　　　　　　　(添え字２の逆ポーランド記法）
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　dim 配列名

（３）中間コード展開のプログラム

[プログラム例]

以下にプログラム例を示しますが，途中を省略します。
全ソースプログラムを参照するには，ソースプログラムをダウンロードしてください。

[⇒今すぐダウンロード]

　private void SA()
　{
　　　int i=0;
　　　while(i<numTokenX)
　　　{
　　　　　if(tokenX[i].type==“Name” && tokenX[i].str==“if”) // if文
　　　　　{
　　　　　　　if論理式(ref i); // if文から論理式を取り出し
　　　　　　　numPolish=0; SA0(); numStatementNo++;
　　　　　　　int oldP=numStatement;
　　　　　　　SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　if(checkBox1.Checked) debugSA(0);
　　　　　　　現Polishのオブジェクト設定();
　　　　　　　IfPush(oldP,numStatement,0);
　　　　　　　SA設定("Number",0,""); SA設定("then",0,"then");
　　　　　　　if(i+1 < numTokenX) MessageBox.Show("thenの後に文は書けません");
　　　　　}
　　　　　else if(tokenX[i].type==“Name” && tokenX[i].str==“else”) // else処理
　　　　　{
　　　　　　　IfStack[IfStackP].ThenP=numStatement;
　　　　　　　SA設定("Number",0,""); SA設定("goto",0,"goto");
　　　　　　　numStatementNo++;
　　　　　　　AllStatement[IfStack[IfStackP].IfP].str=numStatement.ToString();
　　　　　　　SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　if(i+1 < numTokenX) MessageBox.Show("elseの後に文は書けません");
　　　　　}
　　　　　else if(tokenX[i].type=="Name" && tokenX[i].str=="endif") // end if
　　　　　{
　　　　　　　numStatementNo++;
　　　　　　　SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　int IP=IfStack[IfStackP].IfP;
　　　　　　　if(AllStatement[IP].str=="") AllStatement[IP].str=numStatement.ToString();
　　　　　　　else AllStatement[IfStack[IfStackP].ThenP].str=numStatement.ToString();
　　　　　　　if(i+1 < numTokenX) MessageBox.Show("endifの後に文は書けません");
　　　　　　　IfStackP--;
　　　　　}
　　　　　else if(tokenX[i].type==“Name” && tokenX[i].str==“while”) // while文
　　　　　{
　　　　　　　i++; token複写(ref i); numPolish=0; SA0();
　　　　　　　numStatementNo++; int oldP=numStatement;
　　　　　　　SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　if(checkBox1.Checked) debugSA(0);
　　　　　　　現Polishのオブジェクト設定();
　　　　　　　DoPush(oldP,numStatement,0,"while");
　　　　　　　SA設定("Number",0,""); SA設定("then",0,"then");
　　　　　}
　　　　　else if(tokenX[i].type=="Name" && tokenX[i].str=="wend")
　　　　　{
　　　　　　　numStatementNo++; SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　SA設定("Number",0,DoStack[DoStackP].BP.ToString());
　　　　　　　SA設定("goto",0,"goto"); string S=numStatement.ToString();
　　　　　　　if (DoStack[DoStackP].Type=="while")
　　　　　　　　　　　　　　　　　　 AllStatement[DoStack[DoStackP].IfP].str=S;
　　　　　　　else MessageBox.Show
　　　　　　　　　　　　("while_wendの対応がとれません.文="+numStatementNo.ToString());
　　　　　　　// Breakの設定
　　　　　　　for(int k=0;k<numBreak[DoStackP];k++)
　　　　　　　　　　　　　　　AllStatement[BreakP[DoStackP,k]].str=S;
　　　　　　　if(i+1 < numTokenX) MessageBox.Show
　　　　　　　　　　　　　　　("wendの後に文は書けません.文="+numStatementNo.ToString());
　　　　　　　DoStackP--;
　　　　　}
　　　　　else if(tokenX[i].type=="Name" && tokenX[i].str=="break")
　　　　　{
　　　　　　　numStatementNo++; SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　BreakP[DoStackP,numBreak[DoStackP]++]=numStatement;
　　　　　　　SA設定("Number",0,""); SA設定("goto",0,"goto");
　　　　　　　if(i+1 < numTokenX) MessageBox.Show("breakの後に文は書けません");
　　　　　　　break;
　　　　　}
　　　　　・
　　　　　・
　　　　　・
　　　　　（中略）全文を見るには，ソースプログラムをダウンロードして下さい）
　　　　　・
　　　　　・
　　　　　・
　　　　　else if(tokenX[i].type=="Name" && tokenX[i].str=="end")
　　　　　{
　　　　　　　numStatementNo++;
　　　　　　　SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　SA設定("end",0,"end");
　　　　　　　if(i+1 < numTokenX) MessageBox.Show
　　　　　　　　　　 ("endの後に文は書けません.文="+numStatementNo.ToString());
　　　　　　　break;
　　　　　}
　　　　　else if(tokenX[i].type=="Name" && tokenX[i].str=="return")
　　　　　{
　　　　　　　i++; token複写(ref i); numPolish=0; SA0();
　　　　　　　numStatementNo++; int oldP=numStatement;
　　　　　　　SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　if(checkBox1.Checked) debugSA(0);
　　　　　　　現Polishのオブジェクト設定(); SA設定("return",0,"return");
　　　　　　　string S=numStatement.ToString();
　　　　　}
　　　　　else
　　　　　{ // 代入文
　　　　　　token複写(ref i); numPolish=0; SA0();
　　　　　　　numStatementNo++; SA設定("StNo",0,numStatementNo.ToString());
　　　　　　　if(checkBox1.Checked)
　　　　　　　{
　　　　　　　　　listBox2.Items.Clear();
　　　　　　　　　for(int k=0;k<numPolish;k++)
　　　　　　　　　　　　listBox2.Items.Add(Polish[k].operation+ "\t" +
　　　　　　　　　　　　　　　　　　　　　　　　　Polish[k].priority.ToString()+ "\t" +
　　　　　　　　　　　　　　　　　　　　　　　　　Polish[k].str);
　　　　　　　}
　　　　　　　現Polishのオブジェクト設定();
　　　　　}
　　　　　if(checkBox1.Checked) debugSA(i);
　　　　　i++;
　　　}
　}

各領域の取り出し，設定用メソッドを以下に示します。

　private void if論理式(ref int i) // ifの論理式
　{
　　　numToken=0;i++;
　　　if(i<numTokenX)
　　　{
　　　　　while(i<numTokenX)
　　　　　{
　　　　　　　if(tokenX[i].type=="Name" && tokenX[i].str=="then"){i++;break;}
　　　　　　　token[numToken++]=tokenX[i++];
　}　}　 }
　private void for初期化(ref int i) // forの初期化式
　{
　　　numToken=0;
　　　if(i<numTokenX)
　　　{
　　　　　while(i<numTokenX)
　　　　　{
　　　　　　　if(tokenX[i].type=="Delimiter" && tokenX[i].str==";"){i++;break;}
　　　　　　　token[numToken++]=tokenX[i++];
　}　}　　}
　private void for判定(ref int i)　　// forの判定式
　{
　　　numToken=0;
　　　if(i<numTokenX)
　　　{
　　　　　while(i<numTokenX)
　　　　　{
　　　　　　　if(tokenX[i].type=="Delimiter" && tokenX[i].str==";"){i++;break;}
　　　　　　　token[numToken++]=tokenX[i++];
　}　}　　}
　private void for増分(ref int i) // forの増分式
　{
　　　numToken=0;
　　　if(i<numTokenX)
　　　{
　　　　　while(i<numTokenX)
　　　　　{
　　　　　　　if(tokenX[i].type=="Delimiter" && tokenX[i].str==""){i++;break;}
　　　　　　　token[numToken++]=tokenX[i++];
　}　 }　 }
　private void SA設定(string op, int pr, string str)
　{
　　　AllStatement[numStatement].operation=op;
　　　AllStatement[numStatement].priority=pr;
　　　AllStatement[numStatement].str=str;
　　　numStatement++;
　}
　private void IfPush(int BP, int IfP,int ThenP)
　{
　　　IfStackP++;
　　　IfStack[IfStackP].BP=BP; IfStack[IfStackP].IfP=IfP;
　　　IfStack[IfStackP].ThenP=ThenP; IfStack[IfStackP].Type="if"
　}
　private void DoPush(int BP, int IfP,int ThenP, string Type)
　{
　　　DoStackP++;
　　　DoStack[DoStackP].BP=BP;　DoStack[DoStackP].IfP=IfP;
　　　DoStack[DoStackP].ThenP=ThenP;　DoStack[DoStackP].Type=Type;
　　　numBreak[DoStackP]=0;
　}
　private void 現Polishのオブジェクト設定()
{ for(int k=0;k<numPolish;k++) AllStatement[numStatement++]=Polish[k]; }

　　　　目　次

１．言語プロセッサの処理

 ２．文の識別

 ３．語彙解析

 ４．逆ポーランド記法

 ５．構文解析とコード生成

 ６．インタプリタ

ダウンロード
（以下をクリックするとダウンロードできます）

逆ポーランド記法への変換

本記事で示すソースプログラム例