再帰的降下パーサーの複雑さについて

Question

再帰的降下パーサーは、場合によっては指数関数時間を必要とすることがあることが知られています。誰も私にサンプルを教えてもらえますか？特にPEGの場合（優先順位付けされた選択肢）に興味がある。

Answer 1

異なる再帰ブランチで同じことを解析することができます（同じ位置で同じルールをチェックすることができます）。これは再帰を使ってn番目のフィボナッチ数を計算するようなものです。

Grammar: 

A -> xA | xB | x 
B -> yA | xA | y | A 
S -> A 

Input: 
xxyxyy 

Parsing: 
xA(xxyxyy) 
    xA(xyxyy) 
     xA(yxyy) fail 
     xB(yxyy) fail 
     x(yxyy) fail 
    xB(xyxyy) 
     yA(yxyy) 
      xA(xyy) 
       xA(yy) fail 
       xB(yy) fail 
       x(yy) fail 
      xB(xyy) 
       yA(yy) 
        xA(y) fail 
        xB(y) fail 
        x(y) fail 
       xA(yy) fail * 
      x(xyy) fail 
     xA(yxyy) fail * 
     y(yxyy) fail 
     A(yxyy) 
      xA(yxyy) fail * 
      xB(yxyy) fail * 
      x(yxyy) fail * 
    x(xyxyy) fail 
xB(xxyxyy) 
    yA(xyxyy) fail 
    xA(xyxyy) * 
     xA(yxyy) fail * 
     xB(yxyy) fail * 
     ... 

* - 私たちは別のブランチでそれをすでに解析されてきた同じ位置にルールを解析します。私たちがxA（xyxyy）が2度目に失敗し、その全体のサブツリーを再び通過することはないと知っているでしょう。私は全体を書きたいとは思わなかったが、何度も同じサブツリーを繰り返すことがわかった。

変換が重複しているときにいつ発生しますか。優先順位のついた選択は物事を変えない - 最も低い優先順位のルールが唯一の正しいルールになった場合（あるいはまったく正しいルールがない場合）は、とにかくすべてのルールをチェックしなければならなかった。

Answer 2

再帰的降下を含むトップダウンパーサーは、入力と文法の組み合わせが多数のバックトラックが必要な場合、理論的に指数関数的になります。これは、決定的な選択が長いシーケンスの最後に置かれるような文法の場合に発生します。たとえば、 "（（（a - b） - c） - d） - e &）"のようなデータがある場合は、パーサーは移動しなければならないという意味の "&"後方に移動し、すべてのプラッシュをマイナスに変更します。これらの行に沿ってネストされた式を作成し始めると、効果的に終了しない入力セットを作成できます。

現実には、ほとんどの通常の文法とデータセットがこのようなものではないため、ここでは政治的な問題に踏み込んでいることに気づかなければなりません。しかし、システマティックにバードマウスの再帰的な降下自動的にRDを簡単に作成できます。初期のパーサーはすべて、RDよりも自動的に作成する方が簡単なため、すべてLALRです。だから何が起こったのは誰もがLALRとbadmouthed RDを書いたことです。なぜなら、昔はRDを作る唯一の方法は手作業でコード化することだったからです。たとえば、ドラゴンの本を読んだ場合、Aho &ウルマンはRDにただ一つのパラグラフを書いています。それは基本的に「RDが悪い、それはしない」という理念的なテイクダウンです。

もちろん、RDを手作業でコーディングし始めると、さまざまな理由からLALRよりはるかに優れていることがわかります。昔は、LALRを持つコンパイラが実際にどこから50行離れているようなエラーを表示するのに対し、手作業でコード化されたRDを持つコンパイラには、場所的な精度を持つ意味のあるエラーメッセージがあるため、常に伝えることができました。昔から多くのことが変わってきましたが、あなたはRDでFUDを読むことを始めるとき、それは "特定のサークル"でRDを口頭で破棄する長い伝統から来ているということを認識するべきです。