構文主導翻訳.

Presentation on theme: "構文主導翻訳."— Presentation transcript:

1 構文主導翻訳

2 構文主導翻訳 構文主導翻訳(syntax-directed translation)
各生成規則 A→α に｢意味動作｣(意味規則)と呼ぶプログラム p を対応させる：構文主導定義 A→α の還元の際： 対応する意味動作プログラムpも実行 各文法記号Xに翻訳属性を付加 意味動作は主に属性間の演算（属性評価） 意味動作： (中間)コードの生成，記号表の操作，誤り処理など (ここではLR構文解析との組み合わせで考える)

3 LR構文解析のaction表で示される動作
構文解析表のaction部分に示される「シフト」「還元」「受理」「誤り」の四つの動作 　　スタックトップの状態記号sm 　　　次の入力記号(先読み記号)aj もし action[sm,aj] == 「状態sn へシフト｣なら： ajとsnをプッシュする もし action[sm,aj] == ｢A→βで還元｣なら： )βの長さ(r)の２倍の記号をポップ )Aをプッシュ )sn=goto[Sm-r,A]をプッシュ (Sm-r :今プッシュしたAの左の状態記号) もし action[sm,aj] == ｢受理｣なら： 構文解析成功 もし action[sm,aj] == ｢誤り｣なら：構文誤り検出

4 LR構文解析のドライバ push(0); x=入力の先頭トークン; while(1)
if ( action[st,x] == shift 状態 j ) push(x); push(j); x=次のトークン; else if ( action[st,x] == reduce A→α) (αの長さ×2)回pop; tmp=st; push(A); push(goto[tmp,A]); else if (action[st,x] == accept) 入力は文法に合致すると認識; break; else 入力は文法に合致しないと認識; break; end while (注)stは常にスタックトップ値(状態番号)

5 LR構文解析のドライバ(状態のみをpush/pop)
push(0); x=入力の先頭トークン while(1) if ( action[st,x] == shift 状態 j ) push(j); x=次のトークン; else if ( action[st,x] == reduce A→α) (αの長さ)回pop; push(goto[st,A]); else if (action[st,x] == accept) 入力は文法に合致すると認識; break; else 入力は文法に合致しないと認識; break; end while (注)stは常にスタックトップ値(状態番号)

6 ドライバ：スタックを配列変数で実現 sp=0; s[sp]=0; x=入力の先頭トークン while(1)
if (action[s[sp],x]==shift 状態 j) s[sp+1]=j; sp=sp+1; x=次のトークン; else if (action[s[sp],x]==reduce A→α) sp=sp-(αの長さ); s[sp+1]=goto[s[sp],A]; sp=sp+1; else if (action[s[sp],x] == accept) 入力は文法に合致すると認識; break; else 入力は文法に合致しないと認識; break; end while

7 ドライバ：還元時に意味動作も実行 sp=0; s[sp]=0; x=入力の先頭トークン while(1)
if (action[s[sp],x]==shift 状態 j) s[sp+1]=j; sp=sp+1; x=次のトークン; else if (action[s[sp],x]==reduce A→α) sp=sp-(αの長さ); s[sp+1]=goto[s[sp],A]; sp=sp+1; A→αに対応する意味動作を実行; else if (action[s[sp],x] == accept) 入力は文法に合致すると認識; break; else 入力は文法に合致しないと認識; break; end while

8 ドライバ：還元時に意味動作も実行 sp=0; s[sp]=0; x=gettoken() while(1)
if (action[s[sp],x]==shift 状態 j) s[sp+1]=j; sp=sp+1; x=gettoken(); else if (action[s[sp],x]==reduce A→α) sp=sp-(αの長さ); s[sp+1]=goto[s[sp],A]; sp=sp+1; A→αに対応する意味動作を実行; else if (action[s[sp],x] == accept) 受理の意味動作を実行; break; else エラー対処の動作を実行; break; end while

9 LR構文解析のドライバでの属性評価の仕方
構文解析と同様にスタックを用いる 属性スタックas[ ]，スタックトップポインタasp 例)構文解析時に数式の値を評価する構文主導定義 (0)L → E { print as[asp] } (1)E → E + T { as[asp-2]=as[asp-2]+as[asp]; asp=asp-2 } (2)E → T { } (3)T → T * F { as[asp-2]=as[asp-2]×as[asp]; asp=asp-2 } (4)T → F { } (5)F → (E) { as[asp-2]=as[asp-1]; asp=asp-2 } (6)F → num { }

10 ドライバ：還元時に意味動作も実行 sp=0; s[sp]=0; x=gettoken() while(1)
if (action[s[sp],x]==shift 状態 j) s[sp+1]=j; sp=sp+1; x=gettoken(); else if (action[s[sp],x]==reduce A→α) sp=sp-(αの長さ); s[sp+1]=goto[s[sp],A]; sp=sp+1 A→αに対応する意味動作を実行; else if (action[s[sp],x] == accept) 受理の意味動作を実行; break; else エラー対処の動作を実行; break; end while

11 ドライバ：属性値を属性スタックに格納 sp=0; s[sp]=0; asp=0;as[asp]=0; x=gettoken()
while(1) if (action[s[sp],x]==shift 状態 j) s[sp+1]=j; sp=sp+1; as[asp+1]=x.lexval; asp=asp+1; x=gettoken(); else if (action[s[sp],x]==reduce A→α) sp=sp-(αの長さ); s[sp+1]=goto[s[sp],A]; sp=sp+1; A→αに対応する意味動作を実行; else if (action[s[sp],x] == accept) 受理の意味動作を実行; break; else エラー対処の動作を実行; break; end while gettoken()は認識したトークンxに属性x.lexvalを設定する シフト時に属性値を 属性スタックにプッシュ

12 属性スタックを用いた属性評価 構文スタック 属性スタック 入力 0 0 (3+2)*4$
構文スタック 属性スタック 入力 (3+2)*4$ 0( )*4$ - は未定義な属性値を示す 0(4n )*4$ F→n 0(4F )*4$ T→F 0(4T )*4$ E→T 0(4E )*4$ 0(4E )*4$ 0(4E8+6n )*4$ F→n 0(4E8+6F )*4$ T→F 0(4E8+6T )*4$ E→E+T 0(4E )*4$ 0(4E8) *4$ F→(E) 0F *4$ T→F 0T *4$ 0T2* $ 0T2*7n $ F→n 0T2*7F $ T→T*F 0T $ E→T 0E $ 受理(L→E) 注)構文スタックには わかりやすいように 文法記号も積んでいる as[asp-2]=as[asp-2]+as[asp]; asp=asp -2; as[asp-2]=as[asp-1]; asp=asp-2; as[asp-2]=as[asp-2]*as[asp]; asp=asp-2

13 式を評価する属性付き解析木 構文スタック 属性スタック 入力 0 0 (3+2)*4$ 0(4 0 - 3+2)*4$
構文スタック 属性スタック 入力 (3+2)*4$ 0( )*4$ 0(4n )*4$ 0(4F )*4$ 0(4T )*4$ 0(4E )*4$ 0(4E )*4$ 0(4E8+6n )*4$ 0(4E8+6F )*4$ 0(4E8+6T )*4$ 0(4E )*4$ 0(4E8) *4$ 0F *4$ 0T *4$ 0T2* $ 0T2*7n $ 0T2*7F $ 0T $ 0E $ 20 L 20 E $ 20 T 5 T * 5 F ( E ) 5 E 3 + T T 3 2 F 3 F 2 4 F

14 中間コード生成 ー 四つ組 中間言語の種類 四つ組(3番地コード) 後置コード 四つ組
コード形式：(演算子，オペランド1，オペランド2，結果) 　　　　　オペランド：変数，定数，中間結果を格納する一時名 　　　　　　結果：変数，一時名 例) x := (-y+z)*w/2 　　　　([-], y, ,t1) 　　　　(+, t1, z, t2) 　　　　(*, t2, w, t3) 　　　　(/, t3, 2, t4) 　　　　(:=, t4, ,x)

15 後置コード 後置コード(逆ポーランドコード) 後置記法に基づくコード 後置記法
オペランドの後に演算子を記述する( x+y は xy+) (1)Eが変数か定数： Eの後置記法はE (2)Eが｢E1 op E2｣： Eの後置記法はE1’E2’op 　　　　　　　　　　　 E1’とE2’はE1とE2の後置記法 (3)Eが｢op E1｣： Eの後置記法はE1’op 　　　　　 E1’はE1の後置記法 (4)Eが｢(E1)｣： Eの後置記法はE1‘ E1’はE1の後置記法 例) (-y+z)*w/ y[-]z+w*2/

16 後置記法 スタックを用いて後置記法の式の値を求める
後置記法の式を左から右へ見ながら次を行う (1)変数や定数がきたらその値をスタックにプッシュ (2)2項演算子に対して 　　2回ポップし値を取り出し 　　それらに対して演算を行い 　　結果をプッシュ (3)単項演算子に対して 　　1回ポップし値を取り出し 　　それに対し演算を行い 　　結果をプッシュ

17 後置記法による式の評価 例) (-3+6)*4/2の後置記法 3[-]6+4*2/ に対する評価 スタック 入力式 3[-]6+4*2/
スタック　入力式 3[-]6+4*2/ [-]6+4*2/ *2/ *2/ *2/ *2/ / / 6

18 後置コード 例) x := (-y+z)*w/2 右辺の後置コード：y[-]z+w*2/ (LOD, y) yの値をプッシュ
(OPR, [-]) 単項‐演算 (LOD, z) zの値をプッシュ (OPR, +) +演算 (LOD, w) wの値をプッシュ (OPR, *) *演算 (LIT, 2) 定数2をプッシュ (OPR, /) /演算 (STO, x) スタックトップの値をxにストア 後置コード LOD x　　変数 x の値をプッシュ STO x　　ポップし値をxにストア LIT 定数5をプッシュ OPR [-]　 単項‐演算 OPR 演算 OPR 演算 OPR * * 演算 OPR / / 演算

19 後置コード 後置コードは｢スタックマシン｣の機械コード
スタックマシン: 演算結果の一時記憶場所としてスタックを備える 演算はスタックに対して行われる(レジスタではなくて) 後置コードの特徴 レジスタ割当てが不要なのでコード生成が簡単 コードの並べ換えが困難→最適化に不向き 実行効率よりもコンパイラ作成の容易さやコンパイル･デバッグの能率に重点を置いた処理系向き

20 後置コードを生成するための意味動作 数式を評価する後置コードを生成するための意味動作 (0)L → E { L.code = E.code}
(1)E → E1 + T { E.code = E1.code || T.code || (OPR +) } (2)E → T { E.code = T.code} (3)T → T1 * F { T.code = T1 .code || F.code || (OPR *) } (4)T → F { T.code = F.code } (5)F → (E) { F.code = E.code } (6)F → num { F.code = (LIT num.lexval) } ||は文字列の連接を表す

21 式を評価する後置コード生成の属性付き解析木
L→E { L.c = E.c} E→E1+T { E.c = E1.c || T.c || (OPR +) } E→T { E.c = T.c} T→T1*F { T.c = T1 .c || F.c || (OPR *) } T→F { T.c = F.c } F→(E) { F.c = E.c } F→num { F.c = (LIT num.lexval) } L E $ T LIT 3 LIT 2 ORP + LIT 4 OPR * LIT 3 LIT 2 ORP + LIT 4 OPR * LIT 3 LIT 2 ORP + LIT 4 OPR * T * F LIT 3 LIT 2 ORP + LIT 3 LIT 2 ORP + LIT 3 LIT 2 ORP + ( E ) E LIT 3 + T T (3+2)*4の属性付解析木 LIT 2 LIT 3 F F F LIT 2 LIT 4 LIT 3 3.lexval=3 2.lexval=2 4.lexval=4

22 後置コードを生成するための意味動作 代入文の後置コードを生成するための意味動作 x := (-y+z)*w/2の属性付解析木は？
S → i := E E → T E → +T E → -T E → E1 + T E → E1 - T T → F T → T1 * F T → T1 / F F → (E) F → num F → i { S.code = E.code || (STO i) } { E.code = T.code} { E.code = T.code || (OPR [-]) } { E.code = E1.code || T.code || (OPR +) } { E.code = E1.code || T.code || (OPR -) } { T.code = F.code } { T.code = T1 .code || F.code || (OPR *) } { T.code = T1 .code || F.code || (OPR /) } { F.code = E.code } { F.code = (LIT num.lexval) } { F.code = (LOD i) }

23 式を評価する後置コード生成の属性付き解析木
S LOD y OPR[-] LOD z OPR + LOD w OPR * LIT 2 OPR / STO x LOD y OPR[-] LOD z OPR + LOD w OPR * x := (-y+z)*w/2の 属性付解析木 $ x E *= T LOD y OPR[-] LOD z OPR + LOD w OPR * LIT 2 OPR / T / T * LOD y OPR[-] LOD z OPR + F ( E ) E LOD y OPR[-] + T T F F F F LOD y LOD z LOD w LIT w - y z w 2

24 制御コードを生成するための意味動作 条件分岐文(if-then)を生成するための意味規則 S→if C then S1
if C then S1のコード Cのコード JPC lbl S1のコード lbl: ラベルと分岐の後置コード LAB a ラベルa JMP a ラベルaへ分岐 JPC a ラベルaへ条件分岐 ラベル生成関数：newlabel()

25 制御コードを生成するための意味動作 条件分岐文(if-then)を生成するための意味規則 S→if C then S1 { lbl = newlabel(); S.code = C.code || (JPC, lbl) || (S1.code) || (LAB, lbl) } if C then S1のコード Cのコード JPC lbl S1のコード lbl: ラベルと分岐の後置コード LAB a ラベルa JMP a ラベルaへ分岐 JPC a ラベルaへ条件分岐 ラベル生成関数：newlabel()

26 制御コードを生成するための意味動作 条件分岐文(if-then-else)を生成するための意味規則 S→if C then S1 else S2 if C then S1else S2のコード 　　　Cのコード JPC lbl1 　　　S1のコード 　　　JMP lbl2 lbl1: S2のコード lbl2:

27 制御コードを生成するための意味動作 条件分岐文(if-then-else)を生成するための意味規則 S→if C then S1 else S2 { lbl1 = newlabel(); lbl2 = newlabel(); S.code = C.code || (JPC, lbl1) || S1.code || (JMP, lbl2) || (LAB, lbl1) || S2.code || (LAB, lbl2) } if C then S1else S2のコード 　　　Cのコード JPC lbl1 　　　S1のコード 　　　JMP lbl2 lbl1: S2のコード lbl2:

28 制御コードを生成するための意味動作 繰り返し文(while)を生成するための意味規則 S→while C do S1
while C do S1のコード lbl1:Cのコード JPC lbl2 　　　S1のコード 　　　JMP lbl1 lbl2:

29 制御コードを生成するための意味動作 繰り返し文(while)を生成するための意味規則 S→while C do S1 { lbl1 = newlabel(); lbl2 = newlabel(); S.code = (LAB, lbl1) || C.code || (JPC, lbl2) || S1.code || (JMP, lbl1) || (LAB, lbl2) } while C do S1のコード lbl1:Cのコード JPC lbl2 　　　S1のコード 　　　JMP lbl1 lbl2:

30 構文解析プログラム例：電卓プログラム 入力された数式に対し，文法Cに従って構文解析し，その式の値を求める構文主導翻訳プログラム 文法C
C=(N,T,P,E) N={E,T,F} T={+,*,(,),num} P={ (0)L → E { print as[asp] } (1)E → E + T { as[asp-2]=as[asp-2] + as[asp]; asp=asp-2 } (2)E → T { } (3)T → T * F { as[asp-2]=as[asp-2]×as[asp]; asp=asp-2 } (4)T → F { } (5)F → (E) { as[asp-2]=as[asp-1]; asp=asp-2 } (6)F → num { } }

31 電卓プログラム アルファベット：Σ= {0,1, ... ,9, +, *, ( , ) , 空白,タブ,改行} 字句の正規定義：
ws → delim delim* (構文解析においては読捨て) num → digit digit* → + * → * ( → ( ) → ) delim → 空白｜タブ｜改行 digit → 0 | 1 | ... | 9 numに対してはその数値(num.lexval)を字句解析器が求めるものとする

32 電卓プログラム 構文解析表

33 ドライバ：属性値を属性スタックに格納 sp=0; s[sp]=0; asp=0;as[asp]=0; x=gettoken()
while(1) if (action[s[sp],x]==shift 状態 j) s[sp+1]=j; sp=sp+1; as[asp+1]=x.lexval; asp=asp+1; x=gettoken(); else if (action[s[sp],x]==reduce A→α) sp=sp-(αの長さ); s[sp+1]=goto[s[sp],A]; sp=sp+1; A→αに対応する意味動作を実行; else if (action[s[sp],x] == accept) 受理の意味動作を実行; break; else エラー対処の動作を実行; break; end while

34 電卓プログラム 実行例 1+3*2$ Accepted: 7 4*(2+3)$ Accepted: 20 (2+3)(1+2)$
!Syntax Error! 4-3$ !Token Error!

35 全体 #include <stdio.h> #include <ctype.h> int c;
int gettoken(int *); int main() { struct sr {char s; int n;} ; struct sr pta[12][6]={ {{'s',5},{'e',0},{'e',0},{'s',4},{'e',0}, {'e',0}}, {{'s',0},{'s',6},{'e',0},{'e',0},{'e',0}, {'a',0}}, {{'e',0},{'r',2},{'s',7},{'e',0},{'r',2}, {'r',2}}, {{'e',0},{'r',4},{'r',4},{'e',0},{'r',4}, {'r',4}}, {{'e',0},{'r',6},{'r',6},{'e',0},{'r',6}, {'r',6}}, {{'e',0},{'s',6},{'e',0},{'e',0},{'s',11},{'e',0}}, {{'e',0},{'r',1},{'s',7},{'e',0},{'r',1}, {'r',1}}, {{'e',0},{'r',3},{'r',3},{'e',0},{'r',3}, {'r',3}}, {{'e',0},{'r',5},{'r',5},{'e',0},{'r',5}, {'r',5}} }; int ptg[12][3]={ {1,2,3}, {0,0,0}, {8,2,3}, {0,9,3}, {0,0,10}, {0,0,0} struct {int lhs; int rhs;} gr[7]={{0,2},{0,3},{0,1},{1,3},{1,1},{2,3},{2,1}}; struct sr action; int token_id ,lval; int ps[100], psp=0, as[100], asp=0; ps[0] = 0; as[0] = 0; c = getchar(); token_id = gettoken(&lval); while (1) { if ( token_id == 100 ) token_id = gettoken(&lval); if ( token_id == 101 ) { printf("!Unexpected EOF! \n"); break; } else if ( token_id == 102 ) { printf("!Token Error! \n"); break; } action = pta[ps[psp]][token_id]; if ( action.s == 's' ) { ps[psp+1] = action.n; psp = psp +1; as[asp+1] = lval; asp = asp +1; token_id = gettoken(&lval); } else if ( action.s == 'r' ) { psp = psp - gr[action.n].rhs; ps[psp+1] = ptg[ps[psp]][gr[action.n].lhs]; psp = psp+1; switch ( action.n ){ case 1: as[asp-2] = as[asp-2]+as[asp]; asp = asp-2; break; case 3:as[asp-2] = as[asp-2]*as[asp]; asp = asp-2; break; case 5: as[asp-2] = as[asp-1]; asp = asp-2; else if ( action.s == 'a' ) { printf(" %d \n", as[asp]); break; } else { printf("!Syntax Error! \n"); break; } int gettoken(int *rval) { *rval = 0; if isspace(c) { c = getchar(); goto state1; } else if isdigit(c) { *rval = c-'0'; c = getchar(); goto state2; } else if ( c == '+' ){ c = getchar(); return(1); } else if ( c == '*' ){ c = getchar(); return(2); } else if ( c == '(' ) { c = getchar(); return(3); } else if ( c == ')' ) { c = getchar(); return(4); } else if ( c == '$' ){ c = getchar(); return(5); } else if ( c == EOF ) return(101); else return(102); state1: if isspace(c) { c = getchar(); goto state1; } else return(100); state2: if isdigit(c) { *rval = *rval*10+(c-'0'); c = getchar(); goto state2; } else return(0);

36 構文解析表

37 変数定義 構文解析表のaction 部分 #include <stdio.h> #include <ctype.h>
int c; int gettoken(int *); int main() { struct sr {char s; int n;} ; struct sr pta[12][6]={ {{'s',5},{'e',0},{'e',0},{'s',4},{'e',0}, {'e',0}}, {{'e',0},{'s',6},{'e',0},{'e',0},{'e',0}, {'a',0}}, {{'e',0},{'r',2},{'s',7},{'e',0},{'r',2}, {'r',2}}, {{'e',0},{'r',4},{'r',4},{'e',0},{'r',4}, {'r',4}}, {{'e',0},{'r',6},{'r',6},{'e',0},{'r',6}, {'r',6}}, {{'e',0},{'s',6},{'e',0},{'e',0},{'s',11},{'e',0}}, {{'e',0},{'r',1},{'s',7},{'e',0},{'r',1}, {'r',1}}, {{'e',0},{'r',3},{'r',3},{'e',0},{'r',3}, {'r',3}}, {{'e',0},{'r',5},{'r',5},{'e',0},{'r',5}, {'r',5}} }; 構文解析表のaction 部分

38 変数定義 構文解析表のgoto部分 生成規則の左辺(E,T,F)と右辺の長さの対応表 gettokenはtoken_idとlvalを返す
int ptg[12][3]={ {1,2,3}, {0,0,0}, {8,2,3}, {0,9,3}, {0,0,10}, {0,0,0} }; struct {int lhs; int rhs;} gr[7]={{0,2},{0,3},{0,1},{1,3},{1,1},{2,3},{2,1}}; struct sr action; int token_id ,lval; int ps[100], psp=0, as[100], asp=0; ps[0] = 0; as[0] = 0; c = getchar(); token_id = gettoken(&lval); 構文解析表のgoto部分 (0)L → E (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → num 生成規則の左辺(E,T,F)と右辺の長さの対応表 gettokenはtoken_idとlvalを返す

39 構文解析部分 ps[psp+1] = ptg[ps[psp]][gr[action.n].lhs]; 空白トークンの読み飛ばし エラー対処
while (1) { if ( token_id == 100 ) token_id = gettoken(&lval); if ( token_id == 101 ) { printf("!Unexpected EOF! \n"); break; } else if ( token_id == 102 ){ printf("!Token Error! \n"); break; } action = pta[ps[psp]][token_id]; if ( action.s == 's' ) { ps[psp+1] = action.n; psp = psp + 1; as[asp+1] = lval; asp = asp +1; token_id = gettoken(&lval); } else if ( action.s == 'r' ) { psp = psp - gr[action.n].rhs; ps[psp+1] = ptg[ps[psp]][gr[action.n].lhs]; psp = psp+1; switch ( action.n ){ case 1: as[asp-2] = as[asp-2]+as[asp]; asp = asp-2; break; case 3: as[asp-2] = as[asp-2]*as[asp]; asp = asp-2; break; case 5: as[asp-2] = as[asp-1]; asp = asp-2; else if ( action.s == 'a' ) { printf(" %d \n", as[asp]); break; } else { printf("!Syntax Error! \n"); break; } }/* end while */ }/* end main */ エラー対処 action.nは生成規則番号 (0)L → E (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → num ps[psp+1] = ptg[ps[psp]][gr[action.n].lhs];

40 字句解析部分 int gettoken(int *rval) { *rval = 0;
if isspace(c) { c = getchar(); goto state1; } else if isdigit(c) { *rval = c-'0'; c = getchar(); goto state2; } else if ( c == '+' ) { c = getchar(); return(1); } else if ( c == '*' ) { c = getchar(); return(2); } else if ( c == '(' ) { c = getchar(); return(3); } else if ( c == ')' ) { c = getchar(); return(4); } else if ( c == '$' ) { c = getchar(); return(5); } else if ( c == EOF ) return(101); else return(102); state1: if isspace(c) { c = getchar(); goto state1; } else return(100); state2: if isdigit(c) { *rval = *rval*10+(c-'0'); c = getchar(); goto state2; } else return(0); }

41 本スライドの著作権について 本スライドは，電気通信大学大学院情報システム学研究科で，平成17年度前期に開講される｢計算機システム基礎(本多担当分)」の講義資料ならびに本講義受講生の講義復習用資料として本多弘樹によって制作されたもので，その著作権は本多弘樹に属します． 本講義の受講生が，本講義の復習に際し，本スライド閲覧するために本スライドをコピーすることを許可します． 上記以外の目的のために，本スライドを閲覧・コピー・改変・配布することを禁じます．