5 ms·

As much as I enjoyed optimization and static analysis, parsing is probably the single most useful knowledge I got from my formal CS education; and probably the

As much as I enjoyed optimization and static analysis, parsing is probably the single most useful knowledge I got from my formal CS education; and probably the only part of a compiler that most CS students will ever need to know.

olewhalehunter 9y ago
The symbiotic relationship between compiler development and hardware architecture design has a defining role in CS problems, and while you don't need to understand that relationship to write CRUD apps for a living, I think ignorance of it robs those who really want to understand this stuff of truths both technical and profound.
- yeowMeng 9y ago
  Totally! Compiler development = Finite State Automaton + Push Down Automaton + Context Free Grammar + Intermediate representation + Static Analysis/Optimiation + Stack Machine + ... Hardware Architecture = Stack Machine/Turing Machine + electricity + creativity Stack Machine == Turing Machine Compiler development starts and ends with Turing Machines. Hardware architecture ends with Turing Machines operating at the speed of electricity through metal.
  - olewhalehunter 9y ago
    There are alternatives to this mainstream style of computer architecture, such as dataflow or hybrid quantum-classical systems, which both require a very different kind of compiler. https://en.wikipedia.org/wiki/Dataflow_architecture https://en.wikipedia.org/wiki/Dataflow_architecture
amorphid 9y ago
I recently made myself sit down and learn leex (essentially lexx for Erlang), and I found that to be an extremely useful exercise. It helped me understand how to think about what kind of inputs a parser can make use of, and when it makes sense to skip the tokenizing step.
userbinator 9y ago
A recursive-descent parser is probably the only part of a compiler which people will easily derive on their own, even without taking a compiler course.
- anarazel 9y ago
  Funnily enough it's also where a bunch of mature compilers eventually ended up with, because of speed, heuristics and so forth. Like GCC, which used to have bison based compilers IIRC, but but is hand rolled rec dec...
  - vidarh 9y ago
    It's not so much for speed and heuristics but for error reporting and/or recovery. As it turns out (and I've tried many times myself too), designing a parser generator that will retain a compact representation without losing good error reporting is very hard. E.g. consider a BNF type grammar. Almost every symbol represents a potential error. But often deriving that error message automatically in a way that is helpful to a human is incredibly hard because the grammar lacks information about which mistakes are more likely for humans to make. So we end up with bad error reporting, or you end up having to write code to analyse errors anyway, and then a lot of the benefits disappear - the actual parsing is usually easy to do compactly with a recursive descent parser and a tiny library of helpers anyway.
    - anarazel 9y ago
      Yea, I was imprecisely using heuristics to primarily be about error reporting. You essentially have to partially accept a wider set of grammar, to be able to throw more intelligent errors. But speed ime also is a major issue. GCC sped up a good bit when switching, and we are seeing speed issues with bison generated parsers. Ironically one of the benefits of bison is that you get feedback about whether your grammar is conflict free. Can be a significant advantage over a hand built recdec parser for a complex language like SQL.
      - 9y ago
joe_the_user 9y ago
Yes, I think understanding that there's a fundamental difference between the operation of parsing a language and "naive call-and-for-loop programming" is very important. Most naive efforts to parse a language starting with no knowledge simply fail (and that can include, say, things efforts to validate a file name in a somewhat complex file system or to parse a packet in a network protocol). In college, it took me a bit of time to understand what a formal language really was and what the difference between a parser and a simple string processor was and when I arrived in industry, I notice this were something a certain proportion of otherwise experienced programmers simply did not understand this.

olewhalehunter 9y ago

The symbiotic relationship between compiler development and hardware architecture design has a defining role in CS problems, and while you don't need to understand that relationship to write CRUD apps for a living, I think ignorance of it robs those who really want to understand this stuff of truths both technical and profound.

yeowMeng 9y ago
Totally! Compiler development = Finite State Automaton + Push Down Automaton + Context Free Grammar + Intermediate representation + Static Analysis/Optimiation + Stack Machine + ... Hardware Architecture = Stack Machine/Turing Machine + electricity + creativity Stack Machine == Turing Machine Compiler development starts and ends with Turing Machines. Hardware architecture ends with Turing Machines operating at the speed of electricity through metal.
- olewhalehunter 9y ago
  There are alternatives to this mainstream style of computer architecture, such as dataflow or hybrid quantum-classical systems, which both require a very different kind of compiler. https://en.wikipedia.org/wiki/Dataflow_architecture https://en.wikipedia.org/wiki/Dataflow_architecture

amorphid 9y ago

I recently made myself sit down and learn leex (essentially lexx for Erlang), and I found that to be an extremely useful exercise. It helped me understand how to think about what kind of inputs a parser can make use of, and when it makes sense to skip the tokenizing step.

userbinator 9y ago

A recursive-descent parser is probably the only part of a compiler which people will easily derive on their own, even without taking a compiler course.

anarazel 9y ago
Funnily enough it's also where a bunch of mature compilers eventually ended up with, because of speed, heuristics and so forth. Like GCC, which used to have bison based compilers IIRC, but but is hand rolled rec dec...
- vidarh 9y ago
  It's not so much for speed and heuristics but for error reporting and/or recovery. As it turns out (and I've tried many times myself too), designing a parser generator that will retain a compact representation without losing good error reporting is very hard. E.g. consider a BNF type grammar. Almost every symbol represents a potential error. But often deriving that error message automatically in a way that is helpful to a human is incredibly hard because the grammar lacks information about which mistakes are more likely for humans to make. So we end up with bad error reporting, or you end up having to write code to analyse errors anyway, and then a lot of the benefits disappear - the actual parsing is usually easy to do compactly with a recursive descent parser and a tiny library of helpers anyway.
  - anarazel 9y ago
    Yea, I was imprecisely using heuristics to primarily be about error reporting. You essentially have to partially accept a wider set of grammar, to be able to throw more intelligent errors. But speed ime also is a major issue. GCC sped up a good bit when switching, and we are seeing speed issues with bison generated parsers. Ironically one of the benefits of bison is that you get feedback about whether your grammar is conflict free. Can be a significant advantage over a hand built recdec parser for a complex language like SQL.
    - 9y ago

joe_the_user 9y ago

Yes, I think understanding that there's a fundamental difference between the operation of parsing a language and "naive call-and-for-loop programming" is very important. Most naive efforts to parse a language starting with no knowledge simply fail (and that can include, say, things efforts to validate a file name in a somewhat complex file system or to parse a packet in a network protocol). In college, it took me a bit of time to understand what a formal language really was and what the difference between a parser and a simple string processor was and when I arrived in industry, I notice this were something a certain proportion of otherwise experienced programmers simply did not understand this.