01_gramm

Что будем рассматривать?
Что такое ЯЗЫК?
Какие существуют ФОРМАЛЬНЫЕ СПОСОБЫ описания языков?
Что такое ЯЗЫК ПРОГРАММИРОВАНИЯ с точки зрения разработчика компилятора?
Как строится компилятор?
Чем программа компилятора отличается от программы интерпретатора?
Как реализовать интерпретатор или компилятор?

Структура курса
(учебный план 09.03.04 )
Семестр 16 недель
Лекции: 32 часа (1 пара в неделю)
Лабораторные работы: 32 часа (1 пара в неделю)
Экзамен
Литература
Крючкова Е.Н. Методы анализа в теории формальных языков. / Учебное пособие – 276 с.

Лабораторные работы
1 (2 часа) Синтез КС-грамматик
2 (2 часа) КС-грамматика языка программирования
3 (2 часа) Лексика (таблица лексем, конечный автомат лексики, конечный автомат игнорируемых символов)
4 (2 часа) Программа лексического анализатора (сканер)
5 (2 часа) Построение синтаксических диаграмм и их преобразование
6 (2 часа) Синтаксический анализатор ( метод рекурсивного спуска)
7 (2 часа) Анализ контекстных условий языка программирования.
8 (2 часа) Реализация семантического дерева
9 (2 часа) Полный семантический анализ
10 (2 часа) Данные интерпретатора
11 (2 часа) Запись и выборка данных при интерпретации
12 (2 часа) Интерпретация выражений
13(2 часа) Работа с флагом интерпретации - проектирование
14(2 часа) Работа с флагом интерпретации - реализация
15 (2 часа) Промежуточный код - проект конструкций

Отчеты по работам
Отчет по каждой работе в электронном виде должен быть оформлен и сдан:
Отчет по каждой работе оформляется в виде одного файла *.txt или *.doc или *.docx.
Название любого такого файла стандартное: <номер работы>_<номер группы>_<Фамилия студента>
Примеры: 06_92_Иванов.zip, 03_92_Ivanov.doc
Отчеты отсылаются на адрес [e-mail]

Задания №1 и №2
Задание №1 (работа №1) – в учебнике.
Залание №2 (работы 2-15) - в файле в ЛК.
Лабораторная работа 1 – синтез КС-грамматик
Лабораторные работы №2-15 - методы трансляции языков программирования

Задание по трансляторам
В каждом задании описывается некоторый очень усеченный вариант известных языков программирования Java и С++. В задании указывается:
структура программы,
типы данных, которые могут использоваться,
допустимые операции над этими данными,
операторы,
операции и операнды, из которых строятся выражения,
все виды констант, которые могут использоваться в выражениях.

Пример задания по трансляторам
Программа: главная программа языка С++. Допускается описание функций без параметров, функции возвращают значение.
Типы данных: int ( в том числе short , long long, long) .
Операции: арифметические, сравнения.
Операторы: присваивания и do{}while().
Операнды: простые переменные и константы.
Константы: целые в 10 c/c и 16 c/c .

Обратите внимание на полноту реализации задания
во всех заданиях предполагается использование составного и пустого оператора,
всегда разрешается описание глобальных данных,
все перечисленные элементы языка должны использоваться в программе (например, если разрешается описание функций, то, безусловно, в перечень операторов Вам необходимо включить вызовы функций).

Тема 1
Формальные грамматики и языки

Базовые понятия
Алфавит - непустое конечное множество символов.
Цепочка над алфавитом Σ - конечная
последовательность символов алфавита. Длина цепочки x - число ее символов, обозначается |x|. Цепочка нулевой длины называется пустой
цепочкой и обозначается ε .
Множество всех цепочек (включая ε ) над алфавитом Σ обозначается Σ*
Язык L над алфавитом Σ - подмножество множества Σ*, то есть L ⊆ Σ*

Примеры алфавита
Алфавит Σ = {0,1}
Σ* = {ε , 0, 1 ,00, 01, 10, 11, 000,…}
Алфавит Σ = {0,1,…,9,x,X,a,…f,A,…F}
0Xff8a4 ∈ Σ* | 0Xff8a4| = 7
aa4Xff8x ∈ Σ*
Множество часел в 16с/с – подмножество Σ* , но не равно Σ*
Алфавит языка программирования С++ - все символы клавиатуры

Грамматика
Порождающая грамматика - упорядоченная четверка
G = (VT , VN ,P ,S), где
VT - алфавит терминальных символов;
VN – алфавит нетерминальных символов;
P --- конечное множество правил вывода,
u ? v, где u ,v ∈ (VT ∪ VN )* ;
S- начальный нетерминальный символ - аксиома грамматики.
Вывод цепочек языка из S по правилам грамматики

Типы G = (VT , VN ,P ,S)
Тип грамматики определяется сложностью правил P ={u ? v | u ,v ∈ (VT ∪ VN )*
Тип 0 – нет ограничений
Тип 1 - НС-грамматики
αAβ → αϕβ, A ∈VN , α,ϕ,β ∈ (VT ∪ VN )*
Тип 2 – КС-грамматики
A → ϕ, A ∈VN , ϕ ∈ (VT ∪ VN )*
Тип 3 – Автоматные грамматики
- праволинейные
A→ xB или A→ x, A ,B∈VN , x ∈ VT
- леволинейные
A→ Bx или A→ x, A ,B∈VN , x ∈ VT

Пример грамматики
G = (VT ,VN ,P ,S), где
VT = {0,1,…,9,x,a,…f}
VN = {S, H, C}
P = {S?0xH, H?HC, H?C, C?0, C?1, … , C?9, C?a, …, C?f}
Стандартная запись грамматики
G: S ? 0xH
H ? HC | C
C ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f
Пример вывода
S ? 0xH ? 0xHC ? 0xHCC ? 0xCCC -> 0xaCC ? 0xa8C ? 0xa8f

Обозначение нетерминалов
Вариант 1 - большие латинские буквы
(при условии их отсутствия в VT)
G: S ? 0xH
H ? HC | C
C ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a |b | c | d | e | f
Вариант 2 – текст в угловых скобках
G: <число 16> ? 0x <цифры 16>
<цифры 16> ? <цифры 16> <одна цифра 16>
| <одна цифра 16>
<одна цифра 16> ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| a |b | c | d | e | f

Правила КС-грамматики
G = (VT ,VN ,P ,S)
конструкция правила
<нетерминал> ? <цепочка из VT и VN >
Пример
S ? SaB | c
B ? xBy | ε ε - пустая цепочка, | ε | = 0
Пример вывода
S ? SaB ? SaBaB ? caBaB ? caaB ? caaxBy ? caaxxByy ? caaxxxByyy ? caaxxxyyy
Вывели ca2x3y3

КС-грамматика и дерево вывода
Правила вывода в КС-грамматике A ? ϕ
A ∈ VN, ϕ ∈ (VT ∪ VN)*
G: S ? aSAb | c
A ? cA | d
Вывод
S ?aSAb ? acAb
?accAb
? acccAb? acccdb
Дерево вывода

Операции над языками
1) Обычные теоретико-множественные: Объединение L1 ∪ L2
Пересечение L1 ∩ L2
Разность L1 \ L2
2) Специальные:
Произведение или конкатенация L1 L2
Возведение в степень Ln,
Итерация L*,
Усеченная итерация L+

Операции – инструмент синтеза КСГ
Теорема
Семейство КС-языков замкнуто относительно операций объединения, произведения, итерации и усеченной итерации.
Метод синтеза КСГ
Есть КСГ G1 и G2 простых языков L1 и L2
Строим нужную нам КСГ как вариант из L1 ∪ L2, L1 L2 , L2 *, L2 +

Доказательство для L1 L2
Конкатенация (умножение)
Дано:
G1 = (VT1 ,VN1 ,P1 ,S1), G2 = (VT2 ,VN2 ,P2 ,S2)
Нужна грамматика языка L(G) = L(G1) L(G2)
Решение:
VN1 ∩ VN2 = ∅
Новая грамматика с новым нетерминалом S
P = P1 ∪ P2 ∪ {S ? S1 S2 }
Вывод в G
S? S1 S2 ?α S2 ? α β
α выводится в G1 , β выводится в G2

Доказательство для L1 ∪ L2
Объединение
Дано:
G1 = (VT1 ,VN1 ,P1 ,S1), G2 = (VT2 ,VN2 ,P2 ,S2)
Нужна грамматика языка L(G) = L(G1) ∪ L(G2)
Решение:
VN1 ∩ VN2 = ∅
Новая грамматика с новым нетерминалом S
P = P1 ∪ P2 ∪ {S ? S1 | S2 }
Выводы в G (два варианта, так как два привила)
S? S1 ?α или S? S2 ? β
α выводится в G1 , β выводится в G2

Доказательство для L*
Итерация
Дано: G1 = (VT1 ,VN1 ,P1 ,S1)
Нужна грамматика языка L(G) = L(G1) *
Решение:
Новая грамматика с новым нетерминалом S
P = P1 ∪ {S ? S S1 , S ? ε }
Выводы в G
S ? ε
S? SS1 ? S1 ? β
S? SS1 ? SS1S1 ? S1S1 ? …
S? SS1 ? SS1S1 ? SS1S1S1 ? S1S1S1 ? …
…
…
…

Правая рекурсия для L*
Итерация
Дано: G1 = (VT1 ,VN1 ,P1 ,S1)
Нужна грамматика языка L(G) = L(G1) *
Решение:
Новая грамматика с новым нетерминалом S
P = P1 ∪ {S ? S1S , S ? ε }
Выводы в G
S ? ε
S? S1 S ? S1 ? β
S? S1S ? S1S1S ? S1S1 ? …
S? S1S ? S1S1S ? S1S1S1 S ? S1S1S1 ? …
…
…
…

Доказательство для L+
Усеченная итерация
Дано: G1 = (VT1 ,VN1 ,P1 ,S1)
Нужна грамматика языка L(G) = L(G1) +
Решение:
Новая грамматика с новым нетерминалом S
P = P1 ∪ {S ? S S1 , S ? S1 }
Выводы в G
S ? S1 ? β
S? SS1 ? S1 S1 ? …
S? SS1 ? SS1S1 ? S1S1S1 ? …
…
…
…
…

Правая рекурсия для L+
Усеченная итерация
Дано: G1 = (VT1 ,VN1 ,P1 ,S1)
Нужна грамматика языка L(G) = L(G1) +
Решение:
Новая грамматика с новым нетерминалом S
P = P1 ∪ {S ? S1 S , S ? S1 }
Выводы в G
S ? S1 ? β
S? S1 S ? S1 S1 ? …
S? S1 S ? S1 S1 S ? S1S1S1 ? …
…
…
…
…

Пример: язык (ab)*c ∪ b+
G: S ? A | B // объединение (ab)*c и b+
A ? TF // произведение (ab)* и c
F ? c
T ? Tab | ε // итерация ab
B ? Bb | b // усеченная итерация b
Можно проще:
G: S ? A | B
A ? Tс
T ? Tab | ε
B ? Bb | b
Или еще проще*
G: S ? Tc | B
T ? Tab | ε
B ? Bb | b

Пример: идентификатор С++
Идентификатор – это последовательность букв и цифр, начинающаяся с буквы. Знак подчеркивания рассматривается как буква.
G: <идент> ? <буква> <окончание>
<буква> ? a |b | … | z | A | B | … | Z | _
<окончание> ? <окончание> <буква>
| <окончание> <цифра>
<цифра> ? 0 | 1 | 2 | … | 9

Симметрия в языке
L = αnγβn , n >= 0
S ? αSβ | γ
Вывод
S ? αSβ ? α2Sβ2 ? α3Sβ3 ? … ? αnSβn ? αnγβn
Не путать с L = α*γβ*
S ? AγB
A ? A α | ε
B ? Bβ | ε

Простой пример симметрии
Симметричные конструкции
S ? ASB | X
L(S) = L(A)n L(X) L(B)n n >= 0
Пример
(ab)n c (xyz)n n>=0
S ?abSxyz | c

Пример симметрии
L = a2nd(a+b*с)n+1 , n >= 0
Выделим симметрию
L = a2nd(a+b*с)n+1
= (aa)n d a+b*с (a+b*с)n
2. Строим КС-грамматику
G: S ? aaSB | dB
B ? THc
T ? Ta | a
H ? Hb | ε
? AγB
A ? A α | ε
B ? Bβ | ε

Преобразования КСГ
Подстановки
Новые нетерминалы для фрагментов
Неукорачивание
Левая рекурсия ? правая
Правая рекурсия ? левая
Удаление одинаковых правых частей правил
Удаление правил «нетерминал ? нетерминал»
Удаление лишних нетерминалов
…

Левая рекурсия ? правая
Были правила
S ? SA | B
Вывод:
S ? SA ? SAA ? SA* ? BA*
Новые правила
S ? BH
H ? AH | ε
Новый вывод
S ? BH ? BAH ? BAAH ? … ? BA*

Левая рекурсия ? правая
(Общий случай)
Были правила
S ? Sβ1 | Sβ2 | … | Sβk | ϕ1 | ϕ2 | … | ϕm
Преобразуем :
S -> SX | Y (будет S?YH H?XH | ε)
X ? β1 | β2 | … | βk
Y ? ϕ1 | ϕ2 | … | ϕm
Новые правила строим так же, как и ранее
S ? ϕ1 H | ϕ2 H | … | ϕm H
H ? β1 H | β2 H | … | βk H | ε
Новый вывод
S ? BH ? BAH ? BAAH ? … ? BA*

Правая рекурсия ? левая
(Общий случай)
Были правила
S ? β1S | β2S | … | βkS | ϕ1 | ϕ2 | … | ϕm
Преобразуем :
S -> XS | Y (будет S? HY H?HX | ε)
X ? β1 | β2 | … | βk
Y ? ϕ1 | ϕ2 | … | ϕm
Новые правила строим так же, как и ранее
S ?H ϕ1 H | Hϕ2 | … | Hϕm
H ? Hβ1 | Hβ2 | … | Hβk | ε
Новый вывод
S ? BH ? BAH ? BAAH ? … ? BA*

Рекурсия
Грамматика конечна по опреледению.
Язык, как правило, бесконечен.
Рекурсия – единственный способ представить бесконечный язык конечными средствами.
Типы рекурсии:
Левая A ? Ab,
Правая A -> bA,
Центральная A ? aAb,
Неявная A ? xBy B ? uDv D ? aAb .

Рекурсия конструкций ЯП
<оператор> ? <простой оператор>
| <составной оператор>
| <пустой оператор>
<пустой оператор> ? ;
<составной оператор> ? {<опер и описания>}
<простой оператор> ?
|
|
|…
? if (<выражение>) <оператор>
|if (<выражение>) <оператор> else <оператор>
? while (<выражение>) <оператор>
<опер и описания> ? <опер и описания> < оператор >
| <опер и описания> < описание >
| ε

Синтаксический анализ
Задача любого транслятора – построить дерево грамматического разбора.
Если язык бесконечен, а КС-грамматика конечна, то в дереве СА достаточно длинной цепочки обязательно на некотором пути из корня в лист повторится некоторый нетерминал A ? unAwn ? unzwn

Лемма о разрастании
Для любой КС - грамматики, порождающей бесконечный язык, существуют такие натуральные числа p и q, что каждая цепочка γ ∈ L(G), | γ |>p
может быть представлена в виде γ = xuzwy, где |uw|>q и для любого n>0 цепочка x unzwn y ∈ L(G).
Мы получили на предыдущем слайде
нетерминал A ? unAwn ? unzwn

Следствие – теорема о языке anbncn
Теорема
Язык anbncn не является КС-языком.
Вывод: КС-грамматика не может синхронизировать более двух фрагментов.
Пример
int aaaa;
// идентификаторы состоят только из букв a
int main() {
cin >> aaaa;
cout << aaaa * 2;
}

Недетерминированность КСГ недопустима !!!
Пусть V == <выражение> a == <идент>
G: V ? V+V | V-V | V*V | V/V | (V) | a

Выражения
Нет понятия логического, арифметического и т.п. выражения:
Работает семантика контекстных условий для контроля корректности выражений:
int x, z[3][100], T[100];
bool y;
x[i] = z * y(6.7) – 5; // семантические ошибки
T[i] = x * sin(6.7) – 5; // верная конструкция
double a = x – 7.78; // приведение типов

Синтаксис выражений
1 Упорядочить группы операций по приоритетам, начиная с низкоприоритетных .
2 Каждой группе поставить в соответствие нетерминал А1, А2, А3, … ,An
3 Для каждого нетерминала Ai записать правила для каждой операции группы(см. следующий слайд)
4 Добавить правила, соответствующие неприменению операции
Ai ? Ai+1
5 Определить правила для элементарного выражения An+1

Правила для группы многократных операций
Операции многократные, т.е. разрешается запись а*а*а*а
Операция бинарная
выполнение слева направо Ai ? Ai * Ai+1
справа налево Ai ? Ai+1 * Ai
Операция префиксная унарная Ai ? * Ai
постфиксная унарная Ai ? Ai *

Правила для группы однократных операций
Операции однократные, т.е. НЕ разрешается запись а*а*а*а
Операция бинарная Ai ? Ai +1* Ai+1
Операция префиксная унарная Ai ? * Ai+1
постфиксная унарная Ai ? Ai +1*

Пример выражения с бинарными операциями
A1 > < ==
A2 + -
A3 * /
A1 ? A1 > A2 | A1 < A2 | A1 == A2 | A2
A2 ? A2 + A3 | A2 – A3 | A3
A3 ? A3 * A4 | A3 / A4 | A4
A4 ? <идентификатор> | <константа> | (A1)

Лабораторная работа №1
1. Построить КС-грамматику по заданию в учебнике (№ задания == номер в списке группы)
2 . Построить деревья разбора для двух разных цепочек
Учебное пособие (содержит теоретический материал и пример выполнения задания):
глава 1 - материал по грамматикам

Лабораторная работа № 2
1. Построить таблицу приоритетов операций языка программирования индивидуального задания
2. Построить КС-грамматику языка программирования индивидуального задания
Учебное пособие (содержит теоретический материал и пример выполнения задания):
глава 3

Языки, грамматика, автоматы
Грамматика порождает язык
Автомат распознает язык
Программист использует (1) при создании программы
Транслятор использует (2) в процессе работы
Вывод: (1) и (2) должны быть эквивалентны
Разработчик транслятора создает грамматику, выбирает метод распознавания, реализует метод распознавания в соответствии с грамматикой

Типы автоматов при трансляции
Машина Тьюринга == любой алгоритм.
Требование трансляции - эффективность T(v) = O(n)

Автоматы при трансляции
Конечный автомат ? лексика языка
(переходит из состояния в состояние, читая символы)
МП-автомат (автомат с магазинной памятью ? синтаксис языка)

Синтез конечных автоматов
Учебное пособие (содержит теоретический материал и примеры):
глава 2

Целые константы:
1) 8с/с – начинается с 0,
2) 16c/c – начинаются 0x или 0X,
3) 10 с.с – начинаются с цифры, не равной нулю

Целые константы