4 ms·

Early and similar algorithms give you a parse forest rather than a parse tree. For a programming language you don't want to have your grammar be ambiguous. When

Early and similar algorithms give you a parse forest rather than a parse tree. For a programming language you don't want to have your grammar be ambiguous. When Early gives you a bunch of alternative parse trees, how do you disambiguate?

billconan 5y ago
in my implementation, I give each rule a priority. I always choose the one with the highest priority to expand. I basically followed this https://loup-vaillant.fr/tutorials/earley-parsing/parser https://loup-vaillant.fr/tutorials/earley-parsing/parser
- xyzzy_plugh 5y ago
  I've written parsers for context-sensitive grammars, and as it turns out, this is not a desirable feature of a language. The reason you typically see simple parsers is because simple grammars are usually unambiguous and context-free, which is more convenient for humans to understand and internalize. After all, when you're writing software, you pretend to be the compiler to some extent. Natural languages, like English, are a good example of something which humans struggle with because they are complex, ambiguous, and often require context. Sure, it's extremely expressive, but that is the sharpest double-edged sword in programming languages.
- sirwhinesalot 5y ago
  Neat, though this just seems like PEG with extra steps and more pain. Still this answers my question. Thanks!
pfdietz 5y ago
If you are parsing incorrect programs, you want resilience in the parser, including considering alternate parsings and generation of parses of sections of the file. Consider the problem of parsing a C program that has NOT been put through the preprocessor. You want to be able to do this for structure editors and source-to-source transformation systems.
- rightbyte 5y ago
  It is quite possible to redifine much of the syntax with the cpp. Parsing without the cpp is hopeless. My favourite is Bourne's longing for Algol: https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh/mac.h https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd...
  - pfdietz 5y ago
    Of course parsing without cpp is, in general, hopeless. But for something like a structure-aware editor you don't need to parse it perfectly, just "good enough". Ditto for a source-to-source transformation system.
- chrisseaton 5y ago
  If your grammar is ambiguous, then an ambiguous program isn't incorrect.
  - pfdietz 5y ago
    It's not that the grammar is ambiguous, it's that the thing you're parsing may not even be in the language generated by the grammar. But you want to parse it as well as possible, and there may be more than one way to do that.
    - jatone 5y ago
      wow, absolutely not. if i'm parsing a programming language I want to basically stop and bail from the current context as soon as possible. there is basically nothing to gain by continuing. if the shit i'm parsing isn't in the language there is no reason to continue. its invalid.
      - greiskul 5y ago
        If you are writing a code editor you might want to continue parsing it. Or maybe you detected an error, but you want to report more than one error at a time for a better programmer experience. There are lots of use cases for partially parsing a computer program.

billconan 5y ago

in my implementation, I give each rule a priority. I always choose the one with the highest priority to expand. I basically followed this https://loup-vaillant.fr/tutorials/earley-parsing/parser https://loup-vaillant.fr/tutorials/earley-parsing/parser

xyzzy_plugh 5y ago
I've written parsers for context-sensitive grammars, and as it turns out, this is not a desirable feature of a language. The reason you typically see simple parsers is because simple grammars are usually unambiguous and context-free, which is more convenient for humans to understand and internalize. After all, when you're writing software, you pretend to be the compiler to some extent. Natural languages, like English, are a good example of something which humans struggle with because they are complex, ambiguous, and often require context. Sure, it's extremely expressive, but that is the sharpest double-edged sword in programming languages.
sirwhinesalot 5y ago
Neat, though this just seems like PEG with extra steps and more pain. Still this answers my question. Thanks!

pfdietz 5y ago

If you are parsing incorrect programs, you want resilience in the parser, including considering alternate parsings and generation of parses of sections of the file. Consider the problem of parsing a C program that has NOT been put through the preprocessor. You want to be able to do this for structure editors and source-to-source transformation systems.

rightbyte 5y ago
It is quite possible to redifine much of the syntax with the cpp. Parsing without the cpp is hopeless. My favourite is Bourne's longing for Algol: https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh/mac.h https://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd...
- pfdietz 5y ago
  Of course parsing without cpp is, in general, hopeless. But for something like a structure-aware editor you don't need to parse it perfectly, just "good enough". Ditto for a source-to-source transformation system.
chrisseaton 5y ago
If your grammar is ambiguous, then an ambiguous program isn't incorrect.
- pfdietz 5y ago
  It's not that the grammar is ambiguous, it's that the thing you're parsing may not even be in the language generated by the grammar. But you want to parse it as well as possible, and there may be more than one way to do that.
  - jatone 5y ago
    wow, absolutely not. if i'm parsing a programming language I want to basically stop and bail from the current context as soon as possible. there is basically nothing to gain by continuing. if the shit i'm parsing isn't in the language there is no reason to continue. its invalid.
    - greiskul 5y ago
      If you are writing a code editor you might want to continue parsing it. Or maybe you detected an error, but you want to report more than one error at a time for a better programmer experience. There are lots of use cases for partially parsing a computer program.