問題タブ [grammar]

（空白で区切られた）ペアのリストを次の形式で解析したい

どこ：

• NAMEには、空白と等号以外のすべてを含めることができます
• VALUEには、空白以外のものを含めることができます（等号を含む）。

問題は、パーサーを次のような入力と一致させることです。

'NAME EQUALS VALUE'単一のトークンとしてではなく、個別のトークンとして'VALUE'。

PS。これを直接コーディングするのは簡単ですが、より大きなパーサーのコンテキストでこれが必要です。

Ironyを使用して小さなパーサーを作成しようとしています。残念ながら、「シフト削減の競合」が発生します。文法は私の得意分野ではなく、この 1 つの小さなことを完了するだけで済みます。エラーを生成する簡略化された文法は次のとおりです。

「shift-reduce 競合」とは何を意味し、どうすれば解決できますか? それは私の文法があいまいであることを意味していると私は推測していますが、私は自分の論理を十分にひねってその方法を理解することはできません.

追加:明確にするために - 「asd」は単なるリテラル文字列「asd」です。したがって、次の式がこの文法によって解析されると予想されます。

追加 2:言い忘れましたが、文法の語根は ですLogicalExpression。

追加 3:ああ、わかった! あいまいさは、

次の 2 つの異なる方法で解釈できます。

しかし、どうすればこれを解決できますか？OK、AND または OR のどちらか一方を他方よりも強くすることができます (いずれにせよ意図していました)。しかし、オペレーターが 1 人しかいない場合でもエラーが表示されるようになりました。つまり、これも同じエラーを生成します。

この場合、私はこれが欲しい：

これに解析されます：

これを行うためのあいまいでない方法は何ですか?

追加 4:わかりました！

これは、演算子の優先順位を NOT->AND->OR として、すべてのブール式を解析します。「asd」は、用語を意図した表現に置き換えることができます。

私はこの 1 年間、ポーカー ハンドの歴史を解析してきましたが、解析全般についてかなりのことを学びました。

私たちは正規表現から始めましたが、すぐに拡張が容易ではないことに気付きました。Ruby から C++ へと言語を飛ばして、最終的には変更しなければならないのはアルゴリズムであることに気づきました。

Boost::Spirit を手に取ったところ、元の速度の 10 倍以上のオーダーで速度が劇的に上昇するのがわかりました。その後、Java にスキップし、現在、antlr を使用して各サイトの文法を作成しています。これは間違いなくこれまでで最速の方法であり、「完全な」文法の観点から自分がどこに立っているかを正確に知ることができるため、非常に徹底的です。残念ながら、私はこれらの文法を扱うのに信じられないほどの時間を費やしてきました。

とにかく、当面の質問の背景については十分です-私が気付いていない「エキゾチックな」またはあまり知られていない解析手法はありますか? 私は、文法の字句解析/解析と、他の劣った正規表現/ループ方法しか知りません。

ポーカー ハンドの歴史に詳しくない方のために、構造がどのようなものかわかるように投稿します。

情報を収集する他の方法 (スクリーンスクレイピングや dll インジェクションなど) についてはよく知っていますが、ハンド履歴を構造化データに変換する必要性がまだ残っているため、次のような情報を取得する方法のみを調べています。正規表現/文法...

何か見つからない場合は、文法を ocamllex/ocamlyacc で書き直そうと思います。

アップデート

fyi: 正規表現の速度は ~60 ハンド/秒でしたが、文法は 600 ハンド/秒を処理していました... データがすべて整理された後、ハンド全体が xml に変換されます... 20 ～ 30 の正規表現が必要です (最後のカウント) 解析したいサイトごとに....文法側の各サイトには、非常に多くのレクサー/パーサールールを備えた独自の文法があります(ただし、コードサイズはまだ小さいです)

私はドラゴンブックを持っていて、それを読んでいます-これにより、ocamllex/ocamlyacc を使用することに興味がなくなりました....ここでのゲームの名前はスピードです..

ミニ言語の組み込みをサポートするプログラミング言語は非常に多くあります。PHP は HTML に埋め込まれています。XML は JavaScript 内に埋め込むことができます。Linq は C# に組み込むことができます。Perl には正規表現を埋め込むことができます。

考えてみれば、ほとんどのプログラミング言語はさまざまなミニ言語としてモデル化できます。たとえば、Java は、少なくとも 4 つの異なるミニ言語に分割できます。

• 型宣言言語 (パッケージ ディレクティブ、インポート ディレクティブ、クラス宣言)
• メンバー宣言言語 (アクセス修飾子、メソッド宣言、メンバー変数)
• ステートメント言語 (制御フロー、順次実行)
• 式言語 (リテラル、代入、比較、算術)

これらの 4 つの概念言語を 4 つの異なる文法として実装できれば、複雑なパーサーやコンパイラの実装で通常見られるスパゲティ現象の多くを確実に減らすことができます。

私は以前にさまざまな種類の言語のパーサーを実装しました (ANTLR、JavaCC、およびカスタム再帰降下パーサーを使用)。言語が非常に大きく複雑になると、通常、1 つの huuuuuuge 文法になってしまい、パーサーの実装は次のようになります。本当に醜い、本当に速い。

理想的には、これらの言語のいずれかのパーサーを作成するときは、構成可能なパーサーのコレクションとして実装し、それらの間で制御をやり取りするのがよいでしょう。

注意が必要なことは、多くの場合、含まれる言語 (Perl など) が、含まれる言語 (正規表現など) の独自のターミナル センチネルを定義することです。良い例を次に示します。

このコードでは、メインの perl コードが非標準の終端 "|" を定義しています。正規表現用。正規表現パーサーは、親パーサーに相談しないと式の終端を見つける方法がわからないため、正規表現パーサーを perl パーサーとは完全に異なるものとして実装するのは非常に困難です。

または、Linq 式を含めることを許可する言語があったとしますが、(C# のように) セミコロンで終了する代わりに、Linq 式を角かっこ内に表示することを義務付けたいと思いました。

親言語の文法内で Linq 文法を定義した場合、構文の先読みを使用して括弧の囲みを見つける「LinqExpression」の明確な生成を簡単に作成できます。しかし、親の文法は、Linq 仕様全体を吸収する必要があります。そして、それはドラッグです。一方、別の子 Linq パーサーは、外部のトークン型の先読みを実装する必要があるため、停止する場所を見つけるのに非常に苦労します。

そして、Linq パーサーは親パーサーとはまったく異なる一連のトークン化ルールを定義するため、個別の字句解析/解析フェーズを使用することはほぼ除外されます。一度に 1 つのトークンをスキャンしている場合、親言語の字句解析器に制御を戻すタイミングをどのように知るのでしょうか?

皆さんはどう思いますか？より大きな親言語内にミニ言語を含めるために、明確で分離された構成可能な言語文法を実装するために、今日利用できる最良の手法は何ですか?

LALR(1) パーサー ジェネレーター (Bison ですが、問題はそのツールに固有のものではありません) を使用して単純な文法を解析しようとしていますが、shift-reduce の競合が発生しています。これらの修正について私が見つけたドキュメントやその他の情報源は、次の1つ以上を言う傾向があります:

• 文法があいまいな場合 (if-then-else のあいまいさなど)、言語を変更してあいまいさを修正します。
• 演算子の優先順位の問題である場合は、優先順位を明示的に指定してください。
• デフォルトの解像度を受け入れ、ジェネレーターに文句を言わないように伝えます。

ただし、これらのどれも私の状況には当てはまらないようです: 私が知る限り、文法は明確です (もちろん、先読みの文字が 1 つしかないためあいまいですが)、演算子は 1 つしかなく、デフォルトの解決では解析エラーが発生します正しく形成された入力で。文法の定義を作り直して、上記のバケツに当てはまらない shift-reduce 競合を取り除くテクニックはありますか?

具体的に言うと、問題の文法は次のとおりです。

その意図は、"[A-Za-z]+" または "[A-Za-z] -> [A-Za-z]+" の形式のセミコロンで区切られた行を解析することです。

形式的に構造化されたほぼすべての情報セットでは、最初から最後まで、または場合によっては最後から最初に向かって読み始めます (住所など)。しかし、SQL、特に SELECT クエリでは、適切に理解するためにその意味は、FROM 句の途中から開始する必要があります。これにより、特にネストされた SELECT クエリが含まれている場合、長いクエリが非常に読みにくくなる可能性があります。

通常、プログラミングで何かが意味をなさないと思われる場合、その背後には歴史的な理由があります。FROM の代わりに SELECT で始めるのは意味がありません。それがそのように行われる理由を誰かが知っていますか？

次のようなおもちゃの文法があるとします: (出力がより自然に見えるように更新されます)

例：「犬が赤い魔法使いを蹴る」、「鳥が斑点のある魚に出会う、または魔法使いが縞模様の犬と結婚する」

合計n 個のVs + As + Nsを含まなければならないという制約に従って、この文法からどのように文を作成できますか。整数を指定すると、センテンスにはその数の端末が含まれている必要があります。(もちろん、この文法では可能な最小のnは 3 です)。

私はANTLR文法を持っており、オプションのパラメーターを許可する関数を自分の言語で定義しています。オプションのパラメーターがコード生成ブロック内で渡されているかどうかを確認するにはどうすればよいですか？

私は基本的に、この架空のツリー文法ステートメントのようなことを行うための構文を探しています。

ドキュメントへの提案やポインタは大歓迎です！

javacc で非常に単純な文法のパーサーを作成しています。まとまり始めていますが、現時点ではこのエラーに完全に行き詰まっています:

問題の入力行はz = y + z + 5

問題を引き起こしているのは、varDecl() から呼び出される式です。

式は次のようになります。

このエラーが発生する理由がわかりません。洞察をいただければ幸いです。

私は有限オートマトンと文法テストのために勉強していますが、この質問に行き詰まっています:

私は、私の作品は次のようにすべきだと信じています。

C の私のプロダクションでは、m と n の数をどのように記憶できますか? これはむしろ文脈自由文法でなければならないと思います。