4 ms·

Hate to disagree with you. But having written many parsers (and even a few parser generators) it really isn't that difficult if you understand the theory. Peopl

by timtadh 15y ago

Hate to disagree with you. But having written many parsers (and even a few parser generators) it really isn't that difficult if you understand the theory. People encounter problems usually because they don't understand the theory and don't know how to write a grammar. I have never used a PEG based parsing system so I can't speak to it. The wikipedia page seems to be riddled with inaccuracies. For instance it strongly indicates that context free grammars often end up with unresolvable ambiguities eg. > "The following recursive rule matches standard C-style if/then/else statements in such a way that the optional "else" clause always binds to the innermost "if", because of the implicit prioritization of the '/' operator. (In a context-free grammar, this construct yields the classic dangling else ambiguity.)" Nothing could be further from the truth. It is relatively easy to resolve an ambiguity arising from this structure. Indeed, Aho et all use it as an example for how to eliminate ambiguity from a language[pages 211-212 in the second edition. section 4.3.2 "Eliminating Ambiguity"]. Perhaps you could explain why you think PEG and Packrat are superior to CFG and standard parsing tools (eg. recursive descent or LALR and GLR parser generators).

Locke1689 15y ago
Hate to disagree with you. But having written many parsers (and even a few parser generators) it really isn't that difficult if you understand the theory. People encounter problems usually because they don't understand the theory and don't know how to write a grammar. From a software engineering perspective it's annoying. It's not terribly difficult and it's not that interesting, it's just annoying. Nothing could be further from the truth. It is relatively easy to resolve an ambiguity arising from this structure. Indeed, Aho et all use it as an example for how to eliminate ambiguity from a language[pages 211-212 in the second edition. section 4.3.2 "Eliminating Ambiguity"]. I agree that this is a bad example but you should remember from the literature that CFG is undecideably ambiguous. It's of course resolvable by GLR, but that's not the point. For more information I'd recommend you read these papers, starting with Ford's master's thesis. [1] Also remember that I wasn't talking about using packrat vs. a standard GLR parser -- I was talking about what you should do if you want to learn how to implement a parser. Packrat is easier to get right than the corner cases in GLR. [1] http://pdos.csail.mit.edu/~baford/packrat/ http://pdos.csail.mit.edu/~baford/packrat/
- silentbicycle 15y ago
  The LPEG paper (http://www.inf.puc-rio.br/~roberto/docs/peg.pdf http://www.inf.puc-rio.br/~roberto/docs/peg.pdf) is also pretty good. (LPEG is a PEG parsing library for Lua.)
- timtadh 15y ago
  > For more information I'd recommend you read these papers, starting with Ford's master's thesis. [1] Also remember that I wasn't talking about using packrat vs. a standard GLR parser -- I was talking about what you should do if you want to learn how to implement a parser. Packrat is easier to get right than the corner cases in GLR. Thanks for the link. I will definitely check it out. > From a software engineering perspective it's annoying. It's not terribly difficult and it's not that interesting, it's just annoying. It is not clear what you think is annoying (eg. learning the theory or writing a parser). I take it from later on in the post you believe writing the parser is annoying. I don't think writing parsers is in general annoying, but there are some languages which are annoying to write a parser for. I can't agree with your advisor's statement about it being only a "character building" exercise. There are times when you need to write a parser. However, I have to admit if I can get around it I will. For instance last year instead of writing a Java parser I hooked the OpenJDK parser and serialized out an AST. Much easier and a lot less code than a parser. I would always recommend doing something like this for an existing language. It is too easy to mess up a corner case in the grammar. tl;dr : I think we mostly agree, I just haven't read up on PEG's and Packrat.

by timtadh 15y ago

Locke1689 15y ago

Hate to disagree with you. But having written many parsers (and even a few parser generators) it really isn't that difficult if you understand the theory. People encounter problems usually because they don't understand the theory and don't know how to write a grammar. From a software engineering perspective it's annoying. It's not terribly difficult and it's not that interesting, it's just annoying. Nothing could be further from the truth. It is relatively easy to resolve an ambiguity arising from this structure. Indeed, Aho et all use it as an example for how to eliminate ambiguity from a language[pages 211-212 in the second edition. section 4.3.2 "Eliminating Ambiguity"]. I agree that this is a bad example but you should remember from the literature that CFG is undecideably ambiguous. It's of course resolvable by GLR, but that's not the point. For more information I'd recommend you read these papers, starting with Ford's master's thesis. [1] Also remember that I wasn't talking about using packrat vs. a standard GLR parser -- I was talking about what you should do if you want to learn how to implement a parser. Packrat is easier to get right than the corner cases in GLR. [1] http://pdos.csail.mit.edu/~baford/packrat/ http://pdos.csail.mit.edu/~baford/packrat/

silentbicycle 15y ago
The LPEG paper (http://www.inf.puc-rio.br/~roberto/docs/peg.pdf http://www.inf.puc-rio.br/~roberto/docs/peg.pdf) is also pretty good. (LPEG is a PEG parsing library for Lua.)
timtadh 15y ago
> For more information I'd recommend you read these papers, starting with Ford's master's thesis. [1] Also remember that I wasn't talking about using packrat vs. a standard GLR parser -- I was talking about what you should do if you want to learn how to implement a parser. Packrat is easier to get right than the corner cases in GLR. Thanks for the link. I will definitely check it out. > From a software engineering perspective it's annoying. It's not terribly difficult and it's not that interesting, it's just annoying. It is not clear what you think is annoying (eg. learning the theory or writing a parser). I take it from later on in the post you believe writing the parser is annoying. I don't think writing parsers is in general annoying, but there are some languages which are annoying to write a parser for. I can't agree with your advisor's statement about it being only a "character building" exercise. There are times when you need to write a parser. However, I have to admit if I can get around it I will. For instance last year instead of writing a Java parser I hooked the OpenJDK parser and serialized out an AST. Much easier and a lot less code than a parser. I would always recommend doing something like this for an existing language. It is too easy to mess up a corner case in the grammar. tl;dr : I think we mostly agree, I just haven't read up on PEG's and Packrat.