4 ms·

I think PEG let people think they can get away from the complexities of grammars because there are no ambiguities when you express them using PEGs. This is not

I think PEG let people think they can get away from the complexities of grammars because there are no ambiguities when you express them using PEGs. This is not true: the ambiguities are still there, and you still have to think about them, otherwise PEGs will generate "garden path" parses that make no sense. I think the sweet spot for parsing medium and high complexity languages is autogenerated lexer + handwritten recursive descent.

jules 5y ago
PEGs are a compact notation for recursive descent and they compile to recursive descent parsers. What would be the advantage of writing the compiled code by hand?
- vidarh 5y ago
  Few parser generators do well on things like error reporting in a human friendly manner. In effect production parsers tends to end up being hand written or extensively hand-modified for that reason. I wish more work on parser generators would involve focusing on better diagnostics (for end users, not the parser developer) and reporting rather than making them easier to use for the parser writers, as "just" writing the parser is rarely the hard part. EDIT: Even making it easier to annotate the parser specifications to improve error reporting would be an improvement for many parser generators. In the past I've experimented with parser generators that included a prolog-inspired "cut" like operator that stops further backtracking, and that'd take an error message to output if nothing further can be matched without backtracking. It'd prevent the parser from "escaping" out of a likely human error and end up reporting a failure to match productions much higher up. It worked fairly well, and mimics what human parser writers tends to do in recursive descent parsers - we'll often guess at the likely error based on context deep down and bail out.
chrisseaton 5y ago
> people think they can get away from the complexities of grammars because there are no ambiguities when you express them using PEGs. This is not true: the ambiguities are still there It's literally impossible to write a PEG with an ambiguity. So I don't know what you mean?
- HelloNurse 5y ago
  Ambiguities in the intended language aren't literally "still there" in the PEG, but realistically they are "still there" as a source of problems: naive PEGs can remove ambiguities incorrectly in less than obvious ways, and figuring out what's wrong can be more difficult than hitting a brick wall with other parsing approaches.
- frabert 5y ago
  Just because the PEG doesn't have ambiguities doesn't mean the grammar you meant to recognize doesn't have one. What I mean is: PEGs give you a false sense of confidence by making you feel like you solved all your grammar's issues. In reality, you need to think really carefully about what your PEG is doing, because it's not going to warn you. As you said, PEGs are never ambiguous.
  - chrisseaton 5y ago
    Well yeah if the grammar you wrote doesn't match what you intended to write then it's not going to work. Not sure how that's saying anything useful though? If you write the wrong grammar with any parsing system it's also not going to work.
    - frabert 5y ago
      Most other parser generator systems give you indication that what you're writing is probably wrong, by stating e.g. that a grammar is ambiguous. S := A '+' A | A '*' A A := ... If you do that in most PEG systems I've tried, you're just going to get the wrong result with no indication of what might have gone wrong, unless you know where to look.
      - chrisseaton 5y ago
        But that's the point - other parsing systems let you design an ambiguous language and then tell you about it. PEGs don't let you design an ambiguous language in the first place. Unambiguous by construction.
convolvatron 5y ago
why would you recommend using a generated lexer? the machinery is so simple thats its generally not worth trying to deal with the plumbing, esp around types.

jules 5y ago

PEGs are a compact notation for recursive descent and they compile to recursive descent parsers. What would be the advantage of writing the compiled code by hand?

vidarh 5y ago
Few parser generators do well on things like error reporting in a human friendly manner. In effect production parsers tends to end up being hand written or extensively hand-modified for that reason. I wish more work on parser generators would involve focusing on better diagnostics (for end users, not the parser developer) and reporting rather than making them easier to use for the parser writers, as "just" writing the parser is rarely the hard part. EDIT: Even making it easier to annotate the parser specifications to improve error reporting would be an improvement for many parser generators. In the past I've experimented with parser generators that included a prolog-inspired "cut" like operator that stops further backtracking, and that'd take an error message to output if nothing further can be matched without backtracking. It'd prevent the parser from "escaping" out of a likely human error and end up reporting a failure to match productions much higher up. It worked fairly well, and mimics what human parser writers tends to do in recursive descent parsers - we'll often guess at the likely error based on context deep down and bail out.

chrisseaton 5y ago

> people think they can get away from the complexities of grammars because there are no ambiguities when you express them using PEGs. This is not true: the ambiguities are still there It's literally impossible to write a PEG with an ambiguity. So I don't know what you mean?

HelloNurse 5y ago
Ambiguities in the intended language aren't literally "still there" in the PEG, but realistically they are "still there" as a source of problems: naive PEGs can remove ambiguities incorrectly in less than obvious ways, and figuring out what's wrong can be more difficult than hitting a brick wall with other parsing approaches.
frabert 5y ago
Just because the PEG doesn't have ambiguities doesn't mean the grammar you meant to recognize doesn't have one. What I mean is: PEGs give you a false sense of confidence by making you feel like you solved all your grammar's issues. In reality, you need to think really carefully about what your PEG is doing, because it's not going to warn you. As you said, PEGs are never ambiguous.
- chrisseaton 5y ago
  Well yeah if the grammar you wrote doesn't match what you intended to write then it's not going to work. Not sure how that's saying anything useful though? If you write the wrong grammar with any parsing system it's also not going to work.
  - frabert 5y ago
    Most other parser generator systems give you indication that what you're writing is probably wrong, by stating e.g. that a grammar is ambiguous. S := A '+' A | A '*' A A := ... If you do that in most PEG systems I've tried, you're just going to get the wrong result with no indication of what might have gone wrong, unless you know where to look.
    - chrisseaton 5y ago
      But that's the point - other parsing systems let you design an ambiguous language and then tell you about it. PEGs don't let you design an ambiguous language in the first place. Unambiguous by construction.

convolvatron 5y ago

why would you recommend using a generated lexer? the machinery is so simple thats its generally not worth trying to deal with the plumbing, esp around types.