Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 19

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

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

Например, компилятор может заменить 2С на 2нС (2+С тоже годится, но в данном случае мы „знаем", что 2еС правдоподобнее). (3) Устранение одной лексемы. Напрямер, в таком операторе Фортрана, как !)О !О 1=1, 20, часто неправильно ставят запятую после 10. ' (4) Простая перестановка лексем. Например, вместо 11ЧТЕОЕК 1 может быть неправильно написано 1 15)ТЕОЕК. Во многих языках программирования операторы легко опознаются.

Если разбор конкретного неправильно построенного оператора становится безнадежным — даже после того, как произведены изменения вроде описанных выше, часто можно полностью игнорировать этот неправильный оператор и продолжить разбор, как будто его и не было. Вообще, результатов математического характера об алгоритмах, обнаруживающих ошибки, н алгоритмах, выдающих „хорошую" диагностику, мало. В гл.

4 и 5 мы обсудим несколько алгоритмов синтаксического анализа; 1.1.-алгоритм, 1 К-алгоритм и алгоритм Эрли, обладающие тем свойством, что как только выясняется, что просмотренную часть входной цепочки нельзя продолжить до правильной цепочки, алгоритм объявляет об этом, Это свойство полезно для обнаружения и анализа ошибок, однако далее мы будем рассматривать и такие алгоритмы, которые этим свойством не обладают. 4.?.3. Резюме На рис.

1.7 приведена наша принципиальная модель компилятора. Здесь фаза оптимизации следует за фазой генерации кода, но, как мы уже отмечали, разнообразные попытки оптимизации кода могут делаться по ходу всего процесса компиляции. гл. ь введение в компиляцию К процедуре анализа и исправления ошибок можно обращаться на этапах лексического анализа, синтаксического анализа и генерации кода, и если исправление закончилось успешно, то процесс продолжается с того места, где произоп1ло обращение к этой процедуре. Ошибки, при которых в некотором месте входной цепочки не оказывается никакой лексемы, обнаруживаются в ходе лексического анализа.

Ошибки, при ко~арык входную программу можно разбить. на лексемы, но к этой последовательности лексем нг подходит никакое синтаксическое дерево, обнаруживаются в ходе синтаксического анализа. Наконец, ошибки, при которых входная цепочка имеет синтаксическую структуру, но для нее не получается осмысленный код, обнаруживаются в процессе генерации кода. Примером такой ситуации может служить переменная, используемая без описания. Синтаксический анализатор игнорирует информационную компоненту лексемы, так что он ие заметит этой ошибки. Таблицы имен образуются в процессе лексического анализа, а иногда также и в ходе синтаксического анализа, когда, скажем, атрибуты и идентификаторы, к которым они относятся, связываются друг с другом в формируемой древовидной структуре.

Зги таблицы используются при генерации кода и, возможно, на этапе ассемблирования. На рис. 1,7 показана также заключительная фаза, которую мы называем ассемблированием. На этом этапе промежуточный код обрабатывается для получения окончательного представления объектной программы в машинном языке. Некоторые компиляторы могу~ выдавать код иа машинном языке непосредственно как результат процесса генерации кода, так что фазу ассемблирования можно явно не указывать. Модель компилятора, изображенная на рис. 1.7, есть лишь первое приближение к реальному компилятору.

Например, некоторые компиляторы проектируются так, чтобы они занимали небольшой объем памяти. В результате получается много фаз компиляцви, которые выполняются последовательно, постепенно преобразуя исходную программу в объектную. Наша цель состоит не в том, чтобы перечислять все способы построения компиляторов. Мы скорее интересуемся фундаментальными проблемами, возникающими при построении компиляторов и других устройств, предназначенных для обработки языков.

УПРАЖНЕНИЯ *1.2.1. Опишите синтаксис и семантику операторов присваивания Фортрана. *1.2.2. Можно ли на Вашем любимом языке программирования написать программу, определяющую произвольное рекур- 92 ГЛ. Ц ВВЕДЕНИЕ В КОМПИЛЯЦИЮ К процедуре анализа и исправления ошибок можно обращаться на этапах лексического анализа, синтаксического анализа и генерации кода, и если исправление закончилось успешно, то процесс продолжается с того места, где произошло обращение к этой процедуре, Ошибки, при которых в некотором месте входной цепочки не оказывается никакой лексемы, обнаруживаются в ходе лексического анализа.

Ошибки, при ко!орых входную программу можно разбить- на лексемы, но к этой последовательности лексем не подходит никакое синтаксическое дерево, обнаруживаются в ходе синтаксического анализа. Наконец, ошибки, при которых входная цепочка имеет синтаксическую структуру, но для нее не получается осмысленный код, обнаруживаются в процессе генерации кода. Примером такой ситуации может служить переменная, используемая без описания. Синтаксический анализатор игнорирует информационную компоненту лексемы, так что он не заметит этой ошибки. Таблицы имен образуются в процессе лексического анализа, а иногда также и в ходе синтаксического анализа, когда, скажем, атрибуты и идентификаторы, к которым они относятся, связываются друг с другом в формируемой древовидной структуре.

Эти таблицы используются при генерации кода н, возможно, на этапе ассемблирования. На рис. 1.7 показана также заключительная фаза, которую мы называем ассемблированпем. На этом этапе промежуточный код обрабатывается для получения окончательного представления объектной программы в машинном языке.

Некоторые компиляторы могуг выдавать код на машинном языке непосредственно как результат процесса генерации кода, так что фазу ассемблирования можно явно не указывать. Модель компилятора, изображенная иа рис. 1.7, есть лишь первое приближение к реальному компилятору. Например, некоторые компиляторы проектируются так, чтобы они занимали небольшой объем памяти. В результате получается много фаз компиляции, которые выполняются последовательно, постепенно преобразуя исходную программу в объектную.

На!па цель состоит ие в том, чтобы перечислить все способы построения компиляторов. Мы скорее интересуемся фундаментальнымн проблемами, возникающими при построении компиляторов и других устройств, предназначенных для обработки языков. УПРАЖНЕНИЯ *1.2,1. Опишите синтаксис и семантику операторов присваивания Фортрана, '1.2.2. Можно ли на Вашем любимом языке программирования написать программу, определяющую произвольное рекур- ГЛ.

!. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ сивно перечислимое множество? Обязательно ли скомпилирует эту программу заданный компилятор? 1.2.3. Приведите пример программы Фортрана, которая синтаксически построена правильно, но пе задает (всюду определенный) алгоритм. о*1.2.4. На какое максимальное число символов требуется заглядывать вперед при прямом лексическом анализе Фортрана? (Имеется в виду число символов, которые просматриваются анализатором, но не составляют часть лексемы, для обнаружения которой осуществляется этот просмотр.) е"1.2.6. На какое максимальное число символов требуется заглядывать вперед при лексическом анализе Ллгола 60? (Можно считать, что лишние пробелы и концевые маркеры перфокарт уже удалены.) 1.2,6, Разберите оператор Х = А нВ+ С: П, используя дерево с внутренними вершинами, как па рис.

1.4. Унаааны: Вспомните, что по известному соглашению при отсутствии скобок умножения выполняются перед сложениями. 1.2.7. Разберите так же, как в упр. 1.2.6, оператор Х=Ае (В+С)н17. Указание: При перемножении нескольких операндов можно считать, что порядок умножений не играет роли'). Выберите любой, какой Вам нравится. 1.2.8. Примените правила генерации кодов, изложенные в равд. 1,2.5, для синтаксически управляемого перевода деревьев разбора из упр. 1.2.6 и 1,2.7.

"1.2.9. Сохраняет ли преобразование последовательности ) ОЛЭ а; ВТОРОЕ )); ЕОЛР у; ЗТОЕЕ 6 в последовательность ).ОЛ1) у; ЗТОЕЕ 6; 1ОЛ)) а; ВТОЕЕ () отношение между входом и выходом, определяемое программой? Если нет, то какие ограничения' надо наложить на идентификаторы а, )), у, 6? (Предполагается, что к операторам преобразуемой последовательности не происходит переходов извне.) 1.2.16. Приведите примеры преобразований кодов ассемблера, сохраняющих определяемое программой отношение между входом и выходом. ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ е1.2.12.

Постройте схему синтаксически управляемой трансляции арифметических выражений, содержащих как целые, так и вещественные переменные. (Считайте, что тнп каждого идентификатора известен н операция над вещественным значением н целым дает вещественное.) *1.2.13. Докажите, что алгоритм 1.1 работает правильно. Сначала нужно определить, когда входной оператор присваивания эквивалентен выходному коду ассемблера. Проблема для исследования С компиляцией и трансляцией алгоритмов связано много областей исследования н открытых проблем. Их мы еще будем упоминать в других главах. Но об одной из них мы скажем здесь, так как эту область мы рассматривать пе будем. 1.2.14, Разработайте технику доказательства корректности (правильности) компиляторов, В этой и более широкой области доказательства корректности программ и алгоритмов уже проделана некоторая работа (см.

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

Список файлов книги