 ４．逆ポーランド記法 |
|||||||||||||
|
|
|||||||||||||
| 項 | 内 容 |
| （１） | 逆ポーランド記法とは |
| （２） | 変換手順 |
| （３） | 単項演算子の判別 |
（１）逆ポーランド記法とは
構文解析では，語彙解析の結果から文を判別して，
一文の解析結果を作成します。
一般に，構文解析の表現は，前から順に処理できますが，
式の場合は，優先順位を判別し，
処理順序を入れ替える必要があります。
この入れ替えのための基本的な方法が，
まず，式表現を逆ポーランド記法という記法に変換します。
逆ポーランド記法では，
以下のように括弧や式の優先順位に依存しない
演算順序となります。
[通常の式] Ａ＊（Ｂ＋Ｃ）
[逆ポーランド記法] ＡＢＣ＋＊
この式は，
Ａに[ＢとＣを加えた（＋）値]を乗じる（＊）
という意味になります。
日本語による語順に対応していますね。
（２）変換手順
通常の式を逆ポーランド記法に変換するには，
以下の手順で行います。
@変数や定数はそのまま出力トークンへ移動する。
A演算子はスタック上の演算子と比較し，
スタック上の演算子の優先度が取り出した演算子と等しいか
大きい場合，スタック上の演算子をポップして出力トークンに移動する。
C取り出した演算子をプッシュする。
D前括弧の場合，プッシュする。
E後括弧の場合，前括弧までをポップする。
このとき，スタックトップが関数表現ならば，
関数呼出しを出力トークンに移動する。
F関数表現の場合，関数表現と前括弧をプッシュする。
Gコンマの場合，前括弧の直前までポップする。
H１文終わりのときは後括弧と同じ処理を行う。
変換方法の動きは，以下のプログラムで
アニメーション的に観察できます。
「逆ポーランド記法への変換」プログラム
ダウンロードし，実行してみましょう。
同プログラムで示すように，逆ポーランド記法で書かれた式は，
スタックマシンを使って計算を実行したり，
アセンブラプログラムに変換（コンパイル）することができます。
（３）単項演算子の判別
演算子には，２項演算子だけでなく単項演算子もあります。
特に＋や−は，
位置によって２項演算子（加算／減算）か
前置単項演算子（プラス／マイナス）かが異なってきます。
この判別は，以下のように行います。
@演算子モードと値モードを用意し，初期値は値モードとする。
A値モードのとき，演算子がきたら前置単項演算子とみなす。
B演算子モードのとき，前括弧がきたら，
先行する名前は関数表現とみなし，値モードに移行する。
C演算子モードのとき，後置演算子か通常の演算子かを判定する。
後置演算子でない場合，値モードに移行する。
Dコンマのとき，値モードに移行する。
E前括弧の場合，値モードに移行する。
F後括弧の場合，演算子モードに移行する。
[プログラム例]
以下のようなデータ領域を宣言します。
public struct TokenData
{
public string operation;
public int priority;
public string str;
public TokenData(string ope,int pr, string st)
{
operation = ope;
priority = pr ; str = st ;
}
}
public int numPolish=0 ;// 出力トークンの数
public int numToken=0 ; // 入力トークンの数
public int ptrStack=0 ; // スタックの高さ
public TokenData[] Polish=new TokenData[200];// 出力トークン
public TokenData[] Stack=new TokenData[200]; // スタック
public WordData[] token=new WordData[500]; // 入力トークン
また，これらのデータ領域にアクセスするために，
以下のようなメソッドを用意します。
public void push(TokenData TK) { Stack[ptrStack++]=TK; }
public TokenData pop()
{ if(ptrStack==0) return new TokenData("Empty",0,"");
ptrStack--; return Stack[ptrStack];
}
public void postFix(TokenData TK) // 出力トークンへの移動
{ Polish[numPolish]=TK;numPolish++;}
public void pushProc(TokenData TK) // 優先順位を考慮したPush
{
if(ptrStack>0)
while(ptrStack>0 &&TK.priority<=Stack[ptrStack-1].priority
&& TK.operation!="(") postFix(pop());
push(TK);
}
public void popProcS() // 前括弧までをPop
{
TokenData XX=pop();
while(ptrStack>=0)
{
if(XX.operation=="(") break;
if(XX.operation=="Func"){ postFix(XX);break; }
postFix(XX); XX=pop();
}
}
public void popProcF() // 関数表現までPop
{
TokenData XX = pop();
while(ptrStack>=0)
{
if(XX.operation=="Func"){push(XX); break;}
postFix(XX); XX=pop();
}
}
public void popProcBlock() // ifやWhileのブロックまでPop
{
TokenData XX = pop();
while(ptrStack>=0)
{
if(XX.operation=="Block")break;
postFix(XX);
XX=pop();
}
}
public void popProcE() // 式の終わりのPop
{
TokenData XX; XX=pop();
while(ptrStack>0) { postFix(XX);XX=pop();}
if(XX.operation!="Empty")postFix(XX);
}
語彙解析結果を
逆ポーランド記法への変換用領域に移動するための
メソッドを用意しておきます。
private void token複写(ref int i) // 語彙解析結果すべてを複写
{ numToken=0;
while(i<numTokenX) { token[numToken]=tokenX[i];numToken++; i++; }
}
private void token複写Comma(ref int i) // コンマまでを複写（括弧のレベルを考慮する）
{ numToken=0;int lebel=0;
while(i<numTokenX)
{ if (tokenX[i].type=="Delimiter" && tokenX[i].str=="(")lebel++;
else if(tokenX[i].type=="Delimiter" && tokenX[i].str==")")lebel--;
else if(lebel==0 && tokenX[i].type=="Delimiter" && tokenX[i].str==",") return;
token[numToken]=tokenX[i];numToken++; i++;
}
}
まず，例によってトレース用のメソッドを示します。
private void debugSA0(int i,bool Mode)
{
string S="*Lexical\n";
int k;
for(k=i; k<numToken; k++) S +=" " + token[k].str;
S+="\n*Mode = "+(Mode ? "Value" :"Operation")+"\n*Polish\n";
for(k=0; k<numPolish; k++)
{ // 前置単項演算子としての「-」，「+」 は「-$」，「+$」とする。
if(Polish[k].operation=="-$" || Polish[k].operation=="+$")
S +=" " + Polish[k].operation;
else S +=" " + Polish[k].str;
}
S += "\n*Stack\n";
for(k=ptrStack-1; k>=0; k--)
{
if(Stack[k].operation=="-$" || Stack[k].operation=="+$")
S +=" " + Stack[k].operation;
else S +=" " + Stack[k].str; S+="\n";
}
DialogResult result = MessageBox.Show(S, "構文解析途中経過1",
MessageBoxButtons.OKCancel);
if(result==DialogResult.Cancel) checkBox1.Checked=false;
}
変換処理では，値モードと演算子モードに分けて処理します。
演算子の優先順位の判定は，pushProcメソッド中で処理しています。
// 以下の処理を行う前に，
// 文中の式表現に対応する部分を取り出して
// token[numToken]に移しておく
private void SA0()
{ numPolish=0; ptrStack=0 ; int i=0;bool Mode=true;
while(i<numToken)
{ if(checkBox1.Checked) debugSA0(i,Mode);
if(Mode)
{ // 値モード
if(token[i].type=="Delimiter" && (token[i].str=="+" || token[i].str=="-"))
pushProc(new TokenData(token[i].str+“$”,300,token[i].str)); // 前置
else if(token[i].type=="Delimiter" && (token[i].str=="++" || token[i].str=="--"))
pushProc(new TokenData(token[i].str+“$”,300,token[i].str)); // 前置
else if(token[i].type=="Delimiter" && token[i].str=="!" )
pushProc(new TokenData(token[i].str,40,token[i].str)); // 前置
else if(token[i].type=="Delimiter" && token[i].str=="(")
pushProc(new TokenData(token[i].str,0,token[i].str)); // 前括弧
else if(token[i].type=="Name" && token[i].str=="if")
{ // if関数
postFix(new TokenData("if",0,token[i].str));
push(new TokenData("Block",0,token[i].str));
}
else if(token[i].type==“Name” && // 関数表現
i<(numToken-1) &&
(token[i+1].type=="Delimiter" && token[i+1].str=="("))
{
postFix(new TokenData("ArgEnd",0,token[i].str));
push(new TokenData("Func",0,token[i].str));
i++;
}
else if(token[i].type!=“Delimiter”) // 値または変数など
{
postFix(new TokenData(token[i].type,0,token[i].str));
Mode=false; // 演算子モードに移行
}
else { MessageBox.Show("001 区切記号の位置の誤り"); break; }
}
else
{ // 演算子モード
Mode=true; // 標準的には値モードに移行
if (token[i].type=="Delimiter" &&
(token[i].str=="+" || token[i].str=="-"))
pushProc(new TokenData(token[i].str,100,token[i].str));
else if(token[i].type=="Delimiter" &&
(token[i].str=="++" || token[i].str=="--"))
pushProc(new TokenData(token[i].str,10,token[i].str));
else if(token[i].type=="Delimiter" &&
(token[i].str=="+=" || token[i].str=="-="))
pushProc(new TokenData(token[i].str,10,token[i].str));
else if(token[i].type=="Delimiter" &&
(token[i].str=="*=" || token[i].str=="/="))
pushProc(new TokenData(token[i].str,10,token[i].str));
else if(token[i].type=="Delimiter" && token[i].str=="=")
pushProc(new TokenData(token[i].str,10,token[i].str));
else if(token[i].type=="Delimiter" &&
(token[i].str=="||" || token[i].str=="&&" || token[i].str== "%%"))
pushProc(new TokenData(token[i].str,30,token[i].str));
else if(token[i].type=="Delimiter" &&
(token[i].str=="==" || token[i].str=="!=" || token[i].str== ">" ||
token[i].str==">=" || token[i].str=="=>" || token[i].str== "<" ||
token[i].str=="<=" || token[i].str=="=<"))
{
if (token[i].str=="=>") token[i].str=">=";
else if(token[i].str=="=<") token[i].str="<=";
pushProc(new TokenData(token[i].str,50,token[i].str));
}
else if(token[i].type=="Delimiter" &&
(token[i].str=="*" || token[i].str=="/"|| token[i].str=="%"))
pushProc(new TokenData(token[i].str,200,token[i].str));
else if(token[i].type=="Name" && token[i].str=="mod")
pushProc(new TokenData(token[i].str,200,token[i].str));
else if(token[i].type=="Delimiter" && token[i].str=="^")
pushProc(new TokenData(token[i].str,400,token[i].str));
else if(token[i].type=="Delimiter" && token[i].str==")")
{ popProcS();Mode=false;}
else if(token[i].type=="Delimiter" && token[i].str==",") popProcF();
else if(token[i].type=="Name" &&
(token[i].str=="then" || token[i].str=="else"))
{
popProcBlock();
postFix(new TokenData(token[i].str,0,token[i].str));
push(new TokenData("Block",0,token[i].str));
Mode=true;
}
else if(token[i].type=="Name" && token[i].str=="endif")
{
popProcBlock();
postFix(new TokenData(token[i].str,0,token[i].str));
Mode=true;
}
else { MessageBox.Show("002 名前の位置または演算子の誤り"); break; }
}
i++;
}
if(checkBox1.Checked) debugSA0(i,Mode);
popProcE();
}
目 次
１．言語プロセッサの処理
２．文の識別
３．語彙解析
４．逆ポーランド記法
５．構文解析とコード生成
６．インタプリタ
ダウンロード
（以下をクリックするとダウンロードできます）
| 逆ポーランド記法への変換 |
| 本記事で示すソースプログラム例 |