Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода (стр. 4 из 7)
Lex
Theory
Первая фаза в компиляторе – чтение входного исходного файла и его преобразование в токены. Используя регулярные выражения, мы можем специфицировать шаблоны для лексического анализа, и это позволит сгенерировать код, который позволит сканировать и найти совпадающие строки в исходном коде. Каждому шаблону специфицированному в исходном коде для лексического анализа, сопоставляется ассоциированное действие. Обычно действие возвращает токен, который представляет совпадающую строку, в последующем используемую синтаксическим анализатором. Сначала просто печатаем совпавшую строку, если возвращается значение токена.
Далее следует представление простого шаблона, составляющего регулярное выражение, которое ищет идентификаторы. Lex читает этот шаблон и создает C код для лексического анализатора, который ищет идентификаторы.
letter (letter|digit)*
Этот шаблон ищет строку символов, которая начинается с единичного символа, следующим за нулем или больше символов или цифр. Этот пример хорошо иллюстрирует, операции, разрешенные а регулярных выражениях:
• повторение, представленное оператором «*» (repetition)
• чередование, представленное оператором «|» (alternation)
• объединение (concatenation)
Любое регулярное выражение может быть представлено автоматом с конечным числом состояний (finitestateautomaton, 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. Примеры шаблонов выражений (PatternMatchingExamples)
| Выражение (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):