27

あいまいな文法から明確な文法がどのように派生するのか理解できませんでしたか? サイトの例を考えてみましょう: Example . 文法がどのように派生したかは、私を混乱させます。

誰でも私を案内してもらえますか？

4

2 に答える 2

53

この例には 2 つの文法があります。

あいまい:

E → E + E | E ∗ E | (E) | a

明白:

E → E + T | T
T → T ∗ F | F
F → (E) | a

明確な文法は、曖昧な文法で指定されていない情報を使用して、曖昧なものから派生しました。

  • 演算子「*」は、演算子「+」よりも強く結合します。
  • 演算子 '*' と '+' はどちらも左結合です。

外部情報がなければ、変換を行う方法はありません。

外部情報を使用すると、次のことがわかります。

a * a + b * b

次のようにグループ化されます。

(a * a) + (b * b)

次のようではなく:

a * ((a + b) * b)

2 つ目は、'+' が '*' よりも厳密にバインドされ、演算子が左から右ではなく右から左にバインドされることを前提としています。

コメント

次のような例の場合、結合性はどのように現れるでしょうか。

    S → aA | Ba
    A → BA | a
    B → aB | epsilon

これはあいまいな文法なので、あいまいでない文法に変換するにはどうすればよいでしょうか?

「イプシロン」は空の文字列である ε なのだろうか。両方の方法で文法を分析しましょう。

ε は空の文字列です

B の規則では、B は空の文字列であるか、a の後に有効な B が続き、0 個以上の a の無限に長い文字列になります。

A の規則では、A は a か、B の後に a が続くことになります。したがって、無限に長い a の文字列も A である可能性があります。したがって、a の文字列が A であるか B であるかを文法で選択する方法はありません。

そして、S のルールは役に立ちません。S は、a の後に無期限に長い a の文字列が続くか、a の後に無期限に長い文字列の a のいずれかです。少なくとも 1 つの a が必要ですが、a は 1 から上に何個でも OK ですが、文法には左右の選択肢を決定する根拠がありません。

したがって、この文法は本質的にあいまいであり、私の推定では、あいまいさをなくすことはできません。私たちが所有していない他の情報がなければ、それを明確にすることはできません。

ε は空の文字列ではありません

ε が空文字列でない場合はどうなるでしょうか?

  • B は ε または asε です。
  • A は、a または B の後に a が続きます (つまり、a または aaε または aaε のいずれか)。
  • S は a の後に A が続く (したがって、aa、aaε、または aaaε)
  • または: S は B の後に a が続きます (したがって、εa または asa)。

この場合、文法は現状のままで明確です (ただし、必ずしも LR(1) であるとは限りません)。明らかに、多くはコメント/質問の「イプシロン」の意味にかかっています。

結合性

結合性がこの文法に影響を与えるとは思いません。一般に、中置演算子 (「a + b」の「+」など) で使用されます。

于 2010-06-23T23:28:21.903 に答える
11

ウィキペディアから (あいまいな文法の認識について):

あいまいな文法の中には、あいまいでない文法に変換できるものもありますが、あいまいな文法を検出するためのアルゴリズムが存在しないのと同様に、これを行うための一般的な手順はありません。

2 番目の文法を思いつくためには、次の文法を見つけなければなりません。

  1. 最初のものと同等: どちらも同じ言語を生成します
  2. 明確: 言語のすべての文に対して、解析ツリーは一意です
于 2010-06-23T23:35:18.257 に答える