3 ms·
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
by 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 agoIs 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 agoIs the code online? What was the output of your routine?
- zzzcpan 8y agoTo 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. ), )