Курсовая работа: Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода
Разница между этими двумя классами грамматик заключается лишь в том, что в УКС-грамматиках в правой части правил может присутствовать пустая цепочка (X), а в НКС-грамматиках – нет. Доказано, что эти два класса грамматик почти эквивалентны.
КС-грамматики широко используются при описании синтаксических конструкций языков программирования. Синтаксис большинства известных языков программирования основан именно на КС-грамматиках.
Внутри типа КС-грамматик кроме классов НКС и УКС выделяют еще целое множество различных классов грамматик, и все они относятся к типу 2.
Тип 3: регулярные грамматики
К типу регулярных относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
Леволинейные грамматики G (VT, VN, P, S), 
могут иметь правила двух
видов: 
или 
, где 
.
В свою очередь, праволинейные грамматики G (VT, VN,
P, S), 
могут иметь правила тоже двух видов: 
или 
, где
.
Эти два класса грамматик эквивалентны и относятся к типу регулярных грамматик.
Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т.д. Эти грамматики исключительно просты и удобны в использовании, поэтому в компиляторах на их основе строятся функции лексического анализа входного языка.
Соотношения между типами грамматик
Типы грамматик соотносятся между собой особым
образом. Из определения типов 2 и 3 видно, что любая регулярная грамматика
является КС-грамматикой, но не наоборот. Также очевидно, что любая грамматика
может быть отнесена к типу 0, поскольку он не накладывает никаких ограничений
на правила. В то же время существуют укорачивающие КС-грамматики (тип 2),
которые не являются ни контекстно-зависимыми, ни неукорачивающими (тип 1),
поскольку могут содержать правила вида 
,
недопустимые в типе 1.
Одна и та же грамматика в общем случае может быть отнесена к нескольким классификационным типам (например, как уже было сказано, все без исключения грамматики могут быть отнесены к типу 0). Для классификации грамматики всегда выбирают максимально возможный тип, к которому она может быть отнесена. Сложность грамматики обратно пропорциональна номеру типа, к которому относится грамматика.
Трансляторы
Формальное определение транслятора
Транслятор – это программа, которая переводит программу на исходном (входном) языке в эквивалентную ей программу на результирующем (выходном) языке.
С точки зрения преобразования предложений входного языка в эквивалентные им предложения выходного языка транслятор выступает как переводчик.
Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным – не содержит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная (содержит хотя бы одну ошибку), то результатом работы транслятора будет сообщение об ошибке.
Этапы трансляции. Общая схема работы транслятора
На рис. 2.1 представлена общая схема работы компилятора. Из нее видно, что в целом процесс компиляции состоит из двух основных этапов – анализа и синтеза. На этапе анализа выполняется распознавание текста исходной программы, создание и заполнение таблиц идентификаторов. Результатом его работы служит некое внутреннее представление программы, понятное компилятору. На этапе синтеза на основании внутреннего представления программы и информации, содержащейся в таблице идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код. Кроме того, в составе компилятора присутствует часть, ответственная за анализ и исправление ошибок, которая при наличии ошибки в тексте исходной программы должна максимально полно информировать пользователя о типе ошибки и месте ее возникновения. В лучшем случае компилятор может предложить пользователю вариант исправления ошибки.
Эти этапы, в свою очередь, состоят из более мелких этапов, называемых фазами компиляции. Состав фаз компиляции на рис. 2.1 приведен в самом общем виде, их конкретная реализация и процесс взаимодействия могут, конечно, различаться в зависимости от версии компилятора.
Компилятор в целом, с точки зрения теории формальных языков, выполняет две основные функции:
– распознавание языка исходной программы
– генерация результирующей программы на заданном языке.
Далее дается перечень основных фаз (частей) компиляции и краткое описание их функций.
Лексический анализатор (сканер) – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического разбора. С теоретической точки зрения лексический анализатор не является обязательной, необходимой частью компилятора. Однако существуют причины, которые определяют его присутствие практически во всех компиляторах.
Синтаксический анализатор – это основная часть компилятора на этапе анализа. Она выполняет выделение синтаксических конструкций в тексте исходной программы, обработанном лексическим анализатором. На этой же фазе компиляции проверяется синтаксическая правильность программы. Синтаксический разбор играет роль распознавателя текста входного языка программирования.
Семантический анализатор – это часть компилятора, проверяющая правильность текста исходной программы с точки зрения семантики входного языка. Кроме непосредственно проверки семантический анализ должен выполнять преобразования текста, требуемые семантикой входного языка (например, такие, как добавление функций неявного преобразования типов). В различных реализациях компиляторов семантический анализ может частично входить в фазу синтаксического разбора, частично – в фазу подготовки к генерации кода.
Подготовка к генерации кода – это фаза, на которой компилятором выполняются предварительные действия, непосредственно связанные с синтезом текста результирующей программы, но еще не ведущие к порождению текста на выходном языке. Обычно в эту фазу входят действия, связанные с идентификацией элементов языка, распределением памяти и т.п.
Генерация кода – это фаза, непосредственно связанная с порождением команд, составляющих предложения выходного языка и в целом текст результирующей программы. Это основная фаза на этапе синтеза результирующей программы. Кроме непосредственного порождения текста результирующей программы генерация обычно включает в себя также оптимизацию – процесс, связанный с обработкой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы.
Проход транслятора – процесс последовательного чтения компилятором данных из памяти, их обработки и помещёния результата в память. В компиляторе может быть реализовано несколько проходов, например проходы лексического и синтаксического анализатора. В некоторых случаях проходы могут быть объединены в один проход.
Интерпретаторы
Интерпретатор – программа, воспринимающая исходную программу на входном (исходном) языке и выполняющая ее.
Интерпретатор, также как и транслятор, анализирует текст исходной программы, но он не порождает результирующую программу, а сразу выполняет исходную в соответствии с ее смыслом, заданным семантикой ее языка.
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
Первая фаза в компиляторе – чтение входного исходного файла и его преобразование в токены. Используя регулярные выражения, мы можем специфицировать шаблоны для лексического анализа, и это позволит сгенерировать код, который позволит сканировать и найти совпадающие строки в исходном коде. Каждому шаблону специфицированному в исходном коде для лексического анализа, сопоставляется ассоциированное действие. Обычно действие возвращает токен, который представляет совпадающую строку, в последующем используемую синтаксическим анализатором. Сначала просто печатаем совпавшую строку, если возвращается значение токена.
Далее следует представление простого шаблона, составляющего регулярное выражение, которое ищет идентификаторы. Lex читает этот шаблон и создает C код для лексического анализатора, который ищет идентификаторы.
letter (letter|digit)*
Этот шаблон ищет строку символов, которая начинается с единичного символа, следующим за нулем или больше символов или цифр. Этот пример хорошо иллюстрирует, операции, разрешенные а регулярных выражениях:
• повторение, представленное оператором «*» (repetition)
• чередование, представленное оператором «|» (alternation)
• объединение (concatenation)
Любое регулярное выражение может быть представлено автоматом с конечным числом состояний (finite state automaton, FSA). Мы можем представить FSA, использующее состояния и переходы между состояниями. Существует одно начальное состояние и одно, или больше, конечных состояний или разрешенных состояний.
На рис. 3, состояние 0 – является начальным состоянием, а состояние 2 – разрешенным состоянием. Когда происходит чтение символа, осуществляется переход из одного состояния в другое. Когда читается первый символ, осуществляется переход в состояние 1. Автомат остается в состоянии 1, пока читаются буквы (letters) или цифры (digits). Когда осуществляется чтение иного символа, кроме буквы или символа, осуществляется переход в состояние 2, разрешенное состояние. Любой FSA может быть представлен с помощью компьютерной программы. Например, этот автомат с 3 мя состояниями программируется следующим образом:
start: goto state0
state0: read c
if c = letter goto state1
