“Tree-sitter——面向编程工具的新型解析系统” by Max Brunsfeld
"Tree-sitter - a new parsing system for programming tools" by Max Brunsfeld
频道:Strange Loop Conference · 时长:38:37 · 发布:2018-10-14 · 播放:63511
简介
Max Brunsfeld 介绍 Tree-sitter,一个面向开发者工具的解析系统,通过统一的 C API 提供增量解析和稳健的错误恢复。演讲解释了其设计,基于从 LR 扩展到 GLR 的解析方法。
HN 为什么推荐
HN 指出它是解释 tree-sitter 设计选择的最佳材料,也是解析器生成器的易懂入门。
如果你想深入了解 tree-sitter 背后的设计选择,强烈推荐 Max Brunsfield 的 Strange Loop 演讲。 — HN, 2024
中文字幕节选
大家好,我叫Max,在GitHub的Atom文本编辑器团队工作,嗯,我 今天想跟大家聊聊一个我一直在做的项目,叫treesitter, 到现在大概有四年了,目的是改进文本编辑器的一些核心功能。 嗯,treesitter最初只是我的一个业余项目,嗯,甚至在我 开始在GitHub工作之前就开始了,但现在它已经成了我们在GitHub 做的几个产品的一部分。所以今天我要跟大家讲讲treesitter是什么, 聊聊它和你可能用过的其他东西有什么不同, 然后我会展示一些我们在GitHub用treesitter构建的东西, 最后我会讲讲treesitter的工作原理以及它用到的一些算法。 那么首先,treesitter是什么?嗯, treesitter是一个用于解析源代码的库,用C和C++编写, 设计用于像Atom这样需要处理多种不同语言代码的应用程序。 所以你可以用treesitter解析用各种不同语言编写的文件, 生成具有相同接口的语法树。但treesitter真正 独特的地方在于所谓的增量解析,这 意味着一旦你用treesitter解析了文件,之后你编辑文件时, treesitter可以给你一棵反映你所做编辑的新语法树,而无需 重新解析整个文件。嗯,创建这棵新树非常 快,而且占用内存很少,因为新树共享了旧树中 在你编辑后未发生变化的部分。所以这个特性使得 可以用treesitter在像Atom这样的文本编辑器中,在用户 每次按键输入时解析源代码,并在应用程序中同时在多个线程上 使用语法树,而不用担心竞态条件。 treesitter另一个有趣的地方是所谓的错误恢复, 这意味着你可以给treesitter无效的代码,无论是因为你正在 输入代码的过程中,还是因为代码使用了解析器不知道的 某些非标准语言特性。如果你这样做,它不会像 所有常用解析器那样直接中止并给你一条错误消息, treesitter有一种方法可以检查你的代码,找出每个错误的 起点和终点,并仍然返回一棵有用的语法树。所以这个 特性使得即使你解析的是最终用户编写的、你可能并不完全 理解的代码,也能依赖treesitter给你的语法树。 这就是treesitter,treesitter能做什么。嗯,现在我来聊聊它 和你可能用过的其他东西有什么不同。treesitter主要 受到我用过的一些IDE的启发,比如IntelliJ和WebStorm,我真的很 喜欢IDE,因为它们在你编写代码时就解析你的代码,并且用 这些解析树作为IDE中所有功能的基础。所以IDE 做的一切都非常智能,但IDE的问题在于它们非常 针对特定语言定制,而且通常相当慢。所以据我所知,没有 哪个IDE能做到我刚才说的那种增量解析, 这意味着每当你在IDE中输入一个字符,IDE都必须从头 重新解析整个文件,这可能需要几十甚至几百毫秒, 当你在文本编辑器中打字时,这实际上是非常长的时间。
HN 上的讨论
完全同意,这里引用我去年写的一条评论:我认为 tree-sitter 无依赖这一点值得强调。作为背景,我的一些队友维护 OCaml 的 tree-sitter 绑定,并且在我们开发 Semgrep 的工作中经常为语法做贡献(Semgrep 使用 tree-sitter 来搜索代码,并将本身就是代码片段的查询解析为 AST 匹配器)。通常,在编写 linter 时,你需要带上你所针对语言的运行时。例如,在 Python 中,如果你使用内置的 `ast` 模块编写解析器,你需要匹配语言版本和特性。因此,例如你无法在 Python 2.7 上运行的 Pylint 中解析 Python 3 代码。这最终会比一开始想象的更烦人,尤其是在你针对多种语言时。在 tree-sitter 之前,使用语言内置的 AST 工具通常是最好的方法,因为它保证能跟上最新的语法。在我看来,tree-sitter 的天… — ievans, 2024-03
我也很喜欢 5 年前 Max Brunsfeld 的 Treesitter 演讲 [VIDEO]。我目前正在构建一种查询语言,其语法深受 GitHub 搜索语法的启发。我使用的是 Lezer,它类似于 Treesitter 的 GLR,所以这个演讲让我学到了一些解析器生成器的知识(我没有正规的计算机科学教育背景)。如果有人想试试,这是我的语法、一个演练场和一个示例搜索查询 [LINK] [LINK] -(a) spider-man -a b -c -"(quote\"d) str" OR "l o l" OR a b c ((a "c") b) tag:what -deck:"x y" 我刚刚把语法树转换成了抽象语法树,这样我就可以做德摩根定律变换。这 literally 是我职业生涯中唯一一次感觉自己像是在解决 leetcode 风格的问题。 — AlexErrant, 2023-12
很高兴看到更多工具采用 tree-sitter [1]。拥有一个(快速)单一工具,能够准确解析大多数常用编程语言,这非常有用,但它需要维护几十个语法,如果没有大型社区的努力,这很难。希望更多的采用意味着更准确的解析器和对更多语言的支持。Tree-sitter 为 GitHub.com 以及(即将)neovim 和 OniVim 2 提供语法高亮。希望基于正则表达式的语法高亮很快成为过去。如果你还没看过关于 tree-sitter 的 Strange Loop 会议演讲[2],值得一看。我认为使用 tree-sitter 的类似 Prettier 的代码格式化器会很酷,无论是在潜在更广泛的语言支持还是原生性能方面。[1]:[LINK] [2]:[VIDEO] — rtsao, 2020-10
对于错误信息问题的一个非常好的解决方案,请看最近这个 strangeloop 演讲:[VIDEO] 基本上,它使用 GLR 解析器的解析树消歧来寻找用户最可能犯的错误——非常聪明。 — lemming, 2018-11
解析(使用而非理论)很重要,因为它影响我的工作。所以我跟进了一下。见 [VIDEO] Tree sitter 基于 LR 解析(见上述视频 23:30)扩展到 GLR 解析(见 38:30)。我受够了 HN 上的傻瓜发布未经证实的废话来让自己感觉酷和知识渊博(别自欺欺人地以为你发布了错误答案就帮我找到了正确答案)。该退出了。再见 HN。 — throwaway_pdp09, 2020-12
相关视频
- “Pixie——一个拥有‘魔法’力量的轻量级 Lisp” by Timothy Baldridge · Strange Loop Conference · 33:12
- RailsConf 2014 - Sandi Metz 谈所有的小细节 · Confreaks · 38:47
- Rich Harris - 重新思考响应式 · You Gotta Love Frontend · 36:45
- Go 中的词法扫描 - Rob Pike · GoogleFOSSSydney · 51:17
- William Byrd 谈“有史以来最美丽的程序” [PWL NYC] · PapersWeLove · 1:31:05
- “用确定性模拟测试分布式系统” by Will Wilson · Strange Loop Conference · 40:20
- 🚀 TDD,哪里出错了(Ian Cooper) · DevTernity Conference · 1:03:55
- Bret Victor - 在原则中发明 · Rui Oliveira · 54:20
- 用 Clojure 的方式解决问题 - Rafal Dittwald · Clojure/north · 1:02:26
- 火线调试:系统失控时保持冷静 • Bryan Cantrill • GOTO 2017 · GOTO Conferences · 52:34
- Emery Berger 的“性能至关重要” · Strange Loop Conference · 42:15
- Acme编辑器之旅 · Russ Cox · 23:16
- 技术演讲:Linus Torvalds 谈 git · Google · 1:10:15
- Gil Tene 的 "如何不测量延迟" · Strange Loop Conference · 42:59
- Ruby Conf 12 - Gary Bernhardt 的边界 · Confreaks · 45:55
- CppCon 2016: Jason Turner “为微型计算机编写丰富代码:用C++17实现一个简单的Commodore 64游戏” · CppCon · 1:19:52