0

2つの違い、あいまいさは、2つの異なる解析ツリーを持つ文字列が少なくとも1つあるのに対し、あいまいでないツリーには1つしかないことを意味することを理解しています。しかし、私は一方を他方に変換することができないようです。

次のあいまいな文法を明確な文法に変換するにはどうすればよいですか？

S -> aSb
S -> abS
S -> lambda

編集：わかりました、これで私の刺し傷は次のようなものになります

S -> aSb | lambda
b -> abS | lambda

何かご意見は？

4

1 に答える 1

1

次のトークンとして「a」に一致する2つのルールがあるだけでなく、「ab」は最初または2番目のルール（それぞれのSの代わりに3番目を使用）のいずれかで一致できるため、文法はあいまいです。

本質的に曖昧な文法のようなものがありますが、これはそうではありません。

この特定の例に焦点を当てて、解析する文字列を列挙することから始めました。ルール1、2、3に番号を付け、ルール1と2が解析に現れる可能性のあるすべてのシーケンスを検討しました（これらは端末を生成する2つのルールです）。NB「ラムダ」は空の生成を表すと仮定しました。

1,2 => ab
11,12 => abab
21,22 => aabb
111,112 => ababab
121,122 => abaabb
211,212 => aababb
221,222 => aaabbb
1111,1112 => abababab
1121,1122 => ababaabb
1211,1212 => abaababb
1221,1222 => abaaabbb
2111,2112 => aabababb
2121,2122 => aabaabbb
2211,2212 => aaababbb
2221,2222 => aaaabbbb

この演習から、「a」と「b」の偶数の長さの文字列が一致していることは明らかです。ここで、「a」端子の数は「b」端子の数と正確に一致します...さらに、一致する2つの文字列の連結プレフィックスが2番目のルールを使用して一致した場合にのみ、別の一致する文字列が生成されます。

この分析から、私はいくつかの新しい作品を作成しました。

S -> a a X
S -> a b S
S -> lambda
X -> S b b

この新しい文法はあいまいではありませんが、あいまいな文法と同じ文字列に一致します。これは、新しい非終端記号Xを導入することで実現されます。このCFGをプッシュダウンオートマトンとともに使用すると、SとXの両方を使用することで生じる追加の状態情報で、あいまいさを回避できます。

この問題がYaccやBisonのようなものを使用する状況で発生した場合、あいまいさは、多くの場合、ターミナルトークンの選択が不適切であることを示しています。端子として「aa」、「ab」、「bb」を選択した場合、問題は発生していません。（F）lexをトークナイザーとして使用する場合、経験則として、一致するトークンを意味のある大きさにすることをお勧めします...正規表現に一致する方が（少なくとも理論的には）、文脈自由文法-そしてこれは当然のことながら2文字のトークンアプローチを生み出したかもしれません。

于 2011-09-23T19:13:19.250 に答える