|
оманды для создания компилятора, bas.exe, приведены ниже:yacc - d bas.y # create y.tab.h, y.tab.clex bas.l # create lex.yy.ccc lex.yy.c y.tab.c - obas.exe # compile/linkYacc читает грамматические описания в 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.
Страницы: 1, 2, 3, 4, 5
|
