В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 39
Текст из файла (страница 39)
Определение класса лексем состоит в задании имени класса, именатрибутов для этого класса и типов этих атрибутов.216Глава 10. Системы автоматизации построения трансляторовОпределение нетерминальных символов содержит перечисление этих символов с указанием приписанных им атрибутов и их типов. Аксиома грамматики указывается первым символом в списке нетерминалов.Раздел библиотеки содержит заголовки процедур и функций, используемых в формулах атрибутной грамматики.Раздел файлов содержит описание файловых переменных, используемыхв формулах атрибутной грамматики. Файловые переменные можно рассматривать как атрибуты аксиомы.Атрибутная схема состоит из списка синтаксических правил и сопоставленных им семантических правил. Для описания синтаксиса языка используется расширенная форма Бэкуса–Наура.
Терминальные символы в правойчасти заключаются в кавычки, классы лексем и нетерминалы задаются ихименами. Для задания необязательных символов в правой части используются скобки [ ], для задания повторяющихся конструкций используются скобки ( ). В этом случае может быть указан разделитель символов (после /).Например,A ::= B [ C ] ( D ) ( E / ’,’ )Первым правилом в атрибутной схеме должно быть правило для аксиомы.Каждому синтаксическому правилу могут быть сопоставлены семантические действия.
Каждое такое действие — это оператор, который можетиспользовать атрибуты как символов данного правила (локальные атрибуты),так и символов, могущих быть (динамически) предками символа левой части данного правила в дереве разбора (глобальные атрибуты). Для ссылкина локальные атрибуты символы данного правила (как терминальные, таки нетерминальные) нумеруются от 0 (для символа левой части). При ссылкена глобальные атрибуты надо иметь в виду, что атрибуты имеют областивидимости на дереве разбора.
Областью видимости атрибута вершины, помеченной N, является все поддерево N, за исключением его поддеревьев, такжепомеченных N.Исполнение операторов семантической части правила привязывается к обходу дерева разбора сверху-вниз слева-направо. Для этого каждый операторможет быть снабжен меткой, состоящей из номера ветви правила, к выполнению которой должен быть привязан оператор, и, возможно, одного изсуффиксов A, B, E, M.Суффикс A задает выполнение оператора перед каждым вхождениемсинтаксической конструкции, заключенной в скобки повторений ( ). Суффикс B задает выполнение оператора после каждого вхождения синтаксической конструкции, заключенной в скобки повторений ( ).
Суффикс Mзадает выполнение оператора между вхождениями синтаксической конструкции, заключенной в скобки повторений ( ). Суффикс E задает выполнение10.2. Система YACC217оператора в том случае, когда конструкция, заключенная в скобки [ ],отсутствует.Пример использования меток атрибутных формул:D ::= ’d’ =>$0.y:=$0.x+1.A ::= B (C) [D] =>$2.x:=1;2M: $2.x:=$2.x+1;$3.x:=$2.x;3E: $3.y:=$3.x;3: writeln($3.y).Процедура writeln напечатает число вхождений символа C в C-список,если D опущено. В противном случае напечатанное число будет на единицубольше.10.2.
Система YACCВ основу системы YACC положен синтаксический анализатор типаLALR(1), генерируемый по входной (мета)программе. Эта программа состоитиз трех частей:%{Си-текст%}%token Список имен лексем%%Список правил трансляции%%Служебные Си-подпрограммыСи-текст (который вместе с окружающими скобками %{ и %} может отсутствовать) обычно содержит Си-объявления (включая #include и #define),используемые в тексте ниже. Этот Си-текст может содержать и объявления(или предобъявления) функций.Список имен лексем содержит имена, которые преобразуются YACCпрепроцессором в объявления констант (#define).
Как правило, эти именаиспользуются как имена классов лексем и служат для определения интерфейса с лексическим анализатором.Каждое правило трансляции имеет видЛевая_часть : альтернатива_1{семантические_действия_1}| альтернатива_2 {семантические_действия_2}|...| альтернатива_n {семантические_действия_n};218Глава 10. Системы автоматизации построения трансляторовКаждое семантическое действие — это последовательность операторов Си.При этом каждому нетерминалу может быть сопоставлен один синтезируемый атрибут.
На атрибут нетерминала левой части ссылка осуществляетсяпосредством значка $$, на атрибуты символов правой части — посредствомзначков $1, $2 , . . ., $n, причем номер соответствует порядку элементовправой части, включая семантические действия. Каждое семантическое действие может вырабатывать значение в результате выполнения присваивания$$=Выражение. Исполнение такого оператора в последнем семантическомдействии определяет значение атрибута символа левой части.В некоторых случаях допускается использование грамматик, имеющихконфликты. При этом синтаксический анализатор разрешает конфликты следующим образом:– конфликты типа свертка/свертка разрешаются выбором правила, предшествующего во входной метапрограмме;– конфликты типа сдвиг/свертка разрешаются предпочтением сдвига.Поскольку этих правил не всегда достаточно для правильного определенияанализатора, допускается определение старшинства и ассоциативности терминалов.Например, объявление%left ’+’ ’-’определяет + и − имеющими одинаковый приоритет и левую ассоциативность.
Операцию можно определить как правоассоциативную в результатеобъявления:%right ’^’Бинарную операцию можно определить как неассоциативную (т. е. не допускающую объединения двух подряд идущих знаков операции):%nonassoc ’<’Символы, перечисленные в одном объявлении, имеют одинаковое старшинство. Старшинство выше для каждого последующего объявления. Конфликты разрешаются путем присваивания старшинства и ассоциативностикаждому правилу грамматики и каждому терминалу, участвующим в конфликте. Если необходимо выбрать между сдвигом входного символа s и сверткой по правилу A → w, то свертка делается, если старшинство правилабольше старшинства s или если старшинства одинаковы, а правило левоассоциативно.
В противном случае делается сдвиг.Обычно за старшинство правила принимается старшинство самого правоготерминала правила. В тех случаях, когда самый правый терминал не даетнужного приоритета, этот приоритет можно назначить следующим объявлением:%prec терминал10.2.
Система YACC219Старшинство и ассоциативность правила в этом случае будут такими же, каку указанного терминала.YACC не сообщает о конфликтах, разрешаемых с помощью ассоциативности и приоритетов. Восстановление после ошибок управляется пользователемс помощью введения в грамматику «правил ошибки» видаA → error w.Здесь error — ключевое слово YACC. Когда встречается синтаксическаяошибка, анализатор трактует состояние, набор ситуаций которого содержитправило для error, некоторым специальным образом: символы из магазинавыталкиваются до тех пор, пока на его верхушке не будет обнаружено состояние, для которого набор ситуаций содержит ситуацию вида [A → .error w],после чего в магазин фиктивно помещается символ error, как если бы онвстретился во входной строке.Если w пусто, то делается свертка. После этого анализатор пропускаетвходные символы, пока не найдет такой, с которым можно продолжить нормальный разбор.Если w не пусто, просматривается входная строка и делается попыткасвернуть w.
Если w состоит только из терминалов, то эта строка ищетсяво входном потоке..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
