4

こんにちは、本にこの質問があります

このグラマーを考えると

A --> AA | (A) | epsilon

a- 生成するもの\

b- あいまいな表示

今私が考える答えは

a- 隣接括弧

b- 異なる解析ツリーを生成するため、あいまいで、2 つのシナリオを示す描画を行いました。

これは正しいですか、それともより良い答えがありますか?

4

4 に答える 4

2

aほぼ正しいです。
文法は実際()に , ()(), ()()(), … の並びを生成します。
しかし、2 番目のルールにより(())、()((()))、 などを生成できます。

bは正しくありません。
この文法は、すぐ左に再帰するためあいまいです: A → AA.

左再帰を回避する方法: one、two .

于 2010-12-19T20:20:40.310 に答える
1

a）ほぼ正しい...

この文法は、バランスの取れた括弧で構成された文字列のセットを正確に生成します。その理由を理解するために、簡単なデモンストレーションを試してみましょう。

まず、文法から外れるものはすべて、バランスの取れた括弧文字列です。なぜですか？、単純な誘導：

  • イプシロンは、バランスの取れた（空の）括弧文字列です。
  • Aがバランスのとれた括弧文字列の場合、（A）もバランスが取れています。
  • A1とA2のバランスが取れている場合、A1A2もバランスが取れています（A-> AAが必要ないという事実を明示するために、あまりにも異なる識別子を使用しているため、各Aで同じものが生成されます）。

2番目：バランスの取れた文字列のすべてのセットは、文法によって生成されます。文字列のサイズを誘導してやってみましょう。

  • 文字列のサイズがゼロの場合は、イプシロンである必要があります。
  • そうでない場合は、Nを文字列のサイズ、Mをバランスの取れた最短のプレフィックスの長さにします（文字列の残りの部分もバランスが取れていることに注意してください）。
    • M = Nの場合、（A）を使用してその文字列を生成できます。
    • M <Nの場合、A-> AAで生成でき、最初のM文字は最初のAで、最後のN-Mは最後のAで生成できます。いずれの場合も、N文字より短い文字列を生成する必要があります。誘導あなたはそれを行うことができます。QED。

例えば： （（）（））（（））

この文字列は、デモンストレーションのアイデアを正確に使用して生成できます。

A-> AA->（A）A->（AA）A->（（A）（A））A->（（）（））A->（（）（））（A）->（ （）（））（（A））->（（）（））（（））

b）もちろん、左右の再帰はあいまいであると言うのに十分ですが、特にこの文法があいまいである理由を確認するには、デモンストレーションについて同じ考えに従ってください。

最短のバランスの取れたプレフィックスを取る必要がないため、あいまいです。文字列のサイズではない最長のバランスの取れた（または一般的にはバランスの取れたプレフィックス）を取ることができ、デモンストレーション（および生成）は同じプロセスに従います。

元： （（））（）（）

A-> AAを選択し、最初のAで（（））部分文字列、または（（））（）部分文字列を生成できます。

于 2012-05-02T16:13:45.203 に答える
0

はい、あなたは正しいです。

それが曖昧な文法の意味です。

あいまいな文法の問題は、コンパイラを作成していて、コードの特定の行 (またはそのようなもの) の各トークンを識別したい場合、あいまいさが「2 つの説明」を持っているため、識別する際に混乱することです。コード行。

于 2010-12-19T20:21:50.800 に答える
0

パート B に対するあなたのアプローチは正しいように思えます。文法で定義された言語で、同じ文字列に対する 2 つの独立した派生を示しています。

ただし、パートAへの回答には少し作業が必要だと思います。明らかに、2 番目の節を再帰的に使用して (((((epsilon))))) のような文字列を取得できますが、最初の節と 2 番目の節を一緒に使用すると、他のタイプの派生が可能です。

于 2010-12-19T20:26:17.810 に答える