Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, мыщъх, Вы писали:

M> Вообще непонятно, зачем это было.
на кывте писали, что кого-то просили разработать web-сервер в качестве тестового задания. "зачем это надо?" (с). действительно, зачем? сейчас web-сервер входит в набортные библиотеки практически всех современных языков с возможностью кастомизации. производительность, ес-но, никакая. но эту проблему можно решить на более высоком уровне абстракции путем балансировки нагрузки через dns, например.

калькулятор та же песня. во многих языках есть набортные парсеры, лексеры, понимающие bnf. и уж точно генератор парсеров сможет сгенерировать код на любом языке, включая чистый си без библиотек. писать руками? можно и руками, но пускай объяснят, что они хотят и как их танцевать. если генераторы парсеров им не нравятся, то почему они отказываются _явным_ образом запретить их использование?


M> Для калькулятора вообще непонятно, зачем там AST,
если гадать на кофейной гуще, то можно предположить, что калькулятор является частным случаем более общей задачи (распарсить Х) и необходимо продемонстрировать свои знания в этой предметной области.

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

M> обратная польская запись или другое промежуточное представление.
M> Там же все сразу вычислять можно.
сразу это как? а приоритет операций? 1+2*3? или упаси боже 1+2*-3? хотя если не умничать, то можно вычислять и "сразу", но в несколько проходов. сначала вычисляются операции с наивысшим приоритетом, а затем менее приоритетные. но это ИМХО как-то несерьезно.

M> Ну написал, и что?? Что они хотели увидеть через этот калькулятор? Фигня какая-то...
выше по ветке мне предлагали не выпендриваться, а реализовать калькулятор руками. но я с этим категорически не согласен. когда формулировка задачи требует телепатора, то тратить существенную часть времени, отведенного для решения, без гарантий того, что я движусь в правильном направлении... вот я и потратил 5 минут, показав BNF код. как тут уже справедливо заметили -- это не калькулятор, ибо он ничего не вычисляет. да, я в курсе. но мне важно знать движусь ли я в правильном направлении? если да -- прикрутим и вычисления. но оказалось, что ход моих мыслей неправильный.

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

Здравствуйте, skirty, Вы писали:

S>Здравствуйте, мыщъх, Вы писали:

М>>а самые-самые продвинутые даже распараллеливают выполнение однопоточного control flow на несколько цп.

S>Удивительно. В индустрии эта задача до сих пор не решена толком, а студенты одной левой.

см. выделенное. "самые-самые продвинутые". и никто не говорил, что они решают эту задачу лучше, чем разработчики "промышленных" компиляторов. но по крайней мере их знакомят с проблемой и существующими наработками в этой области.

Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, мыщъх, Вы писали:

S>у кого как было, у кого то в P-COD + его интопритатор
S>у меня фактически генерация в COM для MSDOS была (+-94 год)
круто. эх... (ностальгически вздыхая по com) было же время. а сейчас даже вывести синусоиду на экран в винде надо грызть гранит апи. а чтобы она еще и не мерцала... раньше хоть был обратный ход луча, а сейчас все сильно иначе. не представляю как можно преподавать на примере винды.

2/14/2014 6:18 AM, CEMb пишет:

> А что за гномики? О_о Расскажите, а то что-то я не в курсе, а то вдруг
> собеседование...
Открываешь книжку про гору Фудзи и проникаешься. Старые советские книжки
по разным интересным задачкам можешь не смотреть — это слишком сложно
для собеседователей.

2/14/2014 8:29 AM, mefrill пишет:

> Ну да, последние три работы на одну я к знакомым устроился, а две других
> -- моя предметная область и они меня знали уже. Не напрямую, а по
> книжкам и статьям. Ясно, что если люди не тебя знают, то будут
> собеседовать и пытаться выяснить, кто ты такой есть.
Ну и какое отношение к вопросу выше имел твой пост про штаты?
Похвастаться? Здесь??? Кому нужно, те и так тебя знают.

2/14/2014 8:42 AM, kaa.python пишет:

> Поиск помогает
> <https://www.google.ru/#newwindow=1&amp;q=задача%20о%20гномах>. Но вообще,
> там алгоритмы спрашивают, а не задачи о гномиках.
И "гномиков" тоже.

2/14/2014 8:42 AM, mefrill пишет:

> Я то что-то о себе думал поначалу,
> а оказалось -- это просто конвейер, у них там стандартные вопросы и
> должны быть стандартные ответы. В общем, плюнул и зарекся, больше на
> такие собеседования -- ни ногой!
Об этом тут последние 5 лет пишут или более. И если очень хочется к ним
, то идешь в инет, смотришь, как готовиться к их собеседованию
(стандартные вопросы-ответы), готовишься, сдаешь. Все, профит.

Здравствуйте, мыщъх, Вы писали:

M>> Там же все сразу вычислять можно.
М>сразу это как? а приоритет операций? 1+2*3? или упаси боже 1+2*-3? хотя если не умничать, то можно вычислять и "сразу", но в несколько проходов. сначала вычисляются операции с наивысшим приоритетом, а затем менее приоритетные. но это ИМХО как-то несерьезно.

Нет, такие языки очень просто можно парсить и по ходу вычислять. Надо магазин (стек) для сохранения параметров и операторов, а также таблицу приоритетов операций. Идешь по строке, вытаскиваешь число -- кладешь в стек, вытаскиваешь операцию -- смотришь по таблице приоритет с оператором на вершине стека. Если приоритет выше, то кладешь в стек, если нет, то выталкиваешь из стека операции и параметры и вычисляешь, а результаты -- снова в стек. Скажем, выражение 1*2+3:
1. Читаешь 1 -- в стек параметров.
2. Читаешь *, смотришь в стек операций, есть там чего? Нет, значит кладешь в стек.
3. Читаешь 2 -- в стек параметров.
4. Читаешь +, смотришь в стек. Там на вершине *, его приоритет больше. * -- бинарный оператор, выталкиваешь из стека два параметра, вычисляешь и результат снова в стек. Значит, там теперь 2. Снова в стек операций, там ничего нет, вталкиваешь +.
5. Читаешь 3 -- в стек параметров.
6. Читаешь конец строки, выталкиваешь операции и вычисляешь 2+3=5, результат снова в стек. Смотришь в стек операций, там ничего нет. Проверяешь размер стека параметров, там должен быть один элемент, иначе ошибка. Он там есть и равен пяти.

Разбор магазинным автоматом с приоритетом операций возможен для т.н. операторных грамматик. Для более сложных языков не годится. Но для арифметических выражений, для регулярных выражений и т.п. подходит хорошо.

Здравствуйте, Vzhyk, Вы писали:

V>Ну и какое отношение к вопросу выше имел твой пост про штаты?
V>Похвастаться? Здесь??? Кому нужно, те и так тебя знают.

Да написал сгоряча, не подумал. Бывает.

Здравствуйте, мыщъх, Вы писали:

A>>>>этот самый парсер пишется за час.
A>>>>вместе с тестами, ООП и "архитектурой" и т.п.

A>>наверное программисты получше меня напишут быстрее.
М>вот рекурсивный LL парсер выражений на чистом си:
М>http://rosettacode.org/wiki/Arithmetic_Evaluator/C

LOL parse_error делает exit(1). Си такой Си.

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, мыщъх, Вы писали:

M>>> Там же все сразу вычислять можно.
М>>сразу это как? а приоритет операций? 1+2*3? или упаси боже 1+2*-3? хотя если не умничать, то можно вычислять и "сразу", но в несколько проходов. сначала вычисляются операции с наивысшим приоритетом, а затем менее приоритетные. но это ИМХО как-то несерьезно.

M> Нет, такие языки очень просто можно парсить и по ходу вычислять.
M> Надо магазин (стек) для сохранения параметров и операторов, а также таблицу приоритетов операций.
а этот алгоритм работает с 1+2*-3? -2*2? а как быть тут: 1+--1? чтобы отличить унарный минус от простого минуса нужно что-то предпринять. думаю, что самое простое -- после того как нам встретилась операция мы автоматически переключаемся в режим ожидания унарного минуса (плюса) или числа. дальше движемся по цепочке унарных минусов (плюсов) пока не встретим число и запихиваем его в стек с учетом знака.

кстати, если операция возведения в степень это "**", то процедура считывания операции усложняется и в рамках машины состояний после того как мы считали "*" мы переходим в режим ожидания "+", "-", "*" или 0-9.

я бы предпочел написать несложный лексер. в частности, если мы вычисляем 1+2**--3*4, то лексер выдаст следующие токены: 1, +, 2, **, --3, *, 4.

однако, остается неясной ситуация с "-2**2". ожидаемый ответ -4 (можно проверить на том же питоне), а вовсе не +4, т.к. это -(2**2), а не (-2)**2. вот такие приоритеты, блин. неясно как в вашем алгоритме их обрабатывать.

калькулятор на самом деле хитрый, подлый и коварный. на примере с "-2**2*3-4" нам по ходу дела потребуется еще один стек. начинаем разбор выражения и видим "-". т.к. стек параметров пуст это не может быть операцией. следовательно, это унарный минус. и за ним следует число. но мы не можем на данном этапе ложить его в стек параметров как минус два, ибо в этом случае возведение в квадрат даст положительное число. мы держим его "в уме" и движимся дальше. а там у нас "**", за которым следует "*". а за умножением у нас вычитание. получается так

1) кладем минус на ум
2) кладем 2 на стек параметров
3) кладем ** на стек операций
4) кладем 2 на стек параметров
5) встречаем "*", смотрим на стек операций -- там возведение в степень, выполняем, кладем результат на стек параметров
6) кладем "*" на стек операций
7) кладем 3 на стек параметров
8) встречаем "-". стаскиваем минус с ума и обращаем знак параметра на вершине стека параметров, кладем "-" на стек операций
9) встречем "4" и стаскиваем минус со стека операций

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

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

Здравствуйте, Abyx, Вы писали:

A>Здравствуйте, мыщъх, Вы писали:

A>>>наверное программисты получше меня напишут быстрее.
М>>вот рекурсивный LL парсер выражений на чистом си:
М>>http://rosettacode.org/wiki/Arithmetic_Evaluator/C
A>LOL parse_error делает exit(1). Си такой Си.
это не си. это rosettacode такая rosettacode. вика такая вика. никакого ревью. (знаю, знаю. сейчас мне скажут что там есть edit и что если я такой умный, то мог бы исправить, но первым "крякнули" вы. так что вам и править). но exit(1) это ерунда. убрать глобальную переменную намного сложнее. для этого придется перелопатить кучу кода.

Здравствуйте, мыщъх, Вы писали:

М>круто. эх... (ностальгически вздыхая по com) было же время. а сейчас даже вывести синусоиду на экран в винде надо грызть гранит апи. а чтобы она еще и не мерцала... раньше хоть был обратный ход луча, а сейчас все сильно иначе. не представляю как можно преподавать на примере винды.

Да там всё просто, но только кому это надо?... я попытался применить где-то свои знания по графике — всего одна фирма нашлась(зато очень интересная, игры класса ААА), но в Питере. И всё... И видел ещё одного такого же человека, тут на форуме, но из другой страны, и с такими же проблемами

Здравствуйте, мыщъх, Вы писали:

М>вам не кажется, что простой разбор выражения оказался более сложным?
М>мне нравится BNF тем, что на нем можно добавить обработку такой ситуации путем добавления нового правила без правки уже написанного кода.

Все зависит от задачи. Простой калькулятор -- это простой калькулятор. Добавление в него сложных вещей делает калькулятор сложным. Думаю, для тестового задания никто сложные вещи не стал бы спрашивать. Ну и понятно, что BNF это не панацея, это только описание синтаксиса в определенной конкретной парадигме (порождающие КС-грамматики Хомского). Да и не все BNF можно, скажем, тем же Bison разбирать. Даже можно "расширить" синтаксис калькулятора таким образом, что его BNF не опишешь.

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, мыщъх, Вы писали:

М>>вам не кажется, что простой разбор выражения оказался более сложным?
М>>мне нравится BNF тем, что на нем можно добавить обработку такой ситуации путем добавления нового правила без правки уже написанного кода.

M>Все зависит от задачи. Простой калькулятор -- это простой калькулятор.
-2**2 это вроде бы основы основ. а BNF действительно не панацея. в частности он не в состоянии распарсить pdf, потому что pdf нужно парсить начиная с конца файла, продвигаясь к началу и лексеру требуется фидбак от парсера. хотя бы уже потому, что внутри стрима может быть ключевое слово endstream, а истинный конец стрима определяется по его длине (/Length number), причем number может быть как длинной, так и ссылкой на длину, которая может находится в любом месте файла. дополнительный источник информации xref таблица. при этом длина стрима в /Length может не совпадать с информацией из xref и если эти данные заданы некорректно, то мы должны обработать ситуацию восстановления ошибки, пытаясь открыть файл любой ценой.

нормальные парсеры не в состоянии двигаться от конца к началу. look ahead не помогает ;-( самое смешное, что парсер pdf, опирающийся на BNF, открывает порядка 99.96% файлов и даже используется во многих опен-сурсных проектах. оставшийся 0.04% файлов создатели опен-сурса игнорируют, отвечая: скажите спасибо, что оно вообще работает. LR парсер без хаков не сильно помогает. эксперименты с акробатом показывают, что мы имеем дело с unrestricted грамматикой.

один простой пример — ширина записей xref таблицы фиксирована и включает в себя перенос строки, поддерживая как \x0D\x0A, так и \x0A, но в совокупности должно получится 20 байт на строку, что делает разбивку на токены очень, очень нетривиальной задачей.

но это мелочи. акробат ищет магическое слово %PDF- в первом килобайте от начала файла и потому можно создать гибридный файл. например, pkzip и pdf в одном флаконе. или ms word и pdf. антивирусы проверяют первые байты файла в поиске magic word. пусть там будет D0 CF 11 E0 — антивирус говорит "ага" и парсит это как офис. а при открытии в браузее -- браузер смотрит на MIME тип и вызывает плагин акробата, открывающий зловредный pdf.

легко создать файлы, в которых блоки чередуются в произвольном порядке. это и офис и pdf. парсеры с ума сходят. причем наличе %PDF- в файле как бы не является основанием для заключения, что это pdf. и этим форматом пользуются миллионы людей? йаду мне, йаду.

A>>Компания наверн была в РФ?
М>нет, в сша. компания "маленькая, но гордая". не все компании такие. большинство компаний -- нормальные. но даже в нормальных компаниях попадаются совершенно уникальные личности. и если им доверяют собеседовать людей -- тогда "ой". но рассказывать о типичных собеседованиях неинтересно. потому что о них совершенно нечего рассказать. встретились. рассказали о себе, а я -- о себе. выясняется, что я хочу делать одно, а им нужно совсем другое. договорились если ни я, ни они ничего не найдут за определенный срок, тогда встретимся еще и будем идти на взаимный компромис, но это вряд ли, т.к. в сша рынок труда в ИТ довольно развит и если хорошо поискать, то можно найти _то_что_надо_. а когда находишь _то_что_надо_, то там и собеседования может не быть (в моем случае встретились за ланчем в ресторане, где даже ноута не было -- даже разогнав фантазию тут совершенно не о чем писать).

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

Здравствуйте, nen777w, Вы писали:

N>Блин, везет вам там,
1) давайте к нам;
2) ну как везет? работу я искал с августа по март. и это с правом работы в сша;

> а у нас в городе ко мне уже 3-и хрюши с разных
> рекрутинговых агенств с одними и теми же предложениями постучались.
на то они и хрюши. у них интнересная логика. работодатель выставляет требование к позиции -- наличие гражданства сша (и это не каприз работодателя, а действующее законодательство в сфере ИБ). а хрюша спрашивает про право работать в сша. ну как бы очевидно, что если я указываю тип визы в первой строчке резюме, то я не гражданин.

N>А так в основном... саппорт, дазы-банных, саппорт, и все
самое смешное, что сейчас меня зовут в рф те, кто раньше от меня отмахивались. когда-то я был готов работать за любую зарплату (лишь бы хватало на квартиру и еду). теперь предлагают некислые деньги, не понимая, что не все измеряется деньгами. как говорится, условие необходимое, но недостаточное.

> А к вам пока никак не выходит, поехать.
а что не выходит-то? настойчивее быть надо. я тут сейчас собираю в кучу свои заметки про сша как я мигрировал и все такое. приходилось действовать напролом и наугад.

Здравствуйте, artkarma, Вы писали:

A>Вообще-то парсер мат выражений на С++ — это тема курсовой работы старших курсов в одном из ведущих технических вузов Санкт-Петербурга, задание на весь семестр, причем сами всё, от и до, пишут процентов 13 студентов, 50 % не берут эту тему как сложную.

А по какой специальности?

Когда я учился в одном из московских вузов, компиляторы нам читали на 3-м курсе и курсовик был сложнее (но и делался он не в одиночку, а группой в 3-5 человек).

А калькулятор был то-ли лабораторкой, то-ли на семинаре изучали, как его делать (сейчас уже не помню подробностей). Да и пример калькулятора есть, наверное, почти во всех книгах по синтаксическому анализу.

2/17/2014 8:58 PM, мыщъх пишет:

> N>Блин, везет вам там,
> 1) давайте к нам;
nen777w у тебе уже с десяток раз спрашивал: "Как?"

Здравствуйте, Vzhyk, Вы писали:

>> N>Блин, везет вам там,
>> 1) давайте к нам;
V>nen777w у тебе уже с десяток раз спрашивал: "Как?"

Пришли мыши к сове. «Сова, нам от кошки житья нет. Ты птица мудрая, посоветуй, как быть!» Подумала сова. «Вот ежей, — говорит, — никакая кошка не тронет. Вам, мыши, надо ежиками стать!» Поблагодарили ее мыши, пошли домой, но с полдороги вернулись. «А как же мы можем в ежей превратиться?» «Вы, мыши, ко мне с мелкими деталями не лезьте, — отвечает сова, — я СТРАТЕГИЕЙ занимаюсь!

Но если объективно, тема "как" на этом форуме терлась стопицот раз и все кто хотел, включая мыщъха, уехали.