私はAhoのコンパイラ構築から有限オートマトン&の文法を読んでいます。私はこの文法を長年抱いています。文法の正規表現
次の文法を考えてみましょう：私はそれを記述することができる方法の明確な認識を持っていない
S - >（L）| a L→L、S | S
括弧とカンマは実際には 言語の端末であり、この文法で受け入れられる文章に現れることに注意してください。この文法で生成される言語については、 を参照してください。この文法はあいまいですか？ ？
私の関心事は次のとおりです。この文法で生成された言語は、正規表現として記述できますか？私はそれを行う方法について混乱しています。どんな助け？
文法があいまいであることを示すには、同じ文字列を解析するときに2つの異なる構文解析ツリーを構築できる必要があります。文字列は文法の唯一の記号であるため、文字列は "（"、 "）"、 "、"、 "a"で構成されます。
example ambiguous grammar on Wikipediaの精神で、これらの4つの端末記号をいくつかの方法で整理し、異なる成功した構文解析を表示できるかどうかを確認してください。
直ちに左回帰すると、一部のパーサーで問題が発生する傾向があります。 「」で興味深い何もないかどうかを確認し、「L → L、Sを| S」
...
をここに私の関心は、正規表現としてこの文法によって生成される言語は、それを説明することができています...私はやり方について混乱しています
正規表現では完全に文法を説明することはできません。文法の一部を書き換えることは、これがより明らかになります：
＃1と＃4に注意してください。 LはSを生成することができ、Sは（L）を生成することができる。これは、Sが、（S）、（（S）））等を無限に生成することができる（S）を生成できることを意味する。重要なことは、それらのかっこが一致していることです。 「（」記号と同じ）記号があります。
正規表現ではできません。
正規表現は有限オートマトンにマップされます。有限オートマトンはカウントできません。言語L ∈ {w：0 n n}は正規ではありません。 L ∈ {w：（n）n}のように、 "1"の場合は "（"は "0"と "）"を代入するだけです。参照：最初の例のセクションはRegular Languages - Wikipediaです。これは、あなたがその部分を記述するために正規表現を使用することはできません
：（表記のノート。S はがSSはS、...、Nがn回繰り返さSでS、Sです）言語のそれは、CFG、チューリングマシン、プッシュダウンオートマトンの領域に置きます。
正規表現（およびそれを解釈するライブラリ）は、文脈自由文法の文を認識するための貧弱なツールです。代わりに、yacc、bison、またはANTLRのようなパーサジェネレータを使用したいと思うでしょう。
私はAhoの本の練習のポイントは、あいまいかどうかを理解するために、言葉で "言語を説明する"ことだと思います。それにアプローチする1つの方法：文法の生成を考えれば、2つの異なる方法で解析できる文法センテンスを考案できますか？そうであれば、文法はあいまいです。