解答例

言語処理工学中間試験

			2004年11月26日

ノート、教科書持ち込みなし。

問題１は、解答用紙の1枚目、２は、2、3枚目、３は4枚目に書く事。そ
れ以外の部分に書いても得点にしない。

１ T図を用いて以下の作業の様子を表せ。

(1) Cで書かれたプログラムfをX86計算機で稼働するCコンパイラでコンパイ
    ルしてX86計算機のオブジェクトを生成する。

   F              F
   C   C -> X86  X86
         X86

(2) 皆さんが演習で行なっているPascalコンパイラの作成過程と、それを用い
    てPascalプログラムGのX86 計算機のオブジェクトへの変換。ただしCASL
    プログラムは、X86計算機のオブジェクトへのX86計算機で動くCASLコンパ
    イラがあるものとする。

  PAS -> CASL        PAS ->  CASL
      C    C  -> X86     X86
              X86

   G                G                 G
  PAS  PAS -> CASL CASL  CASL -> X86 X86
          X86                X86


２ 次の拡張文法Gにたいして、各非終端記号のFollow集合と構文解析表を求
めよ。

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

また、i+ (i+i) の構文解析の過程および得られた構文木を示せ。

  [0] E' ->  .E
      E	 ->  .E+T
      E	 ->  .T
      T	 ->  .(E)
      T  ->  .i

  [1]  [0]/E
      E' ->  E.
      E	 ->  E.+T

  [2]  [0]/T  [3]/T
      E -> T.

  [3]  [0]/(  [3]/(  [5]/(
      T -> (.E)
      E -> .E +T
      E -> .T
      T -> .(E)
      T -> .i

  [4]  [0]/i  [3]/i  [5]/i
      T -> i.

  [5]  [1]/+  [6]/+
      E -> E+.T
      T -> .(E)
      T ->.i

  [6]  [3]/E
      T -> (E.)
      E -> E.+T

  [7]  [5]/T
      E -> E+T.

  [8]   [6]/)
      T  -> (E).


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

Automaton

     E'    E     T     +     (     )    i
0          1     2           3          4
1                      5
2
3          6     2           3          4
4
5                7           3          4
6                      5           8
7
8


Table

    +     (     )     i     $     E     T 
0         S3          S4          1     2     
1   S5                      A
2   R2          R2          R2 
3         S3          S4          6     2
4   R4          R4          R4
5         S3          S4                7          
6   S5          S8                       
7   R1          R1          R1
8   R3          R3          R3


３ 減法 -、 除法 / 、冪乗 ↑、括弧 ( )、そして数 i を含む式Eを生成する
文法Gが以下のように定められている。

	[G]

	E → E - E | E / E |  E ↑ E | ( E ) | i

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

                  i, -, /, ↑, (, ), $

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


                  i, -, /, ↑, (, ), $

              i,     >> >> >>     >> >>
	      -, <<  >> << <<  << >> >>
	      /, <<  >> >> <<  << >> >>
	      ↑,<<  >> >> <<  << >> >>
	      (, <<  << << <<  << ==
	      ),     >>  >> >>    >> >>
	       $ <<  <<  << << <<   受理

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

       i ↑( i / i )

を演算子順位構文解析法で解析する様子の概略を示せ。


   解答略

以上