正規表現を記述する文脈自由文法？

Question

正規表現エンジンを作成しようとしています。私は手で再帰的な降下パーサーを記述したいと思います。正規表現の言語（正規表現で記述できる言語ではない）の再帰を伴わない文脈自由文法はどのように見えますか？構文糖を再解析するのが最も簡単なのでしょうか？つまり、a+をaa*に変更しますか？前もって感謝します！

Answer 1

左再帰：

Expression = Expression '|' Sequence 
      | Sequence 
      ; 

Sequence = Sequence Repetition 
     | <empty> 
     ; 

右再帰：

Expression = Sequence '|' Expression 
      | Sequence 
      ; 

Sequence = Repetition Sequence 
     | <empty> 
     ; 

あいまいな形：

Expression = Expression '|' Expression 
      | Sequence 
      ; 

Sequence = Sequence Sequence 
     | Repetition 
     | <empty> 
     ; 

Answer 2

Left Recursionのウィキペディアの記事では、これをどうやって解消するかについてかなり良い情報が得られます。

Answer 3

あなたはsource code for Plan 9 grepで見ることができます。 grep.yファイルには、正規表現のためのyacc（正しくリコールすればLALR（1））文法があります。 yacc文法から始め、再帰的な下降解析のためにそれを書き直すことができます。