3 ms·

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

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.

userbinator 10y ago
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.
- david-given 10y ago
  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 https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini
akkartik 10y ago
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-recursive-descent-parser.html http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recur...

userbinator 10y ago

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.

david-given 10y ago
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 https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini

akkartik 10y ago

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-recursive-descent-parser.html http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recur...