TODO

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