LVV>>Зато она ЗНАЧИТЕЛЬНО толще... LVV>>Страшно открывать! P>Следуя твоей логике, матан вообще не стоит пытаться изучать. Трехтомник Фихтенгольца гораздо толще книги Дракона.
Ты будешь смеяться, но Кормен реализовал такой подход на практике.
Основная книга Кормена: https://www.ozon.ru/context/detail/id/22421471/ — ТОЛСТАЯ, овер 1300 страниц
Для тех, кому основную СТРАШНО открывать: https://www.ozon.ru/context/detail/id/24903185/ — 208 страниц...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[4]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, LaptevVV, Вы писали:
P>>Следуя твоей логике, матан вообще не стоит пытаться изучать. Трехтомник Фихтенгольца гораздо толще книги Дракона. LVV>Ты будешь смеяться, но Кормен реализовал такой подход на практике.
Ничего подобного. Аудитория у книг разная.
Это, как в вузах. На некоторых факультетах преподают всю математику в течение 4 или 5 семестров. А на других 3 семестра матана, 2 — алгебры, дифуры и т. д.
Так и здесь. Для профильной специальности — 1300 страниц, для остальных — 208 хватит.
Re[7]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, Flying Dutchman, Вы писали:
FD>Во время разговора с профессором Голуб выяснил, что тот никогда в жизни не написал сам ни одного компилятора
Теоретики это любят. Мне тут один долго рассказывал, что GLR быстрый алгоритм. На просьбу "код в студию" раздалось невнятное бу-бу-бу, после чего теоретик исчез.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, WolfHound, Вы писали:
WH>Гадость редкостная. На весь талмуд я насчитал три полезных страницы.
Второе издание стало по приличнее. Для начинающих как общее введение пойдет.
Твоя к нему неприязнь несколько надумно.
Просто нужно заранее понять и принять, что там нет суп-новых технологий, а ты имеешь дело с общим введением.
WH>После такой "классики" люди начинают думать, что компиляторы это что-то сложное.
Компиляторы это действительно что-то не простое. Потому мы Nitra и делаем.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, VladD2, Вы писали:
VD>Просто нужно заранее понять и принять, что там нет суп-новых технологий, а ты имеешь дело с общим введением.
Pratt parser: It was first described by Vaughan Pratt in the 1973 paper "Top down operator precedence"
Книга дракона:
Principles of Compiler Design (1977, the "Green Dragon Book"), by Alfred V. Aho and Jeffrey D. Ullman
Compilers: Principles, Techniques, and Tools, First Edition (1986, the "Red Dragon Book"), by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman
Compilers: Principles, Techniques, and Tools, Second Edition (2006, the "Purple Dragon Book"), by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman and Monica S. Lam
Как видишь, я говорю про алгоритм, который старше самой первой книги дракона.
Через 33 года после публикации про этот алгоритм в книгах дракона нет ни слова.
А он долгое время был лучшим практическим алгоритмом.
VD>Компиляторы это действительно что-то не простое. Потому мы Nitra и делаем.
Nitra решает задачу построения модульных компиляторов плюс IDE в подарок. Это действительно что-то не простое. Почти все наши проблемы связаны с тем, что нам нужно работать в режиме IDE.
А простой компилятор без IDE делается очень просто.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, pestis, Вы писали:
P>Драконовая книга. Как бы считается классикой
Дракон конечно классика но нужно иметь в виду:
1. Первое издание этой книги крайне устарело и вообще не адекватно. Например, целые разделы посвящены обсуждения рукопашного создания хэш-таблиц. Так что первое издание читать категорически нельзя.
2. Книга описывает классическую теорию которая осталась где-то в 70-х годах. За это время наука и практика ушли далеко вперед.
3. В книге много довольно низкоуровневых погружений в совершенно второстепенные вещи. Можно легко запутаться и начать тупить хотя на практике это или не нужно вообще или довольно просто объясняется, если объяснять без заумностей.
4. Язык книги (особенно русский перевод) крайне косноязычен излишне удлинен и запутан. Так что надо приготовиться, что некоторые разделы придется перечитывать по 5 раз просто для того чтобы въехать в тему.
5. Надо сразу понимать, что по прочтению этой книге вы не сможете создать современный компилятор. Это только набор общих знаний.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, WolfHound, Вы писали:
WH>Pratt parser: It was first described by Vaughan Pratt in the 1973 paper "Top down operator precedence"
WH>Книга дракона:...
В разделе "4.8.1 Precedence and Associativity to Resolve Conflicts" рассказывается о разрешении неоднозначностей с помощью приоритета и ассоциативности.
В разделе 3.4.5 и читаем:
Knuth, Morris, and Pratt presented an algorithm for recognizing a single keyword &i&2 • • • K in a text string. Here the trie is a transition diagram with n states, 0 through n. State 0 is the initial state, and state n represents acceptance, that is, discovery of the keyword.
Делаем вывод. Авторы считают алгоритмы эквивалентными Кнута, Мориса и Пратта эквивалентными и приводят только алгоритм Кнута (видимо из-за того что он проще для понимания императивщика и более известен).
WH>Как видишь, я говорю про алгоритм, который старше самой первой книги дракона. WH>Через 33 года после публикации про этот алгоритм в книгах дракона нет ни слова.
Как вижу ты сам второго издания не читал или читал по диагонали.
WH>А он долгое время был лучшим практическим алгоритмом.
Ты сам о нем узнал совершенно не давно. Не нашел бы я его в какой-то помойке и сейчас бы ничего о нем незнал. А Харкейс использовал Кнутовский алгритм еще когда писал парсер шарпа на Пеге (где Праттом и не пахло).
Что до "лучшим практическим алгоритмом", то ты выдаешь желаемое за действительность. На практике 99% рукописных парсеров использовали рекурсивный спуск. Ну, еще клоны Яков использовали где так же были реализации приоритетного парсинга для LR-автоматов (описанного в книге).
VD>>Компиляторы это действительно что-то не простое. Потому мы Nitra и делаем.
WH>Nitra решает задачу построения модульных компиляторов плюс IDE в подарок.
Можно подумать что создать не модульный компилятор серьезного языка может любой мальчик с улицы.
Nitra, конечно, крута и решает кучу проблем очень высокоуровневым образом, но тем не менее сдеать компилятор даже без IDE, модульности и расширяемости на лету для большинства не реально сложно. И Дракон дает хоть какое-то представление. Тем более что у него почти нет конкурентов.
WH>Это действительно что-то не простое. Почти все наши проблемы связаны с тем, что нам нужно работать в режиме IDE.
Ох. Я лучше о проблемах помолчу.
WH>А простой компилятор без IDE делается очень просто.
Гы-гы.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, WolfHound, Вы писали:
> И Дракон дает хоть какое-то представление.
давайте так... давайте представим себе... компилятор. подадим ему на вход байт-код. на выходе — нативный код со сборкой мусора, с некой моделью безопасности, с оптимизацией хотя бы (хотя бы!) на уровне распределения переменных по регистрам.
стоп. мы линкер забыли. балин. линкер написать это не мешок соли съесть. чтобы собрать несколько файлов в один, да еще с поддержкой разных фич типа отладочной инфы и разных форматов файлов -- это сложно. и сложность тут уровня -- как сравнить две строки в уникоде (это символьные имена если что) если один и тот же символ в разных строках закодирован по разному? уже над одним этим решением можно ломать голову месяцами.
> Тем более что у него почти нет конкурентов.
у меня полки ломятся от книжек о компиляторах. конкурентов очень много. и многие конкуренты намного более монументальны и их очень тяжело поднимать с полки с моим-то телосложением, но зато в них намного больше внимания уделяется тому, что появилось после книги дракона. вот например, современные компиляторы (gcc, студия) борются с ошибками переполнения и если вы хотите чтобы ваш компилятор делает атаку на скомпилированный код намного более нетривиальной -- дракон это вам расскажет? или это мелочь, а нам нужна матчасть? ну так дракон далеко не самая лучшая книга по матчасти по любому.
WH>> А простой компилятор без IDE делается очень просто. VD> Гы-гы.
среди моих знакомых -- разработчиков промышленных компиляторов больше дюжины. на небожителей они совсем непохожи и все они кроме того, что пишут и поддерживают компиляторы имеют еще и область специализации. в дополнение к. и основные области их специализации они сложнее чем. один (мой самый близкий други среди других остальных) нейропроцессоры разрабатывал. это сложнее и этим занимаются намного меньше людей. во всяком случае серийные нейропроцессоры.
или взять такой уникальный во всех отношениях продукт как ida pro (дизассемблер, а сейчас и декомпилятор). отродясь там был IDA C. не компилятор, но очень близко. так что не надо говорить, что это сложно. вот компилятор си++ это сложно, но мы же не об этом, да?
на нашем хуторе где универ совмещен с рестораном (такой мааааленький универ, да) студенты пишут компиляторы еще до того как выберут тему дипломной. при этом компилятор выдает бинарный код для x86 в ELF на котором можно даже писать программы. в этом году решили привлечь raspberry pi и писать под ARM, а то теснота хутора стала приводить к злоупотреблению обмена кода между поколениями студентов. по крайней мере тупо списать уже не получится. это я к тому, что в 21 веке технологии компиляции...
...а еще недавно доказательство теоремы пифагора было ОТКРЫТИЕМ! и буквально вчера ньютон додумался до интегралов, но до ума их довел уже галлей, да и то не один. на тот момент расчет орбиты кометы галлея был настоящим математическим прорывом. настолько прорывным прорывом, что вычисления не успевали закончить в срок. комета вернулась бы раньше и потому точность вычислений принесли в жертву. тем более, что она и не вернулась в предсказанный срок. а задержалась в пути. это юпитер ее задержал. весьма нетривальным путем удалось рассчитать новый срок возвращения. а сейчас кто угодно может рассчитать не только когда примерно появится комета, но где именно она появится. делов-то. хотя это и выходит за рамки средней школы.
это я к тому, что все, чему вас _научили_ (в т.ч. и книги) не может быть запредельно сложным. вам могут встретиться плохие книги. скажи мне что сложно для постижения, друг мой и я скажу какую каку ты читал. ну а если дошел своим умом, то снимаю шляпу (но это случай другой).
ЗЫ. книгу дракона я читал и она у меня больше, чем в одном экземляре. хорошая книга. не спорю. но говорить, что конкурентов нет -- извините, но это говорит о том, что вы даже не смотрели что сейчас продают на том же амазоне.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Re[3]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, VladD2, Вы писали:
VD>5. Надо сразу понимать, что по прочтению этой книге вы не сможете создать современный компилятор. Это только набор общих знаний.
А какую литературу порекомендуете для более полного ознакомления с современными технологиями? Желательно на русском, если такие издания существуют, конечно.
Re[6]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, VladD2, Вы писали:
VD>В разделе "4.8.1 Precedence and Associativity to Resolve Conflicts" рассказывается о разрешении неоднозначностей с помощью приоритета и ассоциативности.
Там про LR.
VD>Делаем вывод. Авторы считают алгоритмы эквивалентными Кнута, Мориса и Пратта эквивалентными и приводят только алгоритм Кнута (видимо из-за того что он проще для понимания императивщика и более известен). http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Это один алгоритм.
И к парсеру Пратта он отношения не имеет.
Попробуй найти там хоть слово про операторы.
VD>Как вижу ты сам второго издания не читал или читал по диагонали.
Меня уже достало то, что ты делаешь выводы, не разобравшись в вопросе.
VD>Ты сам о нем узнал совершенно не давно. Не нашел бы я его в какой-то помойке и сейчас бы ничего о нем незнал.
В этом то и проблема. Если бы о нём хотя бы упоминали в литературе, то узнал бы намного раньше.
VD>А Харкейс использовал Кнутовский алгритм еще когда писал парсер шарпа на Пеге (где Праттом и не пахло).
Он использовал вот этот алгоритм. http://en.wikipedia.org/wiki/Shunting-yard_algorithm
Этот алгоритм придумал Дейкстра. И к алгоритму Кнута, Мориса и Пратта он тоже не имеет никакого отношения.
Кстати можешь попробовать изобразить на нём тренарный оператор.
В то же время парсер Пратта жрёт всё.
VD>Что до "лучшим практическим алгоритмом", то ты выдаешь желаемое за действительность. На практике 99% рукописных парсеров использовали рекурсивный спуск. Ну, еще клоны Яков использовали где так же были реализации приоритетного парсинга для LR-автоматов (описанного в книге).
Что там использовали на практике дело десятое.
Про сообщения об ошибках LR парсеров народ легенды слагает. А уж как грамматику уродовать приходиться.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[7]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, WolfHound, Вы писали:
VD>>В разделе "4.8.1 Precedence and Associativity to Resolve Conflicts" рассказывается о разрешении неоднозначностей с помощью приоритета и ассоциативности. WH>Там про LR.
Там даются общие сведения о неоднозначностях имеющихся в операторных грамматиках и о способах их разрешения. Примеры для LR характерны для американской научной школы. Они везде и всегда суют LR (LALR, SLR) из неизвестных соображений (видимо традиции и любовь к ДКА).
Но уж лучше что-то чем ничего.
WH>Это один алгоритм. WH>И к парсеру Пратта он отношения не имеет.
ОК. Значит Праттовский алгоритм они действительно не упоминаю. Это конечно упущение, но все же не Праттом единым. Кстати, PEG во второй редакции упоминается.
Вообще в мире есть море не очень известных алгоритмов. Праттовский один из них. К тому же Пратовский алгоритм это адаптация Operator-precedence алгоритма к рекурсивному спуску. Пратт сам об этом писал.
Собственно в "Драконе" никто и не обещал исчерпывающих список алгоритмов.
Ты, например, тоже изменил алгоритмы, взятые за основу, до неузнаваемости и по факту создал новый лагоритм. Но о нем кроме нас с тобой никто больше и не знает. Одна только идея соединить парсинг и поиск кротчайшего пути при парсинге уже стоит упоминания как отдельного алгоритма (хотя и относится к восстановлению).
Авторы "дракона" не виноваты, что кто-то недостаточно отпиарил свой алгоритм. В их книге и без этого не мало интересного есть. Например, более полного описания атрибутных грамматик я не видел. Или вопросы генерации промежуточного кода и последующей трансляции его в машкод.
VD>>Как вижу ты сам второго издания не читал или читал по диагонали. WH>Меня уже достало то, что ты делаешь выводы, не разобравшись в вопросе.
А меня твои предвзятое отношение к вещам и чужому труду. Видите ли "не идеал, значит в топку".
VD>>Ты сам о нем узнал совершенно не давно. Не нашел бы я его в какой-то помойке и сейчас бы ничего о нем незнал. WH>В этом то и проблема. Если бы о нём хотя бы упоминали в литературе, то узнал бы намного раньше.
Ну, в других книгах тоже ничего про Праттовский алгоритм не сказано. Что же поделать? Остается только самим написать правильную книгу.
WH>Он использовал вот этот алгоритм. WH>http://en.wikipedia.org/wiki/Shunting-yard_algorithm
In computer science, an operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation relying on order of operations to a format that is optimized for evaluation such as Reverse Polish notation (RPN).
Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator precedence parsers. Other algorithms include the precedence climbing method and the top down operator precedence method.
По сути Пратт встроил bottom up-схему в nop down-парсер, так что он формально становится не совсем "рекурсивного спуска".
WH>Этот алгоритм придумал Дейкстра.
Ну, может я и путаю авторов. Но сути дела это не меняет. Схема одна и та же. Понятно, что адепты Bottom up-методов демонстрируют ее на том что им ближе.
WH>Кстати можешь попробовать изобразить на нём тренарный оператор.
Да, как-то у Хардкейса никаких проблем не возникло с этим. Принципы то одни и те же.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, мыщъх, Вы писали:
М>у меня полки ломятся от книжек о компиляторах. конкурентов очень много. и многие конкуренты намного более монументальны и их очень тяжело поднимать с полки с моим-то телосложением, но зато в них намного больше внимания уделяется тому, что появилось после книги дракона.
Ну, дык давай ссылки. А то может ты единственный хранитель важной информации.
М>вот например, современные компиляторы (gcc, студия) борются с ошибками переполнения и если вы хотите чтобы ваш компилятор делает атаку на скомпилированный код намного более нетривиальной -- дракон это вам расскажет? или это мелочь, а нам нужна матчасть? ну так дракон далеко не самая лучшая книга по матчасти по любому.
Это все не относится к базовым сведениям, а является частной проблемой отдельных языков.
М>среди моих знакомых -- разработчиков промышленных компиляторов больше дюжины.
А, среди моих знакомых разработчиков веб-мордочек и корпоративного софта больше сотни. И это явно только малая толика. Дижина же это не так много, согласись.
Кстати, можно увидеть список языков для которых твои знакомые пишут компиляторы. А то у меня, почему-то, знакомых писателей компиляторов почти нет. А я сам этим занимаюсь.
М>один (мой самый близкий други среди других остальных) нейропроцессоры разрабатывал.
И как, получилось? Где их можно купить?
М>это сложнее и этим занимаются намного меньше людей.
Я тебе могу назвать еще кучу дел которыми занимаются единицы и что? Мы тут мериться чем-то собрались?
Как это делает простым создание компилятора сложного языка?
М>или взять такой уникальный во всех отношениях продукт как ida pro (дизассемблер, а сейчас и декомпилятор). отродясь там был IDA C. не компилятор, но очень близко. так что не надо говорить, что это сложно. вот компилятор си++ это сложно, но мы же не об этом, да?
Компиляторы это сложно. Чем сложнее язык, тем сложнее компиляторы. И то что кто-то там создал IDA C не значит, что ему было легко, хотя IDA C это вряд ли компилятор, и явно очень простой язык (C).
М>на нашем хуторе где универ совмещен с рестораном (такой мааааленький универ, да) студенты пишут компиляторы еще до того как выберут тему дипломной.
Студенты пишут много разных поделок. А вот когда на практике нужно создать компилятор для боле-менее серьезного языка, бвшие студенты изобретают разую фигню вроде языков на основе ХМЛ-я (XAML, WIX, ...) и все равно занимаются этим долго и тратят много сил.
Сама область не простая и требует знаний и инструментов. Потому им в универах и учат. Тольво вот учат их тому же что в Драконах или даже более примитивным знаниям. Для многих паресер-комбинаторы являются Биномом Ньютона.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, AlexRK, Вы писали:
ARK>А какую литературу порекомендуете для более полного ознакомления с современными технологиями? Желательно на русском, если такие издания существуют, конечно.
К сожалению, для полного охвата придется искать отдельные статьи. По парсерам интересны алгоритмы Packrat (упоминается во втором драконе, но не разбирается серьезно, если не ошибаюсь), TDOP Pratta, GLR и GLL представляют теоретический интерес, ALL(*).
Мы в Nitra реализовали алгоритм на основе Packrat-а и TDOP, плюс алгоритм восстановления на основе модифицированного алгоритма Earley. Уверен, что по сумме показателей наш алгоритм на сегодня самый совершенный, хотя, как и все на земле, не идеальный. ALL(*) из ANTLR тоже интересный алгоритм, но он не поддерживает динамической расширяемости и имеет ряд ограничений.
GLR и GLL самые мощные (всеядные) алгоритмы, но из-за своей тормознутости плохо применимы на практике.
Серьезных работы по типизации я вообще не видел. Лучшее что видел — это что-то описывающее типизацию в ML-подобном языке. При этом там было море "матана", т.е. мозгоразрывающих формул и туманных и длинных объяснений.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Там даются общие сведения о неоднозначностях имеющихся в операторных грамматиках и о способах их разрешения. Примеры для LR характерны для американской научной школы. Они везде и всегда суют LR (LALR, SLR) из неизвестных соображений (видимо традиции и любовь к ДКА).
Проблема в том, что для практического применения эти алгоритмы не годятся.
А любят они их из-за того что можно понаписать кучу всяких формул с доказательствами. Это всё выглядит очень круто и умно.
А алгоритм Пратта простой как 3 копейки. И работает лучше, чем весь это автоматный бред.
Если о нём написать, всё остальное, что написано про парсеры, придётся выбросить.
Ибо у читателей возникнет закономерный вопрос: Какого хрена я всё это читал, если простейший алгоритм в пару десятков строк работает лучше?
VD>Собственно в "Драконе" никто и не обещал исчерпывающих список алгоритмов.
В книге, которая претендует на практическое пособие по разработке компиляторов, должна быть не заумная хрень, которая на практике не работает, а то, что можно использовать для практической работы.
VD>Ты, например, тоже изменил алгоритмы, взятые за основу, до неузнаваемости и по факту создал новый лагоритм. Но о нем кроме нас с тобой никто больше и не знает. Одна только идея соединить парсинг и поиск кротчайшего пути при парсинге уже стоит упоминания как отдельного алгоритма (хотя и относится к восстановлению).
Я говорю про алгоритм, который появился за 33 года до второго издания.
VD>А меня твои предвзятое отношение к вещам и чужому труду. Видите ли "не идеал, значит в топку".
Ох. То, что понаписано в книгах дракона, для практической работы использовать нельзя. Оно слишком сложное и даёт плохие результаты.
VD>Да, как-то у Хардкейса никаких проблем не возникло с этим. Принципы то одни и те же.
А отличие от тебя я посмотрел, как Стас его реализовал.
... << RSDN@Home 1.2.0 alpha 5 rev. 62>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Чего бы почитать про архитектуру компиляторов?
Здравствуйте, NeoCode, Вы писали:
NC>Я смотрю понемногу исходники компилятора языка D. Для начала рассчитываю добавить пару возможностей, а затем постепенно полностью переделать в свой собственный язык программирования
Тупиковый путь. Убьешь много лет и станешь заложником принятых автором компилятора решений. Проверено.
Мы вот для подобных целей разрабатываем Nitra. С ее помощью разрабатывать свои языки будет проще в 100 раз и можно менять что захочешь когда захочешь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
