Расширенная форма Бэкуса — Наура
Материал из Википедии — свободной энциклопедии
 |
Эту статью следует викифицировать.
Пожалуйста, оформите её согласно правилам оформления статей.
|
Расширенная форма Бэкуса-Наура (англ. Extended Backus-Naur Form, EBNF) — формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно-свободных формальных грамматик. Предложена Никлаусом Виртом. Является расширенной переработкой форм Бэкуса-Наура, отличается от БНФ более «ёмкими» конструкциями, позволяющими при той же выразительной способности упростить и сократить в объёме описание.
Содержание |
[править] Описание
[править] Терминалы и нетерминалы
Как и в БНФ, описание грамматики в РБНФ представляет собой набор правил, определяющих отношения между терминальными символами (терминалами) и нетерминальными символами (нетерминалами).
- Терминальные символы — это минимальные элементы грамматики, не имеющие собственной грамматической структуры. В РБНФ терминальные символы — это либо предопределённые идентификаторы (имена, считающиеся заданными для данного описания грамматики), либо цепочки — последовательности символов в кавычках или апострофах.
- Нетерминальные символы — это элементы грамматики, имеющие собственные имена и структуру. Каждый нетерминальный символ состоит из одного или более терминальных и/или нетерминальных символов, сочетание которых определяется правилами грамматики. В РБНФ каждый нетерминальный символ имеет имя, которое представляет собой строку символов.
[править] Правила
Правило в РБНФ имеет вид:
идентификатор = выражение.
где идентификатор — имя нетерминального символа, а выражение — соответствующая правилам РБНФ комбинация терминальных и нетерминальных символов и специальных знаков. Точка в конце — спецсимвол, указывающий на завершение правила.
Семантика правила РБНФ — нетерминальный символ, имя которого записано слева от знака «равно», представляет собой определяемую выражением комбинацию терминальных и нетерминальных символов.
Полное описание грамматики представляет собой набор правил, который последовательно определяет все нетерминальные символы грамматики так, что каждый нетерминальный символ может быть сведён к комбинации терминальных символов путём последовательного (рекурсивного) применения правил. В определении РБНФ нет никаких специальных предписаний относительно порядка записи правил, хотя такие предписания могут вводиться при использовании РБНФ программными средствами, обеспечивающими автоматическую генерацию программ синтаксического разбора по описанию грамматики.
[править] Выражения
Набор возможных конструкций РБНФ очень невелик. Это конкатенация, выбор, условное вхождение и повторение.
- Конкатенация. Специального обозначения не имеет, определяется последовательной записью символов в выражении. Правило вида
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|C)(D|E). обозначает, что A состоит из двух символов, первым из которых является либо B, либо C, вторым — либо D, либо E, то есть A может быть одной из цепочек BD, BE, CD, CE.
[править] Варианты синтаксиса
В некоторых работах встречаются модифицированные варианты синтаксиса РБНФ.
- Можно встретить использование в правилах символа «
::=» вместо «=» (по аналогии с БНФ). - Иногда конкатенация в выражениях обозначается не простым следованием символов друг за другом, а с помощью запятой. В таком случае несколько слов, написанных через пробелы, следует понимать как одно многословное имя нетерминального символа. Например:
Условный оператор = "IF", Логическое выражение, "THEN",
Группа операторов,
{"ELSIF", Группа операторов},
["ELSE", Группа операторов],
"ENDIF"
— правило, задающее грамматику условного оператора языка Modula-2, где «Условный оператор» и «Группа операторов» — нетерминальные символы с составными именами. - Стандарт BSI. Принятый в 1981 году Британским институтом стандартов (BSI) стандарт на EBNF отличается от варианта, предложенного Виртом, следующими особенностями:
- конкатенация обозначается запятой;
- конец определения правила обозначается точкой с запятой;
- пробелы в правиле, за исключением заключённых в кавычки, считаются незначимыми.
[править] Примеры конструкций
[править] Формальное самоопределение РБНФ
Общую форму грамматики РБНФ-описания можно описать в виде РБНФ следующим образом:
Синтаксис = { СинтОператор }.
СинтОператор = идентификатор "=" СинтВыражение ".".
СинтВыражение = СинТерм {"|" СинТерм}.
СинТерм = СинтФактор { СинтФактор }.
СинтФактор = идентификатор | цепочка
| "(" СинтВыражение ")" | "[" СинтВыражение "]"
| "{" СинтВыражение "}".
В данном описании предполагается, что идентификатор и цепочка — предопределённые термы. При желании нетрудно записать и их определение в РБНФ, для этого потребуется лишь задать определённый алфавит и, если это необходимо, дополнительные ограничения на вид идентификатора.
[править] Число и идентификатор в РБНФ
Следующие грамматики определяют запись десятичного числа общего вида (с ведущим знаком, возможной дробной частью и порядком) и типичного идентификатора языка программирования (последовательность букв, цифр и знаков подчёркивания, начинающаяся с буквы).
Число = ["+"|"-"]НатЧисло["."[НатЧисло]][("e"|"E")["+"|"-"]НатЧисло].
НатЧисло = Цифра{Цифра}.
Цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".
Идент = Буква{Буква|Цифра|"_"}.
Определение нетерминала Буква здесь не приведено ввиду очевидности и громоздкости — он представляет собой выбор из принятого алфавита.
[править] РБНФ и другие способы описания формальных грамматик
[править] РБНФ и БНФ
Сходства и различия между БНФ и РБНФ очевидны из описания. Отличие состоит, по большому счёту, в двух основных моментах:
- В РБНФ упрощён синтаксис записи правил: знак определения «
::=» заменён на «=» и упразднено использование угловых скобок для выделения нетерминалов. В результате исчезла возможность называть нетерминалы многословными идентификаторами, зато запись стала короче. В модификации синтаксиса РБНФ, в которой конкатенация обозначается запятой, многословные идентификаторы использовать можно. - В РБНФ введены два новых синтаксических элемента: условное вхождение (выражение в квадратных скобках) и повторение (выражение в фигурных скобках).
Об удачности или неудачности первого изменения могут быть разные мнения, но, в любом случае, на выразительных возможностях формы оно не сказывается. А вот второе нововведение весьма существенно. Оно также не добавляет принципиально новых выразительных возможностей (всё, что записано в РБНФ, можно адекватно записать и в обычной БНФ), но существенно сокращает и упрощает запись.
Главное преимущество РБНФ перед БНФ — возможность описывать простые повторяющиеся конструкции неопределённой длины (списки, строки, последовательности и так далее) без рекурсивных правил. Отсутствие в БНФ конструкции повторения приводит к тому, что любое повторение приходится определять путём введения дополнительных промежуточных нетерминальных символов и рекурсивных правил, из-за чего определение становится чрезмерно большим по объёму и малопонятным. Описание повторений в РБНФ оказывается одновременно и короче, и удобнее для восприятия человеком.
В качестве примера можно рассмотреть правила, определяющие нетерминал «список», представляющий собой набор от нуля до любого числа идентификаторов, перечисленных через запятую (предполагается, что символы «ПраваяСкобка», «ЛеваяСкобка», «Запятая» и «Идент» уже определены).
Определение в РБНФ включает всего одно правило:
Список = ЛеваяСкобка [Идент {Запятая Идент}] ПраваяСкобка.
Определение в БНФ выглядит так:
<Список> ::= <ЛеваяСкобка> <ПраваяСкобка> | <ЛеваяСкобка> <ИдентСпис> <ПраваяСкобка>
<ИдентСпис> ::= <Идент> | <Идент> <Запятая> <ИдентСпис>
Уже из этого примера видны отличия форм:
- В БНФ в правиле, определяющем Список, присутствует два варианта — для пустого списка и для любого другого. В РБНФ за счёт конструкции условного вхождения необходимость в явном описании двух вариантов исчезла.
- В БНФ потребовалось ввести искусственное рекурсивное правило ИдентСпис, чтобы описать последовательность идентификаторов, разделённых запятыми. В РБНФ за счёт конструкции повторения данный фрагмент синтаксиса записан прямо в основном правиле, причём в более простом виде.
- Поскольку РБНФ-правило одно, его длина меньше и оно не содержит вариантов и рекурсии, его гораздо легче понять. Чтобы восстановить форму списка по приведённым описаниям, в случае РБНФ-описания достаточно последовательно записать значения символов, а для БНФ-описания придётся определить порядок применения правил и построить списки для каждого варианта (а их по два в каждом правиле).
Естественно, что платой за преимущества РБНФ перед БНФ является бо́льшая сложность автоматической интерпретации РБНФ-описаний. Генераторы программ синтаксического разбора по формальным описаниям грамматики, использующие БНФ, проще тех, которые используют РБНФ.
[править] РБНФ и синтаксические диаграммы
РБНФ эквивалентны подклассу синтаксических диаграмм, которые широко используются для описания грамматик. Любую РБНФ-грамматику можно адекватно представить синтаксической диаграммой, но, в общем случае, синтаксические диаграммы позволяют создать описания, которые невозможно представить в РБНФ (или, во всяком случае невозможно перевести в РБНФ напрямую, не преобразуя перед этим графическое описание).
[править] Применение, достоинства и недостатки РБНФ
РБНФ, как и её предшественница — БНФ, — чрезвычайно широко применяется как средство описания искусственных языков, прежде всего — языков программирования и родственных им систем обозначений. В частности, изобретатель РБНФ, Никлаус Вирт, использовал этот формализм в своих книгах для описания всех рассматриваемых там языков программирования.
РБНФ является основой для нескольких программных генераторов программ грамматического анализа, в том числе Spirit C++ Parser Framework, Coco/R, The SLK Parser Generator. Для применения в таких системах синтаксис РБНФ расширяется в том же направлении, что синтаксис БНФ при использовании парсер-генераторов Yacc или Bison — в описание грамматики напрямую вставляется обрабатывающий её код, так или иначе организуется взаимодействие с лексическим анализатором. Могут накладываться дополнительные ограничения и на структуру правил - не все правила, которые можно описать на РБНФ, могут быть эффективно преобразованы в код. Более высокая сложность РБНФ по сравнению с БНФ приводит к тому, что генераторов программ грамматического разбора, работающих на основе РБНФ, существенно меньше, чем тех, что основаны на БНФ. Тем не менее, они существуют и применяются.
К безусловным достоинствам РБНФ можно отнести простоту (сам язык РБНФ содержит всего 10 специальных знаков — три вида скобок, верктикальная черта, знак «равно» и кавычки, возможно, ещё запятая, его синтаксис определяется пятью правилами), достаточную мощность и наглядность, что делает его удобным для выполнения описаний, предназначенных не только для автоматической интерпретации, но и для чтения людьми. Близость конструкций РБНФ к синтаксическим диаграммам позволяет рисовать последние прямо по РБНФ-описанию.
К недостаткам РБНФ, как, впрочем, и БНФ, можно отнести тот факт, что они описывают грамматическую структуру формального языка без учёта контекстных зависимостей, а значит, при наличии таких зависимостей РБНФ-описание оказывается неполным, и некоторые правила синтаксиса описываемого языка приходится излагать в обычной текстовой форме. Это приводит к тому, что текст, точно соответствующий РБНФ-грамматике, может, тем не менее, оказаться синтаксически некорректным. Например, в РБНФ-грамматике невозможно естественным образом отобразить тот факт, что некоторая операция требует операндов одного и того же типа. Подобные проверки приходится проводить уже написанным вручную кодом грамматического анализатора. С другой стороны, системы описания грамматики, включающие определение контекстных зависимостей, например, грамматика ван Вейнгаардена, оказываются существенно сложнее, и использование их для автоматической генерации парсеров оказывается затруднительным.
 |
Это незавершённая статья о компьютерном программировании. Вы можете помочь проекту, исправив и дополнив её. |
