Aho のコンパイラ構造から有限オートマトンと文法を読んでいますが、この文法に長い間こだわっています。私はそれをどのように説明できるかについて明確な認識を持っていません:
次の文法を検討してください。
S -> (L) | L -> L、S | S
括弧とコンマは実際にはこの言語の終端であり、この文法で受け入れられる文に表示されることに注意してください。この文法によって生成される言語を説明してみてください。この文法は曖昧ですか？
ここでの私の懸念は次のとおりです。この文法によって生成された言語は正規表現として記述できますか? 私はそれを行う方法について混乱しています。何か助けはありますか？
文法があいまいであることを示すには、同じ文字列を解析しながら 2 つの異なる解析ツリーを構築できる必要があります。文字列は、「(」、「)」、「,」、および「a」で構成されます。これは、これらが文法の唯一の終端記号であるためです。
これらの 4 つの終端記号をいくつかの方法で配置してみて、ウィキペディアのあいまいな文法の例の精神で、さまざまな成功した解析を表示できるかどうかを確認してください。
即時左再帰は、一部のパーサーで問題を引き起こす傾向があります。"a,a,a" が "L → L , S | S" に対して何か面白いことをするかどうかを確認してください...
ここでの私の懸念は、この文法によって生成される言語です。正規表現を記述することができます...どうすればよいか混乱しています
正規表現は文法を完全には記述できません。文法の一部を書き直すと、これがより明確になります。
#1と#4に注目してください。L は S を生成でき、S は ( L ) を生成できます。これは、S が ( ( S ) )、( ( ( S ) ) などを無限に生成できる ( S ) を生成できることを意味します。重要なことは、これらの括弧が一致していることです。「(」記号と「)」記号の数は同じです。
正規表現ではそれができません。
正規表現は有限オートマトンにマップされます。有限オートマトンは数えられません。言語 L ∈ {w: 0 n 1 n } は正則ではありません。L ∈ {w: ( n ) n } は、単に "(" を "0" に、")" を "1" に置き換えただけでも、そうではありません。参照:正規言語 - ウィキペディアの最初の例のセクション。(表記上の注意: s 1は s、s 2は ss、...、s nは s が n 回繰り返される。)
これは、言語のその部分を記述するために正規表現を使用できないことを意味します。つまり、CFG、チューリング マシン、およびプッシュダウン オートマトンの領域に置かれます。
正規表現（およびそれらを解釈するためのライブラリ）は、文脈自由文法の文を認識するための貧弱なツールです。代わりに、yacc、bison、ANTLRなどのパーサジェネレータを使用することをお勧めします。
アホの本の練習のポイントは、曖昧かどうかを理解するために、言葉で「言語を説明する」ことだと思います。それにアプローチする1つの方法：文法の生成を考慮して、2つの異なる方法で解析できる文法文を考案できますか？もしそうなら、文法は曖昧です。