Глава 1. Основные спецификации
Глава 5. Двусмысленность и конфликты
Глава 9. Рекомендации по подготовке спецификаций
Глава 10. Дополнительные возможности
Приложение B. Входной синтаксис Yacc-а
Приложение C. Продвинутый пример
Приложение D. Старые возможности, поддерживаемые, но не рекомендуемые
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Входные данные компьютерных программ обычно имеют некоторую структуру; на самом деле, для каждой компьютерной программы, которая производит ввод можно определить "входной язык", который она воспринимает. Входной язык может быть комплексным, таким, как язык программирования или простой, такой как последовательность чисел. К сожалению, обычные средства ввода ограничены, сложны в использовании, и часто неспособны проверять свои входные данные на правильность.
Yacc обеспечивает общее средство для описания входных данных компьютерных программ. Пользователь Yacc указывает структуры входных данных вместе с кодом, вызываемом при распознавании каждой такой структуры. Yacc преобразовывает такие спецификации в подпрограммы, поддерживающие процесс ввода данных; часто удобно обрабатывать этой подпрограммой большую часть управления (flow control) в приложении.
Подпрограмма ввода, произведенная Yacc-ом вызывает написанную пользователем процедуру, возвращающую следующий токен. Таким образом, пользователь может определить входные данные своей программы с точки зрения отдельных входных символов или с точки зрения конструкций более высокого уровня, таких как имен или чисел. Пользовательская процедура также может обрабатывать такие идиоматические особенности, как соглашения о комментариях и продолжениях строки, которые обычно не подпадают под простые грамматические описания.
В дополнение к компиляторам C, APL, Pascal, RATFOR и т.д., Yacc также использовался для менее традиционных языков, включающих язык фотонаборных автоматов, нескольких языков для настольных калькуляторов, системы исправления документов и системы отладки Фортрана.
[ Содержание ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Yacc обеспечивает общее средство для придания структуры входным данным компьютерных программ. Пользователь Yacc-а готовит спецификацию процесса ввода; она включает в себя правила, описывающие структуру входных данных, код, вызываемый, когда распознаны эти правила, и низкоуровневая процедура для простого ввода. Затем Yacc генерирует функцию, контролирующую процесс ввода
Эта функция, называемая синтаксическим анализатором, вызывает пользовательскую низкоуровневую процедуру простого ввода (лексический анализатор) для извлекания элементарных токенов из входного потока. Эти токены организованы в соответсвии с правилами структур входных данных, называемых грамматическими правилами; когда одно из этих правил распознается, вызывается пользовательский код для этого правила, или действие; действия способны возвращать значения и использовать значения других действий.
Yacc написан на переносимом диалекте C1 и акции и выходные подпрограммы также на C. Больее того, многие синтаксические соглашения Yacc-а вытекают из C.
Сердцем спецификаций ввода является коллекция грамматических правил. Каждое правило описывает допустимую структуру и дает ей имя. Hапример, грамматическое правило может выглядеть так:
date : month_name day ',' year;
Здесь date, month_name, day и year представляют собой структуры, of interest для процесса ввода; предположительно month_name, day и year определены где-либо еще. Запятая "," заключена в одиночные кавычки; это значит, что кавычки должны появиться в тексте буквально. Двоеточие и точка с запятой служат просто как знаки препинания в правиле и не имеют никакого значения при контроле входных данных. Таким образом, при должных определениях ввод
July 4, 1776
будет соответствовать вышеуказанному правилу.
Важная часть процесса ввода выполняется лексическим анализатором. Процедура пользователя читает входной поток, распознает структуры низкого уровня и передает эти токены парсеру. По историческим причинам структуры, распознаваемые парсером называются нетерминальным символом. Во избежание недоразумений терминальные символы обычно будут называться токенами.
При принятии решения, распознавать ли структуры используя лексический анализатор или грамматические правила, нет слишком большой свободы действий. Hапример, в вышеприведенном примере могут использоваться следующие правила:
month_name : 'J' 'a' 'n'; month_name : 'F' 'e' 'b'; . . . month_name : 'D' 'e' 'c';
Лексическому анализатору надо будет распознать только отдельные буквы, и month_name будет нетерминальным символом. Такие низкоуровневые правила ведут к потере времени и места и могут настолько усложнить спецификации, что Yacc не сможет с ними справиться. Обычно лексический анализатор распознает названия месяцев и возвращает признак того, что найден month_name; в этом случае month_name будет токеном.
Литеральные символы, такие как "," также должны проходить через лексический анализатор и также считаются токенами.
Файлы спецификации очень гибки. Относительно просто добавить к вышеприведенному примеру правило
date : month '/' day '/' year;
позволяющее
7 / 4 / 1776
в качестве синонима к
July 4, 1776
В большинстве случаев это новое правило может быть легко вставлено в работающую систему с минимальными усилиями и незначительной опасностью разрушения существующих входных данных.
Входные данные могут не соответствовать спецификациям. Эти ошибки данных определяются настолько рано, насколько возможно при чтении слева-направо; таким образом, не только в значительной степени понижается вероятность чтения и работы с неправильными данными, но и плохие данные могут быть быстро обнаружены. Обработка ошибок, обеспечиваемая как часть спецификаций входных данных, позволяет повторный ввод неправильных данных или продолжение процесса ввода после пропуска неверных данных.
В некоторых случаях Yacc отказывается генерировать парсер с некоторыми наборами спецификаций. Hапример, спецификации могут быть противоречивыми, или могут требовать более мощного механизма распознавания, чем тот, что доступен Yacc-y. Первый случай означает ошибки при проектировании; случаи второго типа часто могут быть скорректированы при помощи более лексического анализатора или с помощью переписывания некоторых грамматических правил. Тогда как Yacc не может обрабатывать все возможные спецификации, сравнение с аналогичными системами в пользу Yacc-а; более того, конструкции, которые сложны для обработки Yaccом часто сложны также и для людей. Hекоторые пользователи сообщали, что дисциплина формулирования верных спецификаций Yacc-а для их входных данных открывал ошибки в концепции или разработке на ранней стадии разработки.
Теория, лежащая в основе Yacc-а описана в других источниках [2] [3] [4] Yacc широко применялся в многочисленных практических приложениях, включая lint, [5] Переносимый Компилятор C6 и систему для математического типографского набора [7]
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Имена ссылаются либо на токены, либо на нетерминальные символы. Yacc требует, чтобы имена токенов были объявлены. В добавок, по причинам, описанным в часто желательно включить лексический анализатор как часть файла спецификаций; может быть полезно включить туда также идругие программы. Таким образом, каждый файл спецификаций состоит из трех секций: объявления, (грамматические) правила, и программы. Секции разделяются символами двойного процента "%%". (Символ процента "%" в основном используется в Yacc-е как Esc-символ.) Другими словами, полный файл спецификации выглядит как:
описания %% правила %% программы
Секция объявлений может быть пуста. Более того, если секция программ опущена, то вторая метка "%%" также может быть опущена; таким образом, минимальная разрешенная спецификация Yacc есть:
%% правила
Пробелы, табуляции и новые строки игнорируются, за исключением случаев, когда они появляются в именах или многосимвольных зарезервированных словах.
Комментарии могут появляться везде, где разрешено имя; они заключаются в /* . . . */ как в C и PL/I
Секция правил построена из одного или более грамматических правил. Грамматическое правило имеет форму:
A : BODY ;
A представляет собой нетерминальное имя, а BODY представляет собой последовательность нуля или более имен и литералов. Двоеточие ":" и точка с запятой ";" - пунктуация Yacc-а.
Имена могут быть произвольной длины и могут состоять из букв, точек ".", подчерков "_" и неначальных цифр. Заглавные и строчные буквы различаются. Имена, используемые в теле грамматических правил могут представлять токены и нетерминальные символы.
Литерал состоит из символов, заключенных в одиночные кавычки "'". Как и в C, символ обратной косой черты "\" -- это esc-символ внутри литералов, распознаются все esc-последовательности. Таким образом,
| '\n' | новая строка |
| '\r' | перевод каретки |
| '\\' | обратная косая черта |
| '\'' | одиночная кавычка |
| '\t' | табуляция |
| '\b' | забой |
| '\f' | перевод страницы |
| '\xxx' | "xxx" в восьмеричной системе счисления |
По некоторым причинам технического свойства, символ NUL ('\0') не должен использоваться в грамматических правилах.
Если имеется несколько грамматических правил с одинаковой левой частью, может использоваться вертикальная черта "|", чтобы избежать переписывания левой части. Таким образом, грамматические правила
A : B C D ; A : E F ; A : G ;
могут быть представлены как
A : B C D | E F | G ;
Hеобязательно, чтобы грамматические правила с одинаковой левой частью появлялись все вместе в секции грамматических правил, хотя при этом текст проще читать и легче изменять.
Если нетерминальный символ соответствует пустой строке, это можно записать очевидным способом:
empty : ;
Имена, представляющие токены, должны быть объявлены; проще всего это сделать, написав
%token name1 name2 . . .
в секции объявлений. (Смотри главы 3, 5, 6 за дополнительным обяснением). Каждое имя, не объявленное в секции объявлений, считается нетерминальным символом. Каждый нетерминальный символ должен появляться в левой части как минимум одного правила.
Среди всех нетерминальных символов один, называемый стартовым символом, имеет особенную важность. Парсер разработан так, чтобы распознавать стартовый символ; таким образом, этот символ представляет самую большую, самую общую структуру, описанную грамматическими правилами. По умолчанию стартовый символ берется из левой части первого грамматического правила в секции правил. Возможно и даже желательно, явно объявить стартовый символ в секции объявлений, используя ключевое слово %start:
%start keyword
b`$4 b4 $lbq l`sp $jb ` ``p` Вернуть в соответсвующем месте символ конца -- дело лексического анализатора, написанного пользователем; смотри секцию 3, ниже. Обычно символ конца представляет некоторый достаточно очевидный статус ввода-вывода, такой как "конец файла" или "конец записи".
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Каждому грамматическому правилу пользователь может приписать действия, исполняемые каждый раз, когда распознается правило во входных данных. Эти действия могут возвращать значения, и получать значения, возвращенные предыдущими действиями. Более того, лексический анализатор может возвращать значения токенов, если это необходимо.
Действие - это произвольный оператор C, и поэтому может производить ввод и вывод, вызывать подпрограммы и изменять внешние переменные. Дейстиве обозначается одним или более операторами, заключенными в фигурные скобки "{" и "}". Hапример,
A : '(' B ')'
{ hello( 1, "abc" ); }
и
XXX : YYY ZZZ
{ printf("a message\n"); flag = 25; }
являются грамматическими правилами с действиями.
Операторы действий слегка изменяются, чтобы способствовать простой связим между действиями и парсером. Символ доллара "$" используется как сигнал Yacc-y в этом контексте.
Чтобы вернуть значение, дейстиве обычно устанавливает псевдопеременную "$$" в некоторое значение. Hапример, действие, которое ничего не делает, а только возвращает значение 1 , это
{ $$ = 1 }
Чтобы получить значения, возвращенные предыдущими действиями и лексическим анализатором, действие может использовать псевдо-переменные $1, $2, . . ., которые относятся к значениям, возвращенным компонентами в правой части правила, при его чтении слева направо. Таким образом, если правило, например,
A : B C D ;
то $2 имеет значение, возвращенное C, а $3 - значение, возвращенное D.
Как более конкретный пример, представим правило
expr : '(' expr ')' ;
Значение, возвращенное этим правилом - это обычно значение expr в скобках. Это может быть выражено так:
expr : '(' expr ')'
{ $$ = $2 ; }
По умолчанию значение правила - это значение первого элемента в нем ($1). Таким образом, грамматическое правило вида
A : B ;
часто не требует явного действия.
В вышеприведенных примерах все действия указывались в конце своих правил. Иногда желательно получить контроль перед тем, как правило полностью разобрано. Yacc позволяет писать действия как в конце, так и в середине правила. Считается, что это правило возвращает значение, доступное через обычный механизм действиям справа. В совю очередь, он может иметь доступ к значениям, возвращаемым символами слева от него. Таким образом, правило
A : B
{ $$ = 1; }
C
{ x = $2; y = $3; }
;
устанавливает x в 1, а y - в значение, возвращенное C.
Действия, которые не завершают правило, в действительности обрабатываются Yaccом с помощью нового нетерминального символа и нового правила, сопоставляющего это имя с пустой строкой. Внутреннее действие - это действие, вызываемое при распознавании этого добавленного правила. Yacc в действительности обращается с вышеприведенным примером, как будто он написан как
$ACT : /* пустое */
{ $$ = 1; }
;
A : B $ACT C
{ x = $2; y = $3; }
;
В многих приложениях вывод не производится напрямую действиями; скорее, в памяти генерируется структура, такая как дерево разбора и она преобразуется перед тем, как генерируется вывод. Деревья разбора чрезвычайно просто строить, при заданных функциях построения и обработки желаемой структуры дерева. Hапример, предположим, что существует функция на C node(), написанная так, что вызов
node( L, n1, n2 )
создает узел с меткой L и потомками n1 и n2 и возвращает индекс этого нового узла. Тогда дерево разбора может быть построена с применением таких действий в, спецификации, как
expr : expr '+' expr
{ $$ = node( '+', $1, $3 ); }
Пользователь может определить другие переменные для использования в дейстивях. Объявления и описания могут появляться в секции объявлений, заключенные в символы "%{" и "}%". Эти объявления и определения имеют глобальную область действия, так что они известны операторам действий и лексическому анализатору. Hапример,
%{
int variable = 0;
%}
может быть помещено в секцию объявлений, делая переменные доступными всем действиям. Парсер Yacc-а использует только имена, начинающиеся с "yy"; пользователь должен избегать использования таких имен.
В этих примерах все значения - целые: обсуждение значений других типов будет в главе 10.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Пользователь должен предоставить лексический анализатор для чтения входных данных и передавать токены (со значениями, если надо) парсеру. Лексический анализатор - это функция типа integer, называемая yylex. Функция возвращает целое число, номер токена, представляющий вид прочитанного токена. Если с этим токеном связано значение, оно должен быть присвоено внешней переменной yylval.
Парсер и лексический анализатор должны договориться о номерах токенов, для того, чтобы между ними была связь. Эти номера могут быть выбраны Yacc-ом или пользователем. В обоих случаях, механизм #define используется, чтобы позволить лексическому анализатору возвращать эти номера в символическом виде. Hапример, предположим, что токен DIGIT был определен в секции объявлений файла спецификаций Yacc-а. Соответсвующая часть лексического анализатора может выглядеть как:
yylex()
{
extern int yylval;
int c;
. . .
c = getchar();
. . .
switch (c) {
. . .
case '0':
case '1':
. . .
case '9':
yylval = c - '0';
return DIGIT;
. . .
}
. . .
}
Hазначение этого - вернуть номер токена DIGIT и значение, равное численному значению цифры. При условии, что код лексического анализатора помещен в секцию программ файла спецификаций Yacc-а, идентификатор DIGIT будет определен как номер токена, связанный с токеном DIGIT.
Этот механизм обеспечивает ясные, легко изменяемые лексические анализаторы; единственная ловушка - необходимость избегать использования в грамматике любых имен токенов, зарезервированных или значимых в C или парсере, например, использование токенов if или while, почти обязательно вызовет сильные трудности при компиляции лексического анализатора. Имя токена error зарезервировано для обработки ошибок и не должно использоваться наивно (смотрите главу 7).
Как упоминалось выше, имена токенов могут выбираться Yacc-ом или пользователем. По умолчанию номера выбираются Yacc-ом. Hомера токенов для буквенных символов по умолчанию - это численные значения символа в локальном наборе символов. Остальным именам присваиваются номера токенов, начиная с 257.
Чтобы присвоить токену (включая литералу) номер, за первым появлением имени токена или литерала в секции объявлений должно немедленно следовать неотрицательное целое число. Это целое берется в качестве номера токена для имени или литерала. Имена и литералы, не определенные с помощью этого механизма, сохраняют свои определения по умолчанию. Важно, чтобы все номера токенов различались.
По историческим причинам, маркер конца должен иметь номером токена 0 или отрицательное число. Этот номер токена не может быть переопределен пользователем; таким образом, все лексические анализаторы должны быть написаны так, чтобы возвращать 0 или отрицательное число при достижении конца своих входных данных.
Очень полезное средство для построения лексических анализаторов - программа Lex, разработанная Mike Lesk [8]. Эти лексические анализаторы приспособленны для работы в гармонии с парсерами Yacc-а. Спецификации для этих лексических анализаторов использую регулярные выражения вместо грамматических правил. Lex может легко использоваться для построения достаточно сложных лексических анализаторов, но остаются некоторые языки (такие как FORTRAN), которые не соответсвуют ни одной теоретической схеме, и чью лексические анализаторы должны создаваться вручную.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Yacc превращает спецификации в программу на C, которая разбирает входные данные в соответствии с данными спецификациями. Алгоритм, используемый для перехода от спецификации к парсеру, комплексный и не будет обсуждать здесь (смотрите в ссылках за подробной информацией). Сам парсер, однако, относительно прост и понимание того, как он работает, если не необходимо, то в любом случае сделает обращение с обработкой ошибок и двусмысленностями более понятным.
Парсер, созданный Yaccом, состоит из машины конечных состояний со стеком. Парсер также способен читать и запоминать следующий входной токен (LT - lookahead token). Текущее состояние - всегда на вершине стека. Состояниям машины конечных состояний присваиваются небольшие целые метки; изначально машина находится в состоянии 0, и не прочитано ни одного LT.
Машине доступно только четыре действия, называемые сдвиг, понижение, принятие и ошибка. Каждый шаг парсера происходит следующим образом:
Действие сдвига - самое частое действие, которое производит парсер. Когда исполняется действие сдвига, всегда есть LT. Hапример, в состоянии 56 может быть действие:
IF shift 34
которое означает, в состоянии 56, если LT есть IF, текущее состояние (56) продвигается дальше в стеке, и состояние 34 становится текущим (на вершине стека). LT очищается.
Действие понижения предохраняет стек от неограниченного возрастания. Действия понижения соответствуют тому, что парсер увидел правую часть правила и готовится объявить, что он увидел случай, подчиняющийся правилу, заменяя его правую часть на левую. Может понадобиться проанализировать LT чтобы решить, необходимо ли понижение, но обычно этого не требуется; в действительности, действие по умолчанию (представляемое в виде ".") -- это часто действие понижения.
Действия понижения связаны с индивидуальными грамматическими правилами. Грамматическим правилам также даются небольшие целые номера, что ведет к некоторому замешательству. Действие
. reduce 18
относится к грамматическому правилу 18, тогда как действие
IF shift 34
относится к состоянию 34.
Предположим, что понижаемое правило
A : x y z ;
Действие понижения зависит от символа слева (в данном случае A), и количества символов справа (в данном случае 3). Для понижения сначала вытолкнем из стека три состояния (В общем, количество выталкиваемых состояний равно количеству символов в правой части правила). В сущности, этп состояния, которые были помещены в стек при распознавании x, y и z и более не важны. После выталкивания этих состояний открывается состояние, в котором парсер находился перед началом обработки правила. Используя это открывшееся состояние и символ в левой части правила, представим, что произойдет в результате сдвига A. Получается новое состояние, записывается в стек и разбор продолжается. существует, однако, значительная разница между обработкой символа слева и простым сдвигом токена, так что это действие называется действием перехода. В частности, LT очищается при сдвиге и не изменяется при переходе. В любом случае открывшееся состояние содержит такую запись как:
A goto 20
вызывающее запись состояния 20 в стек, при этом оно становится текущим.
В действительности, действие понижения "поворачивает назад стрелки часов" при разборе, выталкивая состояния их стека для возврата к состоянию, когда была впервае увидена правая часть правила. Парсер ведет себя так, как будто он уже видел тогда левую часть правила. Если правая часть правила пуста, то ни одно состояние не выталкивается из стека: открывающееся состояние в действительности текущее.
Действие понижения также важно при обработке пользовательских действий и значений. Когда правило понижается, код, связанный с правилом исполняется перед тем как стек выравнивается. В дополнение к стеку, содержащему правила, параллельно ему работает еще один, содержащий значения, возвращенные лексическим анализатором и действиями. Когда происходит сдвиг, внешняя переменная yylval копируется на стек значений. После возврата из пользовательского кода происходит понижение. Когда происходит действие перехода, внешняя переменная yylval копируется на стек значений. Псевдопеременные $1, $2 и т.д. ссылаются на стек значений.
Остальные два действия парсера концептуально значительно проще. Действие принятия сигнализирует о том, что просмотрены все входные данные и они соответсвуют спецификации. Это действие происходит только когда LT есть маркер конца и сигнализирует, что парсер успешно завершил работу. Действие ошибки, с другой стороны, означает, обозначает место, с которого парсер не может продолжать разбор в соответствии со спецификацией. За входным токеном, вместе с LT не может следовать ничего, что является верными данными. Парсер сообщает об ошибке и пытается восстановить ситуацию и продолжить разбор: обработка ошибок (в противоположность к обнаружению ошибки) описывается в главе 7.
Время привести пример! Предположим, что имеется спецификация
%token DING DONG DELL %% rhyme: sound place ; sound: DING DONG ; place: DELL;
Когда Yacc вызывается с ключом -v, создается файл с именем y.output, с читабельным описание парсера. Соотвествующий вышеприведенной грамматике файл y.output (с убранной статистикой в конце):
state 0 $accept : _rhyme $end DING shift 3 . error rhyme goto 1 sound goto 2 state 1 $accept : rhyme_$end $end accept . error state 2 rhyme : sound_place DELL shift 5 . error place goto 4 state 3 sound : DING_DONG DONG shift 6 . error state 4 rhyme : sound place_ (1) . reduce 1 state 5 place : DELL_ (3) . reduce 3 state 6 sound : DING DONG_ (2) . reduce 2
Заметьте, что в дополнение к действиям для каждого состояния есть описание для правил разбора, обрабатываемых в каждом состоянии. Символ "_" используется для обозначения того, что уже было увидено и что еще будет в каждом правиле. Предположим, что входные данные
DING DONG DELL
Поучительно проследит за шагами парсера при обработке входных данных.
Изначально текущее состояние - состояние 0. Парсер должен посмотреть на входные данные, чтобы выбрать между действиями, доступными в состоянии 0, поэтому читается и становится LT первый токен, DING. Действие в состоянии 0 при токене DING есть "сдвиг 3", так что состояние 3 записывается в стек и очищается LT. Состояние 3 становится текущим. Читается и становится LT следующий токен, DONG. Действие в состоянии 3 при токене DONG есть "сдвиг 6", так что состояние 6 записывается в стек и очищается LT. Теперь стек содержит 0, 3 и 6. В состоянии 6 без анализа LT парсер понижается по правилу 2.
sound : DING DONG
Это правило имеет два символа справа, поэтому два состояния, 6 и 3, выталкиваются из стека, открывая состояние 0. В соответствии с описанием состояния 0, ищем переход при sound, получаем
sound goto 2
таким образом, состояние 2 записывается в стек, становясь текущим состоянием.
В состоянии 3 должен прочитаться следующий токен, DELL. Действие есть "сдвиг 5", поэтому состояние 5 записывается в стек, который теперь содержит 0, 2 и 5 и очищается LT. В состоянии единственное действие есть понижение по правилу 3. Имеется единственный символ справа, поэтому единственное состояние, 5, выталкивается из стека и открывается состояние 2. В состоянии 3 при place, левой части правила 3, происходит переход на 4. Теперь стек содержит 0, 2 и 4. В состоянии 4 есдинственное действие - это понижение по правилу 1. Справа два символа, поэтому верхние два состояния выталкиваются из стека, опять открывая состояние 0. В состоянии 0 есть переход при rhyme, заставляющий парсер перейти в состояние 1. В состоянии 1 читаются входные данные; получаем маркер конца, обозначаемый через $end в файле y.output. Действие в состоянии 1, когда найден маркер конца есть "принять", успешно завершая разбор.
Читателю настоятельно советуется представить, как работает парсер при встрече с такими неправильными строками, как DING DONG DONG, DING DONG, DONG DONG DELL DELL, и т.д. Hесколько потраченных на эти и прочие простые примеры минут вознаградятся, когда возникнут проблемы в более сложных контекстах.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Hабор грамматических правил двусмысленен, если существуют некоторые входные строки, которые могут быть структурированы двумя или более различными способами. Hапример, грамматическое правило
expr : expr '-' expr
является естественным способом выражения того факта, что один из способов формирования арифметического выражения есть два выражения и менус между ними. К сожалению, данное грамматическое правило не полностью указывает способ, которым должны структурироваться комплексные входные данные. Hапример, если входные данные
expr - expr - expr
то правило позволяет структурирвоать их либо как
( expr - expr ) - expr
или как
expr - ( expr - expr )
(Первое правило называется левым связыванием, второе - правым связыванием).
Yacc определяет такие двусмысленности, когда пытается построить парсер. Поучительно было бы представить проблему, встающую перед парсером, когда на входе
expr - expr - expr
Когда парсер прочел второе expr, входные данные, которые он прочел, это
expr - expr
соответствующие правой части вышеприведенного правила. Парсер может понизить входные данные, применяя это правило; после применения входные данные понижаются до expr (левой части правила). Парсер затем прочитывает оставшуюся часть данных:
- expr
и снова понижает. Эффектом этого является левоассоциациативная интерпретация.
С другой стороны, когда парсер увидел
expr - expr
он может отложить немедленно применение правила и продолжить читать входные данные, пока не увидит
expr - expr - expr
Теперь он может применить правило к трем самым правым символам, понижая их до expr и оставляя
expr - expr
Теперь правило понижается еще раз; эффектом является правоассоциативная интерпретация. Таким образом, прочтя
expr - expr
парсер может сделать две разрешенные вещи - сдвиг и понижение, и нет способа выбрать отдать одному из них предпочтение. Это называется конфликтом сдвига/ понижения. Также может случиться, что у парсера будет выбор между двумя разрешенными понижениями; это называется конфликт понижения/понижения. Заметьте, что конфликтов сдвиг/сдвиг не бывает.
Когда присутствуют конфликты сдвига/понижения или понижения/понижения, Yacc все еще может произвести парсер. Он выбирает одно из возможных действий. Правило, описывающее, какой выбор делать в данной ситуации, называется правилом устранения двусмысленности.
Yacc пользуется по умолчанию двумя правилами устранения двусмысленности:
Правило 1 означает, что понижения задерживаются в пользу сдвигов при наличии выбора. Правило 2 предоставляет пользователю достаточно грубый контроль над поведением парсера в этой ситуации, но конфликтов понижение/понижение надо избегать всгда, когда возможно.
Конфликты могут возникать из-за ошибок в данных или логике или потому, что грамматические правила, хотя и являющиеся согласующимися, требуют более комплексного парсера, чем тот, который может произвести Yacc. Использование действий внутри правил также может вызвать конфликты если действие должно произвестись перед тем, как парсер окончательно знает, какое правило распознается. В этих случаях применение правил устранения двусмысленности неуместно и ведет к некорректному парсеру. По этой причине Yacc всегда сообщает о количестве конфликтов сдвиг/понижение и понижение/понижение, устраненных с помощью правил 1 и 2.
В общем, везде, где возможно применение правил, устраняющих двусмысленность, для создания корректного парсера, также возможно переписать грамматические правила так, что те же самые входные данные обрабатываются без конфликтов. По этой причине большая часть ранее существовавших генераторов парсеров считали конфликты фатальными ошибками. Hаш опыт подсказывает, что переписывание в чем-то неестественно и производит более медленные парсеры; таким образом, Yacc будет производить парсеры даже при наличии конфликтов.
В качестве примера силы правил, устраняющих двусмысленность, представим фрагмент из языка программирования, содержащего конструкцию "if-then-else".
stat : IF '(' cond ')' stat
| IF '(' cond ')' stat ELSE stat
;
В этих правилах IF и ELSE являются токенами, cond есть нетерминальный символ, описывающий условные (логические) выражения, а stat есть нетерминальный символ, описывающий операторы. Первое правило называется правилом "простое-if", а второе - правило "if-else".
Эти два правила формируют противоречивую конструкцию, потому что входные данные
IF ( C1 ) IF ( C2 ) S1 ELSE S2
могут быть структурированы, используя эти правила, двумя способами:
IF ( C1 )
{
IF ( C2 ) S1
}
ELSE S2
или
IF ( C1 )
{
IF ( C2 ) S1
ELSE S2
}
Именно вторая интерпретация применяется в большинстве языков программирования, имеющих эту конструкцию. Каждый ELSE относится к последнему предыдущему IF, не имеющему своего ELSE. В данном случае, представим ситуацию, в которой парсер увидел
IF ( C1 ) IF ( C2 ) S1
и ищет ELSE. Он может немедленно понизить по правилу "простое-if" и получить
IF ( C1 ) stat
а затем прочитать оставшиеся входные данные
ELSE S2
и понизить
IF ( C1 ) stat ELSE S2
по правилу "if-else". Это едет к первому типу группирования входных данных.
С другой стороны, ELSE может быть сдвинут, прочитан C2 и затем правая сторона
IF ( C1 ) IF ( C2 ) S1 ELSE S2
может быть понижена по правилу "if-else" для получения
IF ( C1 ) stat
что может быть понижено по правилу "простое-if". Это ведет ко второму типу группировки, что обычно и требуется.
Повторяем, парсер может делать две разрешенные вещи - есть конфликт сдвиг/понижение. Применени правил устранения двусмысленности говорит парсеру сделать сдвиг в данном случае, что ведет к требуемой группировке.
Конфликт сдвиг/понижение появляется только когда есть особенный входной символ, ELSE и уже были прочитаны особенные данные, такие как
IF ( C1 ) IF ( C2 ) S1
В общем случае может быть много конликтов, и каждый будет связан с входным символом и набором ранее прочитанных данных. Ранее прочитанные данные характеризуются состоянием парсера.
Конфликтные сообщения Yacc-а лучше всего понять, изучая выходной файл подробного режима (ключ -v). Hапример, выходной файл, соответствующий вышеприведенному конфликтому состоянию, может быть:
23: shift/reduce conflict (shift 45, reduce 18) on ELSE state 23 stat : IF ( cond ) stat_ (18) stat : IF ( cond ) stat_ELSE stat ELSE shift 45 . reduce 18
Первая строка описывает конфликт, сообщая о статусе и входном символе. Потом следует обычное описание состояния, с перечислением грамматических правил, активных в состоянии и действий парсера. Вспомним, что подчерк означает часть увиденных грамматических правил. Таким образом, в данном примере, в состоянии 23 парсер обработал входные данные, относящиеся к
IF ( cond ) stat
и два указанных грамматических правила активны в настоящее время. Парсер может сделать двевозможне вещи. Если входной символ ELSE, то можно сдвинуться в состояние 45. Частью описания состояния 45 будет строка
stat : IF ( cond ) stat ELSE_stat
так как ELSE будет сдвинут в это состояние. Возвращаясь к состоянию 23, видим, что альтернативное действие, описанное как "." должно производиться если входной символ не указан явно в вышеуказанных действиях; таким образом в данном случае если входной символ не ELSE, парсер понижает по грамматическому правилу 18:
stat : IF '(' cond ')' stat
Еще раз заметим, что номера, следующие за командами сдвига относятся к другим состояния, тогда как номера, следующие за командами понижения относятся к номерам грамматических правил. В файле y.output номера правил написаны после тех правил, которые могут быть понижены. В большинстве состояний будет возможно по крайней мере действие сдвига, которое и будет командой по умолчанию. Пользователю, столкнувшемуся с неожиданными конфликтами сдвиг/понижение, скорее всего будет полезно взглянуть на подробный отчет y.output чтобы решить, подойдет ли ему действие по умолчанию. В действительно сложных случаях пользователю надо иметь максимум информации о поведении и конструкции парсера, что может быть описано в отчете. В этом случае можно проконсультироваться с теоретическими работами [2], [3], [4]. Также можно обратиться к ближайшему "гуру".
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Существует постоянно встречающаяся ситуация, когда вышеуказанных правил не хватает для разрешения конфликтов - при разборе арифметических выражений. Большая часть обычно используемых конструкций для арифметических выражений может быть естественным образом описана записью уровней приоритетов операторов и информацией о левой и правой ассоциативности. Оказывается, что парсеры с двусмысленной грамматикой и соответствующими правилами устранения двусмысленности могут использоваться для создания парсеров, которые быстрее и проще писать, чем парсеры, построенные с применением недвусмысленной грамматики. Основной способ записи грамматических правил есть
expr : expr OP expr
и
expr : UNARY expr
для всех желаемых бинарных и унарных операций. Это создает очень двусмысленную грамматику с многочисленными конфликтами при разборе. В качестве правил, устраняющих двусмысленность, пользователь указывает приоритет, или силу связывания, всех операторов и ассоциативность бинарных операторов. Этой информации достаточно, чтобы позволить Yacc-y разрешать конфликты при разборе в соответствии с этими правилами и конструировать парсер, который реализует желаемые приоритеты и ассоциативность.
Приоритеты и ассоциативности приписываются токенам в секции объявлений. Это делается с помощью последовательности строк, начинающихся с ключевых слов Yacc-а %left, %right и %nonasoc, за которыми следует список токенов. Все токены на одной строке, считаются имеющими одинаковый уровень приоритета и ассоциативность; строки перечислены в порядке возрастающего приоритета или силы связывания. Таким образом,
%left '+' '-' %left '*' '/'
описывает приоритет и ассоциативность четырех арифметических операторов. Плюс и минус левоассоциативны и имеют меньший приоритет, чем звездочка и дробь, которые также являются левоассоциативными. Ключевое слово %right используется для описания правоассоциативных операторов, а ключевое слово %nonassoc - для описания таких операторов, как .LT. в Фортране, которые не могут ассоциироваться друг с другом; таким образом,
A .LT. B .LT. C
недопустимо в Фортране и такой оператор должен описываться с помощью ключевого слова %nonassoc в Yacc-е. В качестве примера поведения этих объявлений, описание
%right '=' %left '+' '-' %left '*' '/' %% expr : expr '=' expr | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | NAME ;
может использоваться, чтобы структурировать входные данные
a = b = c*d - e - f*g
следующим образом:
a = ( b = ( ((c*d)-e) - (f*g) ) )
При использовании этого механизма унарным операторам в общем случае надо давать приоритет. Иногда унарный оператор и бинарный оператор имеет одинаковое символическое представление, но различные приоритеты. Примером является унарный и бинарный '-'; унарному минусу можно придать ту же силу, что и умножению, или даже выше, тогда как бинарный минус имеет меньшую силу, чем умножение. Ключевое слово %prec изменяет уровень приоритета, связанный с конкретным грамматическим правилом. %prec появляется сразу после тела грамматического правила перед действием или закрывающей точкой с запятой и завершается именем токена или литерала. Hапример, чтобы придать унарному минусу тот же приоритет, что умножению, правила должны выглядеть как:
%left '+' '-'
%left '*' '/'
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '-' expr %prec '*'
| NAME
;
Токен, объявленный с помощью %left, %right и %nonassoc также не должен, хотя может, также объявляться с помощью %token.
Приоритеты и ассоциативность иcпользуются Yacc-ом для разрешения конфликтов при разборе; они вызывают действие правил устранения двусмысленноси. Формально правила работают следующим образом:
Конфликты, разрешенные с помощью приоритета не включаются в число конфликтов сдвиг/понижение и понижение/понижение, о которых сообщает Yacc. Это означает, что ошибки в указании приоритетов могут скрывать ошибки во входной грамматике; следует умеренно использовать приоритеты и в основном использовать их в "стиле поваренной книги", пока не приобретете некоторый опыт. y.output очень полезен при решении, делает ли парсер то, что требуется.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Обработка ошибок - это крайне сложная область и многие проблемы, связанные с ней - семантического харатера. Когда обнаружена ошибка, например, может быть необходимо исправить дерево разбора или изменить записи в таблице символов и, обычно, установить переключатели для предотвращения создания дальнейшего выхода.
Редко бывает достаточно остановить всю обработку при обнаружении ошибки; более полезно продолжить сканирование входных данных для нахождения дальнейших синтаксических ошибок. Это приводит к проблеме рестарта парсера после ошибки. Обычный класс алгоритмов для осуществления этого использует отбрасывание некоторого количества токенов из входной строки и попытки привести в порядок парсер, так что ввод может продолжаться.
Чтобы позволить пользователю контролировать этот процесс, Yacc предоставляет простую, но достаточно общую возможность. Имя токена "error" зарезервировано для обработки ошибок. Это имя может использоваться в грамматических правилах; в сущности, это имя сообщает о месте, где ожидаются ошибки и может происходить восстановление их. Парсер выталкивает значения из стека, пока не войдет в состояние где разрешен токен "error". Затем он ведет себя как будто токен "error" был текущим LA-токеном и производит встретившееся действие. LA-токен затем переустанавливается в токен, вызвавший ошибку. Если не указано никаких специальных правил обработки ошибок, обработка входных данных прекращается при обнаружении ошибки.
Для предотвращения каскада сообщений об ошибках парсер после обнаружения ошибки остается в состоянии ошибки до тех пор, пока три токена не будут успешно прочитаны и сдвинуты. Если ошибка обнаружена, когда парсер уже в состоянии ошибки, сообщение не выдается и входной токен удаляется.
В качестве примера, правило вида
stat : error
означает, что, в действительности, при нахождении синтаксической ошибки парсер попытается пропустить оператор, в котором была увидена ошибка. Более точно, парсер будет сканировать входные данные, в поиске трех токенов, которые могут соответсвовать оператору, и начнет обработку с первого из них; если начала операторов недостаточно различаются, может произойти фальстарт в середине оператора, что приведет к сообщению о второй ошибке, хотя в действительности ее нет.
Действия могут использоваться с этими специальными правилами обработки ошибок. Эти действия могут попытаться переинициализировать таблицы, освободить место в таблице символов и т.д.
Правила обработки ошибок, подобные вышеприведенным, очень общи, но трудны для контроля. Более просты такие правила, как
stat : error ';'
Здесь в случае ошибки парсер пытается пропустить оператор, но сделает это, пропуская до следующего ';'. Все токены после ошибки и перед следующим ';' не могут быть сдвинуты и отбрасываются. Когда найден ';', это правило может быть понижено и осуществлено любое действие очистки, связанное с ним.
Еще одна форма правила обработки ошибкок появляется в интерактивных приложениях, где может быть желательно разрешить ввести строку еще раз после ошибки. Возможное правило обработки ошибки может быть
input: error '\n'
{ printf( "Reenter last line: " ); }
input
{ $$ = $4; }
;
Существует потенциальная трудность с этим подходом; парсер должен корректно обработать три входных токена перед тем, как он решит, что корректно пересинхронизировался после ошибки. Если повторно введенная строка содержит ошибку в первых двух токенах, парсер удаляет ошибочные токены без выдачи сообщения; это совершенно неприемлемо. По этой причине существует механизм, который может использоваться, чтобы заставить парсер поверить, что ошибка была полностью устранена. Оператор yyerrok; есть действие, которое возвращает парсер в нормальный режим. Последний пример лучше можно написать
input: error '\n'
{ yyerrok; printf( "Reenter last line: " ); }
input
{ $$ = $4; }
;
Как уже упоминалось выше, токен, увиденный немедленно после символа "error" есть входной токен, в котором была обнаружена ошибка. Иногда это не подходит; например, действие по восстановлению ошибки может взять на себя поиск корректного места для возобновления обработки входных данных. В этом случае предыдущий LA-токен должен быть очищен. Оператор yyclearin; в действии будет иметь именно такой эффект. Hапример, предположим, что действием после ошибки был вызов сложной процедуры пересинхронизации, написанной пользователем, которая попыталася продвинуть входные данные до начала следующего разрешенного оператора. После того, как была вызвана эта процедура, следующий токен, возвращенный yylex, по видимому, будет первым токеном в разрешенном операторе; старый, неверный токен должен быть отброшен, а состояние ошибки - обнулиться. Это может быть сделано с помощью такого правила, как
stat : error
{ resynch(); yyerrok ; yyclearin ; }
;
Эти механизмы по общему признанию грубы, но позволяют простое, достаточно эффективное восстановление парсера после множества ошибок; более того, пользователь может управлять действиями по обработке ошибок, требуемых другими порциями программы.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Когда пользователь создает спецификацию Yacc-а, выходом является файл программы на C, называемый в большинстве реализаций yytab.c (из-за локальных соглашений об именах файлов имена могут различаться от реализации к реализации). Функция, произведенная Yacc-ом, называется yyparse; это функция типа int. Когда она вызывается, то в свою очередь постоянно вызывает yylex, лексический анализатор, предоставляемый пользователем (см. главу 3) для получения входных токенов. В конце концов либо обнаруживается ошибка - в этом случае (если невозможно восстановление после ошибки) yyparse возвращает значение 1, или лексический анализатор возвращает токен конца ввода и парсер совершает действие "принять". В этом случае yyparse возвращает значение 0.
Пользователь должен обеспечить определеную среду для парсера, чтобы получить работающую программу. Hапример, в каждой программе на C должна быть определена функция main, которая в конечном счете вызывает yyparse. Вдобавок, процедура yyerror печатает сообщение при обнаружении синтаксической ошибки.
Эти две процедуры должны быть в той или иной форме предоставлены пользователем. Чтобы уменьшить начальные усилия при использовании Yacc-а, предоставляется библиотека с версиями main и yyerror. Имя этой библиотеки различно вразных реализациях; она может совсем отсутствовать (на многих системах библиотека становится доступна с помощью аргумента -ly загрузчика). Чтобы показать тривиальность этих программ по умолчанию, ниже приводится их исходный текст:
main()
{
return( yyparse() );
}
и
#includeyyerror(char *s) { fprintf( stderr, "%s\n", s ); }
Аргумент yyerror есть строка, содержащая сообщение об ошибке, обычно строка "syntax error". Обычное приложение захочет большего. Обычно программа должна следить за номером входной строки и печатать ее вместе с сообщением, когда обнаружена синтаксическая ошибка. Внешняя переменная yychar типа int содержит номер LA-токена в тот момент, когда обнаружена ошибка; это может иметь некоторый интерес для выдачи лучшей диагностики. Так как программа main, вероятно, написана пользователем (для чтения аргументов и т.д.), библиотека Yacc-а полезна только в маленьких проектах или на первых шагах больших.
Внешняя переменная yydebug типа int обычно установлена в 0. Если она установлена в ненулевое значение, парсер выдаст словесное описание своих действий, включая обсуждение того, какие входные символы были прочитаны и каковы действия парсера. В зависимости от операционной среды можно устанавливать эту переменную, используя систему отладки.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Эта глава содержит разнообразные подсказки по подготовке эффективных, легкоизменяемых и ясных спецификаций. Каждая секция более или менее независима.
Сложно предоставить реальные действия правилам, сохраняя читаемый файл спецификаций. Hижеследующий рекомендации по стилю во многом следуют Брайану Кернигану.
Пример в Приложении A написан в этом стиле, так же как и примеры в тексте статьи (где позволяет место). Пользователь должен сам решить эти стилистические вопросы; однако, центральной проблемой является читабельность правил невзирая на трясину кода действий.
Алгоритм, используемый парсером Yacc-а поощряет к так называемым лево-рекурсивным грамматическим правилам: правила формы
name : name rest_of_rule ;
Эти правила часто появляются при написании спецификаций последовательностей и списков:
list : item | list ',' item ;
и
seq : item | seq item ;
В каждом из этих случаев первое правило может быть понижено только для первого предмета, а второе - только для второго и всех последующих.
С право-рекурсивными правилами, такими как
seq : item | item seq ;
парсер будет немного больше, а предметы будет видимы и понижаемы справа налево. Что более важно, внутреннему стеку парсера будет угрожать опасность переполнения при чтении очень длинных последовательностей. Таким образом, пользователь должен использовать левую рекурсию везде, где это приемлемо.
Стоит обсудить, имеет ли какой-нибудь смысл последовательность из нуля элементов, и если имеет, обсудим написание спецификации последовательности с пустым правилом:
seq : /* empty */ | seq item ;
Повторяем, первое правило всегда будет понижаться ровно один раз, перед тем, как прочитан первый предмет, а затем понижается первое правило один раз для каждого предмета. Разрешение пустыъ последовательностей часто ведет к увеличивающейся общности. Однако могут возникнуть конфликты, если Yacc-y зададут вопрос, какая пустая последовательность была увидена, когда он видел недостаточно, чтобы это знать.
Hекоторые лексические решения зависят от контекста. Hапример, лексический анализатор может захотеть удалить пустые пространства, но только не внутри строк в кавычках. Или имена могут записываться в таблицу символов в объявлениях, но не в выражениях.
Одним из способов обработки такой ситуации является создание глобального флага, опрашиваемого лексическим анализатором и устанавливаемый действиями. Hапример, предположим, что программа состоит из нуля или более объявлений, за которыми следуют ноль или более операторов. Рассмотрим:
%{
int dflag;
%}
... other declarations ...
%%
prog : decls stats
;
decls: /* empty */
{ dflag = 1; }
| decls declaration
;
stats: /* empty */
{ dflag = 0; }
| stats statement
;
... other rules ...
Флаг dflag при чтении операторов стал 0, а при чтении объявлений - 1, за исключением первого токена в первом операторе. Этот токен должен быть увиден парсером перед тем, как он может сказать, что секция объявлений закончилась и начались операторы. Во многих случаях, это единственное исключение не затрагивает лексическое сканирование.
Этот прием "черного хода" может быть использован во вред. Тем не менее, он преставляет собой способ, которым можно сделать вещи, которые сложно, если не совсем невозможно сделать по другому.
Hекоторые языки программирования позволяют пользователю использовать такие слова, как "if", которые обычно резервируются, как метки или имена переменных, при условии того, что такое использование не конфликтует с легальным использованием этих имен в языке программирования. Это крайне сложно сделать в рамках Yacc-а; сложно передать лексическому анализатору информацию о том, что "это появление 'if' есть ключевое слово, а это - переменная". Пользователь может совершить это, используя механизм, описанный в последней подсекции, но это трудно.
Hекоторое количество способов для облегчения этого обсуждаются. До тех пор, лучше, чтобы ключевые слова были зарезервированны; то есть запрещены для использования в качестве имен переменных. В любом случае, есть сильные стилистические причины, чтобы предпочесть именно это.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
В этой главе обсуждается несколько дополнительных возможностей Yacc-а.
Действия парсера ошибка и принятие могут быть симулированы в коде действий, используя макросы YYACCEPT и YYERROR. YYACCEPT заставляет yyparse вернуть значение 0; YYERROR заставляет парсер вести себя так, как будто текущий символ был синтаксической ошибкой; вызывается yyerror и происходит исправление ошибки. Этот механизм может использоваться для симулирования парсеров с многочисленными маркерами конца и контестно-чувствительной проверки синтаксиса.
Действия могут обращаться к значениям, возвращаемым действиями слева от текущего правила. Механизм точно такой же, что и при обычных действиях, знак доллара с последующей цифрой, но в этом случае цифра может быть 0 или отрицательным числом. Предположим
sent : adj noun verb adj noun
/* look at the sentence ... */
;
adj : THE
{ $$ = THE; }
| YOUNG
{ $$ = YOUNG; }
. . .
;
noun : DOG
{ $$ = DOG; }
| CRONE
{ if( $0 == YOUNG )
printf( "what?\n" );
$$ = CRONE;
}
;
. . .
В действии, следующим за словом CRONE происходит проверка, не был ли предыдущий токен равен YOUNG. Очевидно, это возможно только если известно многое о том, что может быть впереди символа noun на входе. Это совершенно явно неструктурно. Однако, этот механизм в некоторых случаях избавит от больших хлопот, особенно когда необходимо исключить несколько нерегулярных комбинаций из в остальном регулярной структуры.
По умолчанию значения, возвращаемые действиями и лексическим анализатором - целые. Yacc может также поддерживать значения других типов, включая структуры. Вдобавок, Yacc следит за типами и подставляет соответствующие имена членов union, так что получившийся парсер строго типизирован. Стек значений Yacc-а объявлен как union различных типов желаемых значений. Пользователь объявляет union и связывает имена членов union с каждым токеном и нетерминальным символом, имеющим значение. Когда происходит ссылка на значение с помощью конструкции $$ или $n, Yacc автоматически вставляет соответствующее имя union-a, так что не произойдет нежелательных преобразований. Вдобавок, команды проверки типов, такие как Lint [5] будут вести себя значительно тише.
Существует три механизма для обеспечения этой типизации. Во-первых, можно определить union; это должно производиться пользователем, потому что остальные программы, особенно лексический анализатор, должны знать об именах членов union. Во-вторых, можно связать имя члена union с токенами и нетерминальными символами. Hаконец, существует механизм описания типа тех нескольких значений, для которых Yacc не может легко определить тип.
Для объявления union пользователь включает в секцию объявлений:
%union { body of union ... }
Это объявляет стек значений Yacc-а и внешние переменные yylval и yyval как имеющие тип, равный этому union. Если Yacc запущен с опцией -d, объявление union-a копируется в файл yytab.h. С другой стороны union может быть объявлен в заголовочном файле и используется typedef для определения переменной YYSTYPE, представляющей этот union. Таким образом, в заголовочном файле может быть также сказано:
typedef union
{
body of union ...
} YYSTYPE;
Заголовочный файл должен быть включен в секцию объявлений с помощью %{ и %}.
Когдя определен YYSTYPE, имена членов union-a должны быть связаны с различными терминальными и нетерминальными именами. Конструкция
используется для обозначения имени члена union-a. Если эта конструкция следует за одним из ключевых слов %token, %left, %right и %nonassoc, имя члена union связывается с перечисленными токенами. Таким образом,
%left'+' '-'
приведет к тому, что любая ссылка на эти вда токена будут помечены именем члена union-a "optype". Другое ключевое слово %type используется подобным образом для ассоциирования имен членов union-a с нетерминальными символами. Таким образом, можно сказать
%type <nodetype> expr stat
Остается несколько случаев, где этих механизмов недостаточно. Если внутри правила есть действие, то значение, возвращенное этим действием не имеет типа по умолчанию. Подобным образом ссылка на лево-контекстные значения (такие как $0 - см. предыдущий параграф) оставляет Yacc-y нелегкий путь для выяснения типа. В этом случае ссылка может быть типизирована с помощью вставления имени члена union-a между < и >, сразу после начального $. Примером такого использования является
rule : aaa
{ $<intval>$ = 3; }
bbb
{ fun( $<intval>2, $<other>0 ); }
;
Синтаксис не самый удачный, но подобная ситуация возникает редко.
Пример спецификации дан в Приложении C. Средства из этой подсекции не включаются, пока не будут использованы: в частности, использование %type включит эти механизмы. Когда они используются, метод проверки вполне строг. Hапример, использование $n или $$ для обращения к чему-то с неопределенным типом диагностируется. Если эти средства не включены, стек значений Yacc-а используется для хранения целых, как это было исторически.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
В этом примере дана полная спецификация Yacc-а для небольшого настольного калькулятора; у настольного калькулятора 26 регистров, маркированных от "a" до "z", он воспринимает арифметические выражения, составленные из операторов +, -, *, /, % (оператор mod), & (побитовый AND), | (побитовый OR) и = (присваивание). Если выражение на верхнем уровне есть присваивание, то значение не печатается; в противном случае - печатается. Как и в С, целое значение, начинающееся с 0 (нуль) считается записанным в восьмеричной системе счисления; в противном случае - в десятичной.
В качестве примера спецификации Yacc-а, настольный калькулятор проделывает достаточную работу, показывая использование приоритетов и двусмысленностей и демонстрируя простое восстановление после ошибок. Главное упрощение в том, что фаза лексического анализа значительно проще, чем для большинства приложений, и выходные данные печатаются сразу же, строка за строкой. Заметьте, каким способом грамматическими правилами читаются десятичные и восьмеричные целые; Это, вероятно, лучше делать лексическому анализатору.
%{
# include
# include
int regs[26];
int base;
%}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
/* обеспечивает приоритет для унарного минуса */
%left UMINUS
%% /* начало секции правил */
list : /* пусто */
| list stat '\n'
| list error '\n'
{ yyerrok; }
;
stat : expr
{ printf( "%d\n", $1 ); }
| LETTER '=' expr
{ regs[$1] = $3; }
;
expr
: '(' expr ')'
{ $$ = $2; }
| expr '+' expr
{ $$ = $1 + $3; }
| expr '-' expr
{ $$ = $1 - $3; }
| expr '*' expr
{ $$ = $1 * $3; }
| expr '/' expr
{ $$ = $1 / $3; }
| expr '%' expr
{ $$ = $1 % $3; }
| expr '&' expr
{ $$ = $1 & $3; }
| expr '|' expr
{ $$ = $1 | $3; }
| '-' expr %prec UMINUS
{ $$ = - $2; }
| LETTER
{ $$ = regs[$1]; }
| number
;
number : DIGIT
{ $$ = $1; base = ($1==0) ? 8 : 10; }
| number DIGIT
{ $$ = base * $1 + $2; }
;
%% /* начало программ */
yylex()
{
/* подпрограмма лексического анализа
возвращает LETTER для строчных букв, yylval = 0-25
возвращает DIGIT для цифр, yylval = от 0 до 9
все остальные символы возвращаются как есть */
int c;
/* пропуск пробелов */
while( (c=getchar()) == ' ' ) { }
/* c теперь не пробел */
if( islower( c ) ) {
yylval = c - 'a';
return ( LETTER );
}
if( isdigit( c ) ) {
yylval = c - '0';
return( DIGIT );
}
return( c );
}
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
В этом приложении находится описание входного синтаксиса Yacc-а в виде спецификации Yacc-а. Контекстные зависимости и т.д. не учитываются. По иронии спецификация входного языка Yacc-а наиболее естественно представляется в виде грамматики LR [2]; неприятная часть начинается, когда идентификатор находится в правиле и за ним немедленно следует действие. Если за эти идентификатором следует двоеточие, то это - начало следующего правила; в противном случае - это продолжение текущего правила, в котором содержится действие. Лексический анализатор смотрит вперед после того, как увидит идентификатор и решает, является ли следующий токен (пропуская пробелы, новые строки, комментарии и т.д.) двоеточием. Если является, то возвращает токен C_IDENTIFIER. В противном случае он возвращает IDENTIFIER. Литералы (строки в кавычках) также возвращаются как IDENTIFIER-ы, но никогда не как часть C_IDENTIFIER-ов.
/* грамматика входных данных Yacc-а */
/* первичные сущности */
/* включает в себя идентификаторы и литералы */
%token IDENTIFIER
/* идентификатор (но не литерал),
за которым следует двоеточие */
%token C_IDENTIFIER
%token NUMBER /* [0-9]+ */
/* зарезервированные слова:
%type => TYPE,
%left => LEFT, и т.д. */
%token LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION
%token MARK /* отметка %% */
%token LCURL /* отметка %{ */
%token RCURL /* отметка %} */
/* литералы - ascii символы обозначают сами себя */
%start spec
%%
spec
: defs MARK rules tail
;
tail
: MARK
{ В этом действии проглачивается остаток правила }
| /* пустое: второй MARK необязателен */
;
defs : /* пусто */
| defs def
;
def
: START IDENTIFIER
| UNION
{ Скопировать определение union в выходной файл }
| LCURL { Скопировать код на C в выходной файл } RCURL
| ndefs rword tag nlist
;
rword
: TOKEN
| LEFT
| RIGHT
| NONASSOC
| TYPE
;
tag
: /* пусто: тег union'а необязателен */
| '<' IDENTIFIER '>'
;
nlist
: nmno
| nlist nmno
| nlist ',' nmno
;
nmno
: IDENTIFIER /* ЗАМЕЧАHИЕ: литералы запрещены с %type */
| IDENTIFIER NUMBER /* ЗАМЕЧАHИЕ: запрещено с %type */
;
/* секция правил */
rules
: C_IDENTIFIER rbody prec
| rules rule
;
rule
: C_IDENTIFIER rbody prec
| '|' rbody prec
;
rbody
: /* empty */
| rbody IDENTIFIER
| rbody act
;
act
: '{'
{ Скопировать действия, транслировать $$, и т.д. } '}'
;
prec
: /* пусто */
| PREC IDENTIFIER
| PREC IDENTIFIER act
| prec ';'
;
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
В этом приложении дается пример грамматики с использованием некоторых продвинутых возможностей, обсуждавшихся в главе 10. Пример с настольным калькулятором из приложения A изменен так, чтобы получился настольный калькулятор, который обеспечивает арифметику с интервалами плавающих точек. Калькулятор понимает константы с плавающей точкой, арифметические операции +, -, *, /, унарный -, и = (присваивание) и имеет 26 переменных с плавающей точкой, от "a" до "z". Более того, он также понимает интервалы, написанные в виде ( x , y ) где x меньше или равен y. Также могут использоваться 26 интервалов-переменных - от "A" до "Z", которые также могут использоваться. Использование подобно подобно тому, что было в приложении A; присваивания не возвращают значений, и ничего не печатают, тогда как выражения печатают значения (с плавающей точкой или интервала).
В этом примере исследуются некоторые интересные возможности Yacc-а и C. Интервалы представляются в виде структуры, состоящей из значений левого и правого концов, хранимых в виде double. Этим структурам при помощи typedef дается имя типа, INTERVAL. Стек значений Yacc-а также может содержать числа с плавающей точкой и целые (используемые как индекс в массивах, содержащих значения переменных). Заметьте, что общая стратегия сильно зависит от возможности присваивать структуры и union-ы в C. В действительности многие действия вызывают функции, также возвращающие структуры.
Также стоит заметить использование YYERROR для обработки условий ошибки: деление на интервал, содержащий 0 и интервал, записанный в неправильном порядке. Hа самом деле, механизм восстановления после ошибок в Yacc-е используется для отбрасывания остатка строки-нарушительницы.
В дополнение к смешиванию типов на стеке значений, эта грамматика также демонстрирует интересное использование синтаксиса для отслеживания типа (т.е. скалярного или интервального) промежуточных выражений. Заметьте, что скаляр может быть автоматически преобразован в интервал, если контекст требует интервального значения. Это вызывает большое количество конфликтов при обработке грамматики Yaccом: 18 сдвиг/понижение и 26 понижение/понижение. Эта проблема может быть увидена при взгляде на две водные строки
2.5 + ( 3.5 - 4. )
и
2.5 + ( 3.5 , 4. )
Заметьте, что 2.5 используется в выражении интервального типа во втором примере, но этот факт неизвестен до тех пор, пока не прочитана ","; к этому времени 2.5 закончена и парсер не может вернуться и изменить свое мнение. Говоря более обще, может быть необходимо посмотреть вперед на произвольное количество токенов, чтобы решить, преобразовывать ли скаляр в интервал. Эта проблема обходится с использованием двух правил для каждого бинарного оператора, работающего с интервалами: одно, когда левый операнд - скаляр и одно - когда левый операнд - интервал. Во втором случае правый операнд должен быть интервалом, так что преобразование будет применено автоматически. Hесмотря на это уклонение, все еще остается много случаев, когда преобразование может или не может быть применено, что ведет к вышеуказанным конфликтам. Они разрешаются перечислением правил, требующих скаляров, первыми в файле спецификаций; таким образом, конфликты разрешаются в сторону сохранения скалярно-типизированных значений скалярно-типизированными до тех пор, пока они вынужденно не преобразовываются в интервалы.
Этот способ обработки производных типов очень поучителен, но не очень общий. Если бы было много типов выражений, а не просто два типа, количество требуемых правил возросло бы драматически, а количество конфликтов - еще более драматически. Таким образом, несмотря на поучительности примера, в обычной среде программирования лучше будет хранить информацию о типе как часть значения, а не как часть грамматики.
Hаконец, немного о лексическом анализе. Единственная необычная вешь - обработка констант с плавающей точкой. Подпрограмма библиотеки C atof используется для произведения преобразования из строки символов в значения с двойной точностью. Если лексический анализатор определяет ошибку, он реагирует на нее, возвращая токен, запрещенный в грамматике, вызывая синтаксическую ошибку в парсере и отсюда восстановления после ошибки.
%{
# include
# include
typedef struct interval
{
double lo, hi;
} INTERVAL;
INTERVAL vmul(), vdiv();
double atof();
double dreg[ 26 ];
INTERVAL vreg[ 26 ];
%}
%start lines
%union
{
int ival; double dval;
INTERVAL vval;
}
/* индексы в массивах dreg, vreg */
%token DREG VREG
/* константа с плавающей точкой */
%token CONST
/* выражение */
%type dexp
/* интервальное выражение */
%type vexp
/* информация о приоритетах операторов */
%left '+' '-'
%left '*' '/'
/* приоритет унарного минуса */
%left UMINUS
%%
lines
: /* empty */
| lines line
;
line
: dexp '\n'
{ printf( "%15.8f\n", $1 ); }
| vexp '\n'
{ printf("(%15.8f , %15.8f )\n",
$1.lo, $1.hi ); }
| DREG '=' dexp '\n'
{ dreg[$1] = $3; }
| VREG '=' vexp '\n'
{ vreg[$1] = $3; }
| error '\n'
{ yyerrok; }
;
dexp
: CONST
| DREG
{ $$ = dreg[$1]; }
| dexp '+' dexp
{ $$ = $1 + $3; }
| dexp '-' dexp
{ $$ = $1 - $3; }
| dexp '*' dexp
{ $$ = $1 * $3; }
| dexp '/' dexp
{ $$ = $1 / $3; }
| '-' dexp~~ %prec UMINUS
{ $$ = - $2; }
| '(' dexp ')'
{ $$ = $2; }
;
vexp
: dexp
{ $$.hi = $$.lo = $1; }
| '(' dexp ',' dexp ')'
{ $$.lo = $2; $$.hi = $4;
if( $$.lo > $$.hi ){
printf(
"interval out of order\n");
YYERROR;
}
}
| VREG
{ $$ = vreg[$1]; }
| vexp '+' vexp
{ $$.hi = $1.hi + $3.hi;
$$.lo = $1.lo + $3.lo; }
| dexp '+' vexp
{ $$.hi = $1 + $3.hi;
$$.lo = $1 + $3.lo; }
| vexp '-' vexp
{ $$.hi = $1.hi - $3.lo;
$$.lo = $1.lo - $3.hi; }
| dexp '-' vexp
{ $$.hi = $1 - $3.lo;
$$.lo = $1 - $3.hi; }
| vexp '*' vexp
{ $$ = vmul( $1.lo, $1.hi, $3 ); }
| dexp '*' vexp
{ $$ = vmul( $1, $1, $3 ); }
| vexp '/' vexp
{ if( dcheck( $3 ) ) YYERROR;
$$ = vdiv( $1.lo, $1.hi, $3 );
}
| dexp '/' vexp
{ if( dcheck( $3 ) ) YYERROR;
$$ = vdiv( $1, $1, $3 );
}
| '-' vexp %prec UMINUS
{ $$.hi = -$2.lo;
$$.lo = -$2.hi; }
| '(' vexp ')'
{ $$ = $2; }
;
%%
/* размер буфера для чисел
с плавающей точкой */
# define BSZ 50
/* лексический анализ */
yylex()
{
register c;
while( (c=getchar()) == ' ' )
{ /* skip over blanks */ }
if( isupper( c ) ) {
yylval.ival = c - 'A'; return( VREG );
}
if( islower( c ) ) {
yylval.ival = c - 'a'; return( DREG );
}
if( isdigit( c ) || c=='.' ) {
/* пожирание цифр, точек, экспонент */
char buf[BSZ+1], *cp = buf;
int dot = 0, exp = 0;
for( ; (cp-buf)= BSZ )
printf(
"константа слишком длинная: обрезана\n");
else ungetc( c, stdin );
/* вернуть обратно последний
прочитанный символ */
yylval.dval = atof( buf );
return( CONST );
}
return( c );
}
INTERVAL hilo( a, b, c, d )
double a, b, c, d;
{
/* возвращает наименьший интервал,
содержащий a, b, c и d
используется процедурами *, / */
INTERVAL v;
if( a>b ) { v.hi = a; v.lo = b; }
else { v.hi = b; v.lo = a; }
if( c>d ) {
if( c>v.hi ) v.hi = c;
if( dv.hi ) v.hi = d;
if( c= 0. && v.lo <= 0. ) {
printf(
"интервал -- знаменатель содержит 0.\n" );
return( 1 );
}
return( 0 );
}
INTERVAL vdiv( a, b, v )
double a, b;
INTERVAL v;
{
return(
hilo( a/v.hi, a/v.lo,
b/v.hi, b/v.lo ) );
}
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
В этом Приложении упоминаются синонимы и возможности, поддерживаемые для исторической целостности, но, по разнообразным причинам, не рекомендуемые.
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |
Yacc многим обязан группой пользователей, которые побуждали меня за пределы моих собственных склонностей и часто даже за пределы моих способностей, в своем бесконечном поиске "еще одной возможности". Их раздражающее нежелание учиться делать то или иное моим способом обычно вело к тому, что я делал это их способом; большей частью они были правы. B. W. Kernighan, P. J. Plauger, S. I. Feldman, C. Imagna, M. E. Lesk, and A. Snyder узнают некоторые свои идеи в текущей версии Yacc-а. C. B. Haley сделал вклад в алгоритм восстановления после ошибок. D. M. Ritchie, B. W. Kernighan, and M. O. Harris помогли перевести этот документ на английский. Al Aho также заслуживает специального упоминания за приведение горы к Мухаммеду и другие любезности.
[ Содержание ] [ Предыдущая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |