Tree-sitter: an incremental parsing system for programming tools

Post by chrisseaton » Mon, Feb 22, 2021, 5:40 PM UTC

dcreager wrote: post #38

chrisseaton wrote: post #33

Earlier quoted context omitted.

I didn't mean the tree-sitter grammar was not understandable - it's very understandable - I just can't work out how to managed to find such a concise way to express grammars. Even compared to Whitequark it's 1/3 the size. What's the unique thing you do that makes it so concise? It also seems somehow to be completely declarative? How have you managed to transform Ruby parsing to be context-free? For example where's th…

Ahh my mistake! :-) To be fair, we're cheating a little bit because the Ruby grammar relies so heavily on an external scannar, which is just under 1,000 lines of C++: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...

Post by dcreager » Mon, Feb 22, 2021, 5:49 PM UTC

chrisseaton wrote: post #41

dcreager wrote: post #38

Earlier quoted context omitted.

Ahh my mistake! :-) To be fair, we're cheating a little bit because the Ruby grammar relies so heavily on an external scannar, which is just under 1,000 lines of C++: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...

But for example how do you parse the difference between `x = 14; x` and `y = 14; x`? In the latter case `x` is a method call, and in the former it's a local variable read. I can't see where the parser maintains a set of local variables and where it queries this set. Is it somehow done declaratively? If so that's a huge achievement I don't think that's really been done before in a parser generator. I really want to tr…

  $ cat test.rb
  module Test
    def test1
      x = 14; x
    end

    def test2
      y = 14; x
    end
  end
  $ tree-sitter parse test.rb
  (program [0, 0] - [9, 0]
    (module [0, 0] - [8, 3]
      name: (constant [0, 7] - [0, 11])
      (method [1, 2] - [3, 5]
        name: (identifier [1, 6] - [1, 11])
        (assignment [2, 4] - [2, 10]
          left: (identifier [2, 4] - [2, 5])
          right: (integer [2, 8] - [2, 10]))
        (identifier [2, 12] - [2, 13]))
      (method [5, 2] - [7, 5]
        name: (identifier [5, 6] - [5, 11])
        (assignment [6, 4] - [6, 10]
          left: (identifier [6, 4] - [6, 5])
          right: (integer [6, 8] - [6, 10]))
        (identifier [6, 12] - [6, 13]))))

Post by chrisseaton » Mon, Feb 22, 2021, 5:50 PM UTC

dcreager wrote: post #43

chrisseaton wrote: post #41

Earlier quoted context omitted.

But for example how do you parse the difference between `x = 14; x` and `y = 14; x`? In the latter case `x` is a method call, and in the former it's a local variable read. I can't see where the parser maintains a set of local variables and where it queries this set. Is it somehow done declaratively? If so that's a huge achievement I don't think that's really been done before in a parser generator. I really want to tr…

[EDITED to make the example actually line up with OP's test] There's no symbol table in the parser, so at parse time, we don't distinguish those cases: $ cat test.rb module Test def test1 x = 14; x end def test2 y = 14; x end end $ tree-sitter parse test.rb (program [0, 0] - [9, 0] (module [0, 0] - [8, 3] name: (constant [0, 7] - [0, 11]) (method [1, 2] - [3, 5] name: (identifier [1, 6] - [1, 11]) (assignment [2, 4]…

Post by maxbrunsfeld » Mon, Feb 22, 2021, 5:55 PM UTC

anaerobicover wrote: post #40

maxbrunsfeld wrote: post #28

Hey, Tree-sitter author here. Thanks for posting! Let me know if you have questions about the project.

I've done two grammars for my own use in the last few months (well, one isn't quite complete yet) and it's been quite an enjoyable (learning) experience. Thanks for sharing this tool!

Post by srcreigh » Mon, Feb 22, 2021, 5:57 PM UTC

lalaithion wrote: post #27

srcreigh wrote: post #11

Tree Sitter is amazing. The parsing is fast enough to run on every keystroke. The parse tree is extremely concise and readable. It resembles an AST more than a parse tree (ie no 11 levels of binary op precedence rules in the tree). The parse tree emits specific ERROR nodes, so you can get a semi-functional tree even with broken syntax. I can't wait for the tools to get built with this. Paredit for TypeScript. Syntax-…

Maybe I can finally have this syntax highlighting style: https://youtu.be/b0EF0VTs9Dc?t=900