Что почитать по дизайну AST для редакторов / подсветки синтаксиса

Эх, жаль что ты не на лиспе. Я как раз решал подобную задачу для своего языка программирования и дело вплотную подошло к очередному переписыванию «по-взрослому». Посему:

1. Присоединяюсь к вопросу.

2. Я эту задачу частично решил, и понял, что решил не совсем правильно.

3. То ли эта задача очень сложная, то ли я стал стар.

4. Я разбил парсер на 3 слоя:

-- лексер -- обработчик парных скобок -- парсер

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

Я пользуюсь tk text, там ты устанавливаешь приоритет между разными тегами, назначаемыми кускам текста и эти слои раскраски сами между собой выясняют отношения согласно приоритету. На теги же назначаются и действия. Т.е. в целом это похоже на сведение картинки. Первым делом лексер красит своим цветом. Потом обработчик скобок красит своим (например, непарные скобки можно красным покрасить). ПОтом парсер красит своим. Это три отдельных процесса. Если сделать по-иному, будет слишком сложно.

5. Попробуй набить текст хотя бы в окне ответа этого форума и посмотри, как браузер будет подчёркивать слова с ошибками при редактировании текста. Ты увидишь, что если ты начинаешь печатать текст с середины слова, браузер не проверяет правильность. Он проверяет её, когда ты выходишь за границу слова. Ошибка в моём текущем алгоритме состоит в том, что я на каждое нажатие пытаюсь проверять и, естественно, почти всегда имею ошибку разбора. Кроме того, пока ты нажимаешь только литеры и backspace (и не двигаешь курсор), умная программа может понять, что пользователь вводит текст и не перекрашивать ничего справа от курсора. Так трудоёмкость (инкрементного) парсинга сокращается на порядки. После того, как двинул курсор, можно красить до конца.

Без распознавания таких шаблонов в действиях пользователя у тебя вряд ли получится что-то хорошее.

6. Для инкрементного парсера пришлось реализовать механизм, подобный continuations, причём с возможностью повторного запуска одного и того же continuation. ПРавда, реализация оказалась медленной и пока что она выпилена, но в будущем мы к ней обязательно вернёмся.

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

8. Я бы смотрел исходники развитых сред разработки, которые могут всё, что тебе нужно. Я отталкивался изначально от hemlock (клона emacs), возможно, тебе подойдёт какой-нибудь атом или что там модно в вашем мире.

9. Вопрос о добавлении ``` не имеет хорошего решения. В любом случае будет смаргивать. Обходной путь - добавлять ``` только парами. Например, notepad++ при вводе открывающей скобки сам добавляет закрывающую, то же для кавычек.

10. Даже инкрементный разбор занимает время. Если за это время пользователь успеет нажать ещё кнопку, понадобится новый разбор. Таким образом, тебе нужна последовательность выполнений разбора, а также механизм отмены устаревшего разбора. При этом разбор должен быть достаточно часто опрашивать свой статус, чтобы отмена происходила быстро. Впрочем, в моём случае это плохо помогает, поскольку у меня что-то плохо со сборкой мусора и всё начинает лагать в любом случае. Но это уже из другой оперы :)

Я реализовал не все из этих пунктов - скорее это работа над ошибками.

Где-то в моих темах был ещё коммент от товарища, к-рый писал свою CAE систему.

http://texteditors.org/

Проблемы знакомые :) . У меня есть пара комментариев. В задачах как правило на первом месте стоит дизайн данных, и только потом функции. Типа, если данные запроектированы правильно (позволяют реализовать все что нужно), то код скорее всего плохо сделать уже не выйдет.

Поэтому я бы из твоего описания пока выпилил все что касается имплементации парсера, и оставил только описание AST с обоснованием почему нужны именно такие структуры. В конечном счете именно AST является внешним интерфейсом, с которым все работают.

Спасибо

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

С самими данными особой проблемы нет - для этого достаточно знать структуру исходного текста.

Ну не скажи. Я в первом посте дал ссылку на реп с тикетами, где записаны неочевидные моменты. Например как хранить параграф из нескольких строк внутри цитаты. Чтобы это было потом реально обработать.

Там с одной стороны одна «строка» по маркдауну, но физически их несколько и у каждой свой отступ. Если все пихать в одну строку, то непонятно куда отступы засунуть, чтобы не сбились при трансформах. Если бить на сиблинги, то потом усрешься выписывать операции над текстом (например поиск), который между сиблингами побился.

Мне было бы интересно узнать о подходах к решению подобных проблем. Думаю, они не специфичны исключительно для маркдауна. Я вовсе не говорю что ты про парсер написал ненужные вещи, просто IMHO есть вещи еще более значимые.

У меня есть отдельная лексема «кн.» (конец строки) и отдельная лексема «отступ». Я слегка наврал про три этапа, их на самом деле 4, но первые два плотно сплетены. Лексемы конец строки и отступ доживают до парсера. Лексемы «белое поле» и «комментарий» на первом этапе (лексер) существуют как отдельные. Далее на этапе пост-лексера они засовываются в соседнюю (следующую или предыдущую - не помню) «содержательную» лексему. Правда, в маркдауне вроде нет белого поля, но смысл примерно такой же:

сначала у тебя есть базисные лексемы, например «конец строки», «отступ» и «содержимое строки после отступа». Затем на этапе пост-лексера ты строишь из них следующую лексему, у которой есть под-лексемы.

Аналогично с символами. Символ - это совокупность из квалификатора пр-ва имён и собственно идентификатора. Оба читаются по правилам идентификатора и оба могут вызвать ошибку разбора. СОответственно, по символу «а::б» строим сначала три лексемы классов Кля-простой-символ Кля-отделитель-пространства-имён и Кля-простой-символ, потом собираем одну «мегалексему» класса Кля-символ.

Т.е. получается дерево уже на этапе лекс.разбора, а не «классическая» схема «лексер-парсер».

У меня выглядит это примерно так:

;; Пб -это запись "прочитанная буква", содержит букву и информацию о том, из какого файла и в какой позиции эта буква пришла. 
;; Допустимый-класс-лексемы - это перечисление, примеро такое:
;;

(defstruct Лексема 
  ($Текст nil #|(make-string 0)|# :type (nullable string)) ; FIXME потом убрать null, а может быть, текст и не для всех нужен. 
  (Класс nil :type (nullable Допустимый-класс-лексемы)) ; см. П-Я-ЛЕКСЕР::*Классы-лексем*
  ($Начало nil :type (nullable Пб)) 
  ($Конец nil :type (nullable Пб)) 
  (Заготовка nil :type (nullable Заготовка-строки)) 
  Сод  ; Содержимое - некая запись, тип к-рой зависит от класса лексемы, см. файл содержимое-лексем.lisp
  (Белое-поле-до nil :type k:list) ; Если есть, то печатаем.
  ;; если Статус 
  (Статус 'Собирается :type Статус-лексемы)
  Ошибка ; сведения об ошибке (datum &rest arguments)
  (Лексемы nil :type k:list) ; для составной лексемы - лексемы, из к-рых она состоит, необязательно все - часть может быть в поле Сод
  ;; Поля Отступ-подлежит-контролю и Входит-в меняются в группировщике, что противоречит нашей идее о немутабельности лексем задним числом.
  Отступ-подлежит-контролю ; истина для первой не-пробельной лексемы в строке
  (Вышестоящие nil :type (nullable k-cons-of--Вхождение-лексемы-в-группу))
  )

;;; Записи, конкретизирующие содержимое лексем
(defstruct Сод-Строковый-литерал
  (Вид nil :type (nullable Вид-строкового-литерала))
  (Открывающая-последовательность nil :type k:list) ; открывающий разделитель в прямом порядке
  (Приставка nil :type k:list) ; только для строки с отступом - хвост строки с открывающим разделителем
  (Закрывающая-последовательность nil :type k:list)
  )

(defstruct Сод-Простой-символ
  ;; класс операции, выводимый исключительно из текста лексемы
  (Коя-пс nil :type (nullable Допустимый-класс-операции))
  (Закавыченный nil) ; если истина, то указывает на разновидность закавычивания - пока просто проверяем, закавыченный ли
  Строка-имени ; имя как строка, подобно (string symbol)
  Каноническая-строка-имени ; если символ требует закавычивания, то закавыченная, иначе - то же, что Строка-имени. Хороша тем, что можно именовать лексиконы и библиотеки, складывая канонические строки сегментов имени
  )

(defmethod cl:make-load-form ((Э Сод-Простой-символ) &optional env)
  (make-load-form-saving-slots Э :environment env))
 
(defstruct Сод-Символ
  ;; Поля типа k:list - это списки лексем
  (Квал-библ nil :type k:list) ; квалификатор библиотеки
  (Квал-лексикона nil :type k:list) ; квалификатор лексикона
  (Отделитель-имени nil :type (nullable Лексема)) ; точка между лексиконом и символом.
  (Имя nil :type (nullable Лексема)) ; класса Кля-простой-символ
  ;; класс операции, выводимый исключительно из текста лексемы, с учётом того, что
  ;; лексема может быть внутри псимв и из-за этого превратиться в простой символ без всякого Коя
  ;; см. Коя-сохраняется-внутри-псимв
  (Коя-с nil :type (nullable Допустимый-класс-операции))
  Символ-Яра
  )

(defstruct Сод-иерархическая-группа
  "Также для элемента группы. Например, для лексемы класса Кля-элемент-списка-через-запятую - это запятые и/или скобки"
  (Открывающее-слово nil :type (nullable Лексема))
  ;; Поля принадлежности определяют, в какой лексеме будет печататься это слово. По традиции, открывающее слово принадлежит самой внешней группе, а закрывающее - самой внутренней (т.е., в обоих случаях, хронологически первой группе, которая встретила это слово в процессе разбора).
  Откр-слово-принадлежит-ли
  (Закрывающее-слово nil :type (nullable Лексема))
  Закр-слово-принадлежит-ли)

(defstruct Сод-кн*
  (Буква nil :type (nullable character)))

Если бить на сиблинги, то потом усрешься выписывать операции над текстом (например поиск), который между сиблингами побился.

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

Ты можешь заметить там замечания про немутабельность - с ней отдельно можно усраться, особенно если учесть инкрементный парсинг и возможность ошибки в любом месте. Я на это забил и собираюсь воспользоваться «атомной бомбой», т.е. чем-то типа многоверсионной базы данных. Прототип такой базы уже вполне готов год тому назад. Т,е. у меня почти везде дерево строится так, что лексема «запечатывается» и с какого-то момента становится немутабельной, но из этого правила есть исключения.

Я надеюсь, что удастся разогнать неинкрементную раскраску, чтобы она тянула файлы строк до 500, а дальше или ишак, или эмир, или я.

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

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

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

Некоторые задачи таким образом можно сделать легче.

А можно где-то посмотреть список типовых задач?

У меня такие задачи актуальны:

• раскраска - для неё не нужно ходить по дереву, она появляется побочным эффектом лексера/парсера
• автодополнение слов - ещё не делал, сказать не могу. Но если это идентификатор, то от него нужен в моём случае не просто текст
• печать лексем для отладки. Здесь текст в полный рост
• анпарсер - текст в полный рост
• поиск - пока не делал, но тут либо текст, либо ходить по структуруам
• трансляция в другой язык - здесь от текста есть кое-какая польза, но в целом рекурсивное хождение по структурам неизбежно
• действия по щелчку на имени, например, переход к определению - для этого полюбасу нужен отдельный парсер окрестностей текущего положения курсора, т.к. в ЯП имя может встречаться и в комментарии, и внутри строкового литерала. Впрочем, это зависит от языка
• отображение «дерева структуры» - это, по-моему, самое страшное, потому что это дерево не должно моргать, когда текст временно становится невалидным. ЕМНИП эта задача толком не решена в Visual Studio для С++, т.е. дерево очень медленно обновляется. Видимо, нужно ещё искать - может быть, где-то сделано нормально,и взять идеи оттуда. Пока что я на практике пользуюсь кнопкой, которая в отдельное окно выдаёт мне список определений, т.е. в ручном режиме обновляю дерево.
• фолдинг-анфолдинг - мне он не нравится и делать его я не собираюсь
• переход/подсветка парных скобок, переход на лексему вперёд/назад
• показ места ошибки разбора

Моё имхо после нескольких подходов к этой задаче - главное - это попытаться разбить на как можно более мелкие части. Я с этой задачей не справился, но «почти» справился. Связи между слоями возникают в самый последний момент, когда вдруг оказывается, что что-то недоучёл. Я сделал сколько-то рефакторингов, но всё равно в чистом виде модульности добиться не удалось. Однако количество связей между слоями у меня более-менее обозримо и в целом я, как мне кажется, контролирую ситуацию.

Но ты сам видишь - даже список того, что должна уметь среда разработки, весьма внушительный.

в «книге четырех» паттерны разюирают на примере проектирования текстового редактора, в т.ч. касаются вопрсов проектирования структуры хранения форматированного текста - конечно это все не то но если не читал возможно будет полезным

Помню что-то такое. Но там суть перемежалась таким диким количеством кода, что поленился вникать. Мне показалось, что там все-таки был упор на разбор паттернов, а не на полноту покрытия юз-кейзов реального редактора.

Спасибо за примеры.

Да, забыл упомянуть анпарсер как очевидное. Когда я упоминаю AST, то подразумеваю что интересует полное, без потерь информации (с трансформациями в обе стороны). Более простые варианты уже есть.

Да, полная архитектура там не рассматривалась, упор делался на идеи (они же паттерны)

Если нужны фундаментальные знания, то я думаю можно посмотреть «книгу дракона» «Компиляторы: принципы, технологии и инструменты». 80% от нее тебе будут не нужны, но там в первых главах очень подробно разбирается разбиение текста на лексемы, грамматический разбор и т.д. Многовато «матана». Но думаю, первые 4 главы почитать можно.

Есть куча примеров на сишном коде. Может появятся мысли как удобнее хранить аст.