Некоторые IDE и текстовые редакторы парсят исходный файл целиком при каждом изменении, что может тормозить на больших файлах, а некоторые делают это построчно с помощью регулярных выражений, что тоже тормозит и не даёт качественной подсветки кода, т.к. теряется контекст. Для решения этих проблем в недрах GitHub был создан tree-sitter - инкрементальный парсер, который используют всё больше и больше проектов. Давайте разбираться зачем и почему.
Введение с официального сайта гласит:
Tree-sitter это инструмент для создания парсеров и библиотека инкрементального парсинга. Он может построить синтаксическое дерево для исходного файла и эффективно обновлять синтаксическое дерево при изменении исходного файла. Tree-sitter нацелен быть:
Достаточно общим, чтобы парсить любой язык программирования.
Достаточно быстрым, чтобы парсить на каждое нажатие клавиши в текстовом редакторе.
Достаточно надёжным, чтобы выдавать пригодные результаты даже при наличии синтаксических ошибок.
Не иметь зависимостей, чтобы библиотека (написанная на чистом C) могла быть встроена в любое приложение.
Далее на примерах разберём как это влияет на работу IDE и текстовых редакторов (слайды взяты с выступления "Tree-sitter - a new parsing system for programming tools" by Max Brunsfeld).
Подсветка кода
Такие редакторы текста как TextMate, Sublime Text или Visual Studio Code используют регулярные выражения, которые применяются построчно, для подсветки кода. Это приводит к тому, что, в отличие от редакторов опирающихся на синтаксические деревья, они не могут знать контекст и подсветка оставляет желать лучшего. Да и производительностью на больших объемах строк такой подход похвастаться не может.
Но проблемы у редакторов использующих регулярные выражения возникают не только когда строк кода много, но и когда она всего одна, зато очень длинная. В этом случае такие редакторы ограничивают максимальную длину строки для подсветки, иначе парсинг регулярками занимал бы слишком много времени. Если редактор оперирует синтаксическими деревьями, то ни количество строк, ни их длина ему не помеха.
Свёртка кода
Самый простой способ найти блоки кода для свёртывания - ориентироваться на величину отступов, т.к. обычно многострочный блок кода имеет единый размер отступов на каждой строке, что приводит к путанице, когда это не так. Зная синтаксическую структуру кода, текстовый редактор может сворачивать блоки кода независимо от величины отступов.
Расширение выделения
Также знание о синтаксической структуре кода даёт нам такой мощный инструмент как расширение выделения.
Обработка ошибок
Tree-sitter устойчив к синтаксическим ошибкам в коде и достаточно умён чтобы понять какая часть кода (синтаксического дерева) лишняя. Это позволяет текстовым редакторам подсвечивать только ошибочные участки кода, а не окрашивать всё красным.
Скорость
Самая главная фишка tree-sitter - инкрементальный парсинг, т.е. при изменении кода исходный файл не будет обработан целиком - обработана будет только изменённая часть, что делает возможным запускать такой парсинг на каждое нажатие клавиш в текстовом редакторе без задержек в отклике интерфейса.
Как это работает
Tree-sitter использует GLR-парсер - обобщённый LR-парсер. GLR-алгоритм парсинга похож на LR, но приспособлен для работы с неоднозначностями.
Если кратко, то LR парсер имеет стэк и таблицу правил. Он читает токены слева-направо и сверяясь с таблицей правил преобразует стэк. Проблема возникает, если синтаксис языка допускает неоднозначности. Например, выражения ниже начинаются одинаково (x = (y)) и понять что мы в данный момент парсим можно только дойдя до ; или =>.
x = (y); // выражение в скобках
x = (y) => z; // лямбдаТут на помощь и приходит GLR-парсер. При наличии неоднозначностей он параллельно перебирает все возможные варианты не используя backtracking. Т.е. стэк распараллеливается на несколько возможных вариантов, но в итоге остаётся только один, а все неправильные предположения отбрасываются.
Подробнее и с картинками можно посмотреть в выступлении Tree-sitter - a new parsing system for programming tools или в статье A Comprehensive Introduction to Tree-sitter.
Песочница
Tree-sitter можно попробовать в песочнице прямо в браузере. Выбираем свой любимый язык программирования и пишем код. Снизу в реальном времени будет результат парсинга.
В песочнице tree-sitter показывает только именованные узлы (Named Nodes, подсвечены синим), в то время как анонимные узлы (Anonymous Nodes), такие как скобки или точка с запятой, скрыты, но присутствуют в дереве. Также некоторые узлы могут иметь поля (Fields, подсвечены серым), которые позволяют проще ориентироваться в структуре дерева.
Ещё одной фишкой tree-sitter "из коробки" является возможность поиска в дереве по шаблону. Для этого активируем чекбокс Query в песочнице. Синтаксис запросов основан на S-выражениях и позволяет задавать весьма сложные шаблоны для поиска. Подробнее про поиск и синтаксис запросов можно почитать в документации.
Использование
В основном, как не сложно догадаться, tree-sitter используют текстовые редакторы, но есть и другие проекты: поиск по коду, diff и т.д. Для tree-sitter существуют библиотеки для популярных языков программирования, а также готовые парсеры различных языков, если вы вдруг решите использовать его в своём проекте или придумаете какой-то новый. Например, линтер за час написать.
Создание парсера
Грамматика задаётся в специальном файле grammar.js. Как не трудно догадаться, описывается она с помощью JavaScript. Процесс этот не самый простой и подробнее о нём можно почитать в документации. Можно посмотреть на примеры грамматик для Java и JavaScript.
Биндинги
Tree-sitter готов к использованию в виде библиотеки для следующих языков программирования:
Парсеры
Готовы к использованию парсеры следующих языков:
В разработке:
Проекты
Список некоторых проектов использующих tree-sitter:
Atom - текстовый редактор от GitHub, с которого и началась история использования tree-sitter.
GitHub использует для различных фич: подсветка некоторых языков, навигация по коду и т.д.
Anycode - расширение для VSCode от Microsoft для поддержки фичей Language Server в ситуациях, когда Language Server нет.
Neovim (экспериментально с версии 0.5) с помощью nvim-treesitter.
Плагин для Emacs.
Ещё один плагин для Emacs для стуктурного редактирования кода.
Diffsitter - difftool для AST.
Tree-grepper - как grep, но для AST. Позволяет искать в исходных файлах с учетом синтаксической структуры.
Runestone - текстовый редактор для iOS.
Zee - консольный текстовый редактор написаный на Rust.
Zed - ещё не вышедший текстовый редактор от создателя tree-sitter ориентированный на совместную разработку написанный на Rust.
Semantic - Haskell-библиотека и консольная утилита для парсинга, анализа и сравнения исходного кода.
Полезные ссылки
Комментарии (34)
nin-jin
08.06.2022 15:43регулярные выражения, которые применяются построчно, для подсветки кода. Это приводит к тому, что, в отличие от редакторов опирающихся на синтаксические деревья, они не могут знать контекст и подсветка оставляет желать лучшего. Да и производительностью на больших объемах строк такой подход похвастаться не может.
Наоборот, построчный парсинг позволяет парсить код лениво - лишь те, строки, что собираешься показать, а не сразу весь файл. Вот пример. tree-sitter умеет так?
Но проблемы у редакторов использующих регулярные выражения возникают не только когда строк кода много, но и когда она всего одна, зато очень длинная. В этом случае такие редакторы ограничивают максимальную длину строки для подсветки, иначе парсинг регулярками занимал бы слишком много времени.
Регулярки - это такой же конечный автомат как и любой другой парсер. Нет ничего, что делало бы их принципиально медленнее tree-sitter. Опять же, выше пример - там парсится всё регуляркой.
Tree-sitter готов к использованию в виде библиотеки для следующих языков программирования
А как быть с длинным хвостом менее популярных языков? Мучаться без подсветки? Или для каждого языка, который хочешь позволить пользователям использовать, руками реализовывать парсер? Опять же, в примере выше универсальный парсер, которому не надо объяснять что за язык перед ним. tree-sitter умеет хотя бы автоматически язык определять?
ris58h Автор
08.06.2022 16:57+2Наоборот, построчный парсинг позволяет парсить код лениво - лишь те, строки, что собираешься показать, а не сразу весь файл
С этим соглашусь. Опять же, если строки небольшие.
tree-sitter умеет так?
Как именно? Парсить построчно? Конечно нет. Какое синтаксическое дерево вы хотите получить выдрав непонятный кусок из кода? Производительности tree-sitter хватает распарсить большой файл сразу. Об этом есть упоминание в статье.
Нет ничего, что делало бы их принципиально медленнее tree-sitter. Опять же, выше пример - там парсится всё регуляркой.
Я не знаю что за пример выше вы скинули. Нет ни описания, ни документации. Вы тоже никаких комментариев не дали. Подсунуть что-то в этот "текстовый редактор" не получилось. Минифицируйте код, что там есть в одну строку и проверьте как он себя поведёт - очень интересно посмотреть. Ни Sublime Text 4, ни VSCode не справились. Точнее, ST4 не справился, а VSC просто ограничил длину строки. Atom (c tree-sitter внутри) распарсил и подсветил всё.
А как быть с длинным хвостом менее популярных языков? Мучаться без
подсветки? Или для каждого языка, который хочешь позволить пользователям
использовать, руками реализовывать парсер?Странный вопрос. Пока нет парсера, нет ни подсветки, ни свёртки, ни прочих прелестей синтаксического анализа. Магии не бывает.
Опять же, в примере выше универсальный парсер, которому не надо объяснять что за язык перед ним.
Очень интересно. Жаль туда ничего вписать не получается. Может вы подскажите за него что за язык перед вами:
var x = 1;?tree-sitter умеет хотя бы автоматически язык определять?
Ещё более странный вопрос. Зачем парсеру (не текстовому редактору, замечу) уметь распознавать язык? Он получает на вход грамматику и текст, а выдаёт синтаксическое дерево.
nin-jin
08.06.2022 18:47Какое синтаксическое дерево вы хотите получить выдрав непонятный кусок из кода?
Никакое, я хочу подсветку синтаксиса, даже если это не валидный кусок большого файла. Вот, смотрите, метод без класса:
async foo() { return 'bar' }Ни Sublime Text 4, ни VSCode не справились.
Нажмите
Alt+Shift+F, не ломайте глаза.Может вы подскажите за него что за язык перед вами:
var x = 1;?
Ещё более странный вопрос. Зачем парсеру (не текстовому редактору, замечу) уметь распознавать язык? Он получает на вход грамматику и текст, а выдаёт синтаксическое дерево.
Чтобы не приходилось перебирать все грамматики в поисках первой попавшейся, а сразу получать результат с наиболее подходящей.
ris58h Автор
08.06.2022 19:18+1я хочу подсветку синтаксиса
А я хочу подсветку синтаксиса, find usages, line folding и многие другие нужные и полезные мне фичи.
Нажмите
Alt+Shift+F, не ломайте глаза.Если вы имеете в виду
Format document, то в ST4 я этого не нашел, а VSCode сперва собралась взлететь, судя по рёву вентиляторов, но так ничего и не сделала (если вообще должна была что-то сделать). Проблему длинных строк вы подтверждаете, как я понимаю?перебирать все грамматики
Я так и не понял зачем их вообще перебирать, тем более парсеру.
Я так понял, что у вас есть какой-то проект с "универсальной" подсветкой синтаксиса. Похвально. Попробуйте превратить его в полноценный текстовый редактор - может и всплывут какие-то проблемы, для решения которых авторы tree-sitter его и создали.
nin-jin
08.06.2022 21:23+1Вы встали в защитную позицию и на указание проблемных мест в предложенном подходе повторяете, какие у него есть достоинства. Достоинства никто не умаляет, тем не менее откройте глаза:
ris58h Автор
08.06.2022 22:54проблемных мест в предложенном подходе
Можно список этих проблемных мест? Я уже запутался о чём вы, т.к. мы ваш проект почему-то обсуждаем, а не tree-sitter.
тем не менее откройте глаза:
Я в typescript не разбираюсь. Зашел на https://www.typescriptlang.org/play и результат там не лучше:
Вы хоть пишите что вы имеете в виду когда кидаете какие-то ссылки или скрины, иначе очень сложно понять что вы хотели сказать.
nin-jin
09.06.2022 00:14Ну вот можете обратить внимание, что синтаксис подсвечен независимо от того, что код не валидный. Проще говоря, парсер для подсветки синтаксиса и для стат анализа - это два совершенно разных парсера с совершенно разными требованиями.
ris58h Автор
09.06.2022 09:20Ну вот можете обратить внимание, что синтаксис подсвечен независимо от того, что код не валидный.
Где он подсвечен? В вашем комментарии этого нет. Или вы про скрин из TypeScript Playground? В Tree-sitter Playground такой опции и нет вовсе - это не текстовый редактор, а синтаксический парсер. Подсветкой вольны заниматься продукты на основе этого парсера, если им это нужно. Тот же Atom с tree-sitter внутри этот код подсвечивает, хотя, наверное, и не так красиво как мог бы, из-за наличия ошибок.
Проще говоря, парсер для подсветки синтаксиса и для стат анализа - это
два совершенно разных парсера с совершенно разными требованиями.Определённо.
KvanTTT
08.06.2022 19:49+2Чтобы не приходилось перебирать все грамматики в поисках первой попавшейся, а сразу получать результат с наиболее подходящей.
Это не задача парсера. Тут элементы парсинга, конечно, могут использоваться, но могут использоваться и другие методы, в том числе машинное обучение, так как надо очень быстро детектить. А после натравливать полноценный парсер для более качественного разбора.
trokhymchuk
09.06.2022 10:28+1Никакое, я хочу подсветку синтаксиса, даже если это не валидный кусок большого файла. Вот, смотрите, метод без класса:
neovim + TS, подсветка синтаксиса:
А вот ещё менее валидный код на плюсах (подчёркивание у
fот проверки синтаксиса компилятором):
KvanTTT
09.06.2022 13:05VSCode в первом случае автодетектит JavaScript и тоже корректно подсвечивает код.
trokhymchuk
09.06.2022 10:18Наоборот, построчный парсинг позволяет парсить код лениво - лишь те, строки, что собираешься показать, а не сразу весь файл. Вот пример. tree-sitter умеет так?
В смысле "наоборот", вы хотите сказать, что на построчных регулярных выражениях можно собрать хоть сколько-то нормальный контекстно-зависимый парсер? Тут дай бог, чтобы не просто поток лексем, а какое-то синтаксическое дерево было.
А как быть с длинным хвостом менее популярных языков
Это биндинги.
Вас никто не заставляет использовать только tree-sitter, подсветку для неподдерживаемых ЯП можно реализовать любым способом.
Проект открыт, если вам нужен биндинг к другому языку, вы можете его написать
Или для каждого языка, который хочешь позволить пользователям использовать, руками реализовывать парсер
Вы не парсер пишете, а грамматику для него.
Опять же, в примере выше универсальный парсер, которому не надо объяснять что за язык перед ним
Вспомнил анекдот про секретаршу, которая печатает "9000 знаков в минуту". 3 строки CL, взятые из гугла, https://tree.hyoo.ru/#!source=(let* ((x 10) (y (%2B x 10))) (list x y)).
ris58h Автор
09.06.2022 11:00+1собрать хоть сколько-то нормальный контекстно-зависимый парсер
Я не он, но суть в том, что на регулярках можно парсить только те строки что показаны пользователю. Это позволяет сделать какую-нибудь подсветку без лагов.
Проект у @nin-jin интересный. Подойдёт отлично для какого-нибудь stackoverflow где случайные куски кода подсвечивать надо.
nin-jin
09.06.2022 11:29Для подсветки синтаксиса не нужен "сколько-то нормальный контекстно-зависимый парсер".
Смешной анекдот, да:
trokhymchuk
09.06.2022 11:55+2Так вы же его изменили, было:
Стало:
Долго будете изменять парсер под конкретные примеры, выдавая это за общий результат?
Ладно,
Не всё, что в кавычках, это просто строка, так можно и библиотеку подключить.
Почему у scope resolution operator первое двоеточие раскрашено я даже представить не могу.
structc(a) {}это не функция.
Ну и, для простой подсветки синтаксиса хватит и обычного парсера, а вот для хорошей нужен уже контекстно-зависимый.
nin-jin
09.06.2022 12:33Ну так, спасибо за бета-тест, баги поправил.
1 - Имя библиотеки задано строкой, всё правильно.
4 - Без понятия что это, с виду похоже на вызов инициализатора.
Для языка, на котором эта приблуда даже не тестировалась и ничего про него не знает, результат вообще отличный.
trokhymchuk
09.06.2022 14:071. Подключение заголовков должно быть одного цвета.
4.Это инициализация переменной, после которой следует пустое тело ф-ции.
Ну так эта приблуда как раз переваривает всё то, что есть в языках с си-подобным синтаксисом. Шаг влево или вправо --- уже не так, как было с лиспом, как в плюсах.
Можно было вообще взять какой-то APL или идрис :).
Но, стоит признать, как fallback при невозможности определить язык --- вполне себе.
KvanTTT
08.06.2022 18:03+1Не иметь зависимостей, чтобы библиотека (написанная на чистом C) могла быть встроена в любое приложение.
Это странная фраза, сам язык C уже и есть зависимость (в браузере его не запустить).
Можно сравнение с ANTLR4? Все-таки инструменты довольно схожи. Если доработать ANTLR4, то в нем можно делать почти то же самое, что и описано в статье.
Я провел беглый анализ и заметил следующее:
Минусы:- Формат грамматик: монструозный json сильно проигрывает лаконичному формату g4. Во всяком случае я такие видел для Java и JavaScript (странно, почему не заюзали что-нибудь более удобное?)
- Количество грамматик. Хоть по таргетам (биндингам) получается паритет (хотя не совсем корректно это сравнивать, поскольку tree-sitter написан на C, а ANTLR генерирует код под конкретный язык), по количетву грамматик ANTLR явно обходит tree-sitter: grammars-v4.
Плюсы:- Инкрементальный парсинг — это все-таки очень важное преимущество для работы в реальном времени.
- Скорей всего большая производительность (я как major контрибьютер в ANTLR могу сказать что там есть проблемы)
ris58h Автор
08.06.2022 18:45+1Это странная фраза, сам язык C уже и есть зависимость (в браузере его не запустить).
Это цитата с официального сайта. Я ничего с этим поделать не могу. Для браузера есть WebAssembly-биндинг и он прекрасно работает, что можно проверить в песочнице.
Формат грамматик: монструозный json сильно проигрывает лаконичному формату g4.
JSON - это уже внутреннее представление. Грамматика там на JavaScript задаётся (соответственно Java и JavaScript). Почему выбрали именно такой формат не знаю. Возможно, стоило добавить пункт про создание грамматики в статью (update: добавил небольшой пункт про создание парсера).
Количество грамматик
ANTLR, судя по Википедии, был разработан в 1989, а вышел в 1992. Tree-sitter начал разрабатываться около 2014 и был представлен широкой публике в 2017 - проект только стартанул, можно сказать.
Плюсы
Ну в этом и есть суть tree-sitter. Сделать быстрый парсер, заточенный изначально под нужды текстовых редакторов, но не ограничиваясь ими.
Если нужно написать парсер для некоторого формального языка, то старые добрые ANTLR, YACC/Bison и т.п. всё также подходят.
KvanTTT
08.06.2022 20:01Для браузера есть WebAssembly-биндинг и он прекрасно работает, что можно проверить в песочнице.
Только в браузере не всегда можно и нужно запускать WebAssembly. В ANTLR, например, есть полноценный JavaScript таргет, без зависимостей.
JSON — это уже внутреннее представление. Грамматика там на JavaScript задаётся (соответственно Java и JavaScript).
Посмотрел — на мой взгляд тоже неудачный формат. Самый главный минус — нет статических проверок (если, конечно, это обычный js, который исполняется как js). Менее существенные минусы: отношение разработчиков к этому языку и избыточность для описания языков.
ANTLR, судя по Википедии, был разработан в 1989, а вышел в 1992. Tree-sitter начал разрабатываться около 2014 и был представлен широкой публике в 2017 — проект только стартанул, можно сказать.
Все же корректней учитывать последнюю мажорную версию, а это 4, т.к. формат грамматик менялся. ANTLR 4 начал разрабатываться в 2010, а вышел году в 2011. Грамматики начали активно разрабатываться/портироваться и того позже. Так что разница не такая внушительная.
qw1
09.06.2022 10:47+1Мульти-таргетность это фича ANTLR, и она не бесплатная. Посмотрел доки — не все фичи появляются сразу во всех таргетах, т.е. весь зоопарк таргетов поддерживается вручную.
Если доработать ANTLR4, то в нем можно делать почти то же самое
Ну так то «если доработать tree-sitter, он может компилить в js, а не в C». Тем более, никаких экстраординарных конструкций в сгенерированном коде я не вижу, лишь огромные switch-и и тернарные операторы 50-кратной вложенности (по сути, тоже switch-и для диапазонов).
gdt
Выглядит круто, обидно что биндинги для всего есть, а для C# - нет. Вроде должно быть не сложнее чем для java.
ris58h Автор
Всё в ваших руках - проект опенсорсный. Тот же биндинг для Java от стороннего разработчика.
gdt
Справедливо, если буду когда-нибудь делать свой редактор - обязательно об этом подумаю :)
domix32
А зачем вам байндинги, если там уже сам парсер есть.
gdt
Я может что то не совсем правильно понимаю, но выглядит так, как будто бы есть парсер, а есть привязки к нему — ну чтобы на разных языках можно было его использовать. Вот например я фанат C# и делаю супер-новый-ни-на-что-не-похожий-самый-лучший редактор кода на C#, как мне поможет тот факт, что где-то там есть парсер, если я не могу его использовать в своём любимом языке?
domix32
Да собсна тем же самым, чем и наличие байндингов, только без накладных расходов на индирекшн. Есть реализации tree-sitter написанных сразу на языке, и есть байндинги (читай shared library). Останется это дело интегрировать в свои редакторы и скормить ему некоторый набор правил целевого языка/языков. То бишь если хочется писать на C# - подключаем C# реализацию и скармливаем в него правила для любого из поддержанных языков. А уж найти языковые правила с увеличением развития языковых серверов думаю не составит больших проблем.
gdt
Поделитесь ссылочкой на реализацию сразу на C#?
domix32
Я понял где ошибся. Я думал ниже это список интеграций в языки, а не сами грамматики. Вопрос снят.
ris58h Автор
Биндинг - это обвязка на целевом языке (в нашем случае обсуждаем C#), которая дёргает эту shared library.
Биндинга для C# в данный момент нет (по информации с официального сайта).