12 ms·

Incremental Parsing in Go

• xyzzy4747 4y ago
  For max optimization, wouldn’t it be better to create a Rust or C library for parsing that Go links into? I personally don’t see the usefulness of trying to optimize Go itself too much as it’s handicapped by the runtime and garbage collection.
  • tester756 4y ago
    C library for parsing? isn't it dangerous from security perspective?
    • xyzzy4747 4y ago
      It's just an example. The options are really Rust (what I'd prefer), C++, C, or perhaps something like Nim that compiles to C. If you’re trying to make an unoptimized parser, then use whatever you want.
      • deleted 4y ago
        [deleted]
  • pharmakom 4y ago
    For some reason we insist that language parsers are implemented in the language itself, even when the language isn’t great for parsers.
  • 37ef_ced3 4y ago
    You're in for a big surprise. Try using the language. Spend some time using Go, and you will be impressed by its performance. You'll wonder, "Were all those haters on Hacker News misinformed?"
    • xyzzy4747 4y ago
      If you're making something requiring CPU optimization as a core feature, you might as well go with one of the fastest languages instead of handicapping your project from Day 1. Go is not considered one of the fastest. It's better for network or filesystem logic that is I/O limited.
      • dymk 4y ago
        This is a premature optimization, and keeping everything in the same language has benefits like greatly simplified tooling and building
        • xyzzy4747 4y ago
          It’s not a premature optimization - it’s deciding the maximum that the parser can be optimized in the future. Choosing Go sets a lower ceiling. > Keeping everything in the same language has benefits like greatly simplified tooling and building Surely there are other Go libraries that incorporate C, C++, or Rust? Also if both parsers existed and were equally easy to set up, and you were planning on doing a ton of parsing, it would make sense to go with the faster one.
          • dymk 4y ago
            It absolutely is a premature optimization. If it's fast enough, then it's fast enough. The author hasn't indicated that the current Go implementation is hitting a ceiling imposed by the language yet. If you'd like to, you can provide some real-world examples - or even microbenchmarks - showing that Go is so much slower than <your choice here> that it's going to make a difference. > Also if both parsers existed and were equally easy to set up They're not equally easy to set up. Language interop is a pain in the pass.
          • Jtsummers 4y ago
            Look at the current Makefile: https://github.com/aretext/aretext/blob/main/Makefile https://github.com/aretext/aretext/blob/main/Makefile Build is literally a `go build ...` and install is `go install`. Adding any other language to the mix would make this a polyglot project and not be "equally easy to set up". The other question is, do both parsers exist? In this write-up they point to tree-sitter as a possibility which is a JS program that produces C code. This would be viable, but here's the author's take: > I considered integrating tree-sitter, an incremental parsing library with parsers for many existing languages. However, running JavaScript to generate parsers and linking to a C library would have greatly complicated the build process. Today, aretext can be built on almost any platform using a single go install command. I’ve had users install aretext on ARM laptops, FreeBSD servers, Chromebooks, and Android phones. To maintain portability, I wanted a pure Go implementation. So this wasn't some casual decision, but something they at least considered long enough to describe here. And the parsing library itself is only around 1200 lines total (comments, blanks, and code). The parsers for each language add a lot more, of course, but should be roughly equivalent given the same library and interface. I imagine that if this project really takes off and performance becomes a real problem they can do the rewrite at that point. Right now, the code works, seems to work fast enough for its author and primary users, and it's trivial to install on any platform supported by Go. So yes, it would have been a premature optimization to complicate the build process, probably reduce the number of supported platforms (or greatly increase the effort to support the same number of platforms), just to have a slightly faster parser.
  • rollcat 4y ago
    One of Go's primary goals has always been compilation speed. Go started out in C, and was later (post-1.0) incrementally rewritten to be self-hosting. One of the authors (Ken Thompson) is also one of the co-creators of C. I would argue these guys know what they are doing.
    • kaba0 4y ago
      I don’t know, not implementing generics when it was pretty obviously needed was a huge oversight, so I’m not sure. Also, the reason for compiler bootstrapping is more of a “beauty thing”, then practicality. It would definitely be faster in a low-level language, but I doubt it would matter as an end user.
      • fredrikholm 4y ago
        You aren't sure if Ken Thompson knows what he's doing?
        • kaba0 4y ago
          As a software architect? Absolutely. Programming language designer? Not sure, neither C or Go are good languages in my personal opinion. EDIT: I meant to write that I think very highly of him as an architect/developer.
          • sjansen 4y ago
            Experience has shown that often “worse is better”. Go does an amazing job of balancing complexity and power. I haven’t seen a ”better” language that isn’t either slower, harder to become productive, or both. https://en.wikipedia.org/wiki/Worse_is_better https://en.wikipedia.org/wiki/Worse_is_better
      • kcartlidge 4y ago
        > not implementing generics when it was pretty obviously needed was a huge oversight I get the desire for generics. I do a lot of C# and have used generics for a very many years. Yet I've been writing Go for around 6 or 7 years and other than in the beginning (when I was new to it) I haven't found myself missing them at all. In other words, for many people the lack of generics comes across as an oversight. For others, including myself (again, a heavy generics user in C#) that really isn't the case. I write Go in the style of Go and it just hasn't been an issue. Blanket statements are rarely true. YMMV.
  • deleted 4y ago
    [deleted]
  • Thaxll 4y ago
    I've seen some real world example where Go was as fast or faster than Rust for CPU / io intensive task. Go is a fast language even with a GC. https://github.com/boyter/scc/#performance https://github.com/boyter/scc/#performance
  • akira2501 4y ago
    For maximum return on investment, wouldn't it better to focus on something other than raw speed? I personally don't see the usefulness of trying to make everything in Rust itself too much as it's handicapped by it's compiler and lack of specification.
  • frou_dh 4y ago
    None of your ideas in this thread mention involving a profiler, so I take it you're from the Wild-Ass-Guess school of optimization?
• binwiederhier 4y ago
  Interesting read. Thank you for sharing. I always found parsers fascinating and mystical. It seems like these parser functions (which i think are analogous to what Rob Pike calls state functions) are a common way to do parsing, though i know very little about it. I especially found the combinators intriguing, though I don't care much for the functional programming syntax in a language like Go. Anyway, thanks for sharing. Tangentially, I wrote a little mini parser [0] of my own for my side project. It is inspired by Rob Pike's talk on parsers [1]. It doesn't use state functions, but instead just uses the call stack to keep track of where we are. [0] https://github.com/binwiederhier/ntfy/blob/main/server/actions.go#L86 https://github.com/binwiederhier/ntfy/blob/main/server/actio... [1] https://www.youtube.com/watch?v=HxaD_trXwRE https://www.youtube.com/watch?v=HxaD_trXwRE and https://go.dev/src/text/template/parse/lex.go https://go.dev/src/text/template/parse/lex.go
  • skohan 4y ago
    Yeah parsers are fun! We did a recursive descent parser for a toy language in uni and I think it was one of the most illuminating and fun projects we did at school. Lately I've been working on a tool to make it easy to implement a parser, and I end up using it for everything, because DSL's are so nice to work with.
• tester756 4y ago
  Difference in complexity of IDE's parser and Compiler's parser feels like order of magnitude IDE's you want to be very fast, so you use techniques like partial tree reparse and now when I think about it, then you also may need to update other places like you use type that is defined somewhere below and at first parse that type definition doesn't compile, so type usage above shows an error and when you change type definition so it compiles, then if you only update that part of the tree, then previous would still scream about the error it's really tricky the theory behind how to deal with all of this problems seems to be easy but when you actually get to the coding, then you have to be really thoughtful, careful and experienced in order to get the modeling of right https://learn.microsoft.com/en-us/shows/seth-juarez/anders-hejlsberg-on-modern-compiler-construction https://learn.microsoft.com/en-us/shows/seth-juarez/anders-h... ________ I have some experience with simpler and more complex parsers and for me no other type of software requires this much careful thought as parsers do if you want to address all those things like correctness, speed and recovery on broken code fragments, good error messages, good code, maybe concurrency
  • bbkane 4y ago
    You would like https://rust-analyzer.github.io/blog/2020/07/20/three-architectures-for-responsive-ide.html https://rust-analyzer.github.io/blog/2020/07/20/three-archit...
• deleted 4y ago
  [deleted]
• pharmakom 4y ago
  > a successful parse consumes at least one rune This avoids infinite loops?
  • Jtsummers 4y ago
    Yes, there would be two outcomes for an attempted parsing. Either it succeeds and makes progress (and eventually terminates) or it fails and consumes nothing (and terminates because eventually you run out of parsers to try).
• throwaway290 4y ago
  Off-topic but are there any aretext users? How does it fare?
• derek8bai 4y ago
  cool stuff
• hk__2 4y ago
  If you want a hard/interesting parsing challenge, try Clojure’s #_ reader macro. It’s a powerful construct that allows you to comment the next form. If you’re not used to Clojure, it’s like writing #_ in front of anything --a function, an array, a keyword, etc-- to comment it, even if it’s on multiple lines. For example: #_ (defn foo [x y] (println x y)) This is equivalent to commenting the three lines. Things become even harder when you learn that these thing "swallow" the next form and can be used anywhere: (let [a #_ b 43] #_ #_ hello (H N) (print a)) The code above is equivalent to the following: (let [a 43] (print a)) All the rest is comments. The hard/interesting bit is that to tokenize you must construct a syntax tree in order to correctly parse the next form, but in order to construct a syntax tree you first need to tokenize the code.
• diffxx 4y ago
  > The parsers produce a sequence to tokens, not a full syntax tree. Writing a tokenizer is much easier than parsing full syntax trees...Most other editors don’t construct the full syntax tree. Syntax highlighting is nice, but fast semantic analysis is the real holy grail. I have come to think that the best way to develop a new language would be to implement a text editor in that language before releasing the language. The editor should (ideally) have emacs and vim key bindings, though it would surely at least have the bindings that the language author uses. The compiler/interpreter for the language would embedded in the editor. This would allow for a much richer editing experience that goes beyond syntax highlighting. Indeed, the source code would become like a living document in the editor where they editor could display inline information about both syntax _and_ semantics. The editor need not be fancy. It could be written as a terminal application, kind of like a language specific nano or vim. If the language/editor author is careful in how they design the editor, all of the syntactical and semantic tooling should be exportable into packages that can be consumed by other editors with plugin systems/lsp like vscode or neovim. Then the rich editing experience can be relatively easily exported to any other text editor. Tool authors would also then be able to write static analysis/linting/formatting/whatever tools on top of the semantic tooling that the language supports. In some ways what I am describing is a more minimalist version of what one would get out of an image/IDE based language like smalltalk but the code representation would still remain as text files. The editor then becomes like a REPL except rather than being an ephemeral process, the REPL state is continually being written to disk and is resumable at any time from any computer capable of running the editor.
  • maxbond 4y ago
    I think it would be sufficient & more valuable to implement a language server for your new language, which keeps you focused on the parts related to your language rather than the struggles of implementing an editor, and then you'll be able to drop into VSCode, neovim, etc.
    • thechao 4y ago
      Does anyone have an good intro tutorial for writing a language server in, say, C for some simple language? I find most of the docs a little too inscrutable to follow for just a bit of dabbling.
• sesm 4y ago
  This article uses the word 'rune' extensively. From the context I assume it means 'lexem' or 'token' (i.e. the unit the lexer/scanner produces and feeds to parser). But then the article uses the word 'token' to mean the output of a parser ('keyword token'), while the usual terminology is that parser output is called a 'parse tree'. So, in this terminology, the parser consumes 'runes' and outputs 'tokens', while the usual terminology is that parser consumes 'tokens'/'lexems' and outputs 'parse tree'.
  • pgwhalen 4y ago
    Rune is a type alias in go, which more or less maps to the more common words “character” or “code point”. https://go.dev/blog/strings https://go.dev/blog/strings
    • sesm 4y ago
      Thanks! I don't know Go, so this terminology was surprising to me.
  • sjansen 4y ago
    In Go, `rune` is an alias for `int32` and is used to indicate the value is a Unicode "code point". For characters in the ASCII range, that means it's just a character encoded using more bits. If you need to worry about the full Unicode range then it's important to understand Unicode Normalization Forms. https://go.dev/blog/strings https://go.dev/blog/strings https://en.wikipedia.org/wiki/Unicode_equivalence https://en.wikipedia.org/wiki/Unicode_equivalence