[compilation principle] LR (0) analyzer half done

Preface

Our fire , To ignite the world ——《 dragon 》

---

         \;\\\;\\\;

LR(0)

The goal is （ Hang in the air ）

From grammar to state transition table

#include "LR0.h"

// term  E->E.*T
// 9 7 29
// 0 12
// dot=1
typedef struct item {
    
	i8 vt;// non-terminal  E T F
	i8 production[10];// Generative formula , Every element is a number （ Symbol ）
	i8 size;//0~10
	i8 dot;// Location of points ,0 It's the beginning , When dot==size when , I'll make an appointment 
}item;

// Itemsets I0~I11
//I0
// E'->.E
// E ->.E + T
// E ->.T
// T ->.T * F
// T ->.F
// F ->.(E)
// F ->.id
typedef struct state {
    
	DA* vec;
	i8 index; // Used to identify the status number 
}state;

//action-goto entry 
// How big is the parsing table , It is related to the number of States , I don't know until I finish the calculation 

typedef struct unit{
    
	// Terminator  id + * ( ) $
	// 0 1 2 3 4 5
	i8 _action[6];
	// non-terminal  E T F
	// 6 7 8
	i8 _goto[3];  
}unit;

#define Eh 9
#define E 6
#define T 7
#define F 8
#define id 0
#define add 1
#define mul 2
#define lp 3
#define rp 4
#define end 5
#define int2string(x) (x==9?"E'": \ (x==6?"E": \ (x==7?"T": \ (x==8?"F": \ (x==0?"id": \ (x==1?"+": \ (x==2?"*": \ (x==3?"(": \ (x==4?")": \ (x==5?"$":" error "))))))))))
/*  Primitive grammar  E ->E+T|T T ->T*F|F F ->(E)|id  Augmented grammar  E'->.E E'=9 E ->.E+T 0 E ->.T 1 T ->.T*F 2 T ->.F 3 F ->.(E) 4 F ->.id 5 added */



/*----------------------------------------------------------------------------*/
// Static variables 
char* input = "i+i*i$"; // use i Instead of id
DA* statelist; // All itemsets 
DA* predict;// Forecast analysis table 
bool added[7];   //I0 Is this item in I in 
bool self_added[7];	  //. When followed by a non terminator ,self_added Used to determine I0 Whether an item is added I in . E’->.E not 
DA* buf;// Saved symbols 
state* I0;// The first itemset 

/*----------------------------------------------------------------------------*/


/*----------------------------------------------------------------------------*/
// Function declaration 
void through(state* I);
item* new_item();
unit* new_unit();
state* new_state();
bool isVT(i8 symbol);// Whether it is a non terminator 
unit* find_unit(state* I);//state Corresponding forecast table entries 
item* move_item(item* it);// Revised dot Location 
item* copy_item(item* it);// No modification dot Location 
void print_statelist();
void print_predict();
void init_self_added();// initialization self_added
bool myjudge(void* mydata, void* DAdata);

/*----------------------------------------------------------------------------*/

void exec_LR0() {
    
	/*---------------------------------------*/
	predict = newDA(11);
	statelist = newDA(11);
	/*---------------------------------------*/
	
	/*---------------------------------------*/
	I0 = new_state();
	I0->index = 0; //I0
	pushDA(statelist, I0);
	pushDA(predict, new_unit());
	/*---------------------------------------*/
	/*---------------------------------------*/
	item* i_0 = new_item();
	//E'->.E
	i_0->vt = Eh;	 	
	i_0->production[0] = E;
	i_0->size = 1;
	pushDA(I0->vec, i_0);

	item* i_2 = new_item();
	//E ->.T
	i_2->vt = E;	
	i_2->production[0] = T;
	i_2->size = 1;
	pushDA(I0->vec, i_2);

	item* i_1 = new_item();
	//E ->.E + T
	i_1->vt = E;
	i_1->production[0] = E;
	i_1->production[1] = add;
	i_1->production[2] = T;
	i_1->size = 3;
	pushDA(I0->vec, i_1);

	

	item* i_4 = new_item();
	//T ->.F
	i_4->vt = T;		
	i_4->production[0] = F;
	i_4->size = 1;
	pushDA(I0->vec, i_4);

	item* i_5 = new_item();
	//F ->.(E)
	i_5->vt = F;	 	
	i_5->production[0] = lp;
	i_5->production[1] = E;
	i_5->production[2] = rp;
	i_5->size = 3;
	pushDA(I0->vec, i_5);

	item* i_6 = new_item();
	//F ->.id
	i_6->vt = F;	
	i_6->production[0] = id;
	i_6->size = 1;
	pushDA(I0->vec, i_6);

	item* i_3 = new_item();
	//T ->.T * F
	i_3->vt = T;
	i_3->production[0] = T;
	i_3->production[1] = mul;
	i_3->production[2] = F;
	i_3->size = 3;
	pushDA(I0->vec, i_3);

	//item* i_7 = new_item();
	F ->.(id)
	//i_7->vt = F;
	//i_7->production[0] = lp;
	//i_7->production[1] = T;
	//i_7->production[2] = rp;
	//i_7->size = 3;
	//pushDA(I0->vec, i_7);
	/*---------------------------------------*/

	// The first generation I_1、I_2、I_3、I_4、I_5
	through(I0);

	print_statelist();
	print_predict();
}

void through(state* I) {
    
	ASSERT(I == null, "I It's empty ");
	ASSERT(I->vec->size > I0->vec->size, "I(%d) There are too many items in the item set ", I->index);
	// initialization added and self_added
	for (i8 i = 0; i < 7; ++i)
		added[i] = false;

	/// Traverse I0 Item in 1
	for (u8 i = 0; i < I->vec->size; ++i) {
    
		if (added[i] == true)	// This item has been added 
			continue;
		item* it = (item*)(I->vec->v[i]);
		if (it->dot == it->size)  // This item is over 
			continue;
		i8 X = it->production[0];  // First character 

		//1. 
		added[i] = true;  // This item has been added 
		/// Define a new itemset I_1 
		state* new_I = new_state();
		/// take E'->E. Join in I_1
		pushDA(new_I->vec, move_item(it));
		new_I->index = statelist->size;
		pushDA(statelist, new_I);

		//2.
		// Have the same symbol X Other items of are also added I_1
		/// Traverse I0 Item in 2
		for (i8 j = 0; j < I->vec->size; ++j) {
    
			if (added[j] == true)	// This item has been added 
				continue;
			item* it2 = (item*)(I->vec->v[j]);
			if (it2->dot == it2->size)
				continue;
			i8 X2 = it2->production[0];	 // First character 
			if (X2 == X) {
    
				added[j] = true;   // This item has been added 
				/// take E'->E.+T Join in I_1
				pushDA(new_I->vec, move_item(it2));
			}
		}

		//3.
		// Set the previous state I_0 Jump table of entries 
		///Goto(I_0,I_1)=X
		unit* t = find_unit(I);	// The entry corresponding to the previous itemset 
		if (isVT(X))   // non-terminal 
			t->_goto[X - E] = new_I->index;// Point to the current state 
		else
			t->_action[X] = new_I->index;
		pushDA(predict, new_unit());  // The current entry is not set 


		//4.
		// occasionally . Followed by a non Terminator VT, You need to put this symbol 1 Add all items of 
		// If the new . Back （ First character ） There are also non terminators VT, You also need to put this symbol 2 Add all items of 
		// until . There is no non terminator after 
		/// Traverse I_4 The item 3 
		// Used for processing . Followed by a nonterminal 
		init_self_added();
		buf = newDA(10);
		for (i4 k = 0; k < new_I->vec->size; ++k) {
    
			item* it3 = (item*)new_I->vec->v[k];
			if (it3->dot == it3->size)
				continue;
			i8 X3 = it3->production[it3->dot];	//dot Position character 

			// If it is a new symbol and a non terminator, it is stored 
			if (haveDA(buf, X3, myjudge) == false && isVT(X3) == true)
				pushDA(buf, X3);
			
			// Yes no terminator  
			// Usually one round is over ,k Won't take the second round 
			while (isVT(X3)) {
    	 
				// Traverse I_0
				// Can not traverse E'->.E
				for (i8 l = 1; l < I0->vec->size; ++l) {
    
					if (self_added[l] == true)
						continue;
					item* it4 = (item*)I->vec->v[l];
					if (it4->dot == it4->size)
						continue;
					i8 X4 = it4->vt;	 // Left non terminator 

					if (X4 == X3) {
    
						self_added[l] = true;
						/// take E'->.E+T Join in I_4
						pushDA(new_I->vec, copy_item(it4));

						// If it is a new symbol, it is saved 
						if(haveDA(buf,it4->production[0],myjudge)==false)
							pushDA(buf, it4->production[0]);
					}
				}
				// Add several items of the first level I_4
				// But among the newly added items . There is a non terminator after it 
				X3 = buf->v[buf->size - 1];	// The last symbol is new 
			}
		}
	}
	destroyDA(buf);
}







item* new_item() {
    
	item* it = (item*)malloc(sizeof(item));
	ASSERT(it == null, "item Create failure ");

	it->dot = 0;
	for (i4 i = 0; i < 10; ++i)
		it->production[i] = 0;
	it->vt = -1;
	it->size = 0;
	return it;
}


unit* new_unit() {
    
	unit* it = (unit*)malloc(sizeof(unit));
	ASSERT(it == null, "unit Create failure ");

	for (i4 i = 0; i < 6; ++i)	
		it->_action[i] = 0;
	for (i4 i = 0; i < 3; ++i)
		it->_goto[i] = 0;
	return it;
}


state* new_state() {
    
	state* it = (state*)malloc(sizeof(state));
	ASSERT(it == null, "state Create failure ");

	it->vec = newDA(11);
	it->index = -1;
	return it;
}




bool isVT(i8 symbol) {
    // Whether it is a non terminator 
	if (symbol == E || symbol == T || symbol == F)
		return true;
	return false;
}



unit* find_unit(state* I) {
    
	ASSERT(I == null, "I It's empty ");

	return predict->v[I->index];
}


item* move_item(item* it) {
    
	ASSERT(it == null, "item It's empty ");

	item* iter = new_item();
	iter->dot = it->dot + 1; /// Revised dot Location 
	for (i4 i = 0 ;i < 10;++i)
		iter->production[i] = it->production[i];
	iter->vt = it->vt;
	iter->size = it->size;
	return iter;
}

item* copy_item(item* it) {
    
	ASSERT(it == null, "item It's empty ");

	item* iter = new_item();
	iter->dot = it->dot ;	/// No modification dot Location 
	for (i4 i = 0; i < 10; ++i)
		iter->production[i] = it->production[i];
	iter->vt = it->vt;
	iter->size = it->size;
	return iter;
}


void print_statelist() {
    
	if (statelist->size == 0) {
    
		printf(" No state \n");
		return;
	}


	printf("--------------------\n");
	for (i4 i = 0;i<statelist->size; ++i) {
    
		state* s = (state*)statelist->v[i];
		printf("I%d\n", i);
		for (i4 j = 0;j<s->vec->size; ++j) {
    
			item* it = (item*)s->vec->v[j];			
			printf("\t%s->", int2string(it->vt));


			i4 k = 0;
			for (; k < it->size; ++k) {
    
				if (it->dot == k)
					printf(".");
				printf("%s", int2string(it->production[k]));
			}
			if (it->dot == k)
				printf(".");
			printf("\n");
		}
	}
	printf("--------------------\n");
}






void print_predict() {
    

	printf("-------------------------------------\n");
	printf("\t ACTION \t| GOTO\n");
	printf(" id + * ( ) $ | E T F\n");
	for (i4 i=0;i<predict->size;++i) {
    
		printf("[%-2d] ", i);
		unit* u = (unit*)predict->v[i];
		for (i4 j = 0; j < 6; ++j) 
			printf("%3d",u->_action[j]);
		printf(" |");
		for (i4 j = 0; j < 3; ++j)
			printf("%3d", u->_goto[j]);
		printf("\n");
	}
	printf("-------------------------------------\n");
}





void init_self_added() {
    
	self_added[0] = true;
	self_added[1] = false;
	self_added[2] = false;
	self_added[3] = false;
	self_added[4] = false;
	self_added[5] = false;
	self_added[6] = false;
}







bool myjudge(void* mydata, void* DAdata) {
    
	i8 d1 = (i8)mydata;
	i8 d2 = (i8)DAdata;
	if (mydata == DAdata)
		return true;
	return false;
}

         \;\\\;\\\;

effect

Only one round of analysis , from I0 To I1~I5
The second round should be I1~I5
The third round
The fourth round
Until all itemsets , All items have been processed .

My program , Create a new itemset each time , All processing two rounds of memory will explode . The processing method is to judge the items in all previous item sets after each item change , Is there the same , Some words point to . Create a new itemset without .

--------------------
I0
        E'->.E E->.T E->.E+T T->.F F->.(E) F->.id T->.T*F I1 E'->E.
        E->E.+T
I2
        E->T.
        T->T.*F
I3
        T->F.
I4
        F->(.E)
        E->.T
        E->.E+T
        T->.F
        T->.T*F
        F->.(E)
        F->.id
I5
        F->id.
--------------------
-------------------------------------
         ACTION         |   GOTO
      id  +  *  (  )  $ |  E  T  F
[0 ]   5  0  0  4  0  0 |  1  2  3
[1 ]   0  0  0  0  0  0 |  0  0  0
[2 ]   0  0  0  0  0  0 |  0  0  0
[3 ]   0  0  0  0  0  0 |  0  0  0
[4 ]   0  0  0  0  0  0 |  0  0  0
[5 ]   0  0  0  0  0  0 |  0  0  0
-------------------------------------