Генератор программ лексического анализа lex Производственно-внедренческий кооператив "И Н Т Е Р Ф Е Й С" Диалоговая Единая Мобильная Операционная Система Демос/P 2.1 Генератор программ лексического анализа lex Москва 1988 Аннотация В документе описан язык программирования lex, предназ- наченный для разработки программ лексического анализа. При- водятся правила работы с компилятором языка lex ОС ДЕМОС. 1. Введение lex - генератор программ лексического анализа. Лекси- ческий анализ - это распознавание лексем во входном потоке символов. Предположим, что задано некоторое конечное мно- жество слов (лексем) в некотором языке и некоторое входное слово. Необходимо установить, какой элемент множества (если он существует) совпадает с данным входным словом. Обычно лексический анализ выполняется так называемым лексическим анализатором. Лексический анализатор - это программа. Лексический анализ применяется во многих случаях, нап- ример, для построения пакетного редактора или в качестве распознавателя директив в диалоговой программе и т.д. Однако, наиболее важное применение лексического анализатора - это использование его в компиляторе. Здесь лексический анализатор выполняет функцию программы ввода данных. Лексический анализатор выполняет первую стадию компиля- ции - читает строки компилируемой программы, выделяет лек- семы и передает их на дальнейшие стадии компиляции (грамма- тический разбор, кодогенерацию и т.д.). Лексический анализатор распознает тип каждой лексемы и соответствующим образом помечает ее. Например, при компиля- ции Си-программы могут быть выделены следующие типы лексем: число, идентификатор, оператор, ограничитель и т.д. Лексический анализатор должен не только выделить лек- сему, но и выполнить некоторые преобразования. Например, если лексема - число, то его необходимо перевести во внут- реннюю (двоичную) форму записи как число с плавающей или фиксированной точкой. А если лексема - идентификатор, то его необходимо разместить в таблице, чтобы в дальнейшем обращаться к нему не по имени, а по адресу в таблице. Хотя лексический анализ по своей идее прост, тем не менее эта фаза работы компилятора часто занимает больше вре- мени, чем любая другая. Частично это происходит из-за необ- ходимости просматривать и анализировать исходный текст сим- вол за символом. Иногда даже бывает необходимо вернуть про- читанный символ во входной поток с тем, чтобы повторить просмотр и анализ. Происходит это потому, что часто бывает трудно опреде- лить, где проходят границы лексемы. Допустим, имеются две лексемы: make makefile 3 Пусть из входного потока поступает набор символов: ...makefile... При анализе входного потока символов будет выделена лексема make, хотя правильно было бы выделить лексему makefile. Единственный способ преодолеть это затруднение - прос- мотр полученной цепочки символов назад и вперед. В нашем примере при выделении лексемы make мы должны просмотреть следующий поступающий символ и, если он будет символом "f", то вполне возможно, что поступает лексема makefile. Процесс просмотра входного потока можно рассматривать как движение влево и вправо рамки над цепочкой символов. При этом анализируется только тот символ, который охвачен рам- кой. ... . . source make.f.ile file compiler . . ... <=== ===> Анализ заключается в определении соответствия рассматривае- мой последовательности символов некоторому так называемому регулярному выражению. Например, регулярное выражение (+?[0-9])+|(-?[0-9])+ позволяет выделить в цепочке все лексемы типа целое, перед которыми либо указан знак (+ или -), либо не указан. Для чисел с точкой это выражение имело бы вид: (+?[0-9.])+|(-?[0-9.])+ В тех случаях, когда выделение лексемы затруднено либо по причине того, что одно регулярное выражение не позволяет ее однозначно определить, либо из-за того, что лексема является частью другой, приходится прибегать к контекстно-зависимым алгоритмам анализа с использованием левого и правого направ- лений просмотра входной цепочки символов. lex частично или полностью автоматизирует процесс написания программы лексического анализа. lex - это програм- мирующая программа или генератор программ. lex строит прог- рамму - лексический анализатор на так называемом host-языке (или "главном" языке). Это значит, что Lex-программа пишется на "языке" lex, а Lex-генератор, в свою очередь, генерирует программу лексического анализа на каком-либо другом языке. 4 Данная версия lex генерирует лексические анализаторы на язы- ках Си и Ратфор (рациональный диалект Фортрана). В качестве host-языка мы будем использовать язык Си. Сведения об использовании в качестве host-языка Ратфор выделены в отдельный параграф. В каталоге /usr/lib/lex имеется файл-заготовка ncform, который используется Lex-генератором для построения лекси- ческого анализатора. Этот файл является уже готовой прог- раммой лексического анализа, но в нем не определены дейст- вия, которые необходимо выполнить при распознавании лексемы, отстутствуют и сами лексемы, не сформированы рабочие массивы и т.д. lex на основе Lex-программы достраивает файл ncform. В результате мы получаем файл со стандартным именем lex.yy.c, который является текстом Си-программы, осуществляющей лекси- ческий анализ. Lex-программа имеет следующий формат: определения %% правила %% подпрограммы, составленные пользователем Любой из этих разделов может быть пустым. Простейшая Lex- программа имеет вид: %% Здесь нет никаких определений и никаких правил. Все разделы Lex-программы мы подробно рассмотрим ниже. Сейчас целесообразно рассмотреть, что представляют собой правила. Правило состоит из двух частей: РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ По регулярным выражениям, содержащимся в левой части правил, lex строит детерминированный конечный автомат. Этот автомат осуществляет интерпретацию, а не компиляцию. Количество пра- вил и их сложность не влияют на скорость лексического ана- лиза, если только правила не требуют слишком большого объема повторных просмотров входной последовательности символов. Однако, с ростом числа правил и их сложности растет размер конечного автомата, интерпретирующего их и, следовательно, растет размер Си-программы, реализующей этот конечный авто- мат. 5 Рассмотрим в качестве примера следующую Lex-программу: %% [jJ][aA][nN][uU][aA][rR][yY] { printf("Январь"); } [fF][eE][bB][rR][uU][aA][rR][yY] { printf("Февраль"); } [mM][aA][rR][cC][hH] { printf("Март"); } [aA][pP][rR][iI][lL] { printf("Апрель"); } [mM][aA][yY] { printf("Май"); } [jJ][uU][nN][eE] { printf("Июнь"); } [jJ][uU][lL][yY] { printf("Июль"); } [aA][uU][gG][uU][sS][tT] { printf("Август"); } [sS][eE][pP][tT][eE][mM][bB][eE][rR] { printf("Сентябрь"); } [oO][cC][tT][oO][bB][eE][rR] { printf("Октябрь"); } [nN][oO][vV][eE][mM][bB][eE][rR] { printf("Ноябрь"); } [dD][eE][cC][eE][mM][bB][eE][rR] { printf("Декабрь"); } [mM][oO][nN][dD][aA][yY] { printf("Понедельник");} [tT][uU][eE][sS][dD][aA][yY] { printf("Вторник"); } [wW][eE][dD][nN][eE][sS][dD][aA][yY] { printf("Среда"); } [tT][hH][uU][rR][sS][dD][aA][yY] { printf("Четверг"); } [fF][rR][iI][dD][aA][yY] { printf("Пятница"); } [sS][aA][tT][uU][rR][dD][aA][yY] { printf("Суббота"); } [sS][uU][nN][dD][aA][yY] { printf("Воскресенье");} Программа строит конечный автомат, который распознает анг- лийские наименования месяцев и дней недели. Каждое правило здесь определеяет действие (которое взято в фигурные скобки). Обратите внимание на то, что открывающая фигурная скобка стоит в той же строке, что и правило - это требование lex. Действие в каждом правиле данной Lex-программы - это вывод русского значения найденного английского слова. В качестве оператора, выполняющего действие, используется биб- лиотечная функция языка Си. 6 Пара фигурных скобок определяет блок (в смысле языка Си), который может содержать любое количество строк. Если действие содержит всего одну строку Си, то можно ее указать без фигурных скобок, как обычно. Единственное условие - она должна начинаться в той же строке, где указано регулярное выражение. В программе содержится только раздел правил, их всего 19. Регулярное выражение каждого правила определяет английс- кое слово, написанное маленькими или большими латинскими символами. Например "May" (Май) определен как "[mM][aA][yY]". По этому регулярному выражению будет выде- лена во входном потоке символов лексема "May", а по действию этого правила будет выведено "Май". Наличие большой и малой буквы в квадратных скобках обеспечивает распознавание слова "May", написанного любыми латинскими символами. Таким образом, данная Lex-программа строит Си- программу, которая переводит на русский язык имена месяцев и дней недели. Допустим, Lex-программа размещена в файле source.l, тогда, чтобы получить лексический анализатор на Си, необхо- димо выполнить следующий набор команд: % lex source.l % cc -O lex.yy.c -ll -o program % lex всегда, если не указано другое, строит выходной файл с именем lex.yy.c - Си-программу - лексический анализатор. Во второй строке этой последовательности команд запускается Си-компилятор, который выводит результат в файл program. Program может работать как фильтр в конвейере команд, как самостоятельная команда и в интерактивном режиме. Напри- мер: % program May Май MONDAY Понедельник MoNdaY Понедельник CNTRL/C % Флаг -ll требует подключения библиотеки /usr/lib/libl.a - библиотеки lex. Если необходимо получить самостоятельную программу, как в данном случае, подключение библиотеки 7 обязательно, поскольку тогда из нее подключается головной раздел main. В противном случае, если имеется необходимость включить анализатор в качестве функции в другую программу (например, в программу грамматического разбора), эту библио- теку необходимо вызвать уже при сборке и тогда, если main определен в вызывающей лексический анализатор программе, редактор связей не будет подключать раздел main из библио- теки lex. Если необходимо получить файл с именем, отличным от lex.yy.c, можно воспользоваться флагом -t : % lex -t source.l >&gt; file По этому флагу результат поступает в файл file. 2. Регулярные выражения в Lex-правилах Регулярные выражения определяют лексему. Регулярное выражение может содержать символы латинского и русского алфавитов в верхнем и нижнем регистрах, другие символы (цифры, знаки препинания и т.д.) и символы-операторы. Операторы позволяют осуществлять различные действия над выделенной цепочкой символов. Операторы также обозначаются символами. 2.1. Обозначения символов в выражениях В выражении можно использовать любой символ. Символ можно указывать в двойных кавычках. В этом случае это всегда просто символ - его специальное значение отменяется. Напри- мер: "abc" abc эти последовательности символов идентичны. . точка означает любой символ, кроме символа новой строки "\n"; \восьмеричный_код_символа указание символа его восьмеричным кодом (как в Си); \n символ новой строки; \t символ табуляции; \b возврат курсора на один шаг назад; 8 пробел любой символ пробела в выражении, если он не находится внутри квадратных скобок, необходимо заключать в двой- ные кавычки. Это необходимо, так как пробел и табуляция используются lex в качестве разделителя между определе- нием и действием в правиле. 2.2. Операторы регулярных выражений Операторы обозначаются символами-операторами, к ним относятся: \ ^ ? * + | $ / % [] {} () <&lt;>&gt; Каждый из этих символов или пар скобок в регулярном выраже- нии играет роль оператора. Если необходимо отменить специ- альное значение символа, обозначающего оператор, перед ним нужно поставить символ \ или указать его в двойных кавычках. Например: abc+ - символ "+" - оператор; abc\+ - символ "+"; abc"+" - символ "+". 2.3. Оператор выделения классов символов Квадратные скобки задают классы символов, которые в них заключены. [abc] означает либо символ "a", либо "b", либо символ "c"; Знак - используется для указания любого символа из лек- сикографически упорядоченной последовательности: [A-z] означает любой латинский символ; [А-Я] любая прописная русская буква; [+-0-9] все цифры и знаки "+" и "-". 2.4. Повторители Когда необходимо указать повторяемость вхождения сим- вола в регулярном выражении, используют операторы- повторители * и +. 9 Оператор * означает любое (в том числе и 0) число вхож- дений символа или класса символов. Например: x* любое число вхождений символа "x"; abc* любое число вхождений цепочки "abc"; [A-z]* любое число вхождений любой латинской буквы; [A-ZА-Яa-zа-я_0-9]* любое вхождение русских и латинских букв, знака подчер- кивания и цифр. Оператор + означает одно и более вхождений. Например: x+ одно или более вхождений "x"; [0-9]+ одно или более вхождений цифр; abc+ одно или более вхождений цепочки abc; [A-z]+ одно или более вхождений любой латинской буквы. 2.5. Операторы выбора Операторы: / | ? $ ^ управляют процессом выбора символов. Оператор /: ab/cd "ab" учитывается только тогда, когда за ним следует "cd". Опeратор |: ab|cd или "ab", или "cd". Опeратор ?: x? означает необязательный символ "x". _?[A-Za-z]* означает, что перед цепочкой любого количества латинс- ких букв может быть необязательный знак подчеркивания. 10 -?[0-9]+ выделит любое целое число с необязательным минусом впе- реди. Оператор $: x$ означает выбрать символ "x", если он является последним в строке. Стоит перед символом "\n"! abc$ означает выбрать цепочку "abc", если она завершает строку. Оператор ^: ^x означает выбрать символ "x", если он является первым символом строки; ^abc означает выбрать цепочку символов "abc", если она начи- нает строку. [^A-Z]* означает все символы, кроме прописных латинских букв. Когда символ ^ стоит перед выражением или внутри [], он выполняет операцию дополнение. Внутри квадратных скобок символ ^ должен обязательно стоять первым у открывающей скобки! 2.6. Оператор {} Оператор {} имеет два различных применения: x{n,m} здесь n и m натуральные, m > n. Означает от n до m вхождений x, например, x{2,7} - от 2 до 7 вхождений x. {имя} вместо {имя} в данное место выражения будет подстав- лено определение имени из области определений Lex- программы. Пример: БУКВА [A-ZА-Яa-zа-я_] ЦИФРА [0-9] ИДЕНТИФИКАТОР {БУКВА}({БУКВА}|{ЦИФРА})* %% {ИДЕНТИФИКАТОР} printf("\n%s",yytext); lex построит лексический анализатор, который будет опреде- лять и выводить все "слова" из входного файла. Под словом в данном случае подразумевается идентификатор Си-программы. В этом примере {ИДЕНТИФИКАТОР} будет заменен на {БУКВА}({БУКВА}|{ЦИФРА})*, затем на [A-ZА-Яa-zа-я_]([A-ZА- Яa-zа-я_]|[0-9])*. 11 yytext - это внешний массив символов программы lex.yy.c, которую строит lex. yytext формируется в процессе чтения входного файла и содержит текст, для которого уста- новлено соответствие какому-либо выражению. Этот массив дос- тупен пользовательским разделам Lex-программы. Оператор printf выводит каждый идентификатор на новой строке. Правило ".|\n ;" используется для того, чтобы пропустить (не выводить) все цепочки символов, которые не соответствуют регулярному выражению {ИДЕНТИФИКАТОР}. 2.7. Оператор <&lt;>&gt;. Служебные слова START и BEGIN Раздел правил Lex-программы может содержать активные и неактивные правила. Активные правила выполняются всегда. Неактивные выполняются только в тех случаях, когда выполня- ется некоторое начальное условие. Начальные условия Lex-программы помещаются в раздел определений, а неактивные правила помечаются соответствую- щими условиями. Оператор START позволяет указать список начальных условий Lex-программы, а оператор BEGIN позволяет активировать правила, помеченные начальными условиями. Активные правила имеют следующий синтаксис: РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ Неактивные правила имеют следующий синтаксис: <&lt;МЕТКА_УСЛОВИЯ>&gt;РЕГ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ ВАЖНО: любое правило должно начинаться с первой позиции строки, пробелы и табуляции недопустимы - они используются как разделители между регулярным выражением и действием в правиле! Рассмотрим пример: 12 %START COMMENT КОММ_НАЧАЛО "/*" КОММ_КОНЕЦ "*/" %% {КОММ_НАЧАЛО} { ECHO; BEGIN COMMENT;}; [\t\n]* ; <COMMENT>[^*]* ECHO; <COMMENT>[^/] ECHO; <COMMENT>{КОММ_КОНЕЦ} { ECHO; printf("0); BEGIN 0;}; lex построит лексический анализатор, который выделяет ком- ментарии в Си-программе и записывает их в стандартный файл вывода. Программа начинается с ключевого слова START, кото- рое указано после символа %. Ключевое слово START можно указать и так: Start, или S, или s . За ключевым словом START указана метка начального условия COMMENT. Оператор "<COMMENT>x" означает - x, если анализатор находится в начальном условии COMMENT. Oператор "BEGIN COMMENT;" переводит анализатор в начальное условие COMMENT (смотрите первое правило раздела правил этой Lex-программы). После этого анализатор уже нахо- дится в новом состоянии и теперь разбор входного потока сим- волов будет осуществляется и теми правилами, которые начина- ются оператором "<COMMENT>". Например, правило <COMMENT>[^*]* ECHO; выполняется только тогда, когда во входном потоке символов будет обнаружено начало комментариев ("/*"). В этом случае анализатор записывает в стандартный файл вывода любое число (в том числе и ноль) символов, отличных от символа "*". Опе- ратор "BEGIN 0;" переводит анализатор в исходное состояние. Lex-программа может содержать несколько помеченных начальных условий. Например, если Lex-программа начинается строкой %START AA BB CC DD то это означает, что она управляет четырьмя начальными сос- тояниями анализатора. В каждое из этих начальных состояний анализатор можно перевести, используя оператор BEGIN. 13 Каждое правило, перед которым указан оператор типа "<&lt;МЕТКА>&gt;", мы будем называть помеченным правилом. Метка фор- мируется так же, как и метка в Си. Количество помеченных правил не ограничивается. Кроме того, разрешается одно правило помечать несколькими метками, например: <&lt;МЕТКА1,МЕТКА2,МЕТКА3>&gt;x ДЕЙСТВИЕ Запятая - обязательный разделитель списка меток! Рассмотрим пример с несколькими начальными условиями: %START AA BB CC БУКВА [A-ZА-Яa-zа-я_] ЦИФРА [0-9] ИДЕНТИФИКАТОР {БУКВА}({БУКВА}|{ЦИФРА})* %% ^# BEGIN AA; ^[ \t]*main BEGIN BB; ^[ \t]*{ИДЕНТИФИКАТОР} BEGIN CC; \t ; \n BEGIN 0; <AA>define printf("Определение.\n"); <AA>include printf("Включение.\n"); <AA>ifdef { printf("Условная компиляция.\n"); } <BB>[^\,]*","[^\,]*")" { printf("main с аргументамии.\n"); } <BB>[^\,]*")" { printf("main без аргументов.\n"); } <CC>":"/[ \t] printf("Метка.\n"); Программа содержит активные и неактивные правила. Все неак- тивные правила помечены, перед ними указана метка начального условия. Lex-программа управляет тремя начальными условиями, в соответствии с которыми активируются помеченные правила. В результате работы lex мы получим лексический анализа- тор, который будет распознавать в Си-программе строки преп- роцессора Си-компилятора, выделять функцию main, распозна- вая, с аргументами она или без них, распознавать метки. Лексический анализатор не выводит ничего, кроме сообщений о выделенных лексемах. 14 3. Структура Lex-программы Lex-программа включает разделы опредeлений, правил и пользовательских программ. Рассмотрим подробнее способы оформления этих разделов. Все строки, в которых занята первая позиция, относятся к Lex-программе. Любая строка, не являющаяся частью правила или действия, которая начинается с пробела или табуляции, копируется в сгенерированную программу lex.yy.c - результат работы lex. 3.1. Раздел определений Lex-программы Определения, предназначенные для lex, помещаются перед первым %%. Любая строка этого раздела, не содержащаяся между %{ и %} и начинающаяся в первой колонке, является определе- нием строки подстановки lex. Раздел определений Lex- программы может включать: начальные условия, определения, фрагменты программы пользователя, таблицы наборов символов, указатели host-языка, изменения размеров внутренних массивов, комментарии в формате host-языка. НАЧАЛЬНЫЕ УСЛОВИЯ задаются в форме: %START имя1 имя2 ... Если начальные условия определены, то эта строка должна быть первой в Lex-программе. ОПРЕДЕЛЕНИЯ задаются в форме: имя трансляция В качестве разделителя используется один или более пробелов или табуляций. Пример: БУКВА [A-ZА-Яa-zа-я_] DIGIT [0-9] ИДЕНТИФИКАТОР {БУКВА}({БУКВА}|{DIGIT})* Имя - как обычно, любая последовательность букв и цифр, начинающаяся с буквы. Трансляция - это регулярное выражение (или его часть), которое будет подставлено всюду там, где указано имя (смотрите третью строку этого примера). 15 ФРАГМЕНТЫ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ указываются двумя спо- собами: - в виде "пробел фрагмент"; - в виде: %{ строки фрагмента программы пользователя %} Такая форма включения пользовательского фрагмента необходима для ввода, например, макроопределений Си, которые должны начинаться в первой колонке строки. Все строки фрагмента пользовательской программы, раз- мещенные в разделе определений, будут являться внеш- ними для любой функции программы lex.yy.c ТАБЛИЦА НАБОРОВ СИМВОЛОВ задается в виде: %T целое_число строка_символов ......... целое_число строка_символов %T Сгенерированная программа lex.yy.c осуществляет ввод-вывод символов посредством библиотечных функций lex с именами input, output, unput. Таким образом, lex помещает в yytext символы в представлении, используемом в этих библиотечных функциях. Для внутреннего использования символ представля- ется целым числом, значение которого образовано набором битов, представляющих символ в конкретной ЭВМ. Пользователю предоставляется возможность менять представление символов (целых констант) с помощью таблицы наборов символов. Если таблица символов присутствует в разделе определений, то любой символ, появляющийся либо во входном потоке, либо в правилах, должен быть определен в таблице символов. Символам нельзя назначать число 0 и число, большее числа, выделенного для внутреннего представления символов конкретной ЭВМ. Пример: 16 %T 1 Aa 2 Bb 3 Cc . . . 26 Zz 27 28 + 29 - 30 0 31 1 . . . 39 9 %T В этом примере символы верхнего и нижнего регистров перево- дятся в числа 1-26, символ новой строки в 27, "+" и "-" переводятся в числа 28 и 29, а цифры - в числа 30-39. ИЗМЕНЕНИЯ РАЗМЕРА ВНУТРЕННИХ МАССИВОВ задаются в форме: %x число число - новый размер массива; x - одна из букв: p - позиции; n - состояния; e - узлы дерева; a - упакованные переходы; k - упакованные классы символов; o - массив выходных элементов. lex имеет внутренние таблицы, размеры которых ограничены. При построении программы лексического анализа может прои- зойти переполнение любой из этих таблиц, о чем lex сообщает при построении лексического анализатора. Пользователю пре- доставляется возможность изменить размеры таблиц (сокращая размеры одних и увеличивая размеры других) таким образом, чтобы они не переполнялись. Естественно, эти изменения воз- можны лишь в пределах той памяти, которая выделяется под процесс. Ниже перечислены размеры таблиц, которые устанавлива- ются по умолчанию: 17 p - позиций 1500 n - состояний 300 e - узлов 600 a - упакованных переходов 1500 k - упакованных классов символов 1000 o - выходных элементов 1500 Для того чтобы определить, каковы размеры таблиц и насколько они заняты, можно использовать флаг -v, например: % lex -v source.l 33/600 узлов(%e) 97/1500 позиций(%p) 17/300 состояний(%n) 2551 переходов 18/1000 упакованных классов символов(%k) 41/1500 упакованных переходов(%a) 68/1500 выходных элементов(%o) % Здесь показано сообщение, которое выводит lex по флагу -v. Число перед символом "/" указывает сколько элементов массива занято, а число за символом "/" указывает установленный раз- мер массива. КОММЕНТАРИИ в разделе определений задаются в форме host-языка и должны начинаться не с первой колонки строки. 3.2. Раздел правил Все, что указано после первой пары %% и до конца Lex- программы или до второй пары %%, если она указана, относится к разделу правил. Раздел правил может содержать правила и фрагменты программ. Фрагменты программ, содержащиеся в раз- деле правил, становятся частью функции yylex файла lex.yy.c, в которой осуществляется выполнение действий активных пра- вил. Фрагмент программы указывается следующим образом: %{ строки фрагмента программы %} Например: %% %{ #include file.h %} . . . 18 Здесь строка "#include file.h" станет строкой функции yylex(). Раздел правил может включать список активных и неактив- ных (помеченных) правил. Активные и неактивные правила могут быть указаны в любом порядке, в том числе быть "пере- мешанными" в списке. Активные правила выполняются всегда, неактивные только по ссылке на них оператором BEGIN. Активное правило имеет вид: ВЫРАЖЕНИЕ ДЕЙСТВИЕ Неактивное правило имеет вид: <МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ или <СПИСОК_МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ где СПИСОК_МЕТОК имеет вид: метка1,метка2,... В качестве первого правила раздела правил может быть правило вида: BEGIN МЕТКА; В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым действием в разделе правил будет активизация помеченных правил. Для возвращения автомата в исходное состояние можно использовать действие: BEGIN 0; Важно отметить следующее. Если Lex-программа содержит актив- ные и неактивные правила, то активные правила работают всегда. Оператор "BEGIN МЕТКА;" просто расширяет список активных правил, активируя помеченные меткой МЕТКА. А опера- тор "BEGIN 0;" удаляет из списка активных правил все поме- ченные правила, которые до этого были активированы. Кроме того, если из помеченного и активного в данный момент вре- мени правила осуществляется действие BEGIN МЕТКА, то из помеченных правил активными останутся только те, которые помечены меткой МЕТКА. 3.2.1. Действия в правилах Lex-программы Действие можно представлять либо как оператор lex, нап- ример, "BEGIN МЕТКА;", либо как оператор Си. Если имеется необходимость выполнить достаточно большой набор преобразо- ваний, то действие оформляют как блок Си-программы (он 19 начинается открывающей фигурной скобкой и завершается закры- вающей фигурной скобкой), содержащий необходимые фрагменты. Действие в правиле указывается через не менее, чем один пробел или табуляцию после выражения (обязательно в той же строке, где и выражение), а его продолжение может быть ука- зано в следующих строках только в том случае, если действие оформлено как блок Си-программы. Область действия переменных, объявленных внутри блока, распространяется только на этот блок. Внешними переменными для всех действий будут являться только те переменные, кото- рые объявлены в разделе определений Lex-программы. Действия в правилах Lex-программы выполняются, если правило активно, и если автомат распознает цепочку символов из входного потока как соответствующую регулярному выражению данного правила. Однако, одно действие выполняется всегда - оно заключается в копировании входного потока символов в выходной. Это копирование осуществляется для всех входных строк, которые не соответствуют правилам, преобразующим эти строки. Комбинация символов, не учтенная в правилах и поя- вившаяся на входе, будет напечатана на выходе. Можно ска- зать, что действие - это то, что делается вместо копирования входного потока символов на выход. Часто бывает необходимо не копировать на выход некоторую цепочку символов, которая удовлетворяет некоторому регулярному выражению. Для этой цели используется пустой оператор Си, например: [ 0 ; Это правило игнорирует (запрещает) вывод пробелов, табуляций и символа новая строка. Запрет выражается в том, что на указанныe символы во входном потоке осуществляется действие ";" - пустой оператор Си, и эти символы не копируются в выводной поток символов. Существует возможность для нескольких регулярных выра- жений указывать одно действие. Для этого используется символ "|", который указывает, что действие данного правила совпа- дает с действием для следующего, например: " " | | ; Результат будет тот же, что и в примере, указанном выше. Когда необходимо вывести или преобразовать текст, соот- ветствующий некоторому регулярному выражению, используется внешний массив символов, который формирует lex. Называется он yytext и доступен в действиях правил. Например: 20 [A-Z]+ printf("%s",yytext); По этому правилу распознается слово, содержащее прописные латинские буквы и выводится с помощью printf, если оно выде- лено. Операция вывода распознанного выражения используется очень часто, поэтому имеется сокращенная форма записи этого действия: [A-Z]+ ECHO; Результат действия этого правила будет аналогичен результату предыдущего примера. В выходном файле lex.yy.c ECHO опреде- лено как макроподстановка: #define ECHO fprintf(yyout, "%s",yytext); Когда необходимо знать длину обнаруженной последовательности символов, используется счетчик найденных символов yyleng, который также доступен в действиях. Например: [A-Z]+ printf("%c",yytext[yyleng-1]); В этом примере будет выводится последний символ слова, соот- ветствующего регулярному выражению [A-Z]+. Рассмотрим еще один пример: [A-Z]+ {число_слов++;число_букв += yyleng;} Здесь ведется подсчет числа распознанных слов и количества символов во всех словах. 3.2.2. Порядок действия активных правил Список правил Lex-программы может содержать активные и неактивные правила, размещенные в любом порядке в разделе правил. В процессе работы лексического анализатора список активных правил может видоизменяться за счет действий опера- тора BEGIN. В процессе распознавания символов входного потока может оказаться так, что одна цепочка символов будет удовлетворять нескольким правилам и, следовательно, возни- кает проблема: действие какого правила должно выполняться? Для разрешения этого противоречия можно использовать квантование (разбиение) регулярных выражений этих правил Lex-программы на такие новые регулярные выражения, которые дадут, по возможности, однозначное распознавание лексемы. Однако, когда это не сделано, lex использует определенный детерминированный механизм разрешения такого противоречия: - выбирается действие того правила, которое распознает наиболее длинную последовательность символов из вход- ного потока; 21 - если несколько правил распознают последовательности символов одной длины, то выполняется действие того правила, которое записано первым в списке раздела правил Lex-программы. Рассмотрим пример: . . . [Мм][Аа][Йй] ECHO; [А-Яа-я]+ ECHO; . . . Слово "Май" распознают оба правила, однако, выполнится пер- вое из них, так как и первое, и второе правило распознали лексему одинакового размера (3 символа). Если во входном потоке будет, допустим, слово "майский", то первые 3 символа удовлетворяют первому правилу, а все 7 символов удовлетво- ряют второму правилу, следовательно, выполнится второе пра- вило, так как ему удовлетворяет более длинная последователь- ность символов. 3.3. Раздел программ пользователя Все, что размещено за вторым набором %%, относится к разделу программ пользователя. Содержимое этого раздела копируется в выходной файл lex.yy.c без каких-либо измене- ний. В файле lex.yy.c строки этого раздела рассматриваются как функции в смысле Си. Эти функции могут вызываться в действиях правил и, как обычно, передавать и возвращать зна- чения аргументов. 3.4. Комментарии Lex-программы Комментарии можно указывать во всех разделах Lex- программы. Формат комментариев должен соответствовать фор- мату комментариев host-языка. Однако, в каждом разделе Lex- программы комментарии указываются по разному. В разделе определений комментарии должны начинаться не с первой пози- ции строки. В разделе правил комментарии можно указывать только внутри блоков, принадлежащих действиям. В разделе программ пользователя комментарии указываются как и в host- языке. 3.5. Примеры Lex-программ Пример1. 22 %Start KOMMENT /* * Программа записывает в * стандартный файл вывода * комментарии Си-программы. * Обратите внимание на то, что * здесь строки комментариев указаны * не с первой позиции строки! */ КОММ_НАЧАЛО "/*" КОММ_КОНЕЦ "*/" %% {КОММ_НАЧАЛО} { ECHO; BEGIN KOMMENT;} [0* ; <KOMMENT>[^*]* ECHO; <KOMMENT>[^/] ECHO; <KOMMENT>{КОММ_КОНЕЦ} { ECHO; printf("0); /* * Здесь приведен пример * использования комментариев в * разделе правил Lex-программы. * Обратите внимание на то, что * комментрий указан внутри блока, * определяющего действие правила. */ BEGIN 0;} %% /* * Здесь приведен пример комментариев * в разделе программ пользователя. */ Пример 2. 23 %Start IC1 IC2 Normal /* * Отладочный фрагмент * Lex-программы, которая строит * лексический анализатор для * компилятора языка Паскаль. * Действие return(...) * возвращает тип лексемы в * в вызывающую анализатор