6 ms·

I like the idea of specifying a parser through a formal grammar but I think that current technology has a few pretty annoying-severe flaws. * Parser generato

• moring 4y ago
  I disagree to some extent: > Parser generator grammars are usually quite far from 'paper' versions The more useful of parser input formats allow precedence and associativitiy annotations as well as optionals, quantifiers and quantifiers with separators. This really only works great together with your third point, > Parser files are usually fairly illegible because they mix host language code with parser syntax You don't need host code if the parser just outputs an AST. Neither quantifiers with or without separators nor optionals make the parser spec more complex if no host code is needed -- the complexity is in the parser generator and AST generator. > Error messages suck I found error messages okay-ish when you view them in an IDE where it is more important where an error occurred than what exactly is wrong (only applies to syntax errors). I also found it helpful to show the allowed input at that place that would NOT have resulted in a syntax error -- and the parser generator can emit a list of both terminals and nonterminals automatically, because this information is used by it to detect a syntax error in the first place. I also tripped over the often-said problem that LALR parsers produce less useful error messages than LR(1) parsers. In today's time, just using LR(1) is underrated IMHO. In my experiments, the table didn't get too large (400kB parse table for a simple hardware-description language) and I would have tried to apply compression algorithms on the table instead of resorting to LALR, but that size was small enough to be acceptable to me. Only the run time of the table generation process was a bit annoying (10-20 seconds).
  • HarHarVeryFunny 4y ago
    Your experience with the usefulness of error messages from top-down (recursive descent) vs bottom-up (table-driven) parsers is opposite to common experience. The trouble with bottom-up parsers is that they inherently (by way of being bottom-up) have no top-down context, so all they can by default generate is a bottom-up "symbol XXX expected" type error. A top down parser knows what high level construct it's trying to parse, so is in a position to generate a more meaningful error. Of course in either case the grammar could be augmented with thoughtful error constructs designed to generate meaningful errors when parsed, but that doesn't seem to be common practice given how awful compiler error messages tend to be. Try writing "std::cout" instead of "std::endl" and see what gibberish error message g++ generates. clang is generally better than g++ in this regard.
    • moring 4y ago
      I can't speak about common experience, only my own, but that tells me that an LR(1) can tell which high-level construct it is trying to parse -- this is encoded in the states deeper down in the parse stack, and therefore depends on information which the parser/generator already has. While to some extent, this may be ambiguous because it depends on tokens further to the right, this is inherent in the "L" part of LR and applies to LL as well; only raising the lookahead length can fix that. Now I did cheat a bit in what I said above: Parsing further terminal symbols "removes" the high-level information from the state, and then it cannot be used for error messages anymore. This has to notable aspects: First, one can simply keep such information as metadata, either encoded in the state (but this blows up table size because states cannot be merged as easily anymore) or as additional information collected while parsing (probably better -- good idea, I'll have to look at this). () Second, there is the question whether this information is really useful in producing better error messages. An input fragment like "(5 + )" is an incomplete expression, and without further metadata you know that (1) another sub-expression has to appear before the closing parenthesis, (2) you are parsing an expression, (3) you are parsing a high-level construct that expects an expression (this knowledge is inherent in LR(1)), but you don't* know anymore what high-level construct you are parsing anymore -- but for the error message it is probably irrelevant. Obviously, that last part depends, case by case. (*) re-reading that, I'll have to admit that this incorporates top-down aspects into the parser :)
• logicalshift 4y ago
  I wrote a parser generator quite a long time ago that I think improves the syntax quite a lot, and which has an interesting approach to generalisation: you can write conditions on the lookahead (which are just grammars that need to be matched in order to pick a given rule when a conflict needs to be resolved). This construct makes it much easier to write a grammar that matches how a language is designed. Here's an ANSI-C parser, for example: https://github.com/Logicalshift/TameParse/blob/master/Examples/AnsiC.tp https://github.com/Logicalshift/TameParse/blob/master/Exampl... - this is an interesting example because `(foo)(bar)` is fully ambiguous in ANSI C: it can be a cast or a function call depending on if `foo` is a type or a variable. The new construct makes it possible to extend grammars and disambiguate them - here's a C99 grammar that extends the ANSI-C grammar: https://github.com/Logicalshift/TameParse/blob/master/Examples/C99.tp https://github.com/Logicalshift/TameParse/blob/master/Exampl.... It also allows matching at least some context-sensitive languages - see https://github.com/Logicalshift/TameParse/blob/master/Examples/ContextSensitive.tp https://github.com/Logicalshift/TameParse/blob/master/Exampl... An advantage over GLR or backtracking approaches is that this still detects ambiguities in the language so it's much easier to write a grammar that doesn't end up running in exponential time or space, plus when an ambiguity is resolved by the generalisation, which version is specified by the grammar and is not arbitrary (backtracking) or left until later (GLR). I was working on improving error handling when I stopped work on this, but my approach here was not working out. (This is a long-abandoned project of mine but the approach to ambiguities and the syntax seem like they're novel to me and were definitely an improvement over anything else I found at the time. The lexer language has a few neat features in it too)