Серебряков В.А. Лекции по конструированию компиляторов
Подождите немного. Документ загружается.
В основу системы Yacc положен синтаксический анализатор типа
LALR(1), генерируемый по входной (мета) программе. Эта
программа состоит из трех частей:
%{
Си-текст
%}
%token Список имен лексем
%%
Список правил трансляции
%%
Служебные Си-подпрограммы
Си-текст (который вместе с окружающими скобками %{ и %} может
отсутствовать) обычно содержит Си-объявления (включая #include
и #define), используемые в тексте ниже. Этот Си-текст может
содержать и объявления (или предобъявления) функций.
Список имен лексем содержит имена, которые преобразуются
Yacc-препроцессором в объявления констант (#define). Как
правило, эти имена используются как имена классов лексем и
служат для определения интерфейса с лексическим анализатором.
Каждое правило трансляции имеет вид
Левая-часть : альтернатива_1 {семантические действия 1}
| альтернатива_2 {семантические действия 2}
|...
| альтернатива_n {семантические действия n}
;
Каждое семантическое действие - это последовательность
операторов Си. При этом каждому нетерминалу может быть
сопоставлен один синтезируемый атрибут. На атрибут нетерминала
левой части ссылка осуществляется посредством значка $$, на
атрибуты символов правой части - посредством значков $1, $2
,..., причем номер соответствует порядку элементов правой
части, включая семантические действия. Каждое семантическое
действие может вырабатывать значение в результате выполнения
присваивания $$=Выражение. Исполнение текого оператора в
последнем семантическом действии определяет значение атрибута
символа левой части.
В некоторых случаях допускается использование грамматик,
имеющих конфликты. При этом синтаксический анализатор
разрешает конфликты следующим образом:
- конфликты типа свертка/свертка разрешаются выбором
правила, предшествующего во входной метапрограмме;
- конфликты типа сдвиг/свертка разрешаются предпочтением
сдвига. Поскольку этих правил не всегда достаточно для
правильного определения анализатора, допускается определение
старшинства и ассоциативности терминалов.
Например, объявление
%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.