В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 31

При этом синтаксический анализатор разрешает конфликты следующим образом:– конфликты типа свертка/свертка разрешаются выбором правила,предшествующего во входной метапрограмме;– конфликты типа сдвиг/свертка разрешаются предпочтением сдвига. Поскольку этих правил не всегда достаточно для правильного определения анализатора, допускается определение старшинства и ассоциативности терминалов.Например, объявление%left ’+’ ’-’определяет + и −, имеющими одинаковый приоритет и имеющими левую ассоциативность.

Операцию можно определить как правоассоциативную в результате объявления:%right ’^’Бинарную операцию можно определить как неассоциативную (т.е.не допускающую появления объединения двух подряд идущих знаковоперации):%nonassoc ’<’Символы, перечисленные в одном объявлении, имеют одинаковое старшинство. Старшинство выше для каждого последующего объявления.Конфликты разрешаются путем присваивания старшинства и ассоциативности каждому правилу грамматики и каждому терминалу, участвующим в конфликте.

Если необходимо выбрать между сдвигом входного символа s и сверткой по правилу A → w, свертка делается, если старшинство правила больше старшинства s или если старшинство одинаково, а правило левоассоциативно. В противном случае делается сдвиг.10.2. СИСТЕМА YACC189Обычно за старшинство правила принимается старшинство самогоправого терминала правила. В тех случаях, когда самый правый терминал не дает нужного приоритета, этот приоритет можно назначить следующим объявлением:%prec терминалСтаршинство и ассоциативность правила в этом случае будут такимиже, как у указанного терминала.Yacc не сообщает о конфликтах, разрешаемых с помощью ассоциативности и приоритетов.

Восстановление после ошибок управляетсяпользователем с помощью введения в грамматику “правил ошибки” видаA → error w.Здесь error – ключевое слово Yacc. Когда встречается синтаксическаяошибка, анализатор трактует состояние, набор ситуаций для которогосодержит правило для error, некоторым специальным образом: символыиз стека выталкиваются до тех пор, пока на верхушке стека не будет обнаружено состояние, для которого набор ситуаций содержит ситуациювида [A → .error w]. После чего в стек фиктивно помещается символ error,как если бы он встретился во входной строке.Если w пусто, делается свертка.

После этого анализатор пропускаетвходные символы, пока не найдет такой, с которым можно продолжитьнормальный разбор.Если w не пусто, просматривается входная строка и делается попытка свернуть w. Если w состоит только из терминалов, эта строка ищетсяво входном потоке.190ГЛАВА 10. СИСТЕМЫ АВТОМАТИЗАЦИИ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВЛитература[1] Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации.

ДАН СССР. 1962. Т.146. N 2. С. 263-266.[2] Ахо А., Ульман Д. Теория синтаксического анализа, перевода икомпиляции, в 2-х т. М.: Мир, 1978.[3] Бездушный А.Н., Лютый В.Г., Серебряков В.А. Разработка компиляторов в системе СУПЕР. М.: ВЦ АН СССР, 1991.[4] Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.[5] Кнут Д.

Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976.[6] Кнут Д. Семантика контекстно-свободных языков. В сб.: Семантика языков программирования. М.: Мир, 1980.[7] Курочкин В.М. Алгоритм распределения регистров для выражений за один обход дерева вывода. 2 Всес.

конф “Автоматизация производства ППП и трансляторов”. 1983. С. 104-105.[8] Лавров С.С., Гончарова Л.И. Автоматическая обработка данных.Хранение информации в памяти ЭВМ. М.: Наука, 1971.[9] Надежин Д.Ю., Серебряков В.А., Ходукин В.М. Промежуточныйязык Лидер (предварительное сообщение). Обработка символьнойинформации. М.: ВЦ АН СССР, 1987. С. 50-63.[10] Aho A., Sethi R., Ullman J. Compilers: principles, techniques andtools.

N.Y.: Addison-Wesley, 1986.[11] Aho A.U., Ganapathi M., Tjiang S.W. Code generation using treematching and dynamic programing. ACM Trans. Program. Languagesand Systems. 1989. V.11.N 4.[12] Bezdushny A., Serebriakov V. The use of the parsing method foroptimal code generation and common subexpression elimination.Techn. et Sci. Inform. 1993. V.12. N.1.

P.69-92.191192ЛИТЕРАТУРА[13] Emmelman H., Schroer F.W., Landweher R. BEG – a generator forefficient back-ends. ACM SIGPLAN. 1989. V.11. N 4.p.227-237[14] Fraser C.W., Hanson D.R. A Retargetable compiler for ANSI C.SIGPLAN Notices. 1991. V 26.[15] Graham S.L., Harrison M.A., Ruzzo W.L. An improved context-freerecognizer. ACM Trans.

Program. Languages and Systems. 1980. N.2.[16] Harrison M.A. Introduction to formal language theory. Reading,Mass.: Addison-Wesley, 1978..