Математика - это язык. (Гиббс) 

Задача определения языка

• Как определить используемый язык?
• Определение должно быть удобным, т.е.:
  - Определение должно быть конечным
  - Должен существовать алгоритм, за конечное число
  шагов проверяющий принадлежность некоторой
  входной цепочки языку
• Наиболее распространенные формализмы для
  задания языков: грамматики, регулярные
  выражения, конечные и магазинные автоматы,
  машины Тьюринга

Определение грамматики

• Грамматика определяется путем задания
  следующих компонент:
  - Терминальные символы (алфавит)
  - Нетерминальные символы (иногда также
  называемые понятия)
  - Правила вывода
  - Начальный символ 

Некоторые свойства грамматик

• Различные грамматики могут порождать один
  и тот же язык. Такие грамматики называются
  эквивалентными
• Левые части правил могут содержать другие
  нетерминалы (помимо определяемого)
•  По соглашению, можно объединять несколько
  правил с одинаковой левой частью, записывая
  правые части через символ '|' ("или")

Иерархия Хомского

• Включающая иерархия языков:
  - Грамматика без ограничений
  - Контекстно-зависимая грамматика
  - Контекстно-свободная грамматика
  - Выровненные влево или вправо грамматики (они же
  регулярные, лево- или праволинейные)
• Чем меньше ограничений накладывается на
  грамматику, тем более сложный язык
  программирования можно задать с ее помощью

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

• Каждому классу языков соответствует
  эквивалентный класс распознавателей:
  - Язык, задаваемый грамматикой без ограничений,
  определяется машиной Тьюринга
  - Контекстно-зависимые языки определяются
  линейно ограниченными автоматами
  - Контекстно-свободные языки определяются
  автоматом с магазинной памятью
  - Праволинейные языки определяются конечным
  автоматом

Конечные автоматы

• Конечный автомат - это пятерка:
   - конечное множество состояний
   - конечное множестводопустимых
  входных символов
   - функция перехода
   -  начальное состояние
   - множество заключительных состояний

Детерминированные конечные автоматы

• Автомат называется детерминированным, если
  множество значений функции перехода содержит не более одного состояния
  для любых q, a. Если всегда содержится  ровно
  одно состояние, то автомат называется полностью
  определенным.
• Цепочка w допускается автоматом M, если существует
  последовательность шагов, приводящая нас по этой
  цепочке в заключительное состояние автомата
• Язык распознается конечным автоматом, если им
  распознается каждое слово языка
• Удобная форма записи конечных автоматов -
  диаграммы переходов

Недетерминированные и конечные автоматы

• Любому недетерминированному автомату
  соответствует детерминированный автомат,
  определяющий тот же самый язык, причем известен
  метод конструирования эквивалентного конечного
  автомата
• Таким образом, классы языков, задаваемых
  недетерминированными и детерминированными
  конечными автоматами, совпадают
• Конечные автоматы - удобный формализм, так как их
  легко моделировать программно

Эквивалентность конечных автоматов

• Два детерминированных автомата
  называются эквивалентными, если они
  распознают один и тот же язык
• Алгоритм проверки эквивалентности
  конечных автоматов

Минимизация конечного автомата

• Как найти автомат, эквивалентный данному, с
  минимальным числом состояний?
• Алгоритм минимизации конечного автомата
  выглядит так:
  - Вначале мы удаляем все недостижимые состояния
  - Затем разбиваем множество всех достижимых
  состояний на классы эквивалентности
  неразличимых состояний
  - Из каждого класса эквивалентности мы берем
  только по одному представителю

Эквивалентность праволинейных грамматик и конечных автоматов

• Любой конечно-автоматный язык может быть
  определен праволинейной грамматикой и наоборот,
  т.е. классы языков, определяемых этими
  формализмами, эквивалентны
• Для класса языков, задаваемых праволинейными
  грамматиками, можно проверить следующие свойства:
  - Эквивалентность двух языков
  - Пустоту определяемого языка
  - Принадлежит ли входная цепочка заданной грамматике
• К сожалению, праволинейные грамматики позволяют
  задать только весьма ограниченный класс языков

Свойства КС-грамматик

• Процесс синтаксического анализа программы
  можно рассматривать как определение
  принадлежности некоторой цепочки данной
  контекстно-свободной (КС-) грамматике
• Существует проблема неоднозначности
  грамматик
• Проблема учета приоритетов операций
• Для разрешения этих и других проблем
  прибегают к преобразованию грамматик

О преобразовании грамматик

• К сожалению, не существует общего
  механизма приведения КС-грамматик к
  произвольному виду
• Однако известно, что любая КС-
  грамматика может быть приведена к
  нормальному виду Хомского
• Другой стандартный вид КС-грамматик
  - это нормальная форма Грейбах

Магазинные автоматы

• МП-автомат определяется как семерка, где есть:
   - конечное множество состояний
   - конечный входной алфавит
   - конечный алфавит магазинных символов
   - функция перехода
   - начальное состояние
   - начальный символ магазина
   - множество заключительных состояний
• Известно, что МП-автоматы задают тот же класс
  языков, что и КС-грамматики

Детерминированные МП-автоматы

• МП-автоматы недетерминированны. Поэтому
  мы рассмотрим класс детерминированных МП-
  автоматов, которые в каждой конфигурации
  могут сделать не более одного такта
• Детерминированные МП-автоматы очень
  полезны в задачах компиляции
• К сожалению, детерминированные МП-
  автоматы определяют более слабый класс
  языков, чем КС-грамматики.

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

• Основные символы
• Металингвистические переменные
• Металингвистические связки

Расширенная форма Бэкуса-
Наура

• Расширенная форма Бэкуса-Наура,
  использованная Виртом
• В 1981 году Британский институт
  стандартов (British Standards Institute)
  опубликовал стандарт EBNF (BSI).

Грамматика ван Вейнгаардена

• Метаправила
• Гиперправила
• Порождающие правила

 

Литература к лекции

А. Ахо, Дж. Ульман "Теория синтаксического анализа, перевода и компиляции", Т.1 "Синтаксический

анализ", М.: Мир, 1978

Р. Хантер "Проектирование и конструирование компиляторов", ФиС,

1984