Presentation is loading. Please wait.

Presentation is loading. Please wait.

構文解析(2).

Similar presentations


Presentation on theme: "構文解析(2)."— Presentation transcript:

1 構文解析(2)

2 スタックを使ったシフト還元構文解析 解析木の作成動作をコンピュータ上で実現するメカニズムとしてスタックを利用 シフト還元構文解析
入力記号をひとつ先頭(左端)から読み それをスタックに移動(シフト)したり スタック中の文法記号列の還元をしたりして 入力記号列に対する解析木(と等価なものを)をスタック上に生成していく 最右導出を逆にたどっていること等価となる

3 シフト還元構文解析の実現 スタックを用いたシフト還元構文解析の実現 入力記号をスタックにシフトしながら下記動作を行う (スタックの底と入力記号末尾に$をあらかじめ追加) 還元動作:スタックトップからの文法記号列(「ハンドル」)が,ある生成規則の右辺に一致した場合 > その記号列をポップし > その生成規則の左辺をプッシュする シフト動作:還元できない場合 > 次の入力記号をスタックにシフト(プッシュ)する 受理:スタックに$と開始記号だけを含み,入力記号の先頭が$となれば構文解析は成功

4 シフト還元構文解析の実現 ちゃんと開始記号に還元するためにはハンドルを適切な順序で還元していかなくてはならない この件は後程...
まず,シフト還元構文解析の大枠の実現方法を考える

5 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $ abbcde$ S→aABe A→Abc A→b B→d

6 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $ abbcde$ シフト S→aABe A→Abc A→b B→d

7 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $a bbcde$ S→aABe A→Abc A→b B→d

8 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $a bbcde$ シフト S→aABe A→Abc A→b B→d

9 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $ab bcde$ S→aABe A→Abc A→b B→d

10 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $ab bcde$ 還元A→b(bをpop,Aをpush) S→aABe A→Abc A→b B→d

11 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aA bcde$ S→aABe A→Abc A→b B→d

12 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aA bcde$ シフト S→aABe A→Abc A→b B→d

13 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAb cde$ S→aABe A→Abc A→b B→d

14 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAb cde$ シフト (bを還元しないことに注意!) S→aABe A→Abc A→b B→d

15 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAbc de$ S→aABe A→Abc A→b B→d

16 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAbc de$ 還元A→Abc(Abcをpop,Aをpush) S→aABe A→Abc A→b B→d

17 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aA de$ S→aABe A→Abc A→b B→d

18 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aA de$ シフト S→aABe A→Abc A→b B→d

19 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAd e$ S→aABe A→Abc A→b B→d

20 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAd e$ 還元B→d S→aABe A→Abc A→b B→d

21 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAB e$ S→aABe A→Abc A→b B→d

22 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aAB e$ シフト S→aABe A→Abc A→b B→d

23 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aABe $ S→aABe A→Abc A→b B→d

24 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $aABe $ 還元 S→aABe(aABEをpop,Sをpush) S→aABe A→Abc A→b B→d

25 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $S $ S→aABe A→Abc A→b B→d

26 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $S $ 受理 S→aABe A→Abc A→b B→d

27 シフト還元構文解析の動作 例) 右の文法(生成規則)によるabbcdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 動作 $ abbcde$ シフト $a bbcde$ シフト $ab bcde$ 還元 A→b(bをpop,Aをpush) $aA bcde$ シフト $aAb cde$ シフト (bを還元しないことに注意!) $aAbc de$ 還元 A→Abc(Abcをpop,Aをpush) $aA de$ シフト $aAd e$ 還元 B→d $aAB e$ シフト $aABe $ 還元 S→aABe(aABEをpop,Sをpush) $S $ 受理 S→aABe A→Abc A→b B→d

28 シフト還元構文解析の動作 例) 右の文法(生成規則)によるab1b2cdeの構文解析 S→aABe A→Abc A→b B→d
スタック 入力 $ ab1b2cde$ $a b1b2cde$ $ab b2cde$ $aA b2cde$ $aAb cde$ $aAb2c de$ $aA de$ $aAd e$ $aAB e$ $aABe $ $S $ スタック上での動作は 解析木の生成と本質的 に同じもの S→aABe A→Abc A→b B→d S A A B a b1 b2 c d e

29 シフト還元構文解析の動作 クイズ 以下の文法G1に対し入力「(i1+i2)*i3」があった場合のシフト還元解析動作と解析木を示せ
スタック 入力 動作 $      (i1+i2)*i3$ G1 (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i

30 シフト還元構文解析の動作 スタック 入力 動作 $ (i1+i2)*i3$ $( i1+i2)*i3$ G1 $(i1 +i2)*i3$
スタック 入力 動作 $ (i1+i2)*i3$ $( i1+i2)*i3$ $(i i2)*i3$ $(F +i2)*i3$ $(T +i2)*i3$ $(E +i2)*i3$ $(E i2)*i3$ $(E+i )*i3$ $(E+F )*i3$ $(E+T )*i3$ $(E )*i3$ $(E) *i3$ G1 (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i

31 シフト還元構文解析の動作 スタック 入力 動作 $(E) *i3$ $F *i3$ $T *i3$ $T* i3$ $T*i3 $
スタック 入力 動作 $(E) *i3$ $F *i3$ $T *i3$ $T* i3$ $T*i $ $T*F $ $T $ $E $ 受理 還元をするのか否かなど,どのような動作をするのかを決定する方法は,まだ示されていないことに注意 G1 (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i

32 LR構文解析 シフト還元構文解析の一手法: LR構文解析 ある時点でのシフトや還元に関してどのような動作をすべきかを次のように判断する
その時点までに読んだ記号や動作から,構文解析のどのような状態であるかを覚えておく 次の入力記号を先読みする 状態と先読みした次の入力記号から次に行うべき動作を決定する 行うべき動作は構文解析表としてまとめて表現する

33 LR構文解析のスタックと構文解析表 スタックには文法記号に加えて状態番号もしまう 構文解析表:actionとgotoの二つの表で構成される
シフトや還元の際の動作は,スタックトップの状態記号と次の入力記号(先読み記号) から構文解析表を参照し決定する 文法G1の構文解析表 G1 (0)S → E (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i

34 LR構文解析表 action表 sjはシフトして状態 j をプッシュ,rkはk番の生成規則で還元,accは受理,空白は誤りを表す
文法G1の構文解析表

35 LR構文解析表 goto表 還元の後の状態を表す 文法G1の構文解析表

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

37 LR構文解析の動作 例)以下の文法に対して入力「(i1+i2)*i3」があった場合のLR構文解析動作を示せ G1 (0)S → E
(1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i sjはシフトして状態 j をプッシュ, rkは k 番の生成規則で還元, accは受理,空白は誤りを表す

38 LR構文解析の動作 スタック 入力 動作 0 (i1+i2)*i3$ シフトし4をプッシュ 0(4 i1+i2)*i3$ シフトし5をプッシュ 0(4i i2)*i3$ (6) F→iで還元,3をプッシュ なんで3をプッシュ? ・スタック0(4i15でi15がFに  還元されれ0(4Fとなる ・4とFからgoto表をみて3                    をスタックにプッシュ 0(4F i2)*i3$ 以降を各自やってみよう

39 LR構文解析の動作 0 (i1+i2)*i3$ シフトし4をプッシュ 0(4 i1+i2)*i3$ シフトし5をプッシュ 0(4i i2)*i3$ (6) F→iで還元,3をプッシュ 0(4F i2)*i3$ (4) T→Fで還元,2をプッシュ 0(4T i2)*i3$ (2) E→Tで還元,8をプッシュ 0(4E i2)*i3$ シフトし6をプッシュ 0(4E i2)*i3$ シフトし5をプッシュ 0(4E8+6i )*i3$ (6) F→iで還元,3をプッシュ 0(4E8+6F )*i3$ (4) T→Fで還元,9をプッシュ 0(4E8+6T )*i3$ (1) E→E+Tで還元, をプッシュ 0(4E )*i3$ シフトし11をプッシュ 0(4E8) *i3$ (5) F→(E)で還元, をプッシュ

40 文法G1の構文解析表 sjはシフトして状態 j をプッシュ,rkは k 番の生成規則で還元,accは受理,空白は誤りを表す

41 LR構文解析の動作 0(4E8)11 i3$ (5) F→(E)で還元,3をプッシュ
0F3 *i3$ (4) T→Fで還元,2をプッシュ 0T2 *i3$ シフトし、7をプッシュ 0T2* i3$ シフトし、5をプッシュ 0T2*7i $ (6) F→iで還元,10をプッシュ 0T2*7F $ (3) T→T*Fで還元,2をプッシュ 0T $ (2) E→Tで還元,1をプッシュ 0E $ 受理

42 LR構文解析表 構文解析表はどのようにできているのか: LR(0)項とその閉包 正準LR(0)集成 FOLLOW集合

43 LR(0)項 生成規則のLR(0)項 (略して項) 生成規則の右辺の1ヶ所にドット「・」を挿入したもの 例 E → E + T のLR(0)項 E → ・E + T E → E・ + T E → E +・T E → E + T・

44 LR(0)項のclosure I中の全ての項はclosure(I)に含まれる
LR(0)項の集合Iの閉包closure(I): 次の規則によって作られる項の集合 I中の全ての項はclosure(I)に含まれる closure(I)中の項で,・の次が非終端記号となる項 A→α・Bβ に対し、Bを左辺とする生成規則B→γの右辺先頭に・をつけた項 B→・γ をclosure(I)に加える(A→α・Bβをカーネルと呼ぶ) 例) 文法G1でI={E→E+・T}とするとclosure(I)は E → E +・ T T → ・T * F T → ・F F → ・(E) F → ・i

45 LR(0)項のclosureと正準LR(0)集成
clousure(I)とは,「これから解析をする」という点においてI中の項と等価なものをすべて集めたもの 解析器が E→E+・T のドットの位置にいるとすると Tを解析する直前のT→・T * F や T→・F の位置にいるとも考えられる Fを解析する直前のF→・(E) や F→・i の位置にいるとも考えられる clousure(I)はLR構文解析器の状態(オートマトンの状態)に対応する 正準LR(0)集成(LR(0)項集合の正準集成) 構文解析器の全ての状態:LR(0)項の集合の集合

46 正準LR(0)集成 文法G1の正準LR(0)集成とその遷移をグラフで表現 I0:S → ・E E → ・E + T
T → ・T * F T → ・F F → ・(E) F → ・i i I1: E’ → E・ E → E・ + T I5: F → i・ ( i + ( F I4: F → (・E) E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i I6: E → E +・T T → ・T * F T → ・F F → ・(E) F → ・i I3 ( I4 T F i F I5 I2: E → T・ T → T・ * F I3: T → F・ T T * I9: E → E + T・ T → T・ * F E ( * I7: T → T *・ F F → ・(E) F → ・i + I4 I6 I8: F → (E・) E → E・ + T i I5 F ) I10: T → T * F・ I11: F → (E)・

47 正準LR(0)集成に還元動作を付け加えたもの
ある状態て還元が起きると前の状態に戻る E I0:S → ・E E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i i I6,I7 I1: E’ → E・ E → E・ + T I5: F → i・ ( i + ( F I4: F → (・E) E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i I6: E → E +・T T → ・T * F T → ・F F → ・(E) F → ・i I3 ( I6 I4 T F i F I5 I2: E → T・ T → T・ * F I3: T → F・ T T * I9: E → E + T・ T → T・ * F E ( * I7: T → T *・ F F → ・(E) F → ・i + I4 I6 I8: F → (E・) E → E・ + T i I5 F ) I10: T → T * F・ I11: F → (E)・

48 還元とFOLLOW集合 FOLLOW(X)集合 文形式中で非終端記号Xの直後に来うる終端記号の集合 FOLLOW集合はいつ還元するかを与える
文法G1 (0)S → E (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i FOLLOW(S)={ $ } FOLLOW(E)={ $, +, ) } FOLLOW(T)={ $, +, ), * } FOLLOW(F)={ $, +, ), * }

49 LR構文解析表 正準LR(0)集成の状態と状態間での遷移,還元を表でまとめたものが構文解析表 文法G1の構文解析表

50 正準LR(0)集成によるLR構文解析のメカニズム
(i1+i2)*i3 のLR構文解析で、 i1をEまで還元し,i2はTで 還元を止めるメカニズを 考えてみる E T T F E E T T F F F ( i i2 ) * i3

51 正準LR(0)集成によるLR構文解析のメカニズム
スタック 入力 動作 0 (i1+i2)*i3$ シフトし4をプッシュ 0(4 i1+i2)*i3$ シフトし5をプッシュ 0(4i i2)*i3$ (6) F→iで還元,3をプッシュ 0(4F i2)*i3$ (4) T→Fで還元,2をプッシュ 0(4T i2)*i3$ (2) E→Tで還元,8をプッシュ 0(4E i2)*i3$ シフトし6をプッシュ 0(4E i2)*i3$ シフトし5をプッシュ 0(4E8+6i )*i3$ (6) F→iで還元,3をプッシュ 0(4E8+6F )*i3$ (4) T→Fで還元,9をプッシュ 0(4E8+6T )*i3$ (1) E→E+Tで還元,8をプッシュ 0(4E )*i3$ シフトし11をプッシュ i1は状態4で, i2は状態6で読込んでいる 各状態ではこれから解析しようとすることが異なる

52 正準LR(0)集成を用いたLR構文解析のメカニズム
I0: S → ・E E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i 状態4ではこれからEを認識しようとしている I4: F → (・E) E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i I7: T → T *・ F F → ・(E) F → ・i I8: F → (E・) E → E・ + T I9: E → E + T・ T → T・ * F I5: F → i・ I10: T → T * F・ I1: E’ → E・ E → E・ + T I6: E → E +・T T → ・T * F T → ・F F → ・(E) F → ・i I11: F → (E)・ I2: E → T・ T → T・ * F I3: T → F・ 状態6ではこれからE+TのTを認識しようとしている

53 正準LR(0)集成を用いたLR構文解析のメカニズム
E I0:E’ → ・E E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i i I1: E’ → E・ E → E・ + T I5: F → i・ ( i + ( F I4: F → (・E) E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i I6: E → E +・T T → ・T * F T → ・F F → ・(E) F → ・i I3 ( +∈FLOLOW(E)をみて還元 I4 T F i F I5 I2: E → T・ T → T・ * F I3: T → F・ + T T * I9: E → E + T・ T → T・ * F E ( * I7: T → T *・ F F → ・(E) F → ・i + I4 I6 I8: F → (E・) E → E・ + T i I5 F ) I10: T → T * F・ I11: F → (E)・ FOLLOW(E)={ $, +, ) }

54 正準LR(0)集成を用いたLR構文解析のメカニズム
E I0:E’ → ・E E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i i I1: E’ → E・ E → E・ + T I5: F → i・ ( i + ( F I4: F → (・E) E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i I6: E → E +・T T → ・T * F T → ・F F → ・(E) F → ・i I3 ( I4 T F i F I5 I2: E → T・ T → T・ * F I3: T → F・ ) T T * I9: E → E + T・ T → T・ * F )∈FLOLOW(E)をみて還元 E ( * I7: T → T *・ F F → ・(E) F → ・i + I4 I6 I8: F → (E・) E → E・ + T i I5 F ) I10: T → T * F・ I11: F → (E)・ FOLLOW(E)={ $, +, ) }

55 正準LR(0)集成を用いたLR構文解析のメカニズム
E I0:E’ → ・E E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i i I1: E’ → E・ E → E・ + T I5: F → i・ ( i + ( F I4: F → (・E) E → ・E + T E → ・T T → ・T * F T → ・F F → ・(E) F → ・i I6: E → E +・T T → ・T * F T → ・F F → ・(E) F → ・i I3 ( I4 T F i F I5 I2: E → T・ T → T・ * F I3: T → F・ + ) T T * I9: E → E + T・ T → T・ * F E ( * I7: T → T *・ F F → ・(E) F → ・i + I4 I6 I8: F → (E・) E → E・ + T i I5 F ) I10: T → T * F・ I11: F → (E)・ FOLLOW(E)={ $, +, ) }

56 正準LR(0)集成を用いたLR構文解析のメカニズム
状態4でTを認識すると状態2へ遷移 状態2で+を見ての還元は(2)E → T (0)S → E (1)E → E + T (2)E → T (3)T → T * F (4)T → F (5)F → (E) (6)F → i 状態6でTを認識すると状態9へ遷移 状態9で)を見ての還元は(1)E → E + T

57 LR構文解析の種類 これまで説明してきた構文解析表は SLR(1) (Simple LR(1)) と呼ばれているものである。
このほかに以下の解析表がある (正準)LR(1) LALR(1) (LookAhead LR(1)) それぞれの構文解析表を用いる構文解析器をSLR(1), LR(1), LALR(1)構文解析器と呼ぶ。 これらは構文解析アルゴリズム(ドライバ)は同じ 扱える文法の範囲(還元の際の先読み集合の精密さ)がLR,LALR,SLRの順で狭まる。それぞれが扱える文法をSLR(1), LR(1), LALR(1)文法と呼ぶ 一方記号表のサイズは LR>LALR>SLRとなる。

58 構文主導翻訳 コンパイラのフェーズ 文字列(ソースプログラム) 字句解析 記号表管理 トークン列 構文解析 誤り処理 解析木 意味解析 属性付解析木 中間コード生成 中間コード 最適化 最適化中間コード コード生成 機械語コード

59 構文主導翻訳 意味解析 変数の型情報収集・型検査・有効範囲の解析・使用/宣言の対応け、演算子の型やオペランドの型検査 中間コード生成
一旦、機械コードより抽象度の高い中間言語を生成 構文主導翻訳:構文解析をしながら意味解析を行い、意味解析動作として中間コード生成を行う方式 コード最適化 コードの実行効率(時間効率)が良くなるようコードを改良 中間コードから機械語コードの生成 レジスタ割り当てやメモリ割り当て(とその最適化) 記号表管理と誤り処理

60 構文主導翻訳 以降は構文主導翻訳による(中間)コード生成ついてみていく 以下の仮定のコンパイラだとおもえばよい 型解析などはしない
コードの最適化しない 中間コード=機械コード

61 構文主導翻訳 コンパイラのフェーズ 文字列(ソースプログラム) 字句解析 記号表管理 トークン列 誤り処理 中間語=機械語コード
コンパイラのフェーズ 文字列(ソースプログラム) 字句解析 記号表管理 トークン列 誤り処理 中間語=機械語コード 構文主導翻訳

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


Download ppt "構文解析(2)."

Similar presentations


Ads by Google