alecthomas / alecthomas/participle

Generating parser code

Offen
#213 26 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
Vorherrschende Sprache
Go
Sterne
3.9k
Forks
213
PR-Merge-Kennzahlen
Keine gemergten PRs in 30 T.

Beschreibung

Hi there again @alecthomas,

I'm already using this great parser in a large project (a GoLang implementation of Jinja, will be open sourced eventually) and one of the things that somewhat bothers me is the speed and GC pressure (allocations) of the parser. I've considered using the generated lexer to improve it, but it's just not enough. So what if this library could also generate code for the parser? Is this something you've already considered or even started playing with?

I actually already did and have a very ugly prototype that can generate the parser code for this subset of features:
* string and struct fields only
* supported nodes (at least mostly) are `strct`, `sequence`, token `reference`, token `literal`, `capture` (`@`) and `group` (`?`, `*`, `+`, not `!` yet)
* totally trash error reporting
* max lookahead, case insensitive tokens and probably other options are not respected yet

Example grammar it can parse consistently with the native parser (except for error messages):
```
type Stuff struct {
Pos lexer.Position
A string `'test' @Ident @Ident`
Sub SubStuff `@@+`
B string `@Ident`
EndPos lexer.Position
}

type SubStuff struct {
Object string `'(' @Ident 'is'`
Adjective string ` @Ident ')'`
}

// Uses lexer.TextScannerLexer
```

For this grammar and with a pre-built `PeekingLexer` (so that I compare only parsing speed), here are the benchmarks at this moment:
```
Input string, pre-lexed: "test str ing (this is fast) (this is fast) (this is fast) (this is fast) (this is LAST) end"
BenchmarkNative
BenchmarkNative-8 282736 18882 ns/op 11536 B/op 207 allocs/op
BenchmarkGenerated
BenchmarkGenerated-8 10671034 576.2 ns/op 8 B/op 1 allocs/op
```

The reason for being >30x faster for this particular grammar (likely a very cherry-picked example) is that the generated code:
* avoids allocations as much as humanly possible, in fact the only allocation it does in that example is when concatenating strings for `Stuff.A`
* doesn't use Reflect, obviously - the huge benefit of generated code
* avoids unnecessarily small functions - it generates 1 function per struct + 1 wrapper, uses `goto` (responsibly) to solve things that would otherwise need calling a function or duplicating code
* also uses some optimizations that could be applied to the native parser (for example: allocation-free PeekingLexer.Clone alternative, avoiding string concatenation when capturing values, etc.)

It's very possible I'll run into an issue I won't be able to overcome, but for now it seems like this should be very doable. The generated code isn't too long (160 LOC for the above grammar), is quite well isolated (adds one generic method to all `node`s, plus a file for code generation utilities) and doesn't introduce any new dependencies. For now I would just like to let you know I'm working on this, so we can coordinate any similar efforts. :) I would also appreciate your support with a few questions (will post them in this issue later).

What do you think? Cheers!

Beitragsleitfaden

Für dieses Repository ist kein Beitragsleitfaden indexiert

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.