rexp → rexp'|'T1 | T1

T1 → T1' 'T2 | T2

T2 → T2* | T3

T3 → (rexp) | letter

letter = [a-zA-Z]

利用课本P119页程序清单4-3的算法，消除上述规则中的左递归，结果如下：

rexp → T1exp'

exp' → '|' T1rexp' | ε

T1 → T2T1'

T1' → ' 'T2T1' | ε

T2 → T3T2'

T2' → *T2'|ε

T3 → (rexp) | letter

根据上述规则书写程序：

bool flag;
char formula[100];
int i;

void rexp();
void rexp1();
void t1();
void t11();
void t2();
void t21();
void t3();
void match(char expectedToken);

void error()
{
    fprintf(stderr,"IS NOT A REGULAR EXPRESSION!\n");
    exit(1);
}

void match(char expectedToken)
{
    if(formula[i]==expectedToken)
        i++;            //get the next token
    else
        error();
}

void rexp()
{
    t1();
    rexp1();
}

void rexp1()
{
    if(formula[i]=='|')
    {
        match('|');
        t1();
        rexp1();        //update by Plator
    }
}

void t1()
{
    t2();
    t11();
}

void t11()
{
    if(formula[i]==' ')
    {
        match(' ');
        t2();
        t11();
    }
}

void t2()
{
    t3();
    t21();
}

void t21()
{
    if(formula[i]=='*')
    {
        match('*');
        t21();        //update by Plator
    }
}

void t3()
{
    if(formula[i]=='(')
    {
        match('(');
        rexp();    
        if(formula[i]==')')
            match(')');
    }
    else if(formula[i]>='a' && formula[i]<='z')
        match(formula[i]);
    else
        error();
}

int main()
{
    while(cin.getline(formula,100))
    {
        flag=1;
        i=0;
        rexp();
        if(formula[i]=='\0')
            cout<<"IS A REGULAR EXPRESSION!"<<endl;
        else
            error();
    }
    return 0;
}

完整代码： /Files/Plator/rexp.rar