9 ms·

Dreaming of a Parser Generator for Language Design

117 points by matt_d 8y ago

andrewla 8y ago
This is an excellent survey of many of the issues facing modern parsers. They correctly point out that error handling is by far the biggest one, and usually ends up being the biggest part of a parser for a language, full of crufts and strange mixtures of semantics and syntax. Add to this that you frequently want to try to partially recover -- make a guess as to what was intended and continue parsing in the hopes of finding more actionable errors later in the code. I do disagree with a lot of the other conclusions, especially operator precedence, which I've come to believe is generally a bad thing -- associativity can be fine (although even there I'm uncertain), but managing operator precedence is almost always better done by using parentheses. I like scannerless, but the author makes a lot of good points that I might have to rethink. The analogy to how people read makes some sense, but I'm not sure there's as crisp a line between syntax and semantics as that analogy would imply in natural languages. Around ambiguity and grammar constraints, I think in the end it's something you have to live with; a complex language with ambiguities or left-recursion is hard for both a machine to parse and for a human to parse, and should be avoided. This also relates to error handling, and, to some degree, error recovery, which is a very nice feature in a language grammar that allows you to generate some AST information (for the purposes of syntax highlighting or LSP features) even on incomplete or partially truncated code. Here I feel that there's a lot of room for languages to include assertions that serve "no value", like semicolon line endings -- one frustration often expressed by the anti-semicolon people is "the compiler can tell me when a semicolon is missing, let's just have the compiler put them in". I feel that this is misguided and interferes with the ideas of being able to continue parsing code with errors in it.
- johnday 8y ago
  > I do disagree with a lot of the other conclusions, especially operator precedence, which I've come to believe is generally a bad thing -- associativity can be fine (although even there I'm uncertain), but managing operator precedence is almost always better done by using parentheses. This is a very interesting take. I feel like there are many, many situations where relying on operator precedence is not only natural, but will cause the code to become less readable. Look at any language which uses many operators (my go-to would be Haskell) and consider readability of one over the other. Also what do you mean with associativity here? Associativity, as I know it, just means that (a+b+c) = (a+b)+c = a+(b+c). There's clearly no downside to that, right?
  - mattnewport 8y ago
    I'm not sure if this is what the OP meant but floating point addition is not necessarily associative and this can surprise people when the same code can produce different results where evaluation order is not guaranteed. If you require parentheses to determine evaluation order it might reduce surprises.
  - lacey 8y ago
    Usually operators are defined as being left-associative, right-associative, or non-associative. So e.g., a + b + c is interpreted as (a + b) + c because + is commonly left-associative whereas a ^ b ^ c is a ^ (b ^ c) because languages that support ^ for exponentiation treat it as right associative. For non-associative operators, parentheses are required if you have two operators at the same precedence, so I believe the grandparent is arguing that e.g. a + b - c should require parens to disbiguate in a language where + and - have the same precedence.
  - andrewla 8y ago
    Yes, you have associativity right. The question is what kind of price you pay. Allowing a user to type ‘a+b+c’ seems reasonable and forcing them to write ‘a+(b+c)’ seems draconian. But what does ‘a/b/c’ mean? Does your grammar have to have different productions for associative and non-associative binary operators? For general operator support do you have to have productions for every operator, or do you add a little bit of state to your parser outside the grammar to handle the lookback to determine if the same operator is being used? These are ugly decisions to make for the smallish benefit of being able to omit a couple of parentheses. And how often does it really occur outside of heavy numeric computations, which are kind of the minority. Some APLs go overboard here and just say that everything operates right to left so 2*3+4 is 14. This is super awkward but once you get used to it it’s kind of a relief to not have to think about operator precedence. Similarly RPN and Lisp dodge the issue. In my experience operator precedence causes actual bugs, but associativity rarely does. So despite all this I’m not firmly against associativity, but I’m getting there.
    - loup-vaillant 8y ago
      > These are ugly decisions to make for the smallish benefit of being able to omit a couple of parentheses. Careful there. We're not talking about one compiler writer and one user. There will be potentially many users. That little benefit of using parentheses will be multiplied across users (and across uses). Paying a large cost upfront to enjoy small but lasting benefits could very well be worth the cost. (Assuming the benefits are real of course. That would be a separate issue.)
- ltratt 8y ago
  > They correctly point out that error handling is by far the biggest one, and usually ends up being the biggest part of a parser for a language, full of crufts and strange mixtures of semantics and syntax. Add to this that you frequently want to try to partially recover -- make a guess as to what was intended and continue parsing in the hopes of finding more actionable errors later in the code. I agree. Personally, I ignored automated error handling in parsing for years because it seemed to be a lost cause. Eventually, I decided to look in more detail at it, and soon came across a rich vein of previous work that's been largely ignored / forgotten. I suspect that's because the approaches they proposed were too slow to be practical back in the day. After a bit of modernisation, it turns out that these techniques run more than fast enough on modern machines and can even be extended to do a better job than previous approaches attempted (draft paper at https://arxiv.org/abs/1804.07133 https://arxiv.org/abs/1804.07133 ; a more down-to-earth explanation of how to use the accompanying software at https://softdevteam.github.io/grmtools/master/book/errorrecovery.html https://softdevteam.github.io/grmtools/master/book/errorreco...). EDIT: fixed URL.
- WalkerCodeRangr 8y ago
  I'm the author of the post. With regard to operator precedence, my position may be closer to yours than you think. In the post I linked to about intransitive operator precedence (https://blog.adamant-lang.org/2019/operator-precedence/ https://blog.adamant-lang.org/2019/operator-precedence/) I describe what I want. Basically, I think basic order of operations like `*` before `+` and associativity are important. But in more complicated cases you should be forced to put in parentheses. Exactly where that line is drawn can be debated. What I want is a way of handling operator precedence that is more complicated under the hood, but should be more natural for the programmer as it will respect basic precedence, but not leave you guessing about confusing expressions. i.e. `a/b/c` could be illegal and require parentheses even though `a+b/c` doesn't.
  - andrewla 8y ago
    I think our positions are pretty close, I'm just coming around to the idea that any operator precedence at all is of dubious value. It's nice to write `a + b * c` and have it parsed the "right" way, but I've become fairly comfortable with the idea of getting rid of that. To always require parentheses. I don't think writing `a + (b * c)` is that terrible. `a + b == c` is a little more annoying as `(a + b) == c`. Where I think the worst cases are is addition/subtraction, since those are so primitive -- subtraction can be thought of as addition of a negation, and in that form it is directly associative with addition. Indexing into arrays with constructs like `x[a + b - 1]` is incredibly common, and here almost any parenthesization makes it look like it has meaning -- if you see code that says `x[(a + b) - 1]`, is that a different intent than `x[a + (b - 1)]`? It feels different to me; `x[(start + offset) - 1]` is an adjustment, but `x[start + (first_comma - 1)]` is finding the location before an offset. On associativity I think this gets even worse; if you have to parenthesize `a + b + c` then it feels like the language is getting in your way, just by force of habit. Nobody blinks at the idea of deciding between `a b + c +` vs. `a b c + +` in a stack language, so maybe people would just get used to typing `a + (b + c)` and it would just fade into the background. This is all kind of rambly; my general feeling about computer languages is what I said above -- the harder it is for a machine to parse, the harder it is for a person to read; but some idioms are just so ingrained that it's hard to even recognize that you're making assumptions about associativity; and I venture there's a significant class of programmers who don't know what associativity is in any formal sense but routinely use the property because it's so ingrained in how we are taught to calculate.
seanmcdirmid 8y ago
Hand-written recursive descent isn't that bad: it isn't that hard to implement, it gives you lots of control over error recovery, you don't have to worry about how ambiguity is handled (well, you deal with it on your own), and you don't have to worry about interfacing with the rest of your compiler/interpreter pipeline. The tradeoff is that you write some more code and parser performance is less optimized. Considering everything else that happens in a modern compiler, parser performance is in the noise anyways. There are good reasons why most production languages are implemented with hand written parsers. Generators are a bit of a convenience, but come with too many drawbacks.
- Q6T46nT668w6i3m 8y ago
  In my experience, source problems like parsing and linking are still the major costs in compiler performance. I love this article by Walter Bright on the subject: http://www.drdobbs.com/cpp/c-compilation-speed/228701711 http://www.drdobbs.com/cpp/c-compilation-speed/228701711
  - seanmcdirmid 8y ago
    C++ is slow for many reasons, being really hard to parse is just one of them. Languages with recursive descent parsers are bound to have simpler syntaxes; eg many (though definitely not all) avoid ambiguity like using < and > as both operators and braces.
- jstimpfle 8y ago
  In absence of heavy compiler optimizations, parsing consumes about 50% of the compilation time for simple C-style languages. Source: my own experiments. Seems to agree with http://doc.cat-v.org/bell_labs/pikestyle http://doc.cat-v.org/bell_labs/pikestyle (see last section), but note that text was written in 1989.
  - munificent 8y ago
    That's maybe true for simple C-style languages but very likely not near true for modern statically typed languages that freely allow forward declarations and have type inference.
lsh 8y ago
Aren't s-expressions all one really needs?
- krapp 8y ago
  No. Any Lisp you can name has more to it than just s-expressions.
  - cellularmitosis 8y ago
    His point still stands. The ruby parser has 10x the number of lines of code as the clojure parser. https://github.com/ruby/ruby/blob/trunk/parse.y https://github.com/ruby/ruby/blob/trunk/parse.y https://github.com/clojure/tools.reader/blob/master/src/main/clojure/clojure/tools/reader.clj https://github.com/clojure/tools.reader/blob/master/src/main...
    - lispm 8y ago
      Because one parses a data format and the other one an actual programming language...
      - cellularmitosis 8y ago
        Sorry, I linked to the wrong edn reader https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/EdnReader.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...
        lispm 8y ago
        That's still only an s-expression reader, not a programming language parser.
        cellularmitosis 8y ago
        Can you help me understand the distinction you are making? My understanding is that this is the reader used by the repl, and at least for clojure, an edn parser is the same thing as a programming language parser, because clojure programs are written in edn.
scythe 8y ago
I think the reason this happens is that parser generators are probably never (ignoring AGI etc) going to produce code as fast and debugger-friendly as a human being. A really good parser generator might be a good way to "mock up" the design of a language, but for anything that gets used in production, the benefits of hand-rolling your parser will probably always outweigh the costs by a large margin: it's crucial code that affects thousands of projects, so it really should be perfect.
- cwzwarich 8y ago
  I don't think the performance part of your statement is true. There exist techniques for generating extremely efficient LR automata (e.g. https://link.springer.com/article/10.1007/BF00267043 https://link.springer.com/article/10.1007/BF00267043) where the equivalent handwritten code would be a goto-ridden mess.
anth_anm 8y ago
Just skimmed it, but using a good parser combinator library sounds like a lot of what the author wants.
austincheney 8y ago
The paper author understates the importance of composability. > While having a tool that supports combining grammars would be handy, I don’t see it as a must-have. In practice, languages are not combined very often. That was once true, but not any more. Intermixing of grammars within a single code instance is becoming more normal, and in many cases it is now the norm. The inability to accept this new norm leaves you holding a bag of multiple parsers and a large amount of processing overhead with a loss of flexibility on how to manage the entirety of the code. It is a horrid mess to deal with a collection of unrelated and nested ASTs to represent a single code instance. > If the languages being combined are radically different, then for the sake of the programmer, there will probably need to be unambiguous delimiters at the transitions between the languages. A faulty assumption that often does not reflect reality. By focusing on composability first you remove many design barriers that limit or prevent design decisions down the line. --- The fault of many parsers, from a design perspective, are a heavy concern for goals outside of parsing, frequently either a compile step or the shape of the AST. A compile operation is completely independent of a parse operation. Once an AST is created a consuming compiler will execute on it. Keep these concerns separate. Don't force your parser to act as a proxy for the limitations of your compiler. A flexible and well reasoned parser can return an AST is a variety of shapes/formats. It doesn't really matter so long as the data structure is well reasoned and in a way the consuming application understands. Also performance is not well understood in many cases of parsing, which is probably why parsers are often intermingled with the concerns of compilers. A parse operation takes time. It also takes different unrelated time for a consuming application to consume the AST. The speed with which a parse tree is generated is unrelated to the speed with which it is read. This is why composability is more important the paper gives credit for. If anybody is interested I am working on addressing some of these concerns at https://sparser.io/ https://sparser.io/ which is a personal pet project. It doesn't cure cancer or solve world hunger yet (I am just one guy with a job), but the concept does solve some design problems and composability issues associated with parsing.
- tlb 8y ago
  I'm working on a language that embeds Javascript. Javascript syntax makes it quite easy to find the end of a complete block by considering just parens, brackets, braces, strings, and comments. Then I can just pass the string to a JS interpreter. So it's easy to allow javascript { ...any valid javascript code... } C++ syntax, on the other hand, makes it very hard to delimit a block. For instance, it's hard to guess whether a > is an operator or the end of a template parameter list. And preprocessor macros mean that the entire context of all the includes files before the current point can change what any token means. I think a good goal for a syntax is to make it easy to delimit blocks without a complete parser. It also makes syntax highlighting practical.
jheriko 8y ago
yeah, i started working on something to try and address the fact that all of the tools in this space are steaming hot garbage... after struggling to build a new language myself with various and finding it was possible, but the resulting toolchain was terrible and bug-prone. its a shame given how fantastic llvm is for the backend problem that all of the lexer/parser tools are terrible. its very easy to produce much better interfaces and errors than ... well... everything i have been able to find including antlr, flex, bison, haskell parser combinator libraries... an afternoon of lazy work without especially strenuous thought is more than enough. but performance is hard, especially given the appalling quality of the academic literature and example code for the various algorithms. but for proving the point it is not especially important... its not a great example... its garbage code, but here it is, able to generate itself and all the usual hoo hah... complete with a scheme shat out with it in 2 hours instead of the usual mundane 24... https://bitbucket.org/craniumsoftware/cp2/src/c6eb20ce4c05fce595337a646ff3a0e1a99167e2/?at=semi%2Fwork https://bitbucket.org/craniumsoftware/cp2/src/c6eb20ce4c05fc... the parser is awful. i wrote my own totally generic algorithm (can't remember if i solved the left recursion, but its totally do-able) based on conjuring obvious solutions without thinking very much... i keep thinking it would be nice to take it further, or even to impart the wisdom to those continuing to develop the garbage. if only i had the resources and time... (generates shitty vs integrations too) .. no reason this couldn't be extended to remove the c++ and add functionality to describe language features and generate llvm from that. (oh and naturally the lexer and parser come from the same data, because why make two things where one does a considerably better job and removes a huge source of bugs)
xitrium 8y ago
Curious if the author could comment on what Menhir is lacking, my estimation is possibly just the concrete syntax trees, though you could definitely emit an AST that has as much of that as you need to do the tasks the author mentions.
- WalkerCodeRangr 8y ago
  Author here. I don't have any direct experience with Menhir because I haven't tried to write a compiler in OCaml yet. It does seem to be one of the better parser generators and is frequently recommended. Skimming the docs, its seems to be lacking in these areas: * Concrete syntax trees (as you pointed out) * LR(1) will probably still be more restrictive than I want * Unicode support (defaults to ocamllex, requires custom code to use ulex) * Intransitive Operator Precedence isn't supported (though it does have regular precedence levels and associativity) * While it looks to have better error handling than most LR parser generators, I suspect it still isn't where I'd want it to be. I suspect there are other issues, but I don't want to go any further beyond my knowledge base than I already have. I've been thinking about writing on this topic more, if I do, then I might address this more.
  - xitrium 8y ago
    Thanks! The new .messages error message mechanism is great, though we'll see if it supports the full brunt of user needs soon enough.
bd82 8y ago
I've created a Parsing Toolkit (for JavaScript) which I believe fulfills 7/10 of the requirements described. Chevrotain - https://github.com/SAP/chevrotain https://github.com/SAP/chevrotain The list of features can be found here: - https://sap.github.io/chevrotain/docs/features/blazing_fast.html https://sap.github.io/chevrotain/docs/features/blazing_fast.... What is interesting imho is that Chevrotain is not a Parser Generator nor a Parser Combinator. It is a tool that makes it easier to craft hand built recursive decent parsers rather than a whole new level of abstraction.
fjfaase 8y ago
I developed a small interpretting parser, which you can give a grammar on the input and a file to be parsed. It parsers the grammar (with itself) and parsers the input file according to the grammar specification. No need to run a code generator and a compiler before testing a change in the grammar. It uses a recursive decent back-tracking parser which because it uses memorization, works quite fast. See http://github.com/FransFaase/IParse http://github.com/FransFaase/IParse

117 points by matt_d 8y ago

This is an excellent survey of many of the issues facing modern parsers. They correctly point out that error handling is by far the biggest one, and usually ends up being the biggest part of a parser for a language, full of crufts and strange mixtures of semantics and syntax. Add to this that you frequently want to try to partially recover -- make a guess as to what was intended and continue parsing in the hopes of finding more actionable errors later in the code. I do disagree with a lot of the other conclusions, especially operator precedence, which I've come to believe is generally a bad thing -- associativity can be fine (although even there I'm uncertain), but managing operator precedence is almost always better done by using parentheses. I like scannerless, but the author makes a lot of good points that I might have to rethink. The analogy to how people read makes some sense, but I'm not sure there's as crisp a line between syntax and semantics as that analogy would imply in natural languages. Around ambiguity and grammar constraints, I think in the end it's something you have to live with; a complex language with ambiguities or left-recursion is hard for both a machine to parse and for a human to parse, and should be avoided. This also relates to error handling, and, to some degree, error recovery, which is a very nice feature in a language grammar that allows you to generate some AST information (for the purposes of syntax highlighting or LSP features) even on incomplete or partially truncated code. Here I feel that there's a lot of room for languages to include assertions that serve "no value", like semicolon line endings -- one frustration often expressed by the anti-semicolon people is "the compiler can tell me when a semicolon is missing, let's just have the compiler put them in". I feel that this is misguided and interferes with the ideas of being able to continue parsing code with errors in it.

johnday 8y ago
> I do disagree with a lot of the other conclusions, especially operator precedence, which I've come to believe is generally a bad thing -- associativity can be fine (although even there I'm uncertain), but managing operator precedence is almost always better done by using parentheses. This is a very interesting take. I feel like there are many, many situations where relying on operator precedence is not only natural, but will cause the code to become less readable. Look at any language which uses many operators (my go-to would be Haskell) and consider readability of one over the other. Also what do you mean with associativity here? Associativity, as I know it, just means that (a+b+c) = (a+b)+c = a+(b+c). There's clearly no downside to that, right?
- mattnewport 8y ago
  I'm not sure if this is what the OP meant but floating point addition is not necessarily associative and this can surprise people when the same code can produce different results where evaluation order is not guaranteed. If you require parentheses to determine evaluation order it might reduce surprises.
- lacey 8y ago
  Usually operators are defined as being left-associative, right-associative, or non-associative. So e.g., a + b + c is interpreted as (a + b) + c because + is commonly left-associative whereas a ^ b ^ c is a ^ (b ^ c) because languages that support ^ for exponentiation treat it as right associative. For non-associative operators, parentheses are required if you have two operators at the same precedence, so I believe the grandparent is arguing that e.g. a + b - c should require parens to disbiguate in a language where + and - have the same precedence.
- andrewla 8y ago
  Yes, you have associativity right. The question is what kind of price you pay. Allowing a user to type ‘a+b+c’ seems reasonable and forcing them to write ‘a+(b+c)’ seems draconian. But what does ‘a/b/c’ mean? Does your grammar have to have different productions for associative and non-associative binary operators? For general operator support do you have to have productions for every operator, or do you add a little bit of state to your parser outside the grammar to handle the lookback to determine if the same operator is being used? These are ugly decisions to make for the smallish benefit of being able to omit a couple of parentheses. And how often does it really occur outside of heavy numeric computations, which are kind of the minority. Some APLs go overboard here and just say that everything operates right to left so 2*3+4 is 14. This is super awkward but once you get used to it it’s kind of a relief to not have to think about operator precedence. Similarly RPN and Lisp dodge the issue. In my experience operator precedence causes actual bugs, but associativity rarely does. So despite all this I’m not firmly against associativity, but I’m getting there.
  - loup-vaillant 8y ago
    > These are ugly decisions to make for the smallish benefit of being able to omit a couple of parentheses. Careful there. We're not talking about one compiler writer and one user. There will be potentially many users. That little benefit of using parentheses will be multiplied across users (and across uses). Paying a large cost upfront to enjoy small but lasting benefits could very well be worth the cost. (Assuming the benefits are real of course. That would be a separate issue.)
ltratt 8y ago
> They correctly point out that error handling is by far the biggest one, and usually ends up being the biggest part of a parser for a language, full of crufts and strange mixtures of semantics and syntax. Add to this that you frequently want to try to partially recover -- make a guess as to what was intended and continue parsing in the hopes of finding more actionable errors later in the code. I agree. Personally, I ignored automated error handling in parsing for years because it seemed to be a lost cause. Eventually, I decided to look in more detail at it, and soon came across a rich vein of previous work that's been largely ignored / forgotten. I suspect that's because the approaches they proposed were too slow to be practical back in the day. After a bit of modernisation, it turns out that these techniques run more than fast enough on modern machines and can even be extended to do a better job than previous approaches attempted (draft paper at https://arxiv.org/abs/1804.07133 https://arxiv.org/abs/1804.07133 ; a more down-to-earth explanation of how to use the accompanying software at https://softdevteam.github.io/grmtools/master/book/errorrecovery.html https://softdevteam.github.io/grmtools/master/book/errorreco...). EDIT: fixed URL.
WalkerCodeRangr 8y ago
I'm the author of the post. With regard to operator precedence, my position may be closer to yours than you think. In the post I linked to about intransitive operator precedence (https://blog.adamant-lang.org/2019/operator-precedence/ https://blog.adamant-lang.org/2019/operator-precedence/) I describe what I want. Basically, I think basic order of operations like `*` before `+` and associativity are important. But in more complicated cases you should be forced to put in parentheses. Exactly where that line is drawn can be debated. What I want is a way of handling operator precedence that is more complicated under the hood, but should be more natural for the programmer as it will respect basic precedence, but not leave you guessing about confusing expressions. i.e. `a/b/c` could be illegal and require parentheses even though `a+b/c` doesn't.
- andrewla 8y ago
  I think our positions are pretty close, I'm just coming around to the idea that any operator precedence at all is of dubious value. It's nice to write `a + b * c` and have it parsed the "right" way, but I've become fairly comfortable with the idea of getting rid of that. To always require parentheses. I don't think writing `a + (b * c)` is that terrible. `a + b == c` is a little more annoying as `(a + b) == c`. Where I think the worst cases are is addition/subtraction, since those are so primitive -- subtraction can be thought of as addition of a negation, and in that form it is directly associative with addition. Indexing into arrays with constructs like `x[a + b - 1]` is incredibly common, and here almost any parenthesization makes it look like it has meaning -- if you see code that says `x[(a + b) - 1]`, is that a different intent than `x[a + (b - 1)]`? It feels different to me; `x[(start + offset) - 1]` is an adjustment, but `x[start + (first_comma - 1)]` is finding the location before an offset. On associativity I think this gets even worse; if you have to parenthesize `a + b + c` then it feels like the language is getting in your way, just by force of habit. Nobody blinks at the idea of deciding between `a b + c +` vs. `a b c + +` in a stack language, so maybe people would just get used to typing `a + (b + c)` and it would just fade into the background. This is all kind of rambly; my general feeling about computer languages is what I said above -- the harder it is for a machine to parse, the harder it is for a person to read; but some idioms are just so ingrained that it's hard to even recognize that you're making assumptions about associativity; and I venture there's a significant class of programmers who don't know what associativity is in any formal sense but routinely use the property because it's so ingrained in how we are taught to calculate.

seanmcdirmid 8y ago

Hand-written recursive descent isn't that bad: it isn't that hard to implement, it gives you lots of control over error recovery, you don't have to worry about how ambiguity is handled (well, you deal with it on your own), and you don't have to worry about interfacing with the rest of your compiler/interpreter pipeline. The tradeoff is that you write some more code and parser performance is less optimized. Considering everything else that happens in a modern compiler, parser performance is in the noise anyways. There are good reasons why most production languages are implemented with hand written parsers. Generators are a bit of a convenience, but come with too many drawbacks.

Q6T46nT668w6i3m 8y ago
In my experience, source problems like parsing and linking are still the major costs in compiler performance. I love this article by Walter Bright on the subject: http://www.drdobbs.com/cpp/c-compilation-speed/228701711 http://www.drdobbs.com/cpp/c-compilation-speed/228701711
- seanmcdirmid 8y ago
  C++ is slow for many reasons, being really hard to parse is just one of them. Languages with recursive descent parsers are bound to have simpler syntaxes; eg many (though definitely not all) avoid ambiguity like using < and > as both operators and braces.
jstimpfle 8y ago
In absence of heavy compiler optimizations, parsing consumes about 50% of the compilation time for simple C-style languages. Source: my own experiments. Seems to agree with http://doc.cat-v.org/bell_labs/pikestyle http://doc.cat-v.org/bell_labs/pikestyle (see last section), but note that text was written in 1989.
- munificent 8y ago
  That's maybe true for simple C-style languages but very likely not near true for modern statically typed languages that freely allow forward declarations and have type inference.

lsh 8y ago

Aren't s-expressions all one really needs?

krapp 8y ago
No. Any Lisp you can name has more to it than just s-expressions.
- cellularmitosis 8y ago
  His point still stands. The ruby parser has 10x the number of lines of code as the clojure parser. https://github.com/ruby/ruby/blob/trunk/parse.y https://github.com/ruby/ruby/blob/trunk/parse.y https://github.com/clojure/tools.reader/blob/master/src/main/clojure/clojure/tools/reader.clj https://github.com/clojure/tools.reader/blob/master/src/main...
  - lispm 8y ago
    Because one parses a data format and the other one an actual programming language...
    - cellularmitosis 8y ago
      Sorry, I linked to the wrong edn reader https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/EdnReader.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...
      - lispm 8y ago
        That's still only an s-expression reader, not a programming language parser.
        cellularmitosis 8y ago
        Can you help me understand the distinction you are making? My understanding is that this is the reader used by the repl, and at least for clojure, an edn parser is the same thing as a programming language parser, because clojure programs are written in edn.

scythe 8y ago

I think the reason this happens is that parser generators are probably never (ignoring AGI etc) going to produce code as fast and debugger-friendly as a human being. A really good parser generator might be a good way to "mock up" the design of a language, but for anything that gets used in production, the benefits of hand-rolling your parser will probably always outweigh the costs by a large margin: it's crucial code that affects thousands of projects, so it really should be perfect.

cwzwarich 8y ago
I don't think the performance part of your statement is true. There exist techniques for generating extremely efficient LR automata (e.g. https://link.springer.com/article/10.1007/BF00267043 https://link.springer.com/article/10.1007/BF00267043) where the equivalent handwritten code would be a goto-ridden mess.

anth_anm 8y ago

Just skimmed it, but using a good parser combinator library sounds like a lot of what the author wants.

austincheney 8y ago

The paper author understates the importance of composability. > While having a tool that supports combining grammars would be handy, I don’t see it as a must-have. In practice, languages are not combined very often. That was once true, but not any more. Intermixing of grammars within a single code instance is becoming more normal, and in many cases it is now the norm. The inability to accept this new norm leaves you holding a bag of multiple parsers and a large amount of processing overhead with a loss of flexibility on how to manage the entirety of the code. It is a horrid mess to deal with a collection of unrelated and nested ASTs to represent a single code instance. > If the languages being combined are radically different, then for the sake of the programmer, there will probably need to be unambiguous delimiters at the transitions between the languages. A faulty assumption that often does not reflect reality. By focusing on composability first you remove many design barriers that limit or prevent design decisions down the line. --- The fault of many parsers, from a design perspective, are a heavy concern for goals outside of parsing, frequently either a compile step or the shape of the AST. A compile operation is completely independent of a parse operation. Once an AST is created a consuming compiler will execute on it. Keep these concerns separate. Don't force your parser to act as a proxy for the limitations of your compiler. A flexible and well reasoned parser can return an AST is a variety of shapes/formats. It doesn't really matter so long as the data structure is well reasoned and in a way the consuming application understands. Also performance is not well understood in many cases of parsing, which is probably why parsers are often intermingled with the concerns of compilers. A parse operation takes time. It also takes different unrelated time for a consuming application to consume the AST. The speed with which a parse tree is generated is unrelated to the speed with which it is read. This is why composability is more important the paper gives credit for. If anybody is interested I am working on addressing some of these concerns at https://sparser.io/ https://sparser.io/ which is a personal pet project. It doesn't cure cancer or solve world hunger yet (I am just one guy with a job), but the concept does solve some design problems and composability issues associated with parsing.

tlb 8y ago
I'm working on a language that embeds Javascript. Javascript syntax makes it quite easy to find the end of a complete block by considering just parens, brackets, braces, strings, and comments. Then I can just pass the string to a JS interpreter. So it's easy to allow javascript { ...any valid javascript code... } C++ syntax, on the other hand, makes it very hard to delimit a block. For instance, it's hard to guess whether a > is an operator or the end of a template parameter list. And preprocessor macros mean that the entire context of all the includes files before the current point can change what any token means. I think a good goal for a syntax is to make it easy to delimit blocks without a complete parser. It also makes syntax highlighting practical.

jheriko 8y ago

yeah, i started working on something to try and address the fact that all of the tools in this space are steaming hot garbage... after struggling to build a new language myself with various and finding it was possible, but the resulting toolchain was terrible and bug-prone. its a shame given how fantastic llvm is for the backend problem that all of the lexer/parser tools are terrible. its very easy to produce much better interfaces and errors than ... well... everything i have been able to find including antlr, flex, bison, haskell parser combinator libraries... an afternoon of lazy work without especially strenuous thought is more than enough. but performance is hard, especially given the appalling quality of the academic literature and example code for the various algorithms. but for proving the point it is not especially important... its not a great example... its garbage code, but here it is, able to generate itself and all the usual hoo hah... complete with a scheme shat out with it in 2 hours instead of the usual mundane 24... https://bitbucket.org/craniumsoftware/cp2/src/c6eb20ce4c05fce595337a646ff3a0e1a99167e2/?at=semi%2Fwork https://bitbucket.org/craniumsoftware/cp2/src/c6eb20ce4c05fc... the parser is awful. i wrote my own totally generic algorithm (can't remember if i solved the left recursion, but its totally do-able) based on conjuring obvious solutions without thinking very much... i keep thinking it would be nice to take it further, or even to impart the wisdom to those continuing to develop the garbage. if only i had the resources and time... (generates shitty vs integrations too) .. no reason this couldn't be extended to remove the c++ and add functionality to describe language features and generate llvm from that. (oh and naturally the lexer and parser come from the same data, because why make two things where one does a considerably better job and removes a huge source of bugs)

xitrium 8y ago

Curious if the author could comment on what Menhir is lacking, my estimation is possibly just the concrete syntax trees, though you could definitely emit an AST that has as much of that as you need to do the tasks the author mentions.

WalkerCodeRangr 8y ago
Author here. I don't have any direct experience with Menhir because I haven't tried to write a compiler in OCaml yet. It does seem to be one of the better parser generators and is frequently recommended. Skimming the docs, its seems to be lacking in these areas: * Concrete syntax trees (as you pointed out) * LR(1) will probably still be more restrictive than I want * Unicode support (defaults to ocamllex, requires custom code to use ulex) * Intransitive Operator Precedence isn't supported (though it does have regular precedence levels and associativity) * While it looks to have better error handling than most LR parser generators, I suspect it still isn't where I'd want it to be. I suspect there are other issues, but I don't want to go any further beyond my knowledge base than I already have. I've been thinking about writing on this topic more, if I do, then I might address this more.
- xitrium 8y ago
  Thanks! The new .messages error message mechanism is great, though we'll see if it supports the full brunt of user needs soon enough.

bd82 8y ago

I've created a Parsing Toolkit (for JavaScript) which I believe fulfills 7/10 of the requirements described. Chevrotain - https://github.com/SAP/chevrotain https://github.com/SAP/chevrotain The list of features can be found here: - https://sap.github.io/chevrotain/docs/features/blazing_fast.html https://sap.github.io/chevrotain/docs/features/blazing_fast.... What is interesting imho is that Chevrotain is not a Parser Generator nor a Parser Combinator. It is a tool that makes it easier to craft hand built recursive decent parsers rather than a whole new level of abstraction.

fjfaase 8y ago

I developed a small interpretting parser, which you can give a grammar on the input and a file to be parsed. It parsers the grammar (with itself) and parsers the input file according to the grammar specification. No need to run a code generator and a compiler before testing a change in the grammar. It uses a recursive decent back-tracking parser which because it uses memorization, works quite fast. See http://github.com/FransFaase/IParse http://github.com/FransFaase/IParse