4 ms·

"the way you have to wade through months of parsing bullshit to get to the really interesting stuff (optimization and static analysis)." If you look back in th

"the way you have to wade through months of parsing bullshit to get to the really interesting stuff (optimization and static analysis)." If you look back in the late 70's, you'll discover something interesting: Almost everything was parsing of one form or another. Really. Parsing of flowgraphs, etc. Dataflow was done not just by bitvector methods (which were fairly new), but by parsing of graphs using graph grammars. Most optimization analysis are very closely related to parsing (and can often be solved by graph reachability). The complexity bounds of most of them are also driven by parsing complexity results. For example, andersen-style points-to analysis is solvable as a context-free-language problem. The time bounds of it are driven by the time bounds on context-free-language parsing. In particular, all-pairs reachability on Context Free Languages (N^3). etc Parsing is the basis of compilers for a very good reason. The fact that we have advanced other types of methods on top of analysis for optimization and analysis does not change the fact that, at the core, a lot of them are based on equivalence to parsing of graphs and graph reachability. Another way to look at it: If you ever want to be able to be really good at compiler optimization, don't skip parsing. Otherwise you will miss the connections that are really important to being able to design efficient new algorithms, instead of just learning old ones.

nostrademons 9y ago
Parsing also comes up in a stupidly large number of other areas within programming, including: serialization formats, network protocols, DSLs, log analysis, time series interpretation, NLP, unstructured data mining, and probably several I'm not familiar with. Fundamentally understanding what's going on when you're doing recursive-descent, shift/reduce, or combinator-based parsing unlocks a big toolbox that you can use to solve a number of other problems.
pbiggar 9y ago
I'm not saying it isn't useful - I'm saying it's not interesting (and I'm talking about the act of parsing, not the algorithms as applied elsewhere). Think about this: you start learning compilers, you spend months on parsing, and after that what do you have? Nothing - you "compiled" stuff into an AST. Yawn.
- DannyBee 9y ago
  "I'm not saying it isn't useful - I'm saying it's not interesting " Then you are doing it wrong :) "(and I'm talking about the act of parsing, not the algorithms as applied elsewhere)" I'm not sure what this is supposed to mean. It sounds like you are trying to separate parsing text into ASTs and parsing flowgraphs, so you can claim one is boring, and the other is "algorithms as applied elsewhere". There is no such separation. We just happen to name variables a little differently so it doesn't quite look like "figure out if this one parentheses matches this other one". But it is the same algorithm. If you are trying to separate parsing as the thing that happens that makes an AST, that is not the only thing that is parsing. Yes, some books colloquially separate phases like that, but it's silly. "Think about this: you start learning compilers, you spend months on parsing, and after that what do you have? Nothing - you "compiled" stuff into an AST. " You are definitely doing it wrong. The same parsing of a grammar you taught someone to make an AST, you can now say "we can apply a slightly different language grammar to the AST and generate machine code", or "apply a slightly different language grammar to the AST and parse out flowgraphs and statements" etc parsing isn't just take a bunch of text, turn it into an AST. The fact that a ton of people think this is one reason there are so many crappy little compilers that never go anywhere :)
  - pbiggar 9y ago
    We're having two different conversations here. You are saying (correct me if I'm wrong) that the algorithms you use for parsing are broadly applicable to program analysis. You are not wrong. It's just orthogonal to my point, which is that program analysis is really interesting. To make an analogy here (from Lockhart's lament: https://www.maa.org/external_archive/devlin/LockhartsLament.pdf https://www.maa.org/external_archive/devlin/LockhartsLament....), you are saying that color theory is massively important throughout one's career as a artissti. I am saying that I just like painting things. Sure, there's lots of cool shit in parsing theory no doubt, with tons of broad application. But the way that we are taught it ("here's how we get an AST from written text") turns away people who are into program analysis. As such, we shouldn't consider parsing a pre-requisite for program analysis, regardless of how interesting or applicable the theory of parsing is.

nostrademons 9y ago

Parsing also comes up in a stupidly large number of other areas within programming, including: serialization formats, network protocols, DSLs, log analysis, time series interpretation, NLP, unstructured data mining, and probably several I'm not familiar with. Fundamentally understanding what's going on when you're doing recursive-descent, shift/reduce, or combinator-based parsing unlocks a big toolbox that you can use to solve a number of other problems.

pbiggar 9y ago

I'm not saying it isn't useful - I'm saying it's not interesting (and I'm talking about the act of parsing, not the algorithms as applied elsewhere). Think about this: you start learning compilers, you spend months on parsing, and after that what do you have? Nothing - you "compiled" stuff into an AST. Yawn.

DannyBee 9y ago
"I'm not saying it isn't useful - I'm saying it's not interesting " Then you are doing it wrong :) "(and I'm talking about the act of parsing, not the algorithms as applied elsewhere)" I'm not sure what this is supposed to mean. It sounds like you are trying to separate parsing text into ASTs and parsing flowgraphs, so you can claim one is boring, and the other is "algorithms as applied elsewhere". There is no such separation. We just happen to name variables a little differently so it doesn't quite look like "figure out if this one parentheses matches this other one". But it is the same algorithm. If you are trying to separate parsing as the thing that happens that makes an AST, that is not the only thing that is parsing. Yes, some books colloquially separate phases like that, but it's silly. "Think about this: you start learning compilers, you spend months on parsing, and after that what do you have? Nothing - you "compiled" stuff into an AST. " You are definitely doing it wrong. The same parsing of a grammar you taught someone to make an AST, you can now say "we can apply a slightly different language grammar to the AST and generate machine code", or "apply a slightly different language grammar to the AST and parse out flowgraphs and statements" etc parsing isn't just take a bunch of text, turn it into an AST. The fact that a ton of people think this is one reason there are so many crappy little compilers that never go anywhere :)
- pbiggar 9y ago
  We're having two different conversations here. You are saying (correct me if I'm wrong) that the algorithms you use for parsing are broadly applicable to program analysis. You are not wrong. It's just orthogonal to my point, which is that program analysis is really interesting. To make an analogy here (from Lockhart's lament: https://www.maa.org/external_archive/devlin/LockhartsLament.pdf https://www.maa.org/external_archive/devlin/LockhartsLament....), you are saying that color theory is massively important throughout one's career as a artissti. I am saying that I just like painting things. Sure, there's lots of cool shit in parsing theory no doubt, with tons of broad application. But the way that we are taught it ("here's how we get an AST from written text") turns away people who are into program analysis. As such, we shouldn't consider parsing a pre-requisite for program analysis, regardless of how interesting or applicable the theory of parsing is.