Языки, грамматики, Бэкусовские нормальные формы (БНФ)

Введём несколько определений. Пусть задано некоторое непустое, конечное множество знаков А={a1, ...an}, которое мы назовём алфавитом

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

Множество всех слов в алфавите А, включая и пустое слово, которое мы обозначим через ε, будем обозначать через A*. 

Очевидно, A* не пусто и  бесконечно (мы ведь не ограничиваем возможную длину слов!). Но, являясь бесконечным, A* - перечислимое (или, как говорят в математике, счётное) множество.

Действительно, если A={a,b}, то элементы A* можно перечислить, упорядочив их по длине и (внутри одной и той же длины) лексикографически т.е , по алфавиту.  При этом, конечно, мы считаем лексикографический порядок  заранее определённым и на  А. Итак, получим:

0. Слова длины 0: ε

1. Слова длины 1: a, b

2. Слова длины 2: aa, ab, ba, bb

. . .

Далее, языком  над  алфавитом A называется любое множество L ≤ A* (здесь '≤'  для множеств означает отношение нестрогого включения, т.е.  утверждения о том, что L есть подмножество A*, возможно, с A* совпадающее).

Язык может быть конечным (т.е. содержащим конечное множество слов) и бесконечным (содержащим бесконечное множество слов).

Строго определить конечный язык можно простым перечислением всех составляющих его слов. Так, если A={0,1}, то примером  конечного языка над A будет L1={011, 1111, 1, 010101}, состоящий из четырёх слов.

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

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

Рассмотрим,  например, множество всех чётных натуральных чисел (к которому мы отнесём и ноль), представленных в двоичной системе счисления. Очевидно,  оно бесконечно и, в традиционной записи, состоит из завершающихся цифрой 0 последовательностей двоичных цифр (например, 110, 010110, 00, 0, 11111100 и т.д.).

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

Для строгого определения элементов выше указанного множества, попробуем задать их структуру верхнего уровня, например так:  

‹двоичное_чётное›  - это  ‹двоичное›, к которому справа приписан ‹ноль›

Введя специальное обозначение "::="  для 1-й связки (слова "это") и просто опустив 2-ю связку (фразу "к которому справа приписан..."),  то же самое мы можем записать короче:

‹двоичное_чётное›  ::= ‹двоичное‹ноль›         [1]

Здесь четко видно, что составной объект, имеющий обозначение ‹двоичное_чётное› как слово, распадается на два объекта следующего (ещё не окончательного!) уровня: ‹двоичное›  и ‹ноль›.

Теперь, дальнейшая детализация структуры исходного объекта, будет состоять из независимого выявления структуры объектов ‹двоичное›  и ‹ноль›.

Второй из этих двух объектов проще, с него и начнём. Пользуясь уже введёнными нами обозначениями, запишем:

‹ноль› ::= 0           [2]

Здесь просто записано, что под термином (понятием) ‹ноль› понимается слово 0.

При этом ‹ноль› и любое другое обозначение в угловых скобках (т.е. конструкция вида < ... > ) называется нетерминальным (т.е. не окончательным, требующим дальнейшей детализации) символом. В то же время, 0 в правой части формулы [2], как и любая другая конструкция, не обрамлённая угловыми скобками, называется терминальным (окончательным) символом, который являясь неделимым (атомарным), непосредственно входит в состав слова, принадлежащего определяемому языку.

Теперь займёмся нетерминальным символом ‹двоичное›, который может быть определён (детализован) так:

‹двоичное› ::= <двоичная_цифра> | <двоичная_цифра> <двоичное>,         [3]

где знак "|" обозначает связку "или".

Формула [3] - это по существу сокращённая запись двух правил:

‹двоичное› ::= <двоичная_цифра>       [4]

‹двоичное› ::= <двоичная_цифра> <двоичное>      [5]

Правило [3], как и пара правил [4,5] определяют структуру объекта ‹двоичное› следующим образом:  <двоичное> - это либо <двоичная_цифра>, либо <двоичная_цифра>, к которой справа приписан объект, так же представляющий собой  <двоичное>.

Входящее в это определение правило [5] представляет собой пример так называемого рекурсивного правила, когда для определения понятия (<двоичное>), оно же, это понятие, и используется. Важно понимать,  что "порочного круга" в данном случае, при этом, не возникает, т.к. структура объекта, соответствующего понятию <двоичное> в правой части правила [5] в некотором смысле проще, чем структура объекта, соответствующего тому же  понятию в левой части (<двоичное> в правой части, как слово, попросту короче, чем в левой).

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

Вернёмся к примеру. Теперь, единственно недоопределённым элементом наших построений остаётся понятие <двоичная_цифра>, которое уточняется до терминального уровня так:

<двоичная_цифра> ::= 0 | 1

Собрав воедино выше приведённые определения, получим следующее формальное описание языка, представляющего множество всех объектов, рассматриваемых нами как <двоичное_чётное>:

‹двоичное_чётное›  ::= ‹двоичное‹ноль›

‹двоичное› ::= <двоичная_цифра> | <двоичная_цифра> <двоичное>

‹ноль› ::= 0

<двоичная_цифра> ::= 0 | 1

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

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

Точный смысл таких определений состоит в следующем. Пусть <L> - нетерминальный символ, дающий общее наименование всем словам некоторого, определяемого в БНФ языка L (тогда в БНФ-правилах, определяющих L  обязательно присутствует правило вида " <L> ::= ... " ) и пусть  w - некоторое слово, факт принадлежности которого языку L необходимо выяснить. Тогда, w принадлежит L тогда и только тогда, когда:

  1. w содержит только терминальные символы определяющей язык L  БНФ-системы правил;
  2. w может быть получено из <L> в результате некоторой последовательности применения правил данной БНФ-системы.

Например, имея ввиду выше приведённое БНФ- определённие языка "двоичное_чётное", легко убедиться (убедитесь самостоятельно!), что слово 101 никак не может быть получено из "начального" нетерминального символа  ‹двоичное_чётное›, а 1010 - может. Следовательно, 101 - не принадлежит, а 1010 - принадлежит рассматриваемому языку.

Содержательный практический пример применения метаязыка БНФ  для описания сильно упрощённой версии Паскаля дан в комментариях, здесь.



4.81818
Your rating: Нет Average: 4.8 (11 votes)

Комментарии

Задачка по БНФ

Определить в БНФ язык, состоящий из всех палиндромов (слов - перевёртышей, которые слева направо читаются так же, как справа налево) в алфавите B = {0,1}. Этому языку принадлежат, например, слова: 0110110, 101101, 101, 111010010111, ...

Решения предоставлять в красивом коде

попробую:)

может так:

  1. <ноль>::=0
  2. <единица>::=1
  3. <палиндром>::=<ноль>|<единица>
  4. <палиндром>::=<ноль><палиндром><ноль>|<единица><палиндром><единица>

возможно стоит представить в обратном порядке, то есть:

  1. <палиндром>::=<ноль><палиндром><ноль>|<единица><палиндром><единица>
  2. <палиндром>::=<ноль>|<единица>
  3. <единица>::=1
  4. <ноль>::=0

Но мне удобнее все же сначала определить исходное, а потом с ним оперировать:) возможно ошибаюсь)

Есть, Кирилл!

Зачтено!
И ещё задача ...
(но мне хотелось бы чтобы её попробовали другие, хотя можете прислать решение мне на почту).

хорошо:)

можно узнать вашу почту?)

Вопрос снимается заметил:)

БНФ - задача2

БНФ - задача2. Описать в БНФ язык всех правильно построенных скобочных записей в алфавите A= { (, ) }. Т.е. язык тех слов, которые могут быть получены, если стереть все знаки, кроме круглых скобок, в любом правильно построенном алгебраическом выражении, содержащем круглые скобки.

Вот примеры слов языка: (), (())(), ()()()(), и т.д.

e-mail внизу

Мой e-mail внизу страницы. Порядок следования БНФ формул роли не играет.

Задача №2

Может так

  1. <ППСЗ>::=()|(<ППСЗ>)

ППСЗ - правильно построенная скобочная запись

забыл еще одно

забыл еще одно условие

  1. <ППСЗ>::=()|<ППСЗ><ППСЗ>|(<ППСЗ>)

вот так наверное более правильно.

Можно проще

Можно проще, без дополнительных понятий:

  1. <плндр>::=0|1|0<плндр>0|1<плндр>1

Но есть тонкость - у Вас (а следом, и у меня) почти половина палиндромов теряется! Придумайте, что делать ...

Второе реш. верно, Александр.

Включайтесь в первую задачу.

чуть недосмотрел

  1. <ноль>::=0
  2. <единица>::=1
  3. <палиндром>::=<ноль>|<единица>
  4. <палиндром>::=<ноль><палиндром><ноль>|<единица><палиндром><единица>|<палиндром><палиндром>

а если

а если так

  1. <плндр>::=0|1|00|11|0<плндр>0|1<плндр>1

С палиндромом разобрались!

Кирилл -ошибка, Александр - верно.

рад стараться.

рад стараться.

ах да...может взять единицу и

ах да...может взять единицу и ноль

ВНИМАНИЮ СТУДЕНТОВ!

ВНИМАНИЕ! В меню "Статьи" появилось "Описание МиП".
Включайтесь в проработку!

<палиндром>::=<ноль>|<единица

<палиндром>::=<ноль> |<единица>
<палиндром><палиндром>
может выглядеть и как 01 так и 10

БНФ, Задача 3.

Определить в алфавите T={a,b} язык всех таких слов, в которых ни две буквы а, ни две буквы b никогда не cтоят рядом. Примеры слов языка: bab, a, ababab и т.д.

не знаю может я и ошибаюсь.

не знаю может я и ошибаюсь. но если не ошибаюсь то думаю есть и способы легче чем мой )

  1. <слово>::=<слово1>|<слово2>|<буква_а><буква_b>|<буква_b><буква_а>
  2. <слово1>::=<буква_а>|<слово1><сигмент1>|<слово1><сигмент1><буква_b>
  3. <слово2>::=<буква_b>|<слово2><сигмент2>|<слово2><сигмент2><буква_а>
  4. <сигмент1>::=ba
  5. <сигмент2>::=ab
  6. <буква_а>::=a
  7. <буква_b>::=b

Хорошо, Иван

Пока воздержусь от оценок Вашего решения. Хотелось бы послушать других ...
Единственное, попробуйте упростить, обойдясь без промежуточных понятий <сЕгмент1>,<сЕгмент2>, <буква_а>, <буква_b>.

И просьба ко всем - указывайте, пожалуйста, номер решемой задачи.

Очень громоздко вышло.

Очень громоздко вышло. Однако:

БНФ. Задача 3

  1. <слово>::=a|b|<слово1>|<слово2>|<слово3>|<слово4>
  2. <слово1>::=ba|a<слово1>b
  3. <слово2>::=ab|b<слово2>a
  4. <слово3>::=bab|ba<слово3>ab
  5. <слово4>::=aba|ab<слово4>ba

Хорошо бы оценить решение

Хорошо бы оценить решение Ивана, Кирилл. Да и Ваше решение ждёт оценок.
Люди, включайтесь!

хмм..

Кирилл, по моему, как я понял лекцию из этого

  1. <слово1>::=ba|a<слово1>b

могут получиться такие слова: ba , abab , aababb , aaababbb и т.д.
Или я ошибаюсь?

может так легче?

БНФ задача 3.

  1. <слово>::=<слово1>|<слово2>
  2. <слово1>::=<буква_а>|<слово1><сегмент1>|<слово1><буква_b>
  3. <слово2>::=<буква_b>|<слово2><сегмент2>|<слово2><буква_а>
  4. <сегмент1>::=ba
  5. <сегмент2>::=ab
  6. <буква_а>::=a
  7. <буква_b>::=b

Идея Ивана

Идея Ивана расслоить язык на два типа слов верна, но вот дальше ...
Громоздкость или не громоздкость описаний здесь не принципиальна.
Проверка правильности может состоять из попыток вывода некорректного <слова>. Как в решении Ивана,
так и в решении Кирилла мне это удаётся сделать. А кому ещё?

Ну вот, Иван уже кое-что

Ну вот, Иван уже кое-что заметил. Но и Кириллу есть чем ответить

хотя у Кирилла

  1. <слово3>::=bab|ba<слово3>ab
  2. <слово4>::=aba|ab<слово4>ba

эти строки нормально функционируют, но из них нельзя получить многие слова

Проверьте пожалуйста мой

Проверьте пожалуйста мой вариант решения задачи№3:

  1. <Слово>::=a|b|<сл1>|<сл2>
  2. <сл1>:=ab|<cл2>
  3. <сл2>:=ba|<cл1>

здесь теряем часть слов

здесь теряем часть слов

# <слово>::=<слово1>|<слово2>

#
<слово>::=<слово1>|<слово2>
#
<слово1>::=а|<сл1> ba
#
<слово2>::=b|<сл2>ab

хмм

Виталий, помоему это не всё решение, и через него нельзя получить некоторые слова.

Оля, Виталий, Игорь ...

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

P.s. Не ясно, что у Игоря означает "::= ..." c пустой левой частью.

и

Валерий Шахамболетович посмотрите моё решение.

БНФ задача 3.

  1. <слово>::=<слово1>|<слово2>
  2. <слово1>::=<буква_а>|<слово1><сегмент1>|<слово1><буква_b>
  3. <слово2>::=<буква_b>|<слово2><сегмент2>|<слово2><буква_а>
  4. <сегмент1>::=ba
  5. <сегмент2>::=ab
  6. <буква_а>::=a
  7. <буква_b>::=b

не заметил:)

а::=а
b::=b

Нет, Иван. У Вас выводимо,

Нет, Иван. У Вас выводимо, например, abb

Игорь.

"Правила" такого вида невозможны, да и бессмысленны.
Что в БНФ означает A::=B ? Только то, что Вы можете в формируемой Вами строке заменить любое A на B.
Но раз А подлежит замене, оно обязано быть неокончательным, т.е нетерминальным. А нетерминальные символы всегда заключены в угловые скобки!
Т. е. любое БНФ правило имеет вид <...>:= B.
Да и потом, что толку было бы a заменять на а и b заменять на b, что как раз и разрешают делать Ваши "правила"?
Вам необходимо внимательно перечитать и понять статью о БНФ на этом сайте, а так же изучить многочисленные комментарии на эту тему. Будут вопросы - спрашивайте. Удачи!

а всё нашел ошибку

попробую исправить)

хмм

Вполне может быть.

...

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

Виталий

abab

Виталий

у тебя не выводятся слова с четным количеством букв) и это хотя бы одно )

думаю это уже окончательное решение

БНФ задача 3

  1. <слово>::=<слово1>|<слово2>|<слово3>
  2. <слово1>::=a|<слово1> ba
  3. <слово2>::=b|<слово2> ab
  4. <слово3>::=b <слово1>|a <слово2>
  5. <сигмент1>::=ba
  6. <сигмент2>::=ab
  7. <буква_а>::=a
  8. <буква_b>::=b

Вань, погоди, а зачем ты

Вань, погоди, а зачем ты используешь понятие "сЕгмент" если оно не участвует в образовании слова?

ой секунду исправим )

да запутался че то )

вот так )

БНФ задача 3

  1. <слово>::=<слово1>|<слово2>|<слово3>
  2. <слово1>::=a|<слово1><сегмент1>
  3. <слово2>::=b|<слово2><сегмент2>
  4. <слово3>::=b <слово1>|a <слово2>
  5. <сегмент1>::=ba
  6. <сегмент2>::=ab
  7. <буква_а>::=a
  8. <буква_b>::=b

Позволь чуть подправить:)

<слово>::=<слово1>|<слово2>|<слово3>
<слово1>::=a|<слово1>ba
<слово2>::=b|<слово2>ab
<слово3>::=b<слово1>|a<слово2>

Опять же <буква_а> и <буква_b> не использовались:) но это чисто косметические изменения придирчивого взгляда со стороны:) а вообще вроде все работает:)

щас напишу как мне удобнее, ну я так вижу

  1. <слово>::=<слово1>|<слово2>|<слово3>
  2. <слово1>::=<буква_а>|<слово1><сегмент1>
  3. <слово2>::=<буква_b>|<слово2><сегмент2>
  4. <слово3>::=<буква_b><слово1>|<буква_а><слово2>
  5. <сегмент1>::=ba
  6. <сегмент2>::=ab
  7. <буква_а>::=a
  8. <буква_b>::=b

Да, Иван,Кирилл.

На этой задаче можно ставить точку. Молодцы!
Но я бы прислушался к замечанию Кирилла, Иван. Действительно, избыточные понятия только усложняют описание.
Чем полезно, например, слово <буква_а>, если вместо этого понятия всегда можно вписывать непосредственно саму букву а, т.е. тот терминал, которое это слово просто переобозначает? То же относится и к "сегментам".

О метаязыках, БНФ и строгом описании языков

О метаязыках, БНФ и строгом описании языков
прочтите эту статью.