Задача трансляции
Необходимо выполнить перевод (преобразование текста), написанного на входном языке L, в некотороый воход
транслятор
Текст =L -> -> выход
Компилятор (транслятор) транслирует текст алгоритмического языка в язык более низкого уровня.
S-грамматики.
Грамматики вида: A->aβ, где а€Т, β€(ТUN)
Алгоритм:
Начальное состояние: поместить в магазин начальный символ грамматики
Рекурсивно: по очередному символу цепочки и верхнему символу магазина определить цепочку, которая должна быть помещена в магазин:
Если верхний символ магазина – нетерминал, то очередной входной терминал является ключом, определяющий правую часть правила грамматики, которой должен быть заменен нетерминал.
Если верхний символ магазина – терминал, он должен совпадать с очередным терминалом цепочки. При совпадении терминал выбрасывается из магазина и не его место записывается цепочка (епс)
Произвести сдвиг по входной цепочке
Уровни компиляции
Скелетная исходная программа
Препроцессор
Исходный код
Компилятор в промежуточный код
Промежуточный код
Компилятор в объектный код
Объектный код
Редактор связей
Абсолютный объектный код
Канонические выводы цепочек.
Вывод называется левосторонним/правосторонним, если в нем на каждом шаге вывода правило грамматики всегда применяется к крайнему левому/правому нетерминальному символу
Фазы анализа исходной программы. Краткая характеристика. Канонические выводы цепочек.
Исходная прога -> (лекс, синт, сем, анализаторы) -> (генератор промежуточного кода, оптимизатор кода, генератор кода) -> целевая программа
Эквивалентность грамматик.
Любой язык может быть порожден бесконечным числом грамматик. Грамматики называются эквивалентными, если они порождают один и тот же язык
Левая факторизация.
Если A->αβ1 | αβ2 представляют собой две А-продукции и входной поток начинается с непустой строки, порождаемой α, то нельзя сказать будет ли использоваться первая или вторая продукция, можно только отложить решение, проведя замену:
А->αA’
A’->β1 |β2
Лексический анализ. Краткая характеристика.
Линейный (лексический анализ). Поток символов программы считывается слева направо и группируется в лексемы. Для каждой лексемы строится токен, представляющие последовательности символов с определенным совокупным значением: <Имя, значение атрибута>
a:= b + c * 60 => <id,1> <:=> <id,2> <+> <id,3> <*> <60>
Группируется в следующие токены:
Идентификатор a <Id,1>
Символ присвоения <:=>
Идентификатор b <Id,2>
Знак сложения <+>
Идентификатор c <Id,3>
Знак умножения <*>
Число 60 <60>
Однозначность грамматик.
Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить единственный левосторонний (правосторонний) вывод. В противном случае грамматики называется неоднозначной.
Метод рекурсивного спуска.
Программа интерпретации арифметических выражений с грамматикой:
S->A=:E;
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|id|const
E->TE’
E’->+TE’|-TE’|ξ
T->FT’
T’->*FT’|\FT’|ξ
Синтаксический анализ. Краткая характеристика.
Иерархический анализ (синтаксический). Токены иерархически группируются во вложенные конструкции с совокупным значением. Группирование токенов в грамматические фразы, представленные в виде дерева (дерево разбора, синтаксическое дерево). Иерархическая структура выражена рекурсивными правилами
Построение таблицы переходов для метода рекурсивного спуска.
????????????????????????????????
Семантический анализ. Краткая характеристика.
Проверка корректности совместного размещения компонентов программы
Типы атрибутов в атрибутных грамматиках.
Синтезированные атрибуты. Вычисляются через семантические атрибуты потомков. Т.е. это такие атрибуты нетерминала в левой части продукции, значения которых определяются через значения атрибутов грамматических символов правой части продукции.
Унаследованные атрибуты. Вычисляются через семантические атрибуты предка. Т.е. через атрибуты символов правой части продукции значение которых определено через атрибуты других символов этой же продукции