問題タブ [formal-languages]

私は計算可能性に関する本でこれを読みました：

(クリーネの定理) ある言語が正則であるのは、結合、連結、反復の 3 つの操作を有限回数適用することによって有限言語から得られる場合に限ります。

私は「有限言語」に苦労しています。

この言語を考えてみましょう:L = a*

有限ではありません。{0, a, aa, aaa, ...}明らかに無限集合（0＝空の文字列）である集合です。

無限の言語ですね。つまり、「無限集合」とは「無限の言語」ということですよね？

明らかにa*正規言語です。そしてそれは無限の言語です。したがって、クリーネの定理により、正規言語になることはできません。矛盾。

よくわかりません。私は「有限言語」が何を意味するのか分からないと思います。

正式な文法に基づいて出力を生成するためのライブラリ (できれば .NET) が存在するかどうか疑問に思っています。

私はこれについて話している: https://en.wikipedia.org/wiki/Chomsky_hierarchy#Formal_grammars

したがって、次のように文法を指定します。

(非終端記号、終端記号、生産規則、開始記号)

それで：

そして、ライブラリはその文法のランダムな出力の例を次のように生成します。

このようなライブラリを作成または見つけた後に私がやろうとしているのは、出力を生成する方法を変更して、特定の例を他の例よりも多く生成するようにバイアスをかけることです。したがって、前の例では、よりバイアスをかけることができます。掛け算ではなく足し算を使ってより多くの式を生成します。

したがって、基本的にはプロダクション ルールに重みを割り当てて、有効なルールが複数ある場合に適用される可能性が高くなるようにします。

私の主な質問は、私の例のような正式な文法に基づいてランダムな出力を生成する最初のステップを実行できるライブラリがあるかどうかです。

アップデート

この問題についてもう一度考えてみると、さらにいくつかのメモがあります。

• ここでの問題の 1 つは、生産ルールの適用をいつ停止するかを知ることです。文法がある時点で停止することを確認するか、アルゴリズム/コードで式をさらに展開し続ける可能性を低くする方法を考案してください。

• これは理論的すぎる可能性があり、おそらくもっと実用的な方法があることに気づきました。つまり、本質的にこれと同じことを行うツールがいくつか存在する必要がありますが、特定の問題に特化した別の構文やアプローチ、またはより柔軟なものを使用するだけかもしれません。

私は、算術式と論理式、変数の割り当てと印刷を伴うサブ言語の EBNF にこの文法を持っています。

残念ながら、これらの 2 つのルールを理解することはでき ませ
ん

。彼ら。何か案が？
どうもありがとう ：-）

目標: セットの要素を任意の順序で 0 回または 1 回認識する文法を正式に定義する方法を見つけます。その後、それを解析して AST も生成したいと考えています。

例: 私の言語で有効な文字列のセットは{A, B, C}. これらの要素の任意の数のすべての有効な順列を認識する文法を定義したいと考えています。

構文的に有効な文字列は次のとおりです。

• (空の文字列)
• A、
• B A、 と
• C A B

構文的に無効な文字列は次のとおりです。

• A A、 と
• B A C B

明確にするために、CFG で可能なすべての順列を明示的に定義することは、私の目的には受け入れられません。より大きなセットを維持することは不可能だからです。

私が理解していることから、そのような言語は文脈自由言語のポンピング補題に失敗するため、解決策は文脈自由または規則的ではありません。

アップデート

私が求めているのは「順列言語」と呼ばれるもので、Benedek Nagyが文脈自由言語の拡張としていくつかの理論的な作業を行っています。

パーサー ジェネレーターに関しては、順列フェーズを使用してパーサーを実装するという話しか見つかりませんでした (リンク)。パーサーは明らかに、結果として得られる CFG のサイズに指数関数的な下限を持っています。

この問題に対する一種の解決策がANTLR に書かれています。問題を「コード化」するためにセマンティック述語を使用します。

次の簡単な文法を考えてみましょう。

S -> a | b

文法によって生成される文字列のセットは次のとおりです。

{a、b}

したがって、文法は文字列のセットを生成します。

文法のパーサーは、入力文字列を受け取り、その文字列が文法によって生成できるかどうかを判断します。

したがって、パーサーは文法のレコグナイザーです。

少なくとも、それはパーサーの 1 つの用途です。

しかし、多くの場合、パーサーは他の目的で使用されます。たとえば、文法のパーサーは、入力文字列を受け取り、入力データを含み、文法に準拠するツリー構造を作成する場合があります。

その場合、パーサーはレコグナイザーではなく、データ構造ビルダーです。

さまざまな種類のパーサーがあると結論付けています。

私は論理的に考えていますか？本当にさまざまな種類のパーサーがありますか?

パーサーが作成されたさまざまなタイプのリストを誰かが作成しましたか?

上記の記述に緩みや曖昧さがある場合はお知らせください。私は、これらの概念について正確に説明することを学ぼうとしています。たとえば、「文法は一連の文字列を生成する」ことに同意しますか? それは正確ですか？正しい？

BNF (または EBNF) 文法の最初 (最上位) の規則がエントリ ポイントを表すことは必須ですか? たとえば、ウィキペディアの BNF ページから、以下の米国郵便住所の文法には<postal-address>、最初の派生規則とエントリ ポイントがあります。

<postal-address>たとえば、2 番目の位置にルールを配置して、次の代替形式で文法を提供することは自由ですか。

私はpythonが初めてで、文法で可能なすべての文を生成しようとしています。文法は次のとおりです。

これが私の試みです。キュークラスを使用して体系的に実装しています。

私は無限ループに陥っています。また、sf の 1 つのコピーを変更すると、キュー内のすべても変更されます。どんな助けでも大歓迎です、どんな方向性、ヒントも素晴らしいでしょう

予想される出力は次のとおりです。