#prog #rust #parsing #article
Resilient LL Parsing Tutorial
In this tutorial, I will explain a particular approach to parsing, which gracefully handles syntax errors and is thus suitable for language servers, which, by their nature, have to handle incomplete and invalid code. Explaining the problem and the solution requires somewhat less than a trivial worked example, and I want to share a couple of tricks not directly related to resilience, so the tutorial builds a full, self-contained parser, instead of explaining abstractly just the resilience.
The tutorial is descriptive, rather than prescriptive — it tells you what you can do, not what you should do.
* If you are looking into building a production grade language server, treat it as a library of ideas, not as a blueprint.
* If you want to get something working quickly, I think today the best answer is “just use Tree-sitter”, so you’d better read its docs rather than this tutorial.
* If you are building an IDE-grade parser from scratch, then techniques presented here might be directly applicable.
Resilient LL Parsing Tutorial
In this tutorial, I will explain a particular approach to parsing, which gracefully handles syntax errors and is thus suitable for language servers, which, by their nature, have to handle incomplete and invalid code. Explaining the problem and the solution requires somewhat less than a trivial worked example, and I want to share a couple of tricks not directly related to resilience, so the tutorial builds a full, self-contained parser, instead of explaining abstractly just the resilience.
The tutorial is descriptive, rather than prescriptive — it tells you what you can do, not what you should do.
* If you are looking into building a production grade language server, treat it as a library of ideas, not as a blueprint.
* If you want to get something working quickly, I think today the best answer is “just use Tree-sitter”, so you’d better read its docs rather than this tutorial.
* If you are building an IDE-grade parser from scratch, then techniques presented here might be directly applicable.
matklad.github.io
Resilient LL Parsing Tutorial
In this tutorial, I will explain a particular approach to parsing, which gracefully handles syntax errors and is thus suitable for language servers, which, by their nature, have to handle incomplete and invalid code.
Explaining the problem and the solution…
Explaining the problem and the solution…
🔥2🤔1🖕1
#prog #parsing #article
В Just write a parser (примечание к небольшому набору уроков по реализации парсера) автор выступает против глубокого изучения подходов к парсингу в курсах по обучению компиляторостроения и за то, чтобы забить на "академические" подходы и делать рекурсивный спуск руками. В качестве аргументов он приводит:
* Рекурсивный спуск очень хорошо даёт понять, как работает парсер, в отличие от генераторов парсеров.
* Это практичный навык: парсеры реальных компиляторов написаны вручную.
* Это не так уж и сложно.
В статье Why We Need to Know LR and Recursive Descent Parsing Techniques Laurence Tratt соглашается с первым тезисом (не перегружать курс по компиляторам подходами к парсингу), но оспаривает второй.
Именно, он указывает на LR-грамматики: такие грамматики точно являются однозначными, а то, является ли грамматика LR, можно проверить автоматически. Рекурсивный спуск же не даёт ясно понять, какова реализуемая парсером грамматика. В частности, реализуемая парсером грамматика может быть неоднозначной. Более того, то, что самописный рекурсивный спуск сам по себе вполне детерминирован, означает, что парсер таки разрешает неоднозначности грамматики, причём зачастую неочевидным способом.
Автор проводит параллель между валидатором грамматики и тайпчекером: прохождение проверки означает гарантию отсутствия определённых проблем (неоднозначностей грамматики и ошибок несовпадения типов соответственно). Более того, как он отмечает:
> If writing a grammar in LR style is hard for you as the language author, it will almost certainly be hard for users to understand!
Разумеется, автор признаёт, что не для всех языков возможно написать LR-грамматику в принципе, но он отмечает, что попытка написать такую грамматику может как минимум подсказать, где в реализации парсера могут крыться баги из-за неоднозначности.
Разумеется, это не всё, что есть в статье, так что советую прочитать целиком.
В Just write a parser (примечание к небольшому набору уроков по реализации парсера) автор выступает против глубокого изучения подходов к парсингу в курсах по обучению компиляторостроения и за то, чтобы забить на "академические" подходы и делать рекурсивный спуск руками. В качестве аргументов он приводит:
* Рекурсивный спуск очень хорошо даёт понять, как работает парсер, в отличие от генераторов парсеров.
* Это практичный навык: парсеры реальных компиляторов написаны вручную.
* Это не так уж и сложно.
В статье Why We Need to Know LR and Recursive Descent Parsing Techniques Laurence Tratt соглашается с первым тезисом (не перегружать курс по компиляторам подходами к парсингу), но оспаривает второй.
Именно, он указывает на LR-грамматики: такие грамматики точно являются однозначными, а то, является ли грамматика LR, можно проверить автоматически. Рекурсивный спуск же не даёт ясно понять, какова реализуемая парсером грамматика. В частности, реализуемая парсером грамматика может быть неоднозначной. Более того, то, что самописный рекурсивный спуск сам по себе вполне детерминирован, означает, что парсер таки разрешает неоднозначности грамматики, причём зачастую неочевидным способом.
Автор проводит параллель между валидатором грамматики и тайпчекером: прохождение проверки означает гарантию отсутствия определённых проблем (неоднозначностей грамматики и ошибок несовпадения типов соответственно). Более того, как он отмечает:
> If writing a grammar in LR style is hard for you as the language author, it will almost certainly be hard for users to understand!
Разумеется, автор признаёт, что не для всех языков возможно написать LR-грамматику в принципе, но он отмечает, что попытка написать такую грамматику может как минимум подсказать, где в реализации парсера могут крыться баги из-за неоднозначности.
Разумеется, это не всё, что есть в статье, так что советую прочитать целиком.
tiarkrompf.github.io
Tiark's Notebook
Tiark Rompf is an Associate Professor at Purdue University. Notes and blog posts on programming, research, CS, software systems.
👍11❤1🔥1