Реферат: Проектирование трансляторов
│ │ │ │
│ │ │ │
ОПРЕДЕЛЕНИЕ ПОДЛЕЖАЩЕЕ СКАЗУЕМОЕ ДОПОЛНЕНИЕ
│ │ │ │
голодный верблюд съел колючку
В самом общем виде в состав транслятора должны входить сле-
дующие блоки:
- Лексический анализ;
- Синтаксический анализ;
- Семантический анализ;
- Синтез программы на промежуточном языке;
- Оптимизация программы;
- Синтез объектной программы.
Лексический анализ реализуется с помощью лексического анали-
затора (сканера). ЛА выделяет лексемы из транслируемого сообще-
ния и заменяет их на символы языка. В процессе анализа могут воз-
никать ошибки.
Лексемы могут быть следующих классов:
- разделители;
- арифметические операции: + - / *;
- ключевые слова: for, begin, end, do, to, step;
- идентификаторы.
Синтаксический анализатор распознает синтаксис языка (струк-
туру).
Семантический разбор - это программа или группа программ,
занимающаяся распознаванием смысла сообщения.
Синтез программы - программа, которая занимается генерацией
программы на промежуточном языке.
Оптимизация программы - синтез программы в виде объектного
кода.
ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЯ ГРАММАТИКИ:
Грамматика - упорядоченная четверка G = (Vт, Vn, P, S), S C
Vn, множества терминальных Vt и нетерминальных Vn символов, грам-
матических правил P, начальный нетерминальный символ S или аксио-
ма.
Правила P непосредственно определяют процесс вывода. Хом-
ский ввел 4 класса грамматик:
1. Автоматная грамматика: символы, которые встречаются в ле-
вой части правил называются нетерминалами, они образуют множес-
тво нетерминальных символов Vn; символы, которые входят в множес-
тво Vт, называются терминалами. Нетерминалы и терминалы вместе
образуют словарь V.
V = Vn U Vт
U ::= N, U ::= WN
N C Vт, U,W C Vn
На базе автоматной грамматики строятся конечные или беско-
нечные автоматы, использующиеся для сканирования или синтаксичес-
кого анализа.
2. Контекстно-свободная грамматика:
U ::= u ; U C Vn , u C V
│ │
цепочка строка состоит из
исходного термин. и нетерм.
текста символов
(нетерм.)
Строка u сворачивается в U вне зависимости от контекста.
3. Контекстно-зависимые грамматики:
x U y ::= xuy
U C Vn; x,y,u C V
4. Грамматика без ограничения на правила вывода:
V ::= u u C V*, V C V*
Грамматика, которая позволяет разбирать арифметические выра-
жения:
<выражение>::= <терм>│
<выражение>+<терм>│
<выражение>-<терм>
<терм> ::= <множество>│
<терм>*<множество>│
<терм>/<множество>
<множество> ::= (<выражение>)│ i
i - идентификатор
Алфавит языка - это некоторое непустое конечное множество
элементов, называемых символами.
Всякая конечная последовательность символов языка называет-
ся цепочкой.
Пустая цепочка - цепочка, не содержащая ни одного символа.
Ее длина равна 0.
Множества цепочек в алфавите обычно обозначаются заглавными
буквами.
Х = mABCn
│ │
голова хвост
xy - конкатенация цепочек x, y. х - голова, у - хвост цепоч-
ки z=xy.
Произведение АВ двух множеств цепочек А и В:
AB = { xy │ x C A, y C B }
Степень цепочки: x^0 - "", x^N = x^(N-1)*x
V* - рефлексивно-транзитивное замыкание (итерация).
V+ - транзитивное замыкание (усеченная итерация).
Бесконечные множества:
V* = V^0 U V^1 U ... U V^N U ...
Формальное описание строки:
V*={z │ z = "",z = xU}, z,x C V*, U C V - любой символ из V.
Строка x непосредственно порождает y относительно P (x->y),
когда существуют строки u, w, (возможно пустые) такие, что x=uVw,
y=uzw, V ::= z C P.
Строка x порождает y относительно P (x=>y), когда сущес-
твует последовательность строк x0, x1, x2, ... xN, такая, что
x=x0, y=xN, xI-1 -> xI (I=1,2,...,N).
Язык - некоторое множество предложений:
Lg = { x │ x C Vt*, S => x }.
Порождение (либо свертывание) строк Lg можно представить в
виде дерева. Терминальные символы не порождают новых символов,
нетерминальные - порождают. Иначе терминальные символы - это те,
на которых образуются конструкции Lg.
Cентенциальная форма: S => x, х C V+.
Предложение - цепочка терминальных символов, выведенных из
аксиомы: { x │ S => x, x C Vt* }
Пусть w=xuy - сентенциальная форма. Тогда u - фраза для U C
Vn, если S => xUy и U => u. Простая фраза - если U -> u.
Основа - самая левая простая фраза. Существуют леворекурсив-
ные и праворекурсивные грамматики. Различные грамматики могут по-
рождать один и тот же L. Мы можем генерировать синтаксически пра-
вильные сообщения.
<предложение>::=<определение><подлежащее><сказуемое><дополнение>
<определение>::=<голодный>│<большой>
<подлежащее>::=<верблюд>│<слон>│ ...
<сказуемое>::=<съел>│<взял>│ ...
<дополнение>::=<колючку>│<ветку>│ ...
Используя функции порождения строк относительно синтаксиса
этого языка, можно генерировать строки, формально принадлежащие
этому языку, правильные синтаксически, но неверные семантически (
Пример - Глоклая куздра бодланула куздренка).
G1 и G2 эквивалентны, если порождаемые ими языки Lg1 и Lg2
равны. Эквивалентные преобразования грамматик могут быть ис-
пользованы для удобства выбора семантических программ.
Однозначная грамматика - если существует только одно дерево
вывода для каждого предложения Lg.
Разбор или синтаксический анализ сентенциальной формы - это
построение вывода и, возможно, синтаксического дерева для нее.
Существуют методы как нисходящего, так и восходящего разбо-
ра (относительно движения по синтаксическому дереву).
Непосредственный вывод xUy -> xuy называют каноническим, ес-
ли u C Vt*. Вывод w=>v канонический, если все непосредственные
выводы в нем канонические.
Сентенциальная форма, имеющая канонический вывод - канони-
ческая сентенциальная форма.
Свертывание будем называть проходом или анализом. В дальней-
шем будем считать, что в процессе анализа считывание входного
текста происходит слева направо, а свертывание начинается с той
самой левой части строки, которая может быть свернута без допол-
нительного анализа последующего текста. Такое свертывание будем
называть каноническим.
Отношения
->, => - символы отношений между цепочками.
Пара цепочек (c,d) принадлежит отношению R, если выполняет-
ся cRd.
Отношение P включает R, если из (c,d) C R следует (c,d) C Р.
Отношение, обратное R - R^(-1).
Рефлексивное отношение - при справедливости сRc.
Например: i <= i - рефлексивное, а i < i - не рефлексивное
отношение.
Транзитивное отношение R - если выполняется aRb, bRc => aRc.
Произведение R,P: cRPd - если существует е, такое что cRe и ePd.
Итерация R - (обозначается R*): aR*b - когда a=b или aR+b.
Ограничения, накладываемые на грамматику G:
- нет правил вида U ::= U;
- S=>xUy, U=>t, t C Vt* - приведенная грамматика;
Пример. G - язык арифметических выражений.
S ::= E
E ::= T
E ::= E+T
T ::= P
T ::= T*P
P ::= (E)
P ::= I
ЛЕКЦИЯ 3
АНАЛИЗ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ
С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ
Будем рассматривать каноническое свертывание контекстно-сво-
бодных (КС) языков. Нахождение эффективных методов свертывания -
одна из важнейших задач в теории построения трансляторов. В рас-
сматриваемых алгоритмах анализа входного текста, написанного на
КС-языке, используются отношения предшествования между каждой па-
рой соседних символов строки.
Рассмотрим подробнее отношения предшествования: пусть Si и
Sj - символы языка L (Si,Sj С V). Если в некоторой строке языка
они могут быть записаны рядом (...SiSj...), то между ними могут
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
