Смекни!
smekni.com

Проектирование трансляторов (стр. 2 из 31)

только текстовая подготовка.

Синтаксический анализ

Анализаторы выполняют работы по расчленению исходной прог-

раммы на составные части, формированию ее внутреннего представле-

ния и занесению информации в таблицу символов и другие таблицы.

При этом также выполняется полный синтаксический и семантический

контроль программы.

Обычный анализатор представляет собой синтаксически управ-

ляющую программу. В действительности стремяться отделить синтак-

сис от семантики настолько, насколько это возможно. Когда синтак-

сический анализатор узнает конструкцию исходного языка, он вызы-

вает соответствующую семантическую программу, которая контроли-

рует данную конструкцию с точки зрения семантики и затем запоми-

нает информацию о ней в таблице символов или во внутреннем пред-

ставлении программы.

Семантический анализ

Семантическая программа осуществляет семантическую обработ-

ку, когда связанное с ней правило вызывает семантическую редукцию.

Мы предполагаем, что всякий раз, когда в сентенциальной фор-

ме основа x найдена и ее можно привести к нетерминалу U, синтак-

сический распознаватель вызывает программу, связанную с правилом

U ::= x. Генерируемая польская цепочка хранится в одномерном мас-

сиве Р. Целая переменная р содержит индекс, указывающий на пер-

вый свободный элемент массива. Каждый элемент массива может со-

держать один символ (идентификатор или оператор). Предположим

также, что вызванная семантическая программа имеет доступ к сим-

волам основы S(1) ... S(i), находящимся в синтаксическом стеке S,

который используется распознавателем.

Рассмотрим программу, связанную с правилом E1 ::= E2 + T.

Если она вызвана, то мы можем считать, что польская запись для Е2

и Т уже получена. При этом массив Р содержит

... <код для Е2> <код для Т>

поскольку Е2 раположено левее Т. Справа от в исходной прог-

рамме находятся только терминалы, т.к. разбор производится слева

направо. Следовательно, все, что требуется от программы, - это

занести знак "+" в польскую цепочку. При этом инфиксная запись Е2

+ Т переводится в суффиксную запись Е2 Т +. Следоватедьно, семан-

тическая программа имеет вид Р(р) := '+'; p := p+1.

Рассмотрим семантическую программу для F ::= I, где I обоз-

начает произвольный идентификатор. В соответствии с правилами

польской записи идентификаторы предшествуют своим операторам; бо-

лее того они встречаются в том же порядке, что и в инфиксной за-

писи. Все, что необходимо сделать, - это занести идентификатор в

массив Р. Поэтому программа имеет следующий вид;

Р(р) = S(i); p := p+1 где S(i) - верхний символ стека.

Т.к. для каждой продукции мы пишем одну семантическую прог-

рамму, то это помогает поделить обработку на мелкие независимые

части, каждую из которых можно запрограммировать отдельно, что

позволяет не думать обо всем сразу.

Небольшие изменения в синтаксисе или семантике требуют лишь

незначительных изменений в соответствующих правилах грамматики

или семантических программах. Различные части анализа отделены

друг от друга, поэтому внесение изменений не представляет особых

затруднений.

СПИСОК ЛИТЕРАТУРЫ

1. Грис Д. Конструирование компиляторов для цифровых вычис-

лительных машин. М., Мир, 1975 г.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, пере-

вода и компиляции. М. Мир 1978 г.

3. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы

проектирования компиляторов. М., Мир, 1979 г.

4. Вирт, Вебер. Теория перевода, компиляции и редактирова-

ния. М., Мир, 1980 г.

5. Виленкин С.Я., Трахтенгерц Э.А. Математическое обеспече-

ние управляющих вычислительных машин. М., Энергия, 1972 г.

6. Фельдман Дж., Грис Д. Системы построения трансляторов.

Сб. Алгоритмы и алгоритмические языки, вып.5, ВЦ АН СССР, 1971 г.

ЛЕКЦИЯ 2

ОПРЕДЕЛЕНИЯ

Автомат с конечным числом состояний - это пятерка вида

(K,Vt,M,S,Z), где:

K - алфавит элементов, называемых состояниями;

Vt - входной алфавит (литеры, которые могут встретится в

цепочке или предложении);

M - отображение (или функция) множества К*Vt вo множество K

(если M(Q,T) = R, то это значит, что из состояния Q при входной

литере T происходит переключение в состояние R);

S C К - начальное состояние;

Z - непустое множество заключительных состояний, каждое из

которых принадлежит К.

Автомат - устpойство, пpедназначенное для выполнения целе-

напpавленных действий без непосpедственного участия человека.

Абстpактный автомат - математическая модель автомата, задан-

ная множествами (входных символов, состояний и выходных символов)

и двух двуместных функций (пеpеходов и выходов). Функция пеpехо-

дов отобpажает пеpвые два множества во втоpое, а функция выходов,

соответственно - в третье.

Конечный автомат - абстpактный автомат, все тpи опpеделяю-

щие множества котоpого конечны.

V+ - транзитивное замыкание множества V.

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) = { x | S=>x, x С Vt+ } Таким образом,

язык - это выводимое из S подмножество множества всех терми-

нальных цепочек, т.е. цепочек в Vt.

Сентенциальная форма. S => x - цепочка символов языка х, по-

рождаемых из аксиомы S.

Предложение: { x | 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*

Грамматика, которая позволяет разбирать арифметические выра-