|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Kadatch 2:5020/400 19 Jul 2001 11:21:10
To : All
Subject : Re: Компилятор
--------------------------------------------------------------------------------
Я страшно извиняюсь, что влажу в разговор.
Для начинающих, на мой взгляд, лучшая книга -- Грис, "Разработка
компиляторов".
Без выкрутасов, просто и со вкусом. Сразу становится понятно, что и как --
понятно
рассказано, что такое синтаксическое дерево, внутреннее представление
программы,
достаточно много о грамматиках (достаточно, чтобы написать фронт с Си --
если догадаться
использовать LL-2 грамматику :-), не говоря уж о Паскале или Модуле).
Правда, о
кодогенерации автор стыдливо умолчал. И правильно сделал -- это наука
большая и
достаточно сложная.
В качестве следующего уровня -- работы Поттосина, Касьянова, Сабельфельда,
и, для полноты, Ахо и Ульман (я их не люблю -- они вдаются в такие
теоретические
дерби -- н-р, контекстно-свободные грамматики, -- которые разработчика
компилятора
ну просто совсем не интересуют). Будете знать все о грамматиках и внутреннем
представлении программ, а также основных методах оптимизации, как
машинно-независимой,
так и (немножко) машинно-зависимой. Потребуется знание теории графов --
будут нужны
терминология (чтобы не чесать репу над фразой "вершина А доминирует над
вершиной Б")
и, для практического использования, алгоритмы на графах.
Hу а если уж хочется написать что-нибудь, немного приближающееся по качеству
кодогенерации
к Visual C 7, рекомендую почитать "Advanced compiler design and
implementation" by Steven S. Muchnik и
другие 800-страничные фолианты. Hо это уже не для слабонервных.
Hаконец, существует просто огромное множество статей, посвященных различным
аспектам
компиляции и кодогенерации. Hу просто море. Поройтесь в сети или сходите в
comp.compilers.
Hу и совсем на прощание, я бы в качестве отправной точки использовал
компилятор lcc -- он
доступен в исходных текстах (поищите в сети). Советую обратить особое
внимание на:
- использование рукописного LL-2 парсера для Си (вместо LR-1, порожденного
по грамматике) --
рукописные анализаторы устойчивей к ошибкам и лучше восстанавливаются после
ошибок, да
и гораздо легче в понимании, поддержке и, начиная с некоторого уровня
сложности, в разработке;
- нетрадиционная (хмм, скажем, для некоммерческого продукта) система
управления памятью;
- "правильное" внутреннее представление (т.е. легко строится и с ним удобно
работать, а не
следует грамматике входного языка -- многие некоммерческие компиляторы,
доступные публике,
сильно грешат исключительно дилетантским исполнением);
- ну и, наконец, замечательный способ кодогенерации, основанный на
интенсивном использовании
DAG-ов (direct acyclic graph-ов) и BURG-грамматики. Просто, как три копейки,
и обратите внимание,
как замечательно работает (ну, lcc, ввиду отсутствия хорошей распределялки
регистров и оптимизатора,
код порождает тот еще, но, поверьте, если чуть-чуть поработать в этом
направлении, то задачу
выбора инструкций BURG решает замечательно -- не зря же аналогичный подход
используется рядом
сильно оптимизирующих компиляторов).
Должен сказать, что, на мой взгляд, lcc исполнен безупречно. Великолепная,
очень профессиональная
работа -- и, надеюсь, понятная и неспециалисту.
Дизайн lcc и принципы, на которых основан BURG, описаны в работах Криса
Фрэйзера (Christopher Fraser) --
надеюсь, в дистрибутиве lcc есть ссылки. Рекомендую почитать -- кое-что
станет понятней.
Hу и, наконец, что _не_ следует читать. В первую очередь, конечно, тексты
гнусного компилятора --
вот его-то и можно использовать на лекциях по теме: "Компиляторы: как можно
и как не нужно" -- во
второй половине курса, посвященной "как не нужно".
Пардон за длинное письмо,
АК
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
