11 ms·

It's a misconception parsers are easy to write. Plus, they do an unfathomable amount of damage. Parsers are far from harmless pieces of logic you can just thro

by read 13y ago

It's a misconception parsers are easy to write. Plus, they do an unfathomable amount of damage. Parsers are far from harmless pieces of logic you can just throw together. And not just because they take time to write - parsers are physically dangerous. Compiler writers develop incipient carpal tunnel syndrome trying to write parsers. When you finish writing a parser as a language designer the problem of writing a parser for the language doesn't go away. The programming language users might want to apply transformations to source code written in the language -- which now means they need to write brand new parsers from scratch to do these transformations. What s-exprs give you instead is the option to write a "parser" in one function call: using the read function. It doesn't get shorter than that. Now, that's a parser that's easy to write. edit: rewording

joe_the_user 13y ago
It's a misconception that parsers are hard to write and believing this does "unfathomable amount of damage"(whatever that means). If you understand abstract languages, writing a recursive descent parser is a simple, paper and pencil exercise. If you don't understand abstract languages, you should not be designing a language till you stop and learn them and you should STFU about what people designing languages should do until then.
- gamegoblin 13y ago
  Agreed. I wrote a recursive descent parser generator in python and it took about an hour. Takes a BNF grammar and spits out a parser. End of story. Recursive descent parsers are dead simple.
  - read 13y ago
    Yes, the complexity of the parser is related to the size of the language. A smaller language needs a smaller, easier to write parser. Have you ever written a recursive descent parser for C? I realize now what was inaccurate about what I wrote. It's that the things you have to do after you parse might be the more harmful parts. Processing the parse tree you get back. edit: rewording
    - seanmcdirmid 13y ago
      I've gotten really far with a precedence parser before, and as a bonus they are intrinsically incremental. However, beware of braces to match separately.
    - joe_the_user 13y ago
      I would point out that a recursive descent parsing does not have to return an AST or any particular tree, and often it doesn't. Instead, when you create a recursive descent parser, you create a series of functions called whenever a syntax element is discover. In these functions, you construct whatever your final data structures are going to be. Of course, you still can create and return a full abstract syntax tree but one nice thing about recursive descent is that if you are only going to do a few things, you can just have those few operations in your parser and be done with it.
breuleux 13y ago
Top down operator parsing (http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html) is pretty easy to implement, is inherently efficient, and trivial to extend. Even that might be overkill, though: a generic operator parser for unary, binary, ternary, n-ary, and so on will take about 50 lines of code. You can encode a surprisingly large number of control structures with a cleverly crafted precedence parser.
agumonkey 13y ago
may I add this article by Laurence Tratt about parsing : http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/blog/entries/parsing_the_solved_prob... ltu discussion http://lambda-the-ultimate.org/node/4489 http://lambda-the-ultimate.org/node/4489
WalterBright 13y ago
> It's a misconception parsers are easy to write. Really, they are easy. They are literally insignificant when you factor in all the hours you'll work on a language. I wrote another one recently for a small side project. It took more time to write the unit tests for it. The parser practically wrote itself.
- apgwoz 13y ago
  but, to be fair, you've obviously had lots of experience, and understand a great deal more about formal languages and how they translate to something that is trivially parsed, than the majority of people who will read this article. should they attempt a language, they'll likely fail to produce a working parser long before they spendthe rest of the hours on it.
  - jerf 13y ago
    If you can not trivially implement a parser, you probably shouldn't be implementing your own language. The problems only get worse from there. I'm egalitarian inasmuch as I believe every serious programmer ought to implement some sort of toy language at some point, but I'm not so stupid as to think that this is a good idea at all phases of a programmer's development. Beginners should concentrate on other basic tasks, even low-intermediate really should too. I wouldn't reserve this task for "experts" though, because this is one of the big steps in moving from intermediate to expert. (Anyone who has assembled the skill set to implement a toy-but-nontrivial language has assembled the skill set to accomplish a very wide variety of programming tasks. If I were interviewing someone and they could demonstrate this, I would almost entirely cease to care what actual languages or frameworks they may have worked in.)
    - apgwoz 13y ago
      I agree in principle, but that won't stop someone from fighting with shift reduce conflicts or dangling elses for hours on end before giving up. constructing an unambiguous CFG isn't trivial without experience, and it's tough to get that without bashing your head a few times.
csmithuk 13y ago
No-one sane writes parsers any more. People use parser generators.
- munificent 13y ago
  GCC uses a hand-written parser. So does the C# compiler for .NET. V8 and, as far as I know, the other browsers' JS implementations have hand-written parsers. Dart (both the VM and the self-hosted dart2js compiler) have hand-written parsers. Offhand, I'm not aware of any real-world language with lots of users that has a generated parser.
kps 13y ago
The programming language users might want to apply transformations to source code written in the language -- which now means they need to write brand new parsers from scratch to do these transformations. That would be Doing It Wrong. Tools like clang-format (source formatting) and clang-modernize (source transformation to use new language features) use exactly the same parser library — among other things — as the compiler proper.

by read 13y ago

joe_the_user 13y ago

It's a misconception that parsers are hard to write and believing this does "unfathomable amount of damage"(whatever that means). If you understand abstract languages, writing a recursive descent parser is a simple, paper and pencil exercise. If you don't understand abstract languages, you should not be designing a language till you stop and learn them and you should STFU about what people designing languages should do until then.

gamegoblin 13y ago
Agreed. I wrote a recursive descent parser generator in python and it took about an hour. Takes a BNF grammar and spits out a parser. End of story. Recursive descent parsers are dead simple.
- read 13y ago
  Yes, the complexity of the parser is related to the size of the language. A smaller language needs a smaller, easier to write parser. Have you ever written a recursive descent parser for C? I realize now what was inaccurate about what I wrote. It's that the things you have to do after you parse might be the more harmful parts. Processing the parse tree you get back. edit: rewording
  - seanmcdirmid 13y ago
    I've gotten really far with a precedence parser before, and as a bonus they are intrinsically incremental. However, beware of braces to match separately.
  - joe_the_user 13y ago
    I would point out that a recursive descent parsing does not have to return an AST or any particular tree, and often it doesn't. Instead, when you create a recursive descent parser, you create a series of functions called whenever a syntax element is discover. In these functions, you construct whatever your final data structures are going to be. Of course, you still can create and return a full abstract syntax tree but one nice thing about recursive descent is that if you are only going to do a few things, you can just have those few operations in your parser and be done with it.

breuleux 13y ago

Top down operator parsing (http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html) is pretty easy to implement, is inherently efficient, and trivial to extend. Even that might be overkill, though: a generic operator parser for unary, binary, ternary, n-ary, and so on will take about 50 lines of code. You can encode a surprisingly large number of control structures with a cleverly crafted precedence parser.

agumonkey 13y ago

may I add this article by Laurence Tratt about parsing : http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/blog/entries/parsing_the_solved_prob... ltu discussion http://lambda-the-ultimate.org/node/4489 http://lambda-the-ultimate.org/node/4489

WalterBright 13y ago

> It's a misconception parsers are easy to write. Really, they are easy. They are literally insignificant when you factor in all the hours you'll work on a language. I wrote another one recently for a small side project. It took more time to write the unit tests for it. The parser practically wrote itself.

apgwoz 13y ago
but, to be fair, you've obviously had lots of experience, and understand a great deal more about formal languages and how they translate to something that is trivially parsed, than the majority of people who will read this article. should they attempt a language, they'll likely fail to produce a working parser long before they spendthe rest of the hours on it.
- jerf 13y ago
  If you can not trivially implement a parser, you probably shouldn't be implementing your own language. The problems only get worse from there. I'm egalitarian inasmuch as I believe every serious programmer ought to implement some sort of toy language at some point, but I'm not so stupid as to think that this is a good idea at all phases of a programmer's development. Beginners should concentrate on other basic tasks, even low-intermediate really should too. I wouldn't reserve this task for "experts" though, because this is one of the big steps in moving from intermediate to expert. (Anyone who has assembled the skill set to implement a toy-but-nontrivial language has assembled the skill set to accomplish a very wide variety of programming tasks. If I were interviewing someone and they could demonstrate this, I would almost entirely cease to care what actual languages or frameworks they may have worked in.)
  - apgwoz 13y ago
    I agree in principle, but that won't stop someone from fighting with shift reduce conflicts or dangling elses for hours on end before giving up. constructing an unambiguous CFG isn't trivial without experience, and it's tough to get that without bashing your head a few times.

csmithuk 13y ago

No-one sane writes parsers any more. People use parser generators.

munificent 13y ago
GCC uses a hand-written parser. So does the C# compiler for .NET. V8 and, as far as I know, the other browsers' JS implementations have hand-written parsers. Dart (both the VM and the self-hosted dart2js compiler) have hand-written parsers. Offhand, I'm not aware of any real-world language with lots of users that has a generated parser.

kps 13y ago

The programming language users might want to apply transformations to source code written in the language -- which now means they need to write brand new parsers from scratch to do these transformations. That would be Doing It Wrong. Tools like clang-format (source formatting) and clang-modernize (source transformation to use new language features) use exactly the same parser library — among other things — as the compiler proper.