Введение, или зачем нужны синтаксические анализаторы

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

Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.

В недавно вышедшей Visual Studio 11 Beta встроена новая и главная фишка будущего C# 5 — асинхронное программирование с помощью async/await. Про нее уже написано достаточно много статей в том, числе на хабре — например, эта серия статей. Однако, я для себя так и не понял в чем суть нового синтаксиса, пока сам не попробовал его в деле. Данная статья — попытка самому структурировать и до конца разобраться с этим достаточно интересным инструментом и поделиться результатами с сообществом, рассказав про него немного иначе. Итак, поехали…

В продолжение темы расширения функциональности готовых программ хотелось бы рассказать об ещё одном способе изменения логики работы уже скомпилированной программы, который не требует делать изменений в самом исполняемом файле. Это может пригодиться при распространении вашей модификации в США, где прямое вмешательство в исполняемый файл строго осуждается. Речь пойдёт о создании крошечной прокси-dll (всего ≈4 килобайта) для подмены используемой приложением библиотеки на примере ddraw.dll.

Roslyn Services API позволяют легко реализовывать расширения, которые находят и устраняют проблемы в коде прямо в Visual Studio. Roslyn Services API доступно как часть Roslyn CTP.

В этом посте мы реализуем расширение для Visual Studio, которое детектирует вызовы метода Count() у Enumerable, после чего результат проверяется на равенство больше нуля, например, someSequence.Count() > 0. Проблема, заключающаяся в коде, в том, что Count() должен пройтись по всей последовательности, прежде чем вернуть результат. Более правильным подходом в данном случае является вызов метода Enumerable.Any().

Чтобы исправить это, мы реализуем CodeIssueProvider, детектирующий проблему, и CodeAction, который заменяет условие на вызов Enumerable.Any(), как и требуется. Т.е. наш CodeAction изменит что-то типа someSequence.Count() > 0 на someSequence.Any().

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

Нечеткая логика — математические основы
Нечёткое множество

Описание метода
Пусть имеется множество элементов U, а A – его нечеткое подмножество, степень принадлежности его элементов определяется значением X, принимающим значение из интервала [0;1].
Таким образом, объект можно описать набором критериев(параметров) X(1), X(2) … X(n), принадлежащих соответствующим базовым множествам U(1), U(2) … U(n). Совокупность критериев с соответствующими значениями характеризует приемлимость S данного объекта относительно поставленной задачи.

И опять, привет хабравчанам!

Буквально несколько дней назад — начал цикл статей, о том, как можно создавать крутые игры с помощью XNA Framework, своей студии у меня нет, поэтому ограничимся только 2D играми.

На этот раз — мы более подробно рассмотрим Draw и напишем свою первую систему частиц.

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

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

Иллюстраций: 34, символов: 51 609.

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Однажды вечером, сразу после того, как я закончил разбираться с наследованием в JS, мне пришла в голову идея, что пора бы заняться чем-нибудь посложнее — например паттернами. На столе внезапно оказалась книжка Gof, а на экране ноутбука появился труд с названием «JavaScript patterns».

В общем, спустя пару вечеров, у меня появились описания и реализации на JavaScriptе самых основных паттернов — Decorator, Observer, Factory, Mediator, Memoization (не совсем паттерн, а скорее техника, но мне кажется что она прекрасно в этот ряд вписывается) и Singleton.

Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.

Предисловие и постановка задачи

Думаю, многие читатели этого сайта слышали о такой полезной структуре, как дерево отрезков. А если нет, то о нем в интернете можно отыскать множество интересного материала (здесь, статьи на Хабре: раз и два, google, наконец).
Здесь я разберу обобщение дерева отрезков на двумерный случай, причем (в отличие от этой статьи) рассмотрю реализацию дерева именно с поддержкой групповой модификации элементов.

Статья по следам моего доклада на концеренции User Experience`11.

Что такое HTML5?

Сегодня про HTML5 их числа тех, кто так или иначе связан с веб-разработкой, не слышал только ленивый. Вы не сильно прогадаете, предположив, что на каждой модной конференции, где есть что-то про веб, почти наверняка, звучит и что-то про HTML5. Практически каждая крупная компания, связанная с вебом, будь то Google, Apple, Microsoft, Amazon, Adobe, Oracle, Facebook, Яндекс, Mail.ru… говорит что-нибудь про HTML5, расписывается в любви на века и приверженности продвижению и развитию HTML5. Yeah! (Opera и Mozilla, безусловно, тоже в этом списке.)

Это всеобщее стремление может только радовать. Конечно, до тех пока участники рынка не начинают тянуть одеяло на себя, а садятся все вместе за стол и договариваются.

Огромные перспективы, новая волна развития веба, новое поколение веб-приложений! Круто.