Peter Blackson

Info on the fastest Earley impl

16

I made an Earley engine that is much faster in benchmarks than YAEP: [gearley](https://github.com/pczarn/gearley). Here are the results for 88248 tokens (10K lines of C). ``` gearley: bench_parse_c ... bench:...

- [ ] Independently sort RHS1 and LHS grammar columns - [x] Parameterize grammar representation by symbol type (u8, u16, u32) - [ ] Consider removing the LHS0 column, which...

Choose better sorting and priority queue algorithms

2

- [ ] Gather statistics about the order of item arrays to better choose algorithms. - [x] Implement an unstable, O(n log n) time, constant space sorting algorithm that work...

Creation of medial items has only two causes. - completed item advances a predicted item - scanned token advances a predicted item As far as can I see, item completions...

The Earley table can be scanned and reduced by removing items that are too old to be useful. Better do this every now and then for recent Earley sets, and...

LLVM has a Profile-Guided Optimization project. I'm curious how that would affect produced assembly code.

Parse right-recursive rules in linear time

1

Rewrite right-recursive rules into left-recursive ones. Rotate the parse forest to undo that rewrite. It remains to be seen if all right-recursive rules can be rewritten in a simple way....

Allow extending the bocage with a custom node type

1

Downstream libraries, most importantly Panini, should be able to declare their own node types. It is yet unclear whether this will help reduce memory use. Looking to the other side...

The Sum variant of Node holds a `summands` slice, which contains Nodes. It is certain that these Nodes can only come from two constructors -- Product or ShallowProduct -- and...

Fuzz the parser with afl

1

I didn't take a good look, but fuzzing pointed out one minor mistake. I'll try to fuzz more. I expect using a serialized grammar format will be best. Perhaps the...