Re: A tree-sitter code parser for SC
[email protected] Sun, 31 Jan 2021 19:46:13 -0800
| Newsgroups | gmane.comp.audio.supercollider.devel |
|---|---|
| Message-ID | <CAP-jasUeBWfML2-Cp2pWnTOvRVWwaAH3DxMCAXT5=Sc18_nazQ@mail.gmail.com> |
--000000000000a652a705ba3e328f Content-Type: text/plain; charset="UTF-8" Cool. I have a feeling that being able to specify precedence to the parser generator makes this easier. I think the trouble I had been having is some of my own confusion around unary negation support. There isn't, for example, support for arbitrary unary negation, only float and integer literals. So, for example, the following won't parse: ( var a = 1; 1 - - a; ) but "1 - - 1" totally will, as would "a - - 1". I was trying to identify numeric literals entirely at lexing time, but unary negation for floats and integers only means that either I needed to add lookahead for my lexer for this one particular case only, or to follow what sclang currently does and detect the negation at parse time. Anyway, I'm working on IR codegen now, so it will likely be a minute until I have gathered the sclang corpus for testing the parser. And I have a feeling your parser is likely to be less buggy, because you are using a parser generator instead of hand-coding. So maybe I'll end up comparing my parse trees to yours, as it sounds like it is more likely to be canonical parses than the sclang parser. I've followed the project in GitHub, can't wait to see where you turn up! \L On Sun, Jan 31, 2021 at 9:09 AM <mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]> wrote: > I actually just added basic support for unary (negative) operators as well > as some other basic stuff. > On 31/01/2021 16.00, mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected] wrote: > > > > > On 29/01/2021 16.49, [email protected] wrote: > > This is really cool, nice work! > > I've also been (slowly!) writing a new SuperCollider parser, in my case > for use as the frontend for Hadron > <https://github.com/hadron-sclang/hadron>, a re-implementation of sclang > using LLVM to JIT. I use a lexer written using Ragel and a hand-coded > parser in C++. I wonder if we could maybe chat and compare notes? > Specifically: > > Sure! > > - There are some interesting corner cases in the grammar that made for > some design challenges. I'd be curious to understand how you approached > solving some of these. For instance, unary negation (in combination with > arbitrary binary operation) made me rewrite a medium-size chunk of my > parser, particularly because I lex in an independent pass. > > I haven't dealt much with unary negatives yet but tree-sitter has built in > support for this by using left-side or right-side precedence which has > helped me solve a lot of fuzzy problems. > > check this out: > > https://tree-sitter.github.io/tree-sitter/creating-parsers#using-precedence > > > I currently parse unary method calls like 1.round as > <literal><instance_method> (compared to SinOsc.ar which becomes something > like <class><class_method>) See the examples here if oyu want to se how > granular this can become > https://github.com/madskjeldgaard/tree-sitter-supercollider#parsing-examples > > > > - What are your thoughts about LSP > <https://microsoft.github.io/language-server-protocol/>? I think someone > on sc-dev had mentioned this to me, I had thought this might be a good way > to deepen the usefulness of a sclang IDE. I hadn't heard about tree sitter > before, this seems interesting as well. > > Yes my dream is to reach the LSP-stage at some point too. I use a > combination of LSP server (clang) and tree-sitter when writing c++ for > example and it makes for a very comfortable and helpful toolset I think. > > > - I share your intuition that better error reporting would strongly > increase the usability of sclang. I wonder, could we standardize on this? I > also had some ideas/hopes/dreams of someday even soliciting volunteers to > help translate the error messages into other languages. > > - Testing could be another area we could potentially collaborate. Besides unit > test coverage > <https://github.com/hadron-sclang/hadron/blob/master/src/Parser_unittests.cpp> my > integration test plan was to build a large corpus of open source sclang > example code by scraping GitHub repositories, then run my parser on it and > compare the resulting parse tree against the sclang parse tree. > > yeah! Tree-sitter has unit testing built in, and I try to write at least > one test for each rule I add. The tests in tree-sitter must result in > exactly the parsed tree that the test expects to there is no tolerance > there, which is good cause it picks up on the smallest changes. > > > - I'd like to hear more about how tree-sitter-supercollider is fast. Like, > what design choices did you make to support speed, and how have you > measured it? Is it fast relative to the sclang parser? The sclang parser is > built using Bison, and while I went a different direction with my design my > suspicion is that it's pretty tough to write a hand-coded parser that will > be as fast as a Bison-generated one. > > Yeah this is probably true. I actually haven't done any benchmarking, this > is just me buying in to the marketing hype :) > > But tree-sitter parses each piece of code as a node, so when it has to > reparse something, instead of reparsing the whol document it only reparses > that particular node (for example the right side of a binary expression in > sc or something like that). > > > I've been wanting to build a private fork of sclang instrumented with > Perfetto <https://perfetto.dev/>, so traces could be automatically > collected of both Hadron and sclang, for comparisons. Given that I'm > working on a JIT compiler the objective of Hadron is speed. Typical > speedups when moving from an interpreted bytecode model to a JIT model are > more than one order of magnitude. On ARM architectures, particularly, a > work project I was involved in saw a speedup on benchmarks of over 1000x > when moving from a JavaScript interpreter to JIT. Parsing, however, is > typically not the slowest part of compilation, and JITing with LLVM may > result in an overall *slower* compile time. I think as a syntax highlighter > speed is probably really important. But hyper-optimized code is often less > readable and maintainable than standard code, because of all the special > cases and extra tooling involved. > > The sclang parser also does some transformations to the parse tree while > constructing it, to aid in an optimization tree pass that happens right > after passing. I'm thinking specifically of the DropNode work, which allows > the current parser to drop expressions that are dead code *before even > compiling them*. So for example in the block ( 1; 2; 3; ) the first two > expressions will be parsed but not compiled. This is elegant and cool, > IMHO, but what it means is that the parser produced by sclang is not a > *canonical* parse tree. I assume if tree-sitter-supercollider is intended > for syntax highlighting then the objective is to produce a canonical tree, > which makes sense. (Although, it might be quite interesting to use an > editor that was syntax highlighting "dead" code!) > > Yeah this is actually an interesting problem! Should the parser be > opinionated enough to say hey, those two first statements in (1;2;3;) > actually don't do anything? I am also apropos considering whether the > syntax highlighter should somehow emphasize that the last of those three is > actually a return statement equal to ^3. I think that would be helpful for > newbies especially to visually see what gets returned. > > > I also wanted to produce a canonical tree, for ease of testing and > readability of the code. It had been my hope that a hand-coded parser would > be a more inclusive design decision because it removes the Bison language > requirement from potential contributors. Optimization steps could happen in > subsequent passes on the tree, making them easier to test and hopefully > easier to understand and maintain. But all of this means to me that the > comparison between my parser and the sclang parser is not going to be > strictly apples-to-apples. And I'm not so sure that speed matters in > parsing as I suspect that the overwhelming time sink for Hadron during > compilation is going to be during LLVM bytecode generation and > optimization. So I was going to wait until I had a measurement of the e2e > compilation before I started to optimize the parser further. > > Anyway, lots I'd love to discuss, as you can tell! Do you ever dip into > the Slack? Or if you're on Discord I have set up a server to talk about > Scintillator <https://scintillatorsynth.org/> and Hadron, although right > now there's nobody there but me and once Josh P who very kindly dipped in. > But that channel is here <https://discord.gg/uBsyzbG5>. > > Cheers! > > \L > > On Wed, Jan 27, 2021 at 6:02 AM <mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]> wrote: > >> Hello all >> >> Just wanted to let you know I started work on a grammar for >> SuperCollider mapping out the language for use with the tree-sitter code >> parser (https://tree-sitter.github.io). >> >> It's in an early experimental stage but most of the language has been >> mapped in the grammar (phew!) so it can handle simple code examples now. >> I mostly made this to be used in neovim where I do all my coding (and >> have become addicted to using tree-sitter for c++ and lua projects) but >> it should be possible to implement in scide aswell if interested. >> >> There are basically three features in tree-sitter that inspired me to do >> this: >> >> - Scoped syntax highlighting - this makes it possible to easily see if a >> variable is local, an environment variable, class variable, builtin or >> an argument and thus makes code a heck of a lot easier to read and >> understand. >> >> - Very precise syntax error messages. Because tree-sitter structures >> code in node trees, once the whole grammar is done, it should be easy to >> very to get super precise syntax errors. As it is now, if you omit a ; >> it tells you exactly where in the code in expected it to be (because >> that one node in the tree failed to parse) >> >> - It's fast >> >> You can see a screenshot, some examples and follow/help with the >> progress here for now: >> >> https://github.com/madskjeldgaard/tree-sitter-supercollider >> >> Best! >> >> >> _______________________________________________ >> sc-dev mailing list >> >> info (subscription, etc.): >> http://www.birmingham.ac.uk/facilities/ea-studios/research/supercollider/mailinglist.aspx >> archive: http://www.listarc.bham.ac.uk/marchives/sc-dev/ >> search: http://www.listarc.bham.ac.uk/lists/sc-dev/search/ >> > --000000000000a652a705ba3e328f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Cool. I have a feeling that being able to specify preceden= ce to the parser generator makes this easier. I think the trouble I had bee= n having is some of my own confusion around unary negation support. There i= sn't, for example, support for arbitrary unary negation, only float and= integer literals. So, for example, the following won't parse:<div><br>= </div><div>(</div><div>var a =3D 1;</div><div>1 - - a;</div><div>)</div><di= v><br></div><div>but "1 - - 1" totally will, as would "a - -= 1". I was trying to identify numeric literals entirely at lexing time= , but unary negation for floats and integers only means that either I neede= d to add lookahead for my lexer for this one particular case only, or to fo= llow what sclang currently does and detect the negation at parse time.</div= ><div><br></div><div>Anyway, I'm working on IR codegen now, so it will = likely be a minute until I have gathered the sclang corpus for testing the = parser. And I have a feeling your parser is likely to be less buggy, becaus= e you are using a parser generator instead of hand-coding. So maybe I'l= l end up comparing my parse trees to yours, as it sounds like it is more li= kely to be canonical parses than the sclang parser. I've followed the p= roject in GitHub, can't wait to see where you turn up!</div><div><br></= div><div>\L=C2=A0</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr= " class=3D"gmail_attr">On Sun, Jan 31, 2021 at 9:09 AM <<a href=3D"mailt= o:mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]">mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]</a>> wrote:<br></div><b= lockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le= ft:1px solid rgb(204,204,204);padding-left:1ex"> =20 =20 =20 <div> <p>I actually just added basic support for unary (negative) operators as well as some other basic stuff. <br> </p> <div>On 31/01/2021 16.00, <a href=3D"mailto:mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]" target=3D"_blank">mail@mads= kjeldgaard.dk</a> wrote:<br> </div> <blockquote type=3D"cite"> =20 <p><br> </p> <p><br> </p> <p><br> </p> <div>On 29/01/2021 16.49, <a href=3D"mailto:[email protected]" ta= rget=3D"_blank">[email protected]</a> wrote:<br> </div> <blockquote type=3D"cite"> =20 <div dir=3D"ltr">This is really cool, nice work! <div><br> </div> <div>I've also been (slowly!)=C2=A0writing=C2=A0a new SuperCo= llider parser, in my case for use as the frontend for <a href=3D"https= ://github.com/hadron-sclang/hadron" target=3D"_blank">Hadron</a>, a re-impl= ementation of sclang using LLVM to JIT. I use a lexer written using Ragel and a hand-coded parser in C++. I wonder if we could maybe chat and compare notes? Specifically:</div> </div> </blockquote> <p>Sure!<br> </p> <blockquote type=3D"cite"> <div dir=3D"ltr"> <div>- There are some interesting corner cases in the grammar that made for some design challenges. I'd be curious to understand how you approached solving some of these. For instance, unary negation (in combination with arbitrary binary operation) made me rewrite a medium-size chunk of my parser, particularly because I lex in an independent pass.</div= > </div> </blockquote> <p>I haven't dealt much with unary negatives yet but tree-sitter has built in support for this by using left-side or right-side precedence which has helped me solve a lot of fuzzy problems.</p> <p>check this out: <br> </p> <p><a href=3D"https://tree-sitter.github.io/tree-sitter/creating-pars= ers#using-precedence" target=3D"_blank">https://tree-sitter.github.io/tree-= sitter/creating-parsers#using-precedence</a></p> <p><br> </p> <p>I currently parse unary method calls like 1.round as <literal><instance_method> (compared to SinOsc.ar which becomes something like <class><class_method>) See the examples here if oyu want to se how granular this can become <a href=3D"https://github.com/madskjeldgaard/tree-sitter-supercolli= der#parsing-examples" target=3D"_blank">https://github.com/madskjeldgaard/t= ree-sitter-supercollider#parsing-examples</a><br> </p> <p><br> </p> <blockquote type=3D"cite"> <div dir=3D"ltr"> <div><br> </div> <div>- What are your thoughts about <a href=3D"https://microsoft.= github.io/language-server-protocol/" target=3D"_blank">LSP</a>? I think som= eone on sc-dev had mentioned this to me, I had thought this might be a good way to deepen the usefulness of a sclang IDE. I hadn't hear= d about tree sitter before, this seems interesting as well.</div> </div> </blockquote> <p>Yes my dream is to reach the LSP-stage at some point too. I use a combination of LSP server (clang) and tree-sitter when writing c++ for example and it makes for a very comfortable and helpful toolset I think. <br> </p> <blockquote type=3D"cite"> <div dir=3D"ltr"> <div><br> </div> <div>- I share your intuition that better error reporting would strongly increase the usability of sclang. I wonder, could we standardize on this? I also had some ideas/hopes/dreams of someday even soliciting volunteers to help translate the error messages into other languages.</div> <div><br> </div> <div>- Testing could be another area we could potentially collaborate. Besides <a href=3D"https://github.com/hadron-sclan= g/hadron/blob/master/src/Parser_unittests.cpp" target=3D"_blank">unit test = coverage</a>=C2=A0my integration test plan was to build a large corpus of open source sclang example code by scraping GitHub repositories, then run my parser on it and compare the resulting parse tree against the sclang parse tree.</div> </div> </blockquote> <p>yeah! Tree-sitter has unit testing built in, and I try to write at least one test for each rule I add. The tests in tree-sitter must result in exactly the parsed tree that the test expects to there is no tolerance there, which is good cause it picks up on the smallest changes.<br> </p> <blockquote type=3D"cite"> <div dir=3D"ltr"> <div><br> </div> <div>- I'd like to hear more about how tree-sitter-supercollider is fast. Like, what design choices did you make to support speed, and how have you measured it? Is it fast relative to the sclang parser? The sclang parser is built using Bison, and while I went a different direction with my design my suspicion=C2=A0is that it's pretty tough = to write a hand-coded parser that will be as fast as a Bison-generated one.</div> </div> </blockquote> <p>Yeah this is probably true. I actually haven't done any benchmarking, this is just me buying in to the marketing hype :) <br> </p> <p>But tree-sitter parses each piece of code as a node, so when it has to reparse something, instead of reparsing the whol document it only reparses that particular node (for example the right side of a binary expression in sc or something like that). <br> </p> <blockquote type=3D"cite"> <div dir=3D"ltr"> <div><br> </div> <div>I've been wanting to build a private fork of sclang instrumented with <a href=3D"https://perfetto.dev/" target=3D"_= blank">Perfetto</a>, so traces could be automatically collected of both Hadron and sclang, for comparisons. Given that I'm working on a JIT compiler the objective of Hadron is speed. Typical speedups when moving from an interpreted bytecode model to a JIT model are more than one order of magnitude. On ARM architectures, particularly, a work project I was involved in saw a speedup on benchmarks of over 1000x when moving from a JavaScript interpreter to JIT. Parsing, however, is typically not the slowest part of compilation, and JITing with LLVM may result in an overall *slower* compile time. I think as a syntax highlighter speed is probably really important. But hyper-optimized code is often less readable and maintainable than standard code, because of all the special cases and extra tooling involved.</div> <div><br> </div> <div>The sclang parser also does some transformations to the parse tree while constructing it, to aid in an optimization tree pass that happens right after passing. I'm thinking specifically of the DropNode work, which allows the current parser to drop expressions that are dead code *before even compiling them*. So for example in the block ( 1; 2; 3; ) the first two expressions will be parsed but not compiled. This is elegant and cool, IMHO, but what it means is that the parser produced by sclang is not a *canonical* parse tree. I assume if tree-sitter-supercollider is intended for syntax highlighting then the objective is to produce a canonical tree, which makes sense. (Although, it might be quite interesting to use an editor that was syntax highlighting "dead" code!)</div> </div> </blockquote> <p>Yeah this is actually an interesting problem! Should the parser be opinionated enough to say hey, those two first statements in (1;2;3;) actually don't do anything? I am also apropos considering whether the syntax highlighter should somehow emphasize that the last of those three is actually a return statement equal to ^3. I think that would be helpful for newbies especially to visually see what gets returned.<br> </p> <blockquote type=3D"cite"> <div dir=3D"ltr"> <div><br> </div> <div>I also wanted to produce a canonical tree, for ease of testing and readability of the code. It had been my hope that a hand-coded parser would be a more inclusive design decision because it removes the Bison language requirement from potential contributors. Optimization steps could happen in subsequent passes on the tree, making them easier to test and hopefully easier to understand and maintain. But all of this means to me that the comparison between my parser and the sclang parser is not going to be strictly apples-to-apples. And I'm not so sure that speed matters in parsing as I suspect that the overwhelming time sink for Hadron during compilation is going to be during LLVM bytecode generation and optimization. So I was going to wait until I had a measurement of the e2e compilation before I started to optimize the parser further.</div> <div><br> </div> <div>Anyway, lots I'd love to discuss, as you can tell! Do yo= u ever dip into the Slack? Or if you're on Discord I have set up a server to talk about <a href=3D"https://scintillatorsynth.= org/" target=3D"_blank">Scintillator</a>=C2=A0and Hadron, although right now there's nobody there but me and once Jos= h P who very kindly dipped in. But that channel is <a href=3D"htt= ps://discord.gg/uBsyzbG5" target=3D"_blank">here</a>.</div> <div><br> </div> <div>Cheers!</div> <div><br> </div> <div>\L</div> </div> <br> <div class=3D"gmail_quote"> <div dir=3D"ltr" class=3D"gmail_attr">On Wed, Jan 27, 2021 at 6:0= 2 AM <<a href=3D"mailto:mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]" target=3D"_bla= nk">mail-7db+uFJyHB4PRnmXVbbcgVpr/1R2p/[email protected]</a>> wrote:<br> </div> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8= ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hello all<br> <br> Just wanted to let you know I started work on a grammar for <br> SuperCollider mapping out the language for use with the tree-sitter code <br> parser (<a href=3D"https://tree-sitter.github.io" rel=3D"norefe= rrer" target=3D"_blank">https://tree-sitter.github.io</a>).<br> <br> It's in an early experimental stage but most of the languag= e has been <br> mapped in the grammar (phew!) so it can handle simple code examples now. <br> I mostly made this to be used in neovim where I do all my coding (and <br> have become addicted to using tree-sitter for c++ and lua projects) but <br> it should be possible to implement in scide aswell if interested.<br> <br> There are basically three features in tree-sitter that inspired me to do <br> this:<br> <br> - Scoped syntax highlighting - this makes it possible to easily see if a <br> variable is local, an environment variable, class variable, builtin or <br> an argument and thus makes code a heck of a lot easier to read and <br> understand.<br> <br> - Very precise syntax error messages. Because tree-sitter structures <br> code in node trees, once the whole grammar is done, it should be easy to <br> very to get super precise syntax errors. As it is now, if you omit a ; <br> it tells you exactly where in the code in expected it to be (because <br> that one node in the tree failed to parse)<br> <br> - It's fast<br> <br> You can see a screenshot, some examples and follow/help with the <br> progress here for now:<br> <br> <a href=3D"https://github.com/madskjeldgaard/tree-sitter-superc= ollider" rel=3D"noreferrer" target=3D"_blank">https://github.com/madskjeldg= aard/tree-sitter-supercollider</a><br> <br> Best!<br> <br> <br> _______________________________________________<br> sc-dev mailing list<br> <br> info (subscription, etc.): <a href=3D"http://www.birmingham.ac.= uk/facilities/ea-studios/research/supercollider/mailinglist.aspx" rel=3D"no= referrer" target=3D"_blank">http://www.birmingham.ac.uk/facilities/ea-studi= os/research/supercollider/mailinglist.aspx</a><br> archive: <a href=3D"http://www.listarc.bham.ac.uk/marchives/sc-= dev/" rel=3D"noreferrer" target=3D"_blank">http://www.listarc.bham.ac.uk/ma= rchives/sc-dev/</a><br> search: <a href=3D"http://www.listarc.bham.ac.uk/lists/sc-dev/s= earch/" rel=3D"noreferrer" target=3D"_blank">http://www.listarc.bham.ac.uk/= lists/sc-dev/search/</a><br> </blockquote> </div> </blockquote> </blockquote> </div> </blockquote></div> --000000000000a652a705ba3e328f-- _______________________________________________ sc-dev mailing list info (subscription, etc.): http://www.birmingham.ac.uk/facilities/ea-studios/research/supercollider/mailinglist.aspx archive: http://www.listarc.bham.ac.uk/marchives/sc-dev/ search: http://www.listarc.bham.ac.uk/lists/sc-dev/search/