Реферат: Проектирование трансляторов
1) она может использоваться для языков программирования, в
которых определяющая реализация идентификатора появляется (тек-
стуально) раньше любой прикладной реализации, что имеет место для
большинства языков;
2) при написании транслятора необходимо пректировать проме-
жуточный язык, на котором должен представляться исходный текст
между программными проходами.
Лексический анализ (сканер)
Сканер - самая простая часть компилятора, иногда также назы-
ваемая лексическим анализатором. Сканер просматривает литеры ис-
ходной программы слева направо и строит символы программы - це-
лые числа, идентификаторы, служебные слова, двухлитерные символы,
такие как ** и // и т.д. Символы передаются затем на обработку
фактическому анализатору. На этой стадии может быть исключен ком-
ментарий. Сканер также может заносить идентификаторы в таблицу
символов и выполнять другую простую работу, которая фактически
требует анализа исходной программы. Он может выполнить большую
часть работы по макрогенерации в тех случаях, когда требуется
только текстовая подготовка.
Синтаксический анализ
Анализаторы выполняют работы по расчленению исходной прог-
раммы на составные части, формированию ее внутреннего представле-
ния и занесению информации в таблицу символов и другие таблицы.
При этом также выполняется полный синтаксический и семантический
контроль программы.
Обычный анализатор представляет собой синтаксически управ-
ляющую программу. В действительности стремяться отделить синтак-
сис от семантики настолько, насколько это возможно. Когда синтак-
сический анализатор узнает конструкцию исходного языка, он вызы-
вает соответствующую семантическую программу, которая контроли-
рует данную конструкцию с точки зрения семантики и затем запоми-
нает информацию о ней в таблице символов или во внутреннем пред-
ставлении программы.
Семантический анализ
Семантическая программа осуществляет семантическую обработ-
ку, когда связанное с ней правило вызывает семантическую редукцию.
Мы предполагаем, что всякий раз, когда в сентенциальной фор-
ме основа 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) = S=>x, x С Vt+ Таким образом,
язык - это выводимое из S подмножество множества всех терми-
нальных цепочек, т.е. цепочек в Vt.
Сентенциальная форма. S => x - цепочка символов языка х, по-
рождаемых из аксиомы S.
Предложение: S=>x, x C Vt* - выводимая из аксиомы S
цепочка терминальных символов, принадлежащая рефлексивно-транзи-
тивному замыканию множества терминальных символов Vt*.
Транслятор - это программа, которая преобразовывает сообще-
ние, написанное на языке L1, в сообщение, написанное на языке L2,
с сохранением смысла.
Формальный язык характеризуется алфавитом, лексикой, семан-
тикой и синтаксисом.
┌──────────── ПРЕДЛОЖЕНИЕ ───────────┐
Страницы: 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
