再帰と交替を伴うregural文法をregural式に変換する方法

Question

文法は、右直線または左直線のいずれかであれば規則的です。

正規文法は、特殊な性質を持っている：その右側に（ルート1を除く）非終端すべての を代入することにより、あなたはそれを を下に減らすことができますので、のは、それは特殊な性質を持っていることをことをThis tutorial主張のみ 端子とオペレータ右側...端子および演算子の低減 発現を有するルートのための単一の産生が、より一層 コンパクトな形式で書くことができ、正規表現と呼ば

だから私はそれをテストすることに決めました以下に限定されている

IdentifierName :: 
    IdentifierStart 
    IdentifierName IdentifierPart 

と仮定IdentifierStartとIdentifierPart：regural式にregural EcmaScript grammar for IdentifierNameをアイデアと変換

IdentifierStart ::  IdentifierPart :: 
    A      A     
    B      C 
    C      & 
    $      
    _ 

しかしIdentifierNameための文法は両方持っているので、私は続行するかどうかはわかりません再帰と交替。どんな助け？

@Bergiが示した結果正規表現を見つけるのではなく、アプローチにもっと興味があります。[ABC$_][AC&]*です。

Answer 1

このチュートリアルでは、いくつかの非標準的な（そして驚くほど暗黙の）定義を使用しています。

まず、正規表現やEBNFにあるように、文法の繰り返し演算子を使用します。次に、暗黙的には、これらの繰り返し演算子のみを使用し、再帰を使用しない正規の文法を定義します。それを考えると、すべての非終端記号をインライン化するだけで、正規の文法を正規表現に変換するのは簡単です。しかし、その定義によって、JS仕様の識別子の文法は再帰を含んでいるため規則的ではありません。ですから、すべてをインライン化する前に、繰り返し操作を繰り返し操作で置き換える必要があります。

しかし、これは標準的な文法の標準的な定義ではありません。標準的な定義は、あなたが言った通りです。文法は、左リニアまたは右リニアのいずれかであれば規則的です。つまり、プロダクションの一番左のアイテムだけが非終端である場合、または右端のアイテムのみがある場合です。反復演算子は、形式的文法の通常の定義には存在しません。

これらの正規の文法は、正規表現に変換することもできますが、チュートリアルで説明した方法を適用するだけではできません。 1つの方法は、文法を有限オートマトンに変換し、次にthis answerに記載されているアルゴリズムを適用することです。

しかし実際には、（プログラムを作成するのではなく）手作業で変換を行う場合、変換を実行する最も簡単で最も一般的な方法は、文法がどの言語を記述しているかを考えることです（この場合は「言語IdentifierStartシンボルで始まり、次に0個以上のIdentifierPartシンボルを含むすべての単語のうちのいくつかを含む）を生成し、その言語を表現する正規表現を作成します（別名「ソリューションが見えるまで問題を本当に見ています」 - アルゴリズム） 。