КаталогИндекс раздела
НазадОглавлениеВперед


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'а.

 

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). Шаг работы алгоритма состоит в следующем:

Действие перенос - наиболее частое действие алгоритма. В выполнении действия перенос всегда участвует предварительно просмотренная лексема. Например, для состояния 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 всегда сообщает число конфликтов перенос-свертка и свертка-свертка, разрешенных при помощи метода 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, и прочитана определенная входная цепочка,

       IF ( C1 ) IF ( C2 ) S1

Вообще говоря, может быть много конфликтов, и каждому соответствует входной символ и прочитанная перед ним входная цепочка. Прочитанная входная цепочка задает состояние алгоритма разбора.

Сообщения 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
            | 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, можно (но не обязательно) описать и при помощи %token.

Приоритеты и ассоциативность yacc использует для того, чтобы разрешить конфликты разбора. Они задают следующие методы разрешения неоднозначностей:

Конфликты, разрешенные при помощи приведенного метода, не учитываются при подсчете сообщаемого 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 <stdio.h>
       
       yyerror (s)
       char *s;
       {
         (void) fprintf (stderr, "%s\n", s);
       }

демонстрирует банальность этих предопределенных программ. Аргумент у функции yyerror() - текст, содержащий сообщение об ошибке, обычно syntax error. В реальных приложениях чаще выполняются более сложные действия. Обычно программа подсчитывает номер входной строки и печатает его вместе с сообщением об обнаружении синтаксической ошибки. Внешняя переменная целого типа yychar содержит номер предварительно просмотренной лексемы на момент обнаружения ошибки. Это может представлять некоторый интерес для формирования лучшей диагностики. Так как функция main() вероятнее всего задается пользователем (необходимо прочесть аргументы и т.п.), yacc-библиотека полезна только в маленьких проектах или на ранних этапах разработки больших.

Внешняя переменная целого типа yydebug обычно устанавливается равной 0. Если она имеет ненулевое значение, процедура разбора будет выдавать подробное описание действий, включающее сообщение о прочитанных входных символах и выполняемых операциях раз- бора. Значение этой переменной можно переустановить, используя отладчик sdb(1).

 

8. СОВЕТЫ ПО ПОДГОТОВКЕ СПЕЦИФИКАЦИЙ

Этот раздел содержит разнообразные рекомендации по подготовке эффективных, легко изменяемых и понятных спецификаций.

8.1. Стиль

Трудно написать правила, которые выполняют серьезные действия и к тому же имеют удобочитаемый вид. Ниже приводится несколько рекомендаций, касающихся стиля спецификаций.

Основная проблема заключается в том, чтобы не утопить грамматические правила в трясине действий.

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 заставляет yyparse() завершиться, возвратив значение 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> '+' '-'

означает, что любое обращение к значениям, возвращаемым этими двумя лексемами, снабжается тегом - именем элемента объединения optype. Еще одно ключевое слово %type используется для сопоставления имени элемента объединения нетерминальному символу. Чтобы сопоставить элемент объединения nodetype нетерминальным символам expr и stat, можно записать

       %type <nodetype> expr stat

Есть несколько случаев, в которых описанных механизмов недостаточно. Если действие находится внутри правила, возвращаемое этим действием значение не имеет типа, заданного a priori. Аналогично, yacc'у не хватает информации для определения типа при ссылках на значения из левого контекста (таких как $0). В подобных ситуациях тип может быть задан явно ссылкой на имя элемента объединения, которое заключается в угловые скобки < и > и вставляется за первым знаком $. Пример

       rule : aaa
              {
                $<intval>$ = 3;
              }
              bbb
              {
                fun ($<intval>2, $<other>0);
              }
       ;

иллюстрирует данную возможность. Синтаксис не назовешь "сахарным", но и требуется такая конструкция нечасто.

Средства, описанные в данном разделе, проиллюстрированы в более сложном из приводимых ниже примеров. Отметим, что контроль типов включается только при явном использовании типизации (например, если встречается конструкция %type) и контроль этот является весьма жестким. Так, считается ошибкой вхождение $n или $$ без указания определенного типа. Если же описанные здесь возможности не пускаются в ход, считается, что стек значений содержит целые числа.

 

10. ВХОДНОЙ СИНТАКСИС YACC'А

В данном разделе в форме yacc-спецификации описывается входной синтаксис yacc'а. Не рассматриваются контекстные зависимости и аналогичные вопросы. Ирония заключается в том, что, хотя yacc воспринимает LALR(1)-грамматики, сам входной язык спецификаций 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-символы указываются непосредственно */

       %%
       
       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 <stdio.h>
       #include <ctype.h>
       
       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 %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 <stdio.h>
       #include <ctype.h>
       
       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 <ival> DREG VREG /* индексы в массивах dreg, vreg */
       
       %token <dval> CONST     /* константа с плавающей точкой */
       
       %type <dval> dexp       /* выражение */
       
       %type <vval> 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));
       }


НазадОглавлениеВперед
КаталогИндекс раздела