http://felix.sf.net

This project is a high performance compiler and ML family
language developed using Python, Ocaml and C++ tools.

The Felix language allows the end user to define their own grammar,
in particular to add whole 'Domain Specific Sub Languages' to
the system, as a combination of libraries and syntax extensions.

This is implemented with two Ocaml libraries: Dypgen, an extensible GLR
parser takes care of the parsing, whilst the user actions are written
using a tool-chain that starts with Scheme code to calculate AST nodes as
Scheme values (S-expressions): Felix is using OCS Scheme, which is an R5RS
compliant embedded Scheme implementation written in Ocaml:

        http://will.iki.fi/software/ocs/

A sample of the grammar, which happens to implement
the 'if .. then .. else .. endif' expression:

  sconditional := if sexpr then sexpr selse_part endif =>#
    "`(ast_cond (,_2 ,_4 ,_5))";

  selif := elif sexpr then sexpr =># "`(,_2 ,_4)";

  selifs := selif =># "`(,_1)";
  selifs := selifs selif =># "(cons _2 _1)";

  selse_part:= else sexpr =># "_2";
  selse_part:= selifs else sexpr =>#
      """
        (let ((f (lambda (result condthn)
          (let ((cond (car condthn)) (thn (cadr condthn)))
            `(ast_cond (,cond ,thn ,result))))))
        (fold_left f _3 _1))
      """;

where the Scheme code is given after the =># symbol
as a string, and _1, _2 etc are names for the S-expressions
produced by the nonterminals in the production.

I wrote most of this code, having never programmed in Scheme before.

There are some other possible applications for the Scheme system,
one of which is to manage the optimisation passes of the compiler,
and perhaps help in the back end code generation: in general,
to make the scheduling and management of the compiler components
easier and more amenable to dynamic loading and interpretation
of user written specifications.

Ultimately, it may be possible to remodel the compiler as a Scheme
program, with heavyweight and specific functionality written in
Ocaml and embedded as primitives in the Scheme interpreter.

At present, however, the major obstacle for end users is that
to program syntax extensions, they have to write messy Scheme code.
Many usage patterns might be simplified by a combination of parsing
and suitable refactoring of the Scheme code, eg so there are convenience
functions for constructing binary operator AST nodes.

Conversely, the ability of the Scheme to handle various calculations
effectively may influence the Felix grammar, for example by using
table driven operations, specific sets of terminals might be removed
from the language and replaced by a nonterminal which delegates
to a table lookup in Scheme.

In particular, the current system is only a FIRST ORDER system,
in that whilst the end user can use syntax extension grammar
and Scheme code to calculate any AST nodes required, this
mechanism cannot be used to change the grammar used to SPECIFY
how to extend a grammar.

For example, there is no way to add a production which would
allow the end user to write:

        infix "*^" precedence "mult" assoc left;

To do this requires a SECOND ORDER extension mechanism, that is,
one which can be used to extend the syntax used to extend the
syntax.

I hear Scheme is good at this kind of thing, which is why I chose
it as the implementation language.

If you're interested, please build the Felix project first:

        svn co https://felix.svn.sourceforge.net/svnroot/felix/felix/trunk .
        python autogen.py

and take a look at the language syntax specification:

        lib/nugram.flxh

(and promise not to fall over laughing at how bad my Scheme code is :)