問題タブ [recursive-descent]

私は C++ で SQL 選択ステートメントの (手書きの) 再帰降下パーサーを作成しています。作成した解析ツリーが正しいかどうかを知る必要があります。確認したいのですが、SQL 解析ツリーの適切なソースがありませんでした。私のアプローチ方法は、プロダクションごとに関数を作成し、その関数で結果をルート ツリーに追加することです。誰でも私を助けることができますか？前もって感謝します。

私は現在、システムソフトウェア開発のクラスに参加しています。架空のマシンのアセンブリ言語用の 2 パス アセンブラを作成しています。トークナイザーを実装し、このプログラムを抽象化して表現するために必要なすべてのクラスを実装しました。残っているのは (後のフェーズでコード ジェネレーターを実装する以外に) トークンを解析することだけです。ここで私は大きな問題を抱えています。私はこれを再帰降下パーサーとして実装することを選択しています。これは、私が現在経験している唯一の手法であるためです...しかし、構文エラーでアセンブリを停止することは許可されていません。たとえば、ユーザーが無効な構文でロード ワード命令を発行した場合、それを NOP に置き換えます。ユーザーが不適切なラベルを付けた場合は、単純に無視します。ユーザーが不明な文字を行に配置した場合、それらは破棄されます。

簡単そうに思えますが、これを実装すると、再帰降下パーサーの重要なルールの 1 つ (私が理解していること) を破ることになります。考えられる修正可能な構文エラーをすべて考慮する必要があるため、各関数は別の関数を呼び出す前に複数のトークンをプルします。アセンブリを停止することはできず、ユーザーが何をしようとしているのかをインテリジェントに判断するには、現在のコンテキストに関する十分な情報が必要なので、1 つの関数内で多くのことを処理する必要があります。

これにより、プログラムは真の再帰降下パーサーから半有限状態機械に変わります。私はこれをひどくやっているように感じますが、これを実装する方法が他にわかりません。誰か提案/アイデアはありますか?

ところで - ANTLR やその他のパーサー ジェネレーターなどのツールを使用することは許可されていません。

ありがとう。

現在、プログラミング言語用の（非常に）小さなインタープリター/コンパイラーを作成しようとしています。言語の構文を設定したので、言語の文法を書き留める必要があります。少し調査した結果、LL(1) パーサーが最も使いやすいと思われるため、LL(1) パーサーを使用するつもりです。

私はこの分野には不慣れですが、収集した内容から、BNF または EBNF を使用して構文を形式化することを強くお勧めします。ただし、すべての文法が LL(1) パーサーを使用した実装に適しているわけではないようです。したがって、LL(1) 形式で文法を記述するための正しい (または推奨される) アプローチは何かと考えていました。

助けてくれてありがとう、チャーリー。

PS: Haskell の Parsec ライブラリを使用してパーサーを作成するつもりです。

編集: また、SK ロジックによると、Parsec は無限先読み (LL(k) ?) を処理できますが、質問は依然としてそのタイプの文法を表していると思います。

レクサーとパーサーの典型的な構成を知っています。レクサーはソースコードを読み取り、トークンを生成します。トークンはパーサーに送信され、パーサーはそれらを文法生成の終端記号として使用します。典型的な再帰下降パーサーでは、開始非終端記号を表すトップレベル関数を呼び出すことから始めます。この関数は他の関数を呼び出し、レクサーからトークンごとに読み取ります。

しかし、同じレクサーの上に2つの異なるパーサーが必要な場合はどうなりますか？

つまり、レクサーでの不要な重複作業を避けるために、同じソースを複数回読み取ることは望ましくないため、つまり、複数のパスを許可しないため、両方とも同じ場所から読み取ることになります。順番に次のトークンが生成されたときに、両方のパーサーが同時にそれを消費するようにしたいだけです。

ただし、これらのパーサーの1つで呼び出すことができる最上位関数は1つだけです。両方を同時に呼び出すことはできません：/

これらのパーサーをある種のステップモードで実行する方法はありますか？つまり、新しいトークンを取得したら、それを両方のパーサーに次々に渡したいのですが、その1つのトークンだけ進めて、内部状態とデータ構造を可能な限り更新し、すぐに返します。別のトークンを待つ。

この種の構成はこれまで見たことがありません。そのようにパーサーを構築することは可能ですか？この種のパーサーをコードでどのように構造化できるかについての資料はありますか？名前はありますか？

編集1： パーサジェネレータツールを使用したくありませんが、この種のものが内部でどのように機能するかを学びたいので、自分でコードを記述します。

ParentIdを使用して自分自身に結合するナビゲーション付きのテーブルがあります。各レコードの子孫の数を計算しようとしています。再帰でカウンターをインクリメントする必要があることはわかっていますが、どうすればよいかわかりません。

どんな助けでも大歓迎です！

追加されたレベルを編集し、再帰的にインクリメントします：

再帰下降パーサーの書き方について2つの質問があります。

1つ目は、いくつかの異なる非終端記号の1つと一致する非終端記号がある場合はどうなりますか？どちらが正しいかをどのように確認しますか？

次に、ASTをどのように構築しますか？YACCを使用すると、非終端記号のすべてのインスタンスに対して実行するコードを記述でき、ルールの「値」を参照する特別な変数があります。再帰下降パーサーで同様のことをどのように行いますか？

次の EBNF に対して、PHP で再帰降下パーサーを作成しようとしています。

同様の質問で推奨されているこのガイドに従いました。（投稿前に調べました）

ほとんどの場合、私はそれがどのように機能するかを理解し、文法を理解しています. 問題は私の構文にあると思います。私は PHP が初めてなので、W3Schoolsを参照しています。現在、コードで次のエラーが発生しています。

このエラーを調べてみましたが、うまくいきませんでした。間違ったパラメーターを入力した人に関する投稿を読みましたが、その関数にパラメーターが設定されていません。ここで欠けているPHPについて何かありますか?

以下は私のコードです。文法の解析ツリーに基づいているため、ロジックは正しいと思います。$input は、HTML ページのフォーム ボックスから取得されます。また、PHP4 には str_split 関数が組み込まれていないことを発見したときに、別の投稿から str_split 関数を取り上げました。

したがって、基本的に、そのエラーの原因とその理由を知りたいのですが、このパーサーを作成するという点で正しい軌道に乗っています。

コメント、提案、批判、水風船、トマトに感謝します。私の投稿を読んでくれてありがとう。素晴らしい昼/夜をお過ごしください。

主に学習目的で、適切な再帰パーサーをハードコーディングしていますが、いくつかの問題に遭遇しました。

例として、CSS3 文法からのこの短い抜粋を使用します。

まず、とnamespace_prefixの両方のオプション部分であることに気付きませんでした。これは、プロダクションに一致する入力が盲目的に考慮されていたため、入力が与えられたときに常に失敗することにつながりました。type_selectoruniversaltype_selector*|*namespace_prefix

まともな再帰は簡単ですが、プロダクションに落ち着く前に（より適切な言葉がないため）多くの探索的再帰を行う必要があるというのが私の理解です。そこで、ブール値を返すようにプロダクションのシグネチャを変更しました。このようにして、特定のプロダクションが成功したかどうかを簡単に判断できました。

リンクされたリストのデータ構造を使用して任意の先読みをサポートし、このリストを簡単にスライスして生産を試み、生産が成功しない場合は出発点に戻ることができます。ただし、プロダクションを試している間、可変状態を渡し、ドキュメント オブジェクト モデルを構築しようとしています。制作が成功するかどうかはわからないので、うまくいきません。制作がうまくいかない場合は、どうにかして行った変更を元に戻す必要があります。

私の質問はこれです。抽象構文ツリーを中間表現として使用し、そこから移動する必要がありますか? これは、この問題を回避するために一般的に行うことですか? 問題は主にドキュメント オブジェクト モデルが再帰に適したツリー データ構造ではないことにあると思われるためです。

私はこの文法を持っています:

私は部分的に再帰降下パーサーを書きました:

しかし、いくつかの部分で何をすべきかわかりません。たとえば、expr が左辺値になり、その最初の項目が expr になる方法などです。

左再帰は、再帰降下構文解析の基礎の上に構築された多くのパーサー ジェネレーターにとって大きな問題のようです。どの言語でも、それをサポートする PEG ベースのパーサー ジェネレーターを探しています。