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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семинар

Метаязык

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

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

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

Базовая:

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

2. Метапеременная (нетерминал): элемент алфавита языка

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

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

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

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

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

Расширенная (EBNF):

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

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

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

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

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

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

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

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

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

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

EBNF -> BNF: повторение — это рекурсия, необязательность — альтернатива

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

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

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

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

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

• TODO упражнение на EBNF немного посложнее

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

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

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

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

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

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

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

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

• Направление обхода задаётся не стрелками, а закруглением линий (т. н. 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 иkи 3 Choice

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

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

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

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

• TODO Упражнение немного посложнее

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

Д/З

TODO Две-три задачи на БНФ и две-три на RRD