Бэкуса-Наура формы (бнф)

Метаязыки Хомского и Хомского-Щутценберже использовались в математической литературе при описании простых абстрактных языков. Метаязык, предложенный Бэкусом и Науром, впервые использовался для описания синтаксиса реального языка программирования Алгол 60. Наряду с новыми обозначениями метасимволов, в нем использовались содержательные обозначения нетерминалов. Это сделало описание языка нагляднее и позволило в дальнейшем широко использовать данную нотацию для описания реальных языков программирования. Были использованы следующие обозначения:

• символ "::=" отделяет левую часть правила от правой;

• нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки "<" и ">";

• терминалы - это символы, используемые в описываемом языке;

• каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты "|".

Пример описания идентификатора с использованием БНФ:

1. <буква> :: = А|В|С|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V| W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

2. <цифра> :: = 0|1|2|3|4|5|6|7|8|9

3. <идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>

Правила можно задавать и раздельно:

3. <идентификатор> :: = <буква>

4. <идентификатор> :: = <идентификатор> <буква>

5. <идентификатор> :: = <идентификатор> <цифра>

Список рекомендуемой литературы

1. Андерсон Д.А. Дискретная математика и комбинаторика – Пер. с англ. – М.: ИД «Вильямс», 2004.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988

3. Судаплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Из-во НГТУ, 2002.– 280с.

4. Дискретная математика для программистов /Под ред. Ф.А. Новикова.– СПб: Питер, 2001.

5. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука. Физматлит, 2000.

6. Ерусалимский Я.М. Дискретная математика: теория. Задачи, приложения. – М.: Вузовская книга, 2001.

7. Дискретная математика // В. А. Горбатов, А. В. Горбатов, М. В. Горбатова Издательство: АСТ, Астрель , Высшая школа - 2006. – 448 c.

8. Ерусалимский Я. М. Дискретная математика Издательство: Вузовская книга – 2009. – 288c.

9. Баврин И. И. Дискретная математика Издательство: Высшая школа Серия: Для высших учебных заведений, 2007. – 200 c.

10. Редькин Н. П. Дискретная математика Издательство: ФИЗМАТЛИТ – 2009. – 264 c.

11. Иванов Б. Н. Дискретная математика. Издательство: ФИЗМАТЛИТ – 2007. – 408 c.

12. Дискретная математика //М. С. Спирина, П. А. Спирин Издательство: Академия Серия: Среднее профессиональное образование – 2010. – 368 c.

13. Набебин А. А. Дискретная математика Издательство: Научный мир. 2010. – 512 c.

14. Дискретная математика //С. Н. Поздняков, С. В. Рыбин Издательство: Образовательно-издательский центр "Академия", Серия: Высшее профессиональное образование. – 2008. - 448 c.

15. Дискретная математика. Практическая дискретная математика и математическая логика //С. Ф. Тюрин, Ю. А. Аляев. Издательство: Финансы и статистика, Инфра-М 2010. – 445 c.

16. Дискретная математика. Графы, матроиды, алгоритмы //М. О. Асанов, В. А. Баранский, В. В. Расин Издательство: Лань Серия: Учебники для вузов. Специальная литература 2010. 368 c.

17. Просветов Г. И. Дискретная математика. Задачи и решения Издательство: Альфа-Пресс – 2009. – 240 c.

1 http://pgap.chat.ru/zap/zap264.htm#0