5

有什么方法可以将以下 Backus-Naur 形式 (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 ">>"

我很接近，但我不知道如何处理转义\和). 这将捕获命名组中的fieldnameand ：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>(\\\\|\\\)|[^\\\)])*)

我还将字段名更改为一个或多个非开放括号：

fieldname =     [^\(]+

把这些放在一起，我想出了解决方案。

于 2009-01-21T00:12:52.573 回答