4 ms·

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decad

by girvo 12y ago

This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.

jbzz 12y ago
Parsing Techniques by Dick Grune is THE bible for parsing.
- dkarapetyan 12y ago
  It is a nice reference but you won't learn anything from that if you're a beginner. It's super heavy on theory and very light on implementation.
  - thesz 12y ago
    I think you get it backwards. I learned a lot and PTAPG introduction specifically says that it avoids heavy theory. It has all algorithms required in very understandable presentation. It also says what this or that algorithm does to exploit that or this feature from grammar structure.
dkarapetyan 12y ago
Start here: http://nathansuniversity.com/ http://nathansuniversity.com/. All the stuff in the dragon book is designed for limited memory and limited computing capability environments. There is no reason to worry about LL(k) parse table size or predict and follow sets when you don't have to. For most practical purposes you can get away with basic recursive descent or PEG parsers. The link I pointed you to starts with peg.js which is PEG parser generator in JavaScript. If you get through PL101 then picking up the stuff in the dragon book or any other book on parsing and compiling technology will be much easier. Another resource I like is "Compiler Design: Virtual Machines" (http://smile.amazon.com/Compiler-Design-Machines-Reinhard-Wilhelm/dp/3642149081 http://smile.amazon.com/Compiler-Design-Machines-Reinhard-Wi...). Still going through that one but it is very readable and if you go through PL101 then you'll have all the tools to implement the virtual machines described in that book. It is much easier to write a compiler to target machine code or some other language like C when you've built a few targets yourself and understand the trade-offs involved. There's also http://www.greatcodeclub.com/ http://www.greatcodeclub.com/. I think one of the projects is a simple virtual machine and another one is a compiler. Well worth the admission price if you're a beginner and want some help getting started. Hanselman's rule about finiteness of keystrokes applies and I recently wrote some notes about budding PL enthusiasts: http://www.scriptcrafty.com/tips-for-the-budding-pl-enthusiast/ http://www.scriptcrafty.com/tips-for-the-budding-pl-enthusia....
- girvo 12y ago
  You're absolutely brilliant. Thanks so much!
  - dkarapetyan 12y ago
    No problem. I think more programmers should know about this stuff so happy to help.
Flow 12y ago
This is exactly what you want: https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers
- tjaerv 12y ago
  Seconded. This was a good course.
sandal 12y ago
If you want to just see an example of building a parser, you could check out "Parsing JSON the hard way", which uses Racc: https://practicingruby.com/articles/parsing-json-the-hard-way https://practicingruby.com/articles/parsing-json-the-hard-wa...
Dewie 12y ago
The dragon book (at least the first edition) has 330 pages on parsing. 330 pages. IMO that is excessive for a beginner, given how relatively easy it is to implement a parser for a fairly standard language.
keithrel 12y ago
Just start writing the parser/compiler/interpreter for your language, today. You will quickly learn what you need, tokenizer/lexer, some way to represent the AST, how to represent types (if you have any), etc. Later start looking at the literature to see how "its really done". I find this approach takes more time perhaps but I have a much better appreciation for what I am reading afterwards (Oh that's why they did X!).
sklogic 12y ago
You may also want to take a look at this one: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
rabarbers 12y ago
I started with udacity course: https://www.udacity.com/course/cs262 https://www.udacity.com/course/cs262 it teached how to build simple javascript parser.

by girvo 12y ago

jbzz 12y ago

Parsing Techniques by Dick Grune is THE bible for parsing.

dkarapetyan 12y ago
It is a nice reference but you won't learn anything from that if you're a beginner. It's super heavy on theory and very light on implementation.
- thesz 12y ago
  I think you get it backwards. I learned a lot and PTAPG introduction specifically says that it avoids heavy theory. It has all algorithms required in very understandable presentation. It also says what this or that algorithm does to exploit that or this feature from grammar structure.

dkarapetyan 12y ago

Start here: http://nathansuniversity.com/ http://nathansuniversity.com/. All the stuff in the dragon book is designed for limited memory and limited computing capability environments. There is no reason to worry about LL(k) parse table size or predict and follow sets when you don't have to. For most practical purposes you can get away with basic recursive descent or PEG parsers. The link I pointed you to starts with peg.js which is PEG parser generator in JavaScript. If you get through PL101 then picking up the stuff in the dragon book or any other book on parsing and compiling technology will be much easier. Another resource I like is "Compiler Design: Virtual Machines" (http://smile.amazon.com/Compiler-Design-Machines-Reinhard-Wilhelm/dp/3642149081 http://smile.amazon.com/Compiler-Design-Machines-Reinhard-Wi...). Still going through that one but it is very readable and if you go through PL101 then you'll have all the tools to implement the virtual machines described in that book. It is much easier to write a compiler to target machine code or some other language like C when you've built a few targets yourself and understand the trade-offs involved. There's also http://www.greatcodeclub.com/ http://www.greatcodeclub.com/. I think one of the projects is a simple virtual machine and another one is a compiler. Well worth the admission price if you're a beginner and want some help getting started. Hanselman's rule about finiteness of keystrokes applies and I recently wrote some notes about budding PL enthusiasts: http://www.scriptcrafty.com/tips-for-the-budding-pl-enthusiast/ http://www.scriptcrafty.com/tips-for-the-budding-pl-enthusia....

girvo 12y ago
You're absolutely brilliant. Thanks so much!
- dkarapetyan 12y ago
  No problem. I think more programmers should know about this stuff so happy to help.

Flow 12y ago

This is exactly what you want: https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers

tjaerv 12y ago
Seconded. This was a good course.

sandal 12y ago

If you want to just see an example of building a parser, you could check out "Parsing JSON the hard way", which uses Racc: https://practicingruby.com/articles/parsing-json-the-hard-way https://practicingruby.com/articles/parsing-json-the-hard-wa...

Dewie 12y ago

The dragon book (at least the first edition) has 330 pages on parsing. 330 pages. IMO that is excessive for a beginner, given how relatively easy it is to implement a parser for a fairly standard language.

keithrel 12y ago

Just start writing the parser/compiler/interpreter for your language, today. You will quickly learn what you need, tokenizer/lexer, some way to represent the AST, how to represent types (if you have any), etc. Later start looking at the literature to see how "its really done". I find this approach takes more time perhaps but I have a much better appreciation for what I am reading afterwards (Oh that's why they did X!).

sklogic 12y ago

You may also want to take a look at this one: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...

rabarbers 12y ago

I started with udacity course: https://www.udacity.com/course/cs262 https://www.udacity.com/course/cs262 it teached how to build simple javascript parser.