5 ms·

> While rolling your own parser will free you from ever getting error messages from your parser generator, it will also keep you from learning about ambiguities

by Drup 11y ago

> While rolling your own parser will free you from ever getting error messages from your parser generator, it will also keep you from learning about ambiguities you may be inadvertently designing into your language. I tried several time to explain why I think people should use parser generators and the conclusion of this article express my point of view perfectly. The fact that we have a very good parser generator in OCaml (and Coq!)[1] really helps here. I still think that ambiguities of the third kind, "Type/variable ambiguity", are a design issue and your grammar should be changed, because it's going to be completely ambiguous for humans too. [1]: http://gallium.inria.fr/~fpottier/menhir/ http://gallium.inria.fr/~fpottier/menhir/

ufo 11y ago
Menhir is really amazing. Being able to use the high-level rules to parse lists, without needing to use recursion, was super nice. It also gives decent error messages when it detects an ambiguity.
aardvark179 11y ago
Yeah. Reverse engineering a grammar you can give to a parser generator from a hand crafted parser is a fun and occasionally horrifying experience. There's nothing quite like discovering that loop @a ... endloop means start the loop labeled a but loop @a ... endloop means start a loop, the first statement of which refers to attribute a, but that this is the only use of labels in the language where these two cases are parsed differently...
- comex 11y ago
  Out of curiosity, is that a real example from some language?
  - aardvark179 11y ago
    Slightly altered to protect the guilty, but yes, this is a real example. There are few things more frustrating when converting hand written recursive descent parsers into proper grammars than having to insert arbitrary rules about where newlines can or cannot be. You generally can't change the language if there's production code out there (and if there isn't, why are reverse engineering a grammar?) because changing the semantics will lead to more confusion. You just end up making a grammar with really weird rules about where newlines can or cannot be put, and comments that this should not be changed. Oh, and a BIG test suite. Once you've dealt with the grammar then you'll only have bugs in the compiler and runtime semantics to emulate, and language implementations often have an exciting set of those.
tomp 11y ago
exactly. People like to pretend that e.g. PEG grammars don't have ambiguities because of "ordered choice"... But the truth is, they simply mask ambiguity away! Even yacc will always produce a valid grammar, resolving conflicts in a well-defined manner - while also letting you know how to fix your grammar to make it even better! Edit: this is actually explained much better in the article.
- sklogic 11y ago
  > But the truth is, they simply mask ambiguity away! Incorrect. The choice is explicit. Ambiguity gone, period. If the order makes some of the branches unreachable, it can be easily statically proven. In practice this is more than enough and does not require nearly as much effort as all the other parsing approaches.
pdkl95 11y ago
A huge reason anything accepting network (or other potentially hostile input) should use parser generators and validate the entire input before using any of it is security. Additionally, all of those grammars should, whenever possible, be no more complex than deterministic context-free. As Meredith and Sergey explain in their talk[1] at 28c3, Turing complete input and parsers that don't validate the input are creating a "weird machine" just waiting to be programmed in malicious and unexpected ways. [1] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...
- jstimpfle 11y ago
  Couple questions coming--sharing some experience and hoping to learn something. Do you think the use of parser generators is practical also for performance-critical binary data? For example video streams? (I've never parsed one but I imagine they could be so optimized that it could be impractical to do it with a generic parser generator). What formats are examples of complex structure where parser generators are practical? For my personal needs, I've been getting along very well with plain text relational data. Like numPersons 2 numAncestors 1 person john "John Doe" person jane "Jane Dane" ancestor john jane That's so trivial that I would never want to depend on a parser generator. Instead I handroll a parser for this format in 10 minutes and 20 lines of C if I don't mind bad error messages. And what parser generator would make it easy to check (relational) integrity of above data in a secure way? If I leave away the num* fields above, the parser would need one token of lookahead. What type of grammars are these two versions?
  - deleted 11y ago
    [deleted]
  - pdkl95 11y ago
    > Do you think the use of parser generators is practical also for performance-critical binary data? That's not a question I consider very important, because prioritizing performance over correctness (safety) is irresponsible. That said, using a parser generator shouldn't have a significant impact on performance. When a network is involved, the parser isn't going to be the bottleneck anyway. > video I am not very familiar with the details of video formats, but I would suggest trying the parser combinator library Meredith mentions in the talk in my previous [1], known as "hammer"[2]. It's very easy to use, and it has specific support for bit-level parsing of binary formats. > numPersons 2 I highly recommend not using formats like this, because it's more complex than deterministic context-free. Using a length field requires that the parser remember state. It's also redundant information, creating the possibility of a miss-match between the number specified in "numPersons" and the actual number of rows. A format that uses s-expressions would be safer and more easier to implement: (ancestry (ancestor (person john "John Doe") (person jane "Jane Doe") ) ) The closing tag of the s-expression provides a similar benefit as the num* fields by simply marking the end of a complete record/field. > That's so trivial that I would never want to depend on a parser generator Is it really "trivial"? Or is your parse that you write in 10 minutes accepting ambiguous or invalid data? Is it actually checking for all of the error conditions? For most real-world grammars, it's unlikely you will catch all of the subtle ambiguities, interactions, and edge cases. The benefit of using a parser generator is that those entire classes of bugs are impossible. > check (relational) integrity In the trivial example you gave, you shouldn't have a grammar that requires checking relational integrity. In a more complex grammar, such checks would be the job of whatever is walking the AST that the parser returns. Parsers interpret syntax, not semantics. > If I leave away the num* fields above, the parser would need one token of lookahead. You need at least one token of lookahead anyway. Including the num* fields means the parser needs to remember and manage state. [2] https://github.com/UpstandingHackers/hammer https://github.com/UpstandingHackers/hammer
joe_the_user 11y ago
As far as I can tell, parser generators are harder to use and understand than recursive descent parsers because they involve feeding an abstract spec of your language into a tool designed for any language whereas a recursive descent parser involves creating a tool more or less specific to your language. Now, it seems to me that being easier to use and understand is an inherent advantage - I can't see how easier to understand doesn't make bugs easier to understand and so-forth. Moreover, constructing a recursive descent parser involves understanding and transforming your language, an exercise which can also discover ambiguities and give a "deeper" understanding as well. It's hard for me to see Bison commands + code fragments as the ultimate in illumination concerning one's language's properties.
- jstimpfle 11y ago
  I've looked at yacc + bison a couple times and always turned away before even attempting to write parsers in them. It's ugly as hell and I figure sprinkling code is hard to understand and thus insecure. However, have you tried parser combinators? Parsec (a Haskell library) is really nice if it fits your grammar. Here is one guy who simulated that in Python, also very nice: http://jayconrod.com/posts/37/ http://jayconrod.com/posts/37/
  - kccqzy 11y ago
    Parsec is good but it's a rather old library. For more specialised needs there are even better choices in Haskell: (taken from Gabriel Gonzalez's recent post) * attoparsec remains the king of speed, generating parsers competitive in speed with C * trifecta remains the king of error messages, generating gorgeous clang-style errors * earley is a newcomer but deals with context-free grammars, while other parser combinatory are basically recursive descent parsers * and good old alex+happy for direct yacc+bison equivalent * I should probably mention that in certain simple cases you don't even need a parser combinator library to parse things. Just a good old `StateT (Text, r) [] ()` or similar can do wonders.

by Drup 11y ago

ufo 11y ago

Menhir is really amazing. Being able to use the high-level rules to parse lists, without needing to use recursion, was super nice. It also gives decent error messages when it detects an ambiguity.

aardvark179 11y ago

Yeah. Reverse engineering a grammar you can give to a parser generator from a hand crafted parser is a fun and occasionally horrifying experience. There's nothing quite like discovering that loop @a ... endloop means start the loop labeled a but loop @a ... endloop means start a loop, the first statement of which refers to attribute a, but that this is the only use of labels in the language where these two cases are parsed differently...

comex 11y ago
Out of curiosity, is that a real example from some language?
- aardvark179 11y ago
  Slightly altered to protect the guilty, but yes, this is a real example. There are few things more frustrating when converting hand written recursive descent parsers into proper grammars than having to insert arbitrary rules about where newlines can or cannot be. You generally can't change the language if there's production code out there (and if there isn't, why are reverse engineering a grammar?) because changing the semantics will lead to more confusion. You just end up making a grammar with really weird rules about where newlines can or cannot be put, and comments that this should not be changed. Oh, and a BIG test suite. Once you've dealt with the grammar then you'll only have bugs in the compiler and runtime semantics to emulate, and language implementations often have an exciting set of those.

tomp 11y ago

exactly. People like to pretend that e.g. PEG grammars don't have ambiguities because of "ordered choice"... But the truth is, they simply mask ambiguity away! Even yacc will always produce a valid grammar, resolving conflicts in a well-defined manner - while also letting you know how to fix your grammar to make it even better! Edit: this is actually explained much better in the article.

sklogic 11y ago
> But the truth is, they simply mask ambiguity away! Incorrect. The choice is explicit. Ambiguity gone, period. If the order makes some of the branches unreachable, it can be easily statically proven. In practice this is more than enough and does not require nearly as much effort as all the other parsing approaches.

pdkl95 11y ago

A huge reason anything accepting network (or other potentially hostile input) should use parser generators and validate the entire input before using any of it is security. Additionally, all of those grammars should, whenever possible, be no more complex than deterministic context-free. As Meredith and Sergey explain in their talk[1] at 28c3, Turing complete input and parsers that don't validate the input are creating a "weird machine" just waiting to be programmed in malicious and unexpected ways. [1] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...

jstimpfle 11y ago
Couple questions coming--sharing some experience and hoping to learn something. Do you think the use of parser generators is practical also for performance-critical binary data? For example video streams? (I've never parsed one but I imagine they could be so optimized that it could be impractical to do it with a generic parser generator). What formats are examples of complex structure where parser generators are practical? For my personal needs, I've been getting along very well with plain text relational data. Like numPersons 2 numAncestors 1 person john "John Doe" person jane "Jane Dane" ancestor john jane That's so trivial that I would never want to depend on a parser generator. Instead I handroll a parser for this format in 10 minutes and 20 lines of C if I don't mind bad error messages. And what parser generator would make it easy to check (relational) integrity of above data in a secure way? If I leave away the num* fields above, the parser would need one token of lookahead. What type of grammars are these two versions?
- deleted 11y ago
  [deleted]
- pdkl95 11y ago
  > Do you think the use of parser generators is practical also for performance-critical binary data? That's not a question I consider very important, because prioritizing performance over correctness (safety) is irresponsible. That said, using a parser generator shouldn't have a significant impact on performance. When a network is involved, the parser isn't going to be the bottleneck anyway. > video I am not very familiar with the details of video formats, but I would suggest trying the parser combinator library Meredith mentions in the talk in my previous [1], known as "hammer"[2]. It's very easy to use, and it has specific support for bit-level parsing of binary formats. > numPersons 2 I highly recommend not using formats like this, because it's more complex than deterministic context-free. Using a length field requires that the parser remember state. It's also redundant information, creating the possibility of a miss-match between the number specified in "numPersons" and the actual number of rows. A format that uses s-expressions would be safer and more easier to implement: (ancestry (ancestor (person john "John Doe") (person jane "Jane Doe") ) ) The closing tag of the s-expression provides a similar benefit as the num* fields by simply marking the end of a complete record/field. > That's so trivial that I would never want to depend on a parser generator Is it really "trivial"? Or is your parse that you write in 10 minutes accepting ambiguous or invalid data? Is it actually checking for all of the error conditions? For most real-world grammars, it's unlikely you will catch all of the subtle ambiguities, interactions, and edge cases. The benefit of using a parser generator is that those entire classes of bugs are impossible. > check (relational) integrity In the trivial example you gave, you shouldn't have a grammar that requires checking relational integrity. In a more complex grammar, such checks would be the job of whatever is walking the AST that the parser returns. Parsers interpret syntax, not semantics. > If I leave away the num* fields above, the parser would need one token of lookahead. You need at least one token of lookahead anyway. Including the num* fields means the parser needs to remember and manage state. [2] https://github.com/UpstandingHackers/hammer https://github.com/UpstandingHackers/hammer

joe_the_user 11y ago

As far as I can tell, parser generators are harder to use and understand than recursive descent parsers because they involve feeding an abstract spec of your language into a tool designed for any language whereas a recursive descent parser involves creating a tool more or less specific to your language. Now, it seems to me that being easier to use and understand is an inherent advantage - I can't see how easier to understand doesn't make bugs easier to understand and so-forth. Moreover, constructing a recursive descent parser involves understanding and transforming your language, an exercise which can also discover ambiguities and give a "deeper" understanding as well. It's hard for me to see Bison commands + code fragments as the ultimate in illumination concerning one's language's properties.

jstimpfle 11y ago
I've looked at yacc + bison a couple times and always turned away before even attempting to write parsers in them. It's ugly as hell and I figure sprinkling code is hard to understand and thus insecure. However, have you tried parser combinators? Parsec (a Haskell library) is really nice if it fits your grammar. Here is one guy who simulated that in Python, also very nice: http://jayconrod.com/posts/37/ http://jayconrod.com/posts/37/
- kccqzy 11y ago
  Parsec is good but it's a rather old library. For more specialised needs there are even better choices in Haskell: (taken from Gabriel Gonzalez's recent post) * attoparsec remains the king of speed, generating parsers competitive in speed with C * trifecta remains the king of error messages, generating gorgeous clang-style errors * earley is a newcomer but deals with context-free grammars, while other parser combinatory are basically recursive descent parsers * and good old alex+happy for direct yacc+bison equivalent * I should probably mention that in certain simple cases you don't even need a parser combinator library to parse things. Just a good old `StateT (Text, r) [] ()` or similar can do wonders.