О каких алгоритмах любят спрашивать на собеседовании разработчики компиляторов?

На собеседовании они любят поболтать о предстоящей зарплате, бонусах, соцпакете. Так же как и обычные люди.

Что в драгонбук до сих пор дэйтафлоу анализиз по факту отсутствует. Что жена подарила годовую подписку на пиво из пивного бутика, которым заправляют две лесбиянки. И т.п. :)

Если просят рисовать на доске алгоритмы, то надо валить оттуда.

Если просят рисовать на доске алгоритмы, то надо валить оттуда.

Разве не это так любят в Google/MS/Amazon/Facebook? Или это только к компиляторам относится?

по факту это как? год назад он там был, когда я читал драгон бук

Хоть я и понятия не имею что там на собеседованиях могут спрашивать. Если бы хотел поэкзаменовать, то я бы спросил что такое контекстно свободная, решаема ли для неё 'word problem', если да, то зачем нужны LL1, LR1, какой парсер применяется для разбора LL1 и LR1 соответственно. Почему context free не используется? Попросил бы преобразовать простенькую грамматику в LL1 или LR1 (соответствуенно удаление эпсилон-продукций, удаление лево-рекурсивных или право-рекурсивных продукций) ну и т.д. Попросил бы разобрать язык соответствующий грамматике и построить parse tree.

Не забыл бы и про регулярные выражения, про общее устройство компилятора (фронтэнд, бэкэнд, из чего состоянт, что такое AST чем отличается от parse tree, что такое jump code и т.п.)

Вперёд читать :)

LL1, LR1, какой парсер

прямо скажем, не самая важная часть современных компиляторов

Если там есть лоровцы, то обязательно попросят рассказать, как реализовать компилятор на OpenCL/CUDA, и чтоб он работал в тыщу раз быстрее обычного. Тут это один из любимых вопросов.

в интел устраиваешься?

Чего?

Собеседование оно такое:
куриш?Бухаешь с коллективом?Жена?Кредиты?Ты знаешь технологию HTML5 уже 25 лет?

Если на все это ответ ДА-ты принят,ты нормальный социально адаптированный идиот,а то что там программирование-так это научим,главное в коллектив войти,своим стать!

Тяжёлая у тебя жизнь, братюнь.

Во втором издании, в первом не было. И во втором его там тоже мало.

Классности книги не отменяет, просто за пивом с конпеляторописателем такой разговор был :)

Дык невозможно же, кэши чересчур малы

Эх, если бы дело было только в кэшах...

Про графы спрашиваем (алгоритм Дийкстры и тому подобное), про SSA, про аттрибутные грамматики, про динамическое программирование.

А вот как оаз поо всякое связанное с парсингом говно и прочий убогий дрэгонбук никто спрашивать не станет. Все раано у всех recursive descent. Да, и регулярные выражения тоже никому нах не нужны.

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

Вот ты и не прав, анон. рекурсивный спуск подходит для LL грамматик, а они не так круты как LR. А LR парсится табличным парсером. Тот же бизон генерирует табличный парсер.

Вот ты и не прав, анон. рекурсивный спуск подходит для LL грамматик, а они не так круты как LR. А LR парсится табличным парсером. Тот же бизон генерирует табличный парсер.

LL(1) включает в себя все грамматики из LR(1), за исключением леворекурсивных, а левая рекурсия легко устраняется автоматически. ANTLR, к примеру, генерирует нисходящий парсер. Parsec, ЕМНИП, тоже использует нисходящий алгоритм.

Ну и где твой бизон? В студенческих быдлоподелках только. Все промышленные компиляторы с рукописным recursive descent. Недавно peg еще начали применять. А автоматы - фуфло.

все - это какие?

LL(1) включает в себя все грамматики из LR(1)

Наглое 4.2 LL(k) это подмножество LR(k) для любых значений k.

Всякие PEG появились лишь по причине неосиляторства LR-грамматик, а recursive descent так популярен лишь потому, что на нем проще сделать вменяемый error reporting.

Если просят рисовать на доске алгоритмы, то надо валить оттуда.

что не так?

что не так?

Если соискатель не гуглится (патчи, свои проекты, статьи), это уже серьёзная причина его не рассматривать, ибо тема его за душу не берёт. По выгугленной же информации прекрасно составляется мнение о человеке. Зачем его вгонять в стресс у доски с этими алгоритмами? В реальной работе алгоритмы он будет обдумывать и реализовывать тихо и спокойно, со множеством походов за кофе/покурить, замеряя промежуточные результаты в vtune и т.п. В критических ситуациях, когда нужно что-то быстро у клиента заткнуть, там не алгоритмы переписываются, а именно что быстрый анализ проблемы проводится и самая тупая затычка клепается. Нормальный фикс делается позже, в спокойной обстановке.

У меня вообще самые лучшие идеи рождаются, когда я по камням на двухподвесе прыгаю. Когда в спину две-три пары глаз смотрят в ожидании даже простого фикса, то я из вежливо прошу свалить и не мешать. Впрочем, опытные товарищи сами всё знают и не имеют привычки пялиться в чужой экран.

А по поводу динамического программирования - можете объяснить, чего в нём такого особенного? Я так понял, это просто разбиение сложной задачи на простые. Зачем это называть каким-то специальным термином, вроде «динамическое программирование»? Это етественный процесс решения всех сложных задач...

Щито?!? PEG мощнее любого LR. Во первых, lexerless, во вторых динамически расширяемый, в третьих позволяет описывать high order грамматики. Повторяю для извращенцев-драконолюбов: автоматы - фуфло.

Это просто набор методов и эвристик. Спрашиваем про конкретные задачи, конечно же, например про tiling instruction selection.

Зачем это называть каким-то специальным термином, вроде «динамическое программирование»?

http://en.wikipedia.org/wiki/Dynamic_programming#History Всё просто.

Зачем это называть каким-то специальным термином, вроде «динамическое программирование»

Затемже зачем двустрочного чатбота называют ИИ(а не скриптом),затемже зачем описание столкновений называют физикой(а не условиями пересечений границ объектов),затемже зачем 56кб дулап называли «высокоскоростным интернетом»(а не ограничение скорости в 56кбит),затемже зачем ... та блин потомучто лучшего СЕГОДНЯ нет-на сегодняшних калькуляторах ну никак не сделать динамического программирования,поэтому составляют алгоритм,вручную моделируют до определенной глубины,и используют получившееся решение.

Пример практически используемой грамматики являющейся LR, но не являющейся LL без левой рекурсии, в студию.

a: T a | b
b: T b K | <empty>

Это LR(1) грамматика, которую нельзя переписать на LL(k).

Признавайся, какие именно буквы в выражении «практически используемой» ты не осилил?

PEG обладает либо худшей асимптотикой (если без мемоизации), либо большим потреблением памяти (если с мемоизацией).
Сделать «lexerless» можно и в том же bison например. Но это не нужно.
PEG - удел неосиляторов LR/GLR парсеров. Но да, если надо парсить HTML для говноагрегаторов то лучше PEG чем регулярки :)

Необычный вопрос, да

Ещё бы! Это где такое?

ок, приведи пример хотя бы «практически неиспользуемой» LL(k) которая не являлась бы при этом LR(k).

свои проекты, статьи

Ну, с проектами ещё куда ни шло, а если статьи не под своим именем публикует?

Драконофилы все такие примитивные и зашоренные!

Осиль расширяемую грамматику как в Fortress или Katahdin в своем убогом и бесполезном LR.

Ты как раз отлично подтверждаешь эмпирическое правило, которому давно следуют все комптляторные группы из известных мне (Intel, Microsoft, ARM) - любителей автоматов гнать ссаными тряпками.

Так что в промышленных компиляторах ты свой ничтожный LR никогда не увидишь. И на работу в приличной группе претендовать с такими заскоками нн сможешь никогда.

Нет. Ты приводи пример грамматики реально используемого языка программирования, котора требовала бы LR.

Java, C++, C# - всё это требует дополнительного способа разрешения конфликтов в добавку к классическому LL(1).
И даже те языки, которым достаточно LL, могут быть записаны более кратко в LR.

Чушь. Короче чем peg не запишешь, ebnf - параша. С автоматным LR тебе не будет внятного error recovery никогда.

А по поводу динамического программирования - можете объяснить, чего в нём такого особенного? Я так понял, это просто разбиение сложной задачи на простые. Зачем это называть каким-то специальным термином, вроде «динамическое программирование»? Это етественный процесс решения всех сложных задач...

Нет, динамическое программирование - это способ вычисления рекурсивных функций.

А что за способ вычисления рекурсивных функций может быть, отличный от вызова самой себя? (-; Она же рекурсивная.

f(x, y) = max{ f(x-1, y), f(x, y-1) } + g(x, y)

Вызывай...

ибо вонабиконтора? или

покури про уравнение белмана .

а если по простому то часто динпрогом называют миморизацию которая заменяет экспоненту использованием памяти.

естестеный процесс разбиение задачи на подзадачи может приводить к жадному решению - наилучший пример это сортировка за куб.http://en.wikipedia.org/wiki/Stooge_sort

дин прог это понимание что локальный оптимум не обязателен быть на траектории ведущий к глобального оптимуму ( на последнем шаге задачи) .

т.е понимать что полное состояние системы это не только активные но и реактивные показатели . и будущее состояние системы зависит не только он явных(активных) но и от сложно самих по себе измеримых реактивных(потенциальных) параметров.