問題タブ [context-sensitive-grammar]

私が理解している限り、いくつかの例外を除いて、ほとんどの言語は文脈自由です。たとえば、C++ では乗算または乗算をa * b表す場合があります。type * pointer_declarationどちらが行われるかは、コンテキスト、つまり最初の識別子の意味によって異なります。もう 1 つの例はname、VHDL でのプロダクションです。

構文形式が異なることがわかりますが、オプションのパラメーターが省略されている場合は一致する可能性がありますf。

Scala プラグインの設計者と話していて、依存関係が変わったときに AST を再評価するために AST をビルドするということを知りました。AST がある場合は、ファイルを再解析する必要はありません。AST ファイルの内容を表示する価値もあります。ただし、文法が文脈依存の場合、AST は無効になります (f別のファイルで定義された関数であり、後でユーザーが列挙型リテラルまたは未定義に再修飾したとします)。この場合、AST が変更されます。依存関係を変更するたびに、AST が変更されます。評価して作成方法を教えてほしいという別のオプションは、あいまいな AST を構築することです。

私の知る限り、パーサー コンビネーターはPEG のようなものです。最初に一致した生成を返すことであいまいさを隠し、f私の文法では最初の選択肢であるため、関数呼び出しに一致します。最初の成功に頼るのではなく、次の選択肢に進むコンビネータを求めています。最終的に、一致するすべての選択肢のリストが返されます。それは私にあいまいさを返すでしょう。

あいまいなファイル コンテンツ ツリーをユーザーに表示する方法はわかりませんが、依存ファイルを再解析する必要がなくなります。また、現代の言語設計がこの問題をどのように解決するかを知りたいです。

あいまいなノードが解析され、結果のあいまいさが返されたら、パーサーを収束させたいと思います。なぜなら、それを超えて解析を進めnameたいからであり、あいまいさのたびにファイルの最後まで解析したくないからです。f(10)単一の引数を指定した関数呼び出しや、後でインデックス付けされる配列を返す nullary 関数呼び出しのような状況によって、状況は複雑になります。そのため、f(10) は、func_call直接または再帰的にarr_indexing -> name ~ (expr). そのため、 のようにいくつかの並列ルールのように曖昧になることはありませんfcall | literal。一部のブランチは、再収束する前に 1 つのパーサーよりも長くなる場合がありますfcall ~ (expr) | fcall。

どのように解決していきますか？あいまいなコンビネータを PEG に追加することは可能ですか?

私の cs クラスの 1 つで、文脈自由文法と文脈依存文法の違いは、CSG では、生成規則の左側が右側よりも小さいか等しくなければならないということでした。

そのため、彼らが示した例の 1 つは、最初の規則が満たされないため、文脈依存文法は空の文字列を持つことができないというものでした。

ただし、通常の文法は文脈自由に含まれ、文脈自由は文脈依存に含まれ、文脈依存は再帰可算文法に含まれることを理解しています。

したがって、たとえば、文法が再帰的に列挙可能である場合、文脈依存型、文脈自由型、および規則型でもあります。

問題は、これが発生した場合、空の文字列を含む文脈自由文法がある場合、文脈依存としてカウントされる規則を満たさないことですが、矛盾が発生することです。文脈自由です。

私は Xtext を使用していますが、次の 2 つの問題について提案が必要です。

問題＃1

a、b、c の 3 つのルールがあるとします。そして、b と c が 1 回だけ出現することを除いて、これらの規則の任意のシーケンスを許可したいと思います。そのような文法をどのように書くのが最善でしょうか?

これが私が思いついたものです：

ルート文法を記述するより良い方法はありますか? b と c は依然として厳密な順序である必要があり、これは理想的ではありません。

問題＃2

この文法を見てください：

この文法を使用して、次のような言語を記述できると予想しました。

ただし、「c」の下にノード「y」が表示されるため、エラーが発生します。何故ですか？「y」がルールの 1 つでターミナルとして使用されているため、文法の他の場所には表示されないためですか?

この文法を修正するには？

関連する質問/資料:

• a^nb^n を Java 正規表現とどのように一致させることができますか?

• 数値が正規表現で素数かどうかを判断する方法は? （単項素数マッチングを扱いますが、基数≧2を探していますが、それでも良いトリックであり、これについて考えさせられた理由）

• http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html

よく知られているように、さまざまなプログラミング言語でサポートされている「正規表現」は、形式的な意味で非正規の言語を生成し、上記の資料で示されているように、少なくともいくつかの文脈依存言語を認識できます。

言語 L = {x | x は基数 10 の素数です。} は、素数性が線形有界オートマトンによってテストできるため、文脈依存言語です (ただし、ポンピング レンマ引数による文脈自由言語ではありません)。

では、基数 10 のすべての素数を正確に受け入れる Perl または Java の正規表現を作成することは可能でしょうか? 2 以上の他の基数に置き換えるか、すべての合成数を正確に認識する方が簡単だと思われる場合は、自由に置き換えてください。

たとえば、エスケープを使用して任意の Perl コードを実行することは、不正行為と見なされます。置換を繰り返し行うこと (簡単にチューリング完全になる) も範囲外です。全体の作業は正規表現内で行う必要があります。この質問は、正規表現が実際にどれほど強力であるかの境界に関するものです。

私が教えてくれたように、最初のプロダクション ルールはコンテキスト フリーです (左側が右側よりも小さいため) が、2 番目のプロダクション ルールではそうではありません (左側の長さが右側と等しいため)。

さて、このステートメントでこの文法について何が言えるでしょうか。それは文脈自由ですか？

上記の言語の文脈依存文法の設計方法を説明してください。私は文脈依存文法が初めてです。

セクション「Type - 1 Grammar」の下のChomsky Classification of Grammarsで説明されているように、Chomsky によって記述された文脈依存言語の要素を生成することに興味があります。

(基本的に、標準の文脈自由文法に似ていますが、ターミナルを含む生産規則の左側に複数の記号を許可します)。

Prolog の定節文法については知っていますが、それらとチョムスキーの文脈依存言語との間の明確なマッピングは見当たりません。DCG フレームワークを使用して、左側に複数の記号を含むプロダクション ルールを記述する「普遍的な」方法はありますか?それとも、個々の言語ごとにアドホックなアプローチが必要ですか?