13

左再帰の削除で説明されているように、左再帰を削除するには 2 つの方法があります。

  • いくつかの手順を使用して、元の文法を変更して左再帰を削除します
  • 左再帰を持たないように文法を独自に書く

ANTLR で左再帰を削除する (持たない) ために、通常は何を使用しますか? パーサーに flex/bison を使用しましたが、ANTLR を使用する必要があります。ANTLR (または一般的な LL パーサー) の使用に関して私が懸念しているのは、左再帰の削除だけです。

  • 実用的な意味で、ANTLR で左再帰を削除することはどれほど深刻ですか? これは ANTLR を使用する上での目玉ですか? それとも、ANTLR コミュニティでは誰も気にしていませんか?
  • ANTLR の AST 生成のアイデアが気に入っています。AST をすばやく簡単に取得するという点で、(左再帰を削除する 2 つの方法のうち) どの方法が望ましいですか?

追加した

次の文法でいくつかの実験を行いました。

E -> E + T|T
T -> T * F|F
F -> INT | ( え )

左再帰を削除した後、次のものが得られます

E -> TE'
E' -> null | +テ'
T -> FT'
T' -> null | *FT'

次の ANTLR 表現を思い付くことができました。比較的単純で簡単ですが、左再帰を持たない文法の方が適しているようです。

文法T;

オプション {
    言語=Python;
}

start は [値] を返します
   : e {$value = $e.value};
e は [値] を返します
   ：てっぺん  
     {
       $value = $t.value
       $ep.value != なしの場合:
         $value += $ep.value
     }
   ;
ep は [値] を返します
   : {$値 = なし}
   | | '+' tr = ep
     {
       $value = $t.value
       $r.value != なしの場合:
            $value += $r.value
     }
   ;
t は [値] を返します
  : f tp
    {
      $value = $f.value
      $tp.value != なしの場合:
        $value *= $tp.value
    }
  ;
tp は [値] を返します
  : {$値 = なし}
  | | '*' fr = tp
    {
      $value = $f.value;
      $r.value != なしの場合:
        $value *= $r.value
    }
  ;
f は [int 値] を返します
  : INT {$value = int($INT.text)}
  | | '(' e ')' {$value = $e.value}
  ;

INT: '0'..'9'+;
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ;
4

5 に答える 5

12

典型的なパラメータリストのようなものを考えてみましょう。

parameter_list: parameter
              | parameter_list ',' parameter
              ;

優先順位やパラメーターとの関連性などは気にしないので、これは、余分なプロダクションを追加することを犠牲にして、正しい再帰に変換するのはかなり簡単です。

parameter_list: parameter more_params
              ;

more_params:
           | ',' parameter more_params
           ;

最も深刻なケースでは、ドラゴンブックで時間を過ごしたいと思うかもしれません。簡単なチェックを行うと、これは主に第4章で説明されています。

深刻さに関して言えば、ANTLRは左再帰を含む文法を受け入れないので、「絶対に必要」なカテゴリに分類されると確信しています。

于 2010-06-08T18:15:08.607 に答える
6

実用的な意味で、ANTLR で左再帰を削除することはどれほど深刻ですか? これは ANTLR を使用する上での目玉ですか?

左再帰について誤解していると思います。これは文法のプロパティであり、パーサー ジェネレーターや、パーサー ジェネレーターと仕様の間の相互作用ではありません。ルールの右側の最初の記号が、ルール自体に対応する非終端記号と等しい場合に発生します。

ここで固有の問題を理解するには、再帰降下 (LL) パーサーがどのように機能するかについてある程度知っておく必要があります。LL パーサーでは、各非終端記号の規則は、その規則に対応する関数によって実装されます。したがって、次のような文法があるとします。

S -> A B
A -> a
B -> b

次に、パーサーは (大まかに) 次のようになります。

boolean eat(char x) {
  // if the next character is x, advance the stream and return true
  // otherwise, return false
}

boolean S() {
  if (!A()) return false;
  if (!B()) return false;
  return true;
}

boolean A(char symbol) {
  return eat('a');
}

boolean B(char symbol) {
  return eat('b');
}

しかし、文法を次のように変更するとどうなりますか?

S -> A B
A -> A c | null
B -> b

おそらく、この文法で のような言語を表現したいと考えていc*bます。LL パーサーの対応する関数は次のようになります。

boolean A() {
  if (!A()) return false;  // stack overflow!  We continually call A()
                           // without consuming any input.
  eat('c');
  return true;
}

したがって、左再帰を使用することはできません。文法を次のように書き換えます。

S -> A B
A -> c A | null
B -> b

パーサーは次のように変更されます。

boolean A() {
  if (!eat('c')) return true;
  A();
  return true;
}

（免責事項：これは、この質問に関するデモンストレーションのみを目的とした、LLパーサーの私の初歩的な近似です。明らかなバグがあります。）

于 2010-06-08T18:11:23.197 に答える
3

ANTLRについて話すことはできませんが、一般的に、フォームの左再帰を排除するための手順は次のとおりです。

A -> A B
  -> B

次のように変更します。

A -> B+

B（少なくとも1回は表示される必要があることに注意してください）

または、ANTLRがクリーネ閉包をサポートしていない場合は、次のことができます。

A -> B B'

B' -> B B'
   ->

競合しているルールの例を提供していただければ、より適切で具体的な回答を提供できます。

于 2010-06-08T18:15:36.993 に答える
1

文法を作成している場合は、もちろん、特定のパーサー ジェネレーターの落とし穴を回避するためにそれを作成しようとします。

通常、私の経験では、関心のある (レガシー) 言語のリファレンス マニュアルを入手します。そこには既に文法や路線図が含まれており、そのままです。

その場合、文法からの左再帰の除去のほとんどは手作業で行われます。左再帰除去ツールの市場はありません。また、あるとしても、使用している文法構文と一致しない文法構文に特化したものになるでしょう。

この除去を行うことは、多くの場合汗をかく作業であり、通常はそれほど多くはありません。したがって、通常のアプローチは、グラマー ナイフを取り出して実行することです。

左再帰を削除する方法によって、ANTLR がツリーを取得する方法が変わるとは思いません。最初に左再帰の削除を行う必要があります。そうしないと、ANTLR (または使用している LL パーサー ジェネレーター) が文法を受け入れません。

パーサージェネレーターが、文脈自由文法のために書くことができるものに重大な制約を課すことを望まない人がいます。この場合、左または右の再帰を簡単に処理する GLR パーサー ジェネレーターのようなものを使用します。理不尽な人は、文法作成者側の努力なしに自動化された AST 生成を主張することさえできます。両方を実行できるツールについては、DMS Software Reengineering Toolkitを参照してください。

于 2010-06-08T17:55:59.253 に答える
1

これは直交的に関連するだけですが、ルールの書き換えを必要とせずに左再帰文法を直接処理する「ピカ解析」(packrat 解析を参照) と呼ぶ新しい解析方法に関する論文のプレプリントを公開しました。

https://arxiv.org/abs/2005.06444

于 2020-05-14T04:39:48.120 に答える