問題タブ [grammar]

私は最近、パーサー（言語/文脈自由文法用）がどのように機能するかを自分自身に教えようとしていますが、1つを除いて、そのほとんどは理にかなっているようです。特にLL（k）文法に注目しています。このアルゴリズムでは、2つの主要なアルゴリズムがLLパーサー（スタック/解析テーブルを使用）と再帰下降パーサー（単に再帰を使用）のようです。

私が見る限り、再帰下降アルゴリズムはすべてのLL（k）文法で機能し、場合によってはそれ以上で機能しますが、LLパーサーはすべてのLL（k）文法で機能します。ただし、再帰下降パーサーは、LLパーサーよりも実装がはるかに簡単です（LLパーサーがLRパーサーよりも単純であるのと同じです）。

だから私の質問は、どちらかのアルゴリズムを使用するときに遭遇する可能性のある利点/問題は何ですか？同じ文法セットで機能し、実装が難しいのに、なぜ再帰下降よりもLLを選ぶのでしょうか。

私が取り組んでいるオンラインプロジェクトでは、オープンソースの文法チェッカーを探しています。私はグーグルを検索しましたが、いくつかの良い結果（http://www.link.cs.cmu.edu/link/など）がありましたが、皆さんはこのトピックについてどう思いますか。

デスクトップベースではなくオンラインで使用できるようにするためにこれが必要ですが、これが私が持っている唯一の実際の仕様です。スペルチェッカーが組み込まれている場合はプラスになりますが、その目的のためにいつでも別のプロジェクトを使用できます。

助けてくれてありがとう。

こんにちは！

セミコロンやバックスラッシュを必要とせずに複数行の式を処理する単純な ANTLR 文法を作成するにはどうすればよいですか?

式の単純な DSL を作成しようとしています。

全体として、アプリケーションでスクリプトに名前付きの初期値をいくつか提供し、最終結果を引き出す必要があります。しかし、私は構文に夢中になっています。次のような複数行の式をサポートしたいと思います。

私は次のような ANTLR 文法から始めました。

それは簡単に思えますが、私はすでに改行に問題があります:

グラフィカルに、org.antlr.works.IDE で:

意思決定は、複数の選択肢を使用して NL に一致させることができます http://img.skitch.com/20090723-ghpss46833si9f9ebk48x28b82.png

私は文法を蹴散らしましたが、常に期待される動作に違反してしまいます:

• ファイルの末尾に改行は必要ありません
• 空行は許容されます
• ポンド記号以降の行はすべてコメントとして破棄されます
• 代入はセミコロンではなく行末で終わる
• 括弧で囲まれている場合、式は複数の行にまたがることができます

これらの特徴の多くを備えた ANTLR 文法の例を見つけることができます。それらを切り詰めて表現力を必要なものだけに制限すると、何かが壊れてしまうことがわかりました。他は単純すぎて、表現力をつけながら壊していきます。

この文法でどの角度を取るべきですか? 自明または完全なチューリング完全言語ではない例を教えてください。

Git ログで現在時制を使用するのが好きです (たとえば、「追加された機能」ではなく「機能を追加」)。現在、ログメッセージの最初の単語が「ed」で終わる場合にコミットを中止する非常に単純な Git フックがありますが、より堅牢なソリューションが必要です (「より堅牢」とは「完全に不自由ではない」ことを意味します)。次の行に沿ってスクリプトを記述できる文法チェッカーはありますか?

完璧な解決策は必要ありません。/^\w*ed\W/ に一致するよりも優れたものだけです。

SQLiteとJSONのウェブサイトで文法グラフを見ます。これらのきれいな画像を生成するには、どのプログラムを使用できますか?

これは私が立ち往生しているラボの課題です。

この文法を受け入れる必要があります(ab)*b。これは基本的に、任意の数の「ab」と b で終わることを意味します。

私はこのコードを書きましたが、どういうわけか、最初の 2 文字だけをチェックします。

空でない場合（したがってブール値の意味で真）@a = @b || @cを取得することを目的として、割り当ての複雑なバリエーションを実行したいと思います。ドキュメントには、私にはできないことが明記されています。（そしてそれは事実についても正しいです！）@b@c

「||」、「//」、および「&&」演算子は、最後に評価された値を返します（0または1を返すCの「||」および「&&」とは異なります）。

[...]

特に、これは、割り当てのために2つのアグリゲートから選択するためにこれを使用してはならないことを意味します。

残念ながら、それは本当に私に理由を教えてくれません。

私が予想したことはこれでした：

• @a =は配列の割り当てであり、右側にリストコンテキストを誘導します。
• @b || @cは右側で、リストコンテキストで評価されます。
• ||Cスタイルの論理和論理和です。左から右に評価し（必要な場合）、コンテキストを伝播します。
• @bリストコンテキストで評価されます。true（つまり、空でない）の場合、それが返されます。
• そうでない場合は、@cリストコンテキストでも評価され、返されます。

明らかに、私の最後から2番目のステートメントは間違っています。なんで？そして、さらに重要なことに、ドキュメントまたはソースのどの部分がこの動作を説明していますか？

PS：質問の範囲外ですが、三項演算子を使用するというドキュメントの提案を控える理由は、私@bが実際には一時的なもの（関数呼び出しの結果）であるためです。

私は ocamlyacc と ocamllex で書かれたパーサーとレクサーを持っています。行末のセミコロンを忘れた場合のように、解析するファイルが途中で終わっても、アプリケーションは構文エラーを発生させません。私はEOFを発生させてキャッチしているため、lexerが未完成のルールを無視しているためだと認識していますが、構文エラーを発生させるにはどうすればよいですか?

これが私の現在のパーサーです（簡略化）、

およびレクサー (簡体字)、

サンプル入力ファイル、

解決策の 1 つは、コマンド ルールに再帰呼び出しを最後に追加し、空のルールを追加することです。これらはすべて、メイン プログラムに戻るリストを作成します。私はおそらくEofを期待として解釈し、レクサーのエラーではなく終了条件を解釈していると思いますが、これは正しいですか?

式処理文法 (ネストされた括弧などを処理する) を実装しようとしています。これまでのところ、次のものがありますが、一部のケースに対応できません (成功/失敗のケースは、次のコード ブロックの後に表示されます)。何が起こっているか知っている人はいますか？

注: varname +=およびvarname =は、XText の追加の AST 生成ヘルパーにすぎません。今のところは気にしないでください。

そして、ここに解析/失敗のリストがあります: