編譯原理：實驗五 LL(1)文法識别程式設計

一、實驗目的

通過LL(1)文法識别程式的設計了解自頂向下的文法分析思想。

二、實驗重難點

資料結構堆棧在程式設計中的應用

三、實驗内容與要求

根據預測分析表内容，結合自頂向下的文法分析方法，實作對輸入目标串的文法分析。

四、實驗學時

6課時

五、實驗裝置與環境

C語言編譯環境

六、根據實驗過程填寫下列内容

1．實驗準備

給定文法G[E]如下：

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

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

F->(E)|i

⑴該文法是否是LL(1)文法，為什麼？

答：不是

原因：存在左遞歸，是以不是LL（1）文法。

程式：

#include "stdio.h"
#include "malloc.h"
#include "conio.h"
typedef struct Lchar{
	char char_ch;
	
	struct Lchar *next;
}Lchar;
Lchar *p,*h,*temp,*top,*base;
char curchar;
char curtocmp;
int right;
int table[5][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}


};
int i,j;
void push(char pchar){
	temp=(Lchar *)malloc(sizeof(Lchar));
	temp->char_ch=pchar;
	temp->next=top;
	top=temp;
}
void pop(void){
	curtocmp=top->char_ch;
	if(top->char_ch!='#')
	top=top->next;
}

void doforpush(int t){
	switch(t)
	{
	
		    case 0: 
		push('A');  push('T');	break;
		
	    	case 5:
		push('A');  push('T');	break;
		
			case 11:
		push('A');  push('T');  push('+');	break;
		
			case 12:
		push('A');  push('T');  push('-');	break;
		
			case 20:
		push('B');  push('F');	break;
		
			case 25:
		push('B');  push('F');	break;
		
			case 33:
		push('B');  push('F');  push('*');	break;
		
			case 34:
		push('B');  push('F');   push('/');	break;
		
			case 40:
		push('i');  	break;
		
			case 45:
		push(')');  push('E'); push('(');	
    }
}
void changchartoint(){
	switch(curtocmp){
		case 'A':
		i=1; break;
			case 'B':
		i=3; break;
			case 'E':
		i=0; break;
			case 'T':
		i=2; break;
			case 'F':
		i=4;
	
		
	}
		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; 
	
		
	}
	
	
}
void dosome(void){
	int t;
	for(;;){
		pop();
		curchar=h->char_ch;
		printf("\n%c\t%c\n",curchar,curtocmp);
		if(curtocmp=='#'&& curchar=='#')
		break;
		if(curtocmp=='A' || curtocmp=='B' || 
		curtocmp=='E' || curtocmp=='T' || 
		curtocmp=='F'
		){
			if(curtocmp!='#')	{
				changchartoint();
					if(table[i][j]){
						t=10*i+j;
						doforpush(t);
						continue;
					}
					else{
						right=0;break;
					}
			}
			else if(curtocmp!=curchar){
					right=0;break;
			}
			else break;
		}
		else if(curtocmp!=curchar){
					right=0;break;
			}
			else
			{
			h=h->next;continue;
			}
	}
}

int main(void){
	char ch;
	right=1;
	base=(Lchar *)malloc(sizeof(Lchar));
	base->next=NULL;
	base->char_ch='#';
		temp=(Lchar *)malloc(sizeof(Lchar));
	temp->next=base;
	temp->char_ch='E';
	top=temp;
		h=(Lchar *)malloc(sizeof(Lchar));	
		h->next=NULL;
	p=h;
	do{
		ch=getchar();
		putchar(ch);
		if(ch=='i'|| ch=='+'||ch=='*'||ch=='/'||
		ch=='-'||ch=='('||ch==')'||ch=='#'
		){
			
					temp=(Lchar *)malloc(sizeof(Lchar));
					temp->next=NULL;
					temp->char_ch=ch;
					h->next=temp;
					h=h->next;
		}
		else {
			temp=p->next;
			printf("\ninput a wrong vchar ! Input again :\n");
			for(;;){
			
			if(temp!=NULL)
			printf("%c",temp->char_ch);
			else
			break;
			temp =temp->next;
					}
				}
	}while(ch!='#');
	p=p->next;
	h=p;
	dosome();
	if(right)
	printf("\nOK!\n");
	
		else
	printf("\nERROR!\n");
	getchar();
}
           

截圖：