0

質問

文脈自由文法 "S->SbS|ScS|a" が曖昧であることを、文字列 abaca に 2 つの構文木を与えることによって示します。

文字列がどのように曖昧なのかわかりませんか? 私はコンパイラと自己学習に関する本を読んでいたので、本でこの質問をしていましたが、困惑しています。

考えられる解決策

abaca         abaca
a(aba)aca     aba(aca)a

私の解決策が正しいかどうかを誰でも確認できますか。そうでない場合は、誰かが私を案内してください。

4

1 に答える 1

2

これは、ペンと紙で行う方がはるかに簡単です。すべての可能性の中で、最初の記号 を導き出すことによって見つけられる 3 つの可能性をリストしますS。

S -> SbS -> abS -> abScS -> abacS -> abaca
S -> ScS -> Sca -> SbSca -> abSca -> abaca
S -> SbS -> SbScS -> abScS -> abSca -> abaca

他にもありますが、見るのは難しくありません。ただし、多くの場合、文字列 ( abaca) を元の記号 ( S) に縮小する方が簡単です。多くのコンパイラは、無限再帰を回避するためにこれを行います。

abaca <- Sbaca <- SbSca <- Sca <- ScS <- S
abaca <- abacS <- abScs <- abS <- SbS <- S

これを行う方法は、手動で方法 (派生または縮約) を選択し、試行錯誤して、文法に従って行うことができる可能な置換を行うことです。これにより、ツリーが作成されます。ゴールに到達するツリー内のノード (元のシンボルまたは最終的な文字列) が正しいノードです。複数のパスがある場合、それはあいまいです。

さて、これらの派生のそれぞれと他のものは、いわゆる を生成しParse Treeます。解析ツリーは、最初のシンボルから終端文字列を生成できる一連の派生を表します。解析ツリーをよりよく視覚化するために、これらの種類のツリーを描画するためのツールを Web で見つけました。ここで見つけることができます。

使用するフォーマットは であり[NonTerminal terminal [NonTerminal terminal] terminal]、括弧の代わりに角括弧を使用した Lisp に似たリストです。たとえば、私が構築した最初の派生物は、 のS -> SbS -> abS -> abScs -> ...ように書くことができます[S [S a] b [S [S a] c [S a]]]。ここで[S [S ...] b [S ...]]、 は最初の派生物を表し、最初の派生物を 2 番目の派生物で展開[S ...]し[S a]ます。このツールが正式な文法の学習に役立つことを願っています!

于 2014-10-19T01:42:07.577 に答える