Для того чтобы программа могла обрабатывать вводимые данные в интерактивном
или пакетном режиме, необходимо разработать процедуру или дополнительную
программу, которая будет обрабатывать входной поток. Если ввод сложный,
то требуется дополнительный модуль для разбиения ввода на фрагменты,
интерпретируемые программой как отдельные, независимые данные. Для
разработки таких программ ввода можно применять команды lex и
yacc.
Команда lex помогает
создать программу на языке C, которая может получать поток символов и
преобразовывать его в действия программы. Для использования команды
lex необходим файл спецификаций, который содержит:
Формат этого файла и допустимая логика описаны в разделе Файл спецификаций lex описания команды lex.
Команда lex создает программу на языке C, которая может анализировать входной поток на основе информации, заданной в файле спецификаций. Команда lex создает программу в файле lex.yy.c. Если полученная программа применяется для распознавания простого ввода, в котором команде соответствует одно слово, вы можете скомпилировать файл lex.yy.c и получить исполняемую программу-лексический анализатор:
cc lex.yy.c -ll
Если программа должна распознавать более сложный синтаксис, потребуется разработать синтаксический анализатор который будет отвечать за обработку ввода совместно с лексическим анализатором. Дополнительная информация по этому вопросу приведена в разделе Создание синтаксического анализатора с помощью программы yacc.
Файл lex.yy.c может быть откомпилирован в любой системе, компилятор C которой поддерживает библиотечные функции lex.
Откомпилированный лексический анализатор выполняет следующие операции:
Лексический анализатор, создаваемый командой lex, применяет метод анализа, называемый детерминированным конечным автоматом. Этот метод задает ограниченное число состояний лексического анализатора и определяет правила, согласно которым устанавливается состояние анализатора.
Автомат применяет опережающий просмотр более чем на один или два символа вперед. Предположим, например, что в файле спецификаций lex определено два правила: одно распознает строку ab, а другое - строку abcdefg. Если лексический анализатор получает на вход строку abcdefh, он считывает все символы до конца строки, а затем определяет, что строка не совпадает с abcdefg. После этого он возвращается к правилу, соответствующему строке ab, определяет, что оно соответствует части входной строки, обрабатывает его и начинает анализ оставшейся строки - cdefh.
Определение расширенных регулярных выражение в файле спецификаций lex похоже на способы, применяемые в командах sed и ed. Расширенное регулярное выражение определяет набор строк для сравнения. Выражение содержит как текстовые символы, так и символы операторов. Текстовые символы сравниваются с символами во входной строке. Операторы задают повторы, операции выбора и другие операции.
Цифры и буквы алфавита считаются текстовыми символами. Например, расширенное регулярное выражение integer соответствует строке integer, а выражение a57D - строке a57D.
Ниже приведено описание
операторов, которые могут применяться при определении расширенных регулярных
выражений:
| Выражение | Применение |
| Символ | Соответствует символу Символ.
Пример:a соответствует символу a; b соответствует символу b, c соответствует символу c. |
| "строка" | Соответствует строке, заключенной в кавычки; операторы внутри строки
не учитываются.
Пример: для того чтобы команда lex не интерпретировала $ (символ доллара) как оператор, заключайте его в кавычки. |
| \символ или \цифры | Escape-символ. Если символ \ расположен перед
символьным оператором в строке, это означает, что символ оператора должен
интерпретироваться как литерал, а не как оператор. В число допустимых
escape-символов входят:
Пример:\c интерпретируется как символ c, а [\^abc] обозначает класс символов, включающий символы ^abc.
Примечание: Не используйте символы \0 и \x0 в правилах lex. |
| [список] | Соответствует любому символу из указанного диапазона
([x-y]) или списка
([xyz]), с учетом локали, в которой
выполняется команда lex. Все операторы, кроме перечисленных
далее, интерпретируются как символы при указании в квадратных скобках:
- (дефис), ^ (знак вставки) и \ (обратная
косая черта).
Пример:[abc-f] соответствует символам a, b, c, d, e и f в локали En_US. |
| [:класс:] | Соответствует любому символу, принадлежащему классу, указанному в
ограничителях [::], в соответствии с категорией LC_TYPE
текущей локали. Следующие имена классов поддерживаются во всех
локалях:
alnum cntrl lower space alpha digit print upper blank graph punct xdigit Команда lex поддерживает также пользовательские классы символов. Оператор [::] может применяться только в выражении []. Пример:[[:alpha:]] соответствует любому символу из класса символов alpha текущей локали, однако [:alpha:] соответствует только символам :,a,l,p и h. |
| [.составной-символ.] | Соответствует составному символу, указанному в ограничителях
[..], и рассматривается как один символ.
Оператор [..] может применяться в выражении
[ ]. Составной символ должен быть допустимым
составным символом в текущей локали.
Пример:[[.ch.]] соответствует символам c и h вместе, в то время как [ch] соответствует c или h. |
| [=эквивалентный-элемент=] | Соответствует элементу, указанному в ограничителях [==] и всем
элементам того же класса эквивалентности. Оператор [==]
может применяться только в выражении [].
Пример: Если w и v относятся к одному классу эквивалентности, [[=w=]] совпадает с [wv] и соответствует w и v. Если w не принадлежит классу эквивалентности, [[=w=]] соответствует только w. |
| [^символ] | Соответствует любому символу за исключением символа, следующего за
символом ^ (знаком вставки). Результирующий класс символов
содержит только однобайтовые символы. Символ, следующий за
^, может быть и многобайтовым, но для этого в разделе определений
%h и %m должны быть больше нуля.
Пример:[^c] соответствует любому символу, кроме c. |
| элемент-элемент | |
| В классе символов определяет диапазон символов в соответствии с последовательностью упорядочения текущей локали. Диапазоны должны указываться в возрастающем порядке. Порядковый номер конечного символа должен быть большим или равным номеру начального. В связи с тем, что диапазон зависит от текущей локали, фиксированный диапазон может соответствовать разным наборам символов, в зависимости от того, в какой локали запущена команда lex. | |
| выражение? | Соответствует не более чем одному вхождению выражения, расположенного
перед оператором ?.
Пример:ab?c соответствует ac и abc. |
| . | Соответствует любому символу, кроме символа новой строки. Для использования . с многобайтовыми символами значение %z в разделе определений файла спецификаций lex должно быть больше 0. Если %z не установлено, то . соответствует только однобайтовым символам. |
| выражение* | Соответствует нескольким возможным вхождениям выражения, расположенного
непосредственно перед оператором *. Например, a*
соответствует любому числу символов a, включая ни одного
символа. Возможность не указывать ни одного символа полезна в более
сложных выражениях.
Пример: выражение [A-Za-z][A-Za-z0-9]* обозначает все алфавитно-цифровые строки, начинающиеся с буквы, включая однобуквенные строки. Это выражение может использоваться для распознавания идентификаторов в языках программирования. |
| выражение+ | Соответствует ненулевому числу вхождений выражения, расположенного
непосредственно перед оператором +.
Пример: a+ соответствует одному или нескольким вхождениям a. [a-z]+ соответствует всем строкам, состоящим из прописных букв. |
| выражение|выражение | Обозначает соответствие одному из выражений слева или справа от оператора
| (конвейер).
Пример:ab|cd соответствует ab и cd. |
| (выражение) | Соответствует выражению в скобках. Оператор () (скобки)
применяется для группировки и помещает выражение в скобках в массив
yytext. Группа, указанная в скобках, может применяться
вместо любого отдельного символа в других конструкциях.
Пример:(ab|cd+)?(ef)* соответствует таким строкам, как abefef, efefef, cdef и cddd, но не соответствует строкам abc, abcd и abcdef. |
| ^выражение | Соответствует выражению, при условии, что оператор ^ (знак
вставки) находится в начале строки, и ^ является первым символом
выражения.
Пример:^h соответствует h в начале строки. |
| выражение$ | Соответствует выражению, при условии, что $ (символ доллара)
находится в конце строки и $ является последним символом
выражения.
Пример: Описание выражение/выражение. |
| выражение-1/выражение-2 | Соответствует выражению-1, при условии, что выражение-2
следует непосредственно за выражением-1. Оператор
/ (косая черта) помещает в массив yytext только первое
выражение.
Пример: ab/cd соответствует строке ab при условии, что за ней идет строка cd, при этом ab считывается в массив yytext.
Примечание: В одном расширенном регулярном выражении может применяться только один оператор завершающего контекста /. Операторы ^ (знак вставки) и $ (знак доллара) не могут применяться в одном выражении с оператором /, так как они обозначают особые случаи завершающего контекста. |
| {определенное-имя} | Соответствует имени, заданному в разделе определений.
Пример: Если вы определили D как класс цифр, то {D} соответствует любой цифре. |
| {число-1,число-2} | Соответствует от число-1 до число-2 вхождений
набора символов, расположенного непосредственно перед оператором.
Допустимо использование выражения {Число} и
{Число,} для указания точного количества
вхождений, равного Число.
Пример:xyz{2,4} соответствует xyzxyz, xyzxyzxyz и xyzxyzxyzxyz. Отличие от операторов +, * и ? состоит в том, что они относятся только к одному символу, расположенному перед оператором. Для того, чтобы выражение относилось только к одному символу, применяется оператор группировки. Например, выражению xy(z{2,4}) соответствуют строки xyzz, xyzzz и xyzzzz. |
| <начальное-состояние> | Связанное действие выполняется только в том случае, если лексический
анализатор находится в указанном начальном состоянии (Начальные состояния lex).
Пример: Если начало строки соответствует начальному состоянию ONE, то оператор ^ (знак вставки) совпадает с выражением <ONE>. |
Для применения символов операторов в качестве текстовых предназначены escape-последовательности " " (двойные кавычки) и \ (обратная косая черта). Оператор " " означает, что внутри кавычек расположен текст. Таким образом, строка xyz++ может быть описана следующим выражением:
xyz"++"
Обратите внимание, что в кавычки может заключаться только часть строки. Заключение в кавычки обычного текста не влияет на работу анализатора. Следующее выражение эквивалентно приведенному выше:
"xyz++"
Заключение в кавычки всех символов, не являющихся буквами и цифрами, гарантирует, что текст будет обрабатываться именно как текст.
Другим способом указать, что символ оператора следует рассматривать как текст, является символ \ (обратная косая черта) перед символом оператора. Следующее выражение эквивалентно приведенным выше:
xyz\+\+
После того как лексический анализатор найдет соответствие между входной строкой и одним из расширенных регулярных выражений, описанных в разделе правил файла спецификаций, он выполняет действие, связанное в этим выражением. Если для обработки входного потока определено недостаточное количество правил, анализатор просто копирует его в выходной поток. Поэтому создавать правила, которые просто копируют текст из входного потока в выходной, не следует. Показываемый по умолчанию вывод позволяет найти ошибки в правилах.
Если команда lex применяется для обработки входных данных синтаксического анализатора, создаваемого командой yacc, то необходимо задать правила для обработки всех возможных строк. Эти правила должны выводить информацию в формате, понятном команде yacc.
Для того чтобы пропустить текст, связанный с расширенным регулярным выражением, укажите ; (пустой оператор C) в качестве кода действия. Приведенный ниже пример пропускает три символа форматирования (пробел, табуляцию и переход на новую строку):
[ \t\n] ;
Для того чтобы не повторять код действия несколько раз, применяется символ | (символ конвейера). Этот символ означает, что для выражения используется то же действие, что и для следующего выражения. Например, приведенный выше пример для пропуска пробелов, табуляций и символов новой строки может быть записан следующим образом:
" " | "\t" | "\n" ;
Символы \n и \t можно не заключать в кавычки.
Для того чтобы просмотреть текст, в соответствии с которым было выбрано выражение, указанное в разделе правил файла спецификаций, можно использовать функцию printf языка C. После того как лексический анализатор обнаруживает во входном потоке строку, соответствующую одному из правил, он помещает ее во внешние массивы однобайтовых (char) и многобайтовых (wchar_t) символов, называемые yytext и yywtext соответственно. Для вывода обнаруженной строки может, например, использоваться следующий код:
[a-z]+ printf("%s",yytext);
При вызове функции
printf необходимо указать формат и данные для вывода. В этом
примере аргументы printf имеют следующее значение:
Команда lex определяет специальное действие ECHO для вывода массива yytext. Например, два следующих правила равносильны:
[a-z]+ ECHO;
[a-z]+ printf("%s",yytext);
Представление yytext
можно изменить, указав значение %array или %pointer в
разделе определений файла спецификаций lex.
| %array | Определяет yytext как массив символов, оканчивающийся нулем. Это действие по умолчанию. |
| %pointer | Определяет yytext как указатель на строку, оканчивающуюся нулем. |
Для того чтобы определить число
символов в строке, соответствующей расширенному регулярному выражению,
применяются внешние переменные yyleng и yywleng.
| yyleng | Число байт в найденной строке. |
| yywleng | Число многобайтовых символов в найденной строке. Размер многобайтовых символов больше 1. |
Для подсчета числа слов и числа символов во входном потоке используйте следующее действие:
[a-zA-Z]+ {words++;chars += yyleng;}
Это действие подсчитывает общее число символов в найденных словах и помещает его в переменную chars.
Следующее выражение возвращает последний символ в найденной строке:
yytext[yyleng-1]
Команда lex разбивает входной поток и не обеспечивает поиск всех возможных соответствий каждого выражения. Каждый символ учитывается только один раз. Если необходимо найти строки, которые могут перекрываться и содержать друг друга, используйте директивы REJECT. Например, для подсчета всех вхождений she и he, включая вхождения he внутри she, опишите следующие действия:
she {s++; REJECT;}
he {h++}
\n |
. ;
После подсчета числа вхождений she команда lex отклоняет входной поток, а затем подсчитывает число вхождений he. Так как he не может включать she, действие REJECT для he указывать необязательно.
В обычном режиме следующая строка из входного потока заменяет текущую строку в массиве yytext. При вызове процедуры yymore следующая строка добавляется в конец текущей строки в массиве yytext.
Например, следующий лексический анализатор ищет строки:
%s instring
%%
<INITIAL>\" { /* начало строки */
BEGIN instring;
yymore();
}
<instring>\" { /* конец строки */
printf("найдено %s\n", yytext);
BEGIN INITIAL;
}
<instring>. {
yymore();
}
<instring>\n {
printf("Ошибка, обнаружен символ новой строки \n");
BEGIN INITIAL;
}
Несмотря на то, что строка может быть обнаружена несколькими правилами, повторяющиеся вызовы yymore гарантируют, что в массив yytext будет помещена вся строка.
Для того чтобы вернуть символы во входной поток, применяется следующий вызов:
yyless(n)
здесь n обозначает сохраняемое число символов текущей строки. Остальные символы будут помещены обратно во входной поток. Процедура yyless обеспечивает опережающий просмотр текста аналогично оператору / (косая черта), но позволяет выполнять его более гибко.
Процедура yyless используется в случаях, когда текст нужно обработать несколько раз. Например, при анализе программы на C встречаются трудные для анализа выражения, такие как x=-a. Это может означать, что x присваивается значение, противоположное a, или что это устаревший вызов x -= a, означающий уменьшение значения x на величину a. Для того чтобы выражение обрабатывалось как xприсваивается значение, противоположноеa, и при этом выводилось предупреждение, можно задать следующее правило:
=-[a-zA-Z] {
printf("Оператор (=-) не поддерживается \n");
yyless(yyleng-1);
... действие присвоения ...
}
Команда lex позволяет
использовать в программе следующие функции ввода-вывода:
В среде lex эти функции описаны с помощью макроопределений. Они хранятся в файле lex.yy.c. Вы можете создать другую реализацию этих процедур.
Макроопределения winput, wunput и woutput применяют функции yywinput, yywunput и yywoutput. Из соображений совместимости процедуры yy применяют соответствующие процедуры input, unput и output для чтения, замены и записи требуемого числа байт для полного многобайтового символа.
Эти процедуры определяют связь между внешними файлами и внутренними символами. Если вы будете изменять эти процедуры, то изменяйте все процедуры сходным образом. Они должны удовлетворять следующим правилам:
Файл lex.yy.c позволяет лексическому анализатору хранить до 200 символов.
Для работы с файлом, содержащим нулевые значения, необходимо создать новую версию функции input. Стандартная версия input использует нулевое значение (возвращаемое также нулевыми символами) как индикатор конца файла и окончание ввода.
Лексический анализатор, создаваемый командой lex, выполняет ввод-вывод символов с помощью функций input, output, и unput. Таким образом, для возврата значений в процедуре yytext команда lex использует представление символов, которое применяется в этих процедурах. Однако внутри команда lex работает с символами как с целыми числами. При работе со стандартной библиотекой эти числа соответствуют наборам битов, которые используются компьютером для обозначения символов. Обычно букве 'a' соответствует значение символьной константы 'a'. Если вы измените такое соответствие в своих процедурах ввода-вывода, то в раздел определений файла спецификаций необходимо поместить таблицу преобразования. Таблица преобразования начинается и завершается строками, содержащими следующий текст:
%T
Внутри таблицы преобразования располагаются строки, устанавливающие соответствие между значениями и символами. Например:
%T
{целое число} {строка символов}
{целое число} {строка символов}
{целое число} {строка символов}
%T
Когда лексический анализатор
достигает конца файла, он взывает библиотечную функцию
yywrap.
| yywrap | Возвращает значение 1, чтобы указать лексическому анализатору, что он должен завершить обработку входного потока. |
Однако в тех случаях, когда лексический анализатор может получать данные из нескольких источников, необходимо изменить процедуру yywrap. Новая функция должна сформировать новый входной поток и вернуть нулевое значение. Значение 0 указывает на то, что лексический анализатор должен продолжать обработку.
В новую версию функции yywrap может быть также добавлен код, который показывает итоговые таблицы и суммарные значения. Изменение процедуры yywrap - это единственный способ указать процедуре yylex на продолжение или завершение входного потока.
Команда lex передает в лексический анализатор неизмененный код на языке C при следующих условиях:
Вы можете определить строковые макроопределения, которые команда lex должна преобразовывать в строки при создании текста лексического анализатора. Макроопределения должны быть определены перед первым ограничителем %% в файле спецификаций lex. Любая строка в этом разделе, начинающаяся с 1 столбца и не находящаяся внутри блока, ограниченного символами %{ и %}, определяет строку подстановки lex. Определения строк подстановки имеют следующий формат:
имя значение
Поля имя и значение должны быть разделены как минимум одним пробелом или символом табуляции. Имя должно начинаться с буквы. Когда программа lex обнаруживает строку, определенную значением имя, заключенным в {} (фигурные скобки) в разделе правил файла спецификаций, она заменяет это имя на строку, заданную в поле значение, и удаляет фигурные скобки.
Например, для определения имен D и E необходимо поместить следующие строки перед первым ограничителем %% в файле спецификаций:
D [0-9]
E [DEde][-+]{D}+
Теперь эти имена можно применять в разделе правил для сокращения текста:
{D}+ printf("целое число");
{D}+"."{D}*({E})? |
{D}*"."{D}+({E})? |
{D}+{E} printf("действительное число");
В раздел определений могут быть также включены следующие объекты:
Правило может быть связано с любым начальным состоянием. Однако правило будет учитываться программой lex только тогда, когда она находится в указанном состоянии. Текущее начальное состояние можно изменить в любой момент.
Начальные состояния указываются в разделе определений файла спецификаций с помощью следующей конструкции:
%Start имя-1 имя-2
Здесь имя-1 и имя-2 определяют имена, соответствующие состоянию. Число состояний не ограничено, их порядок значения не имеет. Слово Start может быть сокращено до s или S.
При описании правила, соответствующего начальному состоянию, имя состояния в начале правила заключается в символы <> (угловые скобки). Приведенный ниже пример определяет правило, которое распознается программой lex только в случае, если программа lex находится в состоянии имя-1:
<имя-1>выражение
Для перевода программы lex в требуемое состояние применяется действие BEGIN:
BEGIN name1;
Это действие устанавливает состояние name1.
Для перехода в обычное состояние введите:
BEGIN 0;
BEGIN INITIAL;
В этом примере INITIAL соответствует значению 0 согласно определениям программы lex. BEGIN 0; возвращает lex в исходное состояние.
Программа lex поддерживает также исключительные состояния запуска. Они определяются с помощью операторов %x (знак процента, строчная x) и %X (знак процента, заглавная X), за которым следует список имен исключительных состояний, аналогично списку обычных состояний запуска. Исключительные состояния отличаются от обычных тем, что в исключительном состоянии строки, для которых состояние не указано, не учитываются анализатором. Например:
%s one
%x two
%%
abc {printf("найдено ");ECHO;BEGIN one;}
<one>def printf("найдено ");ECHO;BEGIN two;}
<two>ghi {printf("найдено ");ECHO;BEGIN INITIAL;}
В состоянии one будут распознаваться и строка abc, и строка def. В состоянии two будет распознаваться только строка ghi.
Процесс компиляции программы lex разбит на два этапа:
Например, если файл спецификаций lex называется lextest, введите следующие команды:
lex lextest cc lex.yy.c -ll
Библиотека lex
содержит следующие процедуры:
Некоторые функции lex могут быть заменены пользовательскими. Например, lex поддерживает пользовательские версии процедур main и yywrap. Базовые функции этих процедур, составляющие основу для доработки, приведены ниже:
#include <stdio.h>
#include <locale.h>
main() {
setlocale(LC_ALL, "");
yylex();
exit(0);
}
yywrap() {
return(1);
}
Функции yymore, yyless и yyreject доступны только из библиотеки lex, однако они требуются только при вызове действий lex.
Глава 1, Инструменты и утилиты
Работа с программами lex и yacc
Примеры программ с использованием lex и yacc
функция printf