regex - 正規表現を記述する文脈自由文法?

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

Plan9grepのソースコードを見ることができます。ファイルgrep.yには、正規表現用のyacc（正しく思い出せばLALR（1））文法があります。yacc文法から始めて、再帰下降構文解析のために書き直すことができる場合があります。

Answer 3

左再帰に関するウィキペディアの記事は、これを実現する方法についてかなり良い情報を提供しています。