cenggongyufa.c

编写关于编译原理知识的基本语法树和词法分析器

                                                                                                                
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<dos.h>
char analystack[20];/*分析栈*/
char stringleft[20];/*剩余串*/
char terminal[20]={'i','+','*','(',')','#'};/*终结符  */
char unterminal[20]={'E','G','T','S','F'};/*非终结符   */

int j=0,b=0,top=0,l,xyz;/*L为输入串长度b为已归约的终结符的个数 */

typedef struct type/*产生式类型定义      */
{
    char origin;/*大写字符  */
    char array[5];/*产生式右边字符 */
    int length;/*字符个数      */
}type;

struct type e,t,g,g1,s,s1,f,f1;/*结构体变量  */
struct type C[10][10];/*预测分析表  */

void printstack()/*输出分析栈  */
{
    int a;/*指针*/
    for(a=0;a<=top;a++)
        printf("%c",analystack[a]);
    printf("\t\t");
}

void printleft()/*输出剩余串*/
{
    int j;
    for(j=0;j<b;j++)/*输出对齐符*/
        printf(" ");
    for(j=b;j<=l;j++)
        printf("%c",stringleft[j]);
    printf("\t\t\t");
}

void main()
{
    int m,n,k=0,flag=0,finish=1;
    char ch,x;
    struct type cha;/*用来接受C[m][n]*/

    e.origin='E';           /*把文法产生式赋值结构体*/
    strcpy(e.array,"TG");
    e.length=2;
    t.origin='T';
    strcpy(t.array,"FS");
    t.length=2;
    g.origin='G';
    strcpy(g.array,"+TG");
    g.length=3;
    g1.origin='G';
    g1.array[0]='^';
    g1.length=1;
    s.origin='S';
    strcpy(s.array,"*FS");
    s.length=3;
    s1.origin='S';
    s1.array[0]='^';
    s1.length=1;
    f.origin='F';
    strcpy(f.array,"(E)");
    f.length=3;
    f1.origin='F';
    f1.array[0]='i';
    f1.length=1;

    for(m=0;m<=4;m++)/*初始化分析表*/
        for(n=0;n<=5;n++)
            C[m][n].origin='N';/*全部赋为空*/
   /*填充分析表*/
   C[0][0]=e;C[0][3]=e;
   C[1][1]=g;C[1][4]=g1;C[1][5]=g1;
   C[2][0]=t;C[2][3]=t;
   C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;
   C[4][0]=f1;C[4][3]=f;
  printf("Attention:This program can only recognize a sentence consisted of 'i','+','*','(',')'and have an end of'#'\n");
   printf("Please input your sentence!!:");
   do/*读入分析串*/
   {
       scanf("%c",&ch);
       if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
       {
           printf("There are illegal word in input string!\n");
           goto end;
       }
       stringleft[j]=ch;
       j++;
   }while(ch!='#');
   l=j;                  /*L为分析串长度*/
   ch=stringleft[0];     /*当前分析字符 */
   analystack[top]='#'; analystack[++top]='E';/* '#','E'进栈 */
   printf("\n\n");
   printf("step\tanalysis stack \t      character left \t\tProcess formula\n");
   do
   {
      x=analystack[top];/*x为当前栈顶字符*/
      printf("%d",k++);   /* 输出第几步 */
      printf("\t\t");
       for(j=0;j<=5;j++)/*判断是否为终结符*/
          if(x==terminal[j])
          {
              flag=1;
              break;
          }
          if(flag==1)/*如果是终结符*/
          {
              if(x=='#')
              {
                  printf("acc!\n");/*接受 */
                  goto end;
              }
              if(x==ch)     /*当前分析字符*/
              {
                  printstack();
                  printleft();
                  top--;
                  printf("%c match!\n",ch);
                  ch=stringleft[++b];/*下一个输入字符*/
                  flag=0;/*恢复标记*/
              }
              else
              {
                  printstack();
                  printleft();
                  printf("%c Error!\n",ch);/*输出出错终结符*/
                  goto end;
              }
          }
          else    /*非终结符处理*/
          {
              for(j=0;j<=4;j++)
                if(x==unterminal[j])
                {
                    m=j;/*行号*/
                    break;
                }
              for(j=0;j<=5;j++)
                if(ch==terminal[j])
                {
                    n=j;/*列号*/
                    break;
                }
              cha=C[m][n];
              if(cha.origin!='N')
              { printstack();
                printleft();
                top--;
                printf("%c-",cha.origin);
                for(j=0;j<cha.length;j++)
                printf("%c",cha.array[j]);
                printf("\n");
                for(j=(cha.length-1);j>=0;j--)
                {

                    analystack[++top]=cha.array[j];
                }
                if(analystack[top]=='^')
                    top--;
               }
               else
               {
                  printstack();
                  printleft();
                  printf("%c Error!\n",x);
                  goto end;
               }
          }
   }while(finish==1);
  end: getch();
}