4. 어설픈 야크 만들기 (4) FIRST 구현

프로젝트/어설픈 야크 ,20102011. 1. 12. 15:25

4. 어설픈 야크 만들기 (4) FIRST 구현

실제로 구현하기 위해

각 논터미널에 대한 FIRST 집합들을 전역변수로 할당하고

값을 구하게 된다.

#include "pgyacc.h"

#define TER_SET_SIZE (TER_NUM/32)

extern int st_non;
extern int st_ter;
extern int rule_row;
extern int rules[RULE_NUM][RULE_SIZE];
extern char symtab_non[NON_NUM][32];
extern char symtab_ter[TER_NUM][32];

//----------------

int first_sets[NON_NUM][TER_SET_SIZE];

//---------------

void get_first_step1(){
	int i;
	for(i=1; i<=rule_row; i++){
		if(rules[i][1] <= 0){
			add_item(first_sets[rules[i][0]], -1*rules[i][1]);
		}
	}
}

void get_first_step2(){
	int tmp_sets[NON_NUM][TER_SET_SIZE];
	int i,j,chk;
	int tmp[TER_SET_SIZE];
	
	for(i=1; i<=st_non; i++){
		assign_set(tmp_sets[i],first_sets[i],TER_NUM);
	}
	while(1){
		chk = 0;
		for(i=1; i<=rule_row; i++){
			if(rules[i][1]>0){
				assign_set(tmp,tmp_sets[rules[i][1]],TER_NUM);
				for(j=2; rules[i][j]!=0; j++){
					ring_sum(tmp,tmp_sets[rules[i][j]],TER_NUM);
				}
				union_set(tmp_sets[rules[i][0]], tmp, TER_NUM);
			}
		}
		for(i=1; i<=st_non; i++){
			if(!cmp_set(tmp_sets[i],first_sets[i],TER_NUM)){
				chk = 1;
				break;
			}
		}
		if(chk){
			for(i=1; i<=st_non; i++){
				assign_set(first_sets[i],tmp_sets[i],TER_NUM);
			}
		}else{
			break;
		}
	}
}

void get_first_set(){
	get_first_step1();
	get_first_step2();
}

void print_first_set(){
	int i,j;
	puts("====== first =======");
	for(i=1; i<=st_non; i++){
		printf("%s first: ", symtab_non[i]);
		for(j=0; j<TER_NUM; j++){
			if(is_exist_item(first_sets[i],j)){
				if(j==0)
					printf("<e>, ");
				else
					printf("%s, ",symtab_ter[j]);
			}
		}
		printf("\n");
	}
	puts("====================\n");
}

void first(int rule, int pos, int* set){
	int i;
	
	if(rules[rule][pos] < 0){
		add_item(set, -1 * rules[rule][pos]);
	}else if(rules[rule][pos] > 0){
		assign_set(set, first_sets[rules[rule][pos]], TER_NUM);
		for(i=pos+1; rules[rule][i]!=0; i++){
			ring_sum(set, first_sets[rules[rule][i]], TER_NUM);
		}
	}else{
		add_item(set, EPSILON);
	}
}

first_sets 2차원 배열을 보면

논터미널의 개수 만큼 , 터미널 집합들이 배정된다.

실제로 이 상수의 크기는

pgyacc.h 에 정의 되어 있는데

#define RULE_SIZE 32

#define RULE_NUM 1024

#define RULE_SET_SIZE (RULE_SIZE/32)

#define TER_NUM 1024

#define NON_NUM 1024

#define TER_SET_SIZE (TER_NUM/32)

#define LR_NUM 4096

#define LR_SET_SIZE (LR_NUM/32)

#define EPSILON 0

#define DOLLOR (TER_NUM - 1)

#define ACCEPT 1025

#define SH_RE_CONF 1026

#define RE_RE_CONF 1027

크기 제약을 둔것이다.

하지만 상당히 크기가 큰데

실제 문법은 크기가 다양하고 저 값보다 작은 경우가 대부분이고

굳이 최대 크기까지 계산할 필요는 없으므로

실제 문법의 크기는 파싱과정에서 알아낸다.

rule_row // 룰의 개수

st_ter // 터미널 심볼의 개수

st_non // 논터미널 심볼의 개수

앞서 설명한 알고리즘에 따라

2개의 스텝 과정을 거쳐서 FIRST 집합을 구하게 된다.

실제로 2칙(?) 연산 문법을 작성하고

FIRST를 구해보면 작 작동하는 것을 볼 수 있다.

저작자표시

'프로젝트 > 어설픈 야크 ,2010' 카테고리의 다른 글

5. 어설픈 야크 만들기 (2) CLOSURE 와 GOTO 연산 (0)	2011.01.14
5. 어설픈 야크 만들기 (1) LR(0) (0)	2011.01.12
4. 어설픈 야크 만들기 (4) FIRST 구현 (0)	2011.01.12
4. 어설픈 야크 만들기 (3) 집합 관련 표현 (0)	2011.01.12
4. 어설픈 야크 만들기 (2) FIRST 구하기 개념 (1)	2011.01.12
4. 어설픈 야크 만들기 (1) FIRST 구하기 필요성 (0)	2011.01.12

Posted by 멍충한아싸

Trackback 0 Comment 0

댓글을 달아 주세요

«이전 1 ··· 6 7 8 9 10 11 12 13 14 ··· 16 다음»

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

성대아싸의 멍충한 프로그래밍