Технотрек: Занятия 09, 10: Рекурсивный спуск
(Копия блога на Технотреке)
Summary
На лекции мы рассмотрели восстановление дерева из записи, в которой взаимоотношение узлов задано неявно, с помощью приоритетов операций, в более общем случае - с помощью грамматики. Эта задача называется синтаксическим анализом. Одно из ее решений - метод рекурсивного спуска. Несмотря на то, что он достаточно прост, к сожалению, в сети нет внятных его описаний. Поэтому на лекции мы рассматривали много примеров, рисовали деревья синтаксического разбора и читали мантры. :) Хорошая метафора рекурсивного спуска - работа строительной бригады, устроенной наподобие этого:
Следуя нашему методу рассмотрения рекурсивного спуска, нетрудно добавить в грамматику не только арифметические действия, но и операторы присваивания, условия, цикла, вызова функции и другие.
Домашнее задание
1. Реализуйте синтаксический анализатор простых арифметических выражений с операциями +, -, *, / над числами, с поддержкой скобок. Анализатор должен выводить ответ выражения. Дерево на этой стадии строить не надо.
2. Добавьте в анализатор операцию возведения в степень, функцию вычисления квадратного корня, поддержку переменных.
3. Теперь переделайте анализатор из задачи (1), чтобы строилось синтаксическое дерево. После этого переделайте анализатор (2) также с построением дерева.
4. Обойдите дерево через postorder и сформируйте ассемблерный файл для вашего процессора, выводящий ответ выражения.
5. Примените оптимизатор деревьев, взятый из задачи о символьном дифференцировании, перед кодогенерацией, у вас получится оптимизирующий компилятор.
6. Добавьте в (3) операторы присваивания и цикла. Дополните кодогенератор (4) поддержкой этих операторов.
7. Придумайте свой собственный язык программирования и реализуйте компилятор с него в код вашего процессора.
8. Захватите же, наконец, мир!
***
Удачи, и May the Source be with you! :)