4 ms·

I started making a language a few months ago. I found Douglas Crockford's parser from his Top Down Operator Precedence paper pretty useful, which is here: http:

I started making a language a few months ago. I found Douglas Crockford's parser from his Top Down Operator Precedence paper pretty useful, which is here: http://javascript.crockford.com/tdop/index.html http://javascript.crockford.com/tdop/index.html When looking for resources on making toy languages, most of them said not to bother with a parser and use a pre-built solution. I think they're probably wrong - the parser is actually pretty easy (relative to the rest of the process of getting a language working) and at a stretch, fun.

tachyonbeam 12y ago
I agree. It's not as hard as one might think. I implemented my own handwritten JS parser using TDOP: https://github.com/higgsjs/Higgs/blob/master/source/parser/parser.d#L689 https://github.com/higgsjs/Higgs/blob/master/source/parser/p... I think it's more flexible and maintainable this way. I didn't have to wrestle with odd grammar rules. Implementing the JS "automatic semicolon insertion" with parser generator tools seems like it would have been a cluster headache.
- thomasfoster96 12y ago
  I have to admit I also wrote my own parser because I was keen on implementing some pretty advanced macros in it (which I've almost done already). A lot of those parser generator tools assume you have a nice C-like language syntax.
seanmcdirmid 12y ago
Yes! I write my own recursive descent parsers because my programming languages tend to have incremental execution stories to them (you can see an example at http://research.microsoft.com/en-us/people/smcdirm/managedtime.aspx http://research.microsoft.com/en-us/people/smcdirm/managedti...). And writing a recursive descent parser really isn't that hard, plus it gives you more flexibility in tweaking error recovery. It also turns out that in industry, auto generated parsers are rarely used (Java is an exception) given performance and error recovery concerns. On the topic of precedence parsing, they have some really good properties in an incremental context: you can start parsing anywhere and the results will be the same. The problem is expressiveness, and while I came up with some hacks to push them beyond operators, pure recursive descent is much easier to work with (as I learned from Martin Odersky's scalac compiler).
ufo 12y ago
For me the big advantage of using a parser generator is that they let you write things a bit more declaratively. Bottom up parser generators also have the advantage of being able to recognize some grammars that top down parsers can't and they also detect grammar ambiguities at compile time. That said, handwritten top down parsers are very tweakable and flexible which can be a big plus. In particular, error recovery and things like semicolon insertion. You also get more control over code size and parser performance.
- thomasfoster96 12y ago
  I can see why people do use a parser generator. For me though, the language I'm making has a fairly simplistic syntax, and I value code size and parser performance more than I should.
  - kazinator 12y ago
    I have used lex and yacc over almost 30 years numerous, numerous times. I always regretted the decision later. It's a myopic concession for short-term gain. The tools generate a monstrous, ugly mess that nobody understands, which is linked into your executable. When it gets complicated, debugging it is a massage session, where you make changes that you don't entirely understand in hopes that a desired behavioral change comes about. Here is a debugging fail: you cannot just put a break point on a rule, because it's not a function. The state machine is traversing multiple rules at the same time. In a recursive-descent parser, you can break on a rule and get a call stack.
  - Jweb_Guru 12y ago
    If you value parser performance you should use a parser generator. Handwritten parsers rarely approach the performance of a fast table-based generated parser.
    - ufo 12y ago
      The example I was thinking of when I mentioned performance was Lua. Instead of generating a syntax tree the recursive descent parser directly spits out bytecode as it goes, which ends up being a big performance win on large source files.
mamcx 12y ago
I agree. The parsing step is distracting. I have TONS of questions and all the tutorials do the parsing stuff, and stop at doing integer +/*-, maybe vars, maybe if, maybe basic functions! I'm doing one, and I'm only working on the AST. I take the idea from this blog: http://www.trelford.com/blog/post/interpreter.aspx http://www.trelford.com/blog/post/interpreter.aspx And from http://www.itu.dk/people/sestoft/plc/ http://www.itu.dk/people/sestoft/plc/. So I get rid of the parsing, and go directly at "how do type checking?", "How I map vars to the environment?", "How make the debugger???", "So, I can have a AST for INTS, BOOLS... now how let the user create your own types???", "How make possible to do macros? I'm not a LISP!", "I'm on F#. How lift the stuff F# already have to do not doing it again???", "What to do: Erlang actors or GO CSP? and how?", "How do pattern matching", "Auto-instrument the code interpreter with dtrace or similar, and why I think this is good?", "I wanna be a reactive language?", "I decide the language be relational. I strongly believe that is amazing. I don't know yet why and how prove it" and a huge list like this... I don't have a clean answer yet for some of this questions! Also, I get rid of the idea of make a compiler, and do a interpreter instead. That is another distraction. I suspect that if later on I turn the interpreter to a bytecode, the step to full compilation will be simple, and without solve several questions about the full language the task of rewrite both the parsing and the compiler is not cool.
- mrcsparker 12y ago
  I have written a few languages here and there. Hope this helps. They are all separate parts, and you can do them in any order you want. I like to think of the language as two parts - syntax and features. How do I want the language to look and what features do I want the language to have? The parser and lexer handle the syntax, and the AST handles the features. This way, I can play around with the syntax of the language a little later. I would start with a really simple language: - add expressions, proper infix support for arithmetic - variables - if / else / else if - scoping / functions - loops if you don't want to just use recursion then, you can get more advanced: - lambda expressions / first class functions / closures - namespaces or types - macros. if you can make nice looking lisp-style macros for an infix language i would love you write it as an interpreter, add an llvm backend. It should be fun. do a little at a time.
ioddly 12y ago
The more you do yourself, the more you will learn. If you're just learning and not trying to build the next big programming language, try and do some of the low level stuff yourself. Write a parser, write a garbage collector and a virtual machine, re-write the compiler in the language itself. Go hog wild.
- smilepet_26 12y ago
  that's a great suggestion and seems to be useful tip to get started to writing a new language on our own.
- JadeNB 12y ago
  > The more you do yourself, the more you will learn. This is true once you complete the project, but it seems like it can be dangerous: if you start off your mission to make a programming language by soldering components on a breadboard, say, then, you will learn something, to be sure, but you will probably get so embroiled in preliminaries that you will never learn what you intended to learn. (Of course, sometimes learning something other than what you intended is a good thing ….)

tachyonbeam 12y ago

I agree. It's not as hard as one might think. I implemented my own handwritten JS parser using TDOP: https://github.com/higgsjs/Higgs/blob/master/source/parser/parser.d#L689 https://github.com/higgsjs/Higgs/blob/master/source/parser/p... I think it's more flexible and maintainable this way. I didn't have to wrestle with odd grammar rules. Implementing the JS "automatic semicolon insertion" with parser generator tools seems like it would have been a cluster headache.

thomasfoster96 12y ago
I have to admit I also wrote my own parser because I was keen on implementing some pretty advanced macros in it (which I've almost done already). A lot of those parser generator tools assume you have a nice C-like language syntax.

seanmcdirmid 12y ago

Yes! I write my own recursive descent parsers because my programming languages tend to have incremental execution stories to them (you can see an example at http://research.microsoft.com/en-us/people/smcdirm/managedtime.aspx http://research.microsoft.com/en-us/people/smcdirm/managedti...). And writing a recursive descent parser really isn't that hard, plus it gives you more flexibility in tweaking error recovery. It also turns out that in industry, auto generated parsers are rarely used (Java is an exception) given performance and error recovery concerns. On the topic of precedence parsing, they have some really good properties in an incremental context: you can start parsing anywhere and the results will be the same. The problem is expressiveness, and while I came up with some hacks to push them beyond operators, pure recursive descent is much easier to work with (as I learned from Martin Odersky's scalac compiler).

ufo 12y ago

For me the big advantage of using a parser generator is that they let you write things a bit more declaratively. Bottom up parser generators also have the advantage of being able to recognize some grammars that top down parsers can't and they also detect grammar ambiguities at compile time. That said, handwritten top down parsers are very tweakable and flexible which can be a big plus. In particular, error recovery and things like semicolon insertion. You also get more control over code size and parser performance.

thomasfoster96 12y ago
I can see why people do use a parser generator. For me though, the language I'm making has a fairly simplistic syntax, and I value code size and parser performance more than I should.
- kazinator 12y ago
  I have used lex and yacc over almost 30 years numerous, numerous times. I always regretted the decision later. It's a myopic concession for short-term gain. The tools generate a monstrous, ugly mess that nobody understands, which is linked into your executable. When it gets complicated, debugging it is a massage session, where you make changes that you don't entirely understand in hopes that a desired behavioral change comes about. Here is a debugging fail: you cannot just put a break point on a rule, because it's not a function. The state machine is traversing multiple rules at the same time. In a recursive-descent parser, you can break on a rule and get a call stack.
- Jweb_Guru 12y ago
  If you value parser performance you should use a parser generator. Handwritten parsers rarely approach the performance of a fast table-based generated parser.
  - ufo 12y ago
    The example I was thinking of when I mentioned performance was Lua. Instead of generating a syntax tree the recursive descent parser directly spits out bytecode as it goes, which ends up being a big performance win on large source files.

mamcx 12y ago

I agree. The parsing step is distracting. I have TONS of questions and all the tutorials do the parsing stuff, and stop at doing integer +/*-, maybe vars, maybe if, maybe basic functions! I'm doing one, and I'm only working on the AST. I take the idea from this blog: http://www.trelford.com/blog/post/interpreter.aspx http://www.trelford.com/blog/post/interpreter.aspx And from http://www.itu.dk/people/sestoft/plc/ http://www.itu.dk/people/sestoft/plc/. So I get rid of the parsing, and go directly at "how do type checking?", "How I map vars to the environment?", "How make the debugger???", "So, I can have a AST for INTS, BOOLS... now how let the user create your own types???", "How make possible to do macros? I'm not a LISP!", "I'm on F#. How lift the stuff F# already have to do not doing it again???", "What to do: Erlang actors or GO CSP? and how?", "How do pattern matching", "Auto-instrument the code interpreter with dtrace or similar, and why I think this is good?", "I wanna be a reactive language?", "I decide the language be relational. I strongly believe that is amazing. I don't know yet why and how prove it" and a huge list like this... I don't have a clean answer yet for some of this questions! Also, I get rid of the idea of make a compiler, and do a interpreter instead. That is another distraction. I suspect that if later on I turn the interpreter to a bytecode, the step to full compilation will be simple, and without solve several questions about the full language the task of rewrite both the parsing and the compiler is not cool.

mrcsparker 12y ago
I have written a few languages here and there. Hope this helps. They are all separate parts, and you can do them in any order you want. I like to think of the language as two parts - syntax and features. How do I want the language to look and what features do I want the language to have? The parser and lexer handle the syntax, and the AST handles the features. This way, I can play around with the syntax of the language a little later. I would start with a really simple language: - add expressions, proper infix support for arithmetic - variables - if / else / else if - scoping / functions - loops if you don't want to just use recursion then, you can get more advanced: - lambda expressions / first class functions / closures - namespaces or types - macros. if you can make nice looking lisp-style macros for an infix language i would love you write it as an interpreter, add an llvm backend. It should be fun. do a little at a time.

ioddly 12y ago

The more you do yourself, the more you will learn. If you're just learning and not trying to build the next big programming language, try and do some of the low level stuff yourself. Write a parser, write a garbage collector and a virtual machine, re-write the compiler in the language itself. Go hog wild.

smilepet_26 12y ago
that's a great suggestion and seems to be useful tip to get started to writing a new language on our own.
JadeNB 12y ago
> The more you do yourself, the more you will learn. This is true once you complete the project, but it seems like it can be dangerous: if you start off your mission to make a programming language by soldering components on a breadboard, say, then, you will learn something, to be sure, but you will probably get so embroiled in preliminaries that you will never learn what you intended to learn. (Of course, sometimes learning something other than what you intended is a good thing ….)