5

こんにちはスタック オーバー フロー メンバーです。

私はコンパイラクラスのために勉強しています。トップダウン パーサーは左再帰を避け、右再帰に変換する必要があることを理解しました。

質問は、

a) トップダウン パーサーが LL に等しく、ボトムアップ パーサーが LR に等しいことを理解していますか?

b) 左再帰は自分自身を呼び出すルールであることがわかりました ex) Expr :== Expr '+' Term | Expr を見つける無限ループを引き起こす項。とにかく、C または Java での入力を考慮するサンプル コードはありますか? ( パーサーやスキャナーのコードはいらない ) 必要なのは、左再帰による無限ループが発生するセンテンシャル形式のコード例です。

c) トップダウン パーサーで右再帰を使用する方法で実際に何が違いますか?

ANS c) バックトラックの必要性をなくす。しかし、他の何か？

ANS b)x - 2 * yだけでなく、他の何か? これはバックトラックの解析方法で動作するためです。

非左再帰と左再帰の両方を発見した事例。

左再帰文法

A -> Ax

非左再帰文法

A -> Bx
B -> Ay

どちらも無限ループに陥っています。

専門家の皆様、ありがとうございました。

4

1 に答える 1

6

a）正しいトップダウンパーサーがLLに等しく、ボトムアップパーサーがLRに等しいことを理解していますか？はい

トップダウンパーサーは、コード内のプロダクションが次のように見えるため、左再帰で無限ループに入ります。

A() {
  A(); match(x);
}

Aはそれ自体を永久に呼び出し、入力ストリームから何も削除しません。

左再帰は即時である必要はないので、「非左再帰文法」は依然として再帰のままです。

A -> Bx | z
B -> Ay

Bをその生成で置き換えると、再帰的になることがわかります。

A -> Ayx | z

左再帰文法を右再帰文法に正しく変換する例を次に示します。左再帰：

E -> E + T | T

右再帰：

E -> T B
B -> + T B | Lambda

E-> TBなので、ルールではE-> E + T | T、Tは、ルールの適用が終了した後、常に左端に表示されます。左端はE->TBによって処理されるため、B-> +TBで行う文字列の右側を自由に作成できます。再帰。

A->AxとA->xAは同等の文法であり、一方だけが残り、もう一方は右再帰です。

于 2010-10-24T22:24:00.763 に答える