root/trunk/dparser/dparse.d

/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
This is a template meta-program that generates a recursive decent
parser. It is to be mixed into a class or struct. The parameters
for the template are: a string containing almost normal BNF
reduction definitions, and a string defining the start rule.

It extends BNF by allowing "|" for "or" but doesn't implement
optional or repeated terms.

$(TABLE
$(TR $(TD Grammar)  $(TD ::= Rule Grammar | Rule))
$(TR $(TD Rule)     $(TD ::= ID ":" Cases ";"))
$(TR $(TD Cases)    $(TD ::= Case "|" Alt | Case))
$(TR $(TD Case)     $(TD ::= ID "/" Sequence))
$(TR $(TD Sequence) $(TD ::= ID Sequence | ID))
$(TR $(TD Item)     $(TD ::= ID "[?+*]?";))
$(TR $(TD ID)       $(TD ::= "[A-Za-z][A-Za-z0-9]*";))
)

The term between the ':' and '/' is the name of the reduction
action. If a reduction is used but not defined a terminal must
be defined for it.

Example:

-----------------------------------------
struct set
{
/******* action code ********/
static PObject Action(char[] string : "MULTIPLY")(PObject[3] set)
   {...}
static PObject Action(char[] string : "SUM"     )(PObject[3] set)
   {...}
static PObject Action(char[] string : "PASS"    )(PObject[1] set)
   {...}

/******** Terminal code *********/
static PObject Terminal(char[] name : "NUM")(IParser p)
   {...}
static PObject Terminal(char[] name : "PLUS")(IParser p)
   {...}
static PObject Terminal(char[] name : "TIMES")(IParser p)
   {...}

// "ADD" indicates the root rule

mixin Parser!("ADD", ReduceWhite(
    "PRIMARY : PASS/     NUM;
     MUL     : MULTIPLY/ PRIMARY TIMES MUL
             | PASS/     PRIMARY;
     ADD     : SUM/      MUL PLUS ADD
             | PASS/     MUL;
    "));
}

void main()
{
   auto a = new ExpGrammer;
   a.data = "1 + 3 * 4 + 5 * 5 ";

   Value v = cast(Value)set.Parser(a);

   assert(v !is null,"ERR0R");
   writef("%d\n", v.value);
}
----------------

This meta program is distributed with no warranty of any kind.

Author: Benjamin Shropshire (shro8822drop_this at vandals DOT uidaho edu)

Please give credit where credit is due. Don't remove this notice.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
module syntax.dparse;

// Add not grammer, might use non-Action parser
private import std.stdio : writef;
private import std.string : ToString = toString ;

private import glue.templates;


/******************************************************************************
********* PObject Hieracrcy
******************************************************************************/


/** Base class for parsed objects
*/
abstract class PObject
{
    ///
    abstract bool fail();

    abstract char[] BaseName();
}


/************************************************
    Common base type for ObjectVector types
*/
class PObjectVectorBase : PObject
{
    char[] BaseName(){return typeof(this).stringof;}
    abstract char[] string();
}

/************************************************
    A template sub class of PObject for basic tree building
*/
class PObjectVector(uint i) : PObjectVectorBase
{
    char[] BaseName(){return typeof(this).stringof;}
    alias Tupleof!(i,PObject) type;
    type data;
    /// constructor taking i PObjects
    this(type s)
    {
        foreach(int j, t; type)
            data[j] = s[j];
    }

    this(PObject[i] d)
    {
        foreach(uint j, v; data)
        {
            data[j] = d[j];
        }
    }

    PObject[] Get()
    {
        PObject[i] ret;
        foreach(uint j, v; data)
        {
            ret[j] = data[j];
        }
        return ret.dup;
    }

    /// Get the j'th item
    PObject Get(uint j)
    {
        switch(j)
        {
            foreach(int k, t; type)
                case k: return data[k];
            default: throw new Error("Out of bound");
        }
    }

    /// Get the j'th item
    PObject GetT(uint j)()
    {
        static if(j<data.length)
            return data[j];
        else
            static assert(false);
    }

    char[] string()
    {
        char[] ret =  "[";

        foreach(i,_;type)
        {
            if(auto v = cast(PObjectVectorBase)data[i])
            {
                ret ~= " " ~ v.string();
            }
            else if(auto v = cast(PObjectBoxBase)data[i])
            {
                ret ~= " \"" ~ v.string()~\";
            }
            else ret ~= " <UNKNOWN>";
        }
        return ret ~ "]";
    }

    bool fail() { return false; }
}

/************************************************
    Common base type for BoxObject types
*/
class PObjectBoxBase : PObject
{
    char[] BaseName(){return typeof(this).stringof;}
    abstract char[] string();
}

/**
*/
class PObjectBox(T,bool str = true) : PObjectBoxBase
{
    char[] BaseName(){return typeof(this).stringof~"!("~T.stringof~")";}
    T t;

    ///
    T Get() { return t; }

    ///
    this(T ti){t=ti;}

    bool fail() { return false; }

    ///
    char[] string()
    {
        static if(str)
        {
            static if(is(T == char[]))
                return t;
            else static if(is(ToString(t)))
                return ToString(t);
            else
                return "<<"~T.stringof~">>";
        }
        else
            return "<<"~T.stringof~">>";
    }
}
//typedef PObjectVector!(5) Five;

/**
*/
class PObjectList(T) : PObject
{
    char[] BaseName(){return typeof(this).stringof;}
    debug(TypeReport) pragma(msg, ">>T-"__FILE__~":"~itoa!(__LINE__)~": "~typeof(this).stringof~"!("~T.stringof~")");

    T[] list;
    int at=0;

    this(){ list = null; }

    this(T ti)
    {
        static if(is(T :Object)) assert(ti !is null);
        list = new T[5];
        list[at] = ti;
        at++;

    }

    /// Add a T
    uint Add(T ti)
    {
        static if(is(T :Object)) assert(ti !is null);
        if(list.length <= at) list.length = at + 5;
        list[at] = ti;
        at++;
        return at-1;
    }

    /// return the number of items stored
    uint Count(){return at;}

    ///
    T[] get()
    {
        return list[0..at];
    }

    bool fail() { return false; }
}
unittest
{
    writef("unittest@"__FILE__":"~itoa!(__LINE__)~\n);
    
    auto o = new PObjectList!(int);
    o.Add(1);
    o.Add(2);
    o.Add(3);
    o.Add(4);
    o.Add(5);
    o.Add(6);

    assert(o.get == [1,2,3,4,5,6], "PObjectList failed");
}

/************************************************
    List Object that build to the left
*/
class PObjectListLeft(T) : PObjectList!(T)
{
    char[] BaseName(){return typeof(this).stringof;}
    debug(TypeReport) pragma(msg, ">>T-"__FILE__~":"~itoa!(__LINE__)~": "~typeof(this).stringof~"!("~T.stringof~")");

    this(T t)
    {
        list.length = 5;
        list[$-1] = t;
        at = 1;
    }
    this(){}
    
    /// Add a T
    uint Add(T ti)
    {
        static if(is(T :Object)) assert(ti !is null);

        if(list.length <= at)
        {
            auto t = list[$-at..$].dup;
            list.length = at + 5;
            list[$-at..$] = t;
        }
        list[$-1-at] = ti;
        at++;
        return at-1;
    }

    T[] get()
    {
        return list[$-at..$];
    }
}

unittest
{
    writef("unittest@"__FILE__":"~itoa!(__LINE__)~\n);
    
    auto o = new PObjectListLeft!(int)( 0);
               o.Add( 1); o.Add( 2); o.Add( 3); o.Add( 4); o.Add( 5); o.Add( 6); o.Add( 7); o.Add( 8); o.Add( 9);
    o.Add(10); o.Add(11); o.Add(12); o.Add(13); o.Add(14); o.Add(15); o.Add(16); o.Add(17); o.Add(18); o.Add(19);
    o.Add(20); o.Add(21); o.Add(22); o.Add(23); o.Add(24); o.Add(25); o.Add(26); o.Add(27); o.Add(28); o.Add(29);

    assert(o.get == [29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0], "PObjectListLeft failed");
}


/************************************************
    A sub class of PObject that is used for repeated reductions
*/
class PObjectSet : PObjectList!(PObject)
{
    char[] BaseName(){return typeof(this).stringof;}
    /// Discard some PObjects
    void Back(uint b)
    {
        at = b;
    }
}



/************************************************
    Uniform term to prevent needing to know the
    exact type at compile time.
*/
interface PInterfaceLeftFactor(T) { PObject InsertLeft(T,PObject); }

/************************************************
    PObject that uses T.Action!(str) to process a
    left side term with a Right side term
*/
class PObjectLeftFactorT(Tp, int i, char[] str) : PObjectVector!(i), PInterfaceLeftFactor!(Tp)
{
    this(PObject[i] d){super(d);}

    PObject InsertLeft(Tp that, PObject L)
    {
        PObject[i+1] args;

        args[1..$] = Get;
        args[0] = L;

        return SpecialAction!(Tp,str)(that,args);
    }
}


/************************************************
    default fail object
*/
class PObjectFail : PObject
{
    char[] BaseName(){return typeof(this).stringof;}
    char[][] msg;

    this()
    {
        msg.length = 1;
        msg[0] = "Failed";
    }

    this(char[] m)
    {
        msg.length = 1;
        msg[0] = m.dup;
    }

    void Add(char[] m)
    {
        msg ~= m.dup;
    }

    bool fail() { return true; }
}

/************************************************
    default Pass object
*/
class PObjectPass : PObject
{
    char[] BaseName(){return typeof(this).stringof;}
    this() { }
    bool fail() { return false; }
}

/************************************************
    default Filler object, returns fail state as instructed
*/
class PObjectFill : PObject
{
    char[] BaseName(){return typeof(this).stringof;}
    bool b;
    this(bool _b){b=_b;}
    bool fail(){return b;}
}

/*******************************************************
    interface to handle parser data
*/
interface IParser
{
    uint pos();
    void pos(uint);
    debug(dParse_runtime) void mark();
}


/******************************************************************************
******** genaric Template code
******************************************************************************/


/** generate a tuple of i U's
*/
template Tupleof(uint i, U)
{
    static if(i == 0)
        alias T!() Tupleof;
    else
    static if(i == 1)
        alias T!(U) Tupleof;
    else
        alias T!(Tupleof!(i-1, U), U) Tupleof;
}

/** Tuple literal template
*/
template T(A...){alias A T;}


/******************************************************************************
******** CTFE functions
******************************************************************************/

/******************************
drop leading whitespace
*/
char[] DropWhiteF(char[] str)
{

    foreach(int i, char c; str)
        switch(c)
        {
            case ' ', '\t', '\r', '\n':
                continue;
            default:
                return str[i..$];
        }
        return "";
}
struct UnittetDropWhite{
    static const char[] str = DropWhiteF(" \t\n\rhello");
    static assert(DropWhiteF(" \t\n\rhello") == "hello");
}


/**********************************
  find first instance of t in str,
  return str up through that char
*/
char[] FindChar(char t)(char[] str)
{
    foreach(int i, char c; str)
        if(c == t)
            return str[0..i+1];
    return str;
}


/**********************************
  return an identifier
*/
char[] GetID(char[] instr)
{
    char[] str = DropWhiteF(instr);

    if(str.length == 0) return "";

    if(
        !('a' <= str[0] && str[0] <= 'z') &&
        !('A' <= str[0] && str[0] <= 'Z') &&
        !('_' == str[0])
    ) return "";

    foreach(int i, char c; str)
    if(
        !('a' <= c && c <= 'z') &&
        !('A' <= c && c <= 'Z') &&
        !('0' <= c && c <= '9') &&
        !('_' == c)
    ) return str[0..i];

    return str;
}
struct UnittetGetID{
    static assert(GetID("hello world") == "hello", GetID("hello world"));
}

/*********************************
  replace all sequences of white
  space with single spaces
*/
public char[] ReduceWhite(char[] str)
{
    bool pass = true;
    int at = 0;
    foreach(char c; str)
        switch(c)
        {
            case ' ', '\n', '\r', '\t':
                if(!pass)
                {
                    pass = true;
                    str[at++] = ' ';
                }
                break;

            default:
                pass = false;
                str[at++] = c;
                break;
        }
    return str[0..at];;
}
static const char[] test = ReduceWhite("hello");

/*********************************
    Extract # from "$(C,#,NAME)"
*/
int ExtractCount(char[] str)
{
    int ret = int.min;

    if(str.length > 4 && '0' <= str[0] && str[0] <= '9')
    {
        ret = str[0] - '0';
        for(int i = 1; i<str.length; i++)
        {
            if('0' <= str[i] && str[i] <= '9')
            {
                ret *= 10;
                ret += str[i] - '0';
            }
            else
                break;
        }
    }

    return ret;
}

/*********************************
    Extract NAME from "$(C,#,NAME)"
*/
char[] ExtractAct(char[] str)
{
    int c, i;
    for(i=0; i < str.length && c < 2; i++)
        c += (str[i] == ',');

    str = str[i..$];
    i=0;
    int d = 1;
    while(i < str.length && d > 0)
    {
        d += (str[i] == '('); 
        d -= (str[i] == ')'); 
        i++;
    }

    return str[0..i-1];
}

static assert(ExtractAct("$(T,1,$(N,1,abc,def))") == "$(N,1,abc,def)", ExtractAct("$(T,1,$(N,1,abc,def))"));

/******************************************************************************
******* Special Action Code
******************************************************************************/

/// Pack up stuff in a computed type of PObjectLeftFactorT Object
PObject L_Action(Tp, char[] str ) (Tp, PObject[ExtractCount(str[4..$])] i)
{
    static const int c = ExtractCount(str[4..$]);
    static const char[] n = ExtractAct(str);
    static if(false) pragma(msg, str~" == $(L,"~c.stringof~","~n~")");

    return new PObjectLeftFactorT!(Tp, c, n)(i);
}

/// Left Process a Leftmost term and right side terms list.
PObject T_Action(Tp,char[] str) (Tp that, PObject[1+ExtractCount(str[4..$])] i)
{
    static const int num = ExtractCount(str[4..$]);
    static const char[] act = ExtractAct(str);
    static if(false) pragma(msg, str~" == $(T,"~num.stringof~","~act~")");

    PObject[num] args = i[0..num];
    auto ret = SpecialAction!(Tp,act)(that,args);

    auto listO = cast(PObjectList!(PObject)) i[num]; 
    auto list = listO.get;

    foreach(obj; list)
    {
        auto Tobj = cast(PInterfaceLeftFactor!(Tp))obj;
        ret = Tobj.InsertLeft(that,ret);
    }
    return ret;
}


template GetSize(Tp, char[] str)
{
    alias Tp.Action!(str) Fn;
    static if(is(typeof(Fn) Args == function))
        const int size = Args[0].length;
    else
        static assert(false);
}

template GetArgs(Tp, char[] str)
{
    alias Tp.Action!(str) Fn;
    static if(is(typeof(Fn) Args == function))
    {}
    else
        static assert(false);
}

/// Next actions 

template N_parts(char[] str)
{
    const int num = ExtractCount(str[4..$]);
    const char[] firstAct = ExtractAct(str[4..$]);
    const char[] s1 = str[FindChar!(',')(str[4..$]).length + 4..$];
    const char[] secondAct = s1[FindChar!(',')(s1).length..$-1];
}

//alias N_parts!("$(N,3,dummy,dummy)") NP;

PObject N_Action(Tp,char[] str) (Tp that, GetArgs!(Tp,N_parts!(str).firstAct).Args