22/10/2020, Peter Sovietov¶
Очередной выпад в сторону классического подхода к преподаванию синтаксического разбора. Простое и изящное в части содержания пособие по написанию разбора арифметических выражений. Автор красиво и плавно приводит к идее использования рекурсивного спуска совместно с парсером Пратта.
Just write the #!%/* parser https://tiarkrompf.github.io/notes/?/just-write-the-parser/
На первый взгляд эта новость не слишком подходит для PLComp, но обращает на себя внимание личность автора (Tiark Rompf — один из лучших специалистов в области DSL-компиляции) и идеологическая спорность его подхода.
Действительно ли это правильный путь — перейти в обучении сразу к нюансам низкоуровневого кодирования, оставив за бортом вопросы формальной спецификации языка, его синтаксиса? Известные примеры реальных проектов, безусловно, говорят, мол, да, так оно и происходит на практике. И даже если есть спецификация, то она остается «на бумаге» и со временем расходится с реализацией все больше и больше.
10/06/2020, Peter Sovietov¶
Автоматическое извлечение КС-грамматики на основе динамического анализа управляющего графа программы на примерах входных данных. Любопытно, что авторы не стали даже упоминать грамматическое сжатие.
Mining Input Grammars from Dynamic Control Flow https://publications.cispa.saarland/3101/1/fse2020-mimid.pdf
28/05/2020, Vladimir Kazanov¶
Синтаксический анализ программ считается давно изученной и почти даже скучной областью. Но при применении теории к практике текстовых редакторов часто выясняется, что привычные формализмы работают плохо и разработчикам приходится предлагать неординарные решения. В своей статье “SMIE: Simple Minded Indentation Engine” Стефан Монье излагает суть проблемы автоматического расставления отступов и описывает решение на базе грамматик с операторным предшествованием (operator-precedence grammars), используемое в Емаксе.
http://www-labs.iro.umontreal.ca/~monnier/smie.pdf
#editor #emacs #smie #indentation #parsing
15/05/2020¶
Необычный подход к построению PEG-подобного парсера на основе восходящего разбора. Pika parsing: parsing in reverse solves the left recursion and error recovery problems https://arxiv.org/pdf/2005.06444.pdf
14/05/2020¶
Две недавние статьи с участием Alessandro Warth. A. Warth — разработчик системы oMeta и автор известной работы по адаптации Packrat-парсеров для поддержки левосторонней рекурсии.
Incremental Packrat Parsing (оригинальная идея по использованию Pakrat-таблицы для реализации инкрементального разбора) https://dl.acm.org/doi/pdf/10.1145/3136014.3136022
Recognising and Generating Terms using Derivatives of Parsing Expression Grammars Использование производных Бржозовского в PEG-парсере для порождения предложений описываемого языка. Может использоваться в задаче тестирования компилятора (fuzzing). Но особенно интересно расширить эту идею на PEG с иерархическими структурами данных – и порождать тестовые примеры для них. https://arxiv.org/pdf/1801.10490.pdf
12/05/2020¶
О вычислительной универсальности PEG-парсеров. The computational power of Parsing Expression Grammars https://arxiv.org/pdf/1902.08272.pdf