1 Повтор того, что сказано до начала Шагов. — Примеч. Ред.
непосредственно с кодами команд результирующей программы. Дерево операций четко отражает связь всех операций между собой, поэтому его удобно использовать также для преобразований, связанных с перестановкой и переупорядочиванием операций без изменения конечного результата (таких, как арифметические преобразования). Более подробно эти вопросы рассмотрены в [5, 6, т. 2, 82].
Автоматизация построения синтаксических анализаторов (программа yacc)
При разработке различных прикладных программ часто возникает задача синтаксического разбора некоторого входного текста. Конечно, ее можно всегда решить, полностью самостоятельно построив соответствующий анализатор. И хотя задача выполнения синтаксического разбора встречается не столь часто, как задача выполнения лексического разбора, но все-таки и для ее решения были предложены соответствующие программные средства.
Автоматизированное построение синтаксических анализаторов может быть выполнено с помощью программы YACC.
Программа YACC (Yet Another Compiler Compiler) предназначена для построения синтаксического анализатора контекстно-свободного языка. Анализируемый язык описывается с помощью грамматики в виде, близком форме Бэкуса—Наура (нормальная форма Бэкуса—Наура — НФБН). Результатом работы YACC является исходный текст программы синтаксического анализатора. Анализатор, который порождается YACC, реализует восходящий LALR(I) распознаватель [5, 6, т. 1, 15, 65].
Как и программа LEX, служащая для автоматизации построения лексических анализаторов, программа YACC тесно связана с историей операционных систем типа UNIX. Эта программа входит в поставку многих версий OC UNIX или Linux. Поэтому чаще всего результатом работы YACC является исходный текст синтаксического распознавателя на языке C. Однако существуют версии YACC, выполняющиеся под управлением OC, отличных от UNIX, и порождающие исходный код на других языках программирования (например, Pascal).
Принцип работы YACC похож на принцип работы LEX: на вход поступает файл, содержащий описание грамматики заданного КС-языка, а на выходе получаем текст программы синтаксического распознавателя, который, естественно, можно дополнять и редактировать, как и любую другую программу на заданном языке программирования.
Исходная грамматика для YACC состоит из трех секций, разделенных символом %%, — секции описаний, секции правил, в которой описывается грамматика, и секции программ, содержимое которой просто копируется в выходной файл.
Например, ниже приведено описание простейшей грамматики для YACC, которая соответствует грамматике арифметических выражений, многократно использовавшейся в качестве примера в данном пособии:
Секция описаний содержит информацию о том, что идентификатор а является лексемой (терминальным символом) грамматики, а символ e — ее начальным нетерминальным символом.
Грамматика записана обычным образом — идентификаторы обозначают терминальные и нетерминальные символы; символьные константы типа '+' и '-' считаются терминальными символами. Символы :, |, ; принадлежат к метаязыку YACC и читаются согласно НФБН «есть по определению», «или» и «конец правила» соответственно.
B отличие от LEX, который всегда способен построить лексический распознаватель, если входной файл содержит правильное регулярное выражение, YACC не всегда может построить распознаватель, даже если входной язык задан правильной КС-грамматикой. Ведь заданная грамматика может и не принадлежать к классу LALR(I). B этом случае YACC выдаст сообщение об ошибке (наличии неразрешимого LALR(I) конфликта в грамматике) при построении синтаксического анализатора. Тогда пользователь должен либо преобразовать грамматику, либо задать YACC некоторые дополнительные правила, которые могут облегчить построение анализатора. Например, YACC позволяет указать правила, явно задающие приоритет операций и порядок их выполнения (слева направо или справа налево).
C каждым правилом грамматики может быть связано действие, которое будет выполнено при свертке по данному правилу. Оно записывается в виде заключенной в фигурные скобки последовательности операторов языка, на котором порождается исходный текст программы распознавателя (обычно это язык C). Последовательность должна располагаться после правой части соответствующего правила. Также YACC позволяет управлять действиями, которые будут выполняться распознавателем в том случае, если входная цепочка не принадлежит заданному языку. Распознаватель имеет возможность выдать сообщение об ошибке, остановиться либо же продолжить разбор, предприняв некоторые действия, связанные с попыткой локализовать либо устранить ошибку во входной цепочке.
Более подробные сведения о программе автоматизированного построения синтаксических распознавателей YACC можно получить в [5, 11, 39, 68].
Контрольные вопросы и задачи
Вопросы
Что такое трансляция, компиляция, транслятор, компилятор? Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.
2. Какую роль выполняет лексический анализ в процессе компиляции? Как могут быть связаны между собой лексический и синтаксический анализ?
3. Компилятор можно построить, не используя лексический анализатор. Объясните, почему все-таки подавляющее большинство современных компиляторов используют фазу лексического анализа.
4. Постройте общую схему работы интерпретатора. B чем ее отличие от общей схемы работы компилятора, приведенной в этом пособии?
5. Постройте общую схему работы компилятора с языка ассемблера. Какие особенности присущи данному компилятору? Какие фазы компиляции в нем могут отсутствовать?
6. От чего зависит количество проходов, необходимых компилятору для построения результирующей объектной программы на основе исходной программы? Как влияют на необходимое количество проходов синтаксис исходного языка программирования, семантика этого языка, архитектура целевой вычислительной системы?
7. Почему в глобальной сети Интернет используются в основном языки программирования, предусматривающие интерпретацию исходного кода? Какие проблемы проистекают из этого факта?
8. Почему для языка ассемблера, который имеет простую (часто — регулярную) грамматику, чаще всего используется двухпроходный компилятор? Что мешает свести компиляцию исходного кода на языке ассемблера в один проход?
9. Зачем в описании макрокоманды <<#define f2(a) ((a) + (а))» параметр «а» взят в скобки, хотя операция этого не требует?
10. Что такое таблица идентификаторов и для чего она предназначена? Какая информация может храниться в таблице идентификаторов?
11. Какие цели преследуются при организации таблицы идентификаторов? Исходя из каких характеристик оценивается эффективность того или иного метода организации таблицы?
12. Какие существуют способы организации таблиц идентификаторов?
13. Что такое коллизия? Почему она происходит при использовании хэш-функций для организации таблиц идентификаторов? B чем заключаются преимущества и недостатки метода цепочек?
14. Метод логарифмического поиска позволяет значительно сократить время поиска идентификатора в таблице. Однако он же значительно увеличивает время на помещение нового идентификатора в таблицу. Почему тем не менее можно говорить о преимуществах этого метода по сравнению с поиском методом прямого перебора?
15. Проблемы создания хорошей хэш-функции связаны с ограниченной разрядной сеткой компьютера и, следовательно, ограниченным размером доступного адресного пространства. Ho, как сказано в первой части данного учебного пособия, размер адресного пространства можно увеличить, используя внешние накопители данных (прежде всего, жесткие диски) и механизм виртуальной памяти. Почему эти возможности не используются компиляторами при организации хэш-функций?
16. Как могут быть скомбинированы различные методы организации таблиц идентификаторов?
17. Чем различаются таблица лексем и таблица идентификаторов? B какую из этих таблиц лексический анализатор не должен помещать ключевые слова разделители и знаки операций?
18. Какие проблемы необходимо решить при построении сканера на основе конечного автомата? Чем отличается функционирование лексического анализатора в составе компилятора от работы обычного KA?
19. B чем различия между деревом вывода и деревом операций, если и то и другое получается в результате синтаксического разбора?
Задачи
1. B программе на языке C макрокоманда Incl(a,b) и функция Inc2(a,b), выполняющие действие a+2*b, описаны следующим образом:
B каких из перечисленных случаев будет получен логически неверный результат?
2. Изменится ли результат, полученный при выполнении макрокоманды Incl(a,b) из предыдущей задачи, если ее определение будет дано следующим образом:
ldefine Incl(a.b) ((a) + (2*(b)))
Приведет ли это к логически правильным результатам во всех вышеприве денных случаях?
Будет ли верным следующее определение макрокоманды:
#define Incl(a.b) ((a) + (2*b))
Если оно содержит ошибку, укажите, в каком случае выполнение данной макрокоманды даст неверный результат.
3. Напишите программу на языке Pascal или C, реализующую метод логарифмического поиска в упорядоченном массиве строк. B качестве исходных данных для заполнения массива возьмите любой текстовый файл, считая, что все слова в нем являются идентификаторами.
4. Напишите программу на языке Pascal или C, реализующую метод построение бинарного дерева. Используйте динамические структуры данных для организации дерева. B качестве исходных данных для заполнения дерева возьмите любой текстовый файл, считая, что все слова в нем являются идентифика торами. Проверьте эффективность метода на случайных текстовых файлах а также попробуйте в качестве источника данных файл с упорядоченным тек стом.
5. Напишитепрограмму на языке Pascal или C, создающую таблицу идентификаторов с помощью хэш-функций на основе метода простого рехеширования. B качестве исходных данных для заполнения дерева возьмите любой текстовый файл, считая, что все слова в нем являются идентификаторами. Организуйте программу таким образом, чтобы в ней можно было бы легко подменять используемую хэш-функцию. Подсчитывая число коллизий и среднее количество сравнений для поиска идентификатора, сравните результаты для различных хэш-функций. B качестве исходных данных для хэш-функции можно предложить:
--- коды первых двух букв идентификатора;
--- коды последних двух букв идентификатора;
--- код первой и код последней букв идентификатора;
--- коды первой, последней и средней букв идентификатора.
6. Выполните действия, описанные в задаче № 5, для таблицы идентификаторов, организованной на основе метода цепочек. Сравните результаты.
7. B языке C++ возможны два типа комментариев: обычный комментарий, ограниченный символами «/*» и «*/», и строчный комментарий, начинающийся с символов «//» и заканчивающийся концом строки. Постройте сканер, который бы находил и исключал из входного текста все комментарии языка C++.
8. Постройте сканер, который выделял бы из текста входной программы на языке Borland Pascal все содержащиеся в ней строковые константы и записывал их в отдельный файл. Строковые константы в языке Pascal состоят из строк, одиночных символов и кодов символов, которые могут быть объединены между собой знаком «+>>. Строки ограничены символами "" (двойные кавычки), одиночные символы — символами '' (одинарные кавычки), а коды символов начинаются со знака # (диез) и содержат цифры1.
9. Даны две грамматики (см. задачи к предыдущей главе):
1 Следует заметить, что эта задача отнюдь не так проста, как может показаться. Программа должна уметь не только находить в исходном тексте строки и объединять их между собой, но и правильно игнорировать комментарии (которых в языке Pascal два типа). Поэтому лучше сначала корректно описать грамматику, а потом на ее основе построить автомат. Автор непосредственно имел опыт постановки задачи построения такого сканера, причем без предварительной теоретической работы программа сканера представляла собой плохо работающий набор из многочисленных заплаток.
Постройте для каждой из них цепочку вывода для цепочки символов: «аАа&~а&(аА~~а)>>, постройте деревья вывода для каждой из полученных цепочек символов. Преобразуйте полученные деревья вывода в дерево операций. Проделайте то же самое для других цепочек, допустимых в языке, заданном этими грамматиками.