問題タブ [recursive-descent]

私は単純な言語パーサーを構築していますが、優先順位の低いプレフィックス式に問題があります。文法の例を次に示します。

NOTただし、この文法は、より優先順位の高い中置演算子の RHS として使用される場合、つまり次のように正しく機能しません。

これは、==オペレーターが RHS で E1 を要求しているためであり、これは NOT 操作ではありません。

この文法を表現する正しい方法がわかりませんか? この単純化された再帰的降下アプローチを使用してまだ可能ですか、それともより機能的なアルゴリズム (ヤードの迂回または先行登攀) に移行する必要がありますか?

注: これは、プレフィックス式の欠落を解析する再帰的降下の優先順位のより詳細なバージョンです。

私は単純な言語パーサーを構築していますが、優先順位の低いプレフィックス式に問題があります。文法の例を次に示します。

ただし、この文法は、より優先順位の高い中置演算子の RHS として使用される場合、NOT に対しては正しく機能しません。つまり、次のようになります。

これは、RHS で必要な == 演算子が原因でありE3、これは「NOT」操作ではありません。

この文法を表現する正しい方法がわかりませんか? この単純化された再帰的降下アプローチを使用してまだ可能ですか、それともより機能的なアルゴリズム (ヤードの迂回または先行登攀) に移行する必要がありますか?

正しく解析する必要があるいくつかの例を次に示します。

• 入力true == 1 < 2、出力==(true, <(1, 2))
• 入力1 < 2 == true、出力==(<(1, 2), true)
• 入力NOT true == false、出力NOT(==(true, false))
• 入力true == NOT false、出力==(true, NOT(false))** が機能しない
• 入力true < NOT false、出力<(true, NOT(false))** が機能しない

Recursive Descent precedence parsing missing prefix expression (ie , , etc)で提案されているように、中置式の RHS で使用するレベルE4、E3、およびを変更しようとしました。ただし、これはこれらのレベル間の優先順位を壊します。つまり、誤って<(==(true, 1), 2)` になります。E2E5E3 '==' E5E3 '<' E5true == 1 < 2parsed as

実際の言語のパーサーの単純化された部分問題として、標準の命令型言語 (Python、JavaScript など) に似た架空の言語の式のパーサーを実装しようとしています。その構文には、次の構造があります。

• 整数
• 識別子 ( [a-zA-Z]+)
• +and*と括弧を使用した算術式
• を使用した構造アクセス.(例: foo.bar.buz)
• タプル (例: (1, foo, bar.buz)) (あいまいさをなくすため、1 タプルは のように記述します(x,))
• 関数の適用 (例foo(1, bar, buz()))
• 関数はファーストクラスであるため、他の関数から返して直接適用することもできます（たとえば、関数を返す可能性があるfoo()()ため合法です）foo()

したがって、この言語のかなり複雑なプログラムは

結合性は

私は現在、非常に優れuu-parsinglibたアプリカティブ パーサー コンビネーター ライブラリを使用しています。

最初の問題は明らかに、直感的な式の文法 (が左再帰的であることです。しかし、コンビネータexpr -> identifier | number | expr * expr | expr + expr | (expr)を使用してその問題を解決できました (以下の例を参照)。pChainlparseExpr

残りの問題 (したがって、この質問) は、他の関数 ( f()()) から返された関数を使用した関数の適用です。繰り返しますが、文法は recursive のままexpr -> fun-call | ...; fun-call -> expr ( parameter-list )です。を使用してこの問題をエレガントに解決する方法はありuu-parsinglibますか? parsec(この問題は、attoparsecおよび他のパーサー コンビネーターにも直接適用されるはずです)。

以下の私の現在のバージョンのプログラムを参照してください。それはうまく機能しますが、関数の適用は識別子に対してのみ機能し、左再帰を削除します。

私は再帰的な適切な解析について学んでおり、アルゴリズムが機能していないと思われるいくつかのシナリオを考え出しています。それらの 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 つの解決策があります (一般に、必要な先読みの長さはプレフィックスの長さとともに増加するため): 継続の使用を必要とする完全な再帰的降下と、幅優先の再帰的降下です。