ll(1).txt

用LL（1）法对布尔表达式的语法分析

#define MAX 100
#include <iostream>
using namespace std;
#include <string.h>
#include <stdlib.h>

//函数声明
void input();
void init_stack();
void ll1_analyzing();
void ll1array_push(char);
int is_Vt();
int is_ll1array(char);
int Vn_index();
int Vt_index(char);
void pop();
void push(char);
void reverse();
int printerror();

//全局变量定义


//LL(1)表一
//定义LL(1)分析表
char Vn_array[] = "ABCDE";
char Vt_array[] = "i+*()#";
char  *LL1_array[][6] = {
	{"CB", " ", " ", "CB", " ", " "},
	{" ", "+CB", " ", " ", "u", "u"},
	{"ED", " ", " ", "ED", " ", " "},
	{" ", "u", "*ED", " ", "u", "u"},
	{"i", " ", " ", "(A)", " ", " "}
};
//end


/*
//LL(1)表二
//定义LL(1)分析表
char Vn_array[] = "PDEFS";
char Vt_array[] = "bdes;#";
char  *LL1_array[][6] = {
	{"bDSe", " ", " ", " ", " ", "bDSe "},
	{" ", "d;E", " ", " ", " ", " "},
	{" ", "D", " ", "u", " ", " "},
	{" ", " ", "u", " ", ";sF", "u"},
	{" ", " ", " ", "sF", " ", " "}
};
//end
*/

char analyzed_sentence[MAX];

char stack[MAX];
char top;
char *temp;
char identified[MAX];
int n=0;

void main()
{
	input();
	init_stack(); //初始化栈，将'#'和开始符进栈
	ll1_analyzing();
       
}


void input()
{
	int ch=0;
	int	i=0;
	while((ch=cin.get()) != '#') {
		analyzed_sentence[i] = ch;
		i++;
	}
	analyzed_sentence[i] = '#';
}

void init_stack()
{
	stack[0] = '#';
	stack[1] = Vn_array[0]; //开始符进栈
	cout << stack[1] << "->";
}

void ll1_analyzing()
{
	top = stack[1];
	int error;
	for (int i=0;i<=strlen(analyzed_sentence);i++) {
		int test;
		test = is_Vt();
		if (1 == test) {
			if (top == analyzed_sentence[i]) {
				identified[n++] = top;
				pop();
				continue;
			}
			else {
				printerror();
				break;
			}
		}
		else if ('#' == top) {   //结束，将最终的表达式打印出来，除了'#'
			for (int p=0;p<strlen(analyzed_sentence)-1;p++) {
					printf("%c", analyzed_sentence[p]);
				}
				cout<<endl;
				break;
			}
		else {
			do  {
					int judge=0;
					judge = is_ll1array(analyzed_sentence[i]);
					if (judge == 1) {
						if (1 == is_Vt()) {     //假设有符号不匹配，出错
							error=printerror();
							break;
						}
						ll1array_push(analyzed_sentence[i]);
					}
					else {
						error = printerror();
						break;
					}
										
				}
				while (top != analyzed_sentence[i]);
				if (error == 1) 
					break;
				identified[n++] = top;
				if (top != '#')
					pop();
		}
	
	}
}

void ll1array_push(char currentchar)
{
	int i,j;
	i=Vn_index();  //求栈顶元素在Vn数组里面的下标
	j=Vt_index(currentchar);  //求当前处理的符号在Vt数组里面的下标
	temp=LL1_array[i][j];
	reverse();
	pop();
	int k;
	for(k=0;k<strlen(temp);k++)
	{
		push(temp[k]);
	}
	printf("%s", identified);
	for (int m=strlen(stack)-1;m>0;m--)
		cout << stack[m] ;
	cout << "->";
	if (top == 'u')
		pop();
}

void pop()
{
	int topnum;
	topnum = strlen(stack)-1;
	stack[topnum] = '\0';
	top = stack[topnum-1];
}

void push(char element)
{
	int topnum;
	topnum = strlen(stack);
	stack[topnum] = element;
	top = element;
}

int is_Vt()
{
	int i;
	int hit=0;
	for (i=0;i<strlen(Vt_array);i++) {
		if(top == Vt_array[i])
			hit = 1;
	}
	if (top == '#')
		hit = 0;
	if (hit == 1)
		return 1;
	else 
		return -1;
}
	
int is_ll1array(char currentchar)
{
	int i,j;
	i=Vn_index();  //求栈顶元素在Vn数组里面的下标
	j=Vt_index(currentchar);		//求当前处理的符号在Vt数组里面的下标
	if (LL1_array[i][j] == " ") {
		return -1;
	}
	else
		return 1;

}


int Vn_index()
{
	for(int i=0;i<strlen(Vn_array);i++) {
		if (top == Vn_array[i])
			return i;		
	}
	return -1;
}

int Vt_index(char index_array)
{
	for(int i=0;i<strlen(Vt_array);i++) {
		if (index_array == Vt_array[i])
			return i;
	} 
	return -1;
}

void reverse() //逆序处理
{
	char s[MAX];
	strcpy(s, temp);
	int i,j;
	char tem;
	i=0;
	while (s[i] != '\0')
		++i;
	--i;
	if (s[i] == '\n')
		--i;
	j=0;
	while (j<i)
	{
		tem = s[j];
		s[j] = s[i];
		s[i] = tem;
		--i;
		++j;
	}
	temp=s;
}

int printerror()
{
	cout << "这不是一句合法的句子，无法推导！" <<endl;
	return 1;
}