Я пытаюсь определить BNF BNF. Другими словами, я пытаюсь определить метаграмму BNF. То есть, грамматика BNF, которая является экземпляром самой себя и может генерировать любую другую грамматику BNF.Что такое BNF BNF? Как мы определяем метаграмму BNF?
Любые советы/подсказки/фрагменты будут высоко оценены!
Спасибо!
Вот один:
bnf = rules ;
rules = rule ;
rules = rules rule ;
rule = lefthandside EQUAL righthandside SEMICOLON ;
lefthandside = IDENTIFIER ;
righthandside = ;
righthandside = righthandside token ;
token = IDENTIFIER ;
token = QUOTEDLITERAL ;
Это оставляет IDENTIFIER, QUOTEDLITERAL, EQUAL и SEMICOLON неопределен, под предположение, что BNF определена над LANGAUGE лексем.
Вы можете определить BNF над символами. Просто добавьте:
EQUAL = '=' ;
SEMICOLON = ';' ;
IDENTIFIER = letter ;
IDENTIFIER = IDENTIFIER letterordigit ;
letterordigit = letter ;
letterordigit = digit ;
letter = 'A' ;
...
letter = 'Z' ;
digit = '0' ;
...
digit = '9' ;
в качестве упражнения для читателя: добавить выбор (|), несколько правил, и Клини звезду, чтобы сделать это BNF для EBNF; этот ответ, очевидно, ласкает на обработке пробелов, но вы можете справиться с этим, вставив «пробелы» нетерминала везде, где разрешены пробелы (нехорошо, но работает). Существуют системы спецификации BNF, в которых вы действительно записываете грамматику по существу над символами, и для вас делается неявная пустая нетерминальная вставка (например, Stratego's "Syntax Definition Formalism").
Если вы хотите увлекательный урок в BNF-about-BNF, вы должны прочитать paper/do the tutorial для системы обработки BNF от честного до 196-го года под названием «MetaII». В этом документе описывается, как сделать BNF в BNF, и как построить два компилятора на всех 10 страницах.
(Один большой урок здесь: прочитайте все материалы по компьютерной науке с 60-х и 70-х годов. Это не так много, и вы будете поражены тем, насколько там хороший материал).
<line> ::= '<' <word> '>' '::=' <definition>
<definition> ::= <word> '|' | '' <definition> | ''
Ваш вопрос, кажется, отвечает на [Википедии статью о BNF] (http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form#Further_examples). –
@GregHewgill Интересно. Меня научил Фрэнк де Ремер, что BNF не может описать себя. – EJP
@EJP: De Remer был (есть?) Довольно эффектно с генераторами и грамматиками парсера. Я не верю, что он бы это научил. Я подозреваю, что вы неправильно вспомнили, что узнали. –