Show HN: How to write a tiny compiler

Re:Show HN: How to write a tiny compiler by devwastaken on Thursday February 09, 2017 @11:33PM (#13613246)

Unrelated, but how would one get started creating a proper parser for textual content? For example, I have

  {
   "key"
   {
    "key" "value"
    "morekeys"
     {
     "key2" "value2"
     }
    }
   }

The markup would be seperated by newlines, with the key-value pairs on the same line, always in quotes. I've solved it with regex and a crude parser before, but I've always heard of things like Bison and such but never found a 'good' way to impliment a real parser in a language like Python.

[ Parent | on HN ]

Re:Show HN: How to write a tiny compiler by akkartik on Thursday February 09, 2017 @11:51PM (#13613309)

To elaborate on userbinator's comment, you want to think of your format as a set of definitions:

A clause consists of a '{', one or more key-value pairs, and a '}'.

A key-value pair consists of a string and a value.

A value is either a string or a clause.

Now turn each definition into a function.

Here's a nice-looking article from Googling for "writing a recursive descent parser": http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recur...

[ Parent | on HN ]

Re:Show HN: How to write a tiny compiler by userbinator on Thursday February 09, 2017 @11:37PM (#13613258)

I would go with a simple recursive descent parser, unless you are interested in learning a DSL, the intricacies of the parsing algorithm your particular parser generator uses, and willing to debug one --- IMHO not worth it. Even "real", production-quality compilers like GCC, Clang, MSVC, and ICC use recursive-descent; and some, like GCC, switched away from parser generators.

[ Parent | on HN ]

Re:Show HN: How to write a tiny compiler by david-given on Friday February 10, 2017 @09:36AM (#13615612)

Parser generators work really well for context-free grammars, but as soon as you start needing context-sensitive lexing (like C does) you enter World Of Pain time. And they avoid having to deal with lookahead, which is always messy in hand-written parsers.

But I think I'd agree that writing a recursive descent parser from scratch is probably the best way to learn about parsing; at least for a simple grammar.

BTW, fun fact: it turns out that BNF was invented by an Indian linguist called Pāṇini about 2500 years ago, in order to parse Sanskrit.

https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini

[ Parent | on HN ]