■

どうも「Cプログラマのためのアルゴリズム（以下参考文献①)」に書いてある正規表現の構文規則がしっくりこないので何故か考えてみた。以下の正規表現の定義と規則が完全に一致してないからだと思った。
（おそらく著者の頭の中では既に正規表現の構文規則が出来上がっていて、そちらの方が自然だったのであろうけど、構文規則がよくわかっていない者（定義から構文規則の作成方法がよくわかっていない者）にはわかりにくい気がする）
そこで、正規表現の定義をそのまま構文規則にしてみた。

正規表現の定義(括弧の規則を追加)
(1) ε(空記号列)は正規表現である
(2) Aの要素a (a⊆A)は正規表現である
(3) RとSが正規表現ならば
    R|S (union), RS (concat), R* (closure)
    も正規表現である。
(4) R+を簡易記法として以下のように定める
    R+ ::= RR*  
(5) Rが正規表現ならば
    (R)も正規表現である。
また、正規表現の優先順位は
  (R) > R* = R+ > RS > R|S
である。

正規表現の構文規則
 ::=  |  '|' 
※(3)より、RとSが正規表現ならばそのR|Sも正規表現である。ただし、
　R|Sの表現が存在しない場合（|が無い場合）も考え、分岐させた。

 ::=  | 
※(3)より、RとSが正規表現ならばRSも正規表現である。ただし、
　RSの表現が存在しない場合（連結が無い場合）も考え、分岐させた。

 ::=  |  '*' |  '+'
※(3)(4)よりRが正規表現ならばR*, R+も正規表現である。ただし、
　R*, R+の表現が存在しない場合も考え、分岐させた。

 ::= ε | CHAR | '('  ')'
※(1)(2)(5)より空記号、アルファベット、(R)は正規表現である。

ただし、ε* = ε+ = εである（空記号列の任意回数回の繰り返しは空記号列）

参考文献①の構文規則との違いはε(EMPTY)の位置の違いであるけど、これは
 = * ... や  = + ...
といった表現が出てくるのを回避するためにεの位置をの位置まで上げている箇所である。しかし正規表現の定義からするとε*やε+も正規表現なので今回作成した構文規則の方が正しい。
とはいえ、実際に入力される正規表現では「ε」という記号は存在しないのでこれを回避しないとNFA変換後に無限ループが発生してしまう。
の解析時に読み込んだ文字がCHARか'('以外の場合で次の文字が'*', '+'の場合はε*、ε+をεとして構文木にセットする事とする。