8

説明：

Compiler Design in C book を読んでいるときに、文脈自由文法を説明する次の規則に出くわしました。

1 つまたは複数のステートメントのリストを認識する文法。各ステートメントは算術式の後にセミコロンが続きます。ステートメントは、セミコロンで区切られた一連の式で構成されます。各式は、アスタリスク (乗算の場合) またはプラス記号 (加算の場合) で区切られた一連の数値で構成されます。

そして、ここに文法があります：

1. statements ::= expression;
2.                | expression; statements
3. expression ::= expression + term
4.                | term
5. term       ::= term * factor
6.                | factor
7. factor     ::= number
8.                | (expression)

この本は、この再帰的な文法には大きな問題があると述べています。プロダクション 3 のように、いくつかのプロダクションの右側が左側に表示され (そして、このプロパティは左再帰と呼ばれます)、再帰降下パーサーなどの特定のパーサーは左再帰プロダクションを処理できません。それらは永遠にループします。

右辺が複数ある非終端記号を置き換えるときに、パーサーが特定のプロダクションを適用することをどのように決定するかを考えると、問題を理解できます。単純なケースは、プロダクション 7 と 8 で明らかです。パーサーは、次の入力シンボルを見て、因子を展開するときに適用するプロダクションを選択できます。このシンボルが数値の場合、コンパイラは Production 7 を適用し、係数を数値に置き換えます。次の入力記号が開き括弧の場合、パーサーはプロダクション 8 を使用します。しかし、プロダクション 5 と 6 の間の選択は、この方法では解決できません。プロダクション 6 の場合、term の右側は因子で始まり、次に、数字または左括弧のいずれかで始まります。その結果、用語が置き換えられ、次の入力記号が数字または左括弧である場合、パーサーは Production 6 を適用したいと考えています。プロダクション 5 - もう一方の右側 - 項で始まり、因子で開始でき、数字または左括弧で開始できます。これらは、プロダクション 6 を選択するために使用されたのと同じ記号です。

質問：

本からの2番目の引用は、私を完全に迷子にさせました。したがって、いくつかのステートメントの例を (たとえば) として使用すると、次のようになり5 + (7*4) + 14ます。

  1. factor と term はどう違いますか？同じ例を使用して
  2. 再帰降下パーサーが左再帰生成を処理できないのはなぜですか? （2番目の引用を説明してください）。
4

2 に答える 2

5
  1. factor と term はどう違いますか？同じ例を使用して

同じ例を挙げているわけではありません。なぜなら、あなたが疑問に思っていることを明確に理解できないからです!

与えられた、

term       ::= term * factor | factor
factor     ::= number | (expression)

ここで、式 2*3*4 の約数と項を求めたとします。ここで、乗算は連想のままで、次のように評価されます:-

(2*3)*4

ご覧のとおり、ここ (2*3) は項であり、係数は 4 (数値) です。同様に、このアプローチを任意のレベルに拡張して、用語についてのアイデアを引き出すことができます。

与えられた文法に従って、与えられた式に乗算チェーンがある場合、単一の因子を残すそのサブ部分は項であり、それは次に別のサブ部分を生成します---別の項、別の単一の因子を残し、すぐ。これが式の評価方法です。

  1. 再帰降下パーサーが左再帰生成を処理できないのはなぜですか? （2番目の引用を説明してください）。

あなたの2番目の声明は、本質的に非常に明確です。再帰的降下パーサーは、一連の相互再帰的手続き (または非再帰的同等物) から構築された一種のトップダウン パーサーであり、そのような各手続きは通常、文法のプロダクションの 1 つを実装します。

非終端がそれ自体に展開し続けると、再帰的降下パーサーが無限ループに陥ることは明らかであるため、そう言われています。

同様に、再帰的降下パーサーについて言えば、バックトラッキングがあっても --- 非終端記号を展開しようとすると、最終的には入力を消費せずに同じ非終端記号を展開しようとしていることに気付くかもしれません。

A-> Ab

ここで、非終端記号 A を展開しながら、展開を続けることができます

A-> AAb -> AAAb -> ... -> infinite loop of A.

したがって、再帰降下パーサーを使用している間、左再帰生成を防ぎます。

于 2015-05-21T13:36:44.407 に答える
3

  1. ルール要素は文字列 "1*3" に一致しますが、ルール用語は一致しません (ただし、"(1*3)" には一致します)。本質的に、各ルールは 1 レベルの優先順位を表しますexpression。factor最低とterm最高. 用語を使用していて、優先順位の低い演算子を使用する場合は、括弧を追加する必要があります。

  2. 再帰関数を使用して再帰降下パーサーを実装する場合、次のようなルールが次のようa ::= b "*" c | dに実装される可能性があります。

    // Takes the entire input string and the index at which we currently are
// Returns the index after the rule was matched or throws an exception
// if the rule failed
parse_a(input, index) {
  try {
    after_b = parse_b(input, index)
    after_star = parse_string("*", input, after_b)
    after_c = parse_c(input, after_star)
    return after_c
  } catch(ParseFailure) {
    // If one of the rules b, "*" or c did not match, try d instead
    return parse_d(input, index)
  }
}

    このようなものは問題なく動作します (実際には、実際には再帰関数を使用したくない場合がありますが、代わりに使用するアプローチは同様に動作します)。a ::= a "*" b | cそれでは、代わりに左再帰規則を考えてみましょう。

    parse_a(input, index) {
  try {
    after_a = parse_a(input, index)
    after_star = parse_string("*", input, after_a)
    after_b = parse_c(input, after_star)
    return after_b
  } catch(ParseFailure) {
    // If one of the rules a, "*" or b did not match, try c instead
    return parse_c(input, index)
  }
}

関数parse_aが最初に行うことは、同じインデックスで自分自身を再度呼び出すことです。この再帰呼び出しは、再び自分自身を呼び出します。そして、これは無限に、またはスタックがオーバーフローしてプログラム全体がクラッシュするまで続きます。再帰関数の代わりにより効率的なアプローチを使用すると、実際にはスタック オーバーフローではなく無限ループが発生します。いずれにせよ、私たちが望む結果は得られません。

于 2015-05-21T13:34:49.673 に答える