Как преобразовать PCRE в EBNF?

Question

Я пишу спецификацию, и я не знаю EBNF. У меня есть следующий PCRE:

^(?:\$(?:\$|{\d+})|[^$])*$ 

Где, на входе:

• $$ является сбежавший $.
• ${num} - номер аргумента.
• Все остальное (то есть не $) является буквальным.
• A $ не последовали $ или {num} - это ошибка.

И мне нужно преобразовать его в EBNF. Как преобразовать этот PCRE в EBNF?

(я заметил, есть много вопросов о переходе от EBNF к PCRE, но я не видел ни о переходе наоборот)

Answer 1

Две вещи делают ответить на этот простой вопрос, видимо, сложнее:

1. Термин «EBNF» имеет большое разнообразие проявлений. Существует стандарт ISO ISO/IEC 14977:1996 для «Extended BNF», но, насколько я знаю, он редко используется на практике. (Примечание: На этой странице есть свободная ссылка для скачивания: покупка не требуется.) Многие интернет-протоколы используют «расширенный BNF», как определено RFC 5234, что, вероятно, лучше подходит для вашей конкретной проблемы. И есть множество генераторов парсеров, которые расширяют BNF различными способами, как правило, добавляя регулярные выражения, подобные операторам повторения и опциональности, никоим образом не унифицированные. (Фактически, именно этот хаос возможных определений побуждал ИСО к разработке стандарта, но, как это часто бывает со стандартами ИСО, отсутствие свободного доступа к текстам - до десятилетия после его выпуска - и свободно доступное инструменты препятствуют принятию.)

2. регулярных выражений не обязательно производить однозначные грамматики, и регулярное выражение вы предоставите неоднозначно, так как $ разрешаются использовать как обычный символ. Импликация (и, я уверен, намерение) заключается в том, что $ не может рассматриваться как обычный символ, за которым следует еще $ или число, окруженное фигурными скобками, но само регулярное выражение (и не обязательно) делать это различие. Менее очевидным является то, что намерение может быть для строки, как:

   ${42 looks like an error to me but it would be accepted by the regex. 
   

Во всяком случае, вот ISO EBNF что-то похожее на ваш язык. Обратите внимание, что это не принять приведенную выше строку.

(* EBNF does not have wildcard characters and there is no way to 
    enumerate all possible characters, so I use the exception mechanism 
    to describe the set 
*) 
any character 
    = ? Any character representable by the source character encoding ? ; 
decimal digit 
    = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'; 
literal sequence 
    = {any character} - 
     ({any character}, ('$$' | '${'), {any character}) ; 
escaped dollar 
    = '$$' ; 
parameter 
    = '${', decimal digit, {decimal digit}, '}'; 
thingamajig 
    = {literal sequence | escaped dollar | parameter} 

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