4 ms·

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 en

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.

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.