3 ms·

How do you write a parser in a language like Go? I stumbled upon parser combinatory and tried to shoehorn them into Go, but the lack of generics mostly prohibit

How do you write a parser in a language like Go? I stumbled upon parser combinatory and tried to shoehorn them into Go, but the lack of generics mostly prohibited this. I also tried imperatively writing the parser, but this was tedious and error prone. I also explored parser generators, but these seemed to have huge learning curves and still produced awful code. Beyond that, it’s hard to tell what kind of parser I need because of all of the academic jargon. :/ I would love to be pointed in the right direction!

laumars 8y ago
The lack of generics wasn't an issue for me. A 30 second overview: The first thing you need to do is scan your file for tokens (eg "{", "}", "[", "]", ",", "\"", etc in the case of JSON). Then you traverse your tokens and turn them into an AST (Abstract Syntax Tree) which is essentially just a "struct" version of the code (in the dumbest description imaginable). The point of this is you start adding definitions to your tokens. Eg what does a "[" mean? From there you can start writing your real business logic since you now have a Go struct version of your code which you can traverse. However I would really would recommend doing a google for how to write your own compiler. There are dozens of good resources out there (I can't recall the one that I used off hand) and they'll explain this process a thousand times better than I have above. One last thing to note, the theory of writing a parser is pretty language agnostic so don't get put off that one guide is in C or another in Java or Python or LISP or whatever. As long as you get the theory nailed you can write the Go code equivalent without too much headache.
slentprog 8y ago
I can recommend the book writing an interpreter in Go. It requires some basic knowledge of the Go programming language to get started.
zzzcpan 8y ago
Parser combinators don't need generics, as they are merely higher-order recursive descent parsers. I.e. recursive parsers where functions are created via other functions to generalize and compose them. Go is expressive enough to do that. For example, let's say we start with a function that parses a character '['. buf, pos := []byte("[123]"), 0 LBRACK := func()bool { if buf[pos] != '[' { return false } pos ++ // consume character return true } It would suck to write such function for every single character we have to parse. We can generate it instead: CHAR := func(c byte)func()bool { return func()bool { if buf[pos] != c { return false } pos ++ return true } } LBRACK := CHAR('[') Now let's do the same for parsing a sequence. We combine outputs of other functions and return one that parses them one by one. SEQ := func (args... func()bool) func()bool { return func()bool { for i := 0; i < len(args); i++ { f := args[i] if f() == false { return false } } return true } } parser := SEQ( CHAR('['), SEQ( CHAR('1'), CHAR('2'), CHAR('3'), ), CHAR(']'), ) This is the idea. This is not a real world example though. You'll need to have more primitives, a wrapper that handles various things, like restoring buffer index on failure, captures, that save starting index, move buf/pos into context structure, virtual stack to store captures/errors, etc. func SEQ (args... func(ctx *Ctx)bool) func(ctx *Ctx)bool { return wrap (func(ctx *Ctx)bool { ... }) } But it's important to get there on your own. And it's pretty much as fast and as flexible as completely hand-written recursive descent parsers and as powerful as parser generators.
- deleted 8y ago
  [deleted]
- weberc2 8y ago
  Is that a parser? That looks like a matcher. I actually built something that looks almost exactly like this, but it doesn't get you an AST, right? What am I missing?
  - laumars 8y ago
    Is the code online? What was the output of your routine?
  - zzzcpan 8y ago
    To get to AST you have to create AST nodes. Make a function that captures the output and put it into places where you want to create AST nodes. Sort of like this: SEQ( ... CAPTURE( // parser to capture SEQ(...), // extra arguments: // a name, a function to call, // that creates an AST node, etc. ), )

laumars 8y ago

The lack of generics wasn't an issue for me. A 30 second overview: The first thing you need to do is scan your file for tokens (eg "{", "}", "[", "]", ",", "\"", etc in the case of JSON). Then you traverse your tokens and turn them into an AST (Abstract Syntax Tree) which is essentially just a "struct" version of the code (in the dumbest description imaginable). The point of this is you start adding definitions to your tokens. Eg what does a "[" mean? From there you can start writing your real business logic since you now have a Go struct version of your code which you can traverse. However I would really would recommend doing a google for how to write your own compiler. There are dozens of good resources out there (I can't recall the one that I used off hand) and they'll explain this process a thousand times better than I have above. One last thing to note, the theory of writing a parser is pretty language agnostic so don't get put off that one guide is in C or another in Java or Python or LISP or whatever. As long as you get the theory nailed you can write the Go code equivalent without too much headache.

slentprog 8y ago

I can recommend the book writing an interpreter in Go. It requires some basic knowledge of the Go programming language to get started.

zzzcpan 8y ago

Parser combinators don't need generics, as they are merely higher-order recursive descent parsers. I.e. recursive parsers where functions are created via other functions to generalize and compose them. Go is expressive enough to do that. For example, let's say we start with a function that parses a character '['. buf, pos := []byte("[123]"), 0 LBRACK := func()bool { if buf[pos] != '[' { return false } pos ++ // consume character return true } It would suck to write such function for every single character we have to parse. We can generate it instead: CHAR := func(c byte)func()bool { return func()bool { if buf[pos] != c { return false } pos ++ return true } } LBRACK := CHAR('[') Now let's do the same for parsing a sequence. We combine outputs of other functions and return one that parses them one by one. SEQ := func (args... func()bool) func()bool { return func()bool { for i := 0; i < len(args); i++ { f := args[i] if f() == false { return false } } return true } } parser := SEQ( CHAR('['), SEQ( CHAR('1'), CHAR('2'), CHAR('3'), ), CHAR(']'), ) This is the idea. This is not a real world example though. You'll need to have more primitives, a wrapper that handles various things, like restoring buffer index on failure, captures, that save starting index, move buf/pos into context structure, virtual stack to store captures/errors, etc. func SEQ (args... func(ctx *Ctx)bool) func(ctx *Ctx)bool { return wrap (func(ctx *Ctx)bool { ... }) } But it's important to get there on your own. And it's pretty much as fast and as flexible as completely hand-written recursive descent parsers and as powerful as parser generators.

deleted 8y ago
[deleted]
weberc2 8y ago
Is that a parser? That looks like a matcher. I actually built something that looks almost exactly like this, but it doesn't get you an AST, right? What am I missing?
- laumars 8y ago
  Is the code online? What was the output of your routine?
- zzzcpan 8y ago
  To get to AST you have to create AST nodes. Make a function that captures the output and put it into places where you want to create AST nodes. Sort of like this: SEQ( ... CAPTURE( // parser to capture SEQ(...), // extra arguments: // a name, a function to call, // that creates an AST node, etc. ), )