December 1st, 2016

Технотрек: Занятия 09, 10: Рекурсивный спуск


(Копия блога на Технотреке)

Summary

На лекции мы рассмотрели восстановление дерева из записи, в которой взаимоотношение узлов задано неявно, с помощью приоритетов операций, в более общем случае - с помощью грамматики. Эта задача называется синтаксическим анализом. Одно из ее решений - метод рекурсивного спуска. Несмотря на то, что он достаточно прост, к сожалению, в сети нет внятных его описаний. Поэтому на лекции мы рассматривали много примеров, рисовали деревья синтаксического разбора и читали мантры. :) Хорошая метафора рекурсивного спуска - работа строительной бригады, устроенной наподобие этого:



Следуя нашему методу рассмотрения рекурсивного спуска, нетрудно добавить в грамматику не только арифметические действия, но и операторы присваивания, условия, цикла, вызова функции и другие.

Домашнее задание
Collapse )