Начало
Учебные материалы
Разработка компиляторов и интерпретаторов
Способы описания синтаксиса Генератор синтаксических анализаторов BISON Принципы работы BISON, интеграция BISON и FLEX, обработка синтаксических ошибок Создание и обработка деревьев разбора Генератор трансляторов CAIO, пример интерпретатора Пример компилятора Сравнение инструментов для разработки трансляторов Индивидуальное задание LLVM
Создание и обработка деревьев разбора
На следующем этапе трансляции необходимо обработать дерево разбора. Но сначала на этапе синтаксического анализа необходимо создать это дерево в форме, удобной для последующей обработки. Такая форма называется абстрактное синтаксическое дерево (AST) и отличается от дерева разбора тем, что в нем отсутствуют элементы, которые не влияют на семантику программы (разделители, группирующие скобки).
Программа CAIO (входит в состав MinIDE) позволяет сгенерировать по описанию структуры дерева все необходимые классы и функции для создания AST. Обычно узлы AST обычно делятся на типы, так как разные виды узлов могут появляться только в определенных частях дерева.
Рассмотрим как выглядит описание для бинарного числового дерева:
%option ast %type <Tree> node(int,Tree,Tree) empty() %%
В дереве могут быть два типа узлов: node и empty. Узел node содержит целое число и ссылки на два поддерева. По этому описанию будет сгенерирована иерархия из трех классов и две функции node и empty, которые создают объекты соответствующих классов.
Для создания дерева из семи узлов (3 числа и 4 пустых узла)
необходимо написать:
Tree sample_tree=node(5, node(7,empty(),empty()), node(3,empty(),empty()));
Для обхода дерева в программу добавляются операторы match `e` (аналог switch) и rule `n` (аналог case), где `e` – ссылка на узел дерева, а `n` – конкретный тип узла. Эти операторы будут заменены Caio на условные операторы и преобразования с проверкой dynamic_cast. Например, для получения суммы элементов бинарного числового дерева нужно написать следующую функцию:
int sum1(Tree t)
{ match t {
rule node(v,l,r):
return v+sum1(l)+sum1(r);
rule empty():
return 0;
}
}
...
cout<<sum1(sample_tree)<<"\n";
Если какой-то тип узла не был обработан одним из предложений rule, то будет выведено сообщение об ошибке (можно убрать эту проверку опцией nomatcherror).
Альтернативным вариантом для обхода дерева является конструкция visitor `v`<`T`,`R`> { }, где `v` – имя посетителя, `T` – тип узлов, `R` – тип результата. В скобках указывается конструкции visit `n` для обработки узлов дерева, как в match. По данному описанию будет создан класс-посетитель `v`_visitor и конкретный объект этого класса `v`. В данном классе перегружается операция (), поэтому его можно вызывать как функцию. Этот вариант более эффективен, чем match, при большом количестве типов узлов, но менее гибок.
visitor sum2<Tree,int>
{ visit node(v,l,r):
return v+sum2(l)+sum2(r);
visit empty():
return 0;
}
...
cout<<sum2(sample_tree)<<"\n";
Перед первой конструкцией visit можно указать вспомогательные элементы структуры, которые можно использовать для накопления результата во время обхода:
visitor sum3<Tree,void>
{ int s=0;
visit node(v,l,r):
s+=v; sum3(l); sum3(r);
}
...
sum3(sample_tree);
cout<<sum3.s<<"\n";
Можно отделить описание типов от функций для их обработки, тогда при определении функций нужно подключить описание типов с помощью команды %using имя. Опция astprint добавляет в программу семейство функций astprint(ostream&, `T`), которое позволяет вывести дерево в отладочных целях.
