Преобразуйте правила ABNF в REGEX

Question

Мне нужно преобразовать упомянутые правила ABNF (mlaer) в REGEX

   mlaer       =  1*( lebal "." ) lebal
   lebal       =  gid-tel *(rts-hdl)

   rts-hdl    =  *( alpha / digit / "-" ) gid-tel
   gid-tel    =  alpha / digit
   alpha       =  %x41-5A  ; 'A'-'Z'
   alpha       =/ %x61-7A  ; 'a'-'z'
   digit       =  %x30-39  ; '0'-'9'

Есть ли какой-либо инструмент или что-то, чтобы сделать это автоматически?

Answer 1

Следует помнить, что в общем смысле перевести ABNF в REGEX невозможно.

Это связано с тем, что регулярные выражения создают обычный язык , а спецификации ABNF создают контекстно-свободный язык .

Обычный язык может анализироваться с помощью конечного автомата (который также используется для сопоставления регулярных выражений), в то время как контекстно-свободный язык анализируется с помощью автомата с выталкиванием , который является надмножеством конечного автомата (автоматы с выталкиванием могут быть реализованы с помощью инструмент bison/yacc).

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

Следовательно, перевод из ABNF в регулярное выражение возможен только в некоторых случаях. Я предполагаю, что это тот случай, когда ABNF не рекурсивна или не содержит никаких циклических определений. Это (неявное) ограничение вышеупомянутых инструментов автоматического перевода.

Answer 2

Не уверен, есть ли какой-нибудь инструмент, чтобы сделать это автоматически, но это не слишком сложно.

gid-tel

[A-Za-z0-9]

rts-hdl

[A-Za-z0-9-]*[A-Za-z0-9]

lebal

[A-Za-z0-9]([A-Za-z0-9-]*[A-Za-z0-9])*

Обратите внимание, что lebal написанное в этой форме заставит механизм NFA работать очень долго при вводе определенного типа. Это должно быть переписано как:

[A-Za-z0-9]([A-Za-z0-9-]*[A-Za-z0-9])?

mlaer

([A-Za-z0-9]([A-Za-z0-9-]*[A-Za-z0-9])?\.)+[A-Za-z0-9]([A-Za-z0-9-]*[A-Za-z0-9])?

Вы можете создать сложное регулярное выражение, используя конкатенацию строк. Это позволит вам писать чистый код. Хотя в случае с lebal необходимо изменить грамматику, чтобы она хорошо работала на двигателе NFA.

Answer 3

Для небольших ABNF этот онлайн-инструмент, написанный на PHP, работал для меня. В вашем случае это возвращает:

gid-tel: ^([A-Z][a-z0-9])$
rts-hdl: ^(([A-Z][-a-z0-9])*([A-Z][a-z0-9]))$
lebal: ^([A-Z][a-z0-9])((([A-Z][-a-z0-9])*([A-Z][a-z0-9])))*$
mlaer: ^(([A-Z][a-z0-9])((([A-Z][-a-z0-9])*([A-Z][a-z0-9])))*\.)+([A-Z][a-z0-9])((([A-Z][-a-z0-9])*([A-Z][a-z0-9])))*$

Но для больших ABNF, таких как адрес электронной почты, выводится только пустым. В настоящее время я ищу другие инструменты и нашел странный маленький скрипт на Perl и один написанный на Ruby почти 17 лет назад, а последний - 7 лет назад. Последний выглядит многообещающе, так как на самом деле дает RegEx для URI ABNF, но мне все еще нужно заставить его работать.