yiyiyacc

"Yes, indeed! Yiyiyacc *is* yet another compiler compiler!"

Every man should father a child, build a house, plant a tree, and write a compiler compiler. This one is mine.

yiyiyacc is a small lalr(1) syntax generator, designed to output very slim self-contained c methods.

Among others, it has been used to generate the expression evaluation in swfc.

This is an example for a yiyiyacc grammar:

E -> E '+' T
     %% = %1 + %2;
E -> '-' T
     %% = 0 - %1;
E -> E '-' T
     %% = %1 - %2;
E -> T
T -> T '*' F
     %% = %1 * %2;
T -> T '/' F
     %% = %1 / %2;
T -> F
F -> <*>
F -> '(' E ')'
     %% = %1;
<*> 
     %% = atof(%1);

And below is the C code that will be generated. Notice that the complete parser is contained in a single function.

/* automatically generated by yiyiyacc, http://www.quiss.org/yiyiyacc/ */
double parse(const char*s)
{
    static int chr2index[256];
    static int initialized=0;
    if(!initialized) {
	initialized=1;
	memset(chr2index, -1, sizeof(chr2index));
	chr2index['+'] = 0;
	chr2index['-'] = 1;
	chr2index['*'] = 2;
	chr2index['/'] = 3;
	chr2index['('] = 5;
	chr2index[')'] = 6;
	chr2index['\0'] = 7;
    }

    int stackpos = 1;
    int stack[256];
    double values[256];
    stack[0]=0;
    int accept = 18;
    static int left[10]={11,8,8,8,8,9,9,9,10,10}; //production left side
    static int plen[10]={1,3,2,3,1,3,3,1,1,3}; //production size
    static int table[18][12] = {
        {0, 4, 0, 0, 5, 6, 0, 0, 1, 2, 3, 0},
        {7, 8, 0, 0, 0, 0, 0, 18, 0, 0, 0, 0},
        {-4, -4, 9, 10, 0, 0, -4, -4, 0, 0, 0, 0},
        {-7, -7, -7, -7, 0, 0, -7, -7, 0, 0, 0, 0},
        {0, 0, 0, 0, 5, 6, 0, 0, 0, 11, 3, 0},
        {-8, -8, -8, -8, 0, 0, -8, -8, 0, 0, 0, 0},
        {0, 4, 0, 0, 5, 6, 0, 0, 12, 2, 3, 0},
        {0, 0, 0, 0, 5, 6, 0, 0, 0, 13, 3, 0},
        {0, 0, 0, 0, 5, 6, 0, 0, 0, 14, 3, 0},
        {0, 0, 0, 0, 5, 6, 0, 0, 0, 0, 15, 0},
        {0, 0, 0, 0, 5, 6, 0, 0, 0, 0, 16, 0},
        {-2, -2, 9, 10, 0, 0, -2, -2, 0, 0, 0, 0},
        {7, 8, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0},
        {-1, -1, 9, 10, 0, 0, -1, -1, 0, 0, 0, 0},
        {-3, -3, 9, 10, 0, 0, -3, -3, 0, 0, 0, 0},
        {-5, -5, -5, -5, 0, 0, -5, -5, 0, 0, 0, 0},
        {-6, -6, -6, -6, 0, 0, -6, -6, 0, 0, 0, 0},
        {-9, -9, -9, -9, 0, 0, -9, -9, 0, 0, 0, 0}};

    const char*p = s;
    while(1) {
        const char*pnext = p+1;
        int action;
        double value;
        if(!stackpos) {
            fprintf(stderr, "Error in expression\n");
            return 0.0;
        }

        if(chr2index[*p]<0) {
            action = table[stack[stackpos-1]][4];
            if(action>0) {
                while(chr2index[*pnext]<0) 
                    pnext++;
                value = atof(p);
            }
        } else {
            action = table[stack[stackpos-1]][chr2index[*p]];
        }

        if(action == accept) {
            return values[stack[stackpos-1]];
        } else if(action>0) { // shift
            if(stackpos>254) {
                fprintf(stderr, "Stack overflow while parsing expression\n");
                return 0.0;
            }
            values[stackpos]=value;
            stack[stackpos++]=action;
            p=pnext;
        } else if(action<0) { // reduce
            stackpos-=plen[-action];
            stack[stackpos] = table[stack[stackpos-1]][left[-action]];
            switch(-action) {
              case 1:
                values[stackpos] = values[stackpos+0] + values[stackpos+2];
              break;
              case 2:
                values[stackpos] = 0 - values[stackpos+1];
              break;
              case 3:
                values[stackpos] = values[stackpos+0] - values[stackpos+2];
              break;
              case 5:
                values[stackpos] = values[stackpos+0] * values[stackpos+2];
              break;
              case 6:
                values[stackpos] = values[stackpos+0] / values[stackpos+2];
              break;
              case 9:
                values[stackpos] = values[stackpos+1];
              break;
            }
            stackpos++;
        } else {
            fprintf(stderr, "Syntax error in expression\n");
            return 0.0;
        }
    }
}