Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

"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 :)



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....), 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.


I think DannyBee's using a slightly broader definition of parsing than you're used to. There's the narrow definition of parsing ("Here's how we go from a sequence of bytes to an AST") that's the concrete material taught in compiler courses. But there's also a much broader paradigm where "parsing" is broadened to "Here's how we go from a listed set of patterns, possibly overlapping, to a set of transformations defined by those patterns." The source input need not be a linear set of bytes; you can trivially extend it to trees by taking an in-order traversal of the tree, or even operate directly on tree or graph data structures.

With the broader definition, a large number of what you consider the interesting parts of program analysis are actually parsing problems. Instruction selection, for example, involves tiling the AST (or more typically, the IR) with a minimal set of machine instructions. In many compilers, this is implemented with a machine-definition file that describes a grammar for transforming the IR into machine-language instructions. Peephole optimization involves recognizing certain patterns (eg. division by a constant power of 2) and then transforming them into more efficient constructs (eg. shift-right). This can also be described by a grammar on the IR.

I'm not sure if this is explicitly taught in compiler courses - it wasn't really in mine, but it was alluded to - but it's a really powerful way of thinking of the passes in a compiler. It lets you unify concepts, so that instead of memorizing all the specific algorithms used, you can think of a pass as "this is a transformation from this specific input language to this specific output language".




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: