Здравствуйте, Graf Alex, Вы писали:
GA>А можно с этого места поподробнее?
GA>Что значит покрытие дерева паттернами и где возникает перебор?

Это обычно актуально при генерации машинного кода. У нас для каждой машинной
инструкции имеется соответствующий ей паттерн в дереве. Если инструкция простая,
вроде add r0, r2, r3 --- то ей соответсвует просто одна вершина дерева (+ int:x1 int:x2),
а вот если это нечто вроде lea eax, dword ptr [edx + 4*edi + <offset>],
то такой инструкции соответствует целый фрагмент из 3-х узлов ---
(+ int:x1 (+ (* 4 int:x2) int:imm32)).
Тогда задача генерации машинного кода может быть представлена в виде нахождения
покрытия данного дерева паттернами минимальной стоимости.
Про это немного есть в "Красном Драконе" (Ахо, Сети, Ульман. Компиляторы. ...)
Примерно так работает кодогенератор gcc, хотя там все конечно куда как
сложнее.

GA>Ведь у нас все данные уже распаршены и находятся в некотором дереве, что нам из него мешает писать прямо выходной код?
GA>Или может мы говорим о разных видах входных данных?

GA>Для пирмера сузим задачу до следующей: входной язык — паскаль, выходной — С.

GA>Как должна действовать схема транслятора?
GA>предположим во входном языке нет синтаксических ошибок. В варианте без использования парсера дерева я получил пачку классов, которые описывают Типы юзерских данных, описание глобальных переменных их инициализация если есть. Попути я ругал пользователя, за то что он некорректно объявил некоторые куски. В принципе этой информации вполне достаточно, что бы тем же визитором выписать код на С. (процедуры и функции меня пока не волнуют)

Вполне так можно сделать. Особенно если не стоит задача получения красивого года на выходе.
Впрочем, если стоит, то это все равно надо делать пo другому. Я подобную вещь делал,
и она была довольно сложной.
Между прочим, если Вам и впрямь паскаль в Си превратить надо, есть open-source конвертор,
поищите на http://www.garret.ru/~knizhnik/lang.html (Это мой бывший ученик и впоследствии
коллега по работе делал).
Если напрямую не сумеете применить, то хоть некоторые идеи сможете использовать.
Там, правда, на си все написано.

GA>Что я смогу выиграть, если в эту схему я включу парсер дерева?

В данном случае, думаю, надо делать без парсера.