演習問題 2の構文解析表の作り方

  R  →  Q R'                 	(1)
  R' →  ε | '|'  Q R'		(2)
  Q  →  P Q'			(3)
  Q' →  ε | P Q'		(4)
  P  →  O P'			(5)
  P' →  ε | '*' P'		(6)
  O  →  '(' R ')' | ALPHA 	(7)

1. まず、

     First(O) = { '(', ALPHA}
     First(P) = First(O)
     First(Q) = First(P)
   

   より、

     First(Q R') = First(Q) （First(Q)がεを含まないので）
                 = { '(', ALPHA}
   

   ゆえに下の構文解析表の Rの行の ^*1の欄を得る。

2. 次に R'の行について、明らかに

     First('|' Q R') = { '|' }
   

   だから^*2の欄を得る。 さらに、First(ε) = {ε}だから、 Follow(R')を考える必要がある。

     Follow(R') = Follow(R) = { $, ')' }
   

   より、 ^*3の欄を得る。

3. Qの行については、

     First(P Q') = First(P)（First(P)がεを含まないので）
                 = { '(', ALPHA }
   

   より、 ^*4の欄を得る。

4. Q'の行については、やはり、上の First(P Q')の結果から ^*5の欄を得る。 さらに Follow(Q')を求めると、

     Follow(Q') = Follow(Q)
                = First(R')(εを除く) + Follow(R')+ Follow(R)
                = { '|' } + Follow(R) = { '|', ')', $ }
   

   より、 ^*6の欄を得る。

5. Pの行は

     First(O P') = First(O)（First(O)がεを含まないので）
                 = { '(', ALPHA }
   

   より、 ^*7の欄を得る。

6. P'の行は First('*' P') = { '*' }より、 ^*8の欄、

     Follow(P') = Follow(P)
                = First(Q')(εを除く) + Follow(Q') + Follow(Q)
                = { '(', ALPHA } + { '|', ')', $ }
                = { '(', ALPHA, '|', ')', $ }
   

   より ^*9の欄を得る。

7. Oの行はほとんど自明。