5

次のバッカスナウア記法（BNF）文法を.Net正規表現に変換する方法はありますか？（私はBNFに固執していませんが、私がやろうとしていたことを説明するための最良の方法かもしれないと思いました）。

<field> ::= "<<" <fieldname> <options> ">>"

<options> ::= "" | "(" <option> ")"

<option> ::= "" | 
             <option> <non-paren> | 
             <option> <escaped-character>

<escaped-character> ::= "\\" | "\)"

<non-paren> ::= any character but paren

<fieldname> ::= any string that doesn't contain "(" or ">>"

私は近くにいますが、エスケープ\とに対処する方法がわかりません)。fieldnameこれにより、およびoptionが名前付きグループにキャプチャされます。

<<(?<fieldname>.\*?)(\((?<option>.*?)\))?>>

編集

BNFの文法は思ったよりも錆びていたことがわかりました。

私が得ようとしていたのは、括弧は特殊文字であるということです。「オプション」セクション内では、スラッシュでエスケープする必要があります。（スラッシュもエスケープする必要があります）。

4

4 に答える 4

9

BNF は、正規表現では通常記述できない文脈自由言語を記述するために使用されます。文脈自由言語と正規表現を区別するのは、文脈自由言語では両方の側で同時に再帰を実行できることです。古典的な例は、括弧のバランスの問題です。

paren = paren paren
      | '(' paren ')'  <-- there are characters on both sides of the recursion
      | ''

あなたの場合、両面再帰を使用しないため、通常の言語になります。

fieldname = /(?:>?[^(>])+/    //No double >, but single ones are ok.
option = /(?:[^()\\]|\\.)*/   //No parens, unless preceeded by \

pattern = /<<(?<fieldname>   )(?:\((?<option>   )\))?>>/

それを一緒に入れて：

pattern = /<<(?<fieldname>(?:>?[^(>])+)(?:\((?<option>(?:[^()\\]|\\.)*)\))?>>/

いくつかの境界ケース:

<<f>oo(bar>>)>> --> ('f>oo', 'bar>>')
<<foo(bar\))>>  --> ('foo', 'bar\)')
<<foo(bar\\)>>  --> ('foo', 'bar\\')
<<foo\(bar)>>   --> ('foo\', 'bar')

編集：

余分な括弧文字 (およびバックスラッシュ) を<<and内でエスケープ>>する必要がある場合は、次のようにすることができます。

fieldname = /(?:<?[^()\\<]|<?\\[()\\])+/
options = /(?:[^()\\]|\\[()\\])*/
pattern = /<<(?<fieldname>   )(?:\((?<option>   )\))?>>/

/<<(?<fieldname>(?:<?[^()\\]|<?\\[()\\])+)(?:\((?<option>(?:[^()\\]|\\[()\\])*)\))?>>/

更新しました：

<<f>oo(bar>>)>> --> ('f>oo', 'bar>>')
<<foo(bar\))>>  --> ('foo', 'bar\)')
<<foo(bar\\)>>  --> ('foo', 'bar\\')
<<foo\(bar)>>   --> doesn't match
<<foo\((bar)>>  --> ('foo\(', 'bar')
于 2009-01-21T00:02:35.947 に答える
2

正規表現は正規言語を表します。文脈自由文法は、文脈自由言語を生成します。前者の言語セットは後者のサブセットであり、通常、文脈自由言語を正規表現として表現することはできません。

于 2009-01-21T00:54:51.630 に答える
0

私は答えを熟考しており、誰かが私をジャンプさせて止められることを望んでいました. :)

BNF の再帰的な性質は、通常、問題が BNF に適切にマップされている場合、RegExp に適切にマップされていないことを示す良い開始指標です。

認めざるを得ませんが、あなたの BNF を把握できるかどうかさえわかりません。例: x ::= << Boo ( abc321 ) >>

「オプション」のペアは c3、b2、および a1 であることをお勧めします。これは、char が有効な「オプション」であることを前提としています。空の文字列ではないオプションの有効な端末値を定義していません。それは本当にその意図ですか？

再帰的になりたくなかったと仮定すると... エスケープやその他すべての処理... コードを書いたほうがいいかもしれません。これは、文字列をたどって処理するのが他の何よりもはるかに簡単に見えます。あなたが望むものの感触は、先読みや振り返りのロジックが必要ないことを示唆しています。

于 2009-01-20T23:57:45.037 に答える
0

私はそれをうまく機能させることができたと思います...

<<(?<fieldname>[^\(]+)(?<options>\((?<option>(\\\\|\\\)|[^\\\)])*)\))?>>

私が考えることができたトリックは、オプション部分でした：

option =    (\\\\|\\\)||[^\\\)]

これは次のように変換されます: 二重スラッシュ、スラッシュ括弧、またはスラッシュ括弧以外の文字。

次に、それを 0 回以上含めて、"option" という名前のグループにまとめます。

((?<option>(\\\\|\\\)|[^\\\)])*)

また、フィールド名を 1 つまたは複数の開き括弧ではないものに変更しました。

fieldname =     [^\(]+

それをまとめて、私は解決策を思いつきました。

于 2009-01-21T00:12:52.573 に答える