Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 50
Текст из файла (страница 50)
Реализуйте генератор кодов, построенный в упр. 9.1.11. Скомби. пируйте этл програымы с лексическим анализатором, чтобы получи~ь компилятор с этого подмножества Фортрана. Сконструируйте тестовые цепочки, на которых можно было бы проверить правильность работы каждой программы Обсаженные схемы сиетлксическв управляемого переводе опнсены е работе Ахо и Ульыевв 1191111 твм же ыожво найт» решение упр.
9.3 3. В рв. ботс Квутв 1196661 ппределяются слепы перепаде с нвслехственнымп н снитезирооеняыин втрибутеми; твм же обсуждаются ОСУ-скопы но упр. 9.3.10 н 9.3.11. Решение упр. Ч 3 14 дели Бруно в Беркхврд 1Щ701 и Кнут 1196861; упр. 9,3.12 взято из реботы Кнута 11968 61. Е этой главе рассматриваются методы, с помощью которых информацию можно быстро запомнить и найти в таблипах.
Наиболее важное применение этих методов †хранен информации О лексемах, полученных в процессе лексического анализа, и нахождение ее при генерации кода. Мы разберем два подхода: простые методы нахождения информации и формализм грамматик свойств. Последний заключается в том, что атрибуты и идентификаторы связываются между собой по мере того, как появляется уверенность, что для каждого идентификатора доступна вся необходимая для целей перевода информация. Таблицы, хранящие имена и янформацию, связанную с этими именами, называются юабсицами имен. Таблицы имен используются практически во всех компиляторах. Таблица имен нзо.
бражеиа на рнс. 10.1, Элементами палей имен являются обычно идентификаторы. Если имена могут быть различной длины, тв удобнее, чтобы элементы полей имен были указателями на об. лесть памяти, фактически хранящую эти имена. гл. 1О. ОРганизхцяя инФОРиации Элементы полей данных, называемые иногда дескрипторами, лают ннформацхю, которую надо собрать о каждом имени. В некоторых сит! ацнях с данным именем можно связать дюжину илн более элементов информации. Например, возможно, что надо знать тип данных (вещественный, Пелый, строковый а т. д.) идентификатора;был ли он меткои, именем процедуры или формальным параме'ром процедуры; должен ли ов распределяться в статической наи динамической области памяти; был ли он идентификатором, имеющим структуру (например, масспвом), и если да, то какую структуру (напримср, размерность массива).
Если число злешпгов информации, связанной с данным именем, перемеино, то снова удобно хранить в поле данных указатель на эту информацию. 10.1.1. Хранение информации о лексемам Компилятор использует таблицу имен для хранения информации о лексема!, в частности об идентификаторах. Эта инфор. мация используе кя затем для двух целей. Во-первых, для проверки семантической правильности исходной программы. Напри.
мер, если в исходной программе есть оператор вила ПОТО ЕООР то компилятор должен проверить, что идентификатор ЕООР встречается в прпграмме в качестве метки соответствующего оператора. Такую информацию можно найти в таблице имен (хотя и ие обязатвзьно во время обработки оператора перехода). Во-вторых, информация в таблице имен используется при генерации кода. Например, если в исходной программе па Фортране есть оператэр вида А = В +С то генерированный для операции -'- код зависит от атрибутов идентификаторов В н С (скажем, иьюют ли они фиксированную или плавающую точку, находятся ли внутри или вие области СОММО)т( и т, д.) Лексический анализатор заносит имено и информацию в таблицу имен, Например, всякий раз, когда лексический аналязатор обнаруживает идентификатор, он проверяет в таблице имен, встречалась ли ранее такая же лексема.
Если нет, то лексический анализатор заносит в таблицу имя этого идентификатора вместе с соответствующей информацией. Если идентификатор ухтс есть в некоторой ячейке ! таблицы имен, то лексический ана. лизатор вырабатывает на выходе лексему (<идентификатор>, !), Такилт образок, лексический анализатор обращается а таблицу имен каждыв раз, когда он находит лексему, и чтобы скон- 10.1. Тавлицы имен струировать эффективный компилятор, надо уметь по даннолту вхождению идентификатора быстро определить, отведена ли для этого идентнфпкатора ячейка в таблице имен.
Если этого элемента нет, то надо иметь возможность быстро вставить идентификатор в таблипу. Пример 10.1. Предположим, что при компиляции языка типа Фортран дяя всех имен переменных используется единственная лексема типа (идентификатор>, Когда (прямой) лексический анализатор впервые обнаруживает идентификатор, он может завести в таблицу имен информацию о том, имеет ли соответствующая переменная фиксированную или плаватощую тачку. Лексический анализатор получает эту информацию по первой букве идентификатора.
Конечно, если в силу предыдущего объявления идентяфикатор является фуницпей либо подпрограммой или не подчиняется обычному соглашению о фиксированной илн плавающей точке, то ннформацпя для него уже содерисится в таблице имен, и зто приводит и тому, что лексический анализатор не заносит информацию о ием в таблицу. Пример 10.2. Предположим, что разрабатывается компилятор с языка, в котором объявления массивов определяются праниламн (оператор массива) массив (список массивов) (список массивов) (определение массива), (список массивов) ((определение массива) (определение массива) (идентификатор) ((целое)) Примером объявлении массива в этом языке служит (10.1.1) массив АВ(10), СВ(20) Для простоты мы здесь предполагаем, что массивы одномерны. Дерево разбора для оператора (10.1,1) ьзображево на рис.
10.2, на котором идентнфинаторами являются АВ и СП, а целыми— 10 и 20. На этом дереве разбора лексемы <идентификатор>„ <идентификатор)„ (целое)1 и (целое), представляют соответственно АВ, СР, 1О и 20. Естественно, оператор объявления массивов не выполняется; он ие компилнруется в машинный код. Однако имеет смысл рассматривать его перевод как последовательность шагов по орга. низации информации, поторые должны выполняться непосредственно компилятором.
Таким образом, если переводом идентификатора является указатель на отведенное для него место в таблице имен, а перевод целого †о само, то синтаксически управляемым переводом вершины, помеченной (определение хаэ гл ы организация инеогмлции ыл тлатицы имен массива>, мог ут быть команды для механизмов организации информации, предназначенные для того, чтобы запомнить, что идентификато — эт целое. С) ф " р — о ллассвв, вега размер — это соответствухл ее ' у и Рэс.
!О.я. дерево разбора оператора массива. имен, мн Способы применения информации, запомненн й б, о в та лице жения в а и огочисленны. Простой пример: для каждог о подвыраарифметическом выражении может требоваться нвфомаиня о его ви е, чтоб д, бы знать, над какими числами выполйять нвфорарифметические операции †н числами с фиксированной или плавающей точкой, номплексными числами и т. д. Э нф ц ыбирается из таблицы имен для листьев, помеченных как константы нли идентификаторы, и передается вверх по дечисло с реву в соответствии с такимн, например, соглаш число с фиксированной точкой-1-число с плавающ й е точкой = плавающей точкой, а число с плавающей точкой-' лексное число.= очко -'комп.=комплексное числа.
С другой стороны, язык, а следовательно и компилятор, может запрещать выражения со смешанными видами (как это делается, напрнме, н версиях Фортрана). 'пример, в некоторЫх 10.1.2. Меквнизмы запоминания омпнлятору нужны Из сказанного можно закл!очить, чта к методы организации информации, способные быстро запоминать и выдавать информацию о большом числе различных объектов 27а (например, идентификаторах). Кроме тога, в то время как число объектов, реально появляющихся в программе, может быть и велико (скажем, для типичной програллмы порядка 100 ила 1000), число всех возможных объектов имеет порядок несравненно более высокий; большинство из возможных идентификаторов в данной программе не появляется, Изложим кратко возможные способы запоминания информации в таблицах, чтобы обосновать использование таблиц расстановки, нлв распределенной памяти, которые будут изучаться в Следующем разделе. Основную проблему можно сформулировать так.
Есть большой набор об ьектов, которые могут встретиться. Объект здесь может рассматриваться как имя, состоящее из цепочки символов. Объекты встречаются нам в непредсказуемом порядке,и точное число объектов, которые могут встретиться, заранее неизвестно.
Как только объект астретияся, надо проверить в таблице, по. являлся ли он раньц1е, и если нет, внеств его имя в таблицу. Помилю этого, будет еще н другая инфорл~аиня об обьекте, которую нам надо будет запомнить в таблице, Сначала разберем использование для запоминания информации об объектах таблиц с прямым доступом.
В такой таблице для каждого возл1ожиого объекта резервируется отдельная ячейка. В ней запоминается информация относительно этого объекта, и нет необходимости запоминать в таблице его имя. Если число возможных объектов мало и для каждого обьекта действительно можво выделить отдельную ячейку, такая таблаца †табли с прямым доступом — дает очень быстрый механизм звполлинания и извлечения информации об объектах. Однако в большинстве случаев идею применения таблицы с прямым доступом прихо. дится отвергнуть, поскольку размер таблицы был бы недопустим, а ббльшая ее часть не использовалась бы. Например, число идентификаторов Фортрана (буква, за которой следует до пяти букв или цифр) равно примерно 1 33 х 1О'. Другой возможный метод запоминания †использован магазина, Когда встречается новый объект, его имя и указатель на инфорл1ацню, отаасящуюся к этому объекту, помещаются в верхушку магазина.
В этом случае размер таблицы пропорционзл«н числу действительно встретившихся объектов, а новые объекты можно вставить очень быстра. Но извлечение инфорл1ацин об объекте требует просмотра магазина до тех пор, пока объект не будет обнаружен. Таким образом, в средаем поиск требует времени, пропорпионального числу объектов в магазине. Этот метод часто бывает удобен для иеболыпого числа объектов, Кроме того, он имеет преимущества при компиляции языков с блочной структурой, так кзк, помимо старого объявления переменной, в таблицу можно поместить и новое. Когда блок занончен, все 27! гл. ш оеглнизвция инеогмвции ~вл твелипы имен Рвс. 1О.З.
Дерево хвовчвого поиска. хгв его объявления выталкиваются из магазина, а старые объявЛения переменных остаются. Третий метод, более быстрый, чем использование магазина, заключается в приыенении дерева дооичкоео поиска. В дереве двоичаого поиска у каждой вершины может быть левый прямой потомок и правей прямой потомок. Предполагается, что объекты данНых можно линейно упорядочить некоторым отношением например отношением „предшествовать в алфавитном порядке".
Объекты запоминаются как метки в вершинах дерева. Когда встречается первый объект, скажсы ао порождается корень, который помечается а,. Если а — следующий объект и а < в а, ао то к дереву добавляется лист, помеченный а„и он становится левым прямым потомком корпя. (Если а, < ом то этот лист становится правым прямым потомком.) Появление каждого нового объекта приводит н тому, что к дереву добавляется новый лист в такой познани, что дерево всегда обладает следующим свойством, Пусь Лг †верши дерева, помеченная й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
