Преобразование грамматики формы Бэкуса-Наура в регулярное выражение .Net - PullRequest
Новая
       8

Преобразование грамматики формы Бэкуса-Наура в регулярное выражение .Net

4 голосов
/ 21 января 2009

Есть ли способ преобразовать следующую грамматику Бэкуса-Наура (BNF) в регулярное выражение .Net? (Я не застрял в БНФ, но я подумал, что это может быть лучшим способом объяснить, что я пытался сделать). 

<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>.*?)\))?>>

Редактировать

Оказывается, я был более грубым в грамматике БНФ, чем думал.

Я пытался понять, что в скобках указаны специальные символы. Внутри раздела "option" они должны быть отделены косой чертой. (И слэши тоже должны быть убраны).

Ответы [ 4 ]

8 голосов
/ 21 января 2009

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

EDIT:

Если вы хотите, чтобы любые дополнительные символы в скобках (и обратные косые черты) должны были быть экранированы внутри << и >>, вы можете сделать что-то вроде этого: 

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')
2 голосов
/ 21 января 2009

Регулярные выражения обозначают регулярные языки. Контекстно-свободные грамматики генерируют контекстно-свободные языки. Первый набор языков является подмножеством последнего, и в общем случае вы не можете выразить язык без контекста как регулярное выражение.

0 голосов
/ 21 января 2009

Я думаю, мне удалось заставить его работать ... 

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

Уловка, о которой я мог подумать, была в части выбора: 

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

Что означает: знак двойной косой черты, слэш-парен или символ без косой черты.

Затем включите его 0 или более раз и добавьте его в группу с именем "option": 

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

Я также изменил имя поля на один или несколько неоткрытых паренов: 

fieldname =     [^\(]+

Соединив это, я нашел решение.

0 голосов
/ 21 января 2009

Я обдумывал ответ и вроде надеялся, что кто-нибудь прыгнет на меня, чтобы я мог остановиться. :)

Рекурсивный характер BNF обычно является хорошим индикатором открытия, который, если ваша проблема хорошо отображается в BNF, не очень хорошо отображается в RegExp.

Должен признать, я не уверен, что смогу даже выяснить ваш БНФ. Например: x :: = << Boo (abc321) >>

Предполагается, что вашими опциональными парами являются c3, b2 и a1. Предполагается, что символ является допустимым «параметром» - вы не определили допустимое значение терминала для параметра, который не был пустой строкой. Это действительно намерение?

Предполагая, что вы не хотите быть рекурсивным ... Имея дело с побегом и все остальное ... Вам может быть лучше писать код. Это выглядит намного проще, если пройтись по струне и разобраться с чем-либо еще. Ощущение того, что вы хотите, говорит о том, что вам не нужна логика заблаговременного просмотра или оглядки назад.

...