Курсовая работа: Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода
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.l
cc 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.
YACC – Yet Another Compiler Compiler
Грамматики для yacc описываются с помощью Формы Бэкуса-Наура (Backus Naur Form, BNF)
Эту технику была ввели John Backus и Peter Naur и использовали ее, чтобы описать ALGOL60. Грамматика BNF может быть использована для описания контекстно-свободных языков. Большинство конструкций современного программирования могут быть представлены в BNF.
Например, грамматика для выражения, которое умножает и складывает числа может быть представлена следующим образом:
E -> E + E
E -> E * E
E -> id
Были специфицированы 3 правила продукции. Термы, которые могут быть с левой стороны правил продукции(lhs) продукции, такие как E (expression), являются нетерминальными символами. Термы, такие как id (identifier) являются терминальными символами (токенами, возвращаемыми lex) и могут быть только с правой стороны правил продукции(rhs).
