5 ms·

Could you explain in more detail what you mean about LALR error messages? I haven't used the parser generators you mention but I've implemented LALR parsing bef

Could you explain in more detail what you mean about LALR error messages? I haven't used the parser generators you mention but I've implemented LALR parsing before, the error reporting situation doesn't seem drastically different from recursive descent to me. You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. Is the problem that these specific tools (yacc/bison) don't report errors well? Or is the issue you're talking about that LR grammars will fail later on than LL grammars in general? Or the greater ambiguity (e.g. more possible lookaheads due to the greater parsing power)?

chrisseaton 8y ago
> You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. This is a garbage 'computer says no' kind of error message. It doesn't tell you why those tokens would have been allowed to follow, why it is that those are the only tokens allowed to follow, why the token you used is not one of the allowed one, or what you could have more likely been intending to write to make it correct. In a recursive descent parser you have the freedom to use more context and logic to generate your error messages.
- jhpriestley 8y ago
  What context or data would constitute a helpful error message in your opinion? Do you have an example of a recursive-descent parser that generates particularly good error messages?
  - chrisseaton 8y ago
    A great example is if you forget to put 'end' at the end of a function at the end of a file in languages that have that. Your idea of a good parser error message is being told that the end of file was unexpected and being given a list of a hundred possible tokens that could start another statement, including 'end' buried somewhere in the list, because that's what's valid there. My idea of a good parser error message would be in a recursive descent parser looking for the 'end' token, not seeing it, seeing that it's end of file instead and saying 'missing 'end' or a new statement at end of file'.
  - nicoburns 8y ago
    See elm and rust for examples of compilers with good error messages.
    - grandmczeb 8y ago
      Or clang.
nickpsecurity 8y ago
I'll also add you can use two parsers: one that's super fast on code that's correctly written; if that fails, one that makes error messages easy to handle. sklogic said he used that strategy in his tools for program analysis. The extra code is negligible. I don't know how much extra time or maintenance burden but I figured marginal versus cost of handling errors in first place.
- lihaoyi 8y ago
  My FastParse (https://www.lihaoyi.com/fastparse/ https://www.lihaoyi.com/fastparse/) parser combinator library does this; by default it runs without error logging, just giving you an error position, but if something fails you can ask it to re-do the parse keeping track of additional metadata to give you a nice error message with what tokens could have succeeded and a stack trace telling you why wants those tokens. Tracing errors slows things down about 2x, which is why it isnt on by default, on the assumption that most parses are successful
dbcurtis 8y ago
A bottom up parser such as LALR knows what it has built successfully, and knows that the next token makes no sense in the current state. So you have stuff in the parse stack that is headed somewhere but you don't know where, and you know you are at the earliest point you can detect a syntax error. Unless you rummage around in the parse stack for clues, there really isn't much you can do to make a good message, and the rummaging is often ad-hoc. When parsing top-down as in recursive descent, you know what higher level syntactic structure you are in the middle of constructing, and anything successfully parsed so far is probably slotted into the AST in a meaningful way, so you simply have a lot more context to go on when constructing a message, and that context is an intuitive AST walk away.

chrisseaton 8y ago

> You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. This is a garbage 'computer says no' kind of error message. It doesn't tell you why those tokens would have been allowed to follow, why it is that those are the only tokens allowed to follow, why the token you used is not one of the allowed one, or what you could have more likely been intending to write to make it correct. In a recursive descent parser you have the freedom to use more context and logic to generate your error messages.

jhpriestley 8y ago
What context or data would constitute a helpful error message in your opinion? Do you have an example of a recursive-descent parser that generates particularly good error messages?
- chrisseaton 8y ago
  A great example is if you forget to put 'end' at the end of a function at the end of a file in languages that have that. Your idea of a good parser error message is being told that the end of file was unexpected and being given a list of a hundred possible tokens that could start another statement, including 'end' buried somewhere in the list, because that's what's valid there. My idea of a good parser error message would be in a recursive descent parser looking for the 'end' token, not seeing it, seeing that it's end of file instead and saying 'missing 'end' or a new statement at end of file'.
- nicoburns 8y ago
  See elm and rust for examples of compilers with good error messages.
  - grandmczeb 8y ago
    Or clang.

nickpsecurity 8y ago

I'll also add you can use two parsers: one that's super fast on code that's correctly written; if that fails, one that makes error messages easy to handle. sklogic said he used that strategy in his tools for program analysis. The extra code is negligible. I don't know how much extra time or maintenance burden but I figured marginal versus cost of handling errors in first place.

lihaoyi 8y ago
My FastParse (https://www.lihaoyi.com/fastparse/ https://www.lihaoyi.com/fastparse/) parser combinator library does this; by default it runs without error logging, just giving you an error position, but if something fails you can ask it to re-do the parse keeping track of additional metadata to give you a nice error message with what tokens could have succeeded and a stack trace telling you why wants those tokens. Tracing errors slows things down about 2x, which is why it isnt on by default, on the assumption that most parses are successful

dbcurtis 8y ago

A bottom up parser such as LALR knows what it has built successfully, and knows that the next token makes no sense in the current state. So you have stuff in the parse stack that is headed somewhere but you don't know where, and you know you are at the earliest point you can detect a syntax error. Unless you rummage around in the parse stack for clues, there really isn't much you can do to make a good message, and the rummaging is often ad-hoc. When parsing top-down as in recursive descent, you know what higher level syntactic structure you are in the middle of constructing, and anything successfully parsed so far is probably slotted into the AST in a meaningful way, so you simply have a lot more context to go on when constructing a message, and that context is an intuitive AST walk away.