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

Системы 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)

Метасимвол (Metacharacter)	Совпадения (Matches)
.	Любой символ, кроме перевода строки
\n	Символ перевода строки
*	0 или более копий предшествующих выражений
+	1 или более копий предшествующих выражений
?	0 или 1 копия предшествующих выражений
^	Начало строки
$	Конец строки
a|b	a или b
(ab)+	Одна или более копий ab (группировка, grouping)
«a+b»	литерал «a+b» (C escapes still work)
[]	Класс символов

 

Таблица 2. Примеры шаблонов выражений (Pattern Matching Examples)

Выражение (Expression)	Совпадения (Matches)
abc	abc
abc*	ab abc abcc abccc…
abc+	abc abcc abccc…
a(bc)+	abc abcbc abcbcbc…
a(bc)?	a abc
[abc]	Одно из: a, b, c
[a-z]	Любой символ, a-z
[a\-z]	Одно из: a, -, z
[-az]	Одно из: -, a, z
[A-Za-z0–9]+	Один или более символов алфавита или цифр
[\t\n]+	Пробельные символы
[^ab]	Все, кроме: a, b
[a^b]	Одно из: a, ^, b
[a|b]	Одно из: a, |, b
a|b	Одно из: a, b

 

Регулярные выражения в 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 правильно функционирует.

 

Name	Function
int yylex(void)	Вызывается для запуска лексического анализатора, возвращает токен
char *yytext	Указатель на совпавшую строку
yyleng	Длина совпавшей строки
yylval	Значение, ассоциируемое с токеном
int yywrap(void)	Wrapup – обертка возвращает 1 – если завершена, 0 – если не завершено
FILE *yyout	Выходной файл
FILE *yyin	Входной файл
INITIAL	Исходное условие старта
BEGIN	Условие переключающее условие старта
ECHO	Записать совпавшую строку

 

Следующий пример присоединяет слева номер линии для каждой линии в файле. Некоторые реализации 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.