Теория и реализация языков программирования



             

Система YACC


В основу системы YACC положен синтаксический анализатор типа LALR(1), генерируемый по входной (мета) программе. Эта программа состоит из трех частей:

%{ Си-текст %} %token Список имен лексем %% Список правил трансляции %% Служебные Си-подпрограммы

Си-текст (который вместе с окружающими скобками %{ и %} может отсутствовать) обычно содержит Си-объявления (включая #include и #define), используемые в тексте ниже. Этот Си-текст может содержать и объявления (или предобъявления) функций.

Список имен лексем содержит имена, которые преобразуются YACC-препроцессором в объявления констант (#define). Как правило, эти имена используются как имена классов лексем и служат для определения интерфейса с лексическим анализатором.

Каждое правило трансляции имеет вид

Левая"часть : альтернатива"1 {семантические"действия"1} | альтернатива"2 {семантические"действия"2} |... | альтернатива"n {семантические"действия"n} ;

Каждое семантическое действие - это последовательность операторов Си. При этом каждому нетерминалу может быть сопоставлен один синтезируемый атрибут. На атрибут нетерминала левой части ссылка осуществляется посредством значка $$, на атрибуты символов правой части - посредством значков $1, $2 , . . . , $n, причем номер соответствует порядку элементов правой части, включая семантические действия. Каждое семантическое действие может вырабатывать значение в результате выполнения присваивания $$=Выражение. Исполнение текого оператора в последнем семантическом действии определяет значение атрибута символа левой части.

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

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




Содержание  Назад  Вперед