3 ms·

This is awesome. I have been writing and re-writing several horrible regex-based parsers (https://github.com/erikpukinskis/parse-a-little-js https://github.com/

This is awesome. I have been writing and re-writing several horrible regex-based parsers (https://github.com/erikpukinskis/parse-a-little-js https://github.com/erikpukinskis/parse-a-little-js) to back an IDE I am building, and I can sense I am well passed the “you need to learn how to do this properly, Erik) point. So far this book seems to be just at the right pitch for my purposes. Does anyone else have any recommendationed reading for someone like me? My absolute priority is keeping the code simple and having as few features as possible. I’ve actually been using my ignorance as a design constraint... I don’t want to allow complex syntax in the editor, (it’s not a general purpose editor) and I want the parser source to be approachable. But perhaps by this point I may have the resolve to resist the power a proper parser will give me.

jstimpfle 8y ago
> Does anyone else have any recommendationed reading for someone like me? My absolute priority is keeping the code simple and having as few features as possible. Of course, try the OP, maybe there is something for you. You might want to watch Per Vognsen's "bitwise" series (another guy that was at RAD Game Tools I think, like Sean Barrett who is linked in a sibling comment) on youtube as well. The recordings are very approachable and mostly straightforward. Having a little theory to guide you is important, but mostly it's a practical issue. So I mostly recommend trying various approaches yourself. Get high-level ideas somewhere else, and then make implementations on your own. In that spirit, a few high-level tips for approaching parsing, from the top of my head. How you parse a language depends heavily on what the parsed language is. You need a good feel for the language to understand how it wants to be parsed. If you have the luxury of making your own language, great! Pretty much every programming language should be split into parser and lexer for sure, although the stages might need to interact (e.g., parser detects a switch to a different, embedded language, and lets the lexer know). As for the lexer, absolutely don't use any tools. Probably not even regular expressions. Just handcode the stuff as you go. It's boring but extremely straightforward code. You get a lot of flexibility and debuggability this way, and no painful dependencies. In the simplest case the Lexer is a only few type definitions (Token stream wrapper around some I/O facility, Token kind enum, Token record) and a lex_next_token() function. As for the parser, the best computer languages are those that can be parsed by recursive descent (again, no tools. A C-like language is enough for implementation). You look at the next input token and do the appropriate thing. Parsing is extremely simple if a language is designed to be parsed that way. The more mathematical approaches to parsing (like LR) are pretty boring and unapproachable in my opinion. They are comparatively hard to understand and debug. Besides parsing of global structure, most languages have an expression grammar with infix operators and precedence levels. You can work out how to parse that separately. There is the shunting yard algorithm, which is a table driven method unlike recursive descent. I guess you should know how to use it, but you will also quickly see that it gets hairy as soon as function calls and other non-infix syntaxes come into play. Parsing expressions with recursive descent, too, turns out to be not hard after all, and a nice benefit from that approach is that the parser is written in a consistent style.
fao_ 8y ago
> Does anyone else have any recommendationed reading for someone like me? My absolute priority is keeping the code simple and having as few features as possible. http://nothings.org/computer/lexing.html http://nothings.org/computer/lexing.html the focus is on speed, but honestly I found this code easier to read and write (once I got my head around the general concept) than most other parser code I've seen.
shortercode 8y ago
I completed the "Tree walking interpreter" section of this book about a month ago, I used modern JS to write it and I found it a really good experience and learned a fair bit. A lot of the content is obviously about implementing the interpreter so there's probably quite a bit that doesn't apply to your project, but If your looking to make your lexer as simple as possible I would recommend looking at (http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...). It's written by the same guy, and gives a short look on pratt parsers, which is one of the simplest ways to write a parser. There's also a simple language he wrote that uses the method as an example available on GitHub. At a top level you end up with declarations like: infix(token: "plus", parselet: BinaryOperator, precedence: 13); Having done a fair bit of prototyping parsers and reading about it the hardest parts of parsing JS are regex literals and automatic semi-colon insertion.
criddell 8y ago
Bob Nystrom is a fantastic writer. If you like this book, then I would highly recommend his previous book Game Programming Patterns. Even if you don't write games, there's a lot of great stuff in here. He's a very good teacher.
s-shellfish 8y ago
My interpreters course used this book, as well as 'the little schemer'. They follow a lot of conventions that I find really useful for software development (various intricacies of languages in active development tend to follow the same conventions of diagramming, labeling, notation, etc - all really important things to keep standard when reasoning about, teaching, and explaining programming languages!) https://www.amazon.com/Essentials-Programming-Languages-MIT-Press/dp/0262062798 https://www.amazon.com/Essentials-Programming-Languages-MIT-... https://github.com/mwand/eopl3 https://github.com/mwand/eopl3 https://mitpress.mit.edu/books/little-schemer-fourth-edition https://mitpress.mit.edu/books/little-schemer-fourth-edition There's also this book that from my understanding, a lot of people consider fairly foundational / useful (own it, haven't read it) https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html
jonsagara 8y ago
> Does anyone else have any recommendationed reading for someone like me? Writing an Interpreter in Go (https://interpreterbook.com/ https://interpreterbook.com/) It's a very approachable introduction to lexing and parsing using nothing but Go and its standard library.
PretzelFisch 8y ago
You might check "Language Implementation Patterns" I have found it usefull in the pass when creating a DSL https://pragprog.com/book/tpdsl/language-implementation-patterns https://pragprog.com/book/tpdsl/language-implementation-patt...

jstimpfle 8y ago

> Does anyone else have any recommendationed reading for someone like me? My absolute priority is keeping the code simple and having as few features as possible. Of course, try the OP, maybe there is something for you. You might want to watch Per Vognsen's "bitwise" series (another guy that was at RAD Game Tools I think, like Sean Barrett who is linked in a sibling comment) on youtube as well. The recordings are very approachable and mostly straightforward. Having a little theory to guide you is important, but mostly it's a practical issue. So I mostly recommend trying various approaches yourself. Get high-level ideas somewhere else, and then make implementations on your own. In that spirit, a few high-level tips for approaching parsing, from the top of my head. How you parse a language depends heavily on what the parsed language is. You need a good feel for the language to understand how it wants to be parsed. If you have the luxury of making your own language, great! Pretty much every programming language should be split into parser and lexer for sure, although the stages might need to interact (e.g., parser detects a switch to a different, embedded language, and lets the lexer know). As for the lexer, absolutely don't use any tools. Probably not even regular expressions. Just handcode the stuff as you go. It's boring but extremely straightforward code. You get a lot of flexibility and debuggability this way, and no painful dependencies. In the simplest case the Lexer is a only few type definitions (Token stream wrapper around some I/O facility, Token kind enum, Token record) and a lex_next_token() function. As for the parser, the best computer languages are those that can be parsed by recursive descent (again, no tools. A C-like language is enough for implementation). You look at the next input token and do the appropriate thing. Parsing is extremely simple if a language is designed to be parsed that way. The more mathematical approaches to parsing (like LR) are pretty boring and unapproachable in my opinion. They are comparatively hard to understand and debug. Besides parsing of global structure, most languages have an expression grammar with infix operators and precedence levels. You can work out how to parse that separately. There is the shunting yard algorithm, which is a table driven method unlike recursive descent. I guess you should know how to use it, but you will also quickly see that it gets hairy as soon as function calls and other non-infix syntaxes come into play. Parsing expressions with recursive descent, too, turns out to be not hard after all, and a nice benefit from that approach is that the parser is written in a consistent style.

fao_ 8y ago

> Does anyone else have any recommendationed reading for someone like me? My absolute priority is keeping the code simple and having as few features as possible. http://nothings.org/computer/lexing.html http://nothings.org/computer/lexing.html the focus is on speed, but honestly I found this code easier to read and write (once I got my head around the general concept) than most other parser code I've seen.

shortercode 8y ago

I completed the "Tree walking interpreter" section of this book about a month ago, I used modern JS to write it and I found it a really good experience and learned a fair bit. A lot of the content is obviously about implementing the interpreter so there's probably quite a bit that doesn't apply to your project, but If your looking to make your lexer as simple as possible I would recommend looking at (http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...). It's written by the same guy, and gives a short look on pratt parsers, which is one of the simplest ways to write a parser. There's also a simple language he wrote that uses the method as an example available on GitHub. At a top level you end up with declarations like: infix(token: "plus", parselet: BinaryOperator, precedence: 13); Having done a fair bit of prototyping parsers and reading about it the hardest parts of parsing JS are regex literals and automatic semi-colon insertion.

criddell 8y ago

Bob Nystrom is a fantastic writer. If you like this book, then I would highly recommend his previous book Game Programming Patterns. Even if you don't write games, there's a lot of great stuff in here. He's a very good teacher.

s-shellfish 8y ago

My interpreters course used this book, as well as 'the little schemer'. They follow a lot of conventions that I find really useful for software development (various intricacies of languages in active development tend to follow the same conventions of diagramming, labeling, notation, etc - all really important things to keep standard when reasoning about, teaching, and explaining programming languages!) https://www.amazon.com/Essentials-Programming-Languages-MIT-Press/dp/0262062798 https://www.amazon.com/Essentials-Programming-Languages-MIT-... https://github.com/mwand/eopl3 https://github.com/mwand/eopl3 https://mitpress.mit.edu/books/little-schemer-fourth-edition https://mitpress.mit.edu/books/little-schemer-fourth-edition There's also this book that from my understanding, a lot of people consider fairly foundational / useful (own it, haven't read it) https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html

jonsagara 8y ago

> Does anyone else have any recommendationed reading for someone like me? Writing an Interpreter in Go (https://interpreterbook.com/ https://interpreterbook.com/) It's a very approachable introduction to lexing and parsing using nothing but Go and its standard library.

PretzelFisch 8y ago

You might check "Language Implementation Patterns" I have found it usefull in the pass when creating a DSL https://pragprog.com/book/tpdsl/language-implementation-patterns https://pragprog.com/book/tpdsl/language-implementation-patt...