スライド 1

４．６演算子優先順位解析
（１）演算子（Operation）と演算対象(Operand)
以下、逆ポーランド記法による演算子優先順位解析について述べる。
（従来言語では伝統的に用いられている手法）
① すべて2項演算子とすると
＜演算対象＞＜演算子＞＜演算対象＞
の順序となる。
② 単項演算子を例外処理として扱う。
（前置演算子と後置演算子がある）
③ 単項演算子の例
符号としての＋，－（加算、減算の＋，－は2項演算子）
論理演算子のNot（C言語の !）
C言語の＋＋，－－, など
④ 後置演算子と2項演算子は明示的に識別できるものでなくてはならない
（重複した文字列の演算子があってはならない。前置演算子は2項演算
子と同一のものがあってもよい）
（2）2項演算子と単項演算子解釈の状態遷移
演算対象モードと演算子モードの2状態を持つものとする。
演算子（演算子としての‘(’を含
む）
（前置演算子とみなす）
後置演算子
（演算子としての‘) ’ , ‘, ’を含む）
２項演算子
S
演算対象モード
演算対象
演算子モード
（名前、定数など）
‘(‘
終了
エラー終了
（“＜関数名＞(“とみなす）
終了
正常終了
【注】 ‘, ’は、 ①最も優先順位の低い演算子とみなす方法（ただし何も演算しない）
②式の区切りとみなす方法
の二通りがある。
（３）スタックを用いて逆ポーランド記法への変換
① 演算対象は、逆ポーランドストリームに出力。
② 演算子は、スタック上の演算子の優先順位と比較
スタック上の演算子の優先順位が高いか等しければポップし、
ポップした演算子を逆ポーランドストリームに出力
現演算子をプッシュ
③ ‘(’は、スタック上にプッシュ。（”<関数名>(“の形式の括弧と式内の括弧
の区別をつける必要がある）
④ ‘)’は、スタック上の‘(’までをポップし、ポップした演算子を逆ポーランド
ストリームに出力（式から括弧が消える）。
④ ‘,’は、スタック上の‘(’直前までポップし（ ‘(’ はスタック上に残る）、
ポップした演算子を逆ポーランドストリームに出力（式から‘,’が消える）。
逆ポーランド記法への変換例(1)
出力ストリーム
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
演算対象
入力ストリーム
A
スタック
A+B*(C/D-E)
逆ポーランド記法への変換例(２)
出力ストリーム
演算子
+
A
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
入力ストリーム
スタック
+B*(C/D-E)
逆ポーランド記法への変換例(３)
出力ストリーム
A
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
演算対象
B
+
スタック
入力ストリーム
B*(C/D-E)
逆ポーランド記法への変換例(４)
出力ストリーム
演算子（優先順位が高い）
AB
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
*
+
スタック
入力ストリーム
*(C/D-E)
逆ポーランド記法への変換例(５)
出力ストリーム
AB
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
前括弧
(
*
+
スタック
入力ストリーム
(C/D-E)
逆ポーランド記法への変換例(６)
出力ストリーム
AB
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
演算対象
C
(
*
+
スタック
入力ストリーム
C/D-E)
逆ポーランド記法への変換例(７)
出力ストリーム
ABC
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
演算子
/
(
*
+
スタック
入力ストリーム
/D-E)
逆ポーランド記法への変換例(８)
出力ストリーム
ABC
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
演算対象
D
/
(
*
+
スタック
入力ストリーム
D-E)
逆ポーランド記法への変換例(９)
演算子（優先順位が低い）
出力ストリーム
ABCD
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
①/
② -
入力ストリーム
-E)
①スタックをポップ
/
(
*
+
スタック
②現演算子プッシュ
逆ポーランド記法への変換例(１０)
演算対象
出力ストリーム
ABCD/
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
E
(
*
+
スタック
入力ストリーム
E)
逆ポーランド記法への変換例(１１)
出力ストリーム
ABCD/E
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
(までをポップ
-
入力ストリーム
)
(
*
+
スタック
)
逆ポーランド記法への変換例(１２)
スタックすべてをポップ
出力ストリーム
ABCD/E演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
* +
終了
*
+
スタック
入力ストリーム
逆ポーランド記法への変換例(1３)
元の入力ストリーム
出力ストリーム
ABCD/E-*+
演算子の優先順位例
()
1000(引数用を含
む）
^
900
+,800(単項演算子）
*, /, %
600
+,500(2項演算子）
==,>,…
400(比較演算子)
!
300(Not)
|, &
200(論理演算子）
=
100
コンマ(,) 10
比較
A+B*(C/D-E)
（４）逆ポーランド記法を元に戻す①
逆ポーランド記法
A
スタック
ABCD/E-*+
逆ポーランド記法を元に戻す②
逆ポーランド記法
B
BCD/E-*+
A
スタック
逆ポーランド記法を元に戻す③
逆ポーランド記法
C
CD/E-*+
B
A
スタック
逆ポーランド記法を元に戻す④
逆ポーランド記法
D
D/E-*+
C
B
A
スタック
逆ポーランド記法を元に戻す⑤
逆ポーランド記法
/
D
C
B
A
スタック
/E-*+
逆ポーランド記法を元に戻す⑥
逆ポーランド記法
E
E-*+
(C/D)
B
A
スタック
逆ポーランド記法の実行⑦
逆ポーランド記法
-
E
(C/D)
B
A
スタック
-*+
逆ポーランド記法の実行⑧
逆ポーランド記法
*
((C/D)-E)
B
A
スタック
*+
逆ポーランド記法の実行⑨
逆ポーランド記法
+
(B*((C/D)-E))
A
スタック
+
逆ポーランド記法の実行⑩
逆ポーランド記法
(A+(B*((C/D)-E)))
スタック
（５）制御文の取扱い①
go to L2
上記表現は、
⇒L2
次の実行アドレスをL2ラベルの値にする単項演算とみなす。
制御文の取扱い②
If＜式＞goto L2
上記表現は、
＜式＞⇒L2
式が成立すれば、次の実行アドレスをL2ラベルの値に
式が成立しなければ、次の実行アドレスは変えない
ような２項演算として捉える。
制御文の取扱い③
If＜式＞Then ＜文１＞Else ＜文２＞
上記表現は、
＜式＞Then Lelse
＜式＞Then Lelse
(Thenを２項演算子、
LeはElse句のラベル）
式が成立しなければ、
＜文１＞
次の実行アドレスをLeラベルの値に、
Goto Lend
式が成立すれば、
Lelse
次の実行アドレスは変えない
＜文２＞
ような２項演算とみなす。
（If<式>goto と逆であることに注意） Lend
制御文の取扱い④
While＜式＞＜文＞
If＜式＞Thenと同様
Lstart
＜式＞Then Lend
＜文＞
Goto Lstart
Lend
（６）逆ポーランド記法への変換のための基本処理
【基本的な処理】
① スタックへのプッシュ
② スタックからのポップアップ
③ 出力ストリームへの出力
【解析用処理】
④ 優先順位を考慮した現演算子のプッシュ（①、②、③の組合せ）
⑤ 関数呼び出しのための引数のポップアップ
⑥ ‘,’演算子のための引数のポップアップ
⑦ ifブロックやWhileブロックのためのポップアップ
⑧ １文最後のポップアップ
(a) 基本的な処理（C#での表現）
①スタックへのプッシュ
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++;
}
(ｂ)解析用（C#での表現）(その1)
④ 優先順位を考慮したプッシュ
public void pushProc(TokenData TK)
{ if(ptrStack>0)
while(ptrStack>0 &&
TK.priority<=Stack[ptrStack-1].priority &&
TK.operation!="(")
postFix(pop());
push(TK);
}
解析用処理（C#での表現）(その2)
⑤ ’(’まで、または関数呼出し最後までをポップ
(関数名(…）または演算子(…)の ‘)’のときの処理)
public void popProcS()
{
TokenData XX=pop();
while(ptrStack>=0)
{
if(XX.operation=="(")
break;
if(XX.operation=="Func"){postFix(XX);break; }
postFix(XX); XX=pop();
}
}
解析用処理（C#での表現）(その３)
⑥ コンマのときの処理（,）
関数呼出しの際の引数の区切り
public void popProcF()
{
TokenData XX = pop();
while(ptrStack>=0)
{
if(XX.operation=="Func"){push(XX); break;}
postFix(XX); XX=pop();
}
}
解析用処理（C#での表現）(その４)
⑦ ブロックのときのポップアップ
（Ifブロック，Whileブロック）
public void popProcBlock()
{
TokenData XX = pop();
while(ptrStack>=0)
{
if(XX.operation=="Block")break;
postFix(XX); XX=pop();
}
}
解析用処理（C#での表現）(その５)
⑧ 文の最後のポップアップ処理
public void popProcE()
{
TokenData XX;
XX=pop();
while(ptrStack>0) { postFix(XX);XX=pop();}
if(XX.operation!="Empty")postFix(XX);
}
（７）第１レベルの構文解析
private void SA0()
{
numPolish=0; ptrStack=0 ; int i=0;bool Mode=true;
while(i<numToken)
{
if(Mode) { 演算対象モードのときの処理; }
else
{ 演算子モードのときの処理; }
i++;
}
popProcE();
}
（A）演算対象モードのときの処理
① 演算子の +, -, ++, --, ! がきたら単項演算子とみなして
演算子の処理を行う。
② 演算子の ( がきたら ( をプッシュする。
③ 名前ifがきたら予約語ifとみなし、
ifを出力ストリームに出力し、Blockをプッシュする。
以降は、if文における論理式とみなす。
④ 名前と( がきたら、関数呼び出しとみなす。
引数終り符号(ArgEnd)を出力ストリームに出力し、
関数名をプッシュする。
⑤ 演算子以外なら、出力ストリームに移動し、演算子モードとする。
⑥ 上記以外はエラー
C#によるプログラム例
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”){
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++; }
// 演算子としての
// 括弧
// if文
// 関数呼出し
else if(token[i].type!=“Delimiter”) {
// 演算対象
postFix(new TokenData(token[i].type,0,token[i].str)); Mode=false;}
else{ MessageBox.Show(“001 区切記号の位置の誤り”); break; }
（B) 演算子モード
① 次のモードを演算子対象モードとする。
② 各演算子に対して優先順位を付加して、演算子の処理を行う。
③ 名前 mod は、演算子として扱う。
④ カンマ(,)のとき、前述の popProcF の処理を行う。
⑤ 名前 then, else のとき予約語として扱う。
If文の処理でプッシュされているブロックまでをポップアップし、これらを
出力ストリーに出力し、Blockをプッシュしておく。
⑥ 名前 endif のとき予約語として扱う。
If文または then, else の処理でプッシュされているブロックまでをポップ
アップし、endif を出力ストリームに出力する。（Blockプッシュなし、⑤
と比較）
⑦上記以外のときエラー
C#によるプログラム例（その1）
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));
}
C#によるプログラム例（その2）
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));
}
else if(token[i].type=="Name" && token[i].str=="endif"){
popProcBlock(); postFix(new TokenData(token[i].str,0,token[i].str));
}
else{ MessageBox.Show(“002 名前の位置または演算子の誤り”); break;
}
（８）制御構造を含む構文解析
(A) 式解釈の準備
式の部分を逆ポーランド記法で解釈するための領域に移す処理
【例】
① If <式> then
② For(<式1>;<式2>;<式3>)
③ While <式>
④ Until <式>
以下の２種類がある
・単純に文の終りまで複写
・何らかの区切り記号／名前を識別して複写
【プログラム例１】単純なトークン複写
private void token複写(ref int i)
// 単純複写
{ numToken=0;
while(i<numTokenX) {token[numToken]=tokenX[i]; numToken++; i++;}
}
private void token複写Comma(ref int i) // レベル0のコンマまで
{ 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++;
}
}
【プログラム例２】 If ＜式＞ then
private void if論理式(ref int i)
{
numToken=0;
i++;
if(i<numTokenX)
{
while(i<numTokenX)
{
if(tokenX[i].type=="Name" && tokenX[i].str=="then")
{
i++;break; }
token[numToken++]=tokenX[i++];
}
}
}
【プログラム例３】 for ＜式1＞ ; ＜式2＞ ; ＜式1＞ ;
private void for初期化(ref int i)
// 式1
{ 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 現Polishのオブジェクト設定()
{
for(int k=0;k<numPolish;k++)
AllStatement[numStatement++]=Polish[k];
}
【プログラム例５】未解決ブロックアドレスのためのプッシュ
private void IfPush(int BP, int IfP,int ThenP)
{
// Ifブロック用
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; // while, repeat, for
numBreak[DoStackP]=0;
// ループからの抜け出しの数
}
(B) 構文解析の概要
先頭の文字列による判定
private void SA()
{ int i=0;
while(i<numTokenX)
{ if(tokenX[i].type=="Name" && tokenX[i].str=="if")
{ if文の処理; }
else if(tokenX[i].type=="Name" && tokenX[i].str=="else")
{ else句の準備; }
else if(tokenX[i].type=="Name" && tokenX[i].str=="endif")
{ endifの処理;}
・
・
・
i++;
}
}
If文の場合の解釈
Else や End ifの出現を待ってアドレス解決を行う必要がある
If <論理式> Then
の式取出し
演算子優先
順位解析
論理式
オブジェクト
Then句の処理
飛び先
Then
Then句のオブジェクト
Elseの処理
この位置を
スタックに
保存する
飛び先
Goto
Else句の処理
Else句のオブジェクト
End Ifの処理
Elseが
ない場合
Elseがある場合
分岐先
If文の処理例
if論理式(ref i);
// 論理式の設定
numPolish=0;
SA0();
// 式の優先順位の解析
numStatementNo++;
int oldP=numStatement;
SA設定("StNo",0,numStatementNo.ToString()); // 文番号（デバッグ用）
現Polishのオブジェクト設定();
// 式のオブジェクト
IfPush(oldP,numStatement,0);
// 未解決の飛び先挿入位置プッシュ
SA設定("Number",0, "");
// 式の判定
SA設定("then",0,"then");
if(i+1 < numTokenX) MessageBox.Show("thenの後に文は書けません");
通常のインタプリタではデバッガを用意しており、
文番号の表示を必要とするので,
ここでは、StNoというデバッグ用の文番号を出力している。
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の後に文は書けません");
endIf の処理例
numStatementNo++;
SA設定("StNo",0,numStatementNo.ToString());
int IP=IfStack[IfStackP].IfP;
if(AllStatement[IP].str== "") // Elseがない場合
AllStatement[IP].str=numStatement.ToString();
else
// Elseがあった場合
AllStatement[IfStack[IfStackP].ThenP].str=numStatement.ToString();
if(i+1 < numTokenX) MessageBox.Show("endifの後に文は書けません");
IfStackP--;

Download Report