add Serializable to util classes
[sbp.git] / TODO
1 _____________________________________________________________________________
2 Immediately
3
4   - clean up util package
5
6   - serializable parse tables?
7      - all that is required now is to separate Pos and Position
8
9   - currently we GC the doomed stack when the parent dies... but we
10     should also GC the parent when the doomed stack dies if it was a
11     positive conjunct.
12
13   - single-tree-return assumption
14      - have a way to let question marks not be tagged?
15      - "flat" sequences (no subtrees contain "::"s?) -- stringifiable
16      - make it so that we can have multi-result nonterminals
17        so long as they always appear under double-colons?
18        auto-insert the unwrap?
19
20   - get rid of Sequence.Singleton if possible
21
22   - use 'a'-'z' or 'a-z' instead of [a-z]?
23   - de-genericize?
24   - foo.add(x)
25     foo.add(y.andnot(x)) ==> this is broken
26       - distinguish Conjunct from Sequence?
27             => !(Conjunct instanceof Reducible)
28   - avoid building the parts of the tree that end up getting dropped
29       - is it worth adding an additional class of states for these?
30          - or perhaps just a runtime node marker (hasNonDroppedParent)
31       - "ambiguity modulo dropped fragments"?
32          - this may conceal highly inefficient grammars...
33   - double-check all the region logic
34   - automatically collect time statistics and display
35
36 ______________________________________________________________________________
37 v1.1
38
39   - MUST HAVE BETTER ERROR MESSAGES
40      - use for developing java15.g
41      - better ambiguity reporting
42         - colorized tree-diffs?
43         - graphviz?
44      - better toString() methods all around...
45
46   - Treewalker code compiler?
47   - detect and reject circular gramars
48   - skeleton generator?
49   - precedes restrictions ("<-")
50   - More topology untangling [later]
51   - grammar highlighting?
52   - Forest needs a "manual access" API (lifting makes this hard)
53   - rewriting language? multiple passes?
54   - write some grammars
55       - Java grammar (java15.g)
56       - TeX (math?)
57       - RFC2822 (email message/headers)
58       - Wikipedia grammar (needs to be both lexerless and boolean)
59
60
61 ______________________________________________________________________________
62 Features
63
64   - try harder to "fuse" states together along two dimensions:
65      - identical (equivalent) states, or states that subsume each other
66      - unnecessary intermediate states ("short cut" GLR)
67
68   - substring parsing 
69       - better error messages
70       - Rekers & Koorn note that this can do really elegant and generalized "autocompletion".
71   - Parameterized LR
72   - "Regular Right Part" grammars (NP Chapman, etc)
73   - Attribute unification
74       - Partly-Linear-PATR? (O(n^6) unification grammar)
75
76   - optional "prefer whitespace higher up" disambiguation heuristic
77
78   - Incremental parse table construction
79
80   - "lazy GLR" and "lazy trees" -> language with first-class CF matching
81       - perhaps linear boolean grammars instead? (linear time, quad space)
82
83   - Followed-by and not-followed-by predicates of arbitrary length
84       - expands the grammar beyond Boolean LR...
85       - requires *very* smart garbage collection
86
87 ______________________________________________________________________________
88 Optimizations
89
90   - understand and implement the RNGLR "kernel state" optimization.
91     The _Practical Early Parsing_ paper may help.
92
93   - implement Johnstone's algorithm for "reduced, resolved LR
94     tables" to eliminate superfluous reductions on
95     epsilon-transitions.
96
97   - Implement a k-token peek buffer (for each state, see if it "dead
98     ends" during the next k Phases based solely on state -- ignoring
99     result SPPF)
100
101   - Is there any way we can avoid creating a GSS.Node instance for
102     nodes which are transient in the sense that they have only one
103     eligible reduction?
104
105   - Re-read Rekers, particularly the stuff on optimal sharing
106
107   - bring back in parse-table phase resolution of precedence (just
108     like associativity).  This can be inferred from the use of ">"
109     when the rules are in one of these special forms:
110
111        E ::=  E     _
112            >  _     E
113
114        E ::=  _     E
115            >  E  _  E
116
117        E ::=  E  _  E
118            >  E  _  E
119
120     where "_" is anything and "E" is the defining nonterminal.
121     Essentially what we're looking for is the situation where the
122     leftmost portion of one rule produces another rule, and the
123     rightmost portion of the latter produces the former.
124
125     I'm not 100% certain that this is as "strong" as the prefer/avoid
126     form (try to prove this, you probably can), but it's "what people
127     intend" most of the time.
128