TODO

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