paultag/hy — pull request #34 by mattfenwick (2013-01-25 14:15:26+00:00)
Title: Parser:  grammar, top-level parsing, terminology

Hi Paul, enjoyed the talk last night! (I was the nerd in the back asking about semantics!)

I've made a couple of changes:

1. BNF-like grammars are great for succinctly and accurately describing syntax, so I attempted to derive one from your parser. I wasn't sure about a few of the rules, and some of them I know I got wrong. If you could clarify those points for me, I'd be happy to fix it up. Also, I've split the grammar into two parts.*

2. I've added a test case showing that the parser doesn't accept lone strings (same for symbols, lists, maps, etc.). If this is by design, please feel free to ignore this commit! If not, I have a few suggestions for how to change it.

*I also had a couple of nitpicks about terminology. I'm certainly not a Lisp expert so I may be wrong about these, but typically, I've seen these words used differently:

- lexer. As I understand them, lexers are only responsible for breaking the input into tokens, not for assembling them into a parse tree. Thus, tokenizing `(+ 1 2 (+ 3 4)` would not be an error, since all the tokens are valid. Although I split the grammar into lexical and ... whatever the word is for non-lexical ... rules, that was arbitrary and not absolutely necessary (but is commonly done). I'd suggest just calling it a parser instead.
- expression. It looks like what you're calling expressions would usually be called applications; whereas numbers, symbols, constants, lambdas, lists, maps, and applications would all be considered expressions.

Please let me know if you need me to clean up or improve these changes in any way. Thanks!