責任編集: (inoue@ist.osaka-u.ac.jp)


  言語処理工学A 中間テスト           2001年12月6日 井上克郎

ノート、教科書、持ち込み禁止

解答用紙の1ページ目に1番の解答、2ページ目に2番の解答(以下同様)を書くこと
違う場所に書いたら0点。


(1) 今、Cで書かれたPASCALからCへのトランスレータがある。これと、Cから機
械語X86に変換するコンパイラを用いて、X86上で、PASCALプログラムWを実行させる
までの過程をT図式で書け。



  Pascal ----> C                       Pascal ---->  C
            |                                     |
            C         C ----->  X86              X86
                          |
                         X86


   W                            W                          W
   |                            |                          |
 Pascal    Pascal  --->  C      C       C  ---->  X86     X86
                    |                       |
                   X86                      X86


(2) 次の文法Gをまず左くくりだしし、それの左再帰性を除去した文法G'を作
れ。また、G'の各非終端記号のFIRST集合を求めよ。


G:     E →  E+T | E−T | T
    T →  T÷F | T×F | F
    F → i

答

くくりだし

     E → EE’  |   T
    E' → +T  | −T
    T → TT’ |   F
    T' → ÷F  |×F
    F   → i

左再帰除去G’
    E  → TE''
        E''→ E' E''|ε
    E' →  +T | −T
    T → FT''
        T''→  T' T''|ε
    T’→ ÷F | ×F
    F  → i

FIRST(E) = { i }
FIRST(E’)= {+,-}
FIRST(E’’) = {+, -, ε}
FIRST(T) = { i }
FIRST(T’) = {÷, ×}
FIRST(T'') ={÷,×, ε}
FIRST(F) = { i }

(3) 加算 +、 乗算 * 、冪乗 ↑、括弧 ( )、そして数 i を含む文法 

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

を以下の演算子順位表に基づいて構文解析を行なう。
   
                | i   +  *  ↑  (  )  $
              -------------------------
              i |     >> >> >>     >> >>
              + | <<  >> << <<  << >> >>
              * | <<  >> >> <<  << >> >>
              ↑| <<  >> >> <<  << >> >>
              ( | <<  << << <<  << ==
              ) |     >>  >> >>    >> >>
              $ | <<  <<  << << <<   受理

今、   i * (i ↑ i )↑i
を解析する様子を、右文型式、記号列、ハンドルの組を各ステップごとまとめ、
分かるように表せ。


          右文型式                記号列                    ハンドル
0   $ i * (i ↑ i )↑i$   $<>*<<(<>↑<>)>>↑<>$     i
1   $ 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)
6   $ E * E↑E$           $<<*<<↑>>$                          E↑E
7   $ E * E$              $<<*>>$                              E*E
8   $ E$                  $$                                   受理


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

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

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

○Follow集合

Follow(E') ={$}
Follow(E) = {$}


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

I1      E'  -> E.            I0/E

I2      E  -> i.+E           I0/i, I3/i, I4/i
	E  -> i.*E
	E  -> i.

I3      E  -> i+.E           I2/+
	E  -> .i+E
	E  -> .i*E
	E  -> .i

I4      E  -> i *.E          I2/*
	E  -> .i+E
	E  -> .i*E
	E  -> .i

I5      E  -> i + E.         I3/E

I6      E  -> i * E.         I4/E

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



○構文解析表
            action           goto

             i   +   *   $    E   
        I0  s2                1
        I1               r0
        I2      s3  s4   r3
        I3  s2		      5
        I4  s2                6
        I5               r1
        I6               r2

○構文解析過程


stack           input           action
                                initialize
0                i+i*i$
                                shift 2
0i2               +i*i$
                                shift 3
0i2+3              i*i$
                                shift 2
0i2+3i2             *i$
                                shift 4
0i2+3i2*4            i$
                                shift 2
0i2+3i2*4i2           $
                                reduce 3
0i2+3i2*4E6           $
                                reduce 2
0i2+3E5               $
				reduce 1
0E1                   $
				reduce 0
0E'                             accept