４．６ 演算子優先順位解析 （１）演算子（Operation）と演算対象(Operand)

Presentation on theme: "４．６ 演算子優先順位解析 （１）演算子（Operation）と演算対象(Operand)"— Presentation transcript:

1 ４．６ 演算子優先順位解析 （１）演算子（Operation）と演算対象(Operand)
以下、逆ポーランド記法による演算子優先順位解析について述べる。 （従来言語では伝統的に用いられている手法） ① すべて2項演算子とすると 　　　　　　　　＜演算対象＞＜演算子＞＜演算対象＞ の順序となる。 ② 単項演算子を例外処理として扱う。 　　（前置演算子と後置演算子がある） ③ 単項演算子の例 　　　　符号としての＋，－（加算、減算の＋，－は2項演算子） 　　論理演算子のNot（C言語の !） 　　　　C言語の＋＋，－－, など ④ 後置演算子と2項演算子は明示的に識別できるものでなくてはならない（重複した文字列の演算子があってはならない。前置演算子は2項演算子と同一のものがあってもよい）

2 （2）2項演算子と単項演算子解釈の状態遷移 演算対象モードと演算子モードの2状態を持つものとする。 S 演算対象モード 演算子モード
演算子 （ 演算子としての‘(’を含む） （前置演算子とみなす） 後置演算子 （ 演算子としての‘) ’ , ‘, ’を含む） ２項演算子 S 演算対象モード 演算子モード 演算対象 （名前、定数など） ‘(‘　 終了 終了 （“＜関数名＞(“とみなす） エラー終了 正常終了 【注】 ‘, ’は、 ①最も優先順位の低い演算子とみなす方法（ただし何も演算しない） 　 ②式の区切りとみなす方法 　　　の二通りがある。

3 （３）スタックを用いて逆ポーランド記法への変換
① 演算対象は、逆ポーランドストリームに出力。 ② 演算子は、スタック上の演算子の優先順位と比較 スタック上の演算子の優先順位が高いか等しければポップし、 　　ポップした演算子を逆ポーランドストリームに出力 　　現演算子をプッシュ ③　‘(’は、スタック上にプッシュ。（”<関数名>(“の形式の括弧と式内の括弧の区別をつける必要がある） ④　‘)’は、スタック上の‘(’までをポップし、ポップした演算子を逆ポーランドストリームに出力（ 式から括弧が消える）。 ④　‘,’は、スタック上の‘(’直前までポップし（ ‘(’ はスタック上に残る）、 　　ポップした演算子を逆ポーランドストリームに出力（式から‘,’が消える）。

4 A A+B*(C/D-E) 逆ポーランド記法への変換例(1) 演算対象 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 スタック

5 + A +B*(C/D-E) 逆ポーランド記法への変換例(２) 演算子 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 スタック

6 B A B*(C/D-E) + 逆ポーランド記法への変換例(３) 演算対象 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 + スタック

7 * AB *(C/D-E) + 逆ポーランド記法への変換例(４) 演算子（優先順位が高い） 入力ストリーム 出力ストリーム
演算子の優先順位例 () 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 + スタック

8 ( AB (C/D-E) * + 逆ポーランド記法への変換例(５) 前括弧 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 * + スタック

9 C AB C/D-E) ( * + 逆ポーランド記法への変換例(６) 演算対象 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 ( * + スタック

10 / ABC /D-E) ( * + 逆ポーランド記法への変換例(７) 演算子 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 ( * + スタック

11 D ABC D-E) / ( * + 逆ポーランド記法への変換例(８) 演算対象 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 / ( * + スタック

12 ①/ ② - ABCD -E) / ( * + 逆ポーランド記法への変換例(９) 演算子（優先順位が低い） ①スタックをポップ
入力ストリーム 出力ストリーム ①/ ② - ABCD -E) 演算子の優先順位例 () 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 ①スタックをポップ ②現演算子プッシュ / ( * + スタック

13 E ABCD/ E) - ( * + 逆ポーランド記法への変換例(１０) 演算対象 入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 - ( * + スタック

14 - ABCD/E ) ) - ( * + 逆ポーランド記法への変換例(１１) (までをポップ 入力ストリーム 出力ストリーム
演算子の優先順位例 () 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 - ( * + スタック

15 * + 終了 ABCD/E- * + 逆ポーランド記法への変換例(１２) スタックすべてをポップ 入力ストリーム 出力ストリーム
演算子の優先順位例 () 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10 * + スタック

16 ABCD/E-*+ 比較 A+B*(C/D-E) 逆ポーランド記法への変換例(1３) 元の入力ストリーム 出力ストリーム 演算子の優先順位例
() 1000(引数用を含む） ^ +,- 800(単項演算子） *, /, % 600 +,- 500(2項演算子） ==,>,… 400(比較演算子) ! 300(Not) |, & 200(論理演算子） = 100 コンマ(,) 10

17 （４）逆ポーランド記法を元に戻す① 逆ポーランド記法 A ABCD/E-*+ スタック

18 逆ポーランド記法を元に戻す② 逆ポーランド記法 B BCD/E-*+ A スタック

19 逆ポーランド記法を元に戻す③ 逆ポーランド記法 C CD/E-*+ B A スタック

20 逆ポーランド記法を元に戻す④ 逆ポーランド記法 D D/E-*+ C B A スタック

21 逆ポーランド記法を元に戻す⑤ 逆ポーランド記法 / /E-*+ D C B A スタック

22 逆ポーランド記法を元に戻す⑥ 逆ポーランド記法 E E-*+ (C/D) B A スタック

23 逆ポーランド記法の実行⑦ 逆ポーランド記法 - -*+ E (C/D) B A スタック

24 逆ポーランド記法の実行⑧ 逆ポーランド記法 * *+ ((C/D)-E) B A スタック

25 逆ポーランド記法の実行⑨ 逆ポーランド記法 + + (B*((C/D)-E)) A スタック

26 逆ポーランド記法の実行⑩ 逆ポーランド記法 (A+(B*((C/D)-E))) スタック

27 （５）制御文の取扱い① go to L2 上記表現は、 　　　　⇒L2 次の実行アドレスをL2ラベルの値にする単項演算とみなす。

28 If＜式＞goto L2 制御文の取扱い② 上記表現は、 ＜式＞⇒L2 式が成立すれば、次の実行アドレスをL2ラベルの値に
式が成立しなければ、次の実行アドレスは変えない ような２項演算として捉える。

29 If＜式＞Then ＜文１＞Else ＜文２＞ 制御文の取扱い③ ＜式＞Then Lelse ＜文１＞ Goto Lend Lelse
上記表現は、 　　　　＜式＞Then Lelse (Thenを２項演算子、 LeはElse句のラベル） 式が成立しなければ、 　　次の実行アドレスをLeラベルの値に、 式が成立すれば、 　　次の実行アドレスは変えない ような２項演算とみなす。 （If<式>goto と逆であることに注意） ＜式＞Then Lelse ＜文１＞ Goto Lend Lelse ＜文２＞ Lend

30 While＜式＞ ＜文＞ 制御文の取扱い④ Lstart ＜式＞Then Lend ＜文＞ Goto Lstart Lend
If＜式＞Thenと同様 Lstart ＜式＞Then Lend ＜文＞ Goto Lstart Lend

31 （６）逆ポーランド記法への変換のための基本処理
【基本的な処理】 ① スタックへのプッシュ ② スタックからのポップアップ ③ 出力ストリームへの出力 【解析用処理】 ④　優先順位を考慮した現演算子のプッシュ（①、②、③の組合せ） ⑤　関数呼び出しのための引数のポップアップ ⑥　‘,’演算子のための引数のポップアップ ⑦ ifブロックやWhileブロックのためのポップアップ ⑧　１文最後のポップアップ

32 (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++;

33 (ｂ)解析用（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); }

34 解析用処理（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(); }

35 解析用処理（C#での表現）(その３) ⑥ コンマのときの処理（,） 関数呼出しの際の引数の区切り
⑥ コンマのときの処理（,）　　関数呼出しの際の引数の区切り public void popProcF() { TokenData XX = pop(); while(ptrStack>=0) if(XX.operation=="Func"){push(XX); break;} postFix(XX); XX=pop(); }

36 解析用処理（C#での表現）(その４) ⑦ ブロックのときのポップアップ （Ifブロック，Whileブロック）
public void popProcBlock() { TokenData XX = pop(); while(ptrStack>=0) if(XX.operation=="Block")break; postFix(XX); XX=pop(); }

37 解析用処理（C#での表現）(その５) ⑧ 文の最後のポップアップ処理 public void popProcE() {
TokenData XX; XX=pop(); while(ptrStack>0) { postFix(XX);XX=pop();} if(XX.operation!="Empty")postFix(XX); }

38 （７）第１レベルの構文解析 private void SA0() {
numPolish=0; ptrStack=0 ; int i=0;bool Mode=true; while(i<numToken) if(Mode) { 演算対象モードのときの処理; } else { 演算子モードのときの処理; } i++; } popProcE();

39 （A）演算対象モードのときの処理 ① 演算子の +, -, ++, --, ! がきたら単項演算子とみなして 演算子の処理を行う。
① 演算子の　+, -, ++, --, ! がきたら単項演算子とみなして 演算子の処理を行う。 ② 演算子の ( がきたら ( をプッシュする。 ③ 名前ifがきたら予約語ifとみなし、 ifを出力ストリームに出力し、Blockをプッシュする。 　 以降は、if文における論理式とみなす。 ④ 名前と( がきたら、関数呼び出しとみなす。 引数終り符号(ArgEnd)を出力ストリームに出力し、 関数名をプッシュする。 ⑤ 演算子以外なら、出力ストリームに移動し、演算子モードとする。 ⑥ 上記以外はエラー

40 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=="--")) 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; }

41 （B) 演算子モード ① 次のモードを演算子対象モードとする。 ② 各演算子に対して優先順位を付加して、演算子の処理を行う。
③ 名前 mod は、演算子として扱う。 ④ カンマ(,)のとき、前述の popProcF の処理を行う。 ⑤ 名前 then, else のとき予約語として扱う。 If文の処理でプッシュされているブロックまでをポップアップし、これらを出力ストリー に出力し、Blockをプッシュしておく。 ⑥ 名前 endif のとき予約語として扱う。 If文または then, else の処理でプッシュされているブロックまでをポップアップし、endif を出力ストリームに出力する。（Blockプッシュなし、⑤と比較） ⑦上記以外のときエラー

42 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=="-=")) else if(token[i].type=="Delimiter" && (token[i].str=="*=" || token[i].str=="/=")) else if(token[i].type=="Delimiter" && 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)); (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)); }

43 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") 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"){ else{ MessageBox.Show(“002 名前の位置または演算子の誤り”); break;

44 （８）制御構造を含む構文解析 (A) 式解釈の準備
式の部分を逆ポーランド記法で解釈するための領域に移す処理 【例】 ① If <式> then ② For(<式1>;<式2>;<式3>) ③ While <式> ④ Until <式> 以下の２種類がある ・単純に文の終りまで複写 ・何らかの区切り記号／名前を識別して複写

45 【プログラム例１】 単純なトークン複写 private void token複写(ref int i) // 単純複写
【プログラム例１】 単純なトークン複写 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++;

46 【プログラム例２】 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++]; }

47 【プログラム例３】 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++]; } } }

48 【プログラム例４】 解釈結果の設定 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];

49 【プログラム例５】 未解決ブロックアドレスのためのプッシュ
【プログラム例５】 未解決ブロックアドレスのためのプッシュ 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;　　　　 // ループからの抜け出しの数

50 (B) 構文解析の概要 private void SA() { int i=0; while(i<numTokenX)
先頭の文字列による判定 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++; 　 } }

51 If文の場合の解釈 If <論理式> Then の式取出し 演算子優先 順位解析 論理式 オブジェクト Then句の処理 飛び先
Else や End ifの出現を待ってアドレス解決を行う必要がある If <論理式> Then の式取出し 演算子優先 順位解析 論理式 オブジェクト Then句の処理 飛び先 Then この位置を スタックに 保存する Elseの処理 Then句のオブジェクト 飛び先 Goto Else句の処理 Else句のオブジェクト 分岐先 Elseが ない場合 End Ifの処理 Elseがある場合

52 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というデバッグ用の文番号を出力している。

53 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の後に文は書けません");

54 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--;