* Implement a Precedence Climbing Expression Parser based on the description
  in http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm.

	* Add SwitchParser that dispatches to subparsers based on one char
	  of lookahead. Can be used to speed up lexers implemented as
	  one big choice over many subparsers. This is only a short-term
	  solution since these kinds of speed-ups should be handled by
	  factoring the parsers. Speeded up the utest_lexer tests in
	  example/ruby from 6.6 seconds to x.y.

	* Sync with RDG Basic files described in Syngress book.
	


* set_separator should not add separator_parser if it has already been added
  to the first sub_parser.

------------------------------------------------------------------------------
ToDo
------------------------------------------------------------------------------
PHASE I
*******

* Generate "better" lexers
  * Introduce states  la SableCC? Or should it be possible to return a token
    with multiple labels (for example the token for Identifier may match
    the same thing as a string token for a keyword; instead of returning two
    tokens we can return one token with multiple names/labels)? The latter
    would be better if it suffices; it wouldn't complicate matters when
    writing grammars.

* Parser generation todo
  * # as child name expanded to :lexeme
  * Specifying tokens using in production-style with lexical elements:

      QString         -> /'((\\')|[^'])*'/
                      |  '%' delimited_string        [: _,#]

    Elements can be (1) strings, (2) regexps, (3) name of tokenizer. The
    latter is a ruby method defined in the Tokenizers section. It will be
    inserted into the lexer and called to tokenize. It can access the
    attributes string (full string being tokenized), cursor (position of
    the next char to be considered) and string_length (length of the string
    being tokenized). It return the name of the token found (as a symbol),
    the start and end positions of the lexeme and the position of the next
    char to be considered.

    Tokens can have AstSpecs specifying which parts of the matched string
    should be the lexeme. Following symbols can be used:

       # means "the string matched by the lexical element at this position
                should be the lexeme" (only one per AstSpec)
       + means "add string matched by the lexical element at this position
                to the lexeme" (one or several per AstSpec)
       _ means "do NOT include in lexeme"

    Examples:

       A -> '1' /\w+/  [: _, #] 
         matched against "1saffds" will return A:[saffds]

       B -> '1' 'arm' /\w+/  [: +,_,+] 
         matched against "1armsaffds" will return B:[1saffds]
  
  * new_name = m[index].child_name can be used in AstSpec to specify that
    the value of the child named 'child_name' on the element at position
    'index' should be given the name 'new_name'. The "new_name =" part is 
    optional. If not given it must be the only child reference in the AstSpec
    since it will be returned when the production match.

  * Take away the difference between Tokens and Productions for the user.
    The funcs used to write grammars should be smart enough to see if they
    can be implemented as Tokens. If not they must be Productions. It can
    only be a token if all elements are either strings or regexps or can
    be derived from a lhs that is a Token. The operator elements can be used
    both on NonTerminal elements and on Token/Terminal elements. If they are
    used on the rhs of a token def they are expanded to regexp form. If not
    they are expanded as productions. If we do this we cant use [] for 
    specifying options to Tokens (since its confusing cause Productions use 
    them for AST spec). Instead we can use ':' as in

	WhiteSpace -> /\s+/                          :skip:
        Exp -> Exp '+' Exp     [Plus: left, _, left] :left:

    This would give interesting flexibility in that the parser gen can choose
    somewhat what should be tokens and what should be Productions. (My guess
    is of course that its always better to do something as a token if it
    can be done as a token but it would be nice to be proven wrong ;-))

  * Creating stand-alone parsers. Generated file should include all source 
    code needed.

  Grammar:
   * Clean up Element/GrammarSymbol hierarchy and move Token into it.
	Element > [OperatorElement > [PlusE, MultE, ListE, MaybeE, OrE], 
	           GrammarSymbol > [Token, NonTerminal]]
   * GrammarSymbols should be Indexable and created by IndexableFactories
   * prod should make use of an IndexableFactory when creating grammar symbols
   * inspect should include priorities and tree_builders
   * inspect of Production and Grammar are sometimes ugly
   * Grammars should be mergeable/importable. Be able to spec what is imported
     and under what name?

  RockitGrammarSemanticsChecker
  * class for checking that a syntactically correct rockit grammar is 
    semantically correct, for example:
     * All nonterminals and tokens used must be defined somewhere

  GraphDrawing
   * Not longer needed since we have graphviz_dot.rb. Move GlrParser-specific
     stuff to GlrParser and delete this file. 

  LaLrGen
   * Shouldn't include skip tokens when building tables.

  Token:
   * Unify the func of StringToken and RegexpToken into Token. 
     No need to treat them specially. 
     Make sure everyone uses Token when creating implicitly defined tokens. 

  Tests/Checks:
   * More tests of nested operator elements. Its buggy!

  All:
   * Enclose in module Parse

  GlrParser:
   * Add substring extraction to AmbigousParseException so that only the 
     substring where the ambiguity arises is shown.
   * Simplify by using DirectedGraph for the ParseStack?

Phase II. Better error detection, recovery and reporting.

Phase III. Performance. See ideas below.

Phase IV. More example grammars
  * Example grammars in subdir examples
    * Prio medium: examples/yacc-translator
      Translates yacc grammar files to rockit ditto. Build on the ruby parse.y
      to rockit translator.

    * Prio low: examples/ansic-parser
      CLanguage::AnsiCParser - A parser for ANSI C.

------------------------------------------------------------------------------
Size of the generated parse tables
------------------------------------------------------------------------------
* Compact table by defining commonly used large integers (representing
  Terminal sets) as variables and using the vars in the action table.

------------------------------------------------------------------------------
Performance (in order of decreasing perceived potential effect on performance)
------------------------------------------------------------------------------
Parser + Lexer
* Parser-directed token filtering. Assign one bit to each token in the grammar. Represent the valid follow set at each parse stack and send it to the lexer. The lexer will only try out the skip tokens (which can always appear) and the tokens that might follow. This makes for faster lexing and parsing. Drawback is that the follow sets must be saved in the parse table but since they are simply Integers it might not be that big a problem. Maybe add this as an option? Add it by subclassing the existing Lexer, Parser and Generator classes?

GlrParser:
* Implement Alonsos O(n^3) generalized LR parsing algorithm which uses
  dynamic programming instead of a graph-structured stack. It acheives
  linear complexity for LR grammars.
	@inproceedings{ alonso97construction,
    author = "Alonso and Cabrero and Vilares",
    title = "Construction of Efficient Generalized {LR} Parsers",
    booktitle = "{WIA}: International Workshop on Implementing Automata, {LNCS}",
    publisher = "Springer-Verlag",
    year = "1997",
    url = "citeseer.nj.nec.com/44290.html"
	}
    http://www.dc.fi.udc.es/~alonso/papers.html

* Lazy tree creation. Lessen the overhead from the GLR parsing algorithm by
  not creating the trees until the parse is finished. Insert tree creation 
  nodes at the links and collect them into tree structures. The call
  create or build to actually build the tree. But first see if tree creation
  is a major speed problem.

* Check out: J. Aycock and N. Horspool. Faster Generalized LR Parsing. In S. Jahnichen, editor, Proceedings of the eight International Conference on Compiler Construction, volume 1575 of LNCS, pages 32--46. Springer-Verlag, 1999. 

GlrParser:
* Might be a good idea not to check for conflicts all the time but only when
  a real conflict (ambiguity) is found. But it might not be good since we 
  delay the pruning of unneeded paths. Needs to be evaluated in practice.
* Compact unused nodes directly?
* Check out why we find multiple ways to reduce to the
  same trees but that there is no ambiguity since they are the same. This is
  a potential cause of bad performance? Find out how often this happens...

Lexer:
* No need to count newlines and columns in the Lexer with LexerPosition. At least not from an error reporting perspective since we can easily extract this info if we have the char position.

Grammar:
* Memoize normalize on OperatorElement's since they will be the same each time
  once they've been calculated. Probably not important though...

LaLr1ParserGenerator:
* Speed up @grammar.productions.index and @grammar.tokens.index idioms
  by using hash (Memoize).

------------------------------------------------------------------------------
Error recovery and reporting
------------------------------------------------------------------------------
* General problem is that there is no recovery at all! Rockit will fail
  when there is a syntax error. There are many ways to introduce error
  recovery but I'm not yet sure what is "the right way". Any ideas welcome!

* SableCC idea: Syntax error recovery by inserting (error) tokens until the invalid token becomes invalid. This is done on the assumption that it is more common for a user to forget a token than adding erroneous ones.
  Example: 
    "a = 3 + 5 b + 3;"
    where it is assumed the user has forgot an operator so parsed as
    "a = 3 + 5 [OP] b + 3;"

* Check tokens at PTGen time to make sure none of them matches the empty 
  string. If some does it will match at every time...

* Might be good to check out Rekers thesis on subtring recognition and parsing. These techniques can be used for noncorrecting syntax error recovery (answering: Is the rest of the string a legal substring of the language?) and for generating trees for the possible contextual completions of a substring of the language. If we couple this with some fuzzy/pattern-matching technique that adapts to the errors each person frequently do we should get a very powerful error analysis system. General design is that substring recognition/parsing generates the possible correct sentences and the adaptive algorithm chooses the most likely ones based on your previous errors.

------------------------------------------------------------------------------
Ideas / Maybe some day...
------------------------------------------------------------------------------
Node and child naming when nested operators:
* Embed a full AstSpec after the child name in the ElemSpecs.
  Example:
   Currently:

     Grammar -> 
       'Grammar' LanguageName Tokens? Productions Priorities?
       [Grammar: _, language, tokens, productions, priorities]
     Tokens      -> 'Tokens' TokenSpec+                [^: _,tokens]
     Priorities -> 'Priorities' Priority+              [^: _, priorities]

   would become:

     Grammar -> 
       'Grammar' LanguageName 
         ('Tokens' TokenSpec+)? Productions ('Priorities' Priority+)?
       [Grammar: _, language, 
                 tokens[^: _,tokens], productions, 
                 priorities[^: _, priorities]]

Operators:
* Add SequenceOperator that groups elements.

Grammar:
* Change name from Grammar/GrammarModule to LanguageModule or Language? May
  be better description since it not only includes a (context-free) grammar
  but also lexical spec, ast spec and priorities etc.

Lexer:
* The ultimate in lexing is that when you spec

    Blank   = /\s+/
    Newline = /\n/
    Id      = /\w+/

  and have the string " \t\na" you should get the lexer streams
     [[Id:[a]], [Newline, Id:[a]]]

  Right now you'll only get 
      
     [Id:[a]]

  since Blank will eat as much as possible and Newline does not match 
  the beginning of the string.

  One simple way to get the ultimate behavior above is to make some analysis
  beforehand on what tokens may overlap in this way and then handles it.
  One way would be by matching Newline to the match of Blank and then rematch
  Blank to the stuff preceding the previous match up to but not including
  the newline. But the cleanest way is probably to make some kind of DFA out 
  of this mess.

Misc:
* Subclass SyntaxTree for each AST node specified by the user. This would make the separation clearer when writing evaluators. The programmer simply writes an eval method on the corresponding node. Also see MAtju's MetaTypes approach in RubyAST.

* Being able to restrict a parser to a subgrammar R' of the grammar R it was generated for. Jan Rekers introduces a technique for this in his thesis and we can probably adapt his techniques to our context. 

* Lifting and evaluating terminals in the AST spec. Right now one can only
  lift productions. It would also be nice to be able to lift terminals. This
  will lift the lexeme value out of the Terminal. One could also specify that
  the lexeme should be eval'ed when lifted. Proposed syntax
        MyProduction -> num '-' num    [Sub: ^e, nil, ^e]
                     |  num            [Num: ^]

  where '^' is used to mark simple lifting of the lexeme and '^e' for lifting
  and evaluating.

* epsilon productions!? Are they needed?

* Define a tree walking grammar  la Sorcerer in ANTLR.

* Specify that a child2 should always be accessed as an ArrayNode with

    nt -> alpha ',' gamma      [Node: child1, _, child2[]]
    gamma -> numeric           [^]
          |  $seq(string, ',') [^]

  The numeric is converted into ArrayNode when Node is created. Easy to 
  implement.

* Token priorities. Use the existing priority section and syntax to specify
  priorities between tokens. The priorities can be used to handle ambiguities
  arising because two tokens overlap, ie. match the same substring, when
  an ambiguity is found during parsing.

* Look into the possibility of adapting techniques for hard-coding LR parsers for speed to generalized parsing  la Rockit. There is the paper "Very Fast YACC-Compatible Parsers (For Very Little Effort)" by Achyutram Bhamidipaty and Todd A. Proebsting in http://citeseer.nj.nec.com/53129.html.

* Check out what can be learned from fast scanner generators like GLA and RE2C which are said to produce faster lexers than handcoded ones. Can we adapt them to the Forking Scanner technique we use? There's a paper on RE2C in CiteSeer. There are lots of links on the page http://www.compilers.net/ScannerGens.htm. re2c is available from ftp://csg.uwaterloo.ca/pub/peter/re2c.0.5.tar.gz.

  re2c page at http://www.tildeslash.org/re2c/index.html

  a Python clone is mentioned: 
   http://mail.python.org/pipermail/python-dev/2000-July/005333.html

* Def of Attribute grammars: An attribute grammar is a description of the abstract syntax of a programming language, together with rules for decorating the abstract syntax tree with attributes.

* Back-ends:
	* MLRisc http://www.cs.nyu.edu/leunga/www/MLRISC/Doc/html/
	
* The way to go for retargettable compiler back-ends:
	Automatic retargeting of compilers:
           http://www.cs.arizona.edu/~collberg/Research/Publications/Collberg97b/
	Automatic architecture discovery system (AADS):

	Given a C compiler, an assembler, a linker and a way to execute
	commands on the machine having the other components the system
	deduces a machine description that can be used as the basis for
	generating a back-end etc.

	There are 5 parts of the AADS:
	 * Generator, generates small C code samples which is sent to
	   compiler which compiles to assembly language
	 * Lexer, extracts relevant instructions from assembly sample,
	 * Preprocessor, deduces the signatures of instructions and
	    build a data-flow graph,
	 * Extract, deduces the semantics of instructions and
	 * Synthesizer, produces a BEG-description of the architecture

* Collberg doing the AADS system above has lots of interesting stuff.
  Among other the ART system for program rendering (pretty-printing).
  They use the term rendering as "presented using combinations of text and
  graphics on a printed page". Also stuff for obfuscation.

* Very interesting survey of systems using rewriting:
Jan Heering and Paul Klint, Rewriting-Based Languages and Systems, to appear as Chapter 15 in the Terese Group's upcoming book Term Rewriting Systems, Cambridge University Press, 2002. 

 Study and check out the systems therein, especially:

   * BEG (Back-End Generator), http://www.first.gmd.de/beg/
	A bit dated (around 1990) but seems strong.
   * TXL (Transformation Language), http://www.qucis.queensu.ca/STLab/TXL/,
	Examples are grammars for C/C++, Java and XML (with well-formedness
        checking). "Source transformation by example". Also a company called
	Legasys but they do not seem to be up.
   * HOPS (Higher Order Programmin System), 
	http://ist.unibw-muenchen.de/kahl/HOPS/
   * CRL (Common Representation Language)
	http://www.science.uva.nl/pub/programming-research/software/muCRL/

* From Ooge de Moors talk to BCS:
   The above example demonstrates how forwarding is different from ordinary inheritance, because the specialisation can be achieved only dynamically, when we have a tree to manipulate. There have been other attempts to use object-orientation for structuring attribute grammars, notably by Aksit and Mernik. These attempts allow only static inheritance. The idea of forwarding is much closer to the higher-order attribute grammars of Teitelbaum, Swierstra and others. In a higher-order attribute grammar, attributes may be attributed trees themselves, and this is precisely what happens in our implementation of forwarding. Higher-order attribute grammars are an important feature of the Synthesiser Generator, a product of GrammaTech. Indeed, if you want to separate the wheat from the chaff in attribute grammars, restricting your attention to industrial products is a good start.

By comparison, little effort has gone into better ways of structuring attribute grammar descriptions. The efforts of Aksit and Mernik I mentioned before are rare exceptions, as is the work of Waite and Kastens. Like the other big innovation in attribute grammars (Johnsson's demand-driven evaluation), the idea of forwarding came from an outsider, one of the chief designers of intentional programming, Paul Kwiatkowski.

* Psyco compiler for Python: http://homepages.ulb.ac.be/~arigo/psyco/
	Very advanced and seems to give fast execution of Python.

* Reference Attribute Grammars by Grel Hedin
  Hennes RAG papper ger bra introduktion till AG's.

* Paper with slides on "Object-Oriented Compiler Construction"
    http://luna2.informatik.uni-osnabrueck.de/axel/talks/99/aizu.pdf
  Talks about EBNF as syntax graphs.
  Tree traversal with the visitor pattern.

* There are courses in OOCC:
	http://www.cs.uml.edu/~lechner/01s204/01s204syl.htm

* Books of interest:
	Modern Compiler Design, http://www.cs.vu.nl/~dick/MCD.html

* Generating optimal code in the back-end:
   Code Generation = A* + BURS (1996)
   Albert Nymeyer, Joost-Pieter Katoen, Ymte Westra, Henk Alblas
   http://citeseer.nj.nec.com/34447.html

* Machine Descriptions to Build Tools for Embedded Systems
  Ramsey et al
  http://citeseer.nj.nec.com/ramsey98machine.html 

* Building Program Optimizers with Rewriting Strategies 
  Eelco Visser, Zine-el-Abidine Benaissa, Andrew Tolmach 
  http://citeseer.nj.nec.com/visser98building.html

* PAGODE: a realistic back-end generator 
  http://citeseer.nj.nec.com/canalda95pagode.html

* One alternative to learning a back-end generator would be to skip all
  intermediate steps and try to compile Ruby directly onto the machine.
  Benefits would be that we don't need to learn some unfinished, undocumented
  or unsupported back-end generator but could roll our own. Furthermore
  we could write it in OO Ruby and have all the benefits of clear code
  etc.

* Other interesting papers/sites to check out:
	* Ooge De Moors home page with lots of interesting ideas and papers
          relating to intentional programming, program transformation,
	  aspect-oriented compilers etc:
	    http://web.comlab.ox.ac.uk/oucl/work/oege.demoor/
	* One-Pass, Optimal Tree Parsing - With Or Without Trees,
          Todd A. Proebsting and Benjamin R. Whaley, CC'96 April 1996. 
	* T. Rus and T. Halverson. A language independent scanner generator. Available at ftp://ftp.cs.uiowa.edu/pub/rus/scan3.ps, 1998. 
	* Elegant is Philips advanced compiler construction tools that have grown into a full programming language. However, the scanner generator seems to be based on Dragon book so not much new there. They have automatic error recovery though.

	* Generic Attrbiute Grammars with ideas to use for structuring
	  a compiler/rewriter/ag.
	    http://citeseer.nj.nec.com/saraiva99generic.html

	* Mest avancerade FP parser combinatorerna?
	  Mimico: A Monadic Combinator Compiler Generator 
	  http://citeseer.nj.nec.com/camarao01mimico.html

	* Aspect-Oriented Compilers
	    http://citeseer.nj.nec.com/136611.html
 	  Goes further than AttrGrammars so that compilers can be structured
	  by their different semantic aspects (environment, 
	  lexical analysis...)
	* Lots of Haskell goodies:
	    http://www.haskell.org/libraries/#prettyprinting
	* A Comiler Toolkit in Haskell
	    http://www.cse.unsw.edu.au/~chak/haskell/ctk/
	* Pretty-printer toolkit based on _John Hughes ideas
	   (May be older than the ones below?!)
	    http://www.cse.unsw.edu.au/~chak/haskell/code/Pretty.hs
	* Fast, Error-Correcting Haskell PArser Combinators +
          Paper on implementing them in Java! (Not fat, but flexible)
	  Simple, Functional Attribute Grammar system:
	     http://www.cs.uu.nl/people/doaitse/#Software
        * and also Optimal Pretty Printing Combinators:
	     http://www.cs.ruu.nl/groups/ST/Software/PP/
	     http://www.cs.ruu.nl/groups/ST/Software/PP/braga.pdf
             http://www.cs.ruu.nl/groups/ST/Software/PP/UserManPP.html
	* and also a book on "Implementation of Programming Languages"
          which includes much good stuff:
	     http://www.cs.uu.nl/people/doaitse/Books/ipt-dict-20010306.pdf
        * and also a book on "Grammars and Parsing" which doesn't seem to work:
	     http://www.cs.uu.nl/people/doaitse/Books/GramPars2001.pdf
        * and a paper on attribute grammars:
	     http://www.cs.uu.nl/people/doaitse/Papers/2000/WAGA2000.pdf
	* Advanced Pretty-printing ideas ("Galley concept") which is more
	  like document formatting (Maybe not related?):
	    http://citeseer.nj.nec.com/424131.html

   	* Aladin Abstract Machine for marrying FuncProg and ImpProg
	    http://compscinet.dcs.kcl.ac.uk/JP/PDFPapers/jp040201.pdf

	* Can we always adopt the longest-match rule in a scanner?
	  Detection algorithm using the CFG to detect when this is safely so.
		http://citeseer.nj.nec.com/70944.html
	* PAGODE: a realistic back-end generator 
		http://citeseer.nj.nec.com/canalda95pagode.html
	* Keith Cooper, GA in compilers
	   K.D. Cooper, P.J. Schielke, and D. Subramanian, `` Optimizing for Reduced Code Space using Genetic Algorithms,'' LCTES 99, June 1999. 
        * John Aycock, R. Nigel Horspool: Directly-Executable Earley Parsing. 229-243
	* Peter Thiemann: Compiling Adaptive Programs by Partial Evaluation. 264-278
	* Cocktail tools support all phases of compiler construction. 
		http://www.informatik.uni-stuttgart.de/ifi/ps/cocktail/
	  Seems to be very broad.
	* HP's Dynamo project for run-time optimization of native code
		http://www.hpl.hp.com/cambridge/projects/Dynamo/
		http://www.hpl.hp.com/cambridge/projects/Dynamo/PLDI2000.pdf
		
	* Parsing in Lisp with META:
		http://linux.rice.edu/~rahul/hbaker/Prag-Parse.html

        * cocom.sf.net is a set of CC tools which seems very powerful.
	  Includes fast Earley parser with C/C++ interface and MSTA
          which is LR(k) parser with EBNF input.
	* SLK parser generator for LL(k). Table-driven. Commercial => no src.
	* TCLLk. Transforms LL(k) to LL(1) with lookahead trees. Table-driven.
	  Source for Icon language is available.
	   http://www.iit.edu/~tc/toolsfor.htm
	   http://www.iit.edu/~tc/llk.htm
	   It has later been implemented in Python as part of the book
	   Python Programming Patterns. The implementation is very small;
	   only 655 lines of Python code. But it looks like its only an 
	   implementation of the parser that use the tables produced by the
	   Icon implementation.
	  It uses the following process:
		1. Remove left recusion
			a, Remove direct left recursion
			b, Expand nonterminals and remove direct recursions
		2. Factor
			a, Direct factoring: Factor common prefixes
			b, Deep factoring: Expand nonterms and then direct fac 
		3. Build look-ahead trees if necessary
		4. Write LL(1) parsing tables.
	* mxTextTools implements a Tagging Engine which is somthing like a
	  customizable regexp engine that is controlled from a Python array
	  with a tagging program. This can be used to implement a parser
	  by creating a tagging program and then calling mxTextTools.
	  Martel is such a parser generator that uses Regexp and generates
	  tag tables.
	* Lots of pointers and comments on ParserGens allowing backtracking
		http://www.cs.rhul.ac.uk/research/languages/projects/lookahead_backtrack.shtml

	  Mentions their GRDP parser generator which should be released
	  "Real soon now"...

	  They have done some work on Reduced Derivation Trees which seems
	  similar to Rockit lift operator and tree spec behavior. May be 
	  more advanced since they allow priorities etc but the resulting
	  grammars look hairy and I think Rockit's style is simpler.
	  