skiminok: (Default)
Тут один умный человек ещё раз рассосал по косточкам свои объективные претензии к C++. Причем на этот раз я с ним в каждом слове целиком и полностью согласен. Лично я бы добавил ещё парочку пунктов, кроме изложенных, но это уже не суть важно. Читайте.

Кстати, забавно получилось с грамматикой. В комментариях изрядно удивленный народ в шоке обсуждает «как же это так, контекстно-зависимый язык, как они там вообще компилятор-то написали, какая же это каша в нем творится?» У них в голове не укладывается :) Что же, вполне справедливо.
skiminok: (!int)
Феерический пиздец, кровавый угар, содомия и червие
Не ходите, дети, в Африку гулять, по желтопрессным материалам искать, как реализованы регекспы. На козлобарана вроде этого наткнетесь.
Лучше годные книжки читайте.
P.S. Трындец капустный, его еще и в топ выводят. Моя бы воля, стопиццот минусов поставил.

UPD: «Автор переместил топик в черновики.» Вот и славно.
skiminok: (Default)
Ахо и компания — забавные ребята. Особенно забавно они описывают алгоритмы синтаксического разбора.

Читаю, значитца, главу про разные виды грамматик и соответствующие методики.
Концепт LL(1) понятен и коню.
Сквозь SLR я прошел как-то без особого напряга.
На каноническом LR(1) уже пришлось напрячься и поскрипеть мозгами. Продрался, но не могу сказать, что воспроизведу с первой попытки.
А LALR вынес меня просто в тихий омут и дал на прощание по башке канделябром.

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

Офигеть.

P.S. Нет, ребята, я таки продерусь сквозь LALR и сначала напишу свой yacc, с преферансом и артистками, а потом уже буду юзать авторитетов.
skiminok: (Default)
Хопкрофт и Фридл давно осилены. Рихтер третье издание своего "CLR via C#" подготовит только к весне. Пора браться за что-то новенькое, то есть развивать тему синтаксического разбора, языков программирования, формальных языков и автоматной теории, и всей прочей прелести, связанной с текстом. Строки — наше всё.

Три классические книги, которые я собираюсь в обязательном порядке приобрести и осилить в ближайшее время:

Известная всем и каждому «книга дракона». Давно пора было, если уж на то пошло.

А это Великий и Гениальный SICP. После того как Владимир Иванов на майкрософтовском семинаре упомянул её как обязательную книгу для прочтения, я окончательно убедился, что труд стоит своей славы.

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

Постскриптум. Знаете, чем хорош киевский карантин? Тем, что можно без проблем заказывать книги в интернет-магазинах, и не динамить из-за этого пары, ожидая дома доставки.
skiminok: (xkcd)
У меня в кои-то веки дошли руки скачать Хопкрофта в оригинале и прочесть, как же называются эти чертовы состояния, которыми дополняют ДКА до полноты и которые предполагают вечное зацикливание.

Оказывается, это dead states.

Наши русские надмозги в официальном издании перевели их как дьявольские состояния. В итоге я год честно считал, что в оригинале Хопкрофт называл их evil или devil, а посмотреть в сам оригинал было тупо лень. И теперь с моей лёгкой подачи наш преподаватель теории автоматов и языков, и весь поток вместе с ним, называет такое состояние evil.

Надмозги такие надмозги.
skiminok: (Default)
Я теперь счастливый обладатель двух культовых трудов:

   


Сезон мозголомства можно считать торжественно открытым.

А ещё в субботу я эпически зафейлил второй раунд CodeJam`a. Собственно, я ничего другого и не ожидал, но всё-таки немного обидно.
skiminok: (xkcd)
По мотивам продолжения моих разборок с предметом формальных грамматик и иже с ними.
Пусть будет отдельным постом.

Современные регекспы, начиная от перловских, описывают уже далеко не регулярные языки.
К примеру, backreferences (\1, \2 и т.д.) уже относятся, если не ошибаюсь, к контекстно-зависимым языкам.
Я уже молчу про (?R) — подстановку в точку всего шаблона в целом. И всякие там атомарные группировки.
Да, это все очень расширенные регулярные выражения, которые ни хрена не соответствуют математической теории и черта с два их реализуешь конечным автоматом. Но почти все современные движки регекспов поддерживают эти расширения.

Ну и как постскриптум. Регексп, который матчит правильное скобочное выражение на круглых скобках, выглядит, оказывается, так (пробелы для читабельности):
\( ( ( (?>[^()]+) | (?R) )* ) \)
skiminok: (Default)
Немного про L-грамматики. Это потрясающе.
(мотороллер не мой)
skiminok: (Compas)
Судя по всему, из трёх возможных подраундов первого раунда Google Code Jam я выбрал самый жёсткий. Или оно просто так исторически сложилось: раунд был как раз по временной зоне на европейскую и постсоветскую аудиторию =) По крайней мере, часть моих знакомых его успешно завалили, после чего на следующий день в 1С показали просто высший класс. Ладно, идём по порядку.

Задача А. Тупая, вся проблема задачи опять заключалась в текстовом парсинге. И опять у человека тяжёлый выбор: осуществлять ударный посимвольный разбор дерева решений, или попытаться найти способ поэлегантнее. Я, как всегда, предпочел регекспы =) Кстати говоря, я их структуру знаю не настолько хорошо, чтобы выяснить, возможно ли с их помощью описать в общем виде правильное скобочное выражение. Следуя чистой теории формальных языков — можно, наверное. В общем, как-нибудь надо будет особые возможности синтаксиса подучить поподробнее. Пока что я прекрасно обхожусь ^, $, +, *, ?, [] (с отрицанием), (), |, ., символьными классами и нумерованными группами. И хватает с головой. Тем не менее, разделение двух деревьев решений в рекурсивной функции анализа строки я писал вручную, подсчитывая баланс скобок до нуля.

Задача B. Минус в карму C# =) Идея в том, чтобы капельку заставить человека подумать головой, а потом разделить аудиторию на три естественные категории: те, кто умеет писать next_permutation(), те, кто этого делать не умеет, и те, кто его тупо вызывают из STL)) В самом деле, на С++ основная логика решения задачи выглядит следующим образом:
deque<char> f;
/* Считывание входного числа в f */
f.push_front('0');
next_permutation(f.begin(), f.end());
if (f.front() == '0') f.pop_front();

Ваш покорный слуга плюсами не пользовался в силу нелюбви и плохо набитых рук, писал получение следующей перестановки собственными силами, за что и поплатился одной неправильной попыткой сдачи смолл-теста (перепутал < и <= ). *Впрочем, особо на результат это не повлияло, и так в следующий тур спокойно прорвался.* Кстати сказать, самые быстрые цппшники сдавали эту задачу через 4 минуты после начала контеста.

Задача С. Вот это уже интересно. Это уже надо думать, по крайней мере. Если бы у меня оставалось больше, чем полчаса — мог бы таки пораскинуть мозгами и намутить тот несчастный BFS или Дейкстру на графе этого арифметически-мозголомного квадрата и решить хотя бы смолл-тест. Но не судьба.

Ну ничего, впереди раунд 2. *что-то мне подсказывает, что для меня он станет последним: пробиться из 3000 сильнейшних в 500 уже задачка уровня мега* Google Code Jam плавно вступает в свою самую хардкорную стадию) Гудлак & хевфан ;)

Profile

skiminok: (Default)
skiminok

Most Popular Tags

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526272829 30
31      

Syndicate

RSS Atom