2

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

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

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

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

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

  • A A、 と
  • B A C B

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

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

アップデート

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

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

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

4

1 に答える 1

1

代替文字列のセットが固定されており、たとえばサイズnが事前にわかっていると仮定すると、サイズO(n!)の (コンテキストフリーではない) 文法を考え出すことができます。これは、すべての順列を列挙するよりも漸近的に小さくなるわけではないため、良い解決策とは言えません。私は、この文法は文脈依存文法として再定式化できると信じています(ただし、以下で提案している形式ではそうではありません)。

質問で言及されている例{a, b, c}では、そのような文法の 1 つが次のとおりです。慣例に従って、終端記号には小文字を使用し、非終端記号には大文字を使用しています。 Sは最初の非終端記号です。

S ::= XabcY
XabcY ::= aXbcY | bXacY | cXabY
XabY  ::= ab | ba
XacY  ::= ac | ca
XbcY  ::= bc | cb

非終端記号であり、まだ確定されていないプロダクションの部分文字列Xを囲みます。この部分文字列は、最終的に と の間で指定された端子の順列に(任意の順序で)Y置き換えられます。XY

于 2013-08-26T21:24:36.423 に答える