Расширенная форма Бэкуса — Наура рбнф

Привет, сегодня поговорим про расширенная форма бэкуса - наура, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое расширенная форма бэкуса - наура, рбнф , настоятельно рекомендую прочитать все из категории Алгоритмизация и программирование. Структурное программирование. Язык C.

Расширенная форма Бэкуса — Наура (расширенная Бэкус — Наурова форма ( рбнф )) (англ. Extended Backus–Naur Form (EBNF)) — формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно-свободных формальных грамматик. Предложена Никлаусом Виртом. Является расширенной переработкой форм Бэкуса-Наура, отличается от БНФ более «емкими» конструкциями, позволяющими при той же выразительной способности упростить и сократить в объеме описание.

Тем не менее, используется множество различных вариантов РБНФ. Международная организация по стандартизации приняла стандарт РБНФ: ISO/IEC 14977 (в данной статье не описан синтаксис РБНФ согласно этому стандарту, но это сделано в английской версии этой статьи).

Описание

Таблица символов

Ниже представлен предлагаемый стандарт ISO / IEC 14977, разработанный RS Scowen, стр. 7, таблица 1.

Терминалы и нетерминалы

Как и в БНФ, описание грамматики в РБНФ представляет собой набор правил, определяющих отношения между терминальными символами (терминалами) и нетерминальными символами (нетерминалами).

• Терминальные символы — это минимальные элементы грамматики, не имеющие собственной грамматической структуры. В РБНФ терминальные символы — это либо предопределенные идентификаторы (имена, считающиеся заданными для данного описания грамматики), либо цепочки — последовательности символов в кавычках или апострофах.
• Нетерминальные символы — это элементы грамматики, имеющие собственные имена и структуру. Каждый нетерминальный символ состоит из одного или более терминальных и/или нетерминальных символов, сочетание которых определяется правилами грамматики. В РБНФ каждый нетерминальный символ имеет имя, которое представляет собой строку символов.

Правила

Правило в РБНФ имеет вид:

идентификатор = выражение.

где идентификатор — имя нетерминального символа, а выражение — соответствующая правилам РБНФ комбинация терминальных и нетерминальных символов и специальных знаков. Точка в конце — специальный символ, указывающий на завершение правила.

Семантика правила РБНФ — нетерминальный символ, заданный идентификатором слева от знака «равно», представляет собой определяемую выражениемкомбинацию терминальных и нетерминальных символов.

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

Выражения

Набор возможных конструкций РБНФ очень невелик. Это конкатенация, выбор, условное вхождение и повторение.

• Конкатенация. Специального обозначения не имеет, определяется последовательной записью символов в выражении. Правило вида A = BC. обозначает, что нетерминал A состоит из двух символов — B и C. Элементы конкатенации называют еще синтаксическими факторами, или просто факторами. В данном примере B и C — синтаксические факторы. Если конкатенируемые символы могут обозначаться более чем одним знаком (как это обычно бывает при описании языков программирования), они разделяются одним или более пробельными символами (пробелы, переводы строк, табуляции). Например, Присваивание = Переменная ":=" Выражение. — здесь нетерминал Присваивание определен как конкатенация термов Переменная, «:=» и Выражение.
• Выбор. Обозначается вертикальной чертой. Правило вида A = B|C|D. обозначает, что нетерминал A может состоять либо из B, либо из C, либо из D. Элементы выбора называют еще синтаксическими термами, или просто термами. В данном примере B, C, D — синтаксические термы.
• Условное вхождение. Квадратные скобки выделяют необязательный элемент выражения, который может присутствовать, а может и отсутствовать. Правило вида A = [B]. обозначает, что нетерминал A либо является пустым, либо состоит из символа B.
• Повторение. Фигурные скобки обозначают конкатенацию любого числа (включая нуль) записанных в ней элементов. Правило вида A = {B}. обозначает, что A — либо пустой, либо представляет собой конкатенацию любого числа символов B (то есть A — это либо пустой элемент, либо B, либо BB, либо BBB и так далее). Если требуется, чтобы A представлял собой либо B, либо произвольное число B, но не мог быть пустым, используется запись A = B{B}.
• Помимо основных операций, в РБНФ могут использоваться обычные круглые скобки. Они применяются для группировки элементов при формировании сложных выражений. Об этом говорит сайт https://intellect.icu . Например, правило A = (B|C)(D|E). обозначает, что A состоит из двух символов, первым из которых является либо B, либо C, вторым — либо D, либо E, то есть A может быть одной из цепочек BD, BE, CD, CE.
• не общепринято! Также иногда имеет смысл использовать отрицание. Например, A = (B|D)!C означает, что A может быть B или D, но не BC или DC. Такой вариант позволяет четко отличить A от G = (B|D)C и упростить процедуру разбора.
• не общепринято! Определение цифры включает в себя 10 символов — от '0' до '9'. Вполне логично описать понятие «цифра» перечислением: Digit = '0' | '1' | '2' | ... | '9'. Также можно определить понятие «символ».

Или все вышеуказанное вкратце:

• лексема «::=» ее описание (или «=»)
• '…' — текстовый элемент — символ или группа символов
• A B — элемент A, за которым следует элемент B (конкатенация)
• A | B — либо элемент A либо B (выбор)
• [A] — элемент A входит или не входит (условное вхождение)
• {A} — ноль или более элементов A (повторение)
• (A B) — группировка элементов

Варианты синтаксиса

В некоторых работах встречаются модифицированные варианты синтаксиса РБНФ.

• Можно встретить использование в правилах символа «::=» вместо «=» (по аналогии с БНФ).
• Иногда конкатенация в выражениях обозначается не простым следованием символов друг за другом, а с помощью запятой. В таком случае несколько слов, написанных через пробелы, следует понимать как одно многословное имя нетерминального символа. Например:

 Условный оператор = "IF", Логическое выражение, "THEN",  
 Группа операторов,  
 {"ELSIF", Логическое выражение, "THEN", Группа операторов}, 
 ["ELSE", Группа операторов], 
 "ENDIF"

— правило, задающее грамматику условного оператора языка Modula-2, где «Условный оператор» и «Группа операторов» — нетерминальные символы с составными именами.

• Стандарт BSI. Принятый в 1981 году Британским институтом стандартов (BSI) стандарт на EBNF отличается от варианта, предложенного Виртом, следующими особенностями:
  • конкатенация обозначается запятой;
  • конец определения правила обозначается точкой с запятой;
  • пробелы в правиле, за исключением заключенных в кавычки, считаются незначимыми.

Примеры конструкций

Формальное самоопределение РБНФ

Общую форму грамматики РБНФ-описания можно описать в виде РБНФ следующим образом:

 Синтаксис     = { СинтОператор }.
 СинтОператор  = идентификатор "=" СинтВыражение ".".
 СинтВыражение = СинТерм {"|" СинТерм}.
 СинТерм       = СинтФактор { СинтФактор }.
 СинтФактор    = идентификатор | цепочка 
               | "(" СинтВыражение ")" | "[" СинтВыражение "]" 
               | "{" СинтВыражение "}".

В данном описании предполагается, что идентификатор и цепочка — предопределенные термы. При желании нетрудно записать и их определение в РБНФ, для этого потребуется лишь задать определенный алфавит и, если это необходимо, дополнительные ограничения на вид идентификатора.

Число и идентификатор в РБНФ

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

 Число = ["+"|"-"]НатЧисло["."[НатЧисло]][("e"|"E")["+"|"-"]НатЧисло].
 НатЧисло = Цифра{Цифра}.
 Цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

 Идент = Буква{Буква|Цифра|"_"}.

Определение нетерминала Буква здесь не приведено ввиду очевидности и громоздкости — он представляет собой выбор из принятого алфавита.

РБНФ и другие способы описания формальных грамматик

РБНФ и БНФ

Сходства и различия между БНФ и РБНФ очевидны из описания. Отличие состоит, по большому счету, в двух основных моментах:

1. В РБНФ упрощен синтаксис записи правил: знак определения «::=» заменен на «=» и упразднено использование угловых скобок для выделения нетерминалов. В результате исчезла возможность называть нетерминалы многословными идентификаторами, зато запись стала короче. В модификации синтаксиса РБНФ, в которой конкатенация обозначается запятой, многословные идентификаторы использовать можно.
2. В РБНФ введены два новых синтаксических элемента: условное вхождение (выражение в квадратных скобках) и повторение (выражение в фигурных скобках).

Об удачности или неудачности первого изменения могут быть разные мнения, но, в любом случае, на выразительных возможностях формы оно не сказывается. А вот второе нововведение весьма существенно. Оно также не добавляет принципиально новых выразительных возможностей (все, что записано в РБНФ, можно адекватно записать и в обычной БНФ), но существенно сокращает и упрощает запись.

Главное преимущество РБНФ перед БНФ — возможность описывать простые повторяющиеся конструкции неопределенной длины (списки, строки, последовательности и так далее) без рекурсивных правил. Отсутствие в БНФ конструкции повторения приводит к тому, что любое повторение приходится определять путем введения дополнительных промежуточных нетерминальных символов и рекурсивных правил, из-за чего определение становится чрезмерно большим по объему и малопонятным. Описание повторений в РБНФ оказывается одновременно и короче, и удобнее для восприятия человеком.

В качестве примера можно рассмотреть правила, определяющие нетерминал «список», представляющий собой набор от нуля до любого числа идентификаторов, перечисленных через запятую (предполагается, что символы «ПраваяСкобка», «ЛеваяСкобка», «Запятая» и «Идент» уже определены).

Определение в РБНФ включает всего одно правило:

 Список = ЛеваяСкобка [Идент {Запятая Идент}] ПраваяСкобка.

Определение в БНФ выглядит так:

 <Список> ::= <ЛеваяСкобка> <ПраваяСкобка> | <ЛеваяСкобка> <ИдентСпис> <ПраваяСкобка> 
 <ИдентСпис> ::= <Идент> | <Идент> <Запятая> <ИдентСпис>

Уже из этого примера видны отличия форм:

• В БНФ в правиле, определяющем Список, присутствует два варианта — для пустого списка и для любого другого. В РБНФ за счет конструкции условного вхождения необходимость в явном описании двух вариантов исчезла.
• В БНФ потребовалось ввести искусственное рекурсивное правило ИдентСпис, чтобы описать последовательность идентификаторов, разделенных запятыми. В РБНФ за счет конструкции повторения данный фрагмент синтаксиса записан прямо в основном правиле, причем в более простом виде.
• Поскольку РБНФ-правило одно, его длина меньше и оно не содержит вариантов и рекурсии, его гораздо легче понять. Чтобы восстановить форму списка по приведенным описаниям, в случае РБНФ-описания достаточно последовательно записать значения символов, а для БНФ-описания придется определить порядок применения правил и построить списки для каждого варианта (а их по два в каждом правиле).

Естественно, что платой за преимущества РБНФ перед БНФ является бо́льшая сложность автоматической интерпретации РБНФ-описаний. Генераторы программ синтаксического разбора по формальным описаниям грамматики, использующие БНФ, проще тех, которые используют РБНФ.

РБНФ и синтаксические диаграммы

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

Применение, достоинства и недостатки РБНФ

РБНФ, как и ее предшественница — БНФ, — чрезвычайно широко применяется как средство описания искусственных языков, прежде всего — языков программирования и родственных им систем обозначений. В частности, изобретатель РБНФ, Никлаус Вирт, использовал этот формализм в своих книгах для описания всех рассматриваемых там языков программирования.

Преимущества перед БНФ

Любая грамматика, определенная в EBNF, также может быть представлена ​​в BNF, хотя представления в последнем обычно более длинные. Например, варианты и повторения не могут быть напрямую выражены в BNF и требуют использования промежуточного правила или альтернативного производства, определенного как «ничто», либо как факультативное производство для варианта, или либо повторное производство самого себя, рекурсивно, для повторения. Те же конструкции все еще можно использовать в EBNF.

БНФ использует символы ( <, >, |, ::=) для себя, но не включает в себя кавычки терминальных цепочек. Это предотвращает использование этих символов в языках и требует специального символа для пустой строки. В EBNF клеммы строго заключаются в кавычки ( "... "или '... '). Угловые скобки (« <… >») для нетерминалов можно опустить.

Синтаксис БНФ может представлять правило только в одной строке, тогда как в EBNF символ завершения, точка с запятой « ;» обозначает конец правила.

Кроме того, EBNF включает механизмы для улучшений, определения количества повторов, исключения альтернатив, комментариев и т. д.

Более высокая сложность РБНФ по сравнению с БНФ приводит к тому, что генераторов программ грамматического разбора, работающих на основе РБНФ, существенно меньше, чем тех, что основаны на БНФ. Тем не менее, они существуют и применяются. РБНФ является основой для генераторов программ грамматического анализа Spirit C++ Parser Framework, Coco/R, The SLK Parser Generator, а также ряда других. Для применения в таких системах синтаксис РБНФ расширяется в том же направлении, что синтаксис БНФ при использовании парсер-генераторов yacc или bison — в описание грамматики напрямую вставляется обрабатывающий ее код, так или иначе организуется взаимодействие с лексическим анализатором. Могут накладываться дополнительные ограничения и на структуру правил — не все правила, которые можно описать на РБНФ, могут быть эффективно преобразованы в код.

К безусловным достоинствам РБНФ можно отнести простоту (сам язык РБНФ содержит всего 10 специальных знаков — три вида скобок, вертикальную черту, знак «равно» и кавычки, возможно, еще запятую; его синтаксис определяется пятью правилами), достаточную мощность и наглядность, что делает его удобным для выполнения описаний, предназначенных не только для автоматической интерпретации, но и для чтения людьми. Близость конструкций РБНФ к синтаксическим диаграммам позволяет рисовать последние прямо по РБНФ-описанию.

К недостаткам РБНФ, как, впрочем, и БНФ, можно отнести тот факт, что они описывают грамматическую структуру формального языка без учета контекстных зависимостей, а значит, при наличии таких зависимостей РБНФ-описание оказывается неполным, и некоторые правила синтаксиса описываемого языка приходится излагать в обычной текстовой форме. Это приводит к тому, что текст, точно соответствующий РБНФ-грамматике, может, тем не менее, оказаться синтаксически некорректным. Например, в РБНФ-грамматике невозможно естественным образом отобразить тот факт, что некоторая операция требует операндов одного и того же типа. Подобные проверки приходится проводить уже написанным вручную кодом грамматического анализатора. С другой стороны, системы описания грамматики, включающие определение контекстных зависимостей, например, грамматика ван Вейнгаардена, оказываются существенно сложнее, и использование их для автоматической генерации парсеров оказывается затруднительным.

Вау!! 😲 Ты еще не читал? Это зря!

• Meta-II - ранний инструмент для написания компиляторов и обозначений
• Правила структуры фраз - прямой эквивалент РБНФ в естественных языках.
• Регулярное выражение
• Фреймворк Spirit Parser

На этом все! Теперь вы знаете все про расширенная форма бэкуса - наура, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое расширенная форма бэкуса - наура, рбнф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмизация и программирование. Структурное программирование. Язык C