言語処理工学Ａ 中間テスト  解答


１ 今、古い仕様のあるプログラミング言語Xのコンパイラがある。
このコンパイラは、計算機P6で稼働し、P6の機械語プログラムを出力する。た
だし、その出力されたプログラムの実行効率は低い。

今、Xの新しい言語仕様X’が決められたのを機会に、効率の良いP6の機械語プ
ログラムを出力するセルフコンパイラを作成したい。ただし、X’はXの拡張で、
Xの仕様は完全に含んでいる。

できる限り手で書く部分を容易にかつ少なくして、効率良く開発したい。


(1) 既存のコンパイラをT図式で示せ。ただし、効率の悪いプログラムは、＊
をつけて陽に示せ。

	X → P6*
          P6

(2)目的のコンパイラのT図式を書け。

	X’ → P6
	   P6

(3)手で書くコンパイラのT図式を書け。

	X’→ P6
           X

(4) 上記(3)から(1)を使って(2)が生成される過程をT図式で示せ。

               X’→ P6             X’→ P6
    X’→ P6      X        X'→ P6     P6
       X       X → P6*      P6*
                 P6




２ 加算 +、 乗算 * 、冪乗 ↑、括弧 ( )、そして数 i を含む式Eを生成する
文法Gが以下のように定められている。

	[G]

	E → E + E | E * E |  E ↑ E | ( E ) | i

常識的な演算の優先順位を持った構文解析結果を得るための、順位関係表を以
下のように作成した。番号の部分に順位の記号 <<、 >>、 ==、 空白( エラー)、
受理のいずれかを入れよ。

                  i, +, *, ↑, (, ), $

              i,     >> >> >>     >> >>
	      +, <<  >> << <<  << >> >>
	      *, <<  >> >> <<  << >> >>
	      ↑,<<  >> >> <<  << >> >>
	      (, <<  << << <<  << ==
	      ),     >>  >> >>    >> >>
	       $ <<  <<  << << <<   受理


                  i, +, *, ↑, (, ), $

              i,     1  >> >>     >> >>
	      +, <<  >> 2 <<   << >> >>
	      *, <<  >> 3  4   << >> >>
	      ↑,<<  >> >> 5   << >> >>
	      (, <<  << << <<  6  7
	      ),     >>  >> >> 8  >> >>
	       $ <<  <<  << << <<   受理

３ 前述２の文法Gと順位関係表を用いて

       i + i ↑ i ↑ i

を演算子順位構文解析法で解析する様子を表に示せ。表の形式は、

		右文型式		記号列		    ハンドル
  ステップ０   $i + i ↑ i ↑ i$   $<>+<>↑<>↑<>$     i
  ステップ１   $E + i ↑ i ↑ i$   $<<+<>↑<>↑<>$        i
   …

とする。


                右文型式                記号列              ハンドル
  ステップ０   $i + i ↑ i ↑ i$   $<>+<>↑<>↑<>$     i
  ステップ１   $E + i ↑ i ↑ i$   $<<+<>↑<>↑<>$        i
  ステップ2    $E + E ↑ i ↑ i$   $<<+<<↑<>↑<>$           i
  ステップ3    $E + E ↑ E ↑ i$   $<<+<<↑<<↑<>$              i
  ステップ4    $E + E ↑ E ↑ E$   $<<+<<↑<<↑>>$                E↑E
  ステップ5    $E + E ↑ E$        $<<+<<↑>>$                    E↑E
  ステップ6    $E + E$             $<<+>>$                        E+E
  ステップ7    $E$                 $$                             受理


４ 次の拡張文法Gにたいして、Follow集合と構文解析表を求めよ。

文法G
        (0) E'-> E
        (1) E -> E + i
        (2) E -> E * i
        (3) E -> i

また、i+i の構文解析の過程を示せ。

○Follow集合

Follow(E') ={$}
Follow(E) = {$,+,*}


○正準LR(0)集成
I0      E' -> .E
        E  -> .E + i
        E  -> .E * i
        E  -> .i

I1      E'  -> E.            I0/E
        E   -> E. + i
        E   -> E. * i

I2      E  -> i.             I0/i

I3      E  -> E +. i         I1/+

I4      E  -> E *. i         I1/*

I5      E  -> E + i.         I3/i

I6      E  -> E * i.         I4/i

○LR(0)オートマトン
              E   i   +   *
        I0   I1  I2  
        I1           I3   I4
        I2
        I3       I5
        I4       I6
        I5
        I6

○構文解析表
            action	     goto

	     i   +   *   $    E   
        I0  s2                1
        I1      s3  s4  acpt
        I2      r3  r3  r3
        I3  s5
        I4  s6
        I5      r1  r1  r1
        I6      r2  r2  r2

○構文解析過程


stack           input           action
                                initialize
0                i+i+i$
				shift 2
0i2               +i+i$
				shift 3
0i2+3		   i+i$
				shift 5
0i2+3i5		    +i$
				reduce 1,1
0E1		    +i$
				shift 3
0E1+3		     i$
				shift 5
0E1+3i5		      $
				reduce 1,1
0E1		      $
				accept