Проектирование трансляторов

ЛЕКЦИЯ 1

СУЩНОСТЬ ПРЕДМЕТА. СОДЕРЖАНИЕ КП. СРОКИ.

ОРГАНИЗАЦИЯ РАБОТ. МАТЕМАТИЧЕСКИЙ АППАРАТ.

СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА. ПРОХОДЫ ТРАНСЛЯТОРА.

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

Дорогие коллеги. В течении двух семестров мы будем зани-

маться интереснейшим разделом системного и теоретического прог-

раммирования - теорией проектирования трансляторов.

Представляюсь. Семикопенко Геннадий Петрович, к.т.н.

2 преподаватель - Дмитриенко Наталья Олеговна.

1 семестр: Будет прочитан курс основ проектирования трансля-

тора. Вы ознакомитесь с инструментальными средствами, которые ре-

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

порядке Вами будет разработано, согласовано и утверждено ТЗ на КП.

Завершается семестр зачетом. Его можно получить при выполне-

нии следующих условий:

- утвержденного ТЗ на КП;

- пояснительной записки к КП и ее защиты, либо традиционной

сдачи зачета по всему курсу.

Я рекомендую путь разработки ПЗ и ее защиты как наиболее для

нас выгодный. Текст ПЗ явится составной частью КП, а защищать то,

что Вы сами написали, намного легче. Сдача зачета все равно не

освобождает Вас от необходимости последующего составления ПЗ и ее

защиты во 2 семестре. Таким образом, разработка пояснительной

части КП в 1 семестре экономит время и студентам, и преподавате-

лям.

Цели проектирования:

- ознакомление с одним из существующих инструментов созда-

ния трансляторов - генераторов лексического и синтаксического

анализаторов;

- ознакомление с математическим аппаратом - формальными

грамматиками (G), используемыми для описания искуственных языков

(ИЯ);

- проектирование ИЯ (программирования, информационного, опи-

сательного и любых других);

- формальное описание ИЯ с использованием инструментальных

средств;

- отладка лексического (ЛА) и синтаксического (СА) анализа-

торов, входящих в состав проектируемого транслятора;

- разработка семантических программ транслятора;

- комплексная отладка транслятора на контрольных (тестовых)

примерах;

- и, наконец, завершающая подцель - защита КП. Содержание КП:

- введение, в котором Вы излагаете сведения о целях разра-

ботки КП, его связи с РИСКом, назначении проектируемого ИЯ;

- краткое описание используемого математического аппарата;

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

ких и синтаксических анализаторов;

- неформальное описание разработанного ИЯ (назначение, об-

ласть применения, эффективность по сравнению с традиционными ЯП

для реализации конкретных процессов РИСК, примеры программ).

Если у конкретного студента не хватит воображения для разра-

ботки собственного ИЯ, он может использовать логически завершен-

ное подмножество существующего ИЯ (Фортран, Паскаль, ПЛ, языки

работы с БД и другие);

- формальное описание лексики и синтаксиса ИЯ;

- тексты тестовых программ на ИЯ;

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

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

промежуточного языка в КП используется язык Си;

- дерево вывода фрагмента тестовой программы;

- семантические программы (блоки, процедуры, функции), ис-

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

нания результатов трансляции;

- протоколы результатов выполнения процессов трансляции;

- выводы;

- список литературы. В 1 семестре Вы можете мне не предъяв-

лять только протоколы. Все остальное должно обязательно присут-

ствовать в ПЗ КП.

ОРГАНИЗАЦИЯ ОТЛАДКИ. Все, кто проходит практику в подразде-

лениях предприятия, оснащенных ПЭВМ с операционной системой

МS-DOS, может их использовать для выполнения КП. Для этого пер-

вые 3 человека, согласовавшие со мной ТЗ на КП, должны предоста-

вить дискеты (по 1 шт.), на которые я скопирую инструментальное

ПО - генераторы программ лексического и синтаксического анализа-

торов - LEX и YACC соответственно. Есть и некоторая документация

к ПО.

Проектирование КП может вестись и на СМ-1420, находящихся в

распоряжении кафедры.

ПЗ КП лучше всего набрать на ПЭВМ и распечатать. В этом слу-

чае можно Вам подумать и о распределении отдельных составляющих

КП в зависимости от интересов конкретных студентов.

Те из Вас, кто готов сдать мне КП сейчас, завтра либо через

месяц - будет поощрен повышенной оценкой. При этом такие студен-

ты освобождаются от последующего посещения лекций и практических

занятий.

2 семестр: Отладка разработанного ПО и оформление протоко-

лов работы ЭВМ.

МАТЕМАТИЧЕСКИЙ АППАРАТ - теория формальных языков и грамма-

тик. Подробнее мы ознакомимся с ним на последующих лекциях.

ПРОЦЕСС ТРАНСЛЯЦИИ - выполняемое с сохранением смысла

преобразование входного сообщения с одного языка в выходное сооб-

щение на другом языке.

ТРАНСЛЯТОР - программа, выполняющая процесс трансляции. В

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

ходном языке, говорят о режиме интерпретации входной программы.

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

сляцию входного текста в последовательность команд ЭВМ, называет-

ся интерпретатором.

СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА:

- ЛА (сканер), используемый для разбора лексики исходного

языка (ИЯ). Сканер последовательно просматривает литеры исходной

(транслируемой) программы. Из литер по определенным правилам, за-

данным автоматной грамматикой, сканер строит символы программы

(иначе - лексемы). Состав лексем определяется разработчиком ИЯ и

транслятора с него. Как правило, это числа, идентификаторы, слу-

жебные слова, литералы (цепочки литер, имеющие в программе самос-

тоятельное значение);

- СА, используемый для определения синтаксиса транслируемо-

го текста и управления процессом трансляции. Результат СА - дере-

во вывода;

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

транслируемого сообщения (либо его фрагмента). Результат семанти-

ческого анализа - хранение информации о транслируемом сообщении в

специальных структурах (таблицах символов, идентификаторах, кон-

стант, и других);

- синтезатор (генератор) текста на промежуточном языке

(польская запись, триады, тетрады, графы, и другие). В Вашем КП в

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

программирования Си;

- генератор программы в объектном коде;

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

зочного модуля.

Принципы построения транслятора

Общие сведения

Компилятор должен выполнить анализ исходной программы, а

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

на составные части, затем из них строятся части эквивалентной

обьектной программы. Для этого на этапе анализа компилятор строит

несколько таблиц, которые затем используются как при анализе,так

и при синтезе. Этот процесс представлен на рис.

Процесс преобразования языков программирования включает сле-

дующие этапы:

1) распознавание в исходном тексте программы различных сос-

тавляющих языка;

2) этап синтаксического анализа, на котором распознаются

структуры исходной программы и проверяется их правильность;

3) установление связи между используемыми идентификаторами и

их описанием.

Генерирование обьектного кода

Способ взаимодействия и метод обьединения этих этапов в еди-

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

Все 4-е последовательных процесса: сканирование, анализ,

подготовку к генерации и генерацию команд - можно выполнять пос-

ледовательно или параллельно определенной взаимной синхрониза-

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

ляется обьем доступной памяти. Часто выгодно или даже необходимо

иметь несколько проходов.

В однопроходных трансляторах целая последоватеьлность прос-

тых преобразований (этапов) применяется по очереди к каждой не-

большой части исходной программы таким образом, что рабочая прог-

рамма обращается в процессе единственного просмотра исходной

программы. В многопроходном трансляторе последовательности преоб-

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

Имеется много факторов, определяющих выбор числа проходов

при проектировании трансляторов (время компиляции, время разра-

ботки, относительная независимость фаз трансляции, размеры ОП

ЭВМ).

Некоторые языки (Алгол-68, АДА) принципиально требуют для

своей реализации несколько проходов, в частности можно рассмот-

реть двухпроходную схему трансляции. Ее особенности:

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) = { 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 и

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 │ │ │ │

└────┬────┘ │ k:=k+1 │ │

│ └────┬──────┘ │

│ │ │

│ ___│___ │

│ / │3\ ┌─────────┬──┐ │

│ / └──\ Да │ Конец │10│ │

│ / R равно @ \─────>┤ работы └──┤ │

│ \ i / │ алгорита │ │

│ \ / └────────────┘ │

│ \_______/ │

│ │ │

│ │ │

└───────────────────>─┤ │

┌───────────────────>─┤ Нет │

│ ___│____ │

│ / │4\ │

│ / └──\ Нет │

│ / R > L \__________________________│

│ \ i k /

│ \ ? /

│ \________/

│ Да│

│ ├<────────────────────┐

│ ____│______ │

│ / │5\ │

│ / └──\ ┌─────┴───┬─┐

│ / R = R \______│ │6│

│ \ j-1 j / Да │ j:=j-1 └─┤

│ \ / │ │

│ \___________/ └───────────┘

│ │Нет

│ ┌────────┴─────┬─┐

│ │ │7│

│ │ U < R ... R└─┤

│ │ j i │

│ └────────┬───────┘

│ │

│ │

│ ┌───────┴─────┬─┐

│ │ │8│

│ │ Переход на └─┤

│ │ семантические │

│ │ подпрограммы │

│ │ │

│ └───────┬───────┘

│ │

│ ┌───────┴────┬─┐

│ │ i:=j │9│

└───────────────┤ R :=u └─┤

│ i │

└──────────────┘

Рис. 1. Блок-схема алгоритма свертывания

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

вается первый символ программы, т.е. символ "@" (блок 1).

Затем находится самый правый символ самой левой свертывае-

мой части строки (блок 4). Для этого по матрице предшествования,

которая составляется заранее, проверяют отношения предшествова-

ния между символом, находящимся в верхней ячейке магазина Ri, и

очередным входным символом строки Lk. Если условие Ri > Lk не вы-

полняется, то очередной входной символ записывается в верхушку

магазина (блок 2) и процесс продолжается до тех пор, пока не бу-

дет выполнено условие Ri > Lk, т. е. не будет найден самый пра-

вый символ самой левой свертываемой части строки.

Затем находится самый левый символ этой свертываемой части

строки. Для этого проверяется отношение предшествования между

каждой парой символов Rj-1 = Rj, записанных в магазине (блоки 5 и

6). Нарушение условия Ri = Rj означает, что свертываемая часть

строки кончилась и последовательность символов Rj...Ri есть са-

мая левая свертываемая часть строки.

У каждого нетерминального символа может быть несколько са-

мых левых и самых правых символов.

По таблице, имеющейся в трансляторе, в которой записаны

правила свертывания, производится свертывание (блок 7) и управ-

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

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

ке, соответствующую данному синтаксическому правилу (блок 8).

После того, как генерирование соответствующего куска выход-

ной программы закончено, символы Rj...Ri "выталкиваются" из мага-

зина и в его верхнюю ячейку записывается символ u (блок 9).

Процесс продолжается до тех пор, пока в верхней ячейке мага-

зина не будет обнаружен символ "@" (блок 3), определяющий конец

программы.

Для анализа ошибок в алгоритм включены следующие блоки:

Блок 11 проверяет, могут ли символы Rj и Lk стоять в строке

рядом. Если в матрице предшествования (i,j)-ый элемент пуст (знак

_), то символы Si и Sj стоять рядом не могут и осуществляется пе-

реход к блоку 15. Иначе управление передается в блок 4.

Блок 12 проверяет значение величины j: если j=1, то должно

производиться сравнение с символом "@", что по алгоритму анализа

вообще быть не может. В этом случае переход к блоку 15. Если j не

равно 1, то переход к блоку 5.

Блок 13 проверяет, есть ли правило с правой частью Rj...Ri в

грамматике языка. Если да,переход к блоку 7, иначе - к блоку 15.

Блок 14 проверяет, есть ли правило Rj...Ri. Если да, то ал-

горитм анализа и свертывания входного текста закончен (переход к

блоку 10); иначе в тексте есть ошибка, из-за которой он не может

быть свернут (переход к блоку 15).

Блок 15 выводит сообщение об ошибке и переходит к анализу

следующего оператора.

Таким образом, сложный анализ входного текста, написанного

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

Требование единственности отношений предшествования вызы-

вает необходимость перестройки грамматики языка. Устранение этой

неоднозначности иногда становится достаточно трудоемкой задачей.

Мак-Киман разработал алгоритм анализа входного текста, который не

предъявляет к грамматике языка требования однозначности отноше-

ний предшествования.

Для определения границ сворачиваемой строки он использует не

одну, а две матрицы: первую - для нахождения самого правого сим-

вола строки - назовем М1, и вторую - для нахождения самого лево-

го символа строки - М2. В М1 заносятся следующие отношения пред-

шествования: <= (< или =), > и >=< (последнее означает > и либо

=, либо <). B M2 заносятся отношения предшествования => (> или =),

< и <=> (последнее означает < и либо =, либо >).

При поиске самого правого символа безразлино, какое от ноше-

ние предшествование <, = или <= находиться между двумя анализи-

руемыми символами. Аналогично при поиске самого левого символа

безразлично, какое отношение предшествование >, = или => находит-

ся между двумя анализируемыми символами. Поэтому эти отношения в

соответствующих матрицах не различаются. В тех случаях, когда

между парой символов существуеют отношения >=<, при поиске гра-

ниц сворачиваемой строки необходима дополнительная информация.

Эта информация задается в виде логических функций трех аргументов.

При поиске самого правого символа сворачиваемой строки с

помощью матрицы М1 используется функция

| истина, если Si > Lk;

Р1(Si-1, Si, Lk) = <

| ложь в противном случае.

Функция Р1 истинна, если в контексте Si-1SiLk символ Si яв-

ляется самым правым символом сворачиваемой строки ...Si-1Si.

Здесь Si - символ, хранящийся в верхней ячейке стека, Si-1 -сим-

вол, хранящийся в следующейся ячейке стека и Lk - очередной сим-

вол анализируемого текста.

Таким образом, каждой паре символов, у которых в М1 записа-

но отношение >=<, ставится в соответствие несколько функций Р1,

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

ределение правил границы сворачиваемой строки. Но эта тройка уже

должна быть определена так, чтобы ответ был однозначный.

Аналогично при поиске самого левого символа сворачиваемой

строки с помощью матрицы М2 используется функция

| истина, если Sj-1 < Sj;

Р2(Sj-1, Sj, Sj+1) = <

| ложь в противном случае.

B контексте Sj-1SiSj+1 символ Sj является самым левым симво-

лом сворачиваемой строки SjSj+1... . Здесь Sj-1, Sj, Sj+1 - сим-

волы, хранящийся в j-1, j и j+1 ячейках стека.

Каждой паре символов, у которых в М2 записано отношение <=>,

ставится в соответствие несколько функций Р2, позволяющих, как и

функции Р1, анализировать не пару, а тройку символов. Но эта

тройка уже должна быть определена так, чтобы ответ был однознач-

ный.

Блок-схема алгоритма анализа входного текста с помощью мат-

риц предшествования и функций Р1 и Р2 приведена на рис. 2. Буквы

i и j обозначают номера ячеек магазина, k - номер очередного сим-

вола входного текта, Ri и Rj- символы, находящиеся в i-х и j-х

ячейках магазина, Lk - k-й символ входного текста. В начале ана-

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

программы, т.е. символ "@" (блок 1). Затем производится проверка

на конец программы (блок 3). Если Lk = @, то выполнение програм-

мы окончено и осуществляется переход к блоку 14. Если Lk не сов-

падает @, осуществляется переход к блоку 4.

Производится поиск самого правого символа самой левой свер-

тываемой строки. Для этого по М1 проверяется отношение предшес-

твования между символами Lk и Ri (блок 4). Если это отношение

равно <=, т.е. Ri не является самым правым символом сворачивае-

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

(блок 2).

Если между символами Ri и Lk существует отношение <=>, то

блоком 5 проверяется функция Р1 для двух верхних символов магази-

на и очередного символа входного текста. При значении функции Р1

- ложь (на рис. 2), это значение обозначено Л, т.е. если Ri не

является самым правым символом, осуществляется переход к блоку 2.

Если значение Р1 - истина (И), т.е. Ri - самый правый символ

строки, то осуществляется переход к блоку 6.

Блоком 6 начинается поиск самого левого символа свертывае-

мой строки; j присваивается значение i. По М2 определяется отно-

шение между символами Rj-1 и Rj (блок 7). Если отношение есть =>,

т.е. Rj не является самым левым символом свертываемой строки, то

j := j-1 (блок 8) и определяется отношение между следующей парой

символов. Если отношение есть <, т.е. Rj-1 является самым левым

символом, осуществляется переход к блоку 10. Блок 10 введен для

того, чтобы в блоке 11 свертывание всегда происходило от j-го до

i-го элемента.

Если между символами Rj-1 и Rj отношение >=<, то проверяет-

ся функция Р2 для трех символов, находящихся в j-1, j и j+1-й

ячейках магазина. Если значение Р2 - Л (Rj не является самым ле-

вым символом), осуществляется переход к блоку 8; если значение Р2

- И (Rj является самым левым символом), то осуществляется пере-

ход к блоку 11.

Блоки 11,12 и 13 производят свертывание, переход на генери-

рующую подпрограмму и запись вновь полученного нетерминального

символа U в верхнюю ячейку магазина. Они в точности соответ-

ствуют блокам 7, 8, 9 на рис. 1. На рис. 1. не показаны блоки

анализа синтаксических ошибок. Они аналогичны соответствующим

блокам на рис. 2.

Метод Мак-Кимана освобождает от ограничения однозначности

отношений предшествования, накладываемого методом Вирта, но он

требует, естественно, больших объeмов памяти для записи матриц и

функции. В трансляторе с одной из версий языка PL/1 для машин се-

рии IBM-360 М1 составила 90x45 элементов, М2-90x90. Каждый эле-

мент занимает 2 бита. Число функций Р1 и Р2 приближалось к 450.

ЛЕКЦИЯ 4

ПОСТРОЕНИЕ МАТРИЦ ПРЕДШЕСТВОВАНИЯ

И ПРЕОБРАЗОВАНИЕ ГРАММАТИК

Рассмотрим алгоритм составления матрицы предшествования. Для

этого дадим формальные определения отношений предшествования и

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

1. Для любой упорядоченной пары символов (Si, Sj) Si = Sj

тогда и только тогда, когда существует синтаксическое правило ти-

па U::=xSiSjy для некоторого символа U и некоторых строк x и y.

2. Для любой упорядоченной пары символов (Si,Sj) Si < Sj

тогда и только тогда, когда существует синтаксическое правило ти-

па U::= xSiUly для некоторых U, Ul, x, y и порождение Ul -> Sjz

для некоторой строки z.

3. Для любой упорядоченной пары символов (Si, Sj) Si > Sj

тогда и только тогда, когда:

a) существует синтаксическое правило типа U ::= xUkSjy для

некоторых U, Uk, x, y и порождение Uk -> zSi для некоторой стро-

ки z или

б) существует синтаксическое правило типа U ::= xUkUly для

некоторых U, Uk, Ul, x, y и порождения Uk -> zSi, Ul -> Sjw для

некоторых строк z и w.

Строки x,y,z,w могут быть пустыми.

4. В множество L(U) самых левых символов нетерминального

символа U входят все символы S такие, что существует порождение:

U -> Sz,

где z - некоторая строка (возможно, пустая).

Это определения может быть записано в виде:

Л(U) = { S | существует строка z, такая, что (U -> Sz) }.

5. В множество R(U) самых правых символов нетерминального

символа U входят все символы S такие, что существует порождение:

U -> zS,

где z - некоторая строка (возможно, пустая).

Это определения может быть записано в виде:

R(U) = { S | существует строка z, такая, что (U -> zS) }.

Данные выше формальные определения отношений предшествова-

ния и множеств самых левых и самых правых символов хорошо отра-

жают содержательную сторону определяемых понятий, но для их на-

хождения с помощью ЭВМ целесообразно использовать следующие ре-

курсивные определения (символ ] означает существование, символ /\

- "И", символ \/ - "ИЛИ", символ ф - правило):

1а. Si = Sj ::= ] ф (ф: U ::= xSiSjy).

2а. Si < Sj ::= ] ф ((ф: U ::= xSiUly) /\ Sj С L(Ul)).

3а. Si > Sj ::= ] ф ((ф: U ::= xUkSjy) /\ Si С R(Uk)) \/

(] ф ((ф: U ::= xUkUly) /\ Si С R(Uk)) /\

Sj С L(Ul)).

4a. L(U)= S | ]z (U ::= Sz) \/ ]z, U1 (U ::= U1z /\ S С L(U1)).

5a. R(U)= S | ]z (U ::= zS) \/ ]z, U1 (U ::= zU1 /\ S С R(U1)).

Всюду ф C P.

Определения 1а-5а дают эффективный алгоритм нахождения мно-

жеств L(U) и R(U) и отношений предшествования.

Рассмотрим алгоритм нахождение множества самых левых симво-

лов для символов, принадлежащих Vn.

Шаг 1: проверяем, является ли i-ый символ самым левым в

l-том синтаксическом правиле. Если да, то записываем Si в табли-

цу самых левых символов нетерминального символа Ul (при условии,

что он туда еще не записан);

Шаг 2: проверяем, не является ли символ Ul, для которого Si

- самый левый, самым левым символом Uk. Если да, то записываем

символы Ul и Si в таблицу самых левых символов нетерминального

символа Uk (при условии, что они туда еще не записаны).

Осуществляем просмотр всех синтаксических правил, изменяя

индекс l и k (два индекса для того, чтобы различать нетерми-

нальные символы в левой (k) и правой (l) частях правила); индекс

i указывает номер символа в синтаксическом правиле. Блок-схема

алгоритма показана на рис. 2.

┌─────┐

│ 1 │

└──┬──┘

│

┌──┴──┐

│ 2 ├──────────┐

└──┬──┘ │

│ │

нет / \ │

┌─────< 3 > │

│ \ / │

│ │да │

│ ┌──┴──┐ │

│ │ 4 │ │

│ └──┬──┘ │

└───────┤ │<

┌──┴──┐ / \ > ┌─────┐

│ 5 │ <13 >────┤ВЫХОД│

└──┬──┘ \ / └─────┘

┌────────────┤ │

│ / \ нет ┌──┴──┐

│ < 6 >────┐ │ 12 │

│ \ / │ └──┬──┘

│ да│ │ │да

┌──┴──┐ ┌──┴──┐ │нет / \

│ 9 │ │ 7 │ ├────<11 >

└──┬──┘ └──┬──┘ │ \ /

│ ├──────┘ │

│ < / \ > ┌──┴──┐

└──────────< 8 >────────┤ 10 │

\ / └─────┘

Рис. 2. Блок-схема алгоритма нахождения самых левых символов

Обозначения к алгоритму:

1. l = 1.

2. i = 1 - номер символа в синтаксическом правиле.

3. ] P: Ul ::= Si z - является ли i-ый символ самым левым

в синтаксическом правиле l.

4. Si записать в L(Ul): (L(Ul) = L (Ul) U Si).

5. k = 1.

6. ] P: Uk ::= Ul z - является ли Ul самым левым символом Uk

при условии, что Si C L(Ul).

7. L (Uk) = L (Uk) U Ul U Si - дополнить символами Ul и Si

мн-во L(Ul)

8. k < l (k, l - номера синтаксических правил),

проверка окончания цепочки.

9. k = k + 1.

10. i = i + 1.

11. Si = ; - завершилось ли синтаксическое правило.

12. l = l + 1.

13. l <= (L - общее число грамматических правил в грамматике).

Допущения к алгоритму:

- синтаксические правила отделены друг от друга ";"

- левая часть не отделяется от правой, и левая часть (т.е.

контекстно-свободная грамматика) всегда состоит из одного символа.

Аналогично можно построить множество самых правых символов.

Теперь перейдем к нахождению матрицы предшествования.

Блок-схема алгоритма построения матрицы предшествования, ис-

пользующая определения 1а-3а, представлена на рис. 3. Используют-

ся следующие условные обозначения:

i, j - индексы определяют номер символа в списке символов

языка.

M[i,j] - элемент матрицы предшествования;

l, k - номера синтаксических правил языка.

┌─────┐

│ 1 │

└──┬──┘

│

┌──┴──┐

│ 2 ├─────────────────────────┐

└──┬──┘ │

│ │

┌─────┐ / \ │

│ 4 │────< 3 >─────────────────┐ │

└─────┘ \ / │ │

│ │ │

┌──┴──┐ │ │

│ 5 │ │ │

└──┬──┘ │ │

├────────┐ │ │

/ \ да / \ │ │ │

┌──────────< 7 >────< 6 > │ │ │

│ \ / \ / │ │ │

│ │нет │нет │ │ │

│┌─────┐ │ / \ ┌──┴──┐ │ │

└┤ 8 ├─────┴──────< 9 >───┤ 10 │ │ │

└─────┘ \ / < └─────┘ │ │

│> │ │

┌──┴──┐ │ │

│ 11 │ │ │

└──┬──┘ │ │

├────────┐ │ │

┌─────┐ да / \ да / \ │ │ │

│ 14 ├───<13 >────<12 > │ │ │

└──┬──┘ \ / \ / │ │ │

└────────┴────────┤ │ │ │

/ \ ┌──┴──┐ │ │

<15 >───┤ 16 │ │ │

\ / < └─────┘ │ │

│ │ ┌──┴──┐

┌──┴──┐ │ │ 29 │

│ 17 │ │ └──┬──┘

└──┬──┘ ┌──┴──┐ │

├─────────────┐ │ 30 │ / \ > ┌─────┐

┌──┴──┐ │ └──┬──┘ <28 >───┤ВЫХОД│

│ 18 │ │ │ \ / └─────┘

└──┬──┘ │ │ ┌───┘

│ │ │ │>

нет / \ ┌──┴──┐ │ / \

┌──────────────────< 19 > │ 26 │ └──<27 >

│ \ / └──┬──┘ < \ /

│ │ │< │

│┌─────┐да / \ да / \ / \ │

││ 22 ├───<21 >────<20 > <25 >────────┘

│└──┬──┘ \ / \ / \ / >

│ │ │нет │ │

│ │ │ / \ < ┌─────┐ │

└───┴────────┴──────<23 >───┤ 24 │ │

\ / └─────┘ │

│> │

└─────────────┘

Рис. 3. Блок-схема алгоритма построения матрицы предшествования

для контекстно-свободных грамматик

Обозначения к алгоритму 1:

1. i = 1 (номер символа в алфавите языка).

2. j = 1.

3. ] P: U ::= x Si Sj - проверка наличия отношения = и

нахождение элемента матрицы с этим

отношением.

4. М [i,j]= =.

5. k = 1 (k,l - номера синтаксических правил).

6. Si C L (Uk) - находят элементы матрицы.

7. ] P: U ::= x Si Ux y имеющие отношение <.

8. М [i,j] = <.

9. k < j.

10. k = k + 1.

11. k = 1.

12. Si C L(Uk) находят элементы матрицы.

13. ] P: U ::= x Uk Sj y соответствующие отношению >

14. М [i,j] = >.

15. k < j.

16. k = k + 1.

17. k = 1.

18. l = 1.

19. Si C L(Uk) находят

20. Si C L(Ul) элементы матрицы,

21. ] P: U ::= x Uk Ul y соответствующие отношению >

22. М [i,j] = >.

23. l > j.

24. l = l + 1.

25. k < j.

26. k = k + 1.

27. j < I (I - мощность словаря языка).

28. i < I.

29. i = i + 1.

30. j = j + 1.

Блок 3 проверяет условие 1а и находит элементы матрицы, рав-

ные =, блок 4 записывает значение элемента в матрицу.

Блоки 6 и 7 проверяют условие 2а и находят элементы матрицы,

равные <.

Блок 8 записывает значение элемента в матрицу.

Блоки 12, 13, 19, 20 и 21 проверяют условия 3а и находят

элементы, равные >, блоки 14 и 22 записывают значения этих эле-

ментов в матрицу.

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

Данный алгоритм не ограничивается нахождением только одного

отношения предшествования между любыми двумя символами Si и Sj, а

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

ду ними существуют. Такая матрица не может использоваться в алго-

ритме анализа программы, так как не ясно, какое из отношений

предшествования между двумя символами брать для нахождения грани-

цы в каждом отдельном случае.

Но введением дополнительных нетерминальных символов и изме-

нением синтаксических правил, которые не меняют правил написания

программ на языке программирования, т. е. эквивалентным преобра-

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

рой символов существовало не более одного отношения предшествова-

ния.

Единого алгоритма, преобразующего любую КС-грамматику в

грамматику типа 2 по классификации Хомского, отвечающую двум до-

полнительным ограничениям:

- однозначности отношений предшествования;

- отсутствие двух грамматических правил с одинаковыми правы-

ми частями

НЕ СУЩЕСТВУЕТ.

Но, построив матрицу предшествований и выяснив неоднознач-

ность отношений между некоторыми символами, эту неоднозначность

можно устранить введением дополнительных нетерминальных символов

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

Рассмотрим несколько алгоритмов, позволяющих преобразовать

КС-грамматику в грамматику типа 2 с учетом указанных ограничений:

1. Пусть между некоторыми двумя символами Si и Sj сущес-

твуют два отношения предшествования Si = Sj и Si < Sj.

Значит, существуют правила

Un ::= XnSiSjYn (n = 1,2,...,N); (1)

Um ::= ZmSiFkDm (m = 1,2,...,M; k = 1,2,...,K);

Fk -> SjQk; (2)

Введем новые нетерминальные символы Pn и синтаксические

правила Pn ::= SjYn (n = 1,2,...,N), заменяя все правила (1)

правилами Un ::= XnSiPn, при этом если исходная грамматика со-

держит правила вида Qn ::= SjYn, то заменяем их правилами Qn ::=

Pn.

1а. Если применение правила 1 не устраняет неоднозначности,

то вводятся нетерминальные символы Pn и Lm и синтаксические пра-

вила Pn ::= XnSi и Lm ::= ZmSi и все правила (1) заменяются на

Un ::= PnSjYn, а все правила (2) на правила Um ::= LmFkDm.

Если исходная грамматика содержит правила вида Qn ::= XnSi и

Tm ::= ZmSi, то заменяя их на правила Qn::=Pn и Tm::=Lm соответ-

ственно. Правила Pn и Lm надо выбирать так, чтобы Pn не совпада-

ло с Lm, т.е. чтобы ни для каких n и m Xn не совпадало с Zm.

Алгоритмы 1 и 1а устраняют отношения предшествования =. Это

видно из определений 1а-3а.

2. Пусть между некоторыми двумя символами Si и Sj сущес-

твуют два отношения предшествования Si = Sj и Si > Sj.

Значит, существуют правила

Un ::= XnSiSjYn (n = 1,2,...,N); (3)

Um ::= ZmFkSjDm или Um ::= ZmFkRlDm (4)

(m = 1,2,...,M; k = 1,2,...,K; l = 1,2,...,L);

Fk -> QkSi Rl -> SjTl.

Введем новые нетерминальные символы Pn и синтаксические пра-

вила Pn ::= XnSi (n = 1,2,...,N). Заменяем правила (3) правилами

Un ::= PnSjYn, устраняя тем самым отношения предшествования =.

Если исходная грамматика содержит правила вида Qn ::= XnSi, то

заменяем их правилами Qn ::= Pn.

3. Пусть между некоторыми двумя символами Si и Sj сущес-

твуют два отношения предшествования Si < Sj и Si > Sj, т. е. су-

ществуют правила

Un ::= XnSiFkYn (n = 1,2,...,N); (5)

Um ::= ZmRlSjDm или Um ::= ZmRlTpDm (6)

(m = 1,2,...,M; k = 1,2,...,K; l = 1,2,...,L;

p = 1,2,...,P);

Fk -> SjQk Rl -> HlSi, Tp -> SjWp.

Введем новые нетерминальные символы Pn и синтаксические пра-

вила Pn ::= XnSi (n = 1,2,...,N). Заменяем правила (5) правилами

Un ::= PnFkYn, сведя их к правилам (6) и устранив тем самым отно-

шения предшествования типа <. Если исходная грамматика содержит

правила вида Qn ::= XnSi, то заменяем их правилами Qn ::= Pn.

Справедлива теорема, согласно которой алгоритмы 1-3 измене-

ния синтаксиса языка программирования не изменяют правила на-

писания и семантику программ на данном языке.

Для тех случаев, когда КС-грамматику надо преобразовывать в

грамматику типа 2 только с одним дополнительным ограничением -

однозначность отношений предшествования (одинаковые правые части

допускаются), Ленаром и Лимом предложен следующий универсальный

алгоритм.

1. Составляются таблицы L(N) самых левых и R(N) - самых пра-

вых сиволов нетерминального символа N. Символ N C L(N) назовем

леворекурсивным, ссимвол N C R(N) - праворекурсивным.

2. Составляется матрица предшествования и определяются все

нарушения единственности отношений предшествования, и если их

нет, то производится остановка. Если они есть, то осуществляется

переход к 3.

3. К каждому праворекурсивному символу применяется процеду-

ра ограниченного правого расширения, которая заключается в том,

что каждый праворекурсивный символ N заменяется символом N1 и

вводится новое грамматическое правило N1::=N. Символ N не заме-

няется на символ N1, если в данном грамматическом правиле он яв-

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

4. К каждому леворекурсивному символу применяется процедура

ограниченного левого расширения, которая заключается в том, что

каждый леворекурсивный символ N заменяется символом N2 и вводит-

ся новое грамматическое правило N2::=N. Символ N не заменяется

символом N2, если в данном грамматическом правиле он является са-

мым левым символом.

5. Если выполнен п. 3 или 4, то осуществляется переход к

п.1. Если нет, то осуществляется переход к п.6.

6. По матрице предшествования находятся пары символов X,Y и

P,Q такие, что X = Y и P = Q.

а. Если X C R(P) и выполняется одно из следующих условий: Q

и Y являются одними и теми же символами или Q C L(Y) или Y C L(Q)

или существует символ D такой, что D C (L(Q) /\ L(Y)), то к сим-

волу X применяется процедура ограниченного правого расширения.

б. Если Y C L(Q) а P и X являются одними и теми же символа-

ми, то к символу Y применяется процедура ограниченного левого

расширения и осуществляется переход к п.1.

ЛЕКЦИЯ 5

АНАЛИЗ КОНТЕКСТНО-ЗАВИСИМЫХ ЯЗЫКОВ

С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ

Наиболее распространенные грамматики, описывающие языки

программирования, - это КС-грамматики (грамматики типа 2 в клас-

сификации Хомского). Однако описание языков программирования

грамматиками типа 1, т.е. контекстно-зависимыми (КЗ) грамматика-

ми во многих случаях может облегчить как сам процесс описанияопи-

сания языка, так и построение транслятора.

Рассмотрим алгоритм анализа программы, если алгоритмический

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

грамматик совпадает с классом КЗ-грамматик (грамматики типа 1 по

Хомскому).

Грамматика G является неукорачивающей, если для каждого

правила x ::= y С Ф выполняется условие │ x │<=│ y │, где │ x │

i i i i i

и │ y │ - число символов, входящих в строки x и y соответ-

i i i

ственно.

Множества самых левых Л(В) и самых правых П(В) символов сим-

вола В:

L(В) = { U/ ] (Be ::= Ux) С Ф \/ ] (Be ::= B1x) С Ф /\

/\ U С L(В1) };

R(В) = { U/ ] (eB ::= xU) С Ф \/ ] (eB ::= xB1) С Ф /\

/\ U С R(В1) };

где e, x - строки, возможно, пустые; В, В1, U С Vt U Vn.

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

могут обладать непустым множеством самых левых (правых) символов

при условии, что они использовались как начальные (конечные) сим-

волы в строках грамматических правил (x i ::= y i) С Ф.

Из определения L(В) непосредственно следует, что если a ->

b, т. е. a = f1 -> f2 -> ... -> fk = b (k>1) и a = Bx, то на-

чальные символы строк f i = Ux i (1<i<=k), в которых начальный

символ U участвовал в строках y правил вывода, принадлежат мно-

жеству L(В).

Аналогично из определения R(В) непосредственно следует, что

если a -> b, a = xB и, кроме того, a = f1 -> f2 -> ... -> fk =

= b (k>1), то конечные символы строк f i = x i U (1<i<=k), в кото-

рых конечный символ U участвовал в правилах вывода, принадлежат

множеству R(В).

Определим отношения предшествования для неукорачивающих

грамматик:

В = В <--> ] ф (ф: g ::= xB B y) С Ф;

i j i j

B < B <--> ] ф (ф: g ::= xB Ny) С Ф /\ B С Л(N);

i j i j

B > B <--> ] ф (ф: g ::= xNB y) С Ф /\ B С П(N) \/

i j j i

\/ ] ф (ф: g ::= xNN y) С Ф /\ B С П(N) /\ B С Л(N );

1 i i 1

где x и y - строки, возможно, пустые, N, N , С V U V .

1 t n

Описание языка программирования неукорачивающими грамматика-

ми позволяет вводить символы языка типа IF, BEGIN, ELSE, FOR и

идентификаторы стандартных функций типа SIN, COS, EXP и т. п. в

виде нетерминальных символов в грамматические правила, что облег-

чает анализ этих символов и ускоряет процесс трансляции.

Теперь рассмотрим алгоритм анализа входного текста, написан-

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

вования типа 1 по классификации Хомского. Блок-схема алгоритма

показана на рис. 4.

┌─────┐

│ 1 │

└──┬──┘

┌──────────────────────┼───────────────────┐

│ │ │ нет

│ ┌────┐ пусто / \ = ┌─────┐ / \

│ │ 15 ├───┬───────< 2 >────┤ 3 ├────< 4 >

│ └─┬─┬┘ │ \ / < └─────┘ \ /

│ │ │ │ ├─────────┐ │ да

│ │ │ │ │ │ │

│ │ │ │ пусто / \ = ┌──┴──┐ / \ ┌────┐

│ │ │ └───────< 5 >────┤ 6 │ < 13>─1──┤ 14 │

│ │ │ \ / └─────┘ \ / да └────┘

│ │ │ │< нет│

│ │ └──────────────┼───────────────────┘

│ │ / \

│ └──────────────< 7 >

│ нет \ /

│ │ да

│ ┌──┴──┐

│ │ 8 │

│ └──┬──┘

│ ┌──┴──┐

│ │ 9 │

│ └──┬──┘

│ ├────────┐

│ ┌────┐ / \ ┌─┴───┐

└─┤ 11 ├─────────────<10 >────┤ 12 │

└────┘ = \ / =/= └─────┘

Рис.2

1. k,i=1 8. q := │Xn│

Мi=1 9. ГП

2. Ri ? Lk2 10. q=1

3. i=i+1 Ri=Lk3 11. i::=j

k=k+1 12. k=k-1

j=i Lk=n(q)

4. Ri=4 q=q-1

5. Rj=Ri 13. Y=R1...Ri

6. j=j-1 14. выход

7. Сущ. правило Y =Rj...Ri 15. обработка ошибки

При анализе входного текста используется стек R, работающий

по правилу FILO (first in, last out), чтение исходного текста

производится слева направо, а дерево сворачивания строится снизу

вверх.

Алгоритм в каждом текущем предложении Si выделяет самую ле-

вую строку, заключенную между отношениями > и <, и заменяет ее по

соответствующему правилу грамматики. Если грамматика предшество-

вания не имеет двух правил с одинаковыми строками y i, то данный

алгоритм для каждого предложения S L(G) всегда порождает одну и

ту же последовательность правил сворачивания. Для того, чтобы

строки сворачивания всегда были заключены между отношениями > и

<, в грамматиках анализируемых языков, как и в случае КС-грамма-

тик, вводятся ограничители начала и конца текста @.

В начале анализа строки в верхнюю ячейку стека R записыва-

ется первый символ программы, т. е. символ @. Индексам i (номер

символов стека R) и k (номер смвола входного текста) присваива-

ются начальные значения 1.

Блок 2. Проверяется отношение предшествования между верхним

символом стека Ri и очередным символом входного текста Lk . Если

между ними отношение вида _ (пусто), значит во входном тексте до-

пущена ошибка.

Блок 3 записывает в стек R очередной символ входного текста.

Блок 4 выделяет признак окончания текста Ri = @.

Блоки 5 и 6 определяют левую границу сворачиваемой строки.

Для этого проверяется отношение предшествования между каждой па-

рой символов R и R до выполнения условия R < R . В блоке

j-1 j j-1 j

5 не предусмотрен выход при выполнении условия R > R , так как

j-1 j

такое условие не может иметь место; вообще в процессе работы ал-

горитма в стеке R не может появиться пара символов с отношением

>, так как это исключает сам алгоритм.

Блок 7 производит поиск правила y=Rj,...,Ri по таблице грам-

матических правил и запоминает номер правила n, если оно найдено.

Блок 8 записывает в счетчик q число символов строки

Xn (q:=│Xn│).

Блок 9 производит переход на генерирующую подпрограмму.

Блок 10 проверяет длину строки Xn.

Блок 11 "выталкивает" символы Rj,..., Ri из стека R и запи-

сывает в него первый символ строки Xn, обозначенный на блок-схе-

ме Xn(1).

Блок 12 записывает все символы строки Xn, кроме первого, пе-

ред первым непрочитанным символом входного текста. Это не вы-

зовет переполнения массива L, так как по условию │Xn│ <= │Yn│.

Следовательно, число символов строки x не может быть больше чис-

ла символов строки y.

Блок 13 проверяет, выполняется ли правило R1,...,Ri. Если

такое правило выполняется, то алгоритм анализа и свертывания

входного текста закончен. Если такое правило не выполняется, зна-

чит данный текст из-за допущенной ошибки не может быть свернут.

Описания языков программирования КС- и даже неукорачивающи-

ми грамматиками вынуждает переносить определение части формаль-

ных условий из синтаксиса в семантику. Например, в ФОРТРАНе при

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

ли его описание явным или неявным. Если описание явное, то опре-

деляется тип идентификатора.

Пример:

Имеется грамматика:

Vт = { А, B }, Vn = { S, D, H, B`, A` }

1: S -> A`SD

2: S -> A`B`A

3: AD -> HA

4: H -> D

5: B` -> B

6: BD -> BB`A

7: A` -> A

Эта грамматика порождает язык следующего вида:

(А**n)(B**n)(А**n) ; n - степень

L(S) =A`,A,H,D R(S)=A, D

L(B`)=B R(B`)=B

L(A`)=A,H,D R(A`)=A

L(H) =D R(H)=D, A

L(D) =" R(D)=A

L(B) =B R(B)=" (неопределено)

L(A) =H,D R(A)="

Матрица предшествования:

│

S │ = =

B`│ < < =

A`│ = = < < < <

H │ < < =

D │ > > > >

A │ > > > > > > >

B │ = > > > <

@ │ = < < < <

───┼────────────────────────

│ S B` A` H D A B @

Дерево вывода на основе матрицы и правил:

┌──────────────────────────┐

S+──┐ ┌─────────────А+ +D

│ │ │ \ /

│ S+─── +─────+B` H +────+3

│ │ │ │ │

│ │ +5 4+ │

│ │ │ │ │

│ │ +B D+ │

│ │ │ │ │

+А` +А` └──+──┘ │

│ │ ┌──/│\──┐ │

│ │ │ │ │ │

+1 +1 │ +B` │ │

│ │ │ │ │ │

│ │ │ +5 │ │

│ │ │ │ │ │

А А B В А А

Ф : BA ─> BDA B. .A

\./

./│\.

B D A

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ПОРОЖДАЮЩИХ ГРАММАТИК

В ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ

Грамматики называются эквивалентными, если порождающие их

языки совпадают.

Теорема 1. Пусть в порожденной грамматике имеется одно или

несколько вхождений строки y в правые части порождающих правил.

Преобразование грамматики путем введения нового нетерминала Ф,

нового правила вывода Ф::=y и замена всех или части вхождений

строк y на вхождения нового символа порождает новую грамматику,

эквивалентную исходной.

G - грамматика.

Строка АВ, которая входит хотя бы в одну часть грамматичес-

кого правила, называется парой. Если А С R(А), В С L(В), то пара

рекурсивно-неоднозначна.

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

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

матика - рекурсивно-приведенная.

АЛГОРИТМ ПРЕОБРАЗОВАНИЯ РЕКУРСИВНО-НЕОДНОЗНАЧНОЙ ГРАММАТИКИ

В ГРАММАТИКУ ПРЕДШЕСТВОВАНИЯ

1. Находим множество правых символов. Выбираем все рекурсив-

ные символы грамматики (А R(А)). Грамматические правила имеют

вид: Ф::=(psi). Выделяем все вхождения этих символов в строки

psi, при условии, что они являются левыми частями пар. Для каждо-

го выбранного символа, имеющего такое вхождение, введем новый не-

терминальный символ А, новое правило вывода и заменим все выде-

ленные вхождения А на вхождения А`.

2. Для каждого нового правила А`::= А ищем другое правило

вида Ф ::= А, и если R(А) не содержит последнего символа строки,

то заменяем правило Ф ::= А на Ф ::= А`.

3. Находим множество левых символов. Выбираем все леворекур-

сивные символы В L(B), при условии, что В - правый член некото-

рой пары. Выделим все вхождения этих символов в строку (psi), при

условии, что эти вхождения являются правыми членами пар. Для каж-

дого В, имеющего такое вхождение, вводим В`, В`::= В и заменим

все вхождения В на вхождения В`.

4. Для каждого нового правила В` ::= В ищем в G другие пра-

вила вида Ф ::= В, при условии, что правые части этих правил сов-

падают. Если L(B) не содержит первого символа строки Ф, то заме-

няем правило Ф ::= В на Ф ::= В`.

5. Находим множество левых и правых символов для полученной

грамматики, находим матрицу отношений предшествования, если мат-

рица однозначна выход.

6. Перебирая все вхождения пар во всех строках (psi), отли-

чаем вхождения таких пар АiDi, где неоднозначность типа >< или >=

имеется либо между Аi и В L(Di). Для каждого отличного вхождения

пары АiDi в строку (psi)m выделяем подстроку хАi, для нее вводим

нетерминал Nj и новое грамматическое правило вида Nj ::= xАi. В

правых строках грамматических правил выделенные вхождения цепоч-

ки xАi заменяем новым символом Nj. Если в одной строке в правой

части выделено несколько вхождений таких цепочек, то надо после-

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

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

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

самых коротких.

7. Потом повторяется п. 5.

8. Перебирая все вхождения пар в правых частях грамматичес-

ких правил, выбираем (отмечаем) пары АiDi, где имеется неодноз-

начность. Для каждого отмеченного вхождения вычисляем строку Di y.

Для каждой выделенной подстроки, отличной от других, вводит-

ся новый нетерминал вида Nj ::= Di y. Для всех выделенных под-

строк грамматика будет однозначной.

Грамматики предшествования.

L(U)={S/Эz(U=>Sz)}

R(U)={S/Эz(U=>zS)}

Si = Sj ::= Э F (F: U::=xSiSjy)

Si < Sj ::= Э F ((F: U::=xSiUly) & Si{-L(Ul))

Si > Sj ::= Э F ((F: U::=xUkSjy) & Si{-R(Uk)) v

Э F ((F: U::=xUkUly) & Si{-R(Uk) & Sj {- L(Ul))

Алгоритм.

Обозначения:

L - строка анализируемого текста;

L(k) - к-й символ L;

S - стек реализации процесса свертывания;

S(i) - i-й элемент стека S

u(l),w(l),fi(l),psi(l) - соответственно цепочки u,w,fi,psi

правила P(l);

│u(l)│,│w(l)│,│fi(l)│,│psi(l)│ - длины цепочек u,w,fi,psi;

n - индекс самого нижнего символа S(n), такого что

S(n).x.S(n+1);

m - указатель существования в S пропущенной основы;

│p│ - число правил в грамматике.

Блок 1. Инициирует работу алгоритма.

i=k=1; n=max; m=0; Si=1;

Блок 2. Обработка ошибок.

Блоки 3,4. Нахождение правой границы основы свертывания.

3: S(i) ? L(k) =< - 4, >,>< - 6

4: j=i=i+1;

S(i)=L(k);

k=k+1;

Блоки 5,6. Запоминают n.

5: n=i;

6: S(i).><. L(k) & n>i да - 5, нет - 8.

Блоки 8,9. Нахождение левой границы основы свертывания.

8: S(j-1) >< S(j), < - 7, = - 9

9: j=j-1;

Блок 7. Начальное значение номеру грамматического правила Р

l=0

Блок 10. Анализ завершения просмотра всех правил.

l=│p│ да - 12, нет - 11.

Блок 11. Переход на просмотр следующего правила.

l=l+1;

Блок 12 проверяет возможность анализа при отсутствии правил

вида (u fi, u psi) для свертывания выделенной основы.

m=0;

Блок 14 проверяет возможность запоминания выделенной основы

в S.

n=i;

Блок 16 - возврат на первую из пропущенных основ.

L(k-n+j)...L(k+1)=S(n)...S(i)

i=j=n;

m=0;

k=k-n+1;

Блоки 13,15,17 проверяют соответствие строк u(l), w(l), fi

(l) выделенной основе и контекстным строкам, ее окружающим.

ЛЕКЦИЯ 6

LR(k)-ГРАММАТИКИ И СООТВЕТСТВУЮЩИЙ АНАЛИЗАТОР

Анализ для LR(k) - грамматики называется методом Кнута.

LR(k)-анализатор - устройство из неограниченных вправо вход-

ной ленты, верхнего и нижнего магазинов.

На входной ленте помещается еще не обработанная правая под-

цепочка анализируемой цепочки. К анализируемой цепочке справа

приписано k маркеров.

В верхнем магазине - цепочки-символы состояний анализатора.

Состояния подбираются так, чтобы они соответствовали возможным

вариантам дерева вывода на различных тактах анализа.

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

входной цепочки (обработанные анализатором).

На каждом такте работы анализатора может выполняться одно из

действий: сдвиг или свертка. После выполнения определенного коли-

чества тактов анализатор допускает или отвергает анализируемую

цепочку.

Выполнение каждого такта можно разбить на 2 этапа. На 1 -

преобразование информации нижнего (и, возможно, верхнего) магази-

нов. Информация для выполнения 1 этапа - правое состояние цепоч-

ки состояний (верхний магазин) и к левых символов не обработан-

ной части входной цепочки. Если действие - сдвиг, в нижний мага-

зин записывается терминал из левого символа входной цепочки. Вер-

хний магазин остается без изменений. Если действие - свертка, то

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

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

гр.правила). Входная цепочка - без изменений. Информация для

свертки - правые состояние и символ из верхнего и нижнего магази-

нов соответственно (после выполнения 1 этапа). Запись в верхний

магазин "переходного состояния".

Свертка соответствует случаю использования некоторого прави-

ла вывода порождающей грамматики. Символы, исключаемые из нижне-

го магазина, соответствуют правой, а символ, записываемый в мага-

зин - левой части грамматического правила.

ОПРЕДЕЛЕНИЕ: LR(k)-анализатор, соответствующий G=(Vt,Vn,P,S)

- LR(k)=(U,X,H,T,b1,b2,S0,Z0,Sr), где:

U - конечное множество состояний анализатора;

X - конечное множество входных символов, Х=Vt U # -маркер;

H - конечное множество H=(Vt U Vn U Z0),

Х=Vt U # - маркер;

T - {Q U (p,A)}, A C Vn,

p - положительное целое,

Q - сдвиг,

пара (p,A) - cвертка, с исключением p символов из

магазинов и записью в нижний магазин

символа А

k k

b1 - (UxX ) -> T, X - цепочки длины k над алфавитом X;

b1 - частично определенная функция, задающая первые этапы

тактов анализа b2 - (UxH) -> U;

b2 - частично определенная функция, задающая вторые этапы

тактов анализа;

S0 - S0 C U - начальное состояние;

Z0 - граничный маркер;

Sr - Sr C U, заключительное состояние.

Для любой LR(k) - грамматики можно построить LR(1) - грамма-

тику, допускающую тот же язык.

ОПРЕДЕЛЕНИЕ: Автомат с магазинной памятью (сокращенно МП-ав-

томат) - это семерка

P = (Q, X, Г, b, q0, Z0, F),

где:

Q - конечное множество символов состояний, представляющих

всевозможные состояния управляющего устройства;

Х - конечный входной алфавит;

Г - конечный алфавит магазинных символов;

b - отображение множества Q * (X U {e}) * Г в множество ко-

нечных модмножеств множества Q * Г";

q0 C Q - начальное состояние управляющего устройства;

Z0 С Г - символ, находящийся в магазине в начальный момент

(начальный символ);

F C Q - множество заключительных состояний.

ОПРЕДЕЛЕНИЕ: МП-автомат P=(Q,X,Г,b,q0,Z0,F) называется де-

терминированным (сокращенно ДМП-автоматом), если для каждых q C Q

и Z C Г либо

1) b (q,a,Z) содержит не более одного элемента для каждого

а С Х и b (q,e,Z) = 0, либо

2) b (q,a,Z) = 0 для всех а С Х и b (q,e,Z) cодержит не бо-

лее одного элемента.

Утверждение. Любой LR(k) - анализатор может быть преобразо-

ван в детерминированный МП-автомат.

При доказательстве этого утверждения используют свойство

анализатора записывать по одному символу в верхний и нижний мага-

зины. Исключаться из магазина эти символы могут только одновре-

менно и только на этапе свертки, следовательно верхний магазин

может быть исключен, если каждый символ нижнего магазина снаб-

дить индексом. Индекс соответствует тому состоянию, которое запи-

сывается в нижний магазин. Каждый символ нижнего магазина должен

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

ветствующих этому символу.

Для любого языка, распознаваемого LR(k)-анализатором, сущес-

твует распознающий этот язык LR(1)-анализатор (класс языков,

распознаваемых LR(k)-анализатором, совпадает с классом языков

LR(1)-анализатора. Входит в класс несущественно неоднозначных

УКС-языков.

Функции b1 и b2 обычно задаются в виде общей таблицы, сос-

тоящей из конечного числа "рядов". Каждый ряд соответствуют неко-

торому состоянию и имеет следующую структуру:

- состояние;

- наблюдаемая цепочка;

- функция действия (b1);

- символ нижнего м-на;

- функция b2 (переходное состояние). Для заключительного

состояния Sr имеется сл. строка:

- состояние Sr;

- наблюдаемая цепочка - ##### - k раз - маркеры Z0;

- функция действия (b1) - допуск;

- символ нижнего м-на;

- функция b2 (переходное состояние). Таблица наз. анализи-

рующей таблицей LR(k)-анализатора.

┌──────────┬───────────────────┬─────┬───────────────┬──────┐

│ │ k │ │ │ │

│ U │ X │ b1 │ H │ b2 │

│ Состояние│ Наблюдаемая строка│ │ Символ нижнего│ │

│ │ │ │ магазина │ │

├──────────┼───────────────────┼─────┼───────────────┼──────┤

│ │ Xi1 │(p,A)│ Zi1 │ Si1 │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ Xi2 │ Q │ Zi2 │ Si2 │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ ... │(p,B)│ ... │ ... │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ Xij │ Q │ Zij │ Sij │

│ ├───────────────────┼─────┼───────────────┼──────┤

│ │ ... │ ... │ ... │ ... │

└──────────┴───────────────────┴─────┴───────────────┴──────┘

LR(k)-грамматики образут широкий класс грамматик, анализи-

руемых естественным образом снизу вверх с помощью ДМП-автомата.

Пусть ах - правовыводимая цепочка какой-то грамматики при-

чем а - либо пустая цепочка либо оканчивается нетерминалом. Тог-

да а называется открытой частью цепочки ах , х - замкнутой. Гра-

ницу между а и х назовем рубежом.

Алгоритм разбора типа "перенос-свертка" можно рассматривать

как программу расширенного ДМП-преобразователя который проводит

разбор "снизу-вверх". Для данной входной цепочки W ДМП-преобразо-

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

S=a(0)=>a(1)=>...=>a(m)=W

Это правый вывод цепочки W. Каждая правовыводимая цепочка

а(i) распределяется в памяти ДМП так, что ее открытая часть хра-

нится в магазине а замкнутая - на входной ленте справа от голов-

ки. Затем ДМП должен локализовать правый конец основы и сделать

свертку. Число принимаемых ДМП решений - два: решения о переносе

и о свертке (по конкретному правилу).

Грамматика будет LR(K) грамматикой, если для произвольного

правого вывода

S=a(0)=>a(1)=>...=>a(m)=Z

в каждой правовыводимой цепочки а(i), читая ее слева напра-

во, можно выделить основу и определить, каким нетерминалом надо

ее заменить, дойдя при этом не более чем до k-го символа, распо-

ложенного справа от правого конца этой основы.

ОПРЕДЕЛЕНИЕ:

Пусть G=(N,E,P,S) - КС грамматика.

Пополненной грамматикой, полученной из G, будем называть

G'=(N+S',E,P+{S'->S},S').

S' - новый начальный символ, не принадлежащий N.

S' -> S - это нулевое правило грамматики G', добавляемое для

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

можно было интерпретировать как сигнал о том, что цепочка допус-

кается.

ОПРЕДЕЛЕНИЕ: пусть G - КС грамматика, а G' - полученная из

нее пополненная. Будем называть G LR(k) грамматикой для k >= 0,

если из условий:

1) S' -> aAw -> abw;

2) S' -> gBx -> aby;

3) FIRST(k;w) = FIRST(k;y) где k соответствует грамматике.

Из условий следует, что

aAy = gBx (т.е. a=g, A=B, x=y)

Интуитивно это определение говорит о том, что если abw и aby

-правовыводимые цепочки пополненной грамматики, у которых

FIRST(w)=FIRST(y), и A->b -последнее правило, использованное в

правом выводе цепочки abw, то правило A->b должно использоваться

также в правом разборе при свертке aby к aAy.

Так как A дает b независимо от w, то LR(k) условие говорит о

том , что в FIRST(w) содержится информация, достаточная для того,

что ab за один шаг выводится из aA. Поэтому никогда не может воз-

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

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

Кроме того, работая с LR(k)-грамматикой, мы всегда знаем,

допустить ли данную входную цепочку или продолжать разбор.

Если начальный символ S не встречается в правых частях пра-

вил, то в определении LR(k) грамматики вместо S' можно взять S, а

именно G будет LR-грамматикой, если из трех условий:

1: S=>aAw=>abw;

2: S=>yBx=>aby;

3: FIRST(w)=FIRST(y)

следует, что aAy=yBX.

В данном разделе мы кратко рассмотрим, как для каждой

LR-грамматики G можно построить детерминированный правый анализа-

тор, который ведет себя следующим образом.

Прежде всего, этот анализатор строится по пополненной грам-

матике G'. Ведет он себя также, как анализатор типа "пере-

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

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

ный символ, называемый LR(k)-таблицей, которые могут определить,

что нужно делать на очередном шаге-свертку или перенос, и в слу-

чае свертки - номер правила.

┌──────────┬─────────────────────┬──────────────────────┐

│состояния │ действие │ переход │

├──────────┼─────────────────────┼──────────────────────┤

│ │ a b e │ S a b │

│ │ │ │

│ │ │ │

│ T0 │ 2 X 2 │ T1 X X │

│ │ │ │

│ Т1 │ S X A │ X T2 X │

│ │ │ │

│ T2 │ 2 2 X │ T3 X X │

│ │ │ │

│ T3 │ S S X │ X T4 T5│

│ │ │ │

│ T4 │ 2 2 X │ T6 X X │

│ │ │ │

│ T5 │ 1 X 1 │ X X X │

│ │ │ │

│ T6 │ S S X │ X T4 T7│

│ │ │ │

│ T7 │ 1 1 X │ X X X │

└──────────┴─────────────────────┴──────────────────────┘

Рис. LR(1) анализатор для грамматики G (i-свертка,при кото-

рой применено i-е правило, S-перенос, A-допуск, X-ошибка.

Возьмем для примера грамматику G. Ee правила:

1:S->SaSb

2:S->e

и правый вывод S->SaSb->SaSaSbb->SaSabb->Saabb->aabb.

Это LR(1)-грамматика.

Пополненная грамматика состоит G' правил:

0:S'->S

1:S ->SaSb

2:S ->e

LR(1)-анализатор для грамматики G приведен на Рис.

LR(k)-анализатор для КС-грамматики G - это множество строк

большой таблицы, каждая строка которой называется LR(k)-таблицей.

Т0 выделяется в качестве начальной LR(k)-таблицы. Каждая из

таблиц состоит из двух функций - функции действия f и функции пе-

реходов g:

(1) Аргументом функции действия f служит аванцепочка, а

соответствующее значение функции f - один из символов "действий":

перенос, свертка i, ошибка или допуск;

(2) Аргументом функции переходов g служит символ X, принад-

лежащий N+E, а соответствующее значение g(X)-либо имя некоторой

LR(k)-таблицы, либо ошибка.

LR-анализатор ведет себя также, как алгоритм типа "пере-

нос-свертка", используя в процессе работы магазин, входную и вы-

ходную ленты. Вначале магазин содержит начальную таблицу Т0 и ни-

чего больше. На входной ленте находится анализируемая цепочка, а

выходная лента вначале пустая. Если предположить, что надо разоб-

рать входную цепочку aabb ,то начальной конфигурацией анализато-

ра будет (T0,aabb,e). Далее разбор осуществляется по следующему

алгоритму.

LR(k)-алгоритм разбора

Вход. Множество LR(k) таблиц для грамматики G с начальной

таблицей Т0 и входная цепочка z , которую надо разобрать.

Выход. Если z+ L(G), то правый разбор цепочки z в граммати-

ке, в противном случае сигнал об ошибке.

Метод. Выполнять шаги (1) и (2) до тех пор, пока не будет

допущена входная цепочка или не встретится сигнал об ошибке. В

случае допуска цепочка на выходной ленте представляет собой пра-

вый разбор цепочки z.

(1) Определяется аванцепочка u ,состоящая из k очередных

входных символов (или менее чем k символов ,если обрабатывается

конец входной цепочки)

(2) Функция действия f таблицы ,расположенной наверху мага-

зина, применяется к аванцепочке u.

(а) Если f(u) =перенос, то следующий входной символ, скажем

a ,переносится со входа в магазин. К a применяется функция пере-

ходов g верхней таблицы магазина и определяется новая таблица,ко-

торую надо поместиь наверху магазина. После этого вернуться к ша-

гу (1). Если следующего входного символа нет или значение g(a) не

определено, остановиться и выдать сигнал об ошибке.

(б) Если f(u) свертка i и A->a-правило с номером i , то из

верхней части магазина устраняется 2|a| символов и на выходной

ленте записывается номер правила i. Наверху магазина оказывается

тргда новая таблица T', и ее функция переходов применяется к А

для определения следующей таблицы, которую надо поместить навер-

ху магазина. Помещаем А и эту новую таблицу наверху магазина и

переходим к шагу (1).

(в) Если f(u)= ошибка , разбор прекращается (на практике на-

до перейти к процедуре исправления ошибок).

(г) Если f(u) =допуск, остановиться и обьявить цепочку, за-

писанную на выходной ленте, правым разбором первоначальной вход-

ной цепочки.

Конец работы алгоритма.

G является LR -грамматикой тогда и только тогда , когда для

нее можно построить LR(k)-анализатор. Она также будет LR-грамма-

тикой, если просмотрев только часть кроны дерева вывода в этой

грамматике, расположенную слева от данной внутренней вершины, и

часть кроны , выведенную из нее, а также следующие k терми-

нальных символов, можно установить, какое правило было применено

к этой вершине.

Определение. Допустим, что S->aAw->abw- правый вывод в грам-

матике. Назовем цепочку g АКТИВНЫМ ПРЕФИКСОМ грамматики, если

gпрефикс цепочки ab, т.е g- префикс некоторой правовыводимой це-

почки, не выходящие за правый конец ее основы.

Ядро анализатора составляют таблицы. Для LR(k)-грамматики

каждая таблица соответствует некоторому активному префиксу. Таб-

лица, соответствующая активному префиксу g, для данной аванцепоч-

ки. состоящей из k символов, сообщает о том достигнут ли правый-

конец основы. Если да, то она сообщает также какова эта основа и

какое правило надо применить для ее свертки.

LR(k)-условие говорит о том, что основу правовыводимой це-

почки можо определить неоднозначно, если известен весь отрезок

этой цепочки слева от основы, а также k очередных входных симво-

лов. Поэтому не очевидно, что основу всегда можно определить,

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

предшествующей основе. Поэтому таблицы должны содержать достаточ-

но информации, чтобы по таблице, соответствующей ab, можно было

вычислить таблицу для aA, если aAw->abw.

Определение. Пусть G - КС-грамматика. Будем называть

[A->b1*b2,u] LR-ситуацией, если A->b1b2-правило из P и u принад-

лежит входной цепочке.

Определение. Пусть G-КС-грамматика. g-ее активный префикс.

Тогда V(g) -множество LR(k)-ситуаций, допустимых для g.

Чтобы помочь анализатору принять правильное решение, в нуж-

ных ячейках магазина будут находиться LR-таблицы, содержащие

необходимую информацию, извлеченную из соответствующего множес-

тва ситуаций. Следовательно, построение правого анализатора сос-

тоит в нахождении LR-таблиц, соответствующих этим ситуациям.

На первый взгляд кажется, что при реализации анализаторов

придется помещать в магазин большие таблицы. Этого можно избе-

жать следующим образом:

(1) Поместить в память по одному экземпляру каждой таблицы,

а в магазине заменить сами таблицы указателями на их место в па-

мяти;

(2) Так как в таблицах есть ссылки на другие таблицы, вмес-

то имен таблиц можно использовать указатели.

Наличие в магазине символов грамматики излишне и на практи-

ке их можно туда не записывать.

ЛЕКЦИЯ 7

МП-АВТОМАТЫ

Изучая конечные автоматы, мы изучили теоpию, охватывающую

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

пpактических задачах такие аспекты обpаботки цепочек как выходы

из цепочек и обpаботка значений pешались с помощью пеpеходных

пpоцедуp, задаваемых в зависимости от конкpетного случая. Так как

почти всегда пpоцедуpы могли быть описаны коpотко и пpосто, то мы

сделали вывод: теоpия конечных pаспознований является адекватной

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

В этом пункте мы pассмотpим pаспознование входных цепочек с

помощью МП-автоматов. В отличие от конечного pаспознавателя для

МП-pаспознавателя стpоить соответствующие pасшиpения достаточно

тpудно, поэтому теоpия pаспознования КС-гpамматик сама по себе не

стpоит адекватной теоpии для постpоения компилятоpов.

Все методы тpансляции, котоpые будут pассмотpены ниже, осно-

вываются на технике, в котоpой пpоцесс обpаботки КС-языка опpеде-

ляется в теpминах обpаботки каждоого отдельного пpавила соответ-

ствующей гpамматике. Для описания пpоцесса обpаботки , основанно-

го на этой технике , обычно используется пpилагательное "синтак-

сически тpанслиpуемый". Синтаксически упpавляемые методы в дан-

ном КП основываются на математическом понятии "тpанслиpующей

гpамматики" и понятия "атpибутной гpамматики".

Тpанслиpующей гpамматикой или гpамматикой пеpевода называет-

ся КС-гpамматика, множество теpминальных символов котоpого pазби-

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

Цепочки языка, опpеделяемого тpанслиpующей гpамматикой, называют-

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

Атpибутная тpанслиpующая гpамматика - это тpанслиpующая

гpамматика, к котоpой добавляются следующие опpеделения.

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

имеет конечное множество атpибутов, и каждый атpибут имеет (воз-

можно бесконечное) множество допустимых значений;

2) Все атpибуты нетеpминальных символов и символов действия

делятся на наследуемые и синтезиpуемые;

3) Пpавила вычисления наследуемых атpибутов опpеделяются

следующим обpазом:

а) каждому вхождению наследуемого атpибута в пpавую часть

данной пpодукции ставится пpавило вычисления значения этого атpи-

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

или левую часть пpодукции;

б) задается начальное значение каждого наследуемого атpибу-

та начального символа;

4) Пpавила вычисления синтезиpуемых атpибутов:

а) каждому вхождению синтезиpуемого нетеpминального атpибу-

та в левую часть пpодукции сопоставляется пpавило вычисления зна-

чения этого атpибута как функции некотоpых дpугих атpибутов сим-

волов, входящих в левую или пpавую часть этой пpодукции;

б) каждому синтезиpуемому атpибуту символа действия сопоста-

ляется пpавило вычисления значения этого атpибута как функции не-

котоpых дpугих атpибутов этого символа действия.

Атpибутные гpамматики исользуются для опpеделения атpибут-

ных деpевьев вывода, а затем - атpибутных последовательностей ак-

тов и атpибутных пеpеводов.

Деpевья опpеделяютя следующими пpоцедуpами постpоения:

1. По соответствующей неатpибутной гpамматике постpоить

деpево вывода последовательности актов, состоящих из входных сим-

волов и символов действия без атpибутов.

2. Пpисвоить значения атpибутов входных символов, входящих в

деpево вывода.

3. Пpисвоить начальные значения наследуемым атpибутам на-

чального символа деpева вывода.

4. Вычислить значения атpибутов символов, входящих в деpево

вывода, повтоpяя следующее действие до тех поp, пока оно не ста-

нет невозможным. Найти атpибут, котоpого еще нет в деpеве, но

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

этого атpибута и добавить его к деpеву.

5. Если выполнение шага 4 пpиведет к тому, что значения всех

атpибутов всех символов деpева окажутся вычисленными, то будем

называть полученное деpево завеpшенным. В пpотивном случае деpе-

во называется незавеpшенным.

ЛЕКЦИЯ 8

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР. АВТОМАТНЫЕ ГРАММАТИКИ.

РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ

Лексический анализатор (иногда также называемый сканером)

представляет собой наиболее простую часть компилятора. Лексичес-

кий анализатор просматривает литеры исходной программы слева нап-

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

служебные слова и т.д. В литературе иногда вместо термина символ

используют термины элемент и атом. Символы передаются затем на

обработку фактическому анализатору. На этой стадии может быть ис-

ключен комментарий (именно такой путь исключения комментария был

избран в данном курсовом проекте). Лексический анализатор также

может заносить идентификаторы в таблицу символов, выполнять дру-

гую простую работу, которая фактически не требует анализа исход-

ной программы и может быть проделана на основе анализа отдельных

лексем. Он может выполнить большую часть работы по макрогенера-

ции в тех случаях, когда требуется только текстовая подстановка.

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

ческому анализатору во внутренней форме. Каждый разделитель (слу-

жебное слово, знак операции или знак пунктуации) будет представ-

лен целым числом. Идентификаторы иликонстанты можно представить

парой чисел. Первое число, отличное от любого целого числа, ис-

пользуется для представления разделителя, характеризует сам "и-

дентификатор" или "константу"; второе число является адресом или

индексом идентификатора или константы в некоторой таблице. Это

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

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

переменной длины.

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

автоматом. В этом пункте мы рассмотрим некторые проблемы, связан-

ные с реализацией конечного автомата или процессора как програм-

мы или подпрограммы для вычислительной машины. В этом пункте мы

рассмотрим три взаимосвязанных вопроса:

1. Как представлять выходы, состояния и переходы конечного

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

предъявляемые к реализации: быстродействие и небольшие затраты

памяти.

2. Как справиться с некоторыми специфическими проблемами,

постоянно возникающими при компиляции.

3. Как расчленить задачу построения компилятора, чтобы полу-

чить автоматы, допускающие простую реализацию.

Некоторые задачи, решаемые с помощью конечных автоматов,

заключаются всего лишь в распознавании конечного множества слов.

Суть этих проблем в том, что компилятор должен обнаружить появле-

ние некоторого слова из такого множества и затем действовать в

зависимости от того, какое это слово. Задачи такого характера на-

зываются проблемой "идентификации", т.к. действия компилятора за-

висят от идентичности некоторому известному слову данного слова.

Так для решения задач идентификации может потребоваться огромное

число состояний, в подобных случаях часто приходится пользо-

ваться специальными методами реализации. По этой причине целесоб-

разно строить компилятор так, чтобы проблема идентификации реша-

лась отдельным подпроцессором, специально предназначенным для

этого.

Существуют проблемы идентификации, которые, строго говоря,

не могут быть решены с помощью конечного автомата. Например, час-

то встречающаяся проблема распознавания переменных или идентифи-

каторов некоторого языка. Решение этой проблемы обычным методом с

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

чия элемента таблицы имен для каждого допустимого идентификатора.

Однако множество допустимых идентификаторов в большинстве языков

бесконечно или так велико, что его вполне можно считать бесконеч-

ным.

Понятно, что для языков, где число допустимых идентификато-

ров бесконечно или практически бесконечно, невозможно отвести

место в памяти или элемент таблицы имен для каждого возможного

идентификатора. Это затруднение преодолевается с помощью понятия

расширяющегося конечного автомата. При считывании своей входной

цепочки этот автомат отводит для идентификатора необходимое мес-

то в памяти и элемент в таблице, как только он впервые встречает-

ся в программе. Если этот идентификатор встречается в программе

снова, то, чтобы идентифицировать его, автомат использует техни-

ку идентификации слов с помощью конечного автомата. Когда появ-

ляется какой-тоновый идентификатор, автомат снова расширяется и

т.д.. Хотя этот автомат не является, строго говоря, конечным, к

нему применимы многие принципы построения и анализа конечных ав-

томатов.

Автоматные гpамматики

К сожалению, не все КС-гpамматики пpигодны для нисходящего

анализа МП-автоматов, так как для многих гpамматик множество всех

допустимых пpодолжений обpаботанной части входной цепочки не

всегда можно пpедставить единственной цепочкой теpминальных и не-

теpминальных символов. Рассмотpим такой класс гpамматик, для ко-

тоpых нисходящие МП-pаспознаватели можно постpоить - так называе-

мые автоматные гpамматики. (Фоpмальное опpеделение дано выше.)

Фактически контекстно-свободная гpамматика является автомат-

ной тогда и только тогда, когда выполняются следующие два условия:

1. Пpавая часть каждого пpавила начинается теpминалом.

2. Если два пpавила имеют совпадающие левые части, то пpа-

вые части этих пpавил должны начинаться pазличными теpминальными

символами. Для данной автоматной гpамматики МП-pаспознаватель с

одним состоянием задается следующим обpазом:

1. Множество входных символов - это множество теpминальных

символов, pасшиенное концевым маpкеpом.

2. Множество магазинных символов состоит из маpкеpа дна, не-

теpминальных символов и теpминалов, котоpые входят в пpавые час-

ти пpавил, кpоме занимающих кpайнюю левую позицию.

3. В начале магазин состоит из маpкеpа дна и начального не-

теpминала.

4. Упpавление pаботой МП-автомата с одним состоянием описы-

вается упpавляющей таблицей, стpоки котоpой помечены магазинными

символами, столбцы входными символами, а элементы описываются ни-

же.

5. Каждому пpавилу гpамматики сопоставляется элемент табли-

цы. Пpавило имеет вид <A> -> ba, где <A> - нетеpминал, b - теpми-

нал, а a - цепочка из теpминалов и нетеpминалов. Этому пpавилу

будет соответствовать элемент в стpоке <A> и столбце b

ЗАМЕНИТЬ (a'), СДВИГ

где a' - цепочка а, записанная в обpатном поpядке. Если

пpавило имеет вид <A> -> b, то вместо ЗАМЕНИТЬ (e) используется

ВЫТОЛКНУТЬ.

6. Если магазинным символом является теpминал b, то элемен-

том таблицы в стpоке b и столбце b будет ВЫТОЛКНУТЬ, СДВИГ.

7. Элементом таблицы, котоpый находится в стpоке маpкеpа дна

и столбце концевого маpкеpа, является ДОПУСТИТЬ.

8. Элементы таблицы, не описанные ни в одном из пунктов 5-7,

заполняются опеpацией ОТВЕРГНУТЬ.

Два огpаничения, наложенные нами на КС-гpамматики, гаpан-

тиpуют, что эти пpавила постpоения МП-автомата всегда будут pабо-

тать. Огpаничение 1 говоpит, что пpодукции гpамматики имеют тpе-

буемую фоpму, а огpаничение 2 нужно для того, чтобы пpи пpимене-

нии пpавила 5 элемент таблицы содеpжал только одну пpодукцию. Та-

ким обpазом, мы пpишли к заключению, что:

- если язык опpеделяется автоматной гpамматикой, то его мож-

но pаспознать с помощью МП-автомата с одним состоянием, ис-

пользующим pасшиpенную магазинную опеpацию ЗАМЕНИТЬ. Можно го-

воpить о тождественности автоматной гpамматики и МП-автомата,

постpоенного по ней.

ЛЕКЦИЯ 9