4

私は再帰的な適切な解析について学んでおり、アルゴリズムが機能していないと思われるいくつかのシナリオを考え出しています。それらの 1 つは、この単純な文法を考慮すると、次のようになります。

S→E;
E → イド | id + id

次に、文字列id + id;はこの文法の言語で有効です。しかし、再帰的降下アルゴリズムを実行すると、 から まで降下しS、E最初idに一致する端子である まで降下します。これで入力は になり、一致を試みること+に戻りましたが、失敗しました。しかし、 のレベルで選択できるルールは他にありません。S;S

id;言語にはとの 2 つの文字列しかなくid + id;、それぞれに一意の構文木があるため、文法は曖昧ではないと思います。ここでの一般的な問題は、非終端記号が同じプレフィックスを持つプロダクションを持ち、再帰のより深いレベルで一致する選択をする可能性がありますが、より浅いレベルでは無効な入力を作成することです。

左再帰のような再帰的降下の典型的な問題について読んだことがありますが、上記の問題はどこにも見つかりませんでした。これは本当に問題なのですか、それとも何か不足していますか?

Parsing Techniques: A Practical Guide p.182-188上記のアプローチを単純な再帰的まともなものとして分類し、同じ問題を強調する本から信頼できる回答を見つけました。先読みなしの一般的なケースで常に機能する 2 つの解決策があります (一般に、必要な先読みの長さはプレフィックスの長さとともに増加するため): 継続の使用を必要とする完全な再帰的降下と、幅優先の再帰的降下です。

4

3 に答える 3

1

私はこれについて非常に錆びているので、ゴミを投稿しようとしているかもしれませんが、これは先読みで解決できませんか? 何かのようなもの：

func recogniseS
    expect(E)
    expect(semicolon)

fund recogniseE
    expect(id)

    if nextTokenIs(plus) then 
        expect(plus)
        expect(id)
    endif

または、同様に、次のように再定式化できます。

S → id [+ id];

つまり、本質は単に+がオプションであるということです。したがって、任意のものが処理できる限り、状況に対処できます。

于 2014-12-17T15:01:54.187 に答える
1

文法を次のように因数分解できる限り、それは問題ではありません (最初の選択肢E'が空である場合)。

S → E ;
E → id E'
E' → | + id

の場合E'、次のトークンが の場合は最初の選択肢を予測し、次のトークンが;の場合は 2 番目の選択肢を予測します+。

于 2014-12-17T15:02:01.747 に答える