Мне доводилось сопровождать код, объёмом 100000 строк, написанный с использованием такого приёма. Это была самая страшная пытка. Генерить методы налету — величайшее зло, ибо их потом даже нельзя нагрепать в сорцах; а если у вас 15-и кратное наследование, то найти, где же, что появилось… ну просто невозможно! Никогда так не делайте!
И всё же почитайте книжки. Кстати, есть довольно древний алгоритм Бауэра и Замельзона в котором используются два стека. Возможно, он вам будет более симпатичен, чем более современные подходы… Почитайте! Уверяю вас — вам понравится!
это «разные вещи», которые работают одинаково (возможно поэтому они и называются одинаково :-)); и именно на этом я и предлагаю сыграть :-)
И всё же… я вам очень советую не читать мои комменты, не читать мои странички,… а почитать хорошие книжки; можно начать с этой ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf (есть более новая версия этой книги, но я что-то не смог её нагуглить). Я вижу, как вам нравится эта тема. Поверьте! Чтение этой (и других) книжки доставит вам на много больше удовольствия, чем попытки меня в чём-то убедить! Удачи!
Может кому будет интересно. Вот тут лежит моя статья на эту тему.
(она была опубликована в журнале «системный администратор», а автор сайта видимо просто её стырил; ну Бог ему судья)
Вы просили меня прокомментировать с удовольствием.
Во-первых, спасибо за статью! Она лучше многих, я действительно так думаю, хотя вещи, которые я сейчас напишу могут вам не понравиться :-)
К делу.
Прежде всего, я бы советовал вам, почитать что-нибудь про грамматики. Тогда вместо наивных фраз любое сложно выражение (кстати, опечатка), вы могли бы написать грамматика класса LL(1) или что-то в этом духе. Когда вы говорите о разборе выражения, уместно классифицировать его грамматику, иначе звучит диковато и безграмотно (есть выражения, за разбор которых вы получите большие премии от видных математических обществ. есть выражения, которые невозможно разобрать и это доказано).
Далее. Зачем два стека? Вы же точно знаете, как чередуются операции и операнды! Чтобы соблюсти это чередование вы даже добавляете 0 к унарным операциям. Всё можно было бы положить в один стек.
О работе работе со стеком. Ваш алгоритм заставляет вас работать не только с верхушкой стека. Это дополнительное усложнение и источник ошибок. (Кстати, судя по обсуждению, вы не смогли избежать ошибок. А я вас предупреждал об это ещё до публикации этого поста. Работа со стеком требует большой аккуратности)
А теперь вспомним как работает алгоритм рекурсивного спуска. Вспомним, что локальные переменные хранятся в стеке. И что мы видим? Тот же стек, но! 1) он один 2) алгоритм не требует (и даже не позволяет) заглядывать под вершину стека 3) нет никаких проблем с унарными операторами и более сложными грамматиками 4) и самое главное нет необходимости работать со стеком руками! ошибки просто невозможны.
Мне кажется, вы здесь сформулировали тот же алгоритм рекурсивного спуска но, развернули рекурсию и написали работу со стеком вручную, разделили стек на два (видимо интуитивно, вы отделили терминальные токены в один стек, а не-терминальные в другой, но в этом нет никакой необходимости) и добавили костыли в виде переформулирования унарных операций, чтобы сделать разбираемый случай ещё более частным.
Если бы вы использовали рекурсивный спуск, вы застраховались бы от многих ошибок и получили бы универсальный парсер, в который можно было бы легко встроить, скажем, функции или операции с тремя операндами (типа А?B:C). В ваш теперешний парсер встроить такие возможности очень сложно (можно ли вообще). И править его очень опасно, так как тронув стек в одном месте, надо отследить, чтобы всё не посыпалось в другом.
Одним словом, ваш алгоритм я бы не стал использовать сам и не стал бы советовать другим.
1) Я никогда не оптимизировал сайт, но он по многим запросам попадает на первую страницу выдачи гугла. Примеры: спросите у google «perl vs python», «qemu и Windows», «загрузочный CD Grub», «примеры использования рекурсии», «применение фракталов», «парадокс близнецов», «гиперкуб»… это запросы, по котором приходили люди за последние несколько минут. Вывод — и без оптимизации можно привлечь много читателей.
2) Я очень ценю читателей, я ежедневно получаю письма с замечаниями, исправлениями, вопросами, ответы на которые превращаются в новые материалы… Иногда мне очень хочется поделиться с людьми какой-нибудь свежей мыслью и тогда я даю где-нибудь ссылку. Последний раз я прибег к хабру (просто карма была и мысли были; думал, что людям будет интересно и надеялся на конструктивный фидбэк). И что же я получил? Несколько невнятных комментариев в блоге. Несколько одобрительных отзывов в привате (странно, почему люди так стесняются одобрительных отзывов?) Ни одного письма, вопроса (по существу), правки (наверняка ошибки есть), замечания, дополнения, интересной ссылки… ни одного! Я привлёк людей (казалось бы из целевой аудитории), но не получил никакой пользы, никакой пользы не получил и материал, никакой пользы не получили и будущие читатели. Вывод — размещение ссылок (даже в подходящих местах) даёт очень некачественную аудиторию.
Эта аудитория не имеет большой ценности и для тех, кто крутит баннеры (я не кручу). Средний посетитель моего сайта просматривает 7-8 страниц. Почти все, кто пришёл с хабра, посмотрели только одну тсраницу! Наплыв продолжался всего несколько часов и в тот день хосты подскочили, а хиты даже упали (строго говоря, просто остались в рамках обычных флуктуаций).
Конечно, мой опыт не будет интересен торговцам просроченной виагрой, но кому-то, возможно, он пригодится и даст почву для размышлений и поиска вариантов.
Каждый вызов функции — это работа со стеком. Но вы правы — неявная, и вы её не видете. Именно неявность гарантирует, что pop-ов будет солько же, сколько push-ей, и всё будет вовремя и хорошо. А явная работа со стеком — это жуткое болото. Ещё написать такое можно, но вот поддерживать, развивать… не дай бог. Поэтому закладывать сразу стековы дизайн можно только если вы (а) пишите что-то очень маленькое на один день, (б) для вас очень важно быстродействие (обычно стек быстрее) или (ц) вы просто самоубийца :-)
Не верю. Польскую нотацию нельзя разобрать регекспом.
Она относится к контекстно свободным грамматикам и для разобра требует бесконечное (в общем случае) количество состояний. А регексп определеяет конечный(!) автомат. То есть машину с конечным количеством состояний. Регекспом можно ограничться только если ограничить количество волженных конструкций; но уже при глубине 3 регексп становится нечеловеческим.
Так-что, вы либо что-то путаете, либо вы на втором курсе рассматривали очень упрощённый и ограниченный случай.
Расскажите про два стека!
Только мне кажется, что я знаю про что вы ,-)
И я вам сразу хочу напомнить, что автор поста обходится одним стеком (для хранения локальных переменных) и его подход позволяет не следить за стеком вручную — следит язык. Мне очень интересно посмотреть, как вы будете отлаживаться, вылавливать ошибки, тестировать… как от малейшей оплошности вашу аж двустековую машину будет развозить в разные стороны…
Кроме того, метод, про который тут рассказано — это классика (реалиация странновата, правда; всё было бы проще и стройнее, если бы операции хранились бы не в виде сточек, а в виде объектов, но это уже частности и детали).
Я против велосипедов, но я за такие пуликации. Слава тем, кто пишет быстро, используя уже готовые библиотеки; но дважды слава тем, то знает, как эти библиотеки устроены, какие алгоритмы используют.
Недостаток статьи — очень много кода. Было бы полезней привести пример разбора выражений только с двумя операциями (скажем, сложение и умножение). И понять было бы проще и расширить проще.
Ну и надо было всё называть своими именами. Автор, как я понял, использует метод рекурсивного спуска.
Они смотрят шире:
— google вам предоставят средства (их очень много!),
— вы делаете сайты
— размещаете на них рекламу
— реклама крутится — все довольны :-)
Конечно, вы можете разместить рекламу бегуна… но… google, видимо, исходит из того, что скоро выбора у вас не останется :-/
Обязательно продолжайте! Жду двух вещей:
= Хотелось бы оценить синтаксис с высоты птичьего полёта.
= Приведите какие-нибудь выразительные примеры (компактные, но понятные и демонстрирующие плюсы языка). Скажем можно ли на Erlang легко отсортировать массив данных, который хранится на двух машинах и не может поместиться на одной? А если два заменить на 100? ,-) Было бы очень интересно!
Спасибо, очень интересно.
Я знал ребят, которые знаимались такими вещами, они широко использовали словарь Лебедева scon155.phys.msu.su/eng/lebedev.html, там есть файл с правилами образования совоформ russian.aff, может быть он и вам пригодится.
Мне кажется, что в разделе «Архитектура» надо было хотя бы вскользь упамянуть о том, что питон имеет LL(1) парсер (вернее, грамматика питон всё же чуть сложнее, чем LL(1), но не значительно). Это позволяет сделать время компилляции практически пропорциональным длине программы. У большинства языков это не так. И это очень большой плюс питона и свидетельство его изачально отличного дизайна.
wiki.python.org/moin/LanguageParsing
Меня в своё время так же потряс google. Пару лет назад они забанили мою домашнюю страничку. Я им написал, вообще не надеясь, что они обратят внимание на моё письмо. А они не только отбанили, но и вежливо ответили. И тоже в какие-то очень сжатые сроки. Я тогда просто офигел )
И всё же… я вам очень советую не читать мои комменты, не читать мои странички,… а почитать хорошие книжки; можно начать с этой ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf (есть более новая версия этой книги, но я что-то не смог её нагуглить). Я вижу, как вам нравится эта тема. Поверьте! Чтение этой (и других) книжки доставит вам на много больше удовольствия, чем попытки меня в чём-то убедить! Удачи!
(она была опубликована в журнале «системный администратор», а автор сайта видимо просто её стырил; ну Бог ему судья)
странно запостилось — пропали все тире и кавычки :-/
но, вроде, и так всё понятно.
Вы просили меня прокомментировать с удовольствием.
Во-первых, спасибо за статью! Она лучше многих, я действительно так думаю, хотя вещи, которые я сейчас напишу могут вам не понравиться :-)
К делу.
Прежде всего, я бы советовал вам, почитать что-нибудь про грамматики. Тогда вместо наивных фраз любое сложно выражение (кстати, опечатка), вы могли бы написать грамматика класса LL(1) или что-то в этом духе. Когда вы говорите о разборе выражения, уместно классифицировать его грамматику, иначе звучит диковато и безграмотно (есть выражения, за разбор которых вы получите большие премии от видных математических обществ. есть выражения, которые невозможно разобрать и это доказано).
Далее. Зачем два стека? Вы же точно знаете, как чередуются операции и операнды! Чтобы соблюсти это чередование вы даже добавляете 0 к унарным операциям. Всё можно было бы положить в один стек.
О работе работе со стеком. Ваш алгоритм заставляет вас работать не только с верхушкой стека. Это дополнительное усложнение и источник ошибок. (Кстати, судя по обсуждению, вы не смогли избежать ошибок. А я вас предупреждал об это ещё до публикации этого поста. Работа со стеком требует большой аккуратности)
А теперь вспомним как работает алгоритм рекурсивного спуска. Вспомним, что локальные переменные хранятся в стеке. И что мы видим? Тот же стек, но! 1) он один 2) алгоритм не требует (и даже не позволяет) заглядывать под вершину стека 3) нет никаких проблем с унарными операторами и более сложными грамматиками 4) и самое главное нет необходимости работать со стеком руками! ошибки просто невозможны.
Мне кажется, вы здесь сформулировали тот же алгоритм рекурсивного спуска но, развернули рекурсию и написали работу со стеком вручную, разделили стек на два (видимо интуитивно, вы отделили терминальные токены в один стек, а не-терминальные в другой, но в этом нет никакой необходимости) и добавили костыли в виде переформулирования унарных операций, чтобы сделать разбираемый случай ещё более частным.
Если бы вы использовали рекурсивный спуск, вы застраховались бы от многих ошибок и получили бы универсальный парсер, в который можно было бы легко встроить, скажем, функции или операции с тремя операндами (типа А?B:C). В ваш теперешний парсер встроить такие возможности очень сложно (можно ли вообще). И править его очень опасно, так как тронув стек в одном месте, надо отследить, чтобы всё не посыпалось в другом.
Одним словом, ваш алгоритм я бы не стал использовать сам и не стал бы советовать другим.
1) Я никогда не оптимизировал сайт, но он по многим запросам попадает на первую страницу выдачи гугла. Примеры: спросите у google «perl vs python», «qemu и Windows», «загрузочный CD Grub», «примеры использования рекурсии», «применение фракталов», «парадокс близнецов», «гиперкуб»… это запросы, по котором приходили люди за последние несколько минут. Вывод — и без оптимизации можно привлечь много читателей.
2) Я очень ценю читателей, я ежедневно получаю письма с замечаниями, исправлениями, вопросами, ответы на которые превращаются в новые материалы… Иногда мне очень хочется поделиться с людьми какой-нибудь свежей мыслью и тогда я даю где-нибудь ссылку. Последний раз я прибег к хабру (просто карма была и мысли были; думал, что людям будет интересно и надеялся на конструктивный фидбэк). И что же я получил? Несколько невнятных комментариев в блоге. Несколько одобрительных отзывов в привате (странно, почему люди так стесняются одобрительных отзывов?) Ни одного письма, вопроса (по существу), правки (наверняка ошибки есть), замечания, дополнения, интересной ссылки… ни одного! Я привлёк людей (казалось бы из целевой аудитории), но не получил никакой пользы, никакой пользы не получил и материал, никакой пользы не получили и будущие читатели. Вывод — размещение ссылок (даже в подходящих местах) даёт очень некачественную аудиторию.
Эта аудитория не имеет большой ценности и для тех, кто крутит баннеры (я не кручу). Средний посетитель моего сайта просматривает 7-8 страниц. Почти все, кто пришёл с хабра, посмотрели только одну тсраницу! Наплыв продолжался всего несколько часов и в тот день хосты подскочили, а хиты даже упали (строго говоря, просто остались в рамках обычных флуктуаций).
Конечно, мой опыт не будет интересен торговцам просроченной виагрой, но кому-то, возможно, он пригодится и даст почву для размышлений и поиска вариантов.
Она относится к контекстно свободным грамматикам и для разобра требует бесконечное (в общем случае) количество состояний. А регексп определеяет конечный(!) автомат. То есть машину с конечным количеством состояний. Регекспом можно ограничться только если ограничить количество волженных конструкций; но уже при глубине 3 регексп становится нечеловеческим.
Так-что, вы либо что-то путаете, либо вы на втором курсе рассматривали очень упрощённый и ограниченный случай.
Только мне кажется, что я знаю про что вы ,-)
И я вам сразу хочу напомнить, что автор поста обходится одним стеком (для хранения локальных переменных) и его подход позволяет не следить за стеком вручную — следит язык. Мне очень интересно посмотреть, как вы будете отлаживаться, вылавливать ошибки, тестировать… как от малейшей оплошности вашу аж двустековую машину будет развозить в разные стороны…
Кроме того, метод, про который тут рассказано — это классика (реалиация странновата, правда; всё было бы проще и стройнее, если бы операции хранились бы не в виде сточек, а в виде объектов, но это уже частности и детали).
Недостаток статьи — очень много кода. Было бы полезней привести пример разбора выражений только с двумя операциями (скажем, сложение и умножение). И понять было бы проще и расширить проще.
Ну и надо было всё называть своими именами. Автор, как я понял, использует метод рекурсивного спуска.
— google вам предоставят средства (их очень много!),
— вы делаете сайты
— размещаете на них рекламу
— реклама крутится — все довольны :-)
Конечно, вы можете разместить рекламу бегуна… но… google, видимо, исходит из того, что скоро выбора у вас не останется :-/
= Хотелось бы оценить синтаксис с высоты птичьего полёта.
= Приведите какие-нибудь выразительные примеры (компактные, но понятные и демонстрирующие плюсы языка). Скажем можно ли на Erlang легко отсортировать массив данных, который хранится на двух машинах и не может поместиться на одной? А если два заменить на 100? ,-) Было бы очень интересно!
Может быть имеет смысл создать отдельный блог «Google API»? Все посты на эту тему очень интересны.
Я знал ребят, которые знаимались такими вещами, они широко использовали словарь Лебедева scon155.phys.msu.su/eng/lebedev.html, там есть файл с правилами образования совоформ russian.aff, может быть он и вам пригодится.
wiki.python.org/moin/LanguageParsing