4 ms·

One day I decided to write a simple lexer-parser. It's really not black magic as it's commonly made out to be. You read in one character at a time to build "tok

One day I decided to write a simple lexer-parser. It's really not black magic as it's commonly made out to be. You read in one character at a time to build "tokens" (e.g. one-to-n character sequences meaning something like "assign", "equals", "add") and then you use recursive methods to return data structures built out of the tokens. Honestly, the hardest part is remembering mathematical precedence, which doesn't even have much to do with parsing per se. Of course, a compiler backend is a much deeper concept, getting into things like register colouring and such. If you were to write a simple stack-based VM, it'd be much simpler. I've thought of doing exactly this for embedded systems projects where all I have is Assembly, or a very bad C compiler.

SilasX 8y ago
Yes, that was my experience on the nand2tetris course, which teaches that as project 10 and 11: http://nand2tetris.org/course.php http://nand2tetris.org/course.php Interestiny, the toy language you’re writing a compiler for doesn’t have operator precedence except for parentheses, so it sidesteps that problem.
Forge36 8y ago
Annoying thing I learned from doing that: source code does not follow a recursive structure. Preprocessor directives allow for some really strange structures. Of course it only caused my problems for a single file at work. I think a custom stack I can read through when the parsing gets weird makes slightly more sense in retrospect.
- setr 8y ago
  never wrote a c parser but I don't see why the preprocessor would change it from being recursive as long as C is; after preprocessing finishes, you should just have normal C?
userbinator 8y ago
A recommended article for those who want to know more about how to parse expressions with precedence very simply and easily: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
drexlspivey 8y ago
David Beazley gave a talk on the exact topic a couple of weeks ago in PyCon. https://www.youtube.com/watch?v=zJ9z6Ge-vXs https://www.youtube.com/watch?v=zJ9z6Ge-vXs
- wenc 8y ago
  I was at that talk. Beazley is an entertaining speaker (always has been), but frankly I was surprised how many people were oohing-and-aahing over the material as if it was new. A lot of the stuff covered can be found in any intro to compilers course. Also Ply has been surpassed for many years by better parsing tools in Python. Sly, which was demonstrated, doesn't seem to be production grade yet.
  - jmcqk6 8y ago
    >A lot of the stuff covered can be found in any intro to compilers course. So really, you're surprised that not many people have taken an intro to compilers course?
    - wenc 8y ago
      Yes. This was at PyCon. A substantial number of people there have computer science degrees. A compilers course is part of most standard CS curricula.
    - jcadam 8y ago
      It was a required course in my BSCS program, and I didn't even go to a big name tech school. So, yes, I'd expect someone with a CS degree to have written a simple compiler.
      - omaranto 8y ago
        Do you expect most programmers to have CS degrees?
    - wenc 8y ago
      Upon reflection, I think my attitude was wrong. I really oughtn't to have been surprised. There were many developers in the crowd who may not have had a computer science education (developers today, especially web developers, often come from a multitude of disciplines). Sure, there were a ton of CS people, but were also a ton of non-CS people (Math, EE, psych, design, etc.). If the latter group managed to learn something new and interesting from the talk, I ought to be happy for them. I think my reaction was a knee-jerk reaction against how easily people become impressed by things these days. It's ok to be encouraging towards others but in an atmosphere of overly-positive attitudes (especially in SV), there is a certain lack of discernment with respect to ideas and technologies which leads to bandwagonning and susceptibility to marketing (case in point, the early adopters of MongoDB). I'm convinced this has a cost to the tech community. But that is no excuse for me to have a holier-than-thou attitude. It's condescending and discouraging toward people who are just trying to learn [1]. I retract my words. [1] https://news.ycombinator.com/item?id=14225033 https://news.ycombinator.com/item?id=14225033
WalterBright 8y ago
Lexing/parsing is the easiest part of writing a compiler, by far. Even writing the C preprocessor is much, much harder.
vfinn 8y ago
Bisqwit on Youtube has a nice series called "How to Create a Compiler": https://youtu.be/eF9qWbuQLuw https://youtu.be/eF9qWbuQLuw

SilasX 8y ago

Yes, that was my experience on the nand2tetris course, which teaches that as project 10 and 11: http://nand2tetris.org/course.php http://nand2tetris.org/course.php Interestiny, the toy language you’re writing a compiler for doesn’t have operator precedence except for parentheses, so it sidesteps that problem.

Forge36 8y ago

Annoying thing I learned from doing that: source code does not follow a recursive structure. Preprocessor directives allow for some really strange structures. Of course it only caused my problems for a single file at work. I think a custom stack I can read through when the parsing gets weird makes slightly more sense in retrospect.

setr 8y ago
never wrote a c parser but I don't see why the preprocessor would change it from being recursive as long as C is; after preprocessing finishes, you should just have normal C?

userbinator 8y ago

A recommended article for those who want to know more about how to parse expressions with precedence very simply and easily: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

drexlspivey 8y ago

David Beazley gave a talk on the exact topic a couple of weeks ago in PyCon. https://www.youtube.com/watch?v=zJ9z6Ge-vXs https://www.youtube.com/watch?v=zJ9z6Ge-vXs

wenc 8y ago
I was at that talk. Beazley is an entertaining speaker (always has been), but frankly I was surprised how many people were oohing-and-aahing over the material as if it was new. A lot of the stuff covered can be found in any intro to compilers course. Also Ply has been surpassed for many years by better parsing tools in Python. Sly, which was demonstrated, doesn't seem to be production grade yet.
- jmcqk6 8y ago
  >A lot of the stuff covered can be found in any intro to compilers course. So really, you're surprised that not many people have taken an intro to compilers course?
  - wenc 8y ago
    Yes. This was at PyCon. A substantial number of people there have computer science degrees. A compilers course is part of most standard CS curricula.
  - jcadam 8y ago
    It was a required course in my BSCS program, and I didn't even go to a big name tech school. So, yes, I'd expect someone with a CS degree to have written a simple compiler.
    - omaranto 8y ago
      Do you expect most programmers to have CS degrees?
  - wenc 8y ago
    Upon reflection, I think my attitude was wrong. I really oughtn't to have been surprised. There were many developers in the crowd who may not have had a computer science education (developers today, especially web developers, often come from a multitude of disciplines). Sure, there were a ton of CS people, but were also a ton of non-CS people (Math, EE, psych, design, etc.). If the latter group managed to learn something new and interesting from the talk, I ought to be happy for them. I think my reaction was a knee-jerk reaction against how easily people become impressed by things these days. It's ok to be encouraging towards others but in an atmosphere of overly-positive attitudes (especially in SV), there is a certain lack of discernment with respect to ideas and technologies which leads to bandwagonning and susceptibility to marketing (case in point, the early adopters of MongoDB). I'm convinced this has a cost to the tech community. But that is no excuse for me to have a holier-than-thou attitude. It's condescending and discouraging toward people who are just trying to learn [1]. I retract my words. [1] https://news.ycombinator.com/item?id=14225033 https://news.ycombinator.com/item?id=14225033

WalterBright 8y ago

Lexing/parsing is the easiest part of writing a compiler, by far. Even writing the C preprocessor is much, much harder.

vfinn 8y ago

Bisqwit on Youtube has a nice series called "How to Create a Compiler": https://youtu.be/eF9qWbuQLuw https://youtu.be/eF9qWbuQLuw