新建 文本文档 (5).txt

关于LL（1）分析器的

编译原理课程设计-LL(1)语法分析（文政原创）  
［ 作者：wenzheng    转贴自：本站原创    点击数：835    更新时间：2004-11-27    文章录入：admin ］ 
[ 在这里.COM 提示]：双击自动滚屏，再单击停止 
 


一、设计目的： 
理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现。

二、设计内容：
根据下面LL(1)文法，对输入串w: (i+i)*(i+i)+i*i进行LL(1)分析,要求如下：
1、先手工建立LL(1)分析表；
2、分析输入串，判断是否是语法上正确的句子，并输出整个分析过程。
LL(1)文法G为：
E  →TE’
E’→+TE’|ε
T  →FT’
T’→*FT’|ε
F  →(E)|id
分析算法：
输入：串w和文法G的分析表M。
输出：如果W属于L（G），则输出W的最左推导，否则报告错误。
方法：开始时，#S在分析栈中，其中S是文法的开始符号，在栈顶；令指针ip指向W#的第一个符号；repeat
让X等于栈顶符号，a为ip所指向的符号；
if X 是终结符号或# then
If X=a then  把X从栈顶弹出并使ip指向下一个输入符号
else error()
else   /*X 是非终结符号*/
  if M[x,a]=Xày1y2…yk  then begin
从栈中弹出X；把yk,yk-1,…,y1压入栈，y1在栈顶；
输出产生式Xày1y2…yk；end
else error()
until X=#          /*栈空*/


LL(1)语法分析程序流程图

 



四、LL(1)语法分析器源程序


#define   MAXANAL   50  /*最大输入串*/
#define   OK          1
#define   OVERFLOW    -1
#define   ERROR       0
#define   VT          1    /*终结符号1*/
#define   VN         2   /*非终结符号2*/
#define   Ee          U
#define   Tt          V
#include  "string.h"
#include  "stdio.h"
#include "conio.h"
int  line=0;  /*line为要写的行号，全局变量*/
int writeok;
int analysok=1;
int ip=0;
char w[MAXANAL];
char wel[30] = {"Welcome To Use An Wenzheng System"};
char ente[30]={"Press Any Key To Enter"};
char right[40]={"Copyright (c) 2002"};
#define maxsize 100
typedef struct
{char data[maxsize];
 int top;
 }stack;

int emptystack(stack *S)
{if(S->top==0&&S->data[S->top]=='#')return(1);
 else return(0);
}

int push(stack *S,char x)
{if(S->top>=maxsize-1)return(-1);
else{S->top++;
     S->data[S->top]=x;
     return(0);
    }
}
char gettop(stack *S)
{return S->data[S->top];

}
char pop(stack *S)
{if(emptystack(S))printf("the stack is empty\n");
 else S->top--;
return S->data[S->top+1];
 }

void initstack(stack *S)
{S->top=0;S->data[S->top]='#';}
/*文法分析表M*/
void printstack(stack *S)
{int to;
to=0;
while(to<=S->top)
{printf("%c",S->data[to++]);}
}
int sentence(stack *S,char x,char a)    /*返回分析表的位置*/
{int vt,vn,pos;
switch(x){
         case 'E':vn=0;break;
         case 'U':vn=1;break;
         case 'T':vn=2;break;
         case 'V':vn=3;break;
         case 'F':vn=4;break;
         default:{printf("\n 未发现非终结符 \'%c\' !!\n",x);
                  analysok=0;}
         }
switch(a){
         case 'i':vt=0;break;
         case '+':vt=1;break;
         case '*':vt=2;break;
         case '(':vt=3;break;
         case ')':vt=4;break;
         case '#':vt=5;break;
  default:{printf("\n 未发现终结符 \'%c\' !!\n",a);
                 analysok=0;}
        }
pos=vn*10+vt;
switch(pos){
case 0:
case 3:line++;
     write(line,S,"E->TE'");
     return 3;
case 11:
     line++;
     write(line,S,"E->+TE'");
     return 11;
case 14:
case 15:
     line++;
     write(line,S,"E'->$");
     pop(S);
     return 1415;
case 20:
case 23:
     line++;
     write(line,S,"T->FT'");
     return 2023;
case 31:
case 34:
case 35:
     line++;
     write(line,S,"T'->$");
     pop(S);
     return 333;
case 32:
     line++;
     write(line,S,"T'->*FT'");
     return 32;
case 40:
     line++;
     write(line,S,"F->i");
     return 40;
case 43:
     line++;
     write(line,S,"F->(E)");
     return 43;
default:
     {printf("\n 终结符 \'%c\' 不是非终结符 \'%c\' 所期望的 \n",a,x);
      analysok=0;
      return 0;
     }
  }
}
write(int step,stack *S,char *sentenc)
{int i;

if(step%20==0)
{gotoxy(1,23);printf("\n本页显示已满，按任意键继续......");
getche();clrscr();
printf("步骤\t符号栈\t\t输入串\t\t\t   所用产生式");
}
gotoxy(1,line%20+1);
printf("\n%02d \t",step);
/*printf(" 符号栈: ");*/
gotoxy(10,line%20+2);
printstack(S);
/*printf(" 输入串: ");*/
gotoxy(24,line%20+2);
for(i=ip;i<strlen(w);i++)
printf("%c",w[i]);
/*printf(" 用产生式:");*/
gotoxy(55,line%20+2);
printf("%s ",sentenc);
/*fclose(fp);*/
return OK;
}
int analy(char x)
{switch(x)
{case '#':return 3;
case 'E':
case 'V':
case 'F':
case 'U':
case 'T': return VN;
case 'i':
case '(':
case ')':
case '+':
case '*':return VT;
default:
 {printf("\n ERROR IN Function analy(x)!!!");
  return ERROR;}
}
}

welcome()
       {
       textbackground(CYAN);
       textcolor(BLUE);
       gotoxy(33,8);
       printf("LLi词法分析器\n");
       gotoxy(35,13);
       printf("vision 1.0\n");
       gotoxy(31,15);
       printf("指导老师：张绍兰\n");
       gotoxy(28,17);
       printf("设计者    安文政     \n");
       delay(9000000);
}
error()
{printf("error()");
}
/********模拟打字机的效果***/
delay_fun()
{
   int i;
   void music();  
   for(i=0;;i++)
   {
      if(wel[i]!='\0')
      {
         delay(1000);
         textcolor(YELLOW);
         gotoxy(26+i,8);
  cprintf("%c",wel[i]);
          music(1,60); 
      }
      else
         break;
   }
   delay(500000);
   for(i=0; ; i++)
   {
      if(ente[i]!='\0')
      {
          delay(1000);
          textcolor(YELLOW);
          gotoxy(29+i,11);
   cprintf("%c",ente[i]);
          music(1,60); 
      }
      else
         break;
   }
   delay(40000);
   for(i=0;;i++)
   {
      if(right[i] != '\0')
      {
         delay(1000);
         textcolor(YELLOW);
         gotoxy(30+i,14);
         cprintf("%c",right[i]);
        music(1,60);
      }
      else
         break;
   }
   getch();
}

logined()
{  int i;
   clrscr();
   gotoxy(28,10);
   textcolor(YELLOW);
   cprintf("程序正在载入请稍候.....");
   gotoxy(35,12);
   for(i=0;i<=50;i++)
   {
      gotoxy(40,12);
      delay(8000);
      cprintf("%02d%已完成",i*2);
      gotoxy(i+15,13);
      cprintf("\n");
   cprintf("|");
   }
   main0();
}
/***对PC扬声器操作的函数*******/
void music(int loop,int f)  
/* f为频率*/
{  int i;
for(i=0;i<30*loop;i++)
{
sound(f*20);
delay(200);}
nosound();
}

/* #define   VT 1 //终结符号1   */
/* #define VN 2  //非终结符号2  */
main0()
{char x,a,filename[15]; int len;
int kindx,kinds,flag=1,readerr=0;
 stack *st;
FILE *fl;
initstack(st);
textbackground(BLUE);
textcolor(YELLOW);
clrscr();
welcome();
delay(9000000);
clrscr();
textcolor(YELLOW);
cprintf("Please input analyse string:\n");
gets(w);
len=strlen(w);
  w[len]='#';
  w[len+1]='\0';
clrscr();
printf("\n步骤\t符号栈\t\t输入串\t\t\t   所用产生式");
push(st,'E');
do{
  x=gettop(st);
  a=w[ip];
  kindx=analy(x);
  if(kindx==VT)
   {if(x==a)             /*two final char  //2终结符号 */
     {x=pop(st);
     a=w[ip++];
     line++;
     write(line,st," ");}
   else {flag=0;analysok=0;}
   }
   else if(kindx==3)   /* '#'*/
    {if(x==a)
    { flag=0;
     line++;
    write(line,st," ");}
     else{flag=0;analysok=0;}
    }
else if(kindx==VN)
{kinds=sentence(st,x,a);
 switch(kinds)
  {case 0:analysok=0;
          flag=0;
          break;
   case 3:pop(st);
          push(st,'U');
          push(st,'T');
          break;
   case 11:pop(st);
 
          push(st,'U');
          push(st,'T');
          push(st,'+');
          break;
   case 2023:pop(st);
           push(st,'V');
          push(st,'F');
          break;
   case 32:pop(st);
          push(st,'V');
          push(st,'F');
          push(st,'*');
          break;
   case 40:pop(st);
   push(st,'i');
          break;
   case 43:pop(st);
   push(st,')');
          push(st,'E');
          push(st,'(');
          break;
   case 1415:
   case 333: break;     
/*E'->$  ,  T'->$ 不用入栈*/
   default:{analysok=0;flag=0;}
  }  /*switch */
}
}while(flag==1);
if(analysok==1)printf("\n分析完毕, %s 符合语法 right!!!!",w);
else if(analysok==0)printf("\n分析完毕, %s 不符合语法 wrong!!!!",w);
}
main()
{clrscr();
/*setbkcolor(7);*/
delay_fun();
logined();}