Обзор генераторов кода
Системы 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 Goto state0 State1: read c if c = letter goto state1 if c = digit goto state1 Goto state2 State2: accept string Это техника, используемая lex. Регулярные выражения транслируются с помощью lex в компьютерную программу, которая реализует FSA. Используя следующий входной символ и текущее состояние, следующее состояние определяется с помощью индексирования в сгенерированной компьютером таблице состояний. Теперь становится легко понять ограничения в lex. Например, lex не может быть использован.
Таблица 1. Элементарные шаблоны (Pattern Matching Primitives)
Таблица 2. Примеры шаблонов выражений (Pattern Matching Examples)
Регулярные выражения в lex составляются из метасимволов (Таблица 1). Примеры совпадения шаблонов показаны в таблице 2. При использовании класса символов, обычные операторы теряют свое назначение. Следующие два оператора разрешены в классе символов: дефис («–», hyphen) и циркумфлекс («^», circumflex). При использовании между двумя символами дефиса, представляется диапазон символов. Циркумфлекс, при использовании его как первого символа, отрицает выражение. Если два шаблона совпадают с некоторой строкой, используется наиболее шаблон, по которому найдена наиболее длинная строка, в случае, если длина одинакова, используется первый шаблон. … definitions… %% … rules… %% … subroutines… Входные данные lex делятся на 3 секции, с символами%%, разделяющими секции. Это проиллюстрировано в примере. Первый пример – это наименьший возможный файл lex: %% Входные данные копируются выходные по одному символу за раз. Первый разделитель%% требуется всегда, так как всегда должна быть секция правил. Если не специфицировать ни одного правила, тогда действие по умолчанию – совпадение всего и копирование в выходные данные. По умолчанию для входных и выходных данных используются stdin и stdout, соответственно. Вот некоторый пример, с использованием кода по умолчанию: %% /* Совпадение всего, кроме символа новой строки */ ECHO ; /* Совпадение символа перевода строки */ \n ECHO; %% int yywrap(void) { return 1; } int main(void) { yylex(); return 0; } Два шаблона специфицированы в секции правил. Каждый шаблон должен начинаться в первом столбце, то есть должен следовать за пробельным символом. Опциональное действие ассоциируется с шаблоном. Действие может быть единичным выражением на языке C или множественным, заключенным в скобки. Все, не начинающееся с первого столбца, дословно копируется в генерируемый C файл. Можно использовать это для спецификации комментариев в lex файле. В этом примере есть 2 выражения: «.» и «\ n» с действием ECHO, ассоциированным с каждым шаблоном. Несколько макросов и переменных определены в lex. ECHO – это макрос, который пишет код, совпадающий с шаблоном. Это действие по умолчанию для каждой несовпадающей строки. Обычно ECHO определяется как #define ECHO fwrite (yytext, yyleng, 1, yyout) Переменная yytext – указатель на совпавшую строку (оканчивающийся NULL-символом), и yyleng – длина совпавшей строки. Выражение yyout является выходным файлом и по умолчанию является stdout. Функция yywrap вызывается lex, когда входные данные закончились. Возвращает 1, если закончено, 0 если требуется дальнейшая обработка. Каждая программа на C требует main функцию. В этом случае просто вызывается yylex, Основная точка входа для lex. Некоторые реализации lex включают копии main и yywrap в библиотеку, устраняя необходимость явно определять их. Поэтому первый пример, наименьшая программа lex правильно функционирует.
Следующий пример присоединяет слева номер линии для каждой линии в файле. Некоторые реализации lex предопределяют вычисление yylineno. Входной файл для lex – это yyin, и является по умолчанию stdin. %{ Int yylineno; %} %% ^(.*)\n printf («%4d\t % s», ++yylineno, yytext); %% int main (int argc, char *argv[]) { yyin = fopen (argv[1], «r»); Yylex(); Fclose ( yyin ); } Секции определений состоят из замен, кода и начальных состояний. Код в секциях определения просто копируется в начало генерируемого C файла, при этом код должен быть в скобках%{» и «%}». Замены облегчаются правилами совпадения шаблонов. Например, можно определить цифры и символы: digit [0–9] letter [A-Za-z] %{ int count; %} %% /* match identifier */ {letter} ({letter}|{digit})* count++; %% int main(void) { yylex(); printf («number of identifiers =%d\n», count); return 0; } Пробел должен разделять терм и ассоциируемое выражение. Ссылки на подстановки в секциях правил окружены скобками ({ letter }), чтобы различать их с символами. Когда происходит совпадение в секции правил, ассоциируемый C код выполняется. Вот программа, которая считает количество символов, слов и линий в файле (подобная команде wc в Unix): %{ int nchar, nword, nline; %} %% \n {nline++; nchar++;} [^ \t\n]+ {nword++, nchar += yyleng;} {nchar++;} %% int main(void) { yylex(); printf («%d\t % d\t % d\n», nchar, nword, nline); return 0; } Реализация lex в Unix В целом подсистема LEX для систем UNIX включает следующие файлы: /usr/ccs/bin/lex;lex.yy.c;/usr/ccs/lib/lex/ncform;/usr/lib/libl.a;/usr/lib/libl.so.В каталоге /usr/ccs/lib/lex имеется файл-заготовка ncform, который LEX используется для построения ЛА. Этот файл является уже готовой программой лексического анализа. Но в нем не определены действия, которые необходимо выполнять при распознавании лексем, отсутствуют и сами лексемы, не сформированы рабочие массивы и т.д. С помощью команды lex файл ncform достраивается. В результате мы получаем файл со стандартным именем lex.yy.c. Если LEX-программа размещена в файле program.l, то для получения ЛА с именем program необходимо выполнить следующий набор команд: lex program.lcc lex.yy.c – ll – o programЕсли имя входного файла для команды lex не указано, то будет использоваться файл стандартного ввода. Флаг – ll требуется для подключения /usr/ccs/lib/libl.a – библиотеки LEX. Если необходимо получить самостоятельную программу, как в данном случае, подключение библиотеки обязательно, поскольку из нее подключается главная функция main. В противном случае, если имеется необходимость включить ЛА в качестве функции в другую программу (например, в программу синтаксического анализа), эту библиотеку необходимо вызвать уже при сборке. Тогда, если main определен в вызывающей ЛА программе, редактор связей не будет подключать раздел main из библиотеки LEX. Общий формат вызова команды lex: lex [-ctvn – V – Q [y|n]] [file]Флаги: – c – включает фазу генерации Си-файла (устанавливается по умолчанию); – t – поместить результат в стандартный файл вывода, а не в файл lex.yy.c; – v – вывести размеры внутренних таблиц; – n – не выводить размеры таблиц (устанавливается по умолчанию); – V – вывести информацию о версии LEX в стандартный файл ошибок; – Q – вывести (Qy) либо не выводить (Qn, устанавливается по умолчанию) информацию о версии в файл lex.yy.c.
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (316)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |