Реферат: Проектирование трансляторов
V* - рефлексивно-транзитивное замыкание множества V.
Фоpмальная гpамматика - фоpмальная система пpавил, описываю-
щих в опpеделенном аспекте некотоpый язык G=(Vt,Vn,P,S), где:
Vt - множество терминальных символов;
Vn - множество нетерминальных символов;
P - конечный набор правил подстановки;
S С Vn - начальный символ.
Символы в левой и правой частях правил в совокупности обра-
зуют словарь V, V = Vt U Vn.
Символы грамматики G, встречающиеся в левой части правил,
называются нетерминальными. Множество нетерминалов Vn С V являет-
ся подмножеством словаря, остальная часть множества V образует
множество терминальных симолов Vt С V.
В зависимости от ограничений, накладываемых на грамматичес-
каие правила (продукции), различают 4 основных класса грамматик
(по Хомскому). Их определение содержится ниже.
Правила автоматной гpамматики имеют вид:
U ::= N или U ::= NW, где N C Vt, а U, W C Vn.
Правила контекстно-свободной гpамматики имеют вид:
U ::= u, где U C Vn, u C V.
Правила контекстно-зависимой грамматики имеют вид:
xUy ::= xuy, где U C Vn, x, u, y C V.
Грамматика без ограничений на грамматичекие правила:
u ::= v, где u C V+ и v C V*.
Всякая конечная последовательность символов алфавита А назы-
вается цепочкой.
Непосредственный вывод. Пусть G - грамматика. Говорят, что
цепочка v непосредственно порождает цепочку w, т.е. v -> w, если
для некоторых цепочек x и y можно написать v = xUy, w = xuy, где
U ::= u - правило грамматики G. Также говорят, что w непосред-
ственно выводима из v.
Вывод. Пусть G - грамматика. Цепочка v порождает цепочку w,
т.е. v => w, если существует последовательность непосредственных
выводов v = x1 -> x2 -> x3 -> ... -> xn = w.
Формальный язык L(g) = S=>x, x С Vt+ Таким образом,
язык - это выводимое из S подмножество множества всех терми-
нальных цепочек, т.е. цепочек в Vt.
Сентенциальная форма. S => x - цепочка символов языка х, по-
рождаемых из аксиомы S.
Предложение: S=>x, x C Vt* - выводимая из аксиомы S
цепочка терминальных символов, принадлежащая рефлексивно-транзи-
тивному замыканию множества терминальных символов Vt*.
Транслятор - это программа, которая преобразовывает сообще-
ние, написанное на языке L1, в сообщение, написанное на языке L2,
с сохранением смысла.
Формальный язык характеризуется алфавитом, лексикой, семан-
тикой и синтаксисом.
┌──────────── ПРЕДЛОЖЕНИЕ ───────────┐
│ │ │ │
│ │ │ │
ОПРЕДЕЛЕНИЕ ПОДЛЕЖАЩЕЕ СКАЗУЕМОЕ ДОПОЛНЕНИЕ
│ │ │ │
голодный верблюд съел колючку
В самом общем виде в состав транслятора должны входить сле-
дующие блоки:
- Лексический анализ;
- Синтаксический анализ;
- Семантический анализ;
- Синтез программы на промежуточном языке;
- Оптимизация программы;
- Синтез объектной программы.
Лексический анализ реализуется с помощью лексического анали-
затора (сканера). ЛА выделяет лексемы из транслируемого сообще-
ния и заменяет их на символы языка. В процессе анализа могут воз-
никать ошибки.
Лексемы могут быть следующих классов:
- разделители;
- арифметические операции: + - / *;
- ключевые слова: 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. В строке ...SiSj... свертываемая часть строки начинается
└──┘
с символа Sj, то есть Sj - самый левый символ свертываемой под-
строки. Если при этом Si не является последним символом другой
строки свертываемой подстроки, то будем говорить, что Si предшес-
твует Sj. Запишем это условие в виде Si < Sj.
2. В строке ...SiSj... символы Si и Sj входят в одну и ту
└────┘
же свертываемую часть строки.Этот факт запишем в виде Si = Sj и
будем говорить, что Si и Sj входят в одно и то же свертывание.
3. В строке ...SiSj... свертываемая часть строки кончается
└──┘
символом Si, то есть Si - самый правый символ свертываемой части
строки. Это условие запишем в виде Si > Sj и будем говорить, что
Sj следует за Si.
Отношения <, =, > назовем отношениями предшествования. Отно-
шения предшествования обычно записываются в виде матрицы, стол-
бцы и строки которой соответствуют символам словаря V. На пересе-
чении i-ой строки и j-го столбца записывается отношение предшес-
твования между символами Si и Sj. Элементами матрицы являются
знаки <, =, > или пусто. Последний случай означает, что символы
Si и Sj ни в одной строке языка не могут стоять рядом.
В дальнейшем будет введено формальное определение отношений
предшествования и дан алгоритм их определения.
Сейчас же мы рассмотрим алгоритм анализа программы, разрабо-
танный Виртом и Вебером.
Достоинство этого алгоритма заключается в том, что он сни-
мает дополнительное ограничение на грамматику языка, и допускает,
чтобы в правилах грамматики два нетерминальных символа стояли ря-
дом. Но и в этом алгоритме требуется, чтобы между каждой парой
символов языка существовало не более одного отношения предшество-
вания и в множестве синтаксических правил не было двух одинако-
вых правых частей, т.е. правил, у которых правые части одинаковы,
а левые - разные.
Алгоритм основан на каноническом свертывании, т.е. на выде-
лении самой левой свертываемой части строки. Блок-схема алгорит-
ма показана на рис. 1 (@ - символ начального (конечного) ограни-
чителя входного анализируемого текста; не входит в алфавит языка).
┌────────────────────────────────┐
│ ^
┌─────┴───┬─┐ │
┌───────┬─┐ │ i:=i+1 │2│ │
│ i:=1 │1│ │ └─┤ │
│ └─┤ │ j:=i │ │
│ k:=2 │ │ │ │
│ │ │ R :=L │ │
│ R :=@ │ │ i k │ │
│ i │ │ │ │
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
