bliplink博客: 编译原理

显示标签为“编译原理”的博文。显示所有博文

c语言词法分析器

/*程序全部在TC2.o下跳过的，在其它的编译器下可能调不过。这是因为有些非标准的函数，其它的编译器并没有*/

#include <stdio.h>

#include <string.h>

#include <conio.h> /*屏幕操作函数*/

#include <bios.h>

#define Num 256/*缓冲区大小，当分析Mb大小的文件时候，可以让缓冲区设置到大一些，可以缩短分析的时间，提高整体的效率*/

char q1[Num],temp1[Num],token[Num];

char *pp,*qq;/*两个缓冲区的指针 */

char ch;

int syn,p;

int tabflag=1,spaceflag=1,enterflag=1;/*预处理标识符 */

int count=0,flag2=1;/*count记录分析出的结果总数，flag2结束分析的标志，当为0时即由@出现时候分析结束*/

long ft=0;/*记录读到的文件位置 */

char *rwtab[]={"auto","break","case","char","const","continue","default","do","double",

"else","enum","extern","float","for","goto","if","int","long","register",

"return","short","signed","sizeof","static","struct","switch","typedef",

"union","unsigned","void","volatile","while"};/*33个关键字*/

char *limit[]={"(",")","[","]","}","{","<",">","!","*","/",

"+","-","=","&","->",".","|","#","%","~",",",";","<<","<=",

">>",">=","!=","*=","/=","+=","++","-=","-","==","&&","||","^"};/*运算、限界符38*/

/*功能：清理缓冲区

para：q 缓冲区开始指针，n缓冲区大小 */

void cleanBuf(char *q,int n)

{

int i;

for(i=0;i<n;i++)

q[i]='\0';

}

/*帮助菜单界面1*/

void help1()

{

int i;

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

printf("-------Word symbols-------types of code-------Word symbols------types of code\n");

for(i=0;i<14;i++)

printf("||-------------%-8s|--------%2d|-----------------%2s-----------%2d|---------||\n",rwtab[i],i+1,limit[i],i+36);

/* for(i=0;i<6;i=i+2)

printf("||-------------%-8s|--------%2d|-----------------%2s-----------%2d|---------||\n",limit[i+32],i+68,limit[i+33],i+69);

gotoxy(1,22);

printf("--------------------------------------------------------------------------------");

gotoxy(35,23);

printf("up Next");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textbackground(2);

gotoxy(5,5);

cprintf("A");

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

textcolor(RED);

gotoxy(69,5);

cprintf("H");

}

/*帮助菜单界面2*/

void help2()

{

int i;

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

printf("-------Word symbols-------types of code-------Word symbols------types of code\n");

for(i=14;i<28;i++)

printf("||-------------%-8s|--------%2d|-----------------%2s-----------%2d|---------||\n",rwtab[i],i+1,limit[i],i+36);

/* for(i=0;i<6;i=i+2)

printf("||-------------%-8s|--------%2d|-----------------%2s-----------%2d|---------||\n",limit[i+32],i+68,limit[i+33],i+69);

gotoxy(1,22);

printf("--------------------------------------------------------------------------------");

gotoxy(35,23);

printf("up Next");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textbackground(2);

gotoxy(5,5);

cprintf("A");

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

textcolor(RED);

gotoxy(69,5);

cprintf("H");

}

/*帮助菜单界面3*/

void help3()

{

int i;

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

printf("-------Word symbols-------types of code-------Word symbols------types of code\n");

for(i=28;i<33;i++)

printf("||-------------%-8s|--------%2d|-----------------%2s-----------%2d|---------||\n",rwtab[i],i+1,limit[i],i+36);

printf("||-------------Identifier|------34|------------Digital-----------35|---------||\n");

for(i=0;i<6;i=i+2)

printf("||-------------%-8s|--------%2d|-----------------%2s-----------%2d|---------||\n",limit[i+32],i+68,limit[i+33],i+69);

gotoxy(1,22);

printf("--------------------------------------------------------------------------------");

gotoxy(35,23);

printf("up Next");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textbackground(2);

gotoxy(5,5);

cprintf("A");

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

textcolor(RED);

gotoxy(69,5);

cprintf("H");

}

/*主菜单界面*/

void menu()

{

textcolor(YELLOW);

textbackground(2);

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

gotoxy(5,5);

cprintf("A");

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

gotoxy(69,5);

cprintf("H");

}

/*输入文件地址界面（开始分析程序界面)*/

void Readmenu(char *fileAddress)

{

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

printf("Please input your address to open the file:\n");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textcolor(RED);

textbackground(2);

gotoxy(5,5);

cprintf("A");

textcolor(YELLOW);

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

gotoxy(69,5);

cprintf("H");

gotoxy(1,8);

scanf("%s",fileAddress);

}

/*词法分析器开始分析等待界面*/

void resultWait()

{

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

gotoxy(35,14);

textcolor(7);

cprintf("Please wait......\n");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textcolor(RED);

textbackground(2);

gotoxy(5,5);

cprintf("A");

textcolor(YELLOW);

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

gotoxy(69,5);

cprintf("H");

}

/*分析完成界面*/

void resultFinish()

{

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

gotoxy(30,14);

textcolor(7);

cprintf("Analysis has been completed\n");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textcolor(RED);

textbackground(2);

gotoxy(5,5);

cprintf("A");

textcolor(YELLOW);

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

gotoxy(69,5);

cprintf("H");

}

/*打开文件失败界面*/

void OpenError()

{

printf("--------------------------------------------------------------------------------\n");

printf(" C Lexical analyzer\n");

printf("--------------------------------------------------------------------------------");

printf(" 1.Analysis of the beginning || 2.Results || 3.Set up || 4.Quit || 5.Help\n");

printf("--------------------------------------------------------------------------------");

gotoxy(35,14);

textcolor(7);

cprintf("Failure to open files\n");

gotoxy(1,24);

printf("--------------------------------------------------------------------------------");

gotoxy(1,25);

textcolor(YELLOW);

textcolor(RED);

textbackground(2);

gotoxy(5,5);

cprintf("A");

textcolor(YELLOW);

gotoxy(34,5);

cprintf("R");

gotoxy(47,5);

cprintf("S");

gotoxy(59,5);

cprintf("Q");

gotoxy(69,5);

cprintf("H");

}

/*功能：分析字符词法分析器核心程序最终以@字符结束整个分析

para: q第一缓冲区开始指针的指针，n 缓冲区大小，p当前指针所在缓冲区位置，temp第二缓冲区开始指针的指针，fileAddress打开文件的地址*/

void scaner(char **q,int n,int *p,char **temp,char *fileAddress)

{

int i=0,j=0,m=0,h;

char *t;

for(i=0;i<Num;i++)

token[i]='\0';

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

while(ch==' ')

{

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

}

if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||ch=='_')

{

while((ch>='0'&&ch<='9')||(ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||ch=='_')

{

token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

}

token[m++]='\0';

(*p)--;

syn=34;/*34为标示符

//1-33为c语言关键字 */

for(j=0;j<32;j++)

if(strcmp(token,rwtab[j])==0)

{

syn=j+1;

break;

}

else

if((ch>='0'&&ch<='9'))

{

while((ch>='0'&&ch<='9'))

{

token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

}

(*p)--;

syn=35;/*为数字 */

}

else

switch(ch)

{

case'<':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='<')

{

syn=59;

token[m++]=ch;

}

else

if(ch=='=')

{

syn=60;

token[m++]=ch;

}

else

{

syn=42;(*p)--;

}

break;

case'>':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='>')

{

syn=61;

token[m++]=ch;

}

else if(ch=='=')

{

syn=62;

token[m++]=ch;

}

else

{

syn=43;

(*p)--;

}

break;

case'!':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='=')

{

syn=63;

token[m++]=ch;

}

else

{

syn=44;

(*p)--;

}

break;

case'*':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='=')

{

syn=64;

token[m++]=ch;

}

else

{

syn=45;

(*p)--;

}

break;

case'/':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='=')

{

syn=65;

token[m++]=ch;

}

else

{

syn=46;

(*p)--;

}

break;

case'+':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='=')

{

syn=66;

token[m++]=ch;

}

else if(ch=='+')

{

syn=67;

token[m++]=ch;

}

else

{

syn=47;

(*p)--;

}

break;

case'-':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='=')

{

syn=68;

token[m++]=ch;

}

else if(ch=='-')

{

syn=69;

token[m++]=ch;

}

else if(ch=='>')

{

syn=51;

token[m++]=ch;

}

else

{

syn=48;

(*p)--;

}

break;

case'=':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='=')

{

syn=70;

token[m++]=ch;

}

else

{

syn=49;

(*p)--;

}

break;

case'|':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='|')

{

syn=72;

token[m++]=ch;

}

else

{

syn=53;

(*p)--;

}

break;

case'&':token[m++]=ch;

if(*p>=n)

{

t=*q;

*q=*temp;

*temp=t;

*p=0;

cleanBuf(*temp,Num);

h=readqramm(*temp,Num,fileAddress );

if(h==-1) {system("cls");OpenError();}

}

ch=(*q)[(*p)++];

if(ch=='*')

{

syn=71;

token[m++]=ch;

}

else

{

syn=50;

(*p)--;

}

break;

case'.':syn=52;token[0]=ch;break;

case'\'':syn=54;token[0]=ch;break;

case'%':syn=55;token[0]=ch;break;

case'~':syn=56;token[0]=ch;break;

case'^':syn=73;token[0]=ch;break;

case':':syn=74;token[0]=ch;break;

case',':syn=57;token[0]=ch;break;

case';':syn=58;token[0]=ch;break;

case'{':syn=41;token[0]=ch;break;

case'}':syn=40;token[0]=ch;break;

case'[':syn=39;token[0]=ch;break;

case']':syn=38;token[0]=ch;break;

case'(':syn=36;token[0]=ch;break;

case')':syn=37;token[0]=ch;break;

case'#':syn=59;token[0]=ch;break;

case'@':flag2=0;break;

default:syn=-1;token[0]=ch;break;

}

/*功能：从磁盘中读去程序内容

para:q 缓冲区指针，n缓冲区大小，fileAddress 读文件的地址（c:\2.txt)

return: 返回1 文件中还有可读字符 0文件没有可读字符 -1 打开文件失败 */

int readqramm(char *q,int n,char *fileAddress)

{

FILE *fp;

char ch;

int p=0;

if((fp=fopen(fileAddress,"r"))==NULL)

{

return -1;

}

fseek(fp,ft,0);

ch=fgetc(fp);

while(ch!=EOF&&n>p)

{

if(ch==' '&&spaceflag==1)

{

q[p++]=ch;

spaceflag=0;

}

if(ch=='\t'&&tabflag==1)

{

if(q[p-1]!=' ') q[p++]=' ';

tabflag=0;

}

if(ch!=' '&&ch!='\t'&&ch!='\r'&&ch!='\n')

{

q[p++]=ch;

spaceflag=1;

tabflag=1;

}

ch=fgetc(fp);

}

ft=ftell(fp)-1;

fclose(fp);

if(ch==EOF) return 0;

else return 1;

}

int main()

{

char fileAddress[Num];

char ch;

int flag1=1;

FILE *fp;

int jj=0,help_count=0,key;

pp=q1;

qq=temp1;

system("cls");

menu();

while(flag1)

{

key=bioskey(0);

switch(key)

{

case 7777:

case 7745:system("cls");

Readmenu(fileAddress);

flag2=1;

if(fileAddress!=NULL)

{

system("cls");

resultWait();

if(readqramm(qq,Num,fileAddress )==-1||readqramm(pp,Num,fileAddress )==-1) {system("cls");OpenError();}

else

{

scaner(&qq,Num,&p,&pp,fileAddress);

if(jj==0)

{

jj++;

if((fp=fopen("result.txt","w"))==NULL)

{

system("cls");OpenError();

}

else

{

jj++;

if((fp=fopen("result.txt","a"))==NULL)

{

system("cls");OpenError();

}

switch(syn)

{

case -1:fprintf(fp,"%d. (%d,%s) ",++count,syn,token);fclose(fp);continue;/*写入到result.txt文件中，这里最好使用缓冲区可以提高程序的效率，频繁打开文件写，效率低*/

default:fprintf(fp,"%d. (%d,%s) ",++count,syn,token);fclose(fp);continue;/*做法先让这些分析结果写到缓冲区中等缓冲满了，在一次写入到文件中，读取文件就使用了双缓冲效果很好*/

}

}while(flag2);

}

if(flag2==0)

{

system("cls");

resultFinish();

}

break;

case 4978:

case 4946:break;

case 8051:

case 8019:break;

case 4209:

case 4177:flag1=0;break;

case 9064:

case 9032:help_count=0;system("cls");help1();

while((key=bioskey(0))!=283)

{

switch(key)

{

case 20480:if(help_count==0) {system("cls");help2();help_count++;}

else if(help_count==1) {system("cls");help3();help_count++;}

break;

case 18432:if(help_count==2) {system("cls");help2();help_count--;}

else if(help_count==1) {system("cls");help1();help_count--;}

break;

}

system("cls");

menu();

break;

}

......

[阅读全文]

LL(1)源码

LL(1)预测分析表

一．测试文法：（放在文件chanshengshi.txt中）

E->TA

A->+TA

A->~

T->FB

B->*FB

B->~

F->(E)

F->i

二．输出（在analysis_table.txt中）

产生式：

0:E->TA

1:A->+TA

2:A->~

3:T->FB

4:B->*FB

5:B->~

6:F->(E)

7:F->i

--------------------------------------------

first follow

E (i #)

A ~+ #)

T (i +#)

B ~* +#)

F (i *+#)

--------------------------------------------

预测分析表如下：

+ * ( ) i #

E ERROR ERROR 0 ERROR 0 ERROR

A 1 ERROR ERROR 2 ERROR 2

T ERROR ERROR 3 ERROR 3 ERROR

B 5 4 ERROR 5 ERROR 5

F ERROR ERROR 6 ERROR 7 ERROR

三．源码

LL(1)预测分析表的构造，空字用符号~表示

This procedure is written by fanxiangchao.

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<ctype.h>

#include<malloc.h>

#define FALSE 0

#define TRUE 1

#define MAX 100

#define NULL 0

#define ERROR -1

/***********************定义结构体*********************************/

//1.定义非终结符的结构体

struct no_terminal_sign

{

char no_ter; //非终结符

char first[MAX]; //非终结符的first集合

char follow[MAX]; //非终结符的follow集合

};

//2.定义候选式的结构体

struct candidate_formular

{

char candidate[MAX]; //候选式串

char first[MAX]; //候选式的first集合

};

//3.定义产生式的结构体

typedef struct produce

{

char left; //产生式左部

char right[MAX]; //产生式右部

}chanshengshi;

//4.定义终结符的结构体

struct terminal_sign

{

char ter; //终结符

char first[MAX]; //终结符的first集合

};

/******************************************************************/

//函数定义

int is_include(char * a,char b)//一个终结符属于某个集合

{

int i;

for(i=0;a[i]!='\0';i++)

if(b==a[i])

return TRUE;

return FALSE;

}

void add_ter(char * a,char sign)//向一个集合中添加一个终结符

{

int length;

if(!is_include(a,sign)){

length=strlen(a);

a[length]=sign;

a[length+1]='\0';

}

void add_ter_to_first(struct no_terminal_sign * a,char sign)//向一个终结符的first集合中添加一个终结符

{

int length;

if(!is_include(a->first,sign)){

length=strlen(a->first);

a->first[length]=sign;

a->first[length+1]='\0';

}

void add_ter_to_candidate_first(struct candidate_formular * a,char sign)//向一个候选式的first集合中添加一个终结符

{

int length;

if(!is_include(a->first,sign)){

length=strlen(a->first);

a->first[length]=sign;

a->first[length+1]='\0';

}

void add_ter_to_follow(struct no_terminal_sign * a,char sign)//向一个终结符的follow集合中添加一个终结符

{

int length;

if(!is_include(a->follow,sign)){

length=strlen(a->follow);

a->follow[length]=sign;

a->follow[length+1]='\0';

}

int is_terminal(char sign,struct terminal_sign *a)//判断一个符号是终结符还是非终结符

{

struct terminal_sign * p;

if(sign=='~') return -1;

for(p=a;p->ter!=NULL;p++)

if(p->ter==sign)

return TRUE;

return FALSE;

}

int is_include_null(struct no_terminal_sign *a)//判断一个非终结符的first集合中包含空字

{

int i;

for(i=0;a->first[i]!='\0';i++)

if(a->first[i]=='~')

return TRUE;

return FALSE;

}

void subtract_null(char *a)//将一个集合减去空字

{

int i,mark;

for(i=0;a[i]!='\0';i++)

if(a[i]=='~')

break;

mark=i;

for(i=mark;i<(signed)strlen(a);i++)

a[i]=a[i+1];

}

void merge_to_first(struct no_terminal_sign * a,char *b)//将集合b添加到非终结符的first集合a中

{

int i,n;

n=strlen(a->first);

for(i=0;b[i]!='\0';i++)

if(!is_include(a->first,b[i]))

a->first[n++]=b[i];

a->first[n]='\0';

}

void merge_to_candidate_first(struct candidate_formular * a,char *b)//将集合b添加到候选式的first集合a中

{

int i,n;

n=strlen(a->first);

for(i=0;b[i]!='\0';i++)

if(!is_include(a->first,b[i]))

a->first[n++]=b[i];

a->first[n]='\0';

}

void merge_to_follow(struct no_terminal_sign * a,char *b)//将集合b添加到非终结符的first集合a中

{

int i,n;

n=strlen(a->follow);

for(i=0;b[i]!='\0';i++)

if(!is_include(a->follow,b[i]))

a->follow[n++]=b[i];

a->follow[n]='\0';

}

struct no_terminal_sign * search_by_sign(char sign,struct no_terminal_sign *a)//根据一个非终结符找到对应的结构体

{

struct no_terminal_sign *p;

for(p=a;p->no_ter!=NULL;p++)

if(p->no_ter==sign)

return p;

return NULL;

}

int sum_first(struct no_terminal_sign * a)//所有first集合元素的和

{

int sum=0;

struct no_terminal_sign * p;

for(p=a;p->no_ter!=NULL;p++)

sum+=strlen(p->first);

return sum;

}

int sum_follow(struct no_terminal_sign * a)//所有follow集合元素的和

{

int sum=0;

struct no_terminal_sign * p;

for(p=a;p->no_ter!=NULL;p++)

sum+=strlen(p->follow);

return sum;

}

struct candidate_formular * search_by_string(char * a,struct candidate_formular *b)//根据产生式右部找到候选式的结构体

{

struct candidate_formular *p;

for(p=b;p->candidate!=NULL;p++)

if(strcmp(p->candidate,a)==0)

return p;

return NULL;

}

int total_ter(struct terminal_sign *a)//终结符的个数

{

struct terminal_sign *p;

int n=0;

for(p=a;p->ter!=NULL;p++)

n++;

return n;

}

int total_no_ter(struct no_terminal_sign *a)//非终结符的个数

{

struct no_terminal_sign *p;

int n=0;

for(p=a;p->no_ter!=NULL;p++)

n++;

return n;

}

//1.非终结符first集合的构造

void no_ter_first_create(chanshengshi *formular,struct no_terminal_sign * no_terminal,struct terminal_sign * terminal)

{

chanshengshi * p;

int n,i;

struct no_terminal_sign *q;

char temp[MAX]=""; //临时数组变量

for(p=formular;p->left!=NULL;p++)

{

n=0;

q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体

if(strcmp(p->right,"~")==0)//如果产生式右部为空字

continue;

struct no_terminal_sign *r;

for(i=0;p->right[i]!='\0';i++)

{

if(!is_terminal(p->right[i],terminal))

{

r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体

if(is_include_null(r))

n++;

else break;

}

else break;

}

for(i=0;i<n;i++)

{

r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体

strcpy(temp,""); //临时数组变量赋空串

strcpy(temp,r->first);

subtract_null(temp); //减空字

merge_to_first(q,temp);//将所有非空元素加入左部非终结符的first

}

if(n>=(signed)strlen(p->right))

{

add_ter_to_first(q,'~');

}

else

{

if(is_terminal(p->right[n],terminal))

add_ter_to_first(q,p->right[n]);

else{

r=search_by_sign(p->right[n],no_terminal);//根据非终结符找到对应的非终结符结构体

merge_to_first(q,r->first);//将所有元素加入左部非终结符的first(已确定不含空字)

}

//2.候选式first集合的构造

void candidate_first_create(chanshengshi *formular,struct no_terminal_sign * no_terminal,struct terminal_sign * terminal,struct candidate_formular *candi)

{

int n=0,i;

char temp[MAX]; //临时数组变量

chanshengshi *p;

struct candidate_formular *q;

struct no_terminal_sign *r;

for(p=formular;p->left!=NULL;p++){

q=search_by_string(p->right,candi);

for(i=0;i<p->right[i]!='\0';i++){

if(!is_terminal(p->right[i],terminal)){

r=search_by_sign(p->right[i],no_terminal);

if(is_include_null(r))

n++;

else

break;

}else

break;

}

for(i=0;i<n;i++){

r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体

strcpy(temp,""); //临时数组变量

strcpy(temp,r->first);

subtract_null(temp); //减空字

merge_to_candidate_first(q,temp);//将所有非空元素加入到候选式的first

}

if(n>=(signed)strlen(p->right)){

add_ter_to_candidate_first(q,'~');

}else{

if(is_terminal(p->right[n],terminal))

add_ter_to_candidate_first(q,p->right[n]);

else{

r=search_by_sign(p->right[i],no_terminal);//根据非终结符找到对应的非终结符结构体

merge_to_candidate_first(q,r->first);//将所有非空元素加入左部非终结符的first

}

//3.非终结符follow集合的构造

void no_ter_follow_create(chanshengshi *formular,struct no_terminal_sign * no_terminal,struct terminal_sign * terminal,struct candidate_formular *candi)

{

struct no_terminal_sign *q,*r,*s;

chanshengshi *p;

int i;

char temp[MAX];

for(p=formular;p->left!=NULL;p++)

{

q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体

for(i=0;i<(signed)strlen(p->right)-1;i++)

{

if(!is_terminal(p->right[i],terminal))

{

//根据非终结符找到对应的非终结符结构体r，即当前需要求follow集合的非终结符

r=search_by_sign(p->right[i],no_terminal);

int n=i+1;//记录当前非终结符的标号

for(int j=i+1;j<(signed)strlen(p->right);j++){

if(!is_terminal(p->right[j],terminal)){

s=search_by_sign(p->right[j],no_terminal);

if(is_include_null(s))

n++;

else

break;

}else

break;

}

for(j=i+1;j<n;j++){

s=search_by_sign(p->right[j],no_terminal);//根据非终结符找到对应的非终结符结构体

strcpy(temp,""); //临时数组变量

strcpy(temp,s->first);

subtract_null(temp); //减空字

merge_to_follow(r,temp);//将所有非空元素加入当前非终结符的follow集合

}

//如果当前非终结符后面的符号都含空字，则将左部非终结符的follow加入到该终结符的follow集合

if(n>=(signed)strlen(p->right))

{

merge_to_follow(r,q->follow);

}else

{

if(is_terminal(p->right[n],terminal))

add_ter_to_follow(r,p->right[n]);

else{

s=search_by_sign(p->right[n],no_terminal);//根据非终结符找到对应的非终结符结构体

merge_to_follow(r,s->first);//将所有元素加入当前非终结符的follow

}

//如果右部的最后一个字符是非终结符，则将左部的follow加到该非终结符的follow

if(!is_terminal(p->right[i],terminal)){

r=search_by_sign(p->right[i],no_terminal);

merge_to_follow(r,q->follow);

}

/******************************************************************/

//主函数

void main()

{

//构造一个预测分析表，一个二维数组，行代表非终结符序号，列代表非结符序号

int analysis[MAX][MAX];

//定义非终结符集

struct no_terminal_sign no_terminal[MAX];

//定义终结符集

struct terminal_sign terminal[MAX];

//定义开始符号

char start_sign;

//定义产生式集合

chanshengshi formular[MAX];

struct candidate_formular candi[MAX];

chanshengshi *p;

int t1,t2,i,j;

/**********************************************************************/

//读取存放产生式的文件

FILE *in;

if((in=fopen("chanshengshi.txt","r"))==NULL){

printf("cannot open file!\n");

return;

}

char sign;

int no_ter_num=0,ter_num=0,chanshengshi_num=0,candidate_num=0;

char temp[MAX];

sign=fgetc(in);

start_sign=sign;//读取的第一个符号为开始符号

rewind(in); //文件指针重新回到文件头部

//产生式添加并赋初值

while (fscanf(in,"%s",temp)!=-1)

{

formular[chanshengshi_num].left=temp[0];

strcpy(formular[chanshengshi_num].right,temp+3);

chanshengshi_num++;

}

formular[chanshengshi_num].left=NULL;

strcpy(formular[chanshengshi_num].right,"");

//非终结符和终结符添加并赋初值

for(p=formular;p->left!=NULL;p++)

{

//1.将非终结符加入非终结符集并赋初值

for(i=0;i<no_ter_num;i++)

if(p->left==no_terminal[i].no_ter)

break;

if(i>=no_ter_num)

{

no_terminal[no_ter_num].no_ter=p->left;

strcpy(no_terminal[no_ter_num].first,"");

strcpy(no_terminal[no_ter_num].follow,"");

no_ter_num++;

}

//2.将终结符加入非终结符集

for(i=0;p->right[i]!='\0';i++)

if(!((p->right[i]<='Z' && p->right[i]>='A') || (p->right[i]=='~')))

{

for(j=0;j<ter_num;j++)

if(p->right[i]==terminal[j].ter)

break;

if(j>=ter_num){

terminal[ter_num].ter=p->right[i];

strcpy(terminal[ter_num].first,"");

//add_ter(terminal[ter_num].first,temp[i]);

ter_num++;

}

//3.将候选式加入候选式集并赋初值

for(i=0;i<candidate_num;i++)

if(strcmp(p->right,candi[i].candidate)==0)

break;

if(i>=candidate_num)

{

strcpy(candi[candidate_num].candidate,p->right);

strcpy(candi[candidate_num].first,"");

candidate_num++;

}

//各集合终结标志添加

no_terminal[no_ter_num].no_ter=NULL;

strcpy(no_terminal[no_ter_num].first,"");

strcpy(no_terminal[no_ter_num].follow,"");

formular[chanshengshi_num].left=NULL;

strcpy(formular[chanshengshi_num].right,"");

strcpy(candi[candidate_num].candidate,"");

strcpy(candi[candidate_num].first,"");

terminal[ter_num].ter='#';

strcpy(terminal[ter_num].first,"");

ter_num++;

terminal[ter_num].ter=NULL;

strcpy(terminal[ter_num].first,"");

fclose(in);

/**********************************************************************/

//first集合的构造

//1和2是处理空字问题，即先把空字写入每个所属first集合

//1

for(p=formular;p->left!=NULL;p++)

{

struct no_terminal_sign *q;

q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体

if(strcmp(p->right,"~")==0)//如果产生式右部为空字

add_ter_to_first(q,'~');//则将空字加入到左部非终结符的first

}

//2

for(p=formular;p->left!=NULL;p++)

{

struct no_terminal_sign *q,*r;

q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体

if(!is_terminal(p->right[0],terminal))

{

r=search_by_sign(p->right[0],no_terminal);

if(is_include_null(r))

add_ter_to_first(q,'~');

}

//3构造first集合，直至不在增加为止

while(1)

{

t1=sum_first(no_terminal);

no_ter_first_create(formular,no_terminal,terminal);

t2=sum_first(no_terminal);

if(t1>=t2) break;//first集合不再增大

}

//打印first集合

for(i=0;no_terminal[i].no_ter!=NULL;i++)

printf("%s\n",no_terminal[i].first);

printf("\n");

/********************************************************************/

//产生式候选式的first集合的构造

candidate_first_create(formular, no_terminal,terminal,candi);

//打印候选式的first集合

for(i=0;strcmp(candi[i].candidate,"")!=0;i++)

printf("%s\n",candi[i].first);

printf("\n");

/***********************************************************************/

//非终结符follow集合的构造

struct no_terminal_sign *a;

a=search_by_sign(start_sign,no_terminal);//开始符号的结构体

add_ter_to_follow(a,'#'); //把#添加到开始符号的follow集合中

while(1){

t1=sum_follow(no_terminal);

no_ter_follow_create(formular,no_terminal,terminal,candi);

t2=sum_follow(no_terminal);

if(t1>=t2)

break;

}

//打印终结符的follow集合

for(i=0;no_terminal[i].no_ter!=NULL;i++)

printf("%s\n",no_terminal[i].follow);

printf("\n");

/***************************************************************************/

//构造分析表

t1=total_ter(terminal); //终结符个数

t2=total_no_ter(no_terminal); //非终结符个数

printf("%d,%d\n",t1,t2);

//初始化预测分析表

for(i=0;i<t2;i++)

for(j=0;j<t1;j++)

analysis[i][j]=ERROR;

//构造

for(i=0;i<t2;i++){

struct no_terminal_sign *q;

struct candidate_formular *r;

int mark;

for(mark=0;formular[mark].left!=NULL;mark++){ //对每个产生式

q=search_by_sign(formular[mark].left,no_terminal); //由左部找到非终结符结构体

r=search_by_string(formular[mark].right,candi); //由右部找到候选式结构体

if(formular[mark].left==no_terminal[i].no_ter){

for(j=0;j<t1;j++){

if(is_include(r->first,terminal[j].ter)){

analysis[i][j]=mark;

}

if(is_include_null(q)){

for(j=0;j<t1;j++){

if(is_include(q->follow,terminal[j].ter)){

analysis[i][j]=mark;

}

//打印预测分析表

for(i=0;i<t2;i++)

{

for(j=0;j<t1;j++)

printf("%d\t",analysis[i][j]);

printf("\n");

}

/************************************************************************/

//将预测分析表保存到文件中

FILE *fp;

if((fp=fopen("analysis_table.txt","w"))==NULL){

printf("cannot open the file of analysis_table.txt !\n");

return;

}

fprintf(fp,"%s\n","产生式：");

for(i=0,p=formular;p->left!=NULL;p++,i++)

fprintf(fp,"%d%s%c%s%s\n",i,":",p->left,"->",p->right);

fprintf(fp,"%s\n","--------------------------------------------");

fprintf(fp,"%-10s\t%-10s\t%-10s\n","","first","follow");

for(i=0;no_terminal[i].no_ter!=NULL;i++){

fprintf(fp,"%-10c\t%-10s\t%-10s\n",no_terminal[i].no_ter,no_terminal[i].first,no_terminal[i].follow);

}

fprintf(fp,"%s\n","--------------------------------------------");

fprintf(fp,"%s\n","预测分析表如下：");

fprintf(fp,"%-10s","");

for(i=0;terminal[i].ter!=NULL;i++)

fprintf(fp,"%-10c",terminal[i].ter);

fprintf(fp,"\n");

for(i=0;i<t2;i++){

fprintf(fp,"%-10c",no_terminal[i]);

for(j=0;j<t1;j++){

if(analysis[i][j]==ERROR)

fprintf(fp,"%-10s","ERROR");

else

fprintf(fp,"%-10d",analysis[i][j]);

}

fprintf(fp,"\n");

}

fclose(fp);

}

......

[阅读全文]

订阅：博文 (Atom)

bliplink博客

c语言词法分析器

LL(1)源码

关注者

被浏览次数