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

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

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

Генерация кода – это фаза, непосредственно связанная с порождением команд, составляющих предложения выходного языка и в целом текст результирующей программы. Это основная фаза на этапе синтеза результирующей программы. Кроме непосредственного порождения текста результирующей программы генерация обычно включает в себя также оптимизацию – процесс, связанный с обработкой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы.

Проход транслятора – процесс последовательного чтения компилятором данных из памяти, их обработки и помещёния результата в память. В компиляторе может быть реализовано несколько проходов, например проходы лексического и синтаксического анализатора. В некоторых случаях проходы могут быть объединены в один проход.

Интерпретаторы

Интерпретатор – программа, воспринимающая исходную программу на входном (исходном) языке и выполняющая ее.

Интерпретатор, также как и транслятор, анализирует текст исходной программы, но он не порождает результирующую программу, а сразу выполняет исходную в соответствии с ее смыслом, заданным семантикой ее языка.

Lex и Yacc

Обзор генераторов кода

Системы GNU/Linux поставляются с несколькими программами для написания программ. Возможно наиболее популярны:

· Flex, генератор лексического анализатора

· Bison, генератор синтаксического анализатора

· Gperf, развитый генератор хэш-функции

Эти программы генерируют тексты для языка C. Вы можете удивиться, почему они реализованы в виде генераторов кода, а не в виде функций. Тому есть несколько причин:

· Входные параметры для этих функций являются очень сложными и их непросто выразить в виде, корректном для C-кода.

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

· Многие аспекты функционирования этих систем настраиваются произвольным кодом, помещаемым на отдельные позиции. Этот код может впоследствии использовать переменные и функции, являющиеся частью сгенерированной структуры, построенной генератором кода, без необходимости определять и извлекать все переменные вручную.

Каждое из этих инструментальных средств предназначено для создания конкретного типа программ. Bison используется для генерирования синтаксических анализаторов; Flex – для генерирования лексических анализаторов. Другие средства посвящены, в основном, автоматизации конкретных аспектов программирования.

Например, интегрирование методов доступа к базе данных в императивные языки программирования часто является рутинной работой. Для ее облегчения и стандартизации предназначен Embedded SQL – система метапрограммирования, используемая для простого комбинирования доступа к базе данных и C.

Хотя существует немало доступных библиотек, позволяющих обращаться к базам данных в C, использование такого генератора кода как Embedded SQL делает комбинирование C и доступа к базе данных намного более легким путем объединения SQL-сущностей в C в качестве расширения языка. Многие реализации Embedded SQL, однако, в основном являются простыми специализированными макропроцессорами, генерирующими обычные C-программы. Тем не менее, использование Embedded SQL делает для программиста доступ к базе данных более естественным, интуитивным и свободным от ошибок по сравнению с прямым использованием библиотек. При помощи Embedded SQL запутанность программирования баз данных маскируется макроязыком

Совместное использование Lex и Yacc

До 1975 года процесс написания компиляторов занимал очень много времени. Затем Lesk[1975] и Johnson[1975] опубликовали труды по lex и yacc. Эти утилиты сильно упростили написание компиляторов. Детали реализации могут быть найдены у Aho[1986]

Шаблоны кода помещаются на вход Lex. Lex читает шаблоны и генерирует C код для лексического анализатора или сканера.

Лексический анализатор ищет совпадение строк во входных данных, основываясь на заданных шаблонах, и преобразует строки в токены.

Токены являются числовым представлением строк упрощающим обработку.

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

Код грамматики подаются на вход yacc. Yacc читает грамматику и генерирует C код для синтаксического анализатора или разборщика. Синтаксический анализатор использует грамматические правила, которые позволяют ему анализировать токены из лексического анализатора и создать синтаксическое дерево. Синтаксическое дерево устанавливает иерархичскую структуру токенов. Например, оператор precedence и ассоциативности (associativity) показаны в синтаксическом дереве. Следующий шаг, генерация кода, осуществляется с помощью обхода синтаксического дерева. Некоторые компиляторы создают машинный код, когда как некоторые – программу на языках ассемблера.

Команды для создания компилятора, bas . exe , приведены ниже:

yacc – d bas.y # create y.tab.h, y.tab.c

lex bas.l # create lex.yy.c

cc lex.yy.c y.tab.c – obas.exe # compile/link

Yacc читает грамматические описания в bas . y и генерирует синтаксический анализатор (parser), который включает функцию yyparse , в файле y . tab . c . Файл bas . y содержит в себе объявления токенов. Включение опции – d ведет к тому, что yacc генерирует определения для токенов и помещает их в файл y . tab . h . Lex читает шаблоны, описанные в bas . l , включающие файл y . tab . h и генерирует лексический анализатор, который включает функцию yylex , в файле lex . yy . c . Наконец, лексический анализатор (lexer) и синтаксический анализатор (parser) компилируются и компонуются вместе, образуя исполняемый файл bas . exe . Из main , мы вызываем yyparse , чтобы запустить компилятор. Функция yyparse автоматически вызываетyylex , чтобы получить каждый токен.

Lex

Theory