From a9292a98cc6c65e2a4ad6da20937ef7568a4143d Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Mon, 11 Mar 2024 16:33:24 -0700 Subject: earlpy --- DESIGN.txt | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) (limited to 'DESIGN.txt') diff --git a/DESIGN.txt b/DESIGN.txt index 0762ca6..0fafff0 100644 --- a/DESIGN.txt +++ b/DESIGN.txt @@ -1,3 +1,60 @@ +====== Performance Issues ======== +The biggest performance issues involve parsing grammar + + LIST nonterm + LIST , EXPR + EXPR + +With a huge input of + + A , A , A , A , ... + +Naively, the parser will try to match an EXPR starting at each of the As. + +I guess this is because even if you are associating so far like + + (((A, A), A), A), ... + +It doesn't know if, later on in the parse, you might want to reassociate 'across +the boundary': + + (((A, A), A), (A, B)), ... + +At this point, I don't think it's worth trying to do much more general-purpose +optimization for this case. Instead, I think we should have callouts to user +code to give hints. Two possible hint types: + + 1. "Parse this region as this parse tree." Easy to use: when you get there, + just skip all of those indices and complete that tree with any watchers. + (Might need to do prediction at the first index.) + +Actually, that's probably by far the easiest. + +====== More Disambiguation Issues ======== +What if we poison X, use it in completion Y, but then overwrite X with a +nonpoisoned Z? Then Y will be incorrectly poisoned... + +====== More Disambiguation Issues ======== +Consider + + STMTS nonterm .start + STMTS STMT + STMT + +vs. + + STMTS nonterm .start + STMT + STMTS STMT + +Swapping this can actually impact what matches happen in STMT :O + +====== More Disambiguation Issues ======== +Associativity and precedence can have weird interplay + +E.g., maybe you can get Stmts(Error(1), Stmt(2, 3)) which has better +associativity than Stmts(Stmt(1, 2), Stmt(3)) + ====== Disambiguation Issues ======== Consider two possible parses of 0 + 1 * 5 + 4 ( ( 0 + ( 1 * 5 ) ) + 4 ) -- cgit v1.2.3