- •1. Формальные языки и грамматики
- •1.1. Введение
- •1.1.1. Трансляторы, интерпретаторы и компиляторы
- •1.1.2. Стадии работы компилятора
- •1.1.3. Построение компилятора
- •1.2. Определение формальной грамматики и языка
- •1.2.1. Первичные понятия
- •1.2.2. Примеры, иллюстрирующие первичные понятия
- •1.2.3. Пустой язык
- •1.2.4. Резюме
- •1.3. Типы формальных языков и грамматик
- •1.3.1. Грамматики типа 0
- •1.3.2. Грамматики типа 1
- •1.3.3. Грамматики типа 2
- •1.3.4. Грамматики типа 3
- •1.3.5. Вывод в кс-грамматиках и правила построения дерева вывода
- •1.3.6. Синтаксический разбор
- •1.3.7. Левый и правый выводы
- •1.3.8. Неоднозначные и эквивалентные грамматики
- •1.3.9. Резюме
- •1.4. Способы задания схем грамматик
- •1.4.1. Форма Наура-Бэкуса
- •1.4.2. Итерационная форма
- •1.4.3. Синтаксическая диаграмма
- •1.4.4. Резюме
- •1.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
- •1.5.1. Рекомендации по построению грамматик
- •1.5.2. Описание списков
- •1.5.3. Пример построения грамматик
- •1.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
- •1.5.5. Грамматики для арифметических выражений
- •1.5.6. Грамматика для описаний
- •1.5.7. Грамматика, задающая последовательность операторов присваивания
- •1.5.8. Грамматики, описывающие условные операторы и операторы цикла
- •1.5.9. Резюме
- •2. Автоматные грамматики и распознаватели
- •2.1. Автоматные распознаватели
- •2.2. Недетерминированные распознаватели
- •2.3. Преобразование некоторых типов языков и грамматик к автоматному виду.
- •2.4 Построение распознавателя для заданного конечного языка
- •2.5 Минимизация числа состояний распознавателя
- •2.6 Резюме
- •3. Контекстно-свободные грамматики и магазинные автоматы.
- •3.1 Приведенные грамматики.
- •3.2.Преобразование кс-грамматик
- •3.3 Магазинные автоматы.
- •3.4. Нисходящие распознаватели, ll(k) и разделенные грамматики. Построение распознавателя.
- •3.5. Функции перв, след и выбор.
- •3.6. Слаборазделенные и ll(1) - грамматики. Преобразование грамматик к виду ll(1)
1.1.3. Построение компилятора
Для построения компилятора необходимо однозначное и точное задание входного и выходного языков. Такое задание предполагает определение правил построения допустимых конструкций (выражений) языка. Множество таких правил называют синтаксисом языка. Кроме того, задание должно включать описание назначения и смысла каждой конструкции языка. Такое описание называют семантикой языка.
Для построения точных и недвусмысленных описаний применяют метод абстракций, который предполагает выделение наиболее существенных свойств рассматриваемого объекта и опускание свойств, менее значимых для рассматриваемого случая. Например, при построении модели входных языков можно рассматривать входной текст как последовательность символов, построенную по определенным правилам, отвлекаясь от характера начертания символов и их расположения на листе. Математические модели, использующие представление текстов в виде цепочек символов, называют формальными языками и грамматиками.
1.2. Определение формальной грамматики и языка
Изучение предмета начнем с определения первичных понятий.
1.2.1. Первичные понятия
Определение. Конечное множество символов, неделимых в данном рассмотрении, называется словарем или алфавитом, а символы, входящие в множество, - буквами алфавита. |
Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.
Определение. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Число букв, входящих в слово, называется его длиной. |
Например, слово в алфавите A a=ab++c имеет длину l(a) = 5, а слово в алфавите B b=00110010 имеет длину l (b) = 4.
Если задан алфавит A, то обозначим A* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A*.
Определение. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт, VA, <I> Î VA, R }, где Vт - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки порождаемые грамматикой; VA - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения; <I> - начальный символ грамматики <I> Î VA. R - множество правил вывода или порождающих правил вида a ® b , где aи b - цепочки , построенные из букв алфавита VтÈ VA, который называют полным алфавитом (словарем) грамматики Г. |
В множество правил грамматики могут также входить правила с пустой правой частью вида <Е> ® . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е> ® $.
Чтобы установить правила построения цепочек, порождаемых грамматикой , введем следующие понятия.
Определение. Пусть r = t ® g - правило грамматики Г и a = c't c" - цепочка символов, причем c', c" Î(Vт ÈVA) *. Тогда цепочка b= c' g c " может быть получена из цепочки путем применения правила r (т.е. заменой в m цепочки t на g). В этом случае говорят, что цепочка b непосредственно выведена из цепочки a и обозначают a Þb . Определение. Если задана совокупность цепочек W = ( v0, v1,...,vn), таких что существует последовательность непосредственных выводов: v0 Þ v1, v1 Þ v2, ... ,v n-1 Þv n, то такую последовательность называют выводом vn из v0 в грамматике Г и обозначают v 0 Þ* vn. Определение. Множество конечных цепочек терминального алфавита Vт грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L( Г). L( Г ) = {v Î Vт* | <I> Þ*v }. |