только текстовая подготовка.
Синтаксический анализ
Анализаторы выполняют работы по расчленению исходной прог-
раммы на составные части, формированию ее внутреннего представле-
ния и занесению информации в таблицу символов и другие таблицы.
При этом также выполняется полный синтаксический и семантический
контроль программы.
Обычный анализатор представляет собой синтаксически управ-
ляющую программу. В действительности стремяться отделить синтак-
сис от семантики настолько, насколько это возможно. Когда синтак-
сический анализатор узнает конструкцию исходного языка, он вызы-
вает соответствующую семантическую программу, которая контроли-
рует данную конструкцию с точки зрения семантики и затем запоми-
нает информацию о ней в таблице символов или во внутреннем пред-
ставлении программы.
Семантический анализ
Семантическая программа осуществляет семантическую обработ-
ку, когда связанное с ней правило вызывает семантическую редукцию.
Мы предполагаем, что всякий раз, когда в сентенциальной фор-
ме основа 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*
Грамматика, которая позволяет разбирать арифметические выра-