После того, как я собрал все части генератора PEG-парсеров воедино в предыдущем посте, я готов показать как реализовать и некоторые другие интересные штуки.
Содержание серии статей о PEG-парсере в Python
Мы рассмотрим следующие фичи PEG:
Рубрика «алгоритм» - 3
Реализация остальных возможностей PEG
2019-11-01 в 19:56, admin, рубрики: packrat parsers, peg, pgen, python, алгоритм, Алгоритмы, ПрограммированиеЛеворекурсивные PEG грамматики
2019-10-26 в 4:14, admin, рубрики: packrat parsers, peg, pgen, python, алгоритм, Алгоритмы, ПрограммированиеЯ упоминал о левой рекурсии как о камне преткновения несколько раз, и пришло время разобраться с этим. Основная проблема заключается в том, что парсер с лево-рекурсивным спуском мгновенно падает из-за переполнения стека.
Содержание серии статей о PEG-парсере в Python
- PEG парсеры
- Реализация PEG парсера
- Генерация PEG парсера
- Визуализация работы PEG парсера
- Леворекурсивные PEG грамматики
- Добавление экшенов в грамматику PEG
- Реализация остальных возможностей PEG
- PEG на Core Developer Sprint
Рассмотрим это гипотетическое правило грамматики:
expr: expr '+' term | termРеализация PEG парсера
2019-10-19 в 19:08, admin, рубрики: packrat parsers, peg, pgen, python, алгоритм, Алгоритмы, ПрограммированиеВдохновленный лишь частичным пониманием PEG, я решил попробовать его реализовать. Результат может получиться и не самым лучшим среди парсеров PEG общего назначения — их уже много (например, TatSu написан на Python и генерирует код Python) — но это хороший способ разобраться в PEG. В дальнейшем я хочу заменить им текущую реализацию парсера в CPython.
Содержание серии статей о PEG-парсере в Python
- PEG парсеры
- Реализация PEG парсера
- Генерация PEG парсера
- Визуализация работы PEG парсера
- Леворекурсивные PEG грамматики
- Добавление экшенов в грамматику PEG
- Реализация остальных возможностей PEG
- PEG на Core Developer Sprint
В этом разделе я закладываю основы для понимания работы парсера, на примере простой самописной реализации игрушечной грамматики из прошлой статьи.
PEG парсеры
2019-10-17 в 6:36, admin, рубрики: packrat parsers, peg, pgen, python, алгоритм, Алгоритмы, ПрограммированиеНесколько лет назад меня кто-то спросил имеет ли смысл превести Python на PEG-парсер (или на грамматику PEG; я не помню точно кто и когда это было). Тогда я немного посмотрел на него, но так и не пришёл к какому-либо выводу, а потому и отбросил эту тему. Недавно я узнал больше о PEG (Parsing Expression Grammars, грамматике по парсингу выражений), и теперь я думаю, что это интересная альтернатива самописному генератору парсеров, который был разработан 30 лет назад, когда только начинал работать над Python. Я назвал его «pgen», и это был, наверно, первым фрагментом кода, который я написал для Python.
Содержание серии статей о PEG-парсере в Python
- PEG парсеры
- Реализация PEG парсера
- Генерация PEG парсера
- Визуализация работы PEG парсера
- Леворекурсивные PEG грамматики
- Добавление экшенов в грамматику PEG
- Реализация остальных возможностей PEG
- PEG на Core Developer Sprint
Причина, по которой я сейчас заинтересован в парсере PEG, заключается в том, что меня несколько раздражают ограничения pgen. Он построен на собственной реализации LL(1), которая имеет ряд допущений. Например, мне не нравились грамматические правила, которые могли бы генерировать пустые строки, поэтому я запретил их. И тем самым упростил алгоритм для создания таблиц синтаксического анализа. Я также изобрёл свою собственную EBNF-подобную грамматическую нотацию, которая мне до сих пор очень нравится.
Криптографический алгоритм «Кузнечик»: просто о сложном
2019-07-06 в 11:03, admin, рубрики: java, алгоритм, Алгоритмы, гост, криптография, Кузнечик, просто о сложномВ данной статье будет подробно рассмотрен алгоритм блочного шифрования, определенный в ГОСТ Р 34.12-2015 как «Кузнечик». На чем он основывается, какова математика блочных криптоалгоритмов, а так же как реализуется данный алгоритм в java.
Кто, как, когда и зачем разработал данный алгоритм останется за рамками статьи, так как в данном случае нас это мало интересует, разве что:
КУЗНЕЧИК = КУЗнецов, НЕЧаев И Компания.
Так как криптография в первую очередь основана на математике, то чтобы дальнейшее объяснение не вызвало уймы вопросов сначала стоит разобрать базовые понятия и математические функции, на которых строится данный алгоритм.
Читать полностью »
Система генерации ландшафта лабиринта с улучшенным визуальным реализмом [перевод статьи Jinmo Kim]
2019-06-11 в 15:27, admin, рубрики: 3d, AR и VR, алгоритм, Алгоритмы, генерация ландшафта, Дизайн игр, Лабиринт, ландшафт, перевод статьи, Программирование, разработка алгоритмов, разработка игрПривет!
В этой публикации я расскажу о статье автора Jinmo Kim: "Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism". Она была опубликована 4.04.2019. Полный текст статьи можно посмотреть здесь.
Краткое описание системы
В статье предложена авторская система создания лабиринтных ландшафтов, с помощью которой пользователь может автоматически генерировать различные сложные узоры в простой и интуитивно понятной системе. С помощью информации о лабиринте, рассчитанной в программе, быстро и эффективно генерируется трехмерный ландшафт лабиринта.
Предложенная система генерации ландшафта лабиринта состоит из трех основных функций:
- функция автоматической генерации сетки лабиринта различных размеров и узоров, реализованная с помощью классического алгоритма генерации лабиринта;
- функция генерации кругового лабиринта;
- функция преобразования лабиринта из ручного эскиза в 3D объект с помощью алгоритма обработки изображений.
С помощью предложенной системы, состоящей из этих трех функций, можно эффективно создавать различные лабиринты, от однородных до нерегулярных. Эта разработка позволит генерировать лабиринтные ландшафты различных концепций напрямую из расчетов, сделанных через эту же систему. Кроме того, в этой работе проведен анализ улучшения эффекта присутствия и погружения в виртуальную реальность, т.е. визуального реализма. Также, в этой работе был проведен анализ пригодности предложенной авторской системы с помощью опроса.
ARA: алгоритм для нахождения максимального числа точек на прямой линии
2019-06-01 в 0:49, admin, рубрики: complexity, python, алгоритм, Алгоритмы, математика, собеседованиеНедавно мне попалась классическая задачка для собеседований: поиск максимального числа точек, стоящих на прямой линии (на плоскости, координаты целочисленные). В голову сразу пришла идея полного перебора, которая имеет очевидную сложность по времени в O(n^2), но мне показалось, что здесь обязано быть что-то ещё, хоть какая-то альтернатива в O(n*log(n)). Через полчаса нашлось даже нечто лучшее!
Как Amazon выбирает свои, казалось бы, случайные предложения дня. И почему за ними так гонятся продавцы
2019-04-22 в 8:17, admin, рубрики: amazon, pochtoy, алгоритм, Блог компании Pochtoy.com, интернет-магазин, интернет-маркетинг, покупки, продажи, ритейл, скидки, США, Управление e-commerce
Amazon захватила 50% интернет-рынка в Америке. В прошлом году за пятинедельный период со Дня благодарения (22 ноября в США) 89% расходов клиентов крупнейших торговых площадок в Штатах пришлось на этот один интернет-магазин. За 2017-й год акции компании совершили ралли на 55%, в 2018-м – еще на 30%. Причина простая: у компании лучшая инфраструктура, плюс она знает, что давать покупателям. Независимые продажники, третьи лица, обеспечивают до 70% покупок на сайте. И компании нужно знать, какие из них выдавать в поисковой выдаче, и на какие устраивать скидки.
Из сотен миллионов товаров, размещенных на площадке, каждый день компания отбирает всего пару тысяч. Какими параметрами при этом руководствуется компания, чтобы обеспечить максимальные продажи? Как выбирает этот 0,1% подходящих вещей? Или берет товары наугад, рискуя разочаровать покупателей?Читать полностью »
Эволюция программного проекта и ООП
2019-04-14 в 10:27, admin, рубрики: абстракция, алгоритм, Анализ и проектирование систем, инкапсуляция, наследование, ооп, полиморфизм, Программирование, Проектирование и рефакторинг, эволюцияОсваивая рецепты эффективного развития программного проекта, постарался для себя найти причины, делающие полезным использование принципов развития архитектуры SOLID (статья Как не понимать принципы развития архитектуры SOLID).
Анализ этих принципов позволил выделить несколько ключевых закономерностей и базовых элементов, существующих в разработке. Они позволили описать, понять и внедрить SOLID в реальной работе с программным проектом.
Стало интересно выполнить анализ применимости этих понятий для общепринятых парадигм программирования, например для ООП. Хорошо, если результат этой работы будет полезен и Вам.
Как устроен штрихкод?
2019-02-08 в 22:18, admin, рубрики: python, алгоритм, Алгоритмы, баркод, инженерные системы, Научно-популярное, обработка изображений, Программирование, штрихкодПривет!
Со штрихкодами современный человек сталкивается каждый день, даже не задумываясь об этом. Когда мы покупаем в супермаркете продукты, их коды считываются именно с помощью штрихкода. Также посылки, товары на складах, и прочее и прочее. Однако, мало кто знает, как же реально это работает.
Как устроен баркод, и что закодировано на этой картинке?
Попробуем разобраться, заодно напишем декодер таких кодов.Читать полностью »