YACC YACC СОДЕРЖАНИЕ 1. Введение 2. Основные спецификации 2.1. Действия 2.2. Лексический анализ 3. Алгоритм синтаксического разбора 4. Неоднозначности и конфликты 5. Старшинство операций 6. Обработка ошибок 7. Окружение yacc'а 8. Советы по подготовке спецификаций 8.1. Стиль 8.2. Левая рекурсия 8.3. Уловки анализа лексики 8.4. Зарезервированные слова 9. Более сложные вопросы 9.1. Моделирование действий ошибка и успех 9.2. Доступ к значениям в завершенных правилах 9.3. Использование значений произвольных типов 10. Входной синтаксис yacc'а 11. Примеры 11.1. Простой пример 11.2. Более сложный пример 1. ВВЕДЕНИЕ yacc(1) предоставляет универсальные средства для структуризации исходных данных программ. Пользователь yacc'а готовит специфи- кацию, которая включает: Множество правил, описывающих составные части исходных данных. Действия, выполняемые при применении правила. Определение или описание процедуры нижнего уровня, ана- лизирующей исходные данные. Затем yacc отображает спецификацию в функцию на языке C, обра- батывающую входной поток данных. Эта функция, которая называет- ся процедурой разбора, выполняется, обращаясь к низкоуровневому сканеру исходных данных. Низкоуровневый сканер, называемый лек- сическим анализатором, извлекает из входного потока элементы - лексемы. Лексемы сопоставляются с правилами, описывающими структуру входного текста, то есть с грамматическими правилами. Если правило оказывается подходящим, то выполняется ассоцииро- ванное с ним действие. Действие - это фрагмент программы на языке C. Действия могут возвращать значения, а также использо- вать значения, возвращаемые другими действиями. Ядром yacc-спецификации является набор грамматических правил. Каждое правило описывает синтаксическую конструкцию и дает ей имя. Грамматическое правило может быть, например, таким: date : month_name day ',' year ; где date, month_name и day представляют собой рассматриваемые конструкции; предполагается, что они детализируются в другом месте. В примере запятая заключена в одинарные кавычки. Это оз- начает, что запятая должна встретиться во входном тексте. Двое- точие и точка с запятой служат в правиле всего лишь знаками препинания и при анализе текста не учитываются. При подходящих дополнительных определениях цепочка July 4, 1776 может сопоставиться с данным правилом. Важная часть механизма разбора - лексический анализатор. Эта процедура, задаваемая пользователем, читает входной поток, вы- деляет низкоуровневые конструкции и передает их в качестве лек- сем процедуре разбора. Процедура лексического анализа распозна- ет во входном потоке конструкции, являющиеся терминальными сим- волами, процедура синтаксического разбора - конструкции, являю- щиеся нетерминальными символами. Чтобы избежать путаницы, тер- минальные символы называются лексемами. При решении, как распознавать конструкцию, - используя лекси- ческий анализатор или грамматические правила - имеется значи- тельная свобода. Так, в примере, приведенном выше, могут ис- пользоваться правила: month_name : 'J' 'a' 'n' ; month_name : 'F' 'e' 'b' ; . . . month_name : 'D' 'e' 'c' ; Когда лексический анализатор применяется только для распознава- ния отдельных букв, такие низкоуровневые правила ведут к нап- расным затратам времени и памяти и могут чрезмерно усложнить для yacc'а обработку спецификации. Обычно лексический анализа- тор распознает названия месяцев и возвращает указание на то, что найдено month_name. В этом случае month_name является лек- семой и более детальных правил не требуется. Отдельные знаки, такие как запятая, также можно пропускать че- рез лексический анализатор и считать лексемами. Спецификации обладают очень большой гибкостью. Довольно легко добавить к нашему примеру правило: date : month '/' day '/' year ; допускающее использование во входном тексте конструкции 7/4/1776 в качестве синонима ранее упоминавшейся цепочки July 4, 1776 В большинстве случаев новое правило можно вставить в работающую систему с минимальными усилиями и опасностью сделать некоррект- ными уже имеющиеся входные данные. Читаемый текст может не согласовываться со спецификациями. При сканировании входного текста слева направо ошибки выявляются настолько рано, насколько это вообще возможно. Таким образом не только значительно уменьшается вероятность чтения и обработки некорректных данных, но и облегчается выявление места оиибки. Обработка ошибок, которая задается как часть спецификаций, поз- воляет или повторно обработать некорректные данные, или просто пропустить их. В некоторых случаях yacc не может породить процедуру разбора по заданному множеству спецификаций. Например, спецификации могут быть внутренне противоречивыми, либо требовать более мощного механизма распознавания, чем тот, который доступен yacc'у. Пер- вый случай бывает вызван ошибками проектирования спецификаций, второй же часто можно исправить, разработав более мощный лекси- ческий анализатор или переписав некоторые из грамматических правил. Хотя yacc не в состоянии обработать произвольные специ- фикации, сравнение его возможностей с аналогичными системами - в его пользу. Более того, конструкции, с которыми трудно спра- виться yacc'у, часто также трудны и для людей. Некоторые поль- зователи заявляют, что при разработке программ дисциплина фор- мирования правильных yacc-спецификаций для исходных данных поз- воляет на раннем этапе выявить ошибки в постановке задачи и проектировании. В оставшейся части этой главы рассматриваются следующие вопро- сы: Основные шаги подготовки yacc-спецификации. Алгоритм синтаксического разбора. Обработка неоднозначностей. Обработка приоритетов операций в арифметических выраже- ниях. Обнаружение и исправление ошибок. Окружение и специфические свойства процедур разбора, порождаемых yacc'ом. Предложения по улучшению стиля и повышению эффективнос- ти спецификаций. Более сложные вопросы. Кроме того, приводятся два примера и дается сводка входного синтаксиса yacc'а. 2. ОСНОВНЫЕ СПЕЦИФИКАЦИИ Имена обозначают лексемы или нетерминальные символы. YACC тре- бует, чтобы имена лексем были указаны явно. Хотя лексический анализатор можно включить в файл спецификаций, определение его в отдельном файле, вероятно, более соответствует принципам мо- дульного проектирования. Подобно лексическому анализатору, в файл спецификаций могут быть также включены и другие подпрог- раммы. Таким образом, каждый файл спецификаций теоретически состоит из трех секций: определений, (грамматических) правил и подпрограмм. Секции отделяются двумя знаками процента %% (знак % используется в yacc-спецификациях как универсальный управляю- щий). Если используются все секции, полный файл спецификаций выглядит следующим образом: определения %% правила %% подпрограммы Секции определений и подпрограмм являются необязательными. Ми- нимальная допустимая yacc-спецификация - это % правила Пробелы, табуляции и переводы строки, которые встречаются вне имен и зарезервированных слов, игнорируются. Комментарии могут быть везде, где допустимо имя. Они заключаются в "скобки" /*...*/, как в языке C. Секция правил составляется из одного или большего числа грамма- тических правил. Грамматическое правило имеет вид: нтс : тело ; где нтс - нетерминальный символ, а тело - последовательность из нуля или нескольких имен и литералов. Двоеточие и точка с запя- той - знаки препинания yacc'а. Имена могут иметь произвольную длину и должны состоять из букв, точек, подчеркиваний и цифр, однако имя не может начинаться с цифры. Прописные и строчные буквы различаются. Имена, использу- емые в теле грамматического правила, могут представлять лексемы или нетерминальные символы. Литерал - это знак, заключенный в одиночные кавычки, '. Как и в языке C, в качестве управляющего используется знак \, восприни- маются также все принятые в C управляющие последовательности. Например, yacc трактует перечисленные ниже последовательности следующим образом: '\n' перевод строки '\r' возврат каретки '\'' одинарная кавычка ' '\\' обратная наклонная черта \ '\t' табуляция '\b' забой '\f' переход к новой странице '\xxx' xxx в восьмеричной записи По ряду технических причин символ NULL (\0 или 0) нельзя ис- пользовать в грамматических правилах. Если есть несколько грамматических правил с одной и той же ле- вой частью, то, чтобы избежать переписывания левой части, можно использовать вертикальную черту, |. Перед вертикальной чертой точку с запятой ставить не нужно. Например, грамматические пра- вила A : B C D ; A : E F ; A : G ; с использованием вертикальной черты могут быть заданы для yacc'а в виде A | B C D | E F | G ; Не обязательно, чтобы грамматические правила с одной и той же левой частью появлялись в секции правил все вместе, однако та- кая запись облегчает чтение спецификации и ее модификацию Если нетерминал сопоставляется с пустой цепочкой, это можно вы- разить следующим образом: epsilon : ; yacc истолковывает пустое место после двоеточия как нетерми- нальный символ, называемый epsilon. Имена, представляющие лексемы, должны быть описаны. Проще всего это сделать, поместив в секции определений конструкцию вида %token имя1 имя2 ... Считается, что всякое имя, не описанное в секции определений, представляет нетерминальный символ. Каждый нетерминальный сим- вол должен встретиться в левой части по крайней мере одного правила. Из всех нетерминальных символов особую роль играет начальный символ. По умолчанию начальным считается символ, стоящий в ле- вой части первого грамматического правила в секции правил. Мож- но (и желательно) явно объявить начальный символ в секции опре- делений при помощи ключевого слова %start: %start начальный_символ О конце входного текста процедуре разбора сигнализирует специ- альная лексема, называемая маркером конца. Маркер конца предс- тавляется нулем или отрицательным числом. Если прочитанные лек- семы, исключая маркер конца, образуют конструкцию, сопоставляю- щуюся с начальным символом, то после того, как найден маркер конца и исходный текст принят, процедура разбора возвращает уп- равление вызвавшей ее процедуре. Если маркер конца встречается в любом другом контексте, это ошибка. Возвратить, когда следует, маркер конца, - задача определяемого пользователем лексического анализатора. Обычно маркер конца представляет некоторые вполне очевидные состояния ввода/вывода, такие как конец файла или конец записи. 2.1. Действия С каждым грамматическим правилом пользователь может связать действия, которые будут выполняться при применении правила. Действия могут возвращать значения и получать значения, возвра- щенные предыдущими действиями. Кроме того, если требуется, лек- сический анализатор может возвращать значения лексем. Действие - это произвольный оператор на языке C. Следовательно, в действии можно выполнять операции ввода/вывода, вызывать подпрограммы, изменять значения массивов и переменных. Действие задается одним или несколькими операторами в фигурных скобках, { и }. Например, конструкции A : '(' B ')' { hello (1, "abc"); } ; и XXX : YYY ZZZ { (void) printf ("сообщение\n"); flag = 25; } ; являются грамматическими правилами с действиями. Для организации взаимосвязи между действиями и процедурой раз- бора используется знак $ (доллар). Псевдопеременная $$ предс- тавляет значение, возвращаемое завершенным действием. Например, действие {$$ = 1;} возвращает значение 1; в сущности, это все, что оно делает. Чтобы получать значения, возвращаемые предыдущими действиями и лексическим анализатором, действие может использовать псевдопе- ременные $1, $2, ... $n. Они обозначают значения, возвращаемые компонентами от 1-го до n-го, стоящими в правой части правила; компоненты нумеруются слева направо. В случае правила A : B C D ; $2 принимает значение, возвращенное C, а $3 - значение, возвра- щенное D. Пример с правилом expr : '(' expr ')' ; банален. Ожидается, что значение, возвращаемое этим правилом, равно значению expr в скобках. Поскольку первый компонент конструкции - левая скобка, требуемый результат можно получить так: expr : '(' expr ')' { $$ = $2; } ; По умолчанию значение правила равно значению первого компонента в нем ($1). Поэтому грамматические преавила вида A : B ; зачастую не требуют явного указания действия. В предыдущих при- мерах действия всегда выполнялись в конце применения правила. Иногда же бывает желательно получить управление до того, как правило применено полностью. yacc позволяет писать действие в середине правила так же, как и в конце. Считается, что такое действие возвращает значение, доступное действиям справа от не- го посредством обычного механизма $. В свою очередь, оно имеет доступ к значениям, возвращаемым действиями слева от него. Та- ким образом, в правиле, указанном ниже, результатом действия является присваивание переменной x значения 1, а переменной y - значения, которое возвращает C. A : B { $$ = 1; } C { x = $2; y = $3; } ; Для обработки действий, указанных не в конце правила, yacc фор- мирует нетерминал с новым именем и новое правило, сопоставляю- щее данное имя с пустой цепочкой. Внутреннее действие - это действие, запускаемое при применении дополнительного правила. yacc трактует рассмотренный пример, как если бы он был записан в виде $ACT : /* пусто */ { $$ = 1; } ; A : B $ACT C { x = $2; y = $3; } ; где $ACT - пустая цепочка. Во многих приложениях действия не осуществляют вывод непос- редственно. Прежде чем сформировать результат, в памяти конст- руируется такая структура данных, как дерево разбора, и выпол- няются ее трансформации. Деревья разбора особенно легко конст- руировать, если даны процедуры для формирования и управления древовидными структурами. Например, предположим, имеется C- функция node, написанная таким образом, что вызов node (L, n1, n2) создает узел с меткой L и потомками n1 и n2 и возвращает указа- тель на него. Тогда дерево разбора можно построить при помощи действий вида expr : expr '+' expr { $$ = node ('+', $1, $3); } ; Пользователь может определить дополнительные переменные, чтобы использовать их в действиях. Описания и определения могут быть указаны в секции определений между последовательностями %{ и %}. Эти описания и определения являются глобальными, поэтому они доступны в действиях и могут быть сделаны доступными для лексического анализатора. Например, если поместить в секцию оп- ределений строку %{ int variable = 0; %} переменная variable будет доступна всем действиям. Пользовате- лям следует избегать имен, начинающихся с yy, поскольку yacc- процедура разбора использует только такие имена. В примерах, рассмотренных до сих пор, все значения были целочисленными. Ра- бота со значениями других типов обсуждается в разделе БОЛЕЕ СЛОЖНЫЕ ВОПРОСЫ. 2.2. Лексический анализ Пользователь должен определить лексический анализатор, который читает входной поток и передает лексемы (со значениями, если требуется) процедуре разбора. Лексический анализатор - это це- лочисленная функция с именем yylex. Функция возвращает номер_- лексемы, характеризующий вид прочитанной лексемы. Если этой лексеме соответствует значение, его надо присвоить внешней пе- ременной yylval. Процедуры синтаксического разбора и лексического анализа должны быть согласованы относительно номеров лексем. Номера может выб- рать yacc или пользователь. В обоих случаях, чтобы дать возмож- ность лексическому анализатору использовать символические обоз- начения номеров лексем, применяется механизм #define языка C. Например, предположим, что имя лексемы DIGIT определено в сек- ции определений файла yacc-спецификаций. Чтобы возвратить тре- буемый номер лексемы, соответствующий фрагмент лексического анализатора может выглядеть так: int yylex () { extern int yylval; int c; . . . c = getchar (); . . . switch (c) { . . . case '0': case '1': . . . case '9': yylval = c - '0'; return (DIGIT); . . . } . . . } Требуется возвратить номер лексемы DIGIT и значение, равное численному значению цифры. При условии, что процедура лексичес- кого анализа помещена в секцию подпрограмм файла спецификаций, идентификатор DIGIT определяется как номер, соответствующий лексеме DIGIT. Такой механизм дает понятные, легко модифицируемые лексические анализаторы. Единственная неприятность, которую следует избе- гать, - это использование в грамматических правилах в качестве имен лексем слов, зарезервированных в языке C или в yacc'е. Например, использование имен лексем if или while почти наверня- ка приведет к серьезным трудностям при компиляции лексического анализатора. Имя лексемы error зарезервировано для обработки ошибок, не следует использовать его без нужды. По умолчанию имена лексем выбирает yacc. В этом случае номер лексемы для литералов равен численному значению соответствующе- го символа в принятой кодировке символов. Остальные имена полу- чают номера лексем, начиная с 257. Если утилита yacc вызывается с опцией -d, порождается файл с именем y.tab.h, который содер- жит операторы #define для лексем. Если пользователь предпочитает сам назначать имена лексем, сра- зу за первым вхождением имени лексемы или литерала в секции оп- ределений должно следовать неотрицательное целое число. Это число становится номером лексемы для имени или литерала. Не оп- ределенные таким способом имена и литералы доопределяет по умолчанию yacc. Данный механизм оставляет потенциальную возмож- ность многократного использования одного номера. Будьте осто- рожны, обеспечьте различие всех номеров лексем. По историческим причинам маркер конца должен иметь нулевой или отрицательный номер лексемы. Данный номер лексемы не может быть переопределен пользователем. Поэтому все лексические анализато- ры должны возвращать нуль или отрицательное число по достижении конца исходного текста. Весьма полезным инструментом для построения лексических анали- заторов является lex(1). Работа лексических анализаторов, по- рожденных lex'ом, хорошо согласуется с процедурами синтаксичес- кого разбора, порожденными yacc'ом. Спецификации лексических анализаторов используют не грамматические правила, а регулярные выражения. lex удобно использовать для порождения довольно хит- роумных лексических анализаторов, однако остаются отдельные языки (такие как ФОРТРАН), которые не опираются ни на какое те- оретическое обоснование и лексические анализаторы для которых приходится мастерить вручную. 3. АЛГОРИТМ СИНТАКСИЧЕСКОГО РАЗБОРА yacc отображает файл спецификаций в процедуру на языке C, кото- рая разбирает входной текст в соответствии с заданной специфи- кацией. Алгоритм, используемый для того, чтобы перейти от спе- цификации к C-процедуре, сложен и здесь обсуждаться не будет. Алгоритм же самого разбора относительно прост, знание его об- легчит понимание механизма нейтрализации ошибок и обработки не- однозначностей. yacc порождает алгоритм разбора, использующий конечный автомат со стеком. Кроме того, алгоритм разбора может прочесть и запом- нить следующую входную лексему (которая называется предвари- тельно просмотренной). Текущее состояние автомата всегда сохра- няется на вершине стека. Состояния конечного автомата задаются небольшими целочисленными значениями. В начальный момент авто- мат находится в состоянии 0 (стек содержит единственное значе- ние 0) и предварительно просмотренная лексема не прочитана. В алгоритме имеется всего четыре типа действий - перенос (shift), свертка (reduce), успех (accept), ошибка (error). Шаг работы алгоритма состоит в следующем: Основываясь на текущем состоянии автомата, алгоритм вы- ясняет, требуется ли для выбора очередного действия предварительно просмотренная лексема. Если требуется, но не прочитана, алгоритм запрашивает следующую лексему у функции yylex. Используя текущее состояние и, если нужно, предвари- тельно просмотренную лексему, алгоритм выбирает очеред- ное действие и выполняет его. В результате состояния могут быть помещены в стек или извлечены из него, пред- варительно просмотренная лексема может быть обработана, а может быть и нет. Действие перенос - наиболее частое действие алгоритма. В выпол- нении действия перенос всегда участвует предварительно просмот- ренная лексема. Например, для состояния 56 может быть определе- но действие IF shift 34 что означает: в состоянии 56, если предварительно просмотренная лексема равна IF, текущее состояние (56) помещается в стек, те- кущим становится состояние 34 (заносится на вершину стека). Предварительно просмотренная лексема очищается. Действие свертка препятствует неограниченному росту стека. Оно выполняется, когда алгоритм, просмотрев правую часть правила, обнаруживает в обрабатываемых данных ее вхождение, которое и заменяет левой частью. Может понадобиться проанализировать предварительно просмотренную лексему (обычно этого не требует- ся), чтобы решить, выполнять свертку или нет. Часто подразуме- ваемым действием (которое обозначается точкой) оказывается именно свертка. Действия свертка ассоциируются с отдельными грамматическими правилами. Грамматические правила (как и состояния) нумеруются небольшими целыми числами, и это приводит к некоторой путанице. В действии . reduce 18 имеется в виду грамматическое правило 18, тогда как в действии IF shift 34 - состояние 34. Предположим, выполняется свертка для правила A : x y z ; Действие свертка зависит от символа в левой части правила (в данном случае A) и числа символов в правой части (в данном слу- чае три). При свертке сначала из стека извлекаются три верхних состояния. (В общем случае число извлекаемых состояний равно числу символов в правой части правила). В сущности, эти состоя- ния были занесены в стек при распознавании x, y и z и больше не нужны. После того, как извлечены эти состояния, на вершине сте- ка оказывается состояние автомата на момент перед началом при- менения данного правила. Для этого состояния и символа, стояще- го в левой части правила, выполняется действие, имеющее резуль- тат, аналогичный переносу с аргументом A. Конечный автомат пе- реходит в новое состояние, которое заносится в стек, и разбор продолжается. Имеются, однако, существенные отличия между обра- боткой символа из левой части правила и обычным переносом лек- семы, поэтому это действие называется действием переход (goto). В частности, предварительно просмотренная лексема при переносе очищается, а при переходе не затрагивается. В любом случае, открывшееся на вершине стека состояние содержит действие A goto 20 выполнение которого приводит к тому, что состояние 20 помещает- ся на вершину стека и становится текущим. В сущности, действие свертка, извлекая состояния из стека, возвращает разбор к состоянию, в котором было начато применение правой части данного правила. После этого алгоритм разбора пос- тупает так, как будто в данный момент обнаружено не вхождение правой части, а символ, стоящий в левой части правила. Если правая часть правила пуста, ни одно состояние из стека не изв- лекается. Открывающееся состояние - просто то же самое текущее состояние. Действие свертка важно также для понимания процесса выполнения действий, заданных пользователем, и передачи значений. При свертке правила перед преобразованием стека выполняются дейст- вия, ассоциированные с правилом. Кроме стека, содержащего сос- тояния, параллельно поддерживается еще один стек, который со- держит значения, возвращаемые лексическим анализатором и дейст- виями. При выполнении переноса в стек значений заносится внеш- няя переменная yylval. После выполнения пользовательского дей- ствия свертка завершается. При выполнении действия переход в стек значений заносится внешняя переменная yyval. Псевдопере- менные $1, $2 и т.д. указывают на элементы стека значений. Понять два других действия алгоритма значительно проще. Дейст- вие успех обозначает, что входной текст прочитан и сопоставлен со спецификацией. Это действие выполняется только в том случае, когда предварительно просмотренная лексема равна маркеру конца. Оно обозначает, что работа алгоритма успешно завершена. Дейст- вие ошибка, напротив, представляет ситуацию, когда алгоритм не может дальше продолжать разбор в соответствии со спецификацией. Исходные лексемы (вместе с предварительно просмотренной лексе- мой) таковы, что никакой последующий текст не приведет к допус- тимым исходным данным. Алгоритм сообщает об ошибке и пытается восстановить ситуацию и продолжить разбор. Позднее будет обсуж- даться нейтрализация, а не просто обнаружение ошибок. Рассмотрим yacc-спецификацию: %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, алгоритм разбора должен обратиться к входной цепочке, поэтому первая лексема, DING, считывается и становится предварительно просмотренной. Действие в состоянии 0 над DING - перенос 3, состояние 3 помещается в стек, а предварительно просмотренная лексема очищается. Состоя- ние 3 становится текущим. Читается следующая лексема, DONG, и уже она становится предварительно просмотренной. Действие в состоянии 3 над DING - перенос 6, состояние 6 помещается в стек, а предварительно просмотренная лексема очищается. Теперь стек содержит 0, 3 и 6. В состоянии 6, даже не опрашивая пред- варительно просмотренную лексему, алгоритм выполняет свертку sound : DING DONG по правилу 2. Два состояния, 6 и 3, извлекаются из стека, на вершине которого оказывается состояние 0. В соответствии с опи- санием состояния 0 выполняется sound goto 2 Состояние 2 помещается в стек и становится текущим. В состоянии 2 должна быть прочитана следующая лексема, DELL. Действие - перенос 5, поэтому состояние 2 помещается в стек, который теперь содержит 0, 2 и 5, а предварительно просмотрен- ная лексема очищается. В состоянии 5 возможно единственное дей- ствие, свертка по правилу 3. В правой части этого правила один символ, поэтому из стека извлекается единственное состояние 5, а на вершине стека открывается состояние 2. Переход в состоянии 2 к place (левая часть правила 3) приводит к состоянию 4. Те- перь стек содержит 0, 2 и 4. В состоянии 4 единственное дейст- вие - свертка по правилу 1. В его правой части два символа, по- этому из стека извлекаются два состояния, вновь открывая состо- яние 0. В состоянии 0 переход к rhyme переводит разбор в состо- яние 1. В состоянии 1 читается входная цепочка и обнаруживается маркер конца, в файле y.output он обозначается $end. Действие в состоянии 1 (когда найден маркер конца) - успешное завершение разбора. Читателю настоятельно рекомендуется проследить, как действует алгоритм, если сталкивается с такими некорректными цепочками, как DING DONG DONG, DING DONG, DING DONG DELL DELL и т.д. Нес- колько минут, затраченных на эти и другие простые примеры, оку- пятся, когда возникнут вопросы в более сложных случаях. 4. НЕОДНОЗНАЧНОСТИ И КОНФЛИКТЫ Множество грамматических правил неоднозначно, если существует входная цепочка, которую можно структурировать несколькими раз- личными способами. Например, правило expr : expr '-' expr ; - естественный способ выразить тот факт, что арифметическое вы- ражение можно сформировать, взяв два других выражения и разде- лив их знаком минус. К сожалению, это правило не полностью оп- ределяет способ структуризации всей совокупности исходных дан- ных. Так, если входная цепочка - это 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 по умолчанию использует два метода разрешения неоднознач- ностей: При конфликте перенос-свертка по умолчанию выполняется перенос. При конфликте свертка-свертка по умолчанию выбирается правило, встретившееся в yacc-спецификации первым. Первый метод устанавливает, что свертки менее предпочтительны, чем переносы, если есть выбор. Второй метод дает пользователю довольно грубый механизм управления разбором, поэтому, когда возможно, конфликтов свертка-свертка следует избегать. Конфликты могут возникать либо из-за ошибок в исходных данных или в логике спецификаций, либо из-за того, что грамматические правила (вполне корректные) требуют более сложного алгоритма разбора, чем может построить yacc. Использование действий внут- ри правил также может вызывать конфликты, если действие должно выполняться до того, как алгоритм сможет определить достоверно, какое правило следует применить. В таких случаях указанные ме- тоды разрешения неоднозначностей не подходят, поскольку приво- дят к некорректному алгоритму разбора. По этой причине yacc всегда сообщает число конфликтов перенос-свертка и свертка- свертка, разрешенных при помощи метода 1 и метода 2. Вообще говоря, если можно применить методы разрешения неодноз- начностей и породить корректный алгоритм разбора, то можно и переписать грамматические правила таким образом, чтобы они об- рабатывали те же исходные данные, но не содержали конфликтов. По этой причине большинство более ранних генераторов компилято- ров считали конфликты фатальными ошибками. Опыт показал, одна- ко, что подобное переписывание противоестественно и порождает медленные алгоритмы. Поэтому yacc порождает алгоритмы разбора даже при наличии конфликтов. Рассмотрим методы разрешения неоднозначностей на следующем при- мере. stat : IF '(' cond ')' stat | IF '(' cond ')' stat ELSE stat ; Это - фрагмент спецификации языка программирования, включающего оператор if-then-else. В приведенном правиле 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, прочитать S2, а затем выполнить свертку правой части цепочки IF ( C1 ) IF ( C2 ) S1 ELSE S2 по if-else-правилу и получить IF ( C1 ) stat что в свою очередь свертывается по простому if-правилу. Это со- ответствует второй интерпретации, которая обычно считается бо- лее предпочтительной. Такой конфликт перенос-свертка возникает только тогда, когда текущим является определенный входной символ, ELSE, и прочитана определенная входная цепочка, Вообще говоря, может быть много конфликтов, и каждому соот- ветствует входной символ и прочитанная перед ним входная цепоч- ка. Прочитанная входная цепочка задает состояние алгоритма раз- бора. Сообщения yacc о конфликтах лучше всего понять, анализируя описание алгоритма, формируемое по опции -v. Например, фраг- мент, описывающий рассмотренное выше конфликтное состояние, выглядит так: 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, выполняется свертка stat : IF ( cond ) stat по грамматическому правилу 18. Вновь напомним, что номера, следующие за командами переноса, указывают состояния, а номера, следующие за командами свертки, обозначают грамматические правила. В файле y.output номера пра- вил печатаются в скобках после самих правил, для которых может быть выполнена свертка. В большинстве состояний возможно задан- ное по умолчанию действие свертка. Пользователь, обнаруживший непредвиденные конфликты перенос-свертка, захочет, быть может, просмотреть файл описаний, чтобы решить, допустимы ли действия по умолчанию. 5. СТАРШИНСТВО ОПЕРАЦИЙ Есть ситуация, в которой приведенные выше методы разрешения конфликтов не подходят. Имеется в виду разбор арифметических выражений. Большинство конструкций, обычно используемых в ариф- метических выражениях, можно естественным образом описать при помощи понятия уровней старшинства (приоритетов) операций и ин- формации о левой или правой ассоциативности. Применяя данный механизм, можно использовать неоднозначные грамматики с соот- ветствующими правилами разрешения неоднозначностей для порожде- ния алгоритмов разбора, которые быстрее и легче задавать, чем алгоритмы, построенные из однозначных грамматик. Основная идея заключается в том, чтобы записать грамматические правила для всех требуемых бинарных и унарных операций в виде expr : expr OP expr или expr : UNARY expr В результате получается неоднозначная грамматика с очень боль- шим числом конфликтов. В качестве метода разрешения неоднознач- ностей пользователь специфицирует приоритеты (степень связыва- ния) всех операций и ассоциативность бинарных операций. Этой информациии достаточно, чтобы дать возможность yacc'у разрешить конфликты и построить алгоритм разбора, реализующий заданные приоритеты и ассоциативности. Приоритеты и ассоциативности связываются с лексемами в секции определений. Это делается в группе строк, начинающихся с ключе- вых слов yacc'а %left, %right или %nonassoc, за которыми следу- ют списки лексем. Считается, что все лексемы в одной строке имеют одни и те же приоритет и ассоциативность; строки указыва- ются в порядке возрастания приоритета. Так, строки %left '+' '-' %left '*' '/' задают приоритет и ассоциативность четырех арифметических опе- раций. '+' и '-' левоассоциативны и имеют меньший приоритет, чем также левоассоциативные '*' и '/'. Для описания правоассо- циативных операций используется ключевое слово %right, а для описания операций, подобных операции .LT. в Фортране, которые не являются ассоциативными, - ключевое слово %nonassoc. Напри- мер, выражение A .LT. B .LT. C некорректно в Фортране; поэтому такую операцию следует описать в yacc при помощи ключевого слова %nonassoc. Действие названных ключевых слов иллюстрирует спецификация %right '=' %left '+' '-' %left '*' '/' %% expr : expr '=' 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 указывается сразу за телом правила, перед дей- ствием или завершающей точкой с запятой; за ключевым словом следует имя лексемы или литерал. В результате приоритет правила становится таким же, как и у данной лексемы или литерала. Нап- ример, правила %left '+' '-' %left '*' '/' %% expr : expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '-' expr %prec '*' | NAME ; можно использовать, чтобы установить унарному минусу тот же приоритет, что и у умножения. Лексему, описанную при помощи конструкций %left, %right или %nonassoc, можно (но не обязательно) описать и при помощи %to- ken. Приоритеты и ассоциативность yacc использует для того, чтобы разрешить конфликты разбора. Они задают следующие методы разре- шения неоднозначностей: Приоритеты и ассоциативность приписываются тем лексемам и литералам, для которых они заданы явно. Грамматическому правилу сопоставляются приоритет и ас- социативность последней лексемы или литерала в теле правила. В случае использования конструкции %prec это сопоставление переопределяется. Некоторым правилам при- оритет и ассоциативность могут не сопоставляться. Если есть конфликт свертка-свертка или конфликт сверт- ка-перенос, и входной символ или грамматическое правило не имеют приоритета и ассоциативности, то используется общий метод разрешения неоднозначностей, приведенный в начале раздела, и выдается информация о конфликтах. Если есть конфликт свертка-перенос и как грамматическо- му правилу, так и входному символу сопоставлен приори- тет и ассоциативность, то конфликт разрешается в пользу той операции перенос или свертка, которой соответствует больший приоритет. Если приоритеты равны, используется информация об ассоциативности. Левая ассоциативность обозначает свертку, правая - перенос, неассоциативность - ошибку. Конфликты, разрешенные при помощи приведенного метода, не учи- тываются при подсчете сообщаемого yacc'ом числа конфликтов пе- ренос-свертка и свертка-свертка. Это означает, что ошибки в спецификации приоритетов могут замаскировать ошибки во входной грамматике. Хорошо было бы воздерживаться от задания приорите- тов или использовать их весьма осторожно, пока не приобретен определенный опыт. Чтобы убедиться, что получен именно тот ал- горитм разбора, который требуется, следует изучить содержимое файла y.output. 6. ОБРАБОТКА ОШИБОК Обработка ошибок - это чрезвычайно сложная область; многие свя- занные с ней проблемы являются семантическими. Когда ошибка найдена, может потребоваться, например, очистить память, в ко- торой хранилось дерево разбора, удалить или изменить содержимое таблицы символов и (или), чаще всего, установить переключатели, препятствующие дальнейшему формированию выходных данных. Далеко не всегда приемлемо при обнаружении ошибки вообще прек- ратить обработку. Полезнее продолжить сканирование исходного текста для того, чтобы обнаружить и другие синтаксические ошиб- ки. При этом возникает проблема нейтрализации ошибки и возоб- новления разбора. Широкий класс алгоритмов нейтрализации дости- гает цели, пропуская несколько лексем во входной цепочке и пы- таясь найти состояние, в котором можно возобновить разбор ис- ходного текста. Чтобы позволить пользователю как-то управлять данным процессом, в yacc'е зарезервирована лексема с именем error. Это имя можно использовать в грамматических правилах. Оно используется для указания мест, где ожидаются ошибки и может потребоваться их нейтрализация. Алгоритм разбора очищает стек, пока не окажется в состоянии, в котором допустима лексема error. Затем он посту- пает так, будто лексема error является текущей предварительно просмотренной, и выполняет действие, оказавшееся текущим. Пред- варительно просмотренная лексема затем устанавливается равной лексеме, которая вызвала ошибку. Если специальных "ошибочных" правил не задано, после того, как ошибка обнаружена, обработка прекращается. Чтобы предотвратить каскад сообщений об ошибках, алгоритм раз- бора после их обнаружения остается в некорректном состоянии, пока успешно не прочитаны и не обработаны три лексемы. Если ошибка обнаруживается, когда разбор уже находится в некоррект- ном состоянии, сообщение не выдается, и входная лексема молча отбрасывается. Например, правило вида stat : error означает, что при синтаксической ошибке алгоритм разбора пыта- ется перескочить оператор, в котором встретилась ошибка. Более точно, алгоритм продолжает сканирование, обнаруживает, что три лексемы за оператором могут оказаться допустимыми, и начинает обработку с первой из них. Если начало операторов недостаточно отчетливо выделяется, алгоритм может по ошибке стартовать с се- редины оператора и закончиться обнаружением второй ошибки, на самом деле не существовавшей. Со специальными "ошибочными" правилами такого вида могут быть ассоциированы действия, которые могут пытаться заново инициали- зировать таблицы и т.д. Такие правила, как предыдущее, универсальны, но ими трудно уп- равлять. Правила, подобные stat : error ';' несколько удобнее. Здесь, когда возникает ошибка, алгоритм пы- тается перескочить оператор, переходя на следующую точку с за- пятой. Все лексемы после ошибочной и до следующей точки с запя- той пропускаются. После того как точка с запятой найдена, для данного правила делается свертка и выполняется связанное с ним действие по нейтрализации ошибки. Еще одна форма error-правила возникает в интерактивных приложе- ниях, где может потребоваться разрешить после ошибки перенаб- рать строку. Пример input : error '\n' { printf ("Перенаберите последнюю строку: "); } input { $$ = $4; } ; показывает, как это можно сделать. Такой подход имеет, однако, и недостатки. Алгоритм должен корректно обработать три входные лексемы перед тем, как вернется в корректное состояние. Если перенабранная строка содержит ошибки в первых двух лексемах, алгоритм молча удалит их, что, конечно, неприемлемо. Имеется механизм, который принуждает алгоритм разбора завершить нейтра- лизацию ошибок. Включенный в действие оператор yyerrok ; возвращает алгоритм в нормальное состояние. Последний пример можно переписать в виде input : error '\n' { yyerrok; printf ("Перенаберите последнюю строку: "); } input { $$ = $4; } ; Как упоминалось выше, сразу после символа error предварительно просмотренная лексема равна входной лексеме, на которой была обнаружена ошибка. Иногда это неуместно; задачу выбора коррект- ного места для возобновления разбора может взять на себя дейст- вие, соответствующее правилу, содержащему error. В этом случае предыдущая предварительно просмотренная лексема должна быть очищена. Оператор yyclearin ; помещенный в действие, даст желаемый результат. Предположим, например, что действие после error должно вызывать некоторую замысловатую процедуру нейтрализации (определенную пользовате- лем), пытающуюся возобновить разбор с начала следующего кор- ректного оператора. Предполагается, что после того, как вызвана данная процедура, следующая лексема, возвращаемая yylex() - это первая лексема в корректном операторе. Старая недопустимая лек- сема должна быть отброшена и установлено состояние error. К це- ли ведет правило, подобное следующему: stat : error { resynch (); yyerrok; yyclearin; } ; Продемонстрированные методы, возможно, грубоваты, но позволяют просто и довольно эффективно нейтрализовывать большинство оши- бок; Более того, пользователь может управлять теми действиями по обработке ошибок, которых требуют другие фрагменты програм- мы. 7. ОКРУЖЕНИЕ YACC'А В результате обработки пользовательской спецификации утилитой yacc создается содержащий C-подпрограммы файл y.tab.c. Функция, которую порождает yacc, называется yyparse(); это функция с це- лочисленным результатом. Когда она выполняется, то периодически запрашивает у yylex(), функции лексического анализа, заданной пользователем (см. раздел ЛЕКСИЧЕСКИЙ АНАЛИЗ), входные лексемы. В конечном итоге либо обнаруживается ошибка, yyparse() возвра- щает значение 1 и восстановление после ошибки невозможно, либо лексический анализатор возвращает маркер конца и разбор успешно завершается. В этом случае yyparse() возвращает значение 0. Чтобы получить работающую программу, пользователь должен сфор- мировать для процедуры разбора определенное окружение. Напри- мер, как в любой программе на языке C, должна быть определена процедура с именем main(), вызывающая yyparse(). Кроме того, чтобы печатать сообщение об обнаруженной синтаксической ошибке, нужна процедура, называемая yyerror(). Эти две процедуры в той или иной форме должны быть заданы поль- зователем. Чтобы упростить на начальном этапе работу с yacc'ом, предоставляется библиотека с подразумеваемыми версиями функций main() и yyerror(). Библиотека задается при помощи аргумента -ly команды cc(1) или редактора связей. Исходный текст main () { return (yyparse ()); } и #include yyerror (s) char *s; { (void) fprintf (stderr, "%s\n", s); } демонстрирует банальность этих предопределенных программ. Аргу- мент у функции yyerror() - текст, содержащий сообщение об ошиб- ке, обычно syntax error. В реальных приложениях чаще выполняют- ся более сложные действия. Обычно программа подсчитывает номер входной строки и печатает его вместе с сообщением об обнаруже- нии синтаксической ошибки. Внешняя переменная целого типа yyc- har содержит номер предварительно просмотренной лексемы на мо- мент обнаружения ошибки. Это может представлять некоторый инте- рес для формирования лучшей диагностики. Так как функция main() вероятнее всего задается пользователем (необходимо прочесть ар- гументы и т.п.), yacc-библиотека полезна только в маленьких проектах или на ранних этапах разработки больших. Внешняя переменная целого типа yydebug обычно устанавливается равной 0. Если она имеет ненулевое значение, процедура разбора будет выдавать подробное описание действий, включающее сообще- ние о прочитанных входных символах и выполняемых операциях раз- бора. Значение этой переменной можно переустановить, используя отладчик sdb(1). 8. СОВЕТЫ ПО ПОДГОТОВКЕ СПЕЦИФИКАЦИЙ Этот раздел содержит разнообразные рекомендации по подготовке эффективных, легко изменяемых и понятных спецификаций. 8.1. Стиль Трудно написать правила, которые выполняют серьезные действия и к тому же имеют удобочитаемый вид. Ниже приводится несколько рекомендаций, касающихся стиля спецификаций. Пишите имена лексем прописными буквами, а имена нетер- минальных символов - строчными. Так удобнее отлаживать yacc-спецификацию. Помещайте грамматические правила и действия на отдель- ных строках. Это облегчает чтение. Все правила с одинаковой левой частью помещайте вместе. Левую часть пишите только раз, а альтернативы разделяй- те вертикальной чертой. Точку с запятой ставьте на отдельной строке и только после последнего правила в группе правил с одинаковой левой частью. Это позволяет легко добавлять новые пра- вила. Используйте отступы для выделения действий и их тел. Сложные действия выделяйте в подпрограммы, определенные в других файлах. Основная проблема заключается в том, чтобы не утопить граммати- ческие правила в трясине действий. 8.2. Левая рекурсия Алгоритм разбора, используемый в утилите yacc, лучше подходит для так называемых леворекурсивных грамматических правил вида name : name rest_of_rule ; Правила, подобные list : item | list ',' item ; и seq : item | seq item ; часто возникают при спецификации списков и последовательностей. В каждом из этих случаев первое правило будет использовано только для свертки первого элемента, второе правило будет ис- пользоваться для свертки второго и всех последующих элементов. Для праворекурсивных правил, таких как seq : item | item seq ; алгоритм разбора немного сложнее; элементы выделяются и сверты- ваются справа налево. Более серьезно то, что есть опасность пе- реполнения внутреннего стека при чтении очень длинной последо- вательности. Поэтому рекомендуется использовать левую рекурсию. Стоит рассмотреть случай, когда имеет смысл последовательность из нуля элементов. Спецификация такой последовательности вклю- чает правило с пустым телом: seq : /* пусто */ | item seq ; И вновь первое правило будет использоваться для свертки только перед тем, как прочитан первый элемент, а второе - для свертки всех прочитанных элементов. Допущение пустых последовательнос- тей часто ведет к увеличению общности. Однако могут возникнуть конфликты, поскольку yacc вынужден решать, пустая последова- тельность чего прочитана, в то время как он еще недостаточно прочитал, чтобы узнать это. 8.3. Уловки анализа лексики Некоторые решения, принимаемые лексическим анализатором, зави- сят от контекста. Например, лексический анализатор может игно- рировать пробелы всюду, но не в текстах, взятых в кавычки, или имена могут включаться в таблицу в описаниях, но не в выражени- ях. Один из способов обработки таких ситуаций - использование глобального признака, устанавливаемого действиями и опрашивае- мого лексическим анализатором. Например, спецификация %{ int dflag; ... другие определения ... %% prog : decls stats ; decls : /* пусто */ { dflag = 1; } decls declaration ; stats : /* пусто */ { dflag = 0; } stats statement ; ... другие правила ... описывает программу, состоящую из нуля или большего числа опи- саний, за которыми следует нуль или более операторов. Признак dflag равен 0, когда читаются операторы, и 1, когда читаются описания, за исключением первой лексемы в первом операторе. Эта лексема требуется алгоритму разбора для того, чтобы выяснить, что описания закончились и начались операторы. Можно расценить такие попытки пройти с черного хода как вред- ные. Однако они позволяют сделать вещи, которые другими спосо- бами сделать было бы сложно, если не невозможно. 8.4. Зарезервированные слова Некоторые языки программирования позволяют использовать слова, обычно резервируемые (подобные if), в качестве меток или имен переменных, и гарантируют при этом, что такое использование не приведет к конфликту. При работе с yacc'ом сделать это чрезвы- чайно тяжело. Трудно передать лексическому анализатору информа- цию о том, что одно вхождение if является ключевым словом, а другое - именем переменной. Пользователь может применить меха- низм, описанный в предыдущем пункте, но сделать это непросто. Есть несколько предложений, как при развитии yacc'а облегчить решение данной проблемы. А пока лучше резервировать ключевы- слова, то есть запрещать их использование в качестве идентифи- каторов. В пользу этого есть и убедительные стилистические при- чины. 9. БОЛЕЕ СЛОЖНЫЕ ВОПРОСЫ В данном разделе обсуждается ряд усовершенствований yacc'а. 9.1. Моделирование действий ошибка и успех Действия разбора ошибка и успех можно моделировать при помощи макросов YYACCEPT и YYERROR. Макрос YYACCEPT заставляет yypar- se() завершиться, возвратив значение 0; макрос YYERROR застав- ляет процедуру разбора вести себя так, как если бы текущий входной символ был ошибочным; вызывается yyerror() и выполняет- ся нейтрализация ошибки. Эти механизмы можно использовать, что- бы моделировать алгоритмы разбора с многократными маркерами конца и контекстно-зависимым контролем синтаксиса. 9.2. Доступ к значениям завершенных правил Действие может ссылаться на значения, возвращенные в результате обработки предыдущих правил. Происходит это обычным образом - посредством знака $, за которым следует число. sent : adj noun verb adj noun { просмотр предложения ... } ; adj : THE { $$ = THE; } YOUNG { $$ = YOUNG; } . . . ; noun : DOG { $$ = DOG; } CRONE { if ($0 == YOUNG) { (void) printf ("что???\n"); } $$ = CRONE; } ; . . . В этом случае число должно быть нулевым или отрицательным. В действии, следующем за словом CRONE, выполняется проверка, что предыдущая лексема - не YOUNG. Очевидно, такая проверка возмож- на только в случае, когда о предыдущей лексеме есть информация. Иногда с помощью данного механизма, который, правда, к струк- турным не отнесешь, обходят многие проблемы, в особенности, когда требуется исключить из в основном регулярной структуры всего несколько комбинаций. 9.3. Использование значений произвольных типов По умолчанию предполагается, что значения, возвращаемые дейст- виями и лексическим анализатором - целые. yacc поддерживает значения и других типов, в том числе структуры. Кроме того, yacc отслеживает типы и вставляет соответствующие имена элемен- тов объединений, в результате чего получается строго типизиро- ванная процедура разбора. При описании стека значений yacc'у указывается объединение (union) всех ожидаемых типов значений. Пользователь задает это объединение и связывает имена элементов объединения с каждой лексемой и нетерминальным символом, у ко- торых может быть значение. Когда на значение ссылаются при по- мощи конструкций $$ или $n, yacc автоматически вставляет имя соответствующего элемента объединения, так что лишних преобра- зований не происходит, и, кроме того, утилиты проверки типов, такие как lint(1), ведут себя лояльнее. Чтобы обеспечить такие возможности типизации, используются три механизма. Во-первых, определение объединения. Оно должно быть сделано пользователем, так как другие подпрограммы, особенно лексический анализатор, должны знать имена элементов объедине- ния. Во-вторых, связывание имени элемента объединения с лексе- мами и нетерминалами. Наконец, имеется механизм для описания типа тех немногих значений, которые yacc не в состоянии типизи- ровать автоматически. Чтобы описать объединение, пользователь включает конструкцию %union { тело объединения } в секцию определений. Она означает, что элементы стека значений и внешние переменные yylval и yyval имеют тип, совпадающий с этим объединением. Если yacc вызывается с опцией -d, описание объединения копируется в файл y.tab.h в качестве YYSTYPE. После того, как тип YYSTYPE определен, надо сопоставить имена элементов объединения именам лексем и нетерминальных символов. Для указания имени элемента объединения используется конструк- ция <имя> Если эта конструкция следует за одним из ключевых слов %token, %right, %left или %nonassoc, то имя элемента объединения сопос- тавляется лексемам из последующего списка. Так, запись %left '+' '-' означает, что любое обращение к значениям, возвращаемым этими двумя лексемами, снабжается тегом - именем элемента объединения optype. Еще одно ключевое слово %type используется для сопос- тавления имени элемента объединения нетерминальному символу. Чтобы сопоставить элемент объединения nodetype нетерминальным символам expr и stat, можно записать %type expr stat Есть несколько случаев, в которых описанных механизмов недоста- точно. Если действие находится внутри правила, возвращаемое этим действием значение не имеет типа, заданного a priori. Ана- логично, yacc'у не хватает информации для определения типа при сылках на значения из левого контекста (таких как $0). В по- добных ситуациях тип может быть задан явно ссылкой на имя эле- мента объединения, которое заключается в угловые скобки < и > и вставляется за первым знаком $. Пример rule : aaa { $$ = 3; } bbb { fun ($2, $0); } ; иллюстрирует данную возможность. Синтаксис не назовешь "сахар- ным", но и требуется такая конструкция нечасто. Средства, описанные в данном разделе, проиллюстрированы в более сложном из приводимых ниже примеров. Отметим, что контроль ти- пов включается только при явном использовании типизации (напри- мер, если встречается конструкция %type) и контроль этот явля- ется весьма жестким. Так, считается ошибкой вхождение $n или $$ без указания определенного типа. Если же описанные здесь воз- можности не пускаются в ход, считается, что стек значений со- держит целые числа. 10. ВХОДНОЙ СИНТАКСИС YACC'А В данном разделе в форме yacc-спецификации описывается входной синтаксис yacc'а. Не рассматриваются контекстные зависимости и аналогичные вопросы. Ирония заключается в том, что, хотя yacc воспринимает LALR(1)-грамматики, сам входной язык спецификаций yacc'а наиболее естественным образом задается LR(2)-граммати- кой: трудным оказывается случай, когда идентификатор идет сразу за действием. Если после идентификатора стоит двоеточие, то это начало следующего правила, в противном случае, это продолжение текущего правила, которое идет за внутренним действием. Реали- зация такова: лексический анализатор, обнаружив идентификатор, просматривает входной текст вперед и определяет, является ли следующая лексема двоеточием. Если является, лексический анали- затор возвращает C_IDENTIFIER. Если нет, возвращается IDENTIFI- ER. Литералы (в апострофах) также распознаются как IDENTIFIER, но не как C_IDENTIFIER. /* грамматика yacc-спецификаций */ /* основные компоненты */ %token IDENTIFIER /* идентификаторы и литералы */ %token C_IDENTIFIER /* идентификатор (но не литерал), */ /* за которым следует двоеточие */ /* зарезервированные слова: %type=>TYPE %left=>LEFT и т.д.*/ %token LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION %token MARK /* знак %% */ %token LCURL /* знак %{ */ %token RCURL /* знак %} */ /* ASCII-символы указываются непосредственно */ %% spec : defs MARK rules tail ; tail : MARK { В этом действии обрабатывается оставшаяся часть файла } /* пусто: второй MARK необязателен */ ; defs : /* пусто */ defs def ; def : START IDENTIFIER UNION { Копирование определения объединения в выходной файл } LCURL { Копирование C-кода в выходной файл } RCURL rword tag nlist ; rword : TOKEN LEFT RIGHT NONASSOC TYPE ; tag : /* пусто: тег необязателен */ '<' IDENTIFIER '>' ; nlist : nmno nlist nmno nlist ',' nmno ; nmno : IDENTIFIER /* Замечание: литерал нельзя использовать с %type */ IDENTIFIER NUMBER /* Замечание: нельзя использовать с %type */ ; /* секция правил */ rules : C_IDENTIFIER rbody prec rules rule ; rule : C_IDENTIFIER rbody prec '|' rbody prec ; rbody : /* пусто */ | rbody IDENTIFIER | rbody act ; act : '{' { Копирование действия, обработка $$ и т.п. } '}' ; prec : /* пусто */ | PREC IDENTIFIER | PREC IDENTIFIER act | prec ';' ; 11. ПРИМЕРЫ 11.1. Простой пример Этот пример - полная yacc-спецификация, реализующая небольшой калькулятор; калькулятор имеет 26 регистров, помеченных буквами от a до z, и обрабатывает арифметические выражения, построенные при помощи операций +, -, *, /, % (остаток от деления), & (побитное и), | (побитное или) и присваиваний. Если на вход калькулятору дается присваивание, оно выполняется; в противном случае выводится значение выраже- ния. Как и в языке C, целая константа, если она начинается с 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 { (void) 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 '|' expr { $$ = $1 | $3; } '-' expr %prec UMINUS { $$ = - $2; } LETTER { $$ = regs[$1]; } number ; number : DIGIT { $$ = $1; base = ($1==0) ? 8 : 10; } number DIGIT { $$ = base * $1 + $2; } ; %% /* начало секции подпрограмм */ int 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); } 11.2. Более сложный пример В этом пункте рассматривается пример грамматики, в которой ис- пользуются некоторые специфические свойства yacc'а. Калькулятор из предыдущего пункта реконструируется, чтобы обеспечить дейст- вия над вещественными числами и над интервалами таких чисел. Калькулятор понимает вещественные константы, арифметические операции +, -, *, /, унарный -, переменные от a до z. Кроме то- го, он воспринимает интервалы вида (X, Y) где X не превосходит Y. Можно использовать 26 переменных типа интервал с именами от A до Z. Калькулятор работает аналогично тому, который был описан в пункте Простой пример; присваивания не возвращают значений и ничего не выводят, остальные выражения выводят результат (вещественный или интервальный). В данном примере используется ряд интересных особенностей yacc'а и языка C. Интервал представляется структурой, состоящей из левой и правой границ, значения которых имеют тип double. При помощи конструкции typedef этому структурному типу дается имя INTERVAL. В стек значений yacc'а могут быть занесены также значения целого и вещественного типов (целые числа используются В качестве индекса в массиве, содержащем значения переменных). Отметим, что организация вычислений в целом сильно зависит от возможности присваивать структуры и объединения в языке C. Мно- гие действия вызывают функции, возвращающие значения структур- ного типа. Стоит отметить использование макроса YYERROR для обработки оши- бочных ситуаций, когда делается попытка деления на интервал, содержащий 0, или употребляется интервал, левая граница которо- го больше правой. Механизм нейтрализации ошибок используется для того, чтобы отбросить остаток некорректной строки. Кроме смешивания типов в стеке значений данная грамматика де- монстрирует любопытный способ отслеживания типа (скалярного или интервального) промежуточных выражений. Отметим, что скаляр мо- жет быть автоматически преобразован в интервал, если контекст требует значения интервального типа. Это приводит к большому числу конфликтов, которые обнаруживает в грамматике yacc: 18 конфликтов свертка-перенос и 26 свертка-свертка. Проблему можно рассмотреть на примере двух входных строк 2.5 + (3.5 - 4.) и 2.5 + (3.5, 4.) Во втором примере константа 2.5 должна использоваться в интер- вальнозначном выражении, однако данный факт не известен до тех пор, пока не прочитана запятая. К этому времени константа 2.5 обработана и алгоритм разбора не может уже передумать и вер- нуться назад. В более общем случае может оказаться необходимым просмотреть вперед неограниченное число лексем, чтобы сообра- зить, преобразовывать ли скаляр в интервал. Эту проблему обхо- дят, вводя два правила для каждой бинарной интервальнозначной операции: одну на случай, когда левый операнд является скаля- ром, другую - когда левый операнд является интервалом. Во вто- ром случае правый операнд должен быть интервалом, поэтому пре- образование будет выполняться автоматически. Несмотря на эту увертку, остается еще много случаев, в которых преобразование может либо выполняться либо нет, что приводит к конфликтам. Чтобы их разрешить, в начало файла спецификаций помещен список правил, задающих скаляры; такой способ разрешения конфликтов ведет к тому, что скалярные выражения остаются скалярными до тех пор, пока их не заставят стать интервальными. Демонстрируемый способ обработки множественных типов весьма по- учителен и ... непрактичен. Если имеется много типов выражений, а не два, как в данном примере, число правил возрастает лавино- образно, а число конфликтов - еще быстрее. Поэтому в более при- вычных языках программирования лучше считать информацию о типе частью значения, а не частью грамматики. В заключение - несколько слов о лексическом анализе веществен- ных констант. Чтобы преобразовать текст в число двойной точнос- ти, используется процедура atof() из стандартной C-библиотеки. Если лексический анализатор обнаруживает ошибку, он возвращает лексему, которая не допускается грамматикой, провоцируя тем са- мым синтаксическую ошибку и, как следствие, ее нейтрализацию. %{ #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; } %token DREG VREG /* индексы в массивах dreg, vreg */ %token CONST /* константа с плавающей точкой */ %type dexp /* выражение */ %type vexp /* интервальное выражение */ /* информация о приоритетах операций */ %left '+' '-' %left '*' '/' %left UMINUS /* наивысший приоритет у унарного минуса */ %% /* начало секции правил */ lines : /* пусто */ | 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 ("нижняя граница больше верхней\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.hi; $$.lo = $1.lo - $3.lo; } dexp '-' vexp { $$.hi = $1 - $3.hi; $$.lo = $1 - $3.lo; } 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 /* размер буфера для числа с плав. точкой */ /* лексический анализ */ int yylex () { register int c; /* пропустить пробелы */ while ((c = getchar ()) == ' ') ; 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; ++cp, c = getchar ()) { *cp = c; if (isdigit (c)) continue; if (c == '.') { if (dot++ || exp) return ('.'); /* приводит к синт. ошибке */ continue; } if (c == 'e') { if (exp++) return ('e'); /* приводит к синт. ошибке */ continue; } /* конец числа */ break; } *cp = ' '; if (cp - buf >= BSZ) (void) 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 (d < v.lo) v.lo = d; } else { if (d > v.hi) v.hi = d; if (c < v.lo) v.lo = c; } return (v); } INTERVAL vmul (a, b, v) double a, b; INTERVAL v; { return (hilo (a*v.hi, a*v.lo, b*v.hi, b*v.lo)); } dcheck (v) INTERVAL v; { if (v.hi >= 0. && v.lo <= 0.) { (void) 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)); }