問題タブ [context-free-grammar]

正規表現エンジンを作成しようとしています。手動で再帰降下パーサーを書きたいと思います。正規表現の言語 (正規表現で記述できる言語ではない) の左再帰のない文脈自由文法はどのようになりますか? シンタックス シュガーをリファクタリングする、つまり に変更するのが最も簡単でしょうa+かaa*? 前もって感謝します！

私はシミュレーターを作成しており、さまざまなコマンドライン引数のセットを使用して、シミュレーターの多くのインスタンスを呼び出して調査を実行したいと考えています。私はこの質問と他のいくつかを読みましたが、それらは近いように見えますが、実際には特定の正規表現を満たすランダムデータを探しているわけではありません。正規表現に一致するすべての文字列のセットが必要です。入力ファイルの例は次のようになります。

また：

そして以下を生成します：

このようなものはすでに存在すると思いますが、検索する正しい用語がわかりません。どんな助けでも大歓迎です。必要に応じて抽象的な手法やアルゴリズムを自分で実装することもできますが、それが既存のツールである場合は、(少なくともビールのように) 無料で Linux で実行することを好みます。

私はおそらくいくつかの詳細を省略していることを知っており、前もって多くの詳細を人々に殺到させるのではなく、必要に応じて適切なことについてより具体的にすることができます. 私がこれを間違った方法で行っている可能性は十分にあり、別の方法で問題を解決したとしても、すべての解決策を歓迎します.

最も重要なことは、生成する文字列の「交差積」に引数オプションを追加したい場合、このソリューションでは追加の解析コードを記述する必要がないことです。for変数の数または性質を変更するたびに変更する必要がある、各「変数」に対する一連のネストされたループでこれを行う Perl スクリプトが既にあります。

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

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

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

http://www.cs.chalmers.se/Cs/Research/Language-technology/BNFC/

ラベル付きのBNFを記述して、BNFCにINIパーサーを生成させるにはどうすればよいですか？

私は今のところo__Oしか得ていません！

o__O行き詰まっています..。

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

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

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

これは、カンマを区切り文字としてネストされた中括弧の言語を記述することになっている文法です。

文法が受け入れて拒否することを期待する文字列の例をさらにいくつか示します。

承認：

拒絶：

Perl を使用して、Gmail が提供するものと同様の検索文字列を解析したいと考えています。入力例は、「tag:thing by:{user1 user2} {-tag:a by:user3}」です。のような木構造に入れたい

一般的な規則は次のとおりです。

1. スペースで区切られたトークンは、デフォルトで AND 演算子になります。
2. 中括弧内のトークンは代替オプション (OR) です。中かっこは、フィールド指定子の前後に配置できます。つまり、「by:{user1 user2}」と「{by:user1 by:user2}」は同等です。
3. ハイフンで始まるトークンは除外されます。

これらの要素は、結合してネストすることもできます。たとえば、「{by:user5 -{tag:k by:user3}} など」です。

これらの規則を表す文脈自由文法を書き、それをツリーに解析することを考えています。これは不要ですか？(これは単純な正規表現を使用して可能ですか?)

文脈自由文法の解析に推奨されるモジュールは?

(最終的に、これは DBIx::Class でデータベースクエリを生成するために使用されます。)

私の質問は：

L = {x in {a,b}* | x は a と b の数が等しい}

文法を作成できるので、これが文脈自由言語であることはわかっています (e はイプシロン):

通常の言語と交差する文脈自由言語は文脈自由であるという事実を使用して、それが文脈自由であることを証明することもできます。

これは文脈自由言語であるため、CFL のポンピング レンマによれば、ポンピング長 p よりも長い任意の文字列をポンピングできるはずです。ただし、文字列 s = a^pb^pa^pb^p を選択した場合、この文字列はポンピングできないため、言語は文脈自由であってはなりません。

どこが間違っていますか？

任意の IL から CFG を構築し、その CFG を IL に変換したいと考えています。もちろん、CFG 内の頂点の順序は、元の IL 命令の順序と同じではありません。

これは問題ありませんが、いくつかのものが過度に複雑になります。想像：

これは次のようなフロー グラフになります: (ジャンプ B) -> (ジャンプ C) -> (リターン) これはもちろん単純化された例ですが、CFG から変換するときの問題を示しています。

学界でこのトピックに関する情報はありますか? グラフをボトムアップでトラバースするのは非常にエレガントだと思いましたが、より複雑なケースではうまくいきません。

解決策は、トップダウンで歩いて CF マージを検索することかもしれませんが、その場合、ループを正しく処理できません。したがって、これを正しく行う唯一の方法は、可能性のある CF マージが発生した場合にそれを検索することのようです。そうでない場合は、ループが必要です。つまり、ループが優先され、その後に続くパスが評価されます。これは解決可能な問題のように思えますが、非常にコストがかかるため、問題に対するより洗練された解決策が存在する可能性があります。また、「break」ステートメントについて考えると、ループによって CF マージが発生する可能性もあります。

完全な EBNF 文法を含むW3C のXML 1.1仕様に基づいて、コンパイラ ジェネレータを使用して XML トランスレータを実装するというアイデアを考えています。

より正確には、このツールを学びたいので、Qi-YACCを使用する予定です。これは、コンパイラ-コンパイラを使用する最初の試みです。

私が実装しようとしている最初の種類の変換は、非常に簡単です: XML からS-EXPRsへ。その後、翻訳者を一般化する予定ですが、これは私の質問のポイントではありません。

この種のプロジェクトに何か大きな落とし穴があると思いますか? EBNF を使用して XML を翻訳するのは悪い考えだと読んだことがあります。なぜだろう。また、Qi 言語に既に XML パーサーがあったわけではないので、ここで車輪を再発明するつもりはまったくありません。