13 ms·
Hello, I work on the C# compiler and we use a handwritten recursive-descent parser. Here are a few of the more important reasons for doing so: * Incremental r
by tyoverby 10y ago
Hello, I work on the C# compiler and we use a handwritten recursive-descent parser. Here are a few of the more important reasons for doing so:
* Incremental re-parsing. If a user in the IDE changes the document, we need to reparse the file, but we want to do this while using as little memory as possible. To this end, we re-use AST nodes from previous parses.
* Better error reporting. Parser generators are known for producing terrible errors. While you can hack around this, by using recursive-descent, you can get information from further "up" the tree to make your more relevant to the context in which the error occurred.
* Resilient parsing. This is the big one! If you give our parser a string that is illegal according to the grammar, our parser will still give you a syntax tree! (We'll also spit errors out). But getting a syntax tree regardless of the actual validity of the program being passed in means that the IDE can give autocomplete and report type-checking error messages. As an example, the code "var x = velocity." is invalid C#. However, in order to give autocomplete on "velocity", that code needs to be parsed into an AST, and then typechecked, and then we can extract the members on the type in order to provide a good user experience.
My personal opinion is that everyone should just use s-expressions. Get rid of this whole debate :P
- bbcbasic 10y agoThanks it's great to hear from someone that makes the tools I use everyday. > My personal opinion is that everyone should just use s-expressions. Get rid of this whole debate :P C# 8 maybe?
- marxidad 10y agoUntyped S-Expressions would be taking a step back from a C# perspective.
- e12e 10y agoI don't see how s-expressions are inheritently less "typed" than utf-8 text? Have a compiler target dialect that expects "(int 5)" and "(int x)" have a type-inference step that target such "typed" s-expressions?
- tyoverby 10y agoThe "best" part about project Roslyn is that if someone wanted to make an s-expression frontend, they could plug that into the compiler.
- YeGoblynQueenne 10y agoOut of curiosity, how many people do you have working on the parser?
- kodfodrasz 10y agoI guess 12 or more poeple are on the new keyword team, always ready to jump on a new language feature added. After all it happens every 3-5 years. Adding a new keyword to a parser is a huge work, even tests need to be written! hint: irony
- tyoverby 10y agoThe best part about going open source was being able to outsource the bikeshedding discussions to the community! (Just kidding, we still do them internally too)
- tyoverby 10y agoWe don't have specific people that do parsing; if your feature needs changes to the parser, then you make those changes.
- stcredzero 10y agoOne nice thing about using recursive descent, is that your parser "is just a normal program." It's also a potential problem, but every substantive project needs coding standards anyhow.
- PaulHoule 10y agoAnother problem I have with parser generators is that they often have an awful API. For instance, working in a OO language such as C#, I often want to turn the parse into an AST build out of idiomiatic objects. Most compiler-compilers use the same "callback hell" interface that was used for the original yacc in the 1970's. Thus you wind up writing error-prone code. Conceptually, the grammars used in compiler-compilers aren't that much more complex than regexes (you just have named sub-expressions, the possibility of recursion, and possibly some specification of associativity) Yet, regexes are probably used 100x more in application software development. In many systems programming areas I think often using unergonomic tools is a badge of pride, it proves how smart you are, so I think ergonomics are often not taken seriously by those who develop the tools.
- electrum 10y agoANTLR4 automatically generates a visitor for your grammar that you can use to translate into your own idiomatic objects: http://jakubdziworski.github.io/java/2016/04/01/antlr_visitor_vs_listener.html http://jakubdziworski.github.io/java/2016/04/01/antlr_visito... We use this in Presto for parsing SQL and generating an immutable AST: https://github.com/prestodb/presto/blob/master/presto-parser/src/main/antlr4/com/facebook/presto/sql/parser/SqlBase.g4 https://github.com/prestodb/presto/blob/master/presto-parser... https://github.com/prestodb/presto/blob/master/presto-parser/src/main/java/com/facebook/presto/sql/parser/AstBuilder.java https://github.com/prestodb/presto/blob/master/presto-parser...
- Jare 10y ago> My personal opinion is that everyone should just use s-expressions. Aren't S-expressions particularly problematic for providing autocomplete hints?
- tyoverby 10y agoI don't see why they would be any better or worse than another grammar choice. It might be true that s-expressions would make people prefer certain semantic decisions that would be difficult to analyze for autocomplete.
- Jare 10y agoTo clarify: do you think there are sets of semantic decisions using S-expressions that would still "get rid of the whole debate", and not make autocomplete harder in practice? (not that it's important of course, but your remark made me curious, and the reactions to my question even more so)
- tyoverby 10y agoAutocomplete is most commonly used on structures in order to find out which fields and methods that structure contains. If you used an s-expression based grammar that still had fields and methods, then you'd get the exact same experience. foo.bar. <- autocomplete here vs (foo.bar.) ^ autocomplete here
- Flow 10y agoExcept that in some Lisps where you have multi-methods or generated field accessor methods you'd probably would write it backwards. Maybe like this: (. (bar foo) ...) ^ cursor is here
- tyoverby 10y agoSure. That's a property of the language, not S-Expressions. It's just like how SQL decided to write all their queries backwards making it impossible to do good autocomplete.
- Drup 10y agoWhile I agree with you those 3 points are extremely important, it turns out there is at least one parser generator that can do all of it: http://gallium.inria.fr/~fpottier/menhir/ http://gallium.inria.fr/~fpottier/menhir/ It supports both incremental parsing and an API to inspect and recover incomplete ASTs (which powers Merlin, the IDE-like thing for OCaml). It provides stellar debugging features for ambiguous grammars and a way to have good error messages (which is used in compcert's C parser and facebook's reason). So, it's not impossible. Most parser generators are not that good, though.
- tyoverby 10y agoThat is super impressive! I can't find the part on incomplete AST or AST reuse in their reference docs though.
- dsp1234 10y agoDetails about the "incremental" mode are listed in the documentation PDF[0] at section 9.2 Here are the first couple of paragraphs: "In this API, control is inverted. The parser does not have access to the lexer. Instead, when the parser needs the next token, it stops and returns its current state to the user. The user is then responsible for obtaining this token (typically by invoking the lexer) and resuming the parser from that state. The directory demos/calc-incremental contains a demo that illustrates the use of the incremental API. This API is “incremental” in the sense that the user has access to a sequence of the intermediate states of the parser. Assuming that semantic values are immutable, a parser state is a persistent data structure: it can be stored and used multiple times, if desired. This enables applications such as “live parsing”, where a buffer is continuously parsed while it is being edited. The parser can be re-started in the middle of the buffer whenever the user edits a character. Because two successive parser states share most of their data in memory, a list of n successive parser states occupies only O(n) space in memory." There does not appear to be a specific mention of having the partial AST available. [0] - linked from their front page and available at http://gallium.inria.fr/~fpottier/menhir/manual.pdf http://gallium.inria.fr/~fpottier/menhir/manual.pdf
- def-lkb 10y ago
- breatheoften 10y agoAre there any statically typed S-expression languages?
- glenda 10y agoTyped Racket is the only one I've come across but I'm sure there are a few more.
- munificent 10y agoShen is another one: http://www.shenlanguage.org/ http://www.shenlanguage.org/ There are also a ton of hobby languages that are statically typed and use s-exprs so the author doesn't have to spend as much time on syntax.
- shanemhansen 10y agoClojure does allow type annotations that are used to avoid reflection. https://clojure.org/reference/java_interop#Java%20Interop-Type%20Hints https://clojure.org/reference/java_interop#Java%20Interop-Ty... (defn len2 [^String x] (.length x))
- deleted 10y ago[deleted]
- specialist 10y agoI'm curious about your incremental re-parsing strategy. I wasn't smart enough to figure out how to adapt these strategies to my LL(k) grammars (late 90s). Maybe someone's figured this out. Efficient and Flexible Incremental Parsing TIM A. WAGNER and SUSAN L. GRAHAM https://www.researchgate.net/profile/SL_Graham/publication/2377179_Efficient_and_Flexible_Incremental_Parsing/links/004635294e13f23ef1000000.pdf https://www.researchgate.net/profile/SL_Graham/publication/2...
- maxbrunsfeld 10y agoFWIW, I'm developing a library based on the technique outlined in this paper (and others by Time Wagner). Like the original paper, it uses LR(1) (and GLR), not LL(k). The library itself is here: https://github.com/tree-sitter/tree-sitter https://github.com/tree-sitter/tree-sitter and here are some existing grammars: * https://github.com/tree-sitter/tree-sitter-javascript * https://github.com/tree-sitter/tree-sitter-go * https://github.com/tree-sitter/tree-sitter-ruby