2.Лексический анализатор
Лексический анализатор (англ. lexical analyzer, lexer; или «токенизатор» от tokenizer) — это программа или часть программы, выполняющая лексический анализ. Лексический анализатор обычно работает в две стадии: сканирование и оценка.
Схема лексического анализатора
На первой стадии, сканировании, лексический анализатор обычно реализуется в виде конечного автомата, определяемого регулярными выражениями. В нём кодируется информация о возможных последовательностях символов, которые могут встречаться в токенах . Например, токен «целое число» может содержать любую последовательность десятичных цифр. Во многих случаях первый непробельный символ может использоваться для определения типа следующего токена, после чего входные символы обрабатываются один за другим пока не встретится символ, не входящий во множество допустимых символов для данного токена. В некоторых языках правила разбора лексем несколько более сложные и требуют возвратов назад по читаемой последовательности.
Полученный таким образом токен содержит необработанный исходный текст (строку). Для того чтобы получить токен со значением, соответствующим типу (напр. целое или дробное число), выполняется оценка этой строки — проход по символам и вычисление значения.
Токен с типом и соответственно подготовленным значением передаётся на вход синтаксического анализатора
Генераторы лексических анализаторов
Lex — программа для генерации лексических анализаторов, обычно используемая совместно с генератором синтаксических анализаторов yacc. Lex был первоначально написан Эриком Шмидтом (Eric Schmidt) и Майком Леском (Mike Lesk) и является стандартным генератором лексических анализаторов в операционных системах Unix, а также включён в стандарт POSIX. Lex читает входной поток, описывающий лексический анализатор, и даёт на выходе исходный код на языке программирования C.
Структура lex-файла сделана подобно структуре yacc-файла; файл разделяется на три блока, разделённые строками, содержащими два символа процента:
Блок определений
%%
Блок правил
%%
Блок кода на Си
В блоке определений задаются макросы и заголовочные файлы. Здесь также допустимо писать любой код на Си — он будет скопирован в результирующий файл.
Блок правил — наиболее важная часть; она описывает шаблоны и ассоциирует их с вызовами. Шаблоны представляют собой регулярные выражения. Когда анализатор видит текст, подходящий под шаблон, он выполняет указанный код.
Блок кода содержит операторы и функции на Си, которые копируются в генерируемый файл. Предполагается, что эти операторы содержат код, вызываемый правилами из предыдущего блока. Для сложных анализаторов бывает более удобно поместить этот код в отдельный файл, подключающийся на стадии компиляции.
Flex (Fast Lexical Analyzer) — генератор лексических анализаторов. Заменяет Lex в системах на базе пакетов GNU и имеет аналогичную функциональность. При этом Flex не является частью проекта GNU.
Использование
На входе программа получает текст в свободном формате и правила выделения лексем, а на выходе даёт код анализатора, в виде функции на языке Си.[7]
Правила задаются в виде регулярных выражений слева и, обычно, кода на языке Си справа. Они содержат три секции, отделяющиеся строкой «%%»:
Блок определений
%%
Блок правил
%%
Блок кода на Си
Определения содержат стартовые значения и определения, правила, непосредственно сами выражения и соответствующие им действия; пользовательский код просто включается в вывод flex. Некоторые секции могут отсутствовать.
Функция анализатора получает текст на входе и выполняет заданный код для каждой найденной лексемы. Например, данный код для каждого вхождения username в тексте выполнит printf(«%s», getlogin()):
%%
username printf( "%s", getlogin() );
Данная функция выведет в поток строку, возвращаемую функцией getlogin(). То есть, каждое вхождение username во входном потоке будет заменено значением, возвращаемым getlogin().
Правила, согласно которым итоговая функция должна печатать на выходе тип лексемы (if, переменная, число, унарная или бинарная операция) и значения для некоторых лексем:
if printf ("IF statement\n");
[a-z]+ printf ("tag, value %s\n", yytext);
{D}+ printf ("decimal number %s\n", yytext);
"++" printf ("unary op\n");
"+" printf ("binary op\n");
Пример подсчёта количества строк и символов в тексте:
%{
int num_lines = 0, num_chars = 0;
%}
%%
\n++ ++num_lines; ++num_chars;
. ++num_chars;
%%
main()
{
yylex();
printf( "# of lines = %d, # of chars = %d\n", num_lines, num_chars );
}
Функцию, созданную генератором для поиска следующей лексемы, можно использовать с генераторами синтаксических анализаторов. В большинстве случаев flex используется с yacc или GNU bison.
JLex — свободно распространяемый генератор лексических анализаторов для языка программирования Java на основе анализатора Lex. Написан на языке Java. JLex был разработан Эллиотом Берком в Принстонском Университете. Последняя версия — 1.2.6, обновлённая 7 февраля 2003 года.
JLex может быть использован в комбинации с генератором синтаксических анализаторов CUP.