G2文法之最左推导

G2

E->E+T | E-T | T

T->T*F | T/F |F

F->(E) | n

n->0 | 1 |2 |… |9

注意扫描是从右向左扫描，第一次的展开其实得到的是最后一个符号。

如果遇到+或-，则将表达式中的E变为E+T或E-T；
如果遇到*或/，则将表达式中的T变成T*F或T/F；
如果遇到括号对，则将表达式中的F变成(E)；
如果没有符号，只有数字，则将表达式中的E变成T，T变成F，F变成n，n变成相应数字
遍历完一次之后，以符号为分割线，将表达式分割成两部分进行下一次扫描

持续递归，直到中间表达式中没有字母，只剩数字和符号

#include <stdio.h>
#include <string.h>
void Generate(char *s,int L,int n,char P);
int step=1;
int main()
{
    char LIST[1024];
    int N;
    printf("请输入所需推导的式子:\n");
    scanf("%s",LIST);
    N=strlen(LIST);
    Generate(LIST,0,N-1,'E');
    printf("最左推导此式共需%d步",step-1);
    printf("\nEND\n");
    return 0;
}

void Generate(char *s,int L,int n,char P)
{
    int i,flag=0,t=0;
    if(P=='E')
    {
        for(i=n;i>=L;--i) // 必须要从右往左扫描字符串
        {
            if(s[i]==')')
                t++;
            else if(s[i]=='(')
                t--;
            if(t) continue;

            if(s[i]=='+'||s[i]=='-')
            {
                printf("第%d步: E->E%cT\n",step,s[i]);
                step++;
                Generate(s,L,i-1,'E');
                Generate(s,i+1,n,'T');
                flag=1;
                break;
            }
        }
            if(!flag)
            {
                printf("第%d步: E->T\n",step);
                step++;
                Generate(s,L,n,'T');
            }
    }
    else if(P=='T')
    {
        for(i=n;i>=L;--i)
        {
            if(s[i]==')')
                t++;
            else if(s[i]=='(')
                t--;
            if(t) continue;

            if(s[i]=='*'||s[i]=='/')
            {
                printf("第%d步: T->T%cF\n",step,s[i]);
                step++;
                Generate(s,L,i-1,'T');
                Generate(s,i+1,n,'F');
                flag=1;
                break;
            }
        }
            if(!flag)
            {
                printf("第%d步: T->F\n",step);
                step++;
                Generate(s,L,n,'F');
            }
    }
    else if(P=='F')
    {
        if(s[L]=='(')
        {
            printf("第%d步: F->(E)\n",step);
            step++;
            Generate(s,L+1,n-1,'E');
        }
        else
        {
            printf("第%d步: F->n\n",step);
            step++;
            printf("第%d步: n->%c\n",step,s[L]);
            step++;
        }
    }
}