program30.cpp

根据相应的LL(1)分析表对所给算数表达式进行LL(1)分析

// program30.cpp : Defines the entry point for the console application.
//
/* 程序名称： LL(1)文法分析程序 */
/*G[E]:
        E→TE′
        E′→ATE′|ε
        T→FT′
        T′→MFT′|ε
        F→ (E)|i
        A→+|-
        M→*|/
*/
/*二维数组表示LL(1)分析表
行 E-0   E′-1   T-2   T′-3   F-4    A-5    M-6
列 i-0   +-1     --2    *-3    /-4    (-5    )-6    #-7
E′T′为了表示方便分别用C,B 代替
int table[7][8]={
	{1,0,0,0,0,1,0,0},
	{0,1,1,0,0,0,1,1},
	{1,0,0,0,0,1,0,0},
	{0,1,1,1,1,0,1,1},
	{1,0,0,0,0,1,0,0},
	{0,1,1,0,0,0,0,0},
	{0,0,0,1,1,0,0,0}
}
*/

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"

char token[100],in[200];
int n=0;
int i=0;
int flag;
FILE *fp;

void turn()
{
	char ch;
	ch =fgetc(fp);
	while(ch != EOF)
	{
		switch(ch)
		{
		case'\n':break;
		case' ':break;
		case'\0':break;
		default:in[i]=ch;i++;break;
		}
		ch =fgetc(fp);
	}
	in[i]='\0';
	printf("____________输入串为___________\n");
	printf("            ");
	for(i=0;in[i]!='\0';i++)
	{
		if((in[i]=='2' )&& (in[i+1]=='9'))  flag=i+5;
	}
	for(i=flag;in[i]!=';';i++)
	{
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='1'))  {token[n]='+';n++;}
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='2'))  {token[n]='-';n++;}
        if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='3'))  {token[n]='*';n++;}
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='5'))  {token[n]='(';n++;}
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='6'))  {token[n]=')';n++;}
        if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='0'))  {token[n]='/';n++;}
        if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='7'))  {token[n]='i';n++;}
		if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='8'))  {token[n]='i';n++;}
	}
 	token[n]='#';
    for(i=0;i<=n;i++)
	{
		printf("%c",token[i]);
	}
	printf("\n");
	printf("_______________________________\n");
//	printf("\n");
}

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

struct Lchar{
	char char_ch;
	struct Lchar *next;
}Lchar,*p,*h,*temp,*top,*base;
char curchar;//输入串字符
char curtocmp;//分析栈字符
int right;
int j;

/*********二维数组表示LL(1)分析表********/
int table[7][8]={
	{1,0,0,0,0,1,0,0},
	{0,1,1,0,0,0,1,1},
	{1,0,0,0,0,1,0,0},
	{0,1,1,1,1,0,1,1},
	{1,0,0,0,0,1,0,0},
	{0,1,1,0,0,0,0,0},
	{0,0,0,1,1,0,0,0},
};

void push(char ch)//模拟进栈，链表尾部为栈底元素
{
	temp=(struct Lchar *)malloc(sizeof(Lchar));
	temp->char_ch=ch;
    temp->next=top;
    top=temp;
}

void pop()//模拟出栈
{
    if(top->char_ch!='#')
    top=top->next;
}

void doforpush(int t)//将满足的产生式右部反序进栈
{
	switch(t)
	{
	case 0: push('C');push('T');break;
    case 5: push('C');push('T');break;
	case 11:push('C');push('T');push('A');break;
    case 12:push('C');push('T');push('A');break;
    case 20:push('B');push('F');break;
    case 25:push('B');push('F');break;
    case 33:push('B');push('F');push('M');break;
    case 34:push('B');push('F');push('M');break;
    case 40:push('i');break;
    case 45:push(')');push('E');push('(');break;
	case 51:push('+');break;
	case 52:push('-');break;
	case 63:push('*');break;
	case 64:push('/');break;
	default:break;
	}
}

void changchartoint()//判断满足的产生式并标记
{
	switch(curtocmp)
	{
	case 'E':i=0;break;
    case 'C':i=1;break;
    case 'T':i=2;break;
	case 'B':i=3;break;
    case 'F':i=4;break;
    case 'A':i=5;break;
	case 'M':i=6;break;
	default:break;
	}
	switch(curchar)
	{
	case 'i':j=0;break;
    case '+':j=1;break;
    case '-':j=2;break;
    case '*':j=3;break;
    case '/':j=4;break;
    case '(':j=5;break;
    case ')':j=6;break;
    case '#':j=7;break;
	default:break;
	}
}

void dosome()
{
	int t;
    for(;;)
	{
		temp=top;
		n=0;
		for(;;)//打印分析栈中字符
		{  
			in[n]=temp->char_ch;n++;
			if(temp->char_ch=='#')  
				break;  
			else  
				temp=temp->next;  
		}  
		for(i=n-1;i>=0;i--)
		{
			printf("%c",in[i]);
		}
		printf("\t");  
		temp=h;  
		for(;;)//打印输入串中剩余字符  
		{  
			printf("%c",temp->char_ch);  

			if(temp->char_ch=='#')  
				break;  
			else  
				temp=temp->next;  
		}
		printf("\n");
		curtocmp=top->char_ch;
		pop();
		curchar=h->char_ch;
		if(curtocmp=='#' && curchar=='#')
		break;	
	    if(curtocmp=='A'||curtocmp=='B'||curtocmp=='C'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F'||curtocmp=='M')
		{
			changchartoint();
			if(table[i][j])
			{
				t=10*i+j;
              	doforpush(t);
            	continue;//跳到外层的for(';;)
			}
			else 
			{
				right=0;
				printf("%c\t%c\tERROR1!\n----没有对应的产生式",curtocmp,curchar);//没有对应的产生式
				break;	
			}			
		}
		else 
			if(curtocmp!=curchar)  
			{
				right=0;printf("%c\t%c\tERROR2\n----分析栈到底而输入串未分析完!",curtocmp,curchar); //分析栈到底而输入串未分析完
				break;
			}
	    	else
			{
				h=h->next;
				continue;
			}
	}
}

void scanner()
{
	char ch;
	right=1;
	base= (struct Lchar *)malloc(sizeof(Lchar));
	base->next=NULL;
	base->char_ch='#';
	temp= (struct Lchar *)malloc(sizeof(Lchar));
	temp->next=base;
	temp->char_ch='E';
	top=temp;
	h=(struct Lchar *)malloc(sizeof(Lchar));
	h->next=NULL;
	p=h;
	for(i=0;i<=n;i++)
	{
		ch=token[i];
        if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
		{
			temp=(struct Lchar *)malloc(sizeof(Lchar));
            temp->next=NULL;
            temp->char_ch=ch;
            h->next=temp;
            h=h->next;
		}
		else
		{
			temp=p->next;
			printf("输入串错误!\n");
		}
	}
	p=p->next;
	h=p;
	dosome();
	if(right)   printf("\n此输入串是该文法定义的算术表达式!\n");
	else	printf("\n此输入串不是该文法定义的算术表达式!\n");
}

int main(int argc, char* argv[])
{
	fp=fopen("test.txt", "r");
	turn();
	scanner();
	return 0;
}