4 ms·

* Try to quickly write the whole thing as a single recursive descent parser. Note the exploding amount of ugliness. Give up. * Separate out the tokenizer (nov

* Try to quickly write the whole thing as a single recursive descent parser. Note the exploding amount of ugliness. Give up. * Separate out the tokenizer (novel idea, huh?) to keep parser complexity down. Parser is still a mess. Ugh! * Play around with some CL parser frameworks. This helps a bit, but none of the systems I tried produce errors with enough information. * Remember the breeze it was to write a parser with the Haskell Parsec library. Mess around with monads for a while, learn a few things, but not how to write elegant parsers in Common Lisp. I've been going through these exact steps but in JavaScript. Writing languages is fun! And makes me want to kill things!

spacemanaki 13y ago
I have no idea what you're working on, but I spent a few weeks this summer writing parsers and trying to figure out how to tackle the ugliness that seems to be inherent in hand-written recursive descent parsers. While I learned a lot, I am not an expert by a long shot. However I did find an interesting technique that is not well covered elsewhere. I came across this* article, which uses JavaScript as the implementation language, and found it very interesting, in large part because this approach (Top down operator precedence) sort of pulls the precedence hierarchy out of the call graph of a recursive descent parser and into a table, but also because it's an approach that OOP (and JavaScript in particular) is well suited to. I've used it (in combination with traditional recursive descent) in a functional setting (Standard ML) as well, and would use it again, especially for parsing infix expressions (arithmetic expressions, type annotation expressions). This is a bit of a tangent, but I thought you might be interested given the intersection of parsing and JavaScript. I've been meaning to write this up in a short blog post... * http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html There's another article on this using Java as the implementation language: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
- anaphor 13y ago
  I like the precedence climbing algorithm since you can easily fit it into a normal recursive descent parser and it allows you to easily add new operators just by putting them in a table. See: http://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/ http://eli.thegreenplace.net/2012/08/02/parsing-expressions-...
- quarterto 13y ago
  The parser is a bastard mix of recursive descent and parser combinators borne out of looking at the Dragon Book and thinking "fuck me, 2000 pages? I'm sure I can remember some CS325...". The language will eventually have macros I'll use for the built-in operators. I guess it's a Lisp? The syntax is sweet-expressions, so infixes are {l op b} which is just (op a b).
anaphor 13y ago
Tried this? http://tinlizzie.org/ometa/ http://tinlizzie.org/ometa/
saidajigumi 13y ago
If your needs fall towards JS as the target vs. the source language, then it's worth having a look at Fay[1] and GHCJS[2]. Both allow calls from regular Javascript, but Fay currently has a much better interface for that vs. GHCJS' still very low-level support. [1] https://github.com/faylang/fay/wiki https://github.com/faylang/fay/wiki [2] https://github.com/ghcjs/ghcjs https://github.com/ghcjs/ghcjs

spacemanaki 13y ago

I have no idea what you're working on, but I spent a few weeks this summer writing parsers and trying to figure out how to tackle the ugliness that seems to be inherent in hand-written recursive descent parsers. While I learned a lot, I am not an expert by a long shot. However I did find an interesting technique that is not well covered elsewhere. I came across this* article, which uses JavaScript as the implementation language, and found it very interesting, in large part because this approach (Top down operator precedence) sort of pulls the precedence hierarchy out of the call graph of a recursive descent parser and into a table, but also because it's an approach that OOP (and JavaScript in particular) is well suited to. I've used it (in combination with traditional recursive descent) in a functional setting (Standard ML) as well, and would use it again, especially for parsing infix expressions (arithmetic expressions, type annotation expressions). This is a bit of a tangent, but I thought you might be interested given the intersection of parsing and JavaScript. I've been meaning to write this up in a short blog post... * http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html There's another article on this using Java as the implementation language: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...

anaphor 13y ago
I like the precedence climbing algorithm since you can easily fit it into a normal recursive descent parser and it allows you to easily add new operators just by putting them in a table. See: http://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/ http://eli.thegreenplace.net/2012/08/02/parsing-expressions-...
quarterto 13y ago
The parser is a bastard mix of recursive descent and parser combinators borne out of looking at the Dragon Book and thinking "fuck me, 2000 pages? I'm sure I can remember some CS325...". The language will eventually have macros I'll use for the built-in operators. I guess it's a Lisp? The syntax is sweet-expressions, so infixes are {l op b} which is just (op a b).

anaphor 13y ago

Tried this? http://tinlizzie.org/ometa/ http://tinlizzie.org/ometa/

saidajigumi 13y ago

If your needs fall towards JS as the target vs. the source language, then it's worth having a look at Fay[1] and GHCJS[2]. Both allow calls from regular Javascript, but Fay currently has a much better interface for that vs. GHCJS' still very low-level support. [1] https://github.com/faylang/fay/wiki https://github.com/faylang/fay/wiki [2] https://github.com/ghcjs/ghcjs https://github.com/ghcjs/ghcjs