Что такое бнф в информатике

Простая форма Бэкуса — Наура (БНФ)

Краткий обзор, отвечающий на вопросы: Что это? Где используется? Правила написания и примеры использования.

Backus–Naur form или Backus normal form (BNF) это формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик, обычно используется для описания синтаксиса языков программирования, форматов документов, наборов инструкций и протоколов связи. Применяются везде, где необходимо точное описание синтаксиса: например, в официальных спецификациях, руководствах и учебниках.

Так же существует ещё и расширенная форма Бэкуса — Наура, отличающаяся более ёмкими конструкциями.

Термины:

БНФ-конструкция определяет конечное число нетерминалов (символов) и определяет правила замены символа на какую-то последовательность терминалов (букв) и символов.

За процесс построения цепочки букв можно проследить поэтапно:

В конце концов, получается цепочка, состоящая из букв и не содержащая символов.

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

Примеры конструкций БНФ.

Общий вид конструкции.

БНФ-конструкция правильной скобочной последовательности.

Конструкция состоит только из одного правила. Согласно этому правилу символ может быть заменена на пустое место, либо на символ обрамленный круглыми скобками, либо на два симола идущих подряд.

Синтаксис БНФ представленный БНФ-конструкцией (используется латиница)

Источник

Что такое бнф в информатике

Почему у первоклассников, которых учат, что сначала надо выполнять умножение, а уже потом сложение — и сначала действия в скобках, а потом все остальные — никогда никаких проблем с этим материалом не возникает, а чтобы запрограммировать «робота», выполняющего тоже самое, нужны особенные (не тривиальные — не в том смысле, что сложные, а в том смысле, что своими силами до них нормальному человеку не так-то просто дойти) алгоритмы и инструменты?

Зададимся несколькими другими риторическими вопросами из той же серии:

Похоже, что навык распознавания скобочных структур (у людей) опирается на встроенный «речевой процессор».

Отцом-основателем теории о врождённых механизмах производства и восприятия языка (речи) является американский лингвист Ноам Хомский.

Ноам Хомский — «научный дедушка» всех языков высокого уровня — любит интересно порассуждать на и на общие актуальные темы.

Хомский резюмирует годы своей (начальной) работы в книге «Синтаксические структуры» в 1957 году.

В том же году Джон Бэкус (создатель BNF, Backus normal form, «нормальной формы Бэкуса», к описанию которой мы вскоре перейдём) создаёт первый язык программирования высокого уровня «Фортран».

Формальная запись «порождающих грамматик» Хомского, которые он предложил для определения структур естественных языков, с точностью до формы стрелочек совпадает с формальной записью спецификации языка, которую разрабатывает и вскоре публикует Бэкус для описания языков программирования.

Джон Бэкус на фоне своего творения.

Нормальная форма Бэкуса (BNF)

Важная оговорка: далее мы будем говорить

Для формальной записи грамматики формальных языков получила широкое распространение так называемая «нормальная форма Бэкуса» (backus normal form, BNF).

BNF сама по себе является (достаточно простым) формальным языком.

BNF состоит из набора правил вывода для нетерминальных символов («нетерминалов»), которые позволяют (после повторно-рекурсивного применения правил, в конечном итоге) получить набор терминальных символов.

Состав некоего сомнительного кондитерского изделия

Альтернативные правила вывода

Комментарии

Для комментариев используется символ ; :

Пустая строка

Пустая строка (отсутствие символа) обозначается в данном цикле лекций символом ε (эпсилон, от английского empty).

Пускай в нашем «зарплатном языке» разрешены строки вида “100 рублей”, “100 рублей и премия” и “” (пустая строка).

Грамматика будет такая

Иногда ε не пишут, и остаётся просто пустое место. Так тоже можно.

Формальная грамматика и формальный язык

Формальный язык — это совокупность всех возможных «фраз» (последовательностей терминальных символов, то есть строк), которые можно получить из грамматики.

Другими словами, мы можем взять стартовый символ грамматики (первый нетерминал BNF) и провести над ним ряд разрешённых грамматикой преобразований, придя в конечном итоге к строке только лишь из терминальных символов. Вот совокупность всех строк, которые мы таким образом можем получить, и есть наш формальный язык.

И наоборот: любая строка нашего языка может быть «свёрнута» до стартового символа грамматики, если последовательно достаточное число раз применять правила «справа налево».

«Маршрут», по которому такая свёртка произойдёт (какие правила в каком порядке к какому месту исходной строки были применены) составляет дерево парсинга (parse tree) данной строки.

Если для каждой строки языка при данной грамматике существует только одно возможное дерево парсинга, то такая грамматика называется «однозначной».

Например, наивная грамматика инфиксных выражений не является однозначной.

Правило вида «1 и более»

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

В BNF подобные правила моделируются с помощью рекурсии.

Допустим, определим как то и только то, что является последовательностью:

Слова “1 и более” выразим в промежуточном нетерминале вот как:

В самом деле, вообразим строительного робота, который строит здание по структуре, определяемой данной грамматикой:

Нетерминальными символами при этом будут являться «мысли» этого бота, а терминальными — то, что он реально делает.

Дальше у него два варианта развития событий:

Важно ещё раз отметить, что грамматика языка в своём «порождающем» аспекте нацелена именно на «прочерчивание маршрутов» генерации всех возможных строк целевого языка.

Не трудно видеть, что бот таким образом «зацикливается» и, в зависимости от настроения, может построить здание с любым количеством этажей (но один этаж железно будет). Что нам и требовалось.

Итак, формально, для создания правила типа “1 и более x” требуется ввести и использовать дополнительный нетерминал (название условное):

Правило вида «0 и более»

Для правила типа “0 и более x” требуется ввести и использовать дополнительный нетерминал (название условное):

Не углубляясь в тонкости конфликтов shift-reduce и проблем неоднозначных грамматик, отметим, что это правило подходит только для стартового символа.

Rule of thumb вот какой: ни одно правило вывода не должно содержать в качестве одной из веток только ε и больше ничего, кроме стартового правила.

То есть ε должна оказаться на уровне «родительского правила». Плохой вариант, порождающий неоднозначную грамматику:

Хорошая грамматика однозначная — «свёртка» произойдёт ровно столько раз, сколько элементов в массиве.

Плохая грамматика неоднозначная — «свёртка» произойдет сколько угодно раз, поскольку неограниченное число раз может произойти применение последней ветки.

Формально, для создания правила типа “0 и более x” требуется:

Правило вида «0 или 1»

Правило вида 0 или 1 «x» можно задать, создав новый нетерминал :

Не следует совмещать в одном нетерминале правила вида «0 или 1» и «1 и более» для предотвращения случайных ошибок в формулировке правил вывода.

Классы символов

В практических целях удобно опускать некие излишне подробные и повсеместно используемые определения нетерминалов. Например, цифру можно определить как:

Вместо того, чтобы в каждой грамматике каждой лекции, где используется BNF, дописывать эти определения (к тому, имеющие мало значения для практической реализации парсеров), мы используем просто слова number и digit :

При этом слова number и digit не берутся ни в угловые скобки, ни в кавычки. С формально-теоретической точки зрения это нетерминал (определённый как показано выше), а с практической обрабатывается как терминальный символ.

Леворекурсивные и праворекурсивные правила вывода

Правило, которое прямо или опосредовано содержит ссылку на само себя в качестве первого символа одной из веток, называется «леворекурсивным»:

Правило, которое прямо или опосредовано содержит ссылку на само себя в качестве последнего символа одной из веток, называется «праворекурсивным»:.

Диалекты BNF

Существует две распространённых вариации/модификации BNF: EBNF и ABNF.

Применения

Множество различных средств для создания языков программирования используют диалект BNF.

Официальная спецификация ряда современных языков программирования содержит грамматику, записанную на диалекте BNF.

В пользовательской документации к языкам программирования иногда используется диалект BNF.

Стандарты на протоколы интернета, разрабатываемые IETF, зафиксированы на диалекте BNF.

Формальная грамматика BNF в BNF

Примерный вид грамматики BNF в BNF, с учётом изложенных выше рекомендаций:

string — любая строка, не содержащая кавычек, или одна кавычка » ;
identifier — любая строка, не содержащая угловых скобок;

Источник

Форма Бэкуса-Наура

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

Содержание

Применение

Используется для описания синтаксиса языков программирования, данных, протоколов (например, в документах регулярные грамматики являются подмножеством контекстно-свободных).

Описание

Терминология этой статьи может расходиться с традиционной.

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

БНФ-конструкция состоит из нескольких предложений вида

, описывающих правила. Такое правило, означает, что символ может заменяться на одну из последовательностей посл.1. Знак определения, обычно выглядит как ::=, но возможны и другие варианты.

Некоторые специальные символы, как например означают какую-то последовательность (в данном случае — пустую).

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

Вот, как получить с помощью этой конструкции цепочку ((())())() (ниже перечисляются все этапы, символы опускаются):

См. также

Полезное

Смотреть что такое «Форма Бэкуса-Наура» в других словарях:

Форма Бэкуса — Наура — У этого термина существуют и другие значения, см. БНФ. Форма Бэкуса Наура (сокр. БНФ, Бэкуса Наура форма) формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ… … Википедия

форма Бэкуса-Наура — Формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. Используется для описания синтаксиса языков программирования, данных, протоколов. БНФ конструкция определяет… … Справочник технического переводчика

Расширенная форма Бэкуса — Наура — (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно… … Википедия

Расширенная форма Бэкуса-Наура — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. См. также: Синтаксис языков программирования Финансовый словарь Финам … Финансовый словарь

Расширенная форма Бэкуса-Наура — (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно… … Википедия

Расширенная форма Бэкуса—Наура — (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно… … Википедия

дополненная форма Бэкуса-Наура — Наглядная форма представления данных, используемая для задания грамматики (МСЭ Т T.808). [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN augmented Backus Naur formABNF … Справочник технического переводчика

нормальная форма Бэкуса-Наура — БНФ Нотация (метаязык) для записи синтаксиса языков программирования. [ГОСТ Р 54456 2011] Тематики телевидение, радиовещание, видео Синонимы БНФ EN Backus Normal FormBNF … Справочник технического переводчика

расширенная нормальная форма Бэкуса-Наура — расширенная БНФ Способ формального определения грамматики, элементов и атрибутов языка программирования. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом Синонимы расширенная БНФ EN EBNFExtended Backus Naur Form … Справочник технического переводчика

Форма Бэкуса — У этого термина существуют и другие значения, см. БНФ. Форма Бэкуса Наура (сокр. БНФ, Бэкуса Наура форма) формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ… … Википедия

Источник

Представление грамматик

12.1. Другие регулярные выражения

Мы рассмотрели основные области применения регулярных выражений:

Однако существуют и другие области применения регулярных выражений. Об одной из них автор расскажет ниже.

Определения синтаксиса документов XML

DTD расшифровывается как: » document type definition » ( определение типа документа ). Все допустимые для языка, описываемого XML, компоненты (элементы и атрибуты) и все правила (иерархия вложенности и т.п.) записываются в файл DTD. Более подробно об DTD и XML см. [43]. Здесь будет рассказано только часть, которая касается регулярных выражений.

Все объявления типов документов должны начинаться с набора символов: корневому элементу документа.

В документе на XML-совместимом языке могут использоваться только те элементы, которые были заранее объявлены в DTD. Синтаксис объявления элемента следующий:

Тут мы подходим к самому главному: элемент может быть не только предопределенным в ЭВМ типом, но и регулярным выражением, включающий в себя другие элементы!

В качестве индикаторов вхождений используются следующие символы:

означает, что элемент JDATA должен содержать хотя бы один элемент OBJECT ;

расшифруйте это определение сами;

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

При этом адрес содержит:

В этом случае РБНФ для адресной книги будет следующая:

Та же запись на DTD будет:

Пример структуры записи в адресной книге :

Как и грамматику, так и XML-документы проверяют на однозначность.

12.2. Бэкусовская нормальная форма (БНФ)

Отличительные особенности БНФ :

Например, грамматика из примера 01 «Описание формальных грамматик» будет выглядеть так:

12.3. Расширенная БНФ (РБНФ)

Фигурные скобки

Выражение с их участием записывается как:

Фигурные скобки означают, что выражения в них может повторяться от 0 до бесконечности, или согласно модификатору:

Квадратные скобки

В них заключено выражение, повторяющееся ноль или один раз.

Круглые скобки

Диапазон

Метасимволы и терминальные символы

Таким образом, грамматика из (примера 01 «Описание формальных грамматик» ) в РБНФ будет выглядеть так:

Пример 06 «Описание формальных грамматик» в РБНФ может выглядеть так:

Однако чтобы приблизить пример 06 к регулярной грамматике, его следует записать следующим образом:

12.4. Резюме

Конечно же, в этом кратком введении в формальную грамматику «за бортом» осталось множество интересных алгоритмов. Это, прежде всего, алгоритмы «экспертных систем», » семантических сетей «, «фреймов», алгоритмы построения » трансляторов » с языков программирования, разбора, проверки орфографии на «естественных языках» и т.п.. За этими алгоритмами автор отсылает к серьезной литературе по искусственному интеллекту, которую можно найти в библиотеке и во всемирной сети.

Теперь самое время отдохнуть, выпить чашку кофе, и … начать программировать!

Источник

Форма Бэкуса — Наура

Форма Бэкуса — Наура

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

Содержание

Применение

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

Описание

Терминология этой статьи может расходиться с традиционной.

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

БНФ-конструкция состоит из нескольких предложений вида

, описывающих правила. Такое правило, означает, что символ может заменяться на одну из последовательностей посл.1. Знак определения, обычно выглядит как ::=, но возможны и другие варианты.

Некоторые специальные символы, как например означают какую-то последовательность (в данном случае — пустую).

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

Вот как получить с помощью этой конструкции цепочку ((())())() (ниже перечисляются все этапы, символы опускаются):

См. также

Полезное

Смотреть что такое «Форма Бэкуса — Наура» в других словарях:

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

форма Бэкуса-Наура — Формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. Используется для описания синтаксиса языков программирования, данных, протоколов. БНФ конструкция определяет… … Справочник технического переводчика

Форма Бэкуса — У этого термина существуют и другие значения, см. БНФ. Форма Бэкуса Наура (сокр. БНФ, Бэкуса Наура форма) формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ… … Википедия

Расширенная форма Бэкуса — Наура — (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно… … Википедия

Расширенная форма Бэкуса-Наура — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. См. также: Синтаксис языков программирования Финансовый словарь Финам … Финансовый словарь

Расширенная форма Бэкуса-Наура — (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно… … Википедия

Расширенная форма Бэкуса—Наура — (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно… … Википедия

Расширенная форма Бэкуса — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Расширенная форма Бэкуса Наура (расширенная Бэкус Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) формальная система определения… … Википедия

дополненная форма Бэкуса-Наура — Наглядная форма представления данных, используемая для задания грамматики (МСЭ Т T.808). [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN augmented Backus Naur formABNF … Справочник технического переводчика

нормальная форма Бэкуса-Наура — БНФ Нотация (метаязык) для записи синтаксиса языков программирования. [ГОСТ Р 54456 2011] Тематики телевидение, радиовещание, видео Синонимы БНФ EN Backus Normal FormBNF … Справочник технического переводчика

Источник