46023 (665330), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

Р(р) = 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*

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

жения:

::= │

+│

-

::= │

*│

/

::= ()│ 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 и

Характеристики

Список файлов реферата