CONSCOMP (Материалы к контрольным работам), страница 43

- конфликты типа сдвиг/свертка разрешаются предпочтением

сдвига. Поскольку этих правил не всегда достаточно для

правильного определения анализатора, допускается определение

старшинства и ассоциативности терминалов.

Например, объявление

%left '+' '-'

определяет + и -, имеющими одинаковый приоритет и имеющими

левую ассоциативность. Операцию можно определить как

правоассоциативную в результате объявления

%right '^'

Бинарную операцию можно определить как неассоциативную (т.е.

не допускающую появления объединения двух подряд идущих знаков

операции):

%nonassoc '<'

Символы, перечисленные в одном объявлении, имеют одинаковое

старшинство. Старшинство выше для каждого последующего

объявления.

Конфликты разрешаются путем присваивания старшинства и

ассоциативности каждому правилу грамматики и каждому

терминалу, участвующим в конфликте. Если необходимо выбрать

между сдвигом входного символа s и сверткой по правилу a->w,

свертка делается, если старшинство правила больше старшинства

s или если старшинство одинаково, а правило левоассоциативно.

В противном случае делается сдвиг.

Обычно за старшинство правила принимается старшинство самого

правого терминала правила. В тех случаях, когда самый правый

терминал не дает нужного приоритета, этот приоритет можно

назначить следующим объявлением:

%prec терминал

Старшинство и ассоциативность правила в этом случае будут

такими же, как у указанного терминала.

yacc не сообщает о конфликтах, разрешаемых с помощью

ассоциативности и приоритетов.

Восстановление после ошибок управляется пользователем с

помощью введения в грамматику "правил ошибки" вида a->error w.

Здесь error - ключевое слово yacc. Когда встречается

синтаксическая ошибка, анализатор трактует состояние, набор

ситуаций для которого содержит правило для error, некоторым

специальным образом: символы из стека выталкиваются до тех

пор, пока на верхушке стека не будет обнаружено состояние, для

которого набор ситуаций содержит ситуацию вида [a-> . error

w]. После чего в стек фиктивно помещается символ error, как

если бы он встретился во входной строке.

Если w пусто, делается свертка. После этого анализатор

пропускает входные символы, пока не найдет такой, с которым

можно продолжить нормальный разбор.

Если w не пусто, просматривается входная строка и делается

попытка свернуть w. Если w состоит только из терминалов, эта

строка ищется во входном потоке.

Литература

1. aho a., sethi r., ullman j. compilers: principles,

techniques and tools. n.y.: addison-wesley, 1986.

2. Грис Д. Построения компиляторов для цифровых

вычислительных машин. М.: Мир, 1975.

3. fraser c.w., hanson d.r. a retargetable compiler for

ansi c.// sigplan notices. 1991. v 26.

4. Надежин Д.Ю., В.А.Серебряков, В.М.Ходукин.

Промежуточный язык Лидер (предварительное

сообщение)//Обработка символьной информации.М.: ВЦ АН

СССР, 1987. С. 50-63.

5. Ахо А., Ульман Д. Теория синтаксического анализа,

перевода и компиляции. М.: Мир, 1978.

6. Кнут Д. Искусство программирования для ЭВМ. Т. 1.

Основные алгоритмы. М.: Мир, 1976.

7. Лавров С.С., Гончарова Л.И. Автоматическая обработка

данных. Хранение информации в памяти ЭВМ. М.: Наука,

1971.

8. Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм

организации информации// ДАН СССР. 1962. Т. 146. n 2. С.

263-266.

9. Курочкин В.М. Алгоритм распределения регистров для

выражений за один обход дерева вывода//2 Всес. конф

"Автоматизация производства ППП и трансляторов". 1983. С.

104-105.

10. emmelman h.,schroer f.w.,landweher r. beg-a

generator for efficient back-ends// acm sigplan. 1989.

v.11. n 4.p.227-237

11. aho a.u.,ganapathi m.,tjiang s.w. code generation

using tree matching and dynamic programing// acm trans.

program. languages and systems.1989. v.11.n 4.

12. a. bezdushny, v. serebriakov. the use of the parsing

method for optimal code generation and common

subexpression elimination//techn. et sci. inform. 1993.

v.12. n.1. p.69-92.

13. graham s.l., harrison m.a., ruzzo w.l. am improved

context-free recognizer// acm trans. program. languages

and systems. 1980. n.2.

14. harrison m.a. introduction to formal language

theory. reading, mass.: addison-wesley, 1978.