Начальная страница

Bison 1.35 - 8. Обработка контекстных зависимостей

[Содержание]   [Назад]   [Пред]   [Вверх]   [След]   [Вперед]  

8. Обработка контекстных зависимостей

Основной принцип Bison в том, чтобы сначала разбираются лексемы, а затем они группируются в более крупные синтаксические единицы. Во многих языках значение лексемы зависит от её контекста. Хотя это и нарушает принципы Bison, существуют определённые приёмы (известные как кладжи), которые дают вам возможность писать анализаторы Bison для таких языков.

(На самом деле, "кладж" -- это всякий приём, который решает поставленную задачу, но не является ни чистым, ни надёжным.)

8.1 Семантическая информация в типах лексем

Язык C содержит контекстную зависимость -- способ использования идентификаторов зависит от его текущего смысла. Например, рассмотрим: 

foo (x);

Это выглядит как оператор вызова функции, но если foo -- имя определения типа, то на самом деле это объявление x. Как анализатор Bison для C может решить, как разбирать такой входной текст?

В GNU C используется метод, состоящий в том, чтобы иметь два разных типа лексем: IDENTIFIER и TYPENAME. Когда yylex обнаруживает идентификатор, она ищёт текущее объявление идентификтора чтобы решить, какой тип лексемы возвращать: TYPENAME, если идентификатор объявлен как определение типа, и IDENTIFIER в противном случае.

Правила грамматики могут затем выражать контекстную зависимость выбором типа лексемы при распознавании. IDENTIFIER допустима в выражении, а TYPENAME -- нет. Объявление может начинаться с TYPENAME, но не с IDENTIFIER. В контекстах, где смысл идентификатора не имеет значения, таких как в объявлениях, которые могут затенять имя определения типа, принимаются как TYPENAME, так и IDENTIFIER -- для каждого из двух типов лексем есть своё правило.

Этот приём просто использовать, если решение, какой тип идентификаторов допустим, принимается в месте, близком к тому, где разбирается этот идентификатор. Но в C это не всегда так: C допускает, чтобы объявление переопределяло имя определения типа, при условии, что явный тип был задан ранее: 

typedef int foo, bar, lose;
static foo (bar);        /* переопределить bar
                               как статическую переменную */
static int foo (lose);   /* переопределить foo
                               как функцию */

К сожалению, объявляемое имя отделено от самой объявляющей конструкции сложной синтаксической структурой -- "объявлятелем".

В результате часть анализатора Bison для C должна быть продублирована с изменением имён всех нетерминалов: одно для разбора объявления, в котором имя определения типа может быть переопределено, и другое для разбора объявлений, в которых это невозможно. Приведём часть такого дублирования, действия в котором опущены для краткости: 

initdcl:
          declarator maybeasm '='
          init
        | declarator maybeasm
        ;

notype_initdcl:
          notype_declarator maybeasm '='
          init
        | notype_declarator maybeasm
        ;

Здесь initdcl может переопределить имя определения типа, а notype_initdcl -- нет. Та же разница между declarator и notype_declarator.

Есть нечто общее между этим приёмом и лексической увязкой (описанной ниже), в том, что информация, изменяющая ход лексического анализа, изменяется во время разбора другим частями программы. Различие в том, что здесь эта информация глобальна, и используется в программе для других целей. Истинная лексическая увязка имеет флаг специального назначения, управляемый синтаксическим контекстом.

8.2 Лексическая увязка

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

Например, предположим, что у нас есть язык, смутно похожий на C, но со специальной конструкцией `hex (шестнадцатеричное_выражение)'. После ключевого слова hex идёт выражение в скобках, в котором все целые числа записаны в шестнадцатеричной системе счисления. В частности, при появлении в этом контекта лексема `a1b' должна рассматриваться как целое, а не как идентификатор. Вот как вы можете это сделать: 

%{
int hexflag;
%}
%%
...
expr:   IDENTIFIER
        | constant
        | HEX '('
                { hexflag = 1; }
          expr ')'
                { hexflag = 0;
                   $$ = $4; }
        | expr '+' expr
                { $$ = make_sum ($1, $3); }
        ...
        ;

constant:
          INTEGER
        | STRING
        ;

Здесь мы полагаем, что yylex проверяет значение hexflag, когда оно ненулевое, все числа рассматриваются как шестнадцатеричные, и лексемы, начинающиеся в букв, разбираются как целые, если это возможно.

Объявление hexflag, показанное в секции объявлений C файла анализатора, необходимо чтобы оно было доступно для действий (см. раздел 4.1.1 Секция объявлений C). Вы также должны написать код yylex так, чтобы анализ подчинялся этому флагу.

8.3 Лексическая увязка и восстановление после ошибок

Лексическая увязка предъявляет строгие требования ко всем имеющимся у вас правилам восстановления после ошибок. См. раздел 7. Восстановление после ошибок.

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

stmt:   expr ';'
        | IF '(' expr ')' stmt { ... }
        ...
        error ';'
                { hexflag = 0; }
        ;

Если внутри конструкции `hex (выражение)' есть синтаксическая ошибка, будет применено это правило обработки ошибок, и тогда действия для законченного `hex (выражение)' никогда не будут выполнены. Поэтому hexflag останется установленным для всего остального входного текста или до следующего ключевого слова hex, в результате чего идентификаторы будут ошибочно интерпретироваться как целые числа.

Чтобы избежать этой проблемы, правило восстановления после ошибки само сбрасывает hexflag.

Также могут существовать правила восстановления после ошибок, работающие внутри выражений. Например, может быть правило, применяющееся внутри скобок и пропускающее всё до закрывающей скобки: 

expr:   ...
        | '(' expr ')'
                { $$ = $2; }
        | '(' error ')'
        ...

Если это правило действует внутри конструкции hex, оно не приводит к выходу из этой конструкии (поскольку оно применяется к самому внутреннем уровню скобок внутри конструкции). Поэтому не нужно очищать флаг, оставшаяся часть конструкции hex должна быть разобрана пока флаг всё ещё действует.

Что если существует правило восстановления после ошибок, которое может прервать или не прерывать разбор конструкции hex, в зависимости от обстоятельств? Способа написать правило, определяющее, был ли прерван разбор конструкции hex, нет. Поэтому, если вы используете лексиечскую увязку, лучше быть уверенным в том, что ваши правила восстановления после ошибок не таковы. Каждое правило должно быть таким, что вы можете быть уверены в том, что оно всегда будет или никогда не будет сбрасывать флаг.

[Содержание]   [Назад]   [Пред]   [Вверх]   [След]   [Вперед]