5 ms·
Here's a valuable tip for making a compiler/interpreter: don't use a separate lexer and parser like lex and yacc. Parser combinators (also known as parser mona
by smabie 7y ago
Here's a valuable tip for making a compiler/interpreter: don't use a separate lexer and parser like lex and yacc. Parser combinators (also known as parser monads) are so much easier to use. In fact, if you already have decided upon your language's grammar, you can probably write yourself a parser and lexer with a parser combinator inside a day.
- samatman 7y agoAgreed, and this goes even smoother when one realizes the isomorphism between (naive) parser combinators and parsing expression grammars.
- popotamonga 7y agoHow easier are they? I did the lex and yacc for javascript and it was easy (except parsing js's // regex format in lex needed a little hack)
- smabie 7y agoThe easiest. Much much easier than lex and yacc.
- amelius 7y agoWhat is the class of grammar they can handle? (I mean in the sense of LALR(k), LL(k), etc.) And is there a large (e.g. exponential) performance penalty for large lookahead?
- tanin 7y agoThere's still "lookahead" in a hand written parser. The lookahead is decided case by case. Performance penalty only comes if we backtrack in our hand written parsers. I don't think we usually do that. Any glimpse of top-down parser would be simply too slow.
- millstone 7y agoThis is going to be language-specific: parser combinators are much more pleasant in Haskell than in C++ for example. Handwritten recursive descent has a lot going for it, error messages in particular.
- orbifold 7y agoThere is a pretty nice parser combinator library in the capnproto compiler: https://github.com/capnproto/capnproto/tree/master/c%2B%2B/src/kj/parse https://github.com/capnproto/capnproto/tree/master/c%2B%2B/s.... Here is an example of how it is used: https://github.com/capnproto/capnproto/blob/950d23a13f1d602d38b8fe83c2c038dc5d30fba6/c%2B%2B/src/capnp/compiler/parser.c%2B%2B#L411 https://github.com/capnproto/capnproto/blob/950d23a13f1d602d...
- saagarjha 7y agoThey're not too bad in C++; I'm writing one.
- tanin 7y agoYes! I find that writing a parser by hand (using parser combinator) is the most straightforward way (once you know how to write one). It can also support variable-length lookahead, which is really nice.