3 ms·

parsing is in my opinion the crappiest part of compiler writing. I feel pretty safe saying that because we have made tools to automate or near-automate the act

by munin 15y ago

parsing is in my opinion the crappiest part of compiler writing. I feel pretty safe saying that because we have made tools to automate or near-automate the act of writing parsers for compilers ... I would argue that there's a big difference between "demystify how the text of your program changes the coloured lights on your screen" and "demystify why the text of your program changes the coloured lights on your screen". if you are interested only in the first question, you might be an engineer. if you are also interested in the second question, you might be a computer scientist...

barrkel 15y ago
Parsing is the best understood part of writing compilers; that's why it has tools, not because it is the "crappiest". (If anything, the wealth of free tools available gives a clue as to how fun dealing with it is.) But using the tools well requires some understanding of how they work; and if you're doing an industrial-strength parsing job, you'll probably end up writing the parser by hand, because what a tool gives you - speed in converting specification into implementation - is not usually the constraining factor; rather, functionality and performance of the end result are. As to your question "why", nothing about the lambda calculus will tell you anything about why your program changes the coloured lights. There is only "how" and "will", by which I mean human agency. There is no answer to "why" here, and there cannot be, because the "why" resides in people's minds. It takes no more extra effort to believe in "if" than beta reduction. Take that single example: implementing if as a primitive rather than a function with lazily evaluated arguments means greatly increasing practicality at the cost of the sparse beauty of minimalism. 'If' is very common; optimizing it, diagnosing misuses of it, etc. is a lot harder once you've lost it in a forest of function applications.
- gruseom 15y ago
  I agree with everything in your first paragraph and would add the following: parsing is overrated. It's interesting the way that crossword puzzles are. Nothing wrong with that, but it can be a distraction; it's just not that deep a space. That's not to say that the people who worked out how to do it in the first place weren't brilliant. They were, and it was a hard problem. But it's a solved one.
  - barrkel 15y ago
    There are still some fairly hard problems in parsing. For example, doing minimal work to convert a series of text deltas into abstract syntax tree deltas, using caching to avoid throwing away too much. This is highly relevant to IDEs for providing code completion and other analysis, but it's usually solved with a mix of brute force - restarting the whole parse from the top - and trickery, such as skipping uninteresting function bodies, or parsing a much simplified version of the language that ignores many productions.
    - gruseom 15y ago
      I didn't know that. Thanks.
  - njs12345 15y ago
    I'm not sure I'd necessarily agree with your assessment of parsing as a field in 2011. There are still a lot of unsolved problems going forward --- see Laurence Tratt's excellent article on the subject for a few details: http://tratt.net/laurie/tech_articles/articles/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/tech_articles/articles/parsing_the_s...
    - gruseom 15y ago
      I don't know. Barrkel's example seems better to me because there's an obvious practical need for it. The trouble with most of the work on parsing I see is that it's just not hard to hand-write a parser. I used to avoid doing so, and then I wrote one and was surprised: once you factor in error-handling and whatever other meaningful output your system may need from its parser (e.g. text extents for ASTs), the overall complexity of a hand-written one can easily be less than one made with tools at a supposedly higher level of abstraction. And that's not counting the time it takes to learn the tool (which is not trivial, as they don't always have good debugging support) or the complexity cost of having the tool in one's stack (also not trivial, since they typically have their own languages, complicate the build process, and so on). This experience led me to mentally discount the whole field, hence my perhaps overly dismissive comment.
kd0amg 15y ago
I would argue that there's a big difference between "demystify how the text of your program changes the coloured lights on your screen" and "demystify why the text of your program changes the coloured lights on your screen". I agree, there is a big difference between implementation and semantics, but I would normally expect a compilers class to focus on implementation (and I wouldn't expect a typical languages or compilers class to spend half a semester teaching how lambda calculus works as a computation model).

by munin 15y ago

barrkel 15y ago

Parsing is the best understood part of writing compilers; that's why it has tools, not because it is the "crappiest". (If anything, the wealth of free tools available gives a clue as to how fun dealing with it is.) But using the tools well requires some understanding of how they work; and if you're doing an industrial-strength parsing job, you'll probably end up writing the parser by hand, because what a tool gives you - speed in converting specification into implementation - is not usually the constraining factor; rather, functionality and performance of the end result are. As to your question "why", nothing about the lambda calculus will tell you anything about why your program changes the coloured lights. There is only "how" and "will", by which I mean human agency. There is no answer to "why" here, and there cannot be, because the "why" resides in people's minds. It takes no more extra effort to believe in "if" than beta reduction. Take that single example: implementing if as a primitive rather than a function with lazily evaluated arguments means greatly increasing practicality at the cost of the sparse beauty of minimalism. 'If' is very common; optimizing it, diagnosing misuses of it, etc. is a lot harder once you've lost it in a forest of function applications.

gruseom 15y ago
I agree with everything in your first paragraph and would add the following: parsing is overrated. It's interesting the way that crossword puzzles are. Nothing wrong with that, but it can be a distraction; it's just not that deep a space. That's not to say that the people who worked out how to do it in the first place weren't brilliant. They were, and it was a hard problem. But it's a solved one.
- barrkel 15y ago
  There are still some fairly hard problems in parsing. For example, doing minimal work to convert a series of text deltas into abstract syntax tree deltas, using caching to avoid throwing away too much. This is highly relevant to IDEs for providing code completion and other analysis, but it's usually solved with a mix of brute force - restarting the whole parse from the top - and trickery, such as skipping uninteresting function bodies, or parsing a much simplified version of the language that ignores many productions.
  - gruseom 15y ago
    I didn't know that. Thanks.
- njs12345 15y ago
  I'm not sure I'd necessarily agree with your assessment of parsing as a field in 2011. There are still a lot of unsolved problems going forward --- see Laurence Tratt's excellent article on the subject for a few details: http://tratt.net/laurie/tech_articles/articles/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/tech_articles/articles/parsing_the_s...
  - gruseom 15y ago
    I don't know. Barrkel's example seems better to me because there's an obvious practical need for it. The trouble with most of the work on parsing I see is that it's just not hard to hand-write a parser. I used to avoid doing so, and then I wrote one and was surprised: once you factor in error-handling and whatever other meaningful output your system may need from its parser (e.g. text extents for ASTs), the overall complexity of a hand-written one can easily be less than one made with tools at a supposedly higher level of abstraction. And that's not counting the time it takes to learn the tool (which is not trivial, as they don't always have good debugging support) or the complexity cost of having the tool in one's stack (also not trivial, since they typically have their own languages, complicate the build process, and so on). This experience led me to mentally discount the whole field, hence my perhaps overly dismissive comment.

kd0amg 15y ago

I would argue that there's a big difference between "demystify how the text of your program changes the coloured lights on your screen" and "demystify why the text of your program changes the coloured lights on your screen". I agree, there is a big difference between implementation and semantics, but I would normally expect a compilers class to focus on implementation (and I wouldn't expect a typical languages or compilers class to spend half a semester teaching how lambda calculus works as a computation model).