09.17 Формулы Бэкуса-Наура, синтаксические диаграммы

https://moodle.cs.msu.ru/mod/lesson/view.php?id=1323

FIXME: поменьше философии, а то не успеваем хвост практики.

Формальный язык

множество конечных слов (строк, цепочек) над конечным алфавитом.

Как его описать?

• Перечислить все слова

  • Примеры коротких формальных языков? Yes/No, …

• Описать алгоритм порождения слов (правила составления, т. н. generator)

• Описать алгоритм распознавания слов (проверки принадлежности слова языку, т. н. parser)

Что понимается по «словом» в этом определении? неправильно, под словом понимается вся программа ☺

Алгоритмический язык

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

Язык программирования

знаковая система, предназначенная для записи компьютерных программ

Алгоритмический язык ≠ язык программирования:

• Примеры? псевдокод с умолчаниями — не ЯП, Пролог (любой ЯП с заложенным алгоритмом) — не АЯ; ДРАКОН — не АЯ, потому что он не ФЯ

Ахтунг! Путаница в терминах! В описании ЯП часто используют термин «слово» (или «ключевое слово»), но это не вся программа. Это некоторая последовательность символов, имеющая самостоятельное значение — «знак» или «лексема».

• Примеры? имя переменной, арифметическая операция, оператор и т. п.

Уровни рассмотрения ЯП (в скобках даны понятия из соответствующих разделов семиотики и лингвистики):

• Синтаксис («совокупность отношений между знаками») — комбинация лексем в допускаемую языком запись алгоритма.

• Семантика («смысловое значение единиц языка») — формализация поведения исполнителя при выполнении языковых конструкций (задание модели вычислений).

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

  • Пример: что происходит, если вы обращаетесь к одиннадцатому элементу массива размером 10?

Семинар

Форма для сдачи

Метаязык

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

• Обычно не включает семантику и уж тем более прагматику

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

Базовая:

1. Терминал: знак из лексики языка

2. Метапеременная (нетерминал): элемент, не принадлежащий лексике языка

3. Склейка: несколько терминалов и нетерминалов

4. Альтернатива: несколько элементов 1-3, разделённых «|»

5. Определение: нетерминал ::= элемент 1-4

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

В чём принципиальная разница между БНФ и НАМ? один — парсер, другой — генератор

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

• [ необязательная часть ] (встречается 0 или 1 раз)

• { повторяющаяся часть } (встречается 1 и более раз)

• ( группировка ) (для применения альтернативы, склейки и повторения к группе)

Особенности эмулятора

• Терминалы надо брать в кавычки
• Распознавание начинается с первого нетерминала в формуле

• Лексемы можно задавать регулярными выражениями вида #'…', но мы этого делать не будем

Разбор примера «целое число»:

number ::= ["-"] { digit }
digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

• Модифицировать пример, чтобы он не распознавал числа, начинающиеся с нуля

  • добавить распознавание единственного нуля

РБНФ -> БНФ: повторение — это рекурсия, необязательность — альтернатива

• number ::= "-" cardinal | cardinal
  cardinal ::= digit | digit cardinal
  digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

• Модифицировать пример БНФ, чтобы он не распознавал числа, начинающиеся с нуля, кроме нуля

• Группировка — это Декартово произведение

• Превратить РБНФ в БНФ

  yes ::= ("y" | "Y") ("e" | "E") ("s" | "S") 

• Построить РБНФ для периодической дроби. Примеры таких дробей: 0.5, 1.(3), 5.34656(45665)

В лекциях используется БНФ с итерацией, в УМК — БНФ с итерацией и необязательной частью, группировок в них нет.

Синтаксические диаграммы

Генератор, который может служить парсером.

• Терминал заключается в овал

• Нетерминал — в прямоугольник (используется в сложных конструкциях

• Стрелки указывают на возможный следующий символ при разборе / генерации

• Если для данного слова есть путь по стрелкам от начала до конца диаграммы оно принадлежит языку

Особенности построителя (более современная версия с разнообразным лишним)

• Направление обхода задаётся не стрелками, а закруглением линий (т. н. railroad diagram)
• Нужен для красоты! Поэтому включает в себя элементы разметки

• синтаксис

Примеры:

• Последовательность (Sequence( и ) можно убрать, если не нужна группировка)

  Sequence('a', 'b', 'c')

• Двоичное число (первый параметр Choice() — выбор, который будет нарисован посредине)

  OneOrMore(Choice(1, '0', '1'))

• Целое число (используется Skip())

  Choice(1,Skip(),'-'),
  OneOrMore(
      Choice(5,
             '0',
             '1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9'
     )
  )

• Диаграмма, распознающая «yes» или «no» буквами любого регистра

  • Подсказка: это Choice от двух Sequence от 2 или 3 Choice

• Составные диаграммы используют нетерминалы:

  Optional('-'),
  OneOrMore(NonTerminal('Цифра')),
  Optional(Sequence('.', OneOrMore(NonTerminal('Цифра'))))

• Диаграмма, распознающая последовательность сложений и вычитаний чисел-нетерминалов

  • + и - можно вставить в параметр «repeat»

• Описать с помощью синтаксической диаграммы товарный поезд. Поезд состоит из тяги и состава. Тяга содержит от одного до трех электровозов (Э). В состав входят крытые вагоны (К) и платформы (П). Между двумя соседними крытыми вагонами находятся как минимум две платформы.

  Если вдуматься, это язык описания языка описания формального языка o_O

Д/З

1. Палиндромом называется цепочка, которая читается одинаково слева направо и справа налево. Например, цепочки a, aba, abba являются палиндромами. Пустая цепочка также является палиндромом. Постройте синтаксическую диаграмму для палиндрома в алфавите {a, b}. Напоминаем, что синтаксическая диаграмма может содержать рекурсию.

2. Ожерелье Венеры состоит из начала и продолжения. Начало содержит ненулевое четное число топазов (Т). В продолжение входят рубины (Р) и сапфиры (С), продолжение не может быть пустым. В ожерелье может встречаться не более трех рубинов подряд. Постройте БНФ для ожерелья Венеры.
3. Язон засевает борозду зубами дракона. Первым нужно посеять клык (К), затем непустую последовательность из резцов (Р) и моляров (М). В борозде должно быть четное число моляров. Постройте синтаксическую диаграмму для засеянной зубами борозды.
4. «Произносимое слово» в алфавите {o,a,u,r,l,m} состоит из 1+2^n слогов, в каждом из которых 1-3 буквы, причём в слоге ровно одна гласная. Напишите БНФ для произносимого слова.
5. Если из арифметического выражения удалить все символы, кроме скобок, получим скобочную систему. Пустая цепочка также является скобочной системой. Постройте БНФ для скобочных систем.

   • Примеры скобочных систем: ()(), ((())), ((())()).

   • Главное - сбалансированность!

6. Глубиной скобочной системы называется максимальный уровень вложенности скобок. Например, система (()(())()()) имеет глубину 3, а система ()() глубину 1. Глубина пустой системы равна нулю. Постройте синтаксическую диаграмму для скобочных систем с глубиной не менее 2.