Главная » Просмотр файлов » Теория синтаксического анализа, перевода и компиляции - Том 1

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

Файл №943928 Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции) 17 страницаТеория синтаксического анализа, перевода и компиляции - Том 1 (943928) страница 172013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

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

В некотором отношении синтаксический анализ программы напоминает разбор предложений, который все мы проводили в школе. Пример 1.3. Допустим, гго выход лексического анализатора— цепочка лексем (1.2.1) <ид>, = (<ид>, + <ид>,) Р <ид>, Эта цепочка передает информацию о том, что необходимо выполнить в точности следующее: (1) <ид>, прибавить к <ид>„ (2) результат (1) умножить на <ид>„ (3) результат (2) полгестить в ячейку, зарезервированную для <ид>,.

Эту последовательность шагов можно представить наглядно с помощью помеченного дерева, показанного на рис. 1.3. Внут- 1.2.4. Сиитаиснчесимй анализ Как уже упоминалось, выходом лексического анализатора является цепочка лексем. Эта цепочка образует вход синтаксического анализатора, исследующего только первые компоненты лексем † типы. Информация о каждой лексеме (вторая компонента) используется на более позднем этапе процесса компиляции для генерации машинного кода. Синтаксический анализ, или разбор, как его еще пазывают,— это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка.

Какова синтаксическая структура данной цепочки, существенно знать также и при генерации кода. Например, синтаксическая структура выражения А 1-ВвС должна отражать тот факт, что сначала перемножаются В и С„а потом результат складывается с А. При любом другом порядке операций нужное вычисление не получится. 80 Рнс. !.3. ДРевовнднвв стРУктУРа. гл. ь введение з компиляцию ренине вершины дерева представляют те действия, которые надо выполнить.

Прямые потомки каждой вершины либо представляют аргументы, к которым нужно применить действие (если соответствующая вершина помечена идентификатором или является внутренней), либо помогают определить, каким должно быть это действие (в частности, это делают знаки +,, — --).

Заметим, что скобки в цепочке (1.2.!) в дереве явно не укззаиы, хотя мы могли бы изобразить нх в качестве прямых потомков вершины и,. Роль скобок только в том, что они влияют на порядок операций. Если бы в цепочке (1.2,1) их не было, следовало бы поступать согласно обычному соглашению о том, что умножение „предшествует" сложению, и на первом шаге перемножить <ид>, и <ид>,. П 1.2.$.

Генерация кода Дерево, построенное синтаксическим анализатором, используется для того, чтобы получить перевод входной программы, Этот перевод может быть программой в машинном языке, но чаще он бывает программой в промежуточном языке, таком, как язык ассемблера или втрехадресный код" (последний образуется из простых операторов, каждый из которых включает не более трех идентификаторов; например, А — -- В, А = В+С или СОТО А). Если требуется, чтобы компилятор произвел существенную оптимизацию кода, то предпочтительнее код трехадрссного типа.

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

Пусть в этом примере наша машина имеет один рабочий регистр (суммзтор, или регистр результата) н команды языка ассемблера, вид которых определен в тзбл. 1. 2. Запись,с (т) сулей|атор" означает, что содержимое ячейки памяти т надо по. местить в сумматор. Через =-т обозначено численное значение ш. Из этих замечаний ясен смысл всех семи команд. Выходом синтаксического анализатора служит дерево (или некоторое представление дерева), представляющее синтаксическую структуру цепочки лексем, полученной на выходе лексического анализатора. С помощью этого дерева и информации, хранящейся в таблице имен, можно построить объектный код.

На практике построение дерева и генерация кода часто осущест- 82 ьй ОББОР ппоцессй компиляции вляются одновременно, но методически удобнее считать, что они происходят последовательна. Существует несколько методов построения промежуточного кода по синтаксическому дереву. Один нз них, называемый синтаксически управляемым пврвводом (трансляиивй), особенно изящен и эффективен. В нем с каждой вершиной п связывается Таблица А2 Действие К в.л. с (сп) — в сумматор с (сумматор) + с (ю) — сумматор с (сумматор):в с (пй) — в сумматор с (сумматор) — пй гп сумматор с (сумматор)+ сп — сумматор с (сумматор), п1 — в сумматор йОЛР еп АРР еп МРУ пй 8ТО((Е гп сОАР— пй ЛРР =т МРУ =ю Предполагается, сто АРР н МРУ вЂ” операция с плааааппей почкой. 83 цепочка С (п) промежуточного кода.

Код для вершины и строится сцеплением в фиксированном порядке кодовых цепочек, связанных с прямыми потомками вершины п, и некоторых других фиксированных цепочек. Процесс перевода идет, таким образом, снизу вверх (т. е. от листьев к корню). Фиксированные цепочки и фиксированный порядок задаются используемым для перевода алгоритмом.

Подробнее об этом будет изложено в гл. 3 и 9. Здесь возникает важная проблема: для каждой вершины и выбрать код С(п) так, чтобы код, приписываемый корню, оказался искомым кодом всего оператора. Вообще говоря„нужна какая-то интерпретация кода С(п), которой можно было бы единообразие пользоваться во всех ситуациях, где может встретиться вершина и. Для арифметических операторов присваивания нужная интерпретация получается весьма естественно; мы опишем ее в следующих абзацах.

В общем случае при применении синтаксически управляемой трансляции интерпретация должна задаваться создателем компилятора. Эта задача может оказаться легкой или трудной, и в трудных случаях, возможно, придется учитывать структуру всего дерева. В качестве характерного примера опишем синтаксически управляемую трансляцию арифметических выражений. Заметим, что иа рис. 1.3 есть три типа внутренних вершин, зависящих от !.Е. ОБЗОР ПРОЦЕССА КОМПИЛЯЦИИ ГЛ !.

ВВЕДЕНИЕ В КОМПИЛЯЦИЮ е Рис. 1РК Типы ееутренеех еерюии. 85 того, каким из знаков =, -(, е помечен средний потомок. Эти три типа вершин показаны на рис. 1.4, где треугольниками изображены произвольные поддеревья (возможно„состоящие из единственной вершины). Для любого арифметического оператора присваивания, включающего только арифметические операции + и е, можно построить дерево с одной вершиной (корнем) типа а и остальными внутренними вершинами только типов б и а. Код, соответствующий вершине и, будет иметь следующую интерпретацию: (!) Если п — вершина типа а, то С(п) будет кодом, который вычисляет значение выражении, соответствующего правому поддереву, и помещает его в ячейку, зарезервированную для идентификатора, которым помечен левый потомок.

(2) Если и — вершина типа б или в, то цепочка ЕОАО С(п) будет кодом, засылающим в сумматор значение выражения, соответствующего поддереву, над которым доминирует вершина и. Так, для дерева, изображенного на рис. !.3, код !.ОАО С(п,) засылает в сумматор значение выражения <ид>, + <ид>„, код (.ОАВ С(п,) засылает в сумматор значение' выражения (<ид>е+ <ид>,) е <ид>„а код С (пл) засылает в сумматор значение последнего выражения и помещает его в ячейку, предназначенную для <ид>,. Теперь надо показать, как код С(л) строится из иодов потомков вершины и.

В дальнейшем мы будем предполагать, что операторы языка ассемблера записываются в виде одной цепочки и отделяются друг от друга точкой с запятой или началом новой строки. Кроме того, мы будем предполагать, что каждой вершине и дерева приписано число 1(п), называемое ее уровнелл, которое означает максимальную длину пути от этой вершины до листа. Таким образом, 1(п) = О, если п †ли, а если и имеет потомков и„..., ал, то 1(п) = шах 1(пВ+!. Уровни 1(п) можно ! е: ! .,А вычислять снизу вверх одновременно с вычислением кодов С (п).

Уровни записываются для того, чтобы контролировать использование временных ячеек памяти. Две нужные нам величины нельзя засылать в одну и ту же ячейку памяти. На рис. !.5 показаны уровни вершин дерева, изображенного на рис. !.3. Теперь определим синтаксически управляемый алгоритм генерации кода, предназначенный для вычисления кодов С (п) всех <еа>е + си1слз и О 0 Рис.

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

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

Тип файла
DJVU-файл
Размер
4,65 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее