LEX СОДЕРЖАНИЕ 1. Обзор использования lex'а 2. Разработка lex-программ 2.1. Основные элементы правил lex'а 2.1.1. Спецификации 2.1.2. Действия 2.2. Более сложные элементы lex'а 2.2.1. Некоторые специфические свойства 2.2.2. Секция определений 2.2.3. Секция подпрограмм 2.3. Совместное использование lex'а и yacc'а 3. Выполнение lex'а в системе UNIX 1. ОБЗОР ИСПОЛЬЗОВАНИЯ LEX'А lex - это инструмент, который позволяет решать широкий класс проблем, возникающих при обработке текстов, шифровании, реали- зации компиляторов и в других областях. При текстовой обработке Вы можете проверить правильность написания слов, при шифровании - переводить определенные шаблоны символов в другие, при реали- зации компиляторов - определить, какие лексемы (минимальные значащие последовательности символов) встречаются в компилируе- мой программе. Общей для всех этих задач является необходимость распознавать цепочки символов, удовлетворяющие определенным критериям. Если Вы разрабатываете компилятор, Вам придется реа- лизовать лексический анализатор. Отсюда и название - lex. В принципе, чтобы справиться с перечисленными проблемами, не обязательно использовать lex. Можно просто писать программы на стандартном языке, подобном C. В самом деле, lex также порожда- ет C-программы. (Поэтому lex можно назвать генератором прог- рамм). Дело, однако, в том, что lex позволяет достичь цели про- ще и быстрее. Его слабость в том, что он зачастую порождает C программы, которые длиннее, чем необходимо для конкретной зада- чи, и которые работают медленнее, чем могли бы. Но во многих приложениях это несущественно, и в целом преимущества использо- вания lex значительно превосходят недостатки. Чтобы понять, что делает lex, изучите приведенную ниже диаграм- му. Начало - это исходный lex-текст (часто называемый lex-спе- цификацией), который Вы, программист, пишете для решения Вашей задачи. lex-спецификация состоит из списка правил, определяющих последовательности символов (выражения), которые надо искать во входном тексте, и действия, которые надо выполнять, когда выра- жения найдены. Спецификация читается генератором программ lex. Результатом работы генератора является C-программа. Ее, в свою очередь, надо обработать стандартным C-компилятором, чтобы сге- нерировать выполняемую объектную программу, осуществляющую лек- сический анализ. Отметим, что обычно эта процедура не автомати- ческая; требуется вмешательство пользователя. Наконец, программа лексического анализа, полученная в результа- те этого процесса, по входным данным - произвольному исходному файлу - формирует ожидаемые выходные данные, например, изменен- ный текст или список лексем. ~------------ ~----- ~--------------- │ lex- ---> lex --->lex-анализатор │ │спецификация│ │ │ │ на C │ ------------ ----- ------- ------- │ ~------v------- │ C-компилятор │ │ │ ------ ------- │ ~------------- ~-------v------- ~--------------- │ входные -->программа лекси -->результаты: │ │ данные │ │ческого анализа│ │лексемы,текст..│ ------------- --------------- --------------- lex можно также использовать для сбора статистической информа- ции о свойствах входного текста, таких, как число символов, длина слов, число вхождений слов, и т.д. В следующих разделах этой главы Вы увидите, как: Писать lex-спецификации для решения некоторых из наз- ванных задач. Транслировать lex-спецификации. Компилировать, редактировать связи и запускать лекси- ческий анализатор на C. Выполнять программу лексического анализа. После этого Вы сможете самостоятельно оценить мощность средств, предоставляемых lex'ом. 2. РАЗРАБОТКА LEX-ПРОГРАММ lex-спецификация состоит максимум из трех секций: определений, правил и подпрограмм пользователя. Секция правил обязательна. Секции определений и подпрограмм могут отсутствовать, но если они имеются, то должны встречаться в указанном порядке. 2.1. Основные элементы правил lex'а Обязательная секция правил открывается разделителем %%. Если за ней следует секция подпрограмм, секцию правил закрывает еще один разделитель %%. Если второго разделителя нет, весь текст до конца программы трактуется как секция правил. Каждое правило состоит из спецификации искомого шаблона и дей- ствия (или действий), выполняемого, если шаблон найден. Дейст- вие должно быть отделено от шаблона одним или несколькими про- белами. (Отметим двойственный смысл термина спецификация - он может означать и весь исходный lex-текст, и, внутри него, представление конкретного распознаваемого шаблона). Входной текст, не содержащий искомых шаблонов, выводится lex'ом без из- менений. Поэтому простейшая lex-программа - это открывающий секцию правил разделитель %%. Такая программа выводит входной текст целиком без всяких изменений. В типичных случаях правила, разумеется, имеют более сложный вид. 2.1.1. Спецификации Шаблоны специфицируются с помощью нотации, называемой регуляр- ными выражениями. Регулярное выражение задается цепочкой симво- лов со знаками операций или без них. Простейшие регулярные вы- ражения - это цепочки символов без знаков операций. Пример: apple orange pluto Эти три регулярные выражения сопоставляются со всеми вхождения- ми указанных цепочек символов. Если Вы хотите, чтобы порожден- ный лексический анализатор удалял из входного текста цепочки orange, специфицируйте правило orange ; Так как действие справа от шаблона (перед точкой с запятой) не задано, lex не делает ничего, кроме вывода первоначального текста с удалением каждого вхождения данного регулярного выра- жения, то есть вообще без вхождений цепочки orange. В отличие от orange, большинство распознаваемых выражений нель- зя специфицировать так просто. Например, само выражение может быть слишком длинным. В более общем случае класс распознаваемых выражений оказывается слишком большим; на самом деле, он может быть бесконечным. Благодаря использованию операций можно форми- ровать регулярные выражения, обозначающие любое выражение из определенного класса. Операция +, например, обозначает одно или более вхождений предшествующего выражения, ? обозначает 0 или 1 вхождение предшествующего выражения (что, конечно, эквивалентно необязательности предшествующего выражения), * обозначает 0 или более вхождений предшествующего выражения. (На первый взгляд кажется странным говорить о 0 вхождениях выражения и иметь опе- рацию, чтобы выразить данную мысль, однако часто это весьма по- лезно. Ниже мы увидим соответствующий пример). Так, m+ - это регулярное выражение, которое сопоставляется с любой цепочкой из символов m, такой, как каждая из следующих: mmm m mmmmm mm Далее, 7* - это регулярное выражение, которое сопоставляется с любой цепочкой из нуля или большего числа семерок: 77 77777 777 Цепочка пробелов в третьей строке сопоставляется просто потому, что в ней вообще нет семерок. Квадратные скобки, [ ], обозначают произвольный символ из це- почки символов, указанной в скобках. Так, [dgka] сопоставляется с одиночными символами d, g, k и a. Отметим, что символы в квадратных скобках не нужно разделять запятыми. Любая запятая в данном случае рассматривается как символ, который должен рас- познаваться во входном тексте. Диапазоны букв или цифр (в стан- дартном алфавитном или числовом порядке) обозначаются при помо- щи дефиса, -. Так, запись [a-z] обозначает произвольную строч- ную латинскую букву. Приведем пример более интересного регуляр- ного выражения: [A-Za-z0-9*&#] Такой шаблон сопоставляется с любой латинской буквой (строчной или прописной), любой цифрой, символами *, & или #. Если вход- ной текст имеет вид $$$$?? ????!!!*$$ $$$$$$&+====r~~# (( то лексический анализатор, одно из правил которого содержит приведенный выше шаблон, распознает *, &, r и #, выполняя каж- дый раз действие, специфицированное в правиле (в примере дейст- вие опущено), и выводит остаток текста без изменений. Иногда проще указать не само множество нужных символов, а его дополнение, поместив сразу за открывающей скобкой [ символ ^. Чрезвычайно мощным средством является комбинирование операций. Пример - регулярное выражение, обозначающее идентификатор во многих языках программирования: [a-zA-Z][0-9a-zA-Z]* Идентификатор в этих языках определяется как буква, за которой следует нуль или больше букв или цифр, и именно это задается в регулярном выражении. Первая пара скобок сопоставляется с про- извольной буквой. Вторая, если бы за ней не следовал знак опе- рации *, сопоставлялась с произвольной буквой или цифрой. Но за счет использования операции * регулярное выражение сопоставля- ется с буквой, за которой следует произвольное число букв или цифр. В частности, были бы распознаны как идентификаторы следу- ющие цепочки символов: e pay distance pH EngineNo99 R2D2 Отметим, что не будут распознаваться как идентификаторы not_idenTIFIER 5times $hello так как not_idenTIFIER содержит подчеркивание, 5times начинает- ся с цифры, но не с буквы, а $hello начинается с символа $. Ко- нечно, в качестве упражнения Вы можете написать спецификации для этих трех примеров. Очевидно, в тех случаях, когда знаки операций нужно использо- вать как обычные символы, входящие в шаблон, требуется специ- альная нотация. Так, в последнем из приведенных примеров звез- дочка не является частью идентификатора. В lex'е указанную проблему можно решать двумя способами. Символ, заключенный в кавычки, либо символ, перед которым указан знак \, рассматрива- ется буквально, то есть как часть искомого текста. Чтобы приме- нить второй способ для распознавания, скажем, символа *, за ко- торым следует произвольное число цифр, можно использовать шаб- лон \*[0-9]* Чтобы распознать сам символ \, требуется шаблон \\. 2.1.2. Действия После того, как lex распознает цепочку, сопоставляемую с регу- лярным выражением, заданным в начале правила, он ищет в правой части правила действие, которое надо выполнить. Среди возможных видов действий - запись типа обнаруженной лексемы и значения, которое принимает лексема (если таковые имеются); замена одной лексемы на другую; подсчет числа вхождений лексем или типов лексем. Все, что Вы хотите проделать, нужно записать в виде фрагментов программ на языке C. Действие может состоять из про- извольного числа операторов. Можно напечатать сообщение с най- денным текстом или сообщение, как-то трансформирующее этот текст. Так, чтобы распознать выражение Amelia Earhart и сооб- щить об этом, можно специфицировать правило: "Amelia Earhart" printf("нашли Amelia"); Чтобы заменить в тексте длинные медицинские термины их эквива- лентными обозначениями, следует воспользоваться правилом Electroencephalogram printf("EEG"); Если требуется подсчитать число строк в тексте, нужно распозна- вать признаки конца строк и увеличивать на единицу счетчик строк. lex использует стандартные для языка C управляющие пос- ледовательности символов, подобные \n для символа перевода строки. Для подсчета числа строк можно использовать правило \n lineno++; где lineno, как и другие C-переменные, описывается в секции оп- ределений, которую мы обсудим позднее. lex сохраняет каждую сопоставленную цепочку в массиве символов yytext[]. Вы можете распечатать содержимое этого массива или манипулировать им, как угодно. Иногда Ваше действие может сос- тоять из двух или большего числа C-операторов и Вы должны (или решили из соображений стиля и ясности) написать их на несколь- ких строках. Чтобы информировать lex о том, что действие отно- сится к одному правилу, надо просто заключить C-операторы в скобки. Например, чтобы подсчитать общее число всех цепочек цифр во входном тексте, печатать текущее общее число таких це- почек и выводить каждую из них, как только она обнаружена, мож- но воспользоваться такой записью: \+?[0-9]+ { digstrgcount++; printf("%d",digstrngcount); yytext [yyleng] = (char) 0; printf("%s",yytext); } Эта спецификация сопоставляется с цепочками цифр, перед кото- рыми, быть может, стоит знак плюс, поскольку операция ? обозна- чает, что знак плюс спереди не обязателен. Кроме того, будут учитываться и отрицательные цепочки цифр, так как последова- тельность, которая следует за знаком минус, -, будет сопостав- ляться с приведенным шаблоном. В следующем разделе показано, как отличить отрицательные целые числа от положительных. 2.2. Более сложные элементы lex'а lex предоставляет средства, позволяющие обрабатывать входной текст, пропуская его сквозь весьма хитроумные шаблоны. Среди этих средств - соглашения, определяющие, какую спецификацию выбрать, если на первый взгляд подходит более одной; функции, которые трансформируют один сопоставляемый шаблон в другой; ис- пользование определений и функций. Прежде чем перейти к упомя- нутым средствам, убедитесь в своем понимании изложенного выше, изучив пример, затрагивающий сразу несколько из рассмотренных вопросов. %% -[0-9]+ printf("отрицательное число"); \+?[0-9]+ printf("положительное число"); -0\.[0-9]+ { printf("отрицательная дробь, целая часть отсутствует"); } rail[ ]+road printf("railroad - одно слово"); crook printf("Это crook"); function subprogcount++; G[a-zA-Z]* { yytext [yyleng] = (char) 0; printf("G-слово: %s", yytext); Gstringcount++; } Первые три правила распознают отрицательные числа, положитель- ные числа и отрицательные дроби от -1 до 0. Использование + в конце каждой спецификации определяет, что рассматриваемое число составлено из одной или более цифр. Символ . является знаком операции, поэтому перед десятичной точкой в третьем правиле указан \. Каждое из трех следующих правил распознает особый шаблон. Спецификация для railroad сопоставляется в случаях, когда между двумя слогами слова вклинивается один или более пробелов. В случаях railroad и crook можно просто печатать си- ноним, а не выдавать сообщения. Правило, распознающее function, увеличивает на единицу счетчик. Последнее правило иллюстрирует несколько возможностей: Скобки задают последовательность действий на нескольких строках. Действие использует массив yytext[], в который заносит- ся распознанная цепочка символов; Спецификация использует символ *, обозначающий, что за G может следовать нуль или более букв. 2.2.1. Некоторые специфические свойства Кроме сохранения распознанной цепочки в yytext[], lex автомати- чески подсчитывает число сопоставленных символов и сохраняет его в переменной yyleng. Можно использовать эту переменную, чтобы обратиться к любому отдельному символу, уже помещенному в массив yytext[]. Напомним, что в языке C элементы массива нуме- руются, начиная с 0, поэтому, чтобы распечатать третью цифру в распознанном целом числе (если таковая имеется), следует напи- сать: [0-9]+ { if (yyleng > 2) printf("%c", yytext[2]); } Чтобы разрешить неоднозначности, к которым может приводить со- вокупность заданных пользователем спецификаций, lex следует нескольким соглашениям. Подобные неоднозначности возникают, например, в ситуациях, когда цепочка символов (скажем, зарезер- вированное слово), может сопоставляться с шаблонами из двух правил. В примере лексического анализатора, описанном ниже в разделе Совместное использование lex и yacc, зарезервированное слово end может сопоставляться как с шаблоном из второго прави- ла, так и с шаблоном из правила (седьмого) для идентификаторов. Примечание Если имеет место сопоставление с двумя или более специ- фикациями, выполняется действие, относящееся к первой из них. Поместив правило для end и других зарезервированных слов перед правилом для идентификаторов, мы гарантируем, что зарезервиро- ванные слова будут распознаваться должным образом. Другая потенциальная проблема может возникнуть в случаях, когда один из распознаваемых шаблонов является началом другого. Нап- ример, два последних правила в упомянутом лексическом анализа- торе служат для распознавания операций > и >=. Может возникнуть предположение, что в случае, когда текст содержит цепочку >=, лексический анализатор, обнаружив символ >, выполнит действие для шаблона >, но не станет читать следующий символ и не выпол- нит действие для >=. Примечание Сопоставляется самая длинная из подходящих цепочек сим- волов и выполняется соответствующее действие. В данном случае распознается операция >= и выполняется ассоции- рованное с ней действие. Другой пример: данное правило позволя- ет различить в C-программах операции + и ++. Наконец, еще одна трудность возникает в случае, когда анализа- тор должен прочитать символы вне искомой цепочки, поскольку не может быть уверенным в том, что в самом деле обнаружил ее, не прочитав дополнительные символы. Такие случаи доказывают важ- ность завершающего контекста. Классический пример - оператор DO в Фортране. При анализе оператора DO 50 k = 1, 20, 1 нельзя быть уверенным в том, что первая единица - это начальное значение управляющей переменной k, пока не прочитана первая за- пятая, поскольку оператор DO50k = 1 есть просто оператор присваивания. (Напомним, что в Фортране пробелы игнорируются.) Для обработки ситуаций, требующих опере- жающего просмотра, используется символ / (не путать с символом \), который обозначает, что следующая за ним последовательность является завершающим контекстом и ее не следует сохранять в yytext[], поскольку она не входит в саму лексему. Правило для распознавания DO в Фортране можно записать так: DO/[0-9 ]*[a-zA-Z0-9 ]+=[a-zA-Z0-9 ]+, printf("нашли DO"); Различные версии Фортрана налагают различные ограничения на длину идентификаторов, в том числе имен управляющих переменных цикла. Чтобы упростить пример, в правиле описывается имя произ- вольной длины. (На самом деле сделано еще несколько упрощающих предположений.) Для обозначения специального завершающего контекста - конца строки - lex использует знак операции $. (Это эквивалентно \n). Ниже приведено правило, которое игнорирует все пробелы и табу- ляции в конце строки: [ \t]+$ ; С другой стороны, если нужно сопоставить шаблон непременно с начала строки, lex предлагает операцию ^ (это пример начального контекста). Например, в утилите форматирования nroff требуется, чтобы строка никогда не начиналась с пробела, поэтому для про- верки входных данных nroff можно использовать такое правило: ^[ ] printf("ошибка: удалите начальные пробелы"); Наконец, для выполнения некоторых действий может потребоваться прочитать еще один символ, возвратить символ обратно для после- дующего повторного прочтения или вывести символ на устройство вывода. lex предоставляет для этих целей три функции - input(), unput(c) и output(c) соответственно. Один из способов пропус- тить все символы между двумя специальными символами, скажем, между парой двойных кавычек, заключается в использовании input(): \" while (input() != '"'); После того, как найдена первая двойная кавычка, сгенерированная программа a.out будет продолжать чтение всех последующих симво- лов без попыток сопоставления с шаблонами, пока не найдет вто- рую двойную кавычку. Для выполнения специальных операций ввода/вывода можно перепи- сать функции input(), unput(), и output(), используя стандарт- ные для языка C средства ввода/вывода. Эти и другие определен- ные программистом функции следует поместить в секцию подпрог- рамм. В таком случае новые подпрограммы заменят стандартные. Стандартная функция input(), в действительности, эквивалентна getchar(), а стандартная функция output() - putchar(). В lex'е имеется ряд подпрограмм, которые предоставляют возмож- ность многократной обработки цепочек символов. Это функции yymore() и yyless(n) и действие REJECT. Повторим, что текст, сопоставленный с некоторой спецификацией, помещается в массив yytext[]. В общем случае, после того как выполнено действие для данной спецификации, символы в yytext[] замещаются последующими символами входного потока, образующими следующую сопоставляемую цепочку. Функция yymore(), напротив, гарантирует, что последую- щие распознаваемые символы будут добавляться после тех, которые уже содержатся в yytext[]. Тем самым в случае, когда значимыми оказываются как одна цепочка символов, так и другая, более длинная, включающая первую, появляется возможность выполнить сначала одно действие, а потом другое, ассоциированное с длин- ной цепочкой. В качестве примера рассмотрим словарь, в котором чередуются английские слова и их русские эквиваленты. Слова (как англий- ские, так и русские) разделяются запятыми; запятые стоят также в начале и конце словаря. Требуется распечатать содержимое сло- варя в виде пар (английское слово, русский эквивалент). К цели ведет следующее правило: ,[^,]* { if (flag == 0) { flag = 1; yymore(); } else { flag = 0; yytext [yyleng] = (char) 0; printf ("%s\n", &yytext[1]); } } Предполагается, что переменная flag описана (и снабжена нулевым начальным значением) в секции определений; она нужна, чтобы от- личить цепочку символов, завершающуюся перед второй запятой (английское слово), от цепочки, завершающейся перед третьей за- пятой (русский эквивалент). Функция yyless(n) позволяет переустановить указатель конца об- работанных символов на символ, оказавшийся n-м в массиве yytext[]. Предположим, что мы занимаемся расшифровкой кода и уловка заключается в том, чтобы обрабатывать только половину символов в последовательности, заканчивающейся определенным символом, например, прописной или строчной буквой z. Достаточно воспользоваться правилом [a-yA-Y]+[Zz] { yyless(yyleng/2); ...обработка первой половины цепочки...} Наконец, действие REJECT упрощает обработку цепочек символов в случаях, когда они перекрываются или одна является частью дру- гой. Выполнение REJECT заключается в немедленном переходе к следующему правилу без изменения содержимого yytext[]. Напри- мер, для подсчета числа вхождений в тексте как цепочки символов snapdragon, так и ее подцепочки dragon, можно использовать пра- вило snapdragon { countflowers++; REJECT; } dragon countmonsters++; В следующем примере, иллюстрирующем частичное перекрытие двух шаблонов, подсчитывается число вхождений цепочек comedian и diana, причем правильно обрабатываются даже такие входные це почки, как comediana...: comedian { comiccount++; REJECT; } diana princesscount Отметим, что действия здесь могут быть существенно сложнее, чем просто увеличение счетчика. Как всегда, счетчики и другие необ- ходимые переменные описываются в секции определений, с которой начинается lex-спецификация. 2.2.2. Секция определений Секция определений может содержать конструкции разных видов, самыми важными из которых являются описания внешних объектов, операторы #include и сокращения. Напомним, что в принципе дан- ная секция необязательна, однако в большинстве случаев некото- рые определения необходимы. Описания внешних объектов имеют те же форму и смысл, что и в языке C. Они означают, что перемен- ные, глобально определенные где-то в другом месте (возможно, в другом исходном файле), будут доступны в сгенерированной lex- программе a.out. Рассмотрим определение из примера, который об- суждается ниже: extern int tokval; Целочисленное значение, присвоенное переменной, определенной таким образом, будет доступно в функции, вызывающей лексический анализатор, скажем, в функции разбора. Если, с другой стороны, нужно описать локальную переменную для использования в пределах последовательности действий из одного правила (например, управ- ляющую переменную цикла), ее описание можно поместить в начале самого действия, справа от открывающей скобки, {. Назначение оператора #include - то же, что и в языке C: вклю- чать в программу нужные файлы. Некоторые описания могут требо- ваться более чем в oодном исходном lex-файле, поэтому предпоч- тительно поместить их в один файл, включаемый в нужных случаях. Примером может служить использование lex'а совместно с yacc(1), который генерирует функции разбора, вызывающие лексический ана- лизатор. В такой ситуации следует включать файл y.tab.h, пос- кольку он может содержать операторы #define для имен лексем. Подобно описаниям, операторы #include должны содержаться между скобками %{ и %}: %{ #include "y.tab.h" extern int tokval; int lineno; %} В секции определений после разделителя %}, который завершает описания и операторы #include, можно поместить сокращения для регулярных выражений, используемые в секции правил. В левой части строки указывается сокращение, а в правой, отделенной од- ним или несколькими пробелами, - его описание. Сокращения, ис- пользуемые в правилах, обязательно должны быть заключены в фи- гурные скобки. Примечание Назначение сокращений - избежать излишних повторов при написании спецификаций и улучшить их читаемость. В качестве примера вернемся к lex-спецификации, рассмотренной в начале раздела Более сложные элементы lex'а. Использование сок- ращений упрощает последующие ссылки на цифры, буквы и пробелы. Сокращения особенно полезны, когда они встречаются в правилах несколько раз. D [0-9] L [a-zA-Z] B [ ] %% -{D}+ printf("отрицательное число"); \+?{D}+ printf("положительное число"); -0\.{D}+ printf("отрицательная дробь"); G{L}* printf("G-слово"); rail{B}+road printf("railroad - одно слово"); crook printf("не положено"); \"\./{B}+ printf(".\""); . . . . . . Применение последнего правила, несколько более сложного, чем остальные, гарантирует, что в конце предложения точка окажется перед кавычкой. Так, example". будет заменено на example." 2.2.3. Секция подпрограмм Смысл применения подпрограмм при использовании lex'а тот же, что и в случае других языков программирования. Действия, кото- рые должны встречаться в нескольких правилах, можно записать один раз и вызывать там, где требуется. Подпрограммы, как и сокращения, облегчают написание и чтение программ. Например, функция put_in_tabl(), обсуждаемая в следующем о разделе, - достойный кандидат в подпрограммы. Иногда подпрограмму помещают в эту секцию по методологическим соображениям - чтобы выделить некоторую часть действий или уп- ростить секцию правил, даже если данное действие используется только в одном правиле. В качестве примера рассмотрим следующую подпрограмму, которая пропускает комментарии в языке, подобном C, где комментарии выделяются символами /* и */: "/*" skipcmnts(); . . . /* Остальные правила */ %% skipcmnts () { for (;;) { while (input () != '*') ; if (input () != '/') { unput (yytext [yyleng-1]); } else return; } } В этом примере затронуты три интересных вопроса. Во-первых, функция unput(c) (возвратить последний прочитанный символ) нуж- на, чтобы правильно обработать комментарии, заканчивающиеся комбинацией символов **/. Во-вторых, выражение yytext [yyleng- 1] используется для выборки последнего прочитанного символа. В-третьих, в рассматриваемой подпрограмме предполагается, что комментарии не могут быть вложены. (Для языка C это действи- тельно так.) Если, в отличие от C, в исходном тексте коммента- рии вложены, после распознавания цепочки */, закрывающей внут- ренний комментарий, сгенерированная программа будет продолжать чтение оставшейся части комментариев, как если бы это была часть текста, которую надо распознавать. Другими примерами подпрограмм могут служить заданные програм- мистом варианты обсуждавшихся выше функций ввода/вывода input(), unput() и output(). Подобные функции могут использо ваться во многих программах, поэтому, вероятно, лучше всего бы ло бы поместить их в отдельный файл или библиотеку и вызыв по мере необходимости. При этом в секцию определений следовало бы поместить соответствующие операторы #include. 2.3. Совместное использование lex'а и yacc'а При работе над компилятором или программой, проверяющей пра- вильность исходного текста, целесообразно воспользоваться мощ ным инструментальным средством системы UNIX - yacc(1). yacc ге- нерирует функции синтаксического разбора и программы, анализи- рующие входной текст с целью убедиться в его синтаксической корректности. При разработке компиляторов объединение lex'а и yacc'а часто оказывается плодотворным. Даже если Вы пока не предполагаете использовать lex вместе с yacc, обязательно про- читайте этот раздел, так как он содержит информацию, интересную для всех пользователей lex'а. Процедура лексического анализа, которую генерирует lex, (но не файл, в котором она сохраняется), имеет имя yylex(). Это удоб- но, поскольку yacc обращается к лексическому анализатору как раз по этому имени. При использовании lex'а для создания лекси- ческого анализатора в компиляторе следует завершать каждое lex действие оператором return лексема, где лексема - введенное обозначение некоторого целочисленного значения. Возвращаемое значение лексемы указывает процедуре разбора, какую цепочку об- наружил лексический анализатор. Процедура разбора, которую yacc помещает в файл y.tab.c, вновь получает управление и выполняет очередное обращение к лексическому анализатору, когда ей требу- ется очередная лексема. При компиляции различные значения обозначают типы лексем, то есть показывают, является ли лексема определенным зарезервиро- ванным словом, идентификатором, константой, арифметической опе- рацией или операцией сравнения. Во всех перечисленных случаях, кроме первого, анализатор, кроме того, должен указать точное значение лексемы: какой именно идентификатор обнаружен, какая константа, скажем, 10 или 1812, какая арифметическая операция, + или * (умножение), какая операция сравнения, = или >. Расс- мотрим следующий фрагмент lex-спецификации лексического анали- затора для некоторого языка программирования, несколько напоми- нающего язык Ада: begin return (BEGIn); end return (END); while return (WHILE); if return (IF); package return (PACKAGE); reverse return (REVERSE); loop return (LOOP); [a-zA-Z][a-zA-Z0-9]* { tokval = put_in_tabl (); return (IDENTIFIER); } [0-9]+ { tokval = put_in_tabl (); return (INTEGER); } \+ { tokval = PLUS; return (ARITHOP); } \- { tokval = MINUS return (ARITHOP); } > GREATER; return = RELOP); } >= { tokval = GREATEREQL; return = RELOP); } Классы лексем и значения, присваиваемые переменной tokval, обозначены именованными целочисленными константами, что облег- чает понимание и модификацию правил. Соответствие между именами и значениями констант устанавливается при помощи операторов #define в C-процедуре разбора. Пример: #define BEGIn 1 #define END 2 . . . #define PLUS 7 . . . (В имени BEGIn последняя буква сделана строчной, поскольку имя BEGIN зарезервировано lex'ом.) При использовании yacc'а целесо- образно вставить оператор #include "y.tab.h" в секцию определений lex-спецификаций. Файл y.tab.h содержит операторы #define, связывающие имена лексем, такие, как BEGIn, END и т.д. с целочисленными значениями, имеющими смысл для сге- нерированной процедуры разбора. В нашем примере для того, чтобы однозначно задать зарезервиро- ванное слово, достаточно возвращаемого значения. Для других ти- пов лексем значение лексемы сохраняется в определенной програм- мистом переменной tokval. Эта переменная описывается в секции определений как глобальная, доступная и процедуре лексического анализа, и процедуре синтаксического разбора. yacc для этих же целей предоставляет переменную yylval. Отметим, что в примере показано два способа установки значения переменной tokval. В соответствии с первым способом функция put_in_tabl() заносит имя и тип идентификатора или константы в таблицу символов, к которой компилятор имеет доступ на этой и следующих стадиях процесса компиляции. Кроме того, put_in_tabl() выдает в качестве результата имя идентификатора или значение константы; этот результат присваивается переменной tokval. Предполагается, что функция put_in_tabl() помещается разработчиком компилятора в секцию подпрограмм. При втором спо- собе, например, в нескольких последних действиях примера, пере- менной tokval присваивается определенное число, обозначающее, какую операцию распознал анализатор. Если PLUS в соответствии с приведенным выше оператором #define обозначает семерку, то при обнаружении знака + переменной tokval будет присвоено значение 7, характеризующее +. Значение, возвращаемое процедуре разбора, обозначает целый класс операций (в нашем примере - значения ARITHOP и RELOP). 3. ВЫПОЛНЕНИЕ LEX'А В СИСТЕМЕ UNIX Прежде чем продвигаться дальше, вернемся на некоторое время к рисунку в начале главы. Для порождения C-текста лексического анализатора следует выполнить команду lex файл где файл содержащит lex-спецификацию. Обычно в качестве имени файла берется lex.l, однако в принципе имя файла может быть лю- бым. Порожденный lex'ом выходной файл будет автоматически наз- ван lex.yy.c. Он содержит созданную C-программу лексического анализа, которую следует откомпилировать и выполнить редактиро- вание связей с обязательным подключением библиотеки lex'a libl.a, что достигается указанием опции -ll: cc lex.yy.c -ll Библиотека предоставляет недостающую программу main(), которая по имени yylex вызывает лексический анализатор, так что созда- вать свою собственную программу main() нет необходимости. Если lex-спецификация состоит из нескольких файлов, можно для каждого из них запустить lex, обязательно переименовывая ре- зультирующий файл lex.yy.c [при помощи команды mv(1)] перед следующим запуском lex'а. В противном случае каждый следующий результат будет затирать предыдущий. После того как все .c-фай- лы сгенерированы, можно скомпилировать их все разом посредством одной командной строки. Если выполняемый файл a.out порожден, с его помощью можно проа- нализировать любой входной текст. Предположим, текст помещен в файл с именем textin (имя выбирается произвольно). Лексический анализатор по умолчанию осуществляет ввод с терминала. Чтобы использовать файл textin, достаточно переназначить ввод: a.out < textin По умолчанию и вывод осуществляется на терминал, но его также можно переназначить: a.out < textin > textout При использовании lex'а совместно с yacc'ом любой из инструмен- тов может быть запущен первым. Команды yacc -d grammar.y lex lex.l формируют процедуру разбора в файле y.tab.c. (Если указана оп- ция -d, создается файл y.tab.h., который содержит операторы #define, связывающие назначенные yacc'ом целочисленные значения типов лексем с определенными пользователем именами лексем). Чтобы откомпилировать порожденные файлы и отредактировать свя- зи, введите командную строку cc lex.yy.c y.tab.c -ly -ll Заметим, что библиотека yacc'а загружается (опция -ly) перед библиотекой lex'а (опция -ll), что гарантирует использование той программы main(), которая вызывает процедуру разбора. У команды lex есть несколько допустимых опций, которые следует указывать между именем команды lex и именем файла-аргумента. Для того, чтобы lex выводил сгенерированную C-программу lex.yy.c на терминал (устройство вывода, заданное по умолча- нию), используется опция -t: lex -t lex.l По опции -v распечатывается небольшая статистическая сводка, характеризующая так называемый конечный автомат, который реали- зует порожденная lex'ом C-программа lex.yy.c. Для представления конечного автомата lex использует таблицу (двумерный массив в C). Максимально возможное число состояний конечного автомата по умолчанию устанавливается равным 500. Ес- ли lex-спецификация содержит много правил или очень сложные правила, может потребоваться большее число состояний. Увеличе- ние максимального числа состояний достигается добавлением к секции определений строки вида %n 700 Подобная строка заставляет lex сделать таблицу достаточно боль- шой, чтобы вместить до 700 состояний. (Опция -v позволит уз- нать, какое число состояний было фактически использовано). Для того, чтобы увеличить максимально допустимое число переходов между состояниями с подразумеваемого значения 2000, предусмот- рен параметр a: %a 2800 В заключение рекомендуем изучить статью lex(1) из Справочника пользователя, в которой содержится список всех опций, предус- мотренных у данной команды. Описание нотации регулярных выраже- ний можно найти, например, в статье ed(1) Справочника пользова- теля. Вы прочитали введение в разработку lex-программ. Чтобы овладеть lex'ом, как и любым другим программистским инструментом, нужно им пользоваться - чем больше, тем лучше.