BNF到正则表达式

Question

有什么办法将下面的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>.*?)\))?>> 

---

编辑

事实证明，我在BNFs rustier比我想象的。

我想知道的是，parens是特殊字符。在“选项”部分，他们必须用斜线转义。 （并且斜杠也必须被转义）。

Answer 1

我一直在思考一个答案，并希望有人会跳我，所以我可以停下来。 :)

BNF的递归性质通常是一个很好的开放性指标，如果您的问题很好地映射到BNF，则它不能很好地映射到RegExp。我不得不承认，我不知道我甚至可以弄清楚你的BNF。例如： x :: = < < Boo（abc321）>>

建议您的'选项'对是c3，b2和a1。这假定一个char是一个有效的'选项' - 你没有为不是空字符串的选项定义任何有效的终端值。这真的是意图吗？

假设你不想递归... 处理转义和其他一切... 你可能会更好地编写代码。这看起来好像比任何其他事情都更容易穿过弦乐并处理。你想要的感觉表明你不需要任何预见或回顾逻辑。

Answer 2

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') 

---

编辑：

如果你想要任何额外的括号characte RS（和回斜线）有内部<<和>>进行转义，你可以做这样的事情：

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') 

Answer 3

我想我设法得到它的工作。 ..

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

，我能想到的是选择部分的诀窍：

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

转换为：双斜杠，斜杠或非斜杠字符。

然后包括它0次或更多次和一个名为“选项”组中的一巴掌吧：

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

我也改变字段名是一个或多个非开放式的括号：

fieldname =  [^\(]+ 

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

Answer 4

正则表达式表示常规语言。上下文无关语法生成上下文无关语言。前一种语言集是后者的一个子集，在一般情况下，您不能将上下文无关语言表达为正则表达式。