Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 17
Текст из файла (страница 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- и е. Предполагается, что уровни всех вершин уже вычислены, Выход. Код в языке ассемблера, вычисляющий этот оператор Присваивания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
