Аргументы командной строки Lex
Lex понимает только четыре опции.
-с
Создать выходной файл на языке С. По умолчанию.
-n
Подавить создание итоговой статистики. По умолчанию.
-t
Направить программу в поток стандартного вывода. Это способ переименовать файл.
-v
Направить статистический отчет Lex в поток стандартного вывода.
[ ] [ ] [ ]
Файл спецификации Lex
Спецификации Lex разделяются на три блока, и граница между ними состоит из строки с двумя символами процента (%%) в начале. Первый раздел - определения. Второй - раздел правил Lex, и заключительный, третий, - раздел подпрограмм пользователя. Раздел правил Lex должен присутствовать обязательно. В случае, если нет никаких определений, первыми символами в спецификации должны быть ограничители %%.
Файл спецификаций Yacc
Файл спецификаций Yacc во многом похож на аналогичный файл Lex, но несколько сложнее. В нем существует раздел объявлений, раздел правил и раздел программ. Они аналогичны разделам определений, правил и подпрограмм файла спецификаций Lex. Каждый раздел точно также отделяется двойным символом процента. Также как и в Lex, обязательно должен присутствовать раздел правил, в случае отсутствия любых объявлений файл должен начаться с символов %%.
Функции и переменные Lex
Lex создает несколько функций, которые являются доступными программисту. Кроме переменных yytext и yyleng существует переменная yyin. Это дескриптор файла, который используется для операций ввода.
Первой рассмотрим функцию yylex. Она не имеет аргументов и возвращает целое число. По достижении конца файла возвращается ноль, иначе возвращается считанная лексема (для использования с Yacc). Обращение к этой функции осуществляется для вызова лексического анализатора.
Функция yymore также не имеет аргументов и возвращает целое число. При вызове этой функции Lex конкатенирует следующее регулярное выражение к yytext.
Функция yyless принимает в качестве аргумента целое число и возвращает целое число. При ее вызове Lex сохраняет оканчивающуюся null-указателем строку из определенного количества символов. Эти символы игнорируются при анализе.
Функция ввода не имеет аргументов и возвращает целое число. Эта подпрограмма возвращает следующий символ из потока ввода. Символ удаляется из входного потока.
Функция unput принимает в качестве аргумента целое число и возвращает определенный символ в начало входного потока.
Две функции доступны только через библиотеку Lex, но можно разработать свои собственные функции и включить их в раздел подпрограмм.
Все программы С требуют наличия функции main. Функция yywrap не имеет аргументов и используется для обработки конца файла. Обычно она просто возвращает 1, чтобы сообщить Lex о окончании ввода. Чтобы переместиться в новый файл, необходимо связать yyin с новым файлом и заставить yywrap возвратить 0.
Функции и переменные Yacc
Yacc создает для Вас функцию yyparse. Эта функция не имеет аргументов и возвращает 0 или 1 в случае успеха или отказа. Все используемые переменные (yytext, yylval и так далее) определены в лексическом анализаторе.
Интеграция Lex и Yacc Lex очень часто используется в качестве лексического анализатора для Yacc. Эти две программы были специально разработаны для эффективного совместного использования. Обычно, при определении лексем в Yacc ожидается, что анализатор yylex возвратит эти лексемы. Эти зависимости несложно установить. В Yacc можно определить строку типа
% token INTEGER
Эта лексема затем используется в грамматике. В Lex необходимо определить способ возврата этого целого числа:
%{ #include "y. tab. h" %} %% [1-9][0-9]* { yylval=atoi(yytext); return INTEGER;}
Необходимо включить заголовок в вывод Lex таким образом, чтобы значения лексем корректно передавались между лексическим и синтаксическим анализатором. Также необходимо сформировать вашу грамматику, используя опцию -d для Yacc, чтобы создать соответствующий файл заголовка.
[ ] [ ] [ ]
Функции Lex
|
Использовать действие для следующего правила этого регулярного выражения. Должно быть единственным в поле действия
ECHO;
Вывести значение yytext в поток стандартного вывода.
REJECT;
Продолжить до следующего выражения, соответствующего текущему вводу
BEGIN состояние;
Переключить соответствующую определенному состоянию переменную.
Lex пытается найти соответствие самой длинной строке, которая соответствует определенному регулярному выражению. Если найдено соответствие двум регулярным выражениям одной длины, то используется первое определенное выражение. REJECT заставить искать соответствие для второго или последующих регулярных выражений.
Использование Lex
После разработки вашей спецификации Lex используйте команду lex, чтобы создать модуль С. Команда задается в виде:
lex word.l
Принято использовать расширение .l для исходных файлов Lex. Полученный выходной файл lex.yy.c будет состоять в нашем случае из 317 строк исходного кода С. Исследовав этот код, мы обнаружим, что процесс лексического анализа управляется при помощи таблицы. Созданная функция ууlех() осуществляет собственно анализ.
Можно легко создать программу, компилируя этот файл С и подключая библиотеку Lex: cclex.yy.c
При этом создается выполняемый файл имя файла с a. out. (Можно определить и другое помощью опции процедуру, -о.) Библиотека Lex по умолчанию подключает основную которая вызывает ууваша lех (). Скомпонованный в результате выполняемый файл - программа.
После разработки вашей спецификации Lex используйте команду lex, чтобы создать модуль С. Команда задается в виде:
lex word.l
Принято использовать расширение .l для исходных файлов Lex. Полученный выходной файл lex.yy.c будет состоять в нашем случае из 317 строк исходного кода С. Исследовав этот код, мы обнаружим, что процесс лексического анализа управляется при помощи таблицы. Созданная функция ууlех() осуществляет собственно анализ.
Можно легко создать программу, компилируя этот файл С и подключая библиотеку Lex: cclex.yy.c
При этом создается выполняемый файл имя файла с a. out. (Можно определить и другое помощью опции процедуру, -о.) Библиотека Lex по умолчанию подключает основную которая вызывает ууваша lех (). Скомпонованный в результате выполняемый файл - программа.
Использование Yacc
Можно откомпилировать спецификации Yacc в файл с помощью команды:
уасс example.y
Обычно для исходных файлов Yacc используется расширение. у.
При этом будет создан файл у.tab.с из 508 строк исходного кода С, соответствующего предыдущему примеру. Можно также создать файл заголовка, y.tab.h, указав опцию -d. В файле с исходным кодом С находится функция уурагsе(), являющаяся собственно синтаксическим анализатором. Она не имеет аргументов и возвращает 0 при удачном проведении анализа и 1 при возникновении синтаксической ошибки. Можно откомпилировать этот файл:
сс у. tab. с -lу
Будет создан выполняемый файл a.out. Библиотека Yacc подключает по умолчанию стандартную функцию main () и все дополнительные подпрограммы, необходимые для выполнения. При этом не подключается подпрограмма передачи лексемы в синтаксический анализатор уу1ех (). Необходимо или использовать созданный Lex лексический анализатор, или написать свой собственный.
Командная строка Yacc
Yacc имеет несколько опций, представленных в таблице
-b cтрока
Использовать строку в качестве префикса файла вместо у
-d
Cоздать файл заголовка у.tab.h для использования лексическим анализатором
-l
Cоздать код, который не использует конструкции #line
-p cтрока
Использовать строку в качестве префикса для переменных вместо уу
-t
Изменить код, чтобы включить условные отладочные выражения. По умолчанию
-v
Cоздать файл, содержащий статистику синтаксического анализа
[ ] [ ] [ ]
Лексический анализ
Лексический анализ - это процесс простого извлечения слов из текста и их последующего анализа. В данном случае слово является строкой, которая соответствует регулярному выражению. UNIX предоставляет инструмент, который в состоянии создавать использующиеся в разных режимах лексические анализаторы.
Можно подумать, что намного проще написать свой собственный лексический анализатор,- ведь для опытного программиста это довольно простая задача. Но, рассмотрев спецификации Lex, вы найдете их использование несложным, тем более, что получаемый в результате код работает достаточно быстро.
[ ] [ ]
Объявления таблиц Lex
Поскольку Lex управляет процессом лексического анализа с помощью таблиц, на размер грамматики наложены некоторые ограничения. Чтобы определить, насколько Вы приблизились к этим ограничениям, запустите Lex с опцией -V, при этом создается дамп размеров таблицы.
Можно заменить эти размеры таблиц в разделе определений спецификаций Lex, как это представлено в таблице
%а
2000
Количество переходов Lex
%с
1000
Количество вершин дерева синтаксического анализа
%k
1000
Количество упакованных классов символов
%n
500
Количество разрешенных состояний
%о
3000
Размер вводимого массива
%р
2500
Количество разрешенных позиций в Lex
Можно использовать эти декларации, сопровождаемые числом для изменения размерив таблицы. Можно также объявить, каким образом будет сохраняться значение yytext. Если в определениях находится %аггау, то yytext - символьный массив. Если присутствует %pointer, yytext является указателем на символ. В обоих случаях, yytext всегда оканчивается null-указателем.
Объявления Yacc
В разделе объявлений Yacc определяются лексемы, а также приоритет операторов и начальные символы для синтаксического анализа. Для объявления значений используются семь ключевых слов. Конструкция %token определяет лексемы, используемые в синтаксическом анализаторе. Допускается дополнительно определять поле объединения в угловых скобках, это объединение передает информацию от лексического анализатора к синтаксическому и ниже будет описано более подробно.
После дополнительного поля можно перечислять имена лексем, при желании сопровождая каждое из них номером. Эти лексемы будут преобразованы в значения #define и использованы в коде С для определения конструкций. Например:
%token WORD 0 SEHTENCE MONTH
Определены три лексемы, которые возвращаются ууlех() в случае, если лексема WORD принимает значение целого числа 0. %left и %right определяют старшинство лексем слева направо или справа налево. Синтаксис такой же, что и для %token. Директивы порядка старшинства в исходном тексте Yacc определяет старшинство операторов. Конструкция %nonassoc определяет лексемы, которые не должны использоваться при любой ассоциации. Конструкция %type определяет тип лексем, которые не являются печатными (нетерминальные лексемы). Поскольку эти лексемы не печатаются, им нельзя присваивать числовые значения.
Остальные конструкции объявлений немного различны. Конструкция %start определяет нетерминальный символ, который нужно рассматривать как начальный. Это должна быть самая большая, чаще всего употребляемая структура, определенная в грамматике. Если символ %start не определен, Yacc по умолчанию принимает его равным первому символу первого правила.
Конструкция %union объявляется аналогично объединению в С. Например, можно объявить объединение:
%union { long vall; short sval; char* string; }
При этом изменяется определение структуры yylval, которая используется для передачи данных между синтаксическим и лексическим анализаторами. После объявления объединения можно расставить метки в строках %token. В случае возвращения данных из лексического анализатора нужно объявить лексемы следующим образом:
%token <vall> TIME %token <строка> WORD %token <sval> MONTH DATE
Yacc автоматически сохраняет эти поля объединения для проверки соответствия типов в результирующей грамматике.
Определения Lex
Определением является имя, сопровождаемое образцом для замены. Все имена должны начинаться в первом столбце, поскольку любые строки с пробелом в нем обрабатываются как строки исходного кода С и без изменений записываются в выходной файл. Это свойство передачи исходных кодов позволяет объявлять переменные, препроцессорные директивы С и т.д.
Кроме того, можно сгруппировать весь исходный код С в ограничители %{... %}. Тогда весь код, расположенный между этими символами, будет без изменении записан в выходный файл.
Эти определения не обязательны для работы Lex, но весьма полезны. Если один и тот же образец замены используется в различных правилах, то его не нужно повторять. Аналогично, если существует необходимость изменить определение, нужно откорректировать только один фрагмент, а не несколько. Например, можно определить как
DIGIT 0-9
Затем можно поставить в соответствие этому типу и целые, и десятичные числа:
/* порядковое число*/ {DIGIT}+ /* десятичное число*/ {DIGIT}+.{DIGIT}*
Допускается указывать объявления Lex в разделе определений. Они включают спецификации размеров таблиц, состояний и определений для текстового указателя.
Подпрограммы Lex
Используя перечисленные ниже правила Lex можно определять необходимые любые подпрограммы, включая подпрограмму main. Этот код без изменений записывается в файл lex.yy.c и компилируется обычным способом. Таким образом можно полностью написать программу внутри файла спецификаций Lex.
Правила грамматики Yacc
В основе работы Yacc лежит определение грамматики. Грамматика оговаривает набор правил, которые формулируются для построения связанного выражения. Формат:
Цель: Тело
Цель - это объект, который нужно сформировать, а тело - ото определение способа формирования. Тело может состоять из нескольких лексем, как полученных из лексического анализатора терминальных лексем, так и нетерминальных лексем. (Нетерминальные лексемы указывается в левой части правила.) Вы определяете список лексем, отделяемых пробелами. Можно определять альтернативные списки лексем в разных строках, указывая в начале каждой строки вертикальную черту. Кроме того, в фигурных скобках записывается действие, которое выполняется при идентифицикации лексемы. Каждое правило должно оканчиваться точкой с запятой.
Допускается определять символьные литералы, включая их в одиночные кавычки. В качестве примера приведем лексему высшего уровня для грамматики Yacc:
grammar: declarations MARK rules tail;
MARK соответствует символу %%. Так как раздел программ не является обязательным, MARK включена в определение правила tail.
Более сложное правило поможет определить действие при поиске соответствия. Правила могут быть довольно сложными, поэтому легко совершить ошибку. Наиболее частыми ошибками являются конфликты при синтаксическом анализе методом сдвига/уменьшения. Это означает, что синтаксический анализатор не в состоянии уверенно определить, передать ли текуший блок информации конструкции с более высоким приоритетом или продолжать набирать данные в стек.
Обычно это является результатом неоднозначной, двусмысленной грамматики. Yacc по-прежнему в состоянии создать синтаксический анализатор для этой грамматики, но результаты его работы могут быть непредсказуемы.
Правила Lex
Правила Lex являются его сутью. Правила - это расширенные регулярные выражения и действия. Каждое регулярное выражение имеет соответствующее действие, и этому действию соответствует код С. Действие может быть довольно сложным и заключаться в фигурные скобки. С помощью вертикальной полосы можно разбить большое регулярное выражение на несколько строк.
При определении соответствия некоторому действию происходит несколько операций. Сначала переменной yytext присваивается номер строки, которая соответствует регулярному выражению и завершается null-указателем. Затем переменной yyleng присваивается длина строки. В заключение выполняются все необходимые действия. Как показано в табл. 30. 2, в Lex определены четыре специальных действия. Таблица 30.
программа Valspeak
Забавное использование Lex: Valspeak. Много лет назад была написана пара программ, преобразующих нормальный английский текст к так называемому джайву (jive) или провинциальному сленгу. Эти программы были написаны с помощью Lex. Можно использовать Lex для преобразования текста из известного входного формата в другой выходной формат. Ниже приведена программа лексического преобразования к провинциальному сленгу.
Исходный код Lex для Valspeak
Т [" .!?,"]* % "bad" printf("mean"); "big" printf("bitchin'est"); "body" printf("bod"); "bore" printf("drag"); "car" printf("rod"); "dirty" printf("grodie"); "filthy" printf("grodie to thuh max"); "food" printf("munchies"); "girl" printf("chick"); "good" printf("bitchin"); "great" printf("awesum"); "gross" printf("grodie"); "guy" printf("dude"); "her" printf("that chick"); "him" printf("that dude"); "house" print ("pad"); "interesting" printf ("cool"); "large" printf("awesum"); "leave" printf("blow"); "man" printf("nerd "); "meeting" printf("party"); "movie" printf("flick"); "music" printf("tunes"); "neat" printf("keen"); "nice" printf("class"); "no way" printf("just no way"); "people" printf("guys"); "really" printf("totally"); "strange" printf("freaky"); "the" printf("thuh"); "very" printf("super"); "want" printf("want"); "weird" printf("far ouf"); "yes" printf("fer shure"); "But" printf("Man,"); "He" printf("That dude"); "I like" printf("I can dig"); "No," printf("Like, no way,"); "Sir" printf("Man"); "She" printf("That fox"); "This" printf("Like, ya know, this"); "There" printf("Like, there"); "We" printf("Us guys"); "Yes," printf("Like,");
"can be" "can't be" "should have been" "shouldn't have been" "should be" "shouldn't be" "was" "wasn't" "will be" "won't be"
ing printf ("in");
"is" { ECHO; switch (rand () % 4) { case 0: printf ("like, ya know,"); break; case 1: printf(""); break; case 2: printf ("like wow!"); break; case 3: printf ("ya know, like,"); break; } }
"maybe" { switch( rand () % 5) { case 0: printf("if yon're a Pisces"); break; case 1: printf ("if the moon is full"); break; case 2: printf ("if the vibes are right"); break; case 3: printf("when you get the feeling"); break; case 5: printf("maybe"); break; } }
"," { switch (rand () % 6) { case 0: printf(", like,"); break; case 1: printf(", fer shure,"); break; case 2: printf(", like, wow,"); break; case 3: printf(", oh, baby,"); break; case 4: printf(", man,"); break; case 5: printf(", mostly, "); break; } }
"!" { switch (rand () % 3) { case 0: printf("! Gag me with a SPOOOOON!"); break; case 1: printf("! Gag me with a pitchfork!"); break; case 2: printf("! Oh, wow!"); } }
. ECHO; \n ECHO;
%
main () { srand(getpid()); yylex(); }
Исходный код легко читается и понимается - при обнаружении некоторых слов или знаков пунктуации происходит простая замена. Например, слово house заменяется на pad. Если я ввожу:
This is my house boat, sir!
To получаю в ответ:
Like, ya know, this is my pad boat, like, sir! Gag me with a SPOOOOON!
Эта программа Lex использует генератор случайных чисел, поэтому при последовательных вводах одной и той же строки скорее всего будут получены различные результаты. Вводя во второй раз ту же строку, получим в результате:
Like, ya know, this is like wow! My pad boat, fer shure,sir! Gag my with a pitch work!
Шутки ради я обработал преамбулу Конституции с помощью Valspeak, чтобы посмотреть, какой вид имел бы главный закон страны, будь Джеймс Мэдисон родом из какой-то долины Сими:
We, like, the guys of thuh United States, fer shure, in order to form a more perfect Union, like, wow, establish justice, fer shure, insure domestic tranquility, like, wow, provide for the common defense, fer shure, promote thuh general welfare, man, and secure the blessin's of liberty to ourselves and our posterity do ordain and establish this Constitution for thuh united States of America.
Я думаю, что подобный документ оскорбил бы вековые традиции юриспруденции.
[ ] [ ] [ ]
Программы Yacc
После определения правил можно добавить код С к файлу y. tab. c (это необязательная операция). Следует указать в начале этого кода ограничитель %% и скопировать его дословно в файл. Обычно, в этом сегменте объявляются функция анализа ввода уу1ех (). Можно также определить функцию main() и функцию завершения процесса ууеrrоr (). В случае определения всех трех функций нет необходимости подключать библиотеку Yacc или синтаксический анализатор Lex для компилирования программы.
Простейший пример Lex
Можно использовать Lex для извлечения слов из файла с последующей распечаткой их по одному в каждой строке. Это полезно при сортировке ввода для определения слова, чаще всего используемого в тексте. Нижеприведенный код Lex решает эту задачу:
word [A-Za-z][-A-Za-z']* eol \n %% {word} { printf ("%s\n", yytext);} {eol} ; . ; %%
Первым в структуре спецификаций Lex располагается набор определений. В этом примере я определил "word" как произвольную последовательность символов. После первого символа допускается наличие черточки или апострофа. Согласно определению, сокращенные и написанные через дефис слова рассматриваются как одиночные, не разделенные на отдельные компоненты. Как видим, определение регулярного выражения в качестве "word" довольно несложно.
Я также включаю определение конца строки. И таким образом получаю возможность отбрасывать символ конца строки. В противном случае, из-за того, что Lex тупо передает любые символы, которые не фильтруются потоком стандартного вывода, на экране появится множество посторонних новых строк. Аналогичным образом я объявляю любые другие игнорируемые непечатаемые символы. По такой схеме можно игнорировать, к примеру, знаки пунктуации.
После создания такого программного файла я обработал им черновик моей предыдущей главы. Первые 10 строк вывода приведены ниже:
Программа написана давайте сделаем ее быстрее после удаления всех ошибок
Ясно, что, подсчитывая слова, я должен отсортировать их и обработать с помощью uniq -с:
wordextract | sort | uniq -с
Результат будет получен весьма интересный, так как сортировка чувствительна к регистру и поэтому необходимо использовать tr для преобразования всего текста в нижний регистр перед сортировкой. Также необходимо отсортировать вывод по частоте использования слов. Десятью наиболее часто используемыми словами в предыдущей главе будут (английский вариант):
291 the 129 of 120 а 113 to 104 is 81 and 77 i 69 you 64 code 62 for
Здесь нет ничего удивительного. Я выполнил эти вычисления, используя конвейер. Более профессиональным использованием Lex была бы возможность преобразовать код Lex в одну программу С.
[ ] [ ] [ ]
Простейший пример Yacc
В качестве простейшего пример приведем "очень сложный", но короткий сценарий Yacc:
%token WORD % DOCUMENT : WORD | DOCUMENT WORD; { printf ("Have a document\n"); }
Для работы также необходим лексический анализатор, который возвращает слова:
% { #Include "y. tab. h" %} % . {return WORD;}
Этот пример печатает строку "Have a document" для каждого символа в документе.
[ ] [ ] [ ]
Синтаксический анализ
Лексический анализатор - лишь небольшая часть программы, обрабатывающей ввод. Следующая, более важная, задача состоит в том, чтобы создать синтаксический анализатор.
Как обсуждалось ранее, при синтаксическом анализе возможно использование двух методов: синтаксического анализа со сдвигом и уменьшением и нисходящего парсинга. Создание синтаксического анализатора, который корректно работает с грамматикой, задача намного более трудная, чем разработка простого лексического анализатора. UNIX предоставляет инструмент, который в состоянии написать синтаксический анализатор вместо Вас. Yacc (или Yet Another Compiler Compiler - Еще Один Транслятор Трансляторов) обрабатывает четко сформулированную грамматику и создает синтаксический анализатор, который понимает эту грамматику.
[ ] [ ] [ ]
Состояния Lex
Иногда существует необходимость отслеживать состояние ввода и, в зависимости от состояния, выполнять различные типы замен или действий. Хорошим примером является комментарий в С - если считанные лексемы принадлежат комментарию, то они игнорируются. Поскольку комментарии могут распространяться на несколько строк, необходимо изменять состояние.
Состояние определяется с помощью ключевых символов %s. При определении зависимых от состояния правил необходимо указывать в угловых скобках определенное состояние перед регулярным выражением. При объявлении состояния, по умолчанию оно рассматривается неактивным. Например:
%s COMMENT %% <COMMENT>. {} <COMMENT>"/*" {} <COMMENT>"*/" { BEGIN INITIAL;} "/* " { BEGIN COMMENT;}
Я хочу обрабатывать все символы, кроме комментариев и ограничителей комментариев, поэтому при обнаружении начала комментария вводится состояние COMMENT. Любой символ в состоянии COMMENT игнорируется до тех пор, пока не будет достигнут конца комментария. Затем восстанавливается начальное состояние. Если бы я хотел начать обработку в режиме COMMENT, следовало бы указать следующие строки:
%{ BEGIN COMMENT; %}
в разделе определений лексических спецификаций.
[ ] [ ] [ ]
