4 ms·

One reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you did

by wrs 6y ago

One reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you didn’t realize. A hand-coded parser tends to just codify your bad assumptions. It can actually be a good idea to maintain a YACC (or other) grammar for your language just to run the tool as a kind of “grammar linter”, even if you’re going to write the parser by hand.

pklausler 6y ago
If you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.
- thequux 6y ago
  Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)
  - UK-Al05 6y ago
    Do they hide or do they just apply order to choices. Making it impossible to be ambiguous compared to the CFG definition? It's only sweeping under the rug, if you look at PEG under CFG rules. PEG is not CFG. I think practice of writing industrial software that is better.
    - WorldMaker 6y ago
      I do sometimes wonder if a lot of these arguments themselves would be less ambiguous if PEGs (or some other name of them) were formally added to Chomsky's Hierarchy of Languages between Regular Languages and the languages expressed by CFGs. Though I think it would take someone with a much more rigorous math background than myself to make the case formal enough to get it accepted. (If it helps, and it may be a red herring, the dualism between PEGs and Parser Combinators has me thinking it's a Category Theory related "step" in the hierarchy. "Deterministic Monadic Compositions" in a reflection of DFA/NFA duals to Regular Languages might imply "Monadic Languages" as a possible name? Again, my math background is definitely not formal enough here to make actual suggestions, but maybe it sparks an idea for someone else.)
  - chrisseaton 6y ago
    PEGs absolutely do prevent ambiguity - they don't 'hide' it - I don't even know what that would mean? There is exactly one way a PEG can parse - there is no ambiguity at all.
chrisseaton 6y ago
If you define your language using a recursive descent parser then it can’t be ambiguous.
- wrs 6y ago
  Yes, exactly — that means you’re resolving ambiguities whether or not you’re aware of them (“codify your bad assumptions”).
  - chrisseaton 6y ago
    You're not aware of them... because they never exist. A language specified by a recursive descent parser is never ambiguous in the first place. There's nothing to resolve. I don't know where 'codify your bad assumptions' comes into it? What assumptions? How are they codified without you knowing?
    - wrs 6y ago
      The language your parser parses may not be the language you had in mind. Indeed, the language you had in mind may not actually exist. It’s easy to operate based only on examples, and think you know what your language is, when in fact there are cases you didn’t consider. Your parser will resolve the ambiguity (because it has to), but if the tool had told you about the ambiguity, you might have redesigned the language. The result is often that one of your users will discover the ambiguity instead, and then it may be too late. As an example too well-known to actually occur, suppose you parse “if x then if y then x else z” with the else clause associated to the first if statement, because that’s just how you happened to write the parser. It’s not ambiguous, but your users won’t be happy when they find out the unambiguous rule.
      - chrisseaton 6y ago
        > The result is often that one of your users will discover the ambiguity instead, and then it may be too late. But there are no ambiguities in recursive descent! They won't discover them because... they don't exist! It's literally impossible. > As an example too well-known to actually occur, suppose you parse... Great example - and the good thing about recursive descent means it's impossible to write this ambiguously - you must prefer one or the other. > It’s not ambiguous Correct. So why are you telling me the problems of ambiguity? > but your users won’t be happy when they find out the unambiguous rule Why won't they be happy? You can tell them exactly how their code is going to be parsed. I thought ambiguities was bad but now you're complaining about ambiguity as well?!

by wrs 6y ago

pklausler 6y ago

If you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.

thequux 6y ago
Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)
- UK-Al05 6y ago
  Do they hide or do they just apply order to choices. Making it impossible to be ambiguous compared to the CFG definition? It's only sweeping under the rug, if you look at PEG under CFG rules. PEG is not CFG. I think practice of writing industrial software that is better.
  - WorldMaker 6y ago
    I do sometimes wonder if a lot of these arguments themselves would be less ambiguous if PEGs (or some other name of them) were formally added to Chomsky's Hierarchy of Languages between Regular Languages and the languages expressed by CFGs. Though I think it would take someone with a much more rigorous math background than myself to make the case formal enough to get it accepted. (If it helps, and it may be a red herring, the dualism between PEGs and Parser Combinators has me thinking it's a Category Theory related "step" in the hierarchy. "Deterministic Monadic Compositions" in a reflection of DFA/NFA duals to Regular Languages might imply "Monadic Languages" as a possible name? Again, my math background is definitely not formal enough here to make actual suggestions, but maybe it sparks an idea for someone else.)
- chrisseaton 6y ago
  PEGs absolutely do prevent ambiguity - they don't 'hide' it - I don't even know what that would mean? There is exactly one way a PEG can parse - there is no ambiguity at all.

chrisseaton 6y ago

If you define your language using a recursive descent parser then it can’t be ambiguous.

wrs 6y ago
Yes, exactly — that means you’re resolving ambiguities whether or not you’re aware of them (“codify your bad assumptions”).
- chrisseaton 6y ago
  You're not aware of them... because they never exist. A language specified by a recursive descent parser is never ambiguous in the first place. There's nothing to resolve. I don't know where 'codify your bad assumptions' comes into it? What assumptions? How are they codified without you knowing?
  - wrs 6y ago
    The language your parser parses may not be the language you had in mind. Indeed, the language you had in mind may not actually exist. It’s easy to operate based only on examples, and think you know what your language is, when in fact there are cases you didn’t consider. Your parser will resolve the ambiguity (because it has to), but if the tool had told you about the ambiguity, you might have redesigned the language. The result is often that one of your users will discover the ambiguity instead, and then it may be too late. As an example too well-known to actually occur, suppose you parse “if x then if y then x else z” with the else clause associated to the first if statement, because that’s just how you happened to write the parser. It’s not ambiguous, but your users won’t be happy when they find out the unambiguous rule.
    - chrisseaton 6y ago
      > The result is often that one of your users will discover the ambiguity instead, and then it may be too late. But there are no ambiguities in recursive descent! They won't discover them because... they don't exist! It's literally impossible. > As an example too well-known to actually occur, suppose you parse... Great example - and the good thing about recursive descent means it's impossible to write this ambiguously - you must prefer one or the other. > It’s not ambiguous Correct. So why are you telling me the problems of ambiguity? > but your users won’t be happy when they find out the unambiguous rule Why won't they be happy? You can tell them exactly how their code is going to be parsed. I thought ambiguities was bad but now you're complaining about ambiguity as well?!