10 ms·
Just Write the Parser
- prezjordan 6y agoAside (sorry!) but https://tiarkrompf.github.io/notes https://tiarkrompf.github.io/notes is really cool and it's fun to see this format
- brundolf 6y agoThe only annoying thing is that the scroll bar is in the middle of my screen. I wish they'd max-widthed the text while leaving the scrollable element full-width
- ofrzeta 6y agoThe other annoying thing is the manipulation of the browser history :) In my opinition it should keet its hands off it.
- awinter-py 6y agothose scroll-matched curly braces are something
- jraph 6y agoWow, thank you very much for this link! This is very inspiring. First, there is an impressive overlap with what I like and what I have been doing. The notes on the piano, the parser, on GraphViz and on React all hit very close if not exactly things I've thought about or programmed. Second, the means of presenting things is awesome too. I get lost very easily so there are probably ways to improve but this is very clever and interesting. The creativity and pedagogy here is incredible at all levels. I am very impressed. I need to keep an eye on this. I wish there was an RSS feed. I'll contact him.
- tiarkrompf 6y agoThanks - very glad to hear. RSS should be doable
- mamcx 6y agoI like the bit about CPS, but wish it show how do the last part without having the async machinery in the host language. What I have a hard time to get is how implement fully delimited continuations. All the examples I know reuse the machinery of the host so is hard to translate (in my case, to Rust)
- neurotrace 6y agoI don't want to be that guy but I originally thought the CSS was broken. Harsh black on harsh white, everything squeezed in to the left third of my screen, and an unused scrollbar on the bottom. That being said, I love the information. I don't care for the workflow that comes with the most popular parser generators and I inevitably want more control over my parser as I start adding error handling, etc. It's easier to just write it by hand in the first place
- millstone 6y agoI think the design is great. Simple and easy to read.
- neurotrace 6y agoDifferent strokes for different folks, I suppose. I found it to be confusing and painful
- Supermancho 6y agoI'm not quite sure why they went with the borked "half the screen is empty" look. Ok, it's easier to read, but that negative space is bad design, regardless.
- toolz 6y agoI found the design to be very intuitive even though I'd never encountered that type of information flow before. The curly braces didn't seem to serve any purpose as far as I could tell, but the negative space was great. I knew exactly where the content was going to pop up before I clicked the "link". No jarring resize, just plain ole empty space not taking your attention away from the main content until you want see content in there.
- megous 6y agoBecause... ? https://megous.com/dl/tmp/da01875b777013e9.png https://megous.com/dl/tmp/da01875b777013e9.png
- 6y ago
- epistasis 6y agoThere's been a ton of code that I've written that in retrospect, I should never have written. But I've never regretted when I wrote a parser. Maybe because it takes such a large activation energy to get over the hump and actually do it, that I only do it when absolutely necessary. But it always seems easier and more useful than I thought before doing it. Now that this post has prompted that realization, I wonder if it will stay true...
- pianoben 6y agoI have _absolutely_ regretted writing a parser by hand. Once I replaced it with an ANTLR grammar and a comparatively-trivial bit of glue, my thrift parser became not only easier to refactor but more reliable. My hand-written recursive descent parser was a perennial source of bugs, where ANTLR has yielded almost none. Some fiddly things I was doing with comments became much easier, if not effortless. I highly, HIGHLY recommend at least starting with a compiler-generator like ANTLR. The "activation cost" of your project will be much lower, and you may find that you never actually _need_ the level of control you give up.
- tiarkrompf 6y agoAuthor here - happy to answer questions, as always. Thanks also for feedback on the format of the article. It's a bit of an experiment on how to present dense information effectively. Some more rationale here: https://tiarkrompf.github.io/notes/?/octopus-notes/ https://tiarkrompf.github.io/notes/?/octopus-notes/
- LeonB 6y agoOctopus notes is an interesting idea. Thanks for the link on it. And I do like to write a lot of little parsers. I worked with someone once who would somehow transform every business problem into “we need to write a compiler”. Sounds crazy but he achieved brilliant results and has gone on to great things.
- musicale 6y agoWhat's the best way to handle unary "-" and other unary operators? I'd like to be able to write expressions like "-2^-(2+2)" or "a cos b + a sin b". For "-2^-(2+2)" note that exponentiation has higher precedence than negation.
- myk9001 6y agoTake a look at "Parsing expressions by precedence climbing"[1] by Eli Bendersky. See the "Other resources" section for other approaches to this problem. 1: https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions...
- musicale 6y ago1) Like the original article, this leaves unary operators as an exercise for the reader (though it does note so explicitly and provides a small hint) 2) This looks more like Pratt parsing vs. the approach described in the article 3) I was asking the original author
- thysultan 6y agoTake the current + next node i.e: parse_node + parse_peek When parse_node is an operator you know it is the "-2" in "-2^-2(2+2)" and when parse_peek is the operator it is "-(2+2)" in the same. An example of this: - https://github.com/thysultan/Ally/blob/8ba0b4de7ab104ceae54d810fced69f43ca852cc/src/Parser.js#L140-L197 https://github.com/thysultan/Ally/blob/8ba0b4de7ab104ceae54d...
- tofflos 6y ago> Enter an expression on the left and see the parse tree change! I don't get it. The left input field is uneditable in Firefox, Edge and Chrome. Navigation is broken across the board. Even copying and pasting the quote above somehow included most of the page even though I only selected that one sentence. This looks very cool and I would love to try it out! :(
- blcArmadillo 6y agoYeah I think something is broken because at least in chrome when you try to type in the left box the following exception keeps being thrown in the console VM463:82 Uncaught TypeError: Cannot read property 'startContainer' of undefined at HTMLPreElement.eval (eval at run (eval at runScriptElement (octopus-2.js:525)), <anonymous>:82:40)
- tiarkrompf 6y agoI just pushed a fix for Chrome (apparently it doesn't report affected selection ranges for input events). Hope it works now!
- ben509 6y ago> Why simpler is better and why you don't need a parser generator. As far as I can see, this isn't fully answered, unless the claim is strictly limited to the question of need. In my case, I certainly want a parser generator. I'm working on a language, and I did a very early version using a hand-rolled recursive descent parser. Then I realized I wanted a syntax that was human friendly, so I graduated to megaparsec. That worked, it's an elegant way to describe a parser, but as a language gets complex you have to work in implicit orderings (magic, frankly) to handle the limits of recursive descent. Finally, I realized I needed a spec and an implementation in sync with that spec, so I went with BNFC[2], and it even generates some pretty documentation[1] for me. This is the classic debate over using a domain specific language vs. a general purpose language, so there's no hard answer one way or the other. For me, the deciding factor was I didn't want to write, test, etc. my own parser, and I think there being a canonical way for others to parse my language (in other languages as well) is helpful. [1]: https://tenet-lang.org/spec-syn.html https://tenet-lang.org/spec-syn.html [2]: https://bnfc.digitalgrammars.com/ https://bnfc.digitalgrammars.com/
- dfabulich 6y agoRight below the line you quote, the author makes three arguments: > • It’s highly instructive, in a way that using a parser generator is not. To quote Feynman: “What I cannot create, I do not understand” > • It’s an important skill: most real-world compilers use hand-written parsers because they provide more control over error handling, significant whitespace, etc. > • It’s not actually difficult! The exercises themselves are meant to justify these arguments. I think the exercises conclusively demonstrate that #1 and #3 are true. If you can easily follow these exercises, and if, by the end, you feel like you've learned something useful, then it follows that hand-rolling a parser is instructive and not too difficult. I strongly agree with the author that if you're developing a language for the first time, you shouldn't use a parser generator at first. You should hand-roll a parser first, and then, when you see the limitations of your hand-rolled parser, adopt a parser generator, now with full understanding of what the generator is doing for you (and not doing for you). As for #2, the article demonstrates how to do error handling in a manner that would be a head-scratcher in Yacc. You claim here that it was easier to develop a "human friendly" syntax with megaparsec than it was to do that in a hand-rolled recursive-descent parser. That could be true, but that's not my experience. To be convincing, you'd need to do what the author did, (even though you say the author didn't): you'd need to justify your argument with specific examples.
- cwp 6y agoIf you're writing a compiler, sure, a hand-written parser is probably better than a generated parser. However, I'd also make the related claim that we should be much more ready to write formal parsers for other use cases. Far too often developers implement a "pile of regular expressions" where a parser—even a generated parser-would be a better choice.
- wrs 6y agoOne reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you didn’t realize. A hand-coded parser tends to just codify your bad assumptions. It can actually be a good idea to maintain a YACC (or other) grammar for your language just to run the tool as a kind of “grammar linter”, even if you’re going to write the parser by hand.
- pklausler 6y agoIf you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.
- thequux 6y agoMost parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)
- UK-Al05 6y agoDo they hide or do they just apply order to choices. Making it impossible to be ambiguous compared to the CFG definition? It's only sweeping under the rug, if you look at PEG under CFG rules. PEG is not CFG. I think practice of writing industrial software that is better.
- WorldMaker 6y agoI do sometimes wonder if a lot of these arguments themselves would be less ambiguous if PEGs (or some other name of them) were formally added to Chomsky's Hierarchy of Languages between Regular Languages and the languages expressed by CFGs. Though I think it would take someone with a much more rigorous math background than myself to make the case formal enough to get it accepted. (If it helps, and it may be a red herring, the dualism between PEGs and Parser Combinators has me thinking it's a Category Theory related "step" in the hierarchy. "Deterministic Monadic Compositions" in a reflection of DFA/NFA duals to Regular Languages might imply "Monadic Languages" as a possible name? Again, my math background is definitely not formal enough here to make actual suggestions, but maybe it sparks an idea for someone else.)
- jtolmar 6y agoI'd highly recommend looking at a few toy parser projects, like this and Crafting Interpreters (which are both recursive decent, with very different styles), writing however much of a typical parser you think makes sense "for fun," and then saving that somewhere you can get at it. Writing a parser from scratch is kind of an obnoxious hurdle, but if you have some code you're already familiar with that you can copy-paste in and modify to your purposes, that's a lot more accessible. (Also hats off to this author for making a parser so damn terse.)
- swyx 6y agowhat is "recursive decent"?
- newlikeice 6y agoman can dig hole. while digging one hole he finds two holes. he Diggs the one hole till he finds the bottom. climbs up to where he found the two the proceeds down the other hole. till he finds two more holes and then digs to the bottom of the first hole he finds until he hits bottom there. he descends until he hits bottom or digs through the earth. one hole at a time. the digging is just the way your language constructs itself into different elements spread out like directories and sub-directories.
- swyx 6y agoah. i was thrown off by the typo. i thought you were complimenting their decency.
- samatman 6y agoAn alternate title: "Just Shotgun Parse Your Inputs". This isn't bad advice across the board, but it is bad advice for many applications. This is how you end up with context-sensitive formats, or ones where the semantics of a particular particle require running the parser, or worse. It exposes a rich surface area for exploitation with adversarial inputs. That said, the advantages cited at the front of the article are all real: error recovery and decent error messages are unsolved problems with existing parser generators, although ANTLR is pretty good at it. But, especially if you're developing the data format rather than just implementing it, I strongly suggest using something like Instaparse which can generate a parser directly from a grammar. Once this is solidified, it's reasonable to hand-roll something, but even there, I suggest using a nice parser combinator library, like hammer or Nom. This provides more discipline: as long as you're coloring inside the lines, you'll end up with a parser which actually implements your spec. When you start adding functions to provide context, recover from errors, and provide meaningful feedback in the form of error messages for unexpected inputs, you'll know what you're doing: a classic recursive-descent parser can't provide the same conceptual separation between the parsing logic and the logic to support ergonomics or one-pass compiling or whatever add-ons you're putting in there.
- specialist 6y ago"where the semantics of a particular particle require running the parser, or worse" Yup. Consider the much maligned (apache) httpd.conf and makefile. Their code was the source of truth for correctness. No matter horrible terrible their syntax, they would have been sufferable if they had grammars. Bespoke parsing of expressions benefits from having an implicit grammar, like this OC. But threshold for needing explicit grammars is pretty low. Prime examples are all the data exchange formats. Descriptions of JSON and CSV are short and naively reasonable, but insufficient. As we've seen, any ambiguity that can happen will happen.
- thequux 6y agoI agree with everything you say, except your advice to use a parser combinator library, because most implement PEGs. Hammer is, of course, an exception to this, as long as you call `h_compile` to tell it to use a different backend. Why not use PEGs? In short, they don't actually remove ambiguity from your grammar, but rather hide it in ways that are difficult to reason about. You're still dependent on code as a definition of the language that you accept, and worse, that code is very fragile in the face of refactoring. Further, the lexical analysis step is generally the source of most ambiguity, and most parser combinator libraries make it extremely inconvenient to parse something that isn't a character stream. (Hammer is actually worse than most here; it's not possible to use it to parse anything other than streams of bytes, though perhaps it can be excused because of the limitations of C)
- Const-me 6y agoDid something similar a few times when I needed that. Here’s an open source example: https://github.com/Const-me/vis_avs_dx/tree/master/avs_dx/DxVisuals/Expressions https://github.com/Const-me/vis_avs_dx/tree/master/avs_dx/Dx... It’s mostly in C++, just a few offline pieces in C# in T4 templates (they produce C++ code).
- eyelidlessness 6y agoConsidering that something as simple and limited as JSON has been a source of security vulnerabilities from ambiguities in the spec, thanks but nope. Declarative definitions of a grammar help identify those ambiguities... and if the grammar is defined separately from its interpretation, it opens the door to invisible ambiguities that can become another vector for vulnerabilities. Unless you have provable implementations (great if you do!), declarative grammars meaningfully limit points of failure.
- lifthrasiir 6y agoSpec ambiguities of JSON mostly come from the insufficient description of data model and well-formedness and not from the syntax itself. Say, to this day (including RFC 8259) duplicate keys from the JSON object are not explicitly forbidden, even though most applications require that. Probably the only issue arisen from the JSON syntax proper would be the treatment of line and paragraph separators.
- sleavey 6y agoAnd my number one gripe, that you can't add a trailing comma to the last list item. Very annoying when streaming JSON data.
- deleted 6y ago[deleted]
- maest 6y agoThe framing in this page is broken on Firefox Android. The last couple of lines can't be scrolled into view.
- kmstout 6y agoA long time ago I did a deep-dive on recursive descent parsing and ended up writing a parser generator [1]. [1] https://github.com/reindeereffect/tools-from-blog/tree/master/yakety https://github.com/reindeereffect/tools-from-blog/tree/maste...
- tomcam 6y agoI find it handy to write out the grammar for a parser generator to check for problems, then handwrite the parser once it passes.
- Cloudef 6y agoWhenever someone mentions parsers or parser combinators, the only thing that comes to my mind is ragel that's really suited for generating any sort of parsers http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/
- Cloudef 6y agohttps://git.cloudef.pw/escpos2raster.git/tree/src/escpos/parser.rl https://git.cloudef.pw/escpos2raster.git/tree/src/escpos/par... here is example, where I use ragel to parse ESC/POS printer protocol. Software that allows raster printers to print ESC/POS stuff.
- ThePhysicist 6y agoI'd recommend reading the "Elkhound" paper [1], which introduces a GLR parser that's really easy to implement and very powerful, they use it in the paper to parse a large subset of C++. GLR parsers are so much more powerful and intuitive than recursive descent parser (I find), and they often make grammars easier to read and understand. That said if you're building a real programming language it makes sense to build the parser by hand as it often runs faster. For example, my GLR Python parsers clocked in at around 100.000-300.000 lines of Python code per second, while the regular Python parser could do 5-10 times as much per second (including tokenizing, parsing and AST generation). Looking at the amount of Python code that is parsed every day, this is a significant difference. [1] https://people.eecs.berkeley.edu/~necula/Papers/elkhound_cc04.pdf https://people.eecs.berkeley.edu/~necula/Papers/elkhound_cc0...
- kenoph 6y agoHow about no? Parsers are one of the main sources of bugs in software. You should write parsers manually only when you have a very good reason to. Go ask any of your system security friends.
- Terr_ 6y agoIt may be worth distinguishing between: 1. Having a formal grammar definition as the authoritative spec 2. Using the formal grammar definition to generate your parser #1 is quite valuable on its own, even if you don't want to do #2. It can be analyzed for ambiguities and inconsistencies, and you avoid the tar-pit of "the original implementation is the spec".
- leonliang 6y agoAs a previous student in Professor Rompf's compiler class, I had the best learning experience while writing the parser for a Scala-like language. The parser logic has since influenced not only how I code, also how I think.