재귀 하강 방식으로 PL/0 파싱,실행하기 (Recursive descent parser)

대학

재귀 하강 방식으로 PL/0 파싱,실행하기 (Recursive descent parser) - 2

SavvyTuna 2015. 2. 9. 18:10

컴파일러가 코드를 해석하는 일을 약간 교과서적인 방법으로 몇가지 뭉텅이로 나눠서 생각해보자.

왠만한 컴파일러 관련 책이라면 이런 그림이 들어가 있을거다.

1.Lexical analysis
하나의 긴 복잡한 문자열이라고 볼 수 있는 코드를 의미있는 토큰 단위로 조각조각내는 단계. 예를들어,

begin
x := m; y := n; call multiply;
end.

위의 코드를 토큰들로 나누면

"begin", "x", ":=", ";", "y", ":=", "n", ";", "call", "multiply", ";", "end", ".'

이런 문자열들이 되겠다. 여기에서 의미 없는 문자열들은 전부 무시한다. 공백, 개행, 주석 처럼.

2. Syntax analysis
문법 오류를 검사하는 단계이다. 토큰을 하나씩 읽어 나가면서 문법에 명시된 순서대로 나열되어있는지를 확인한다.

만약 변수 선언할때 var 123,;;;; 이라고 해놓았으면? var 까지 읽고나서 뒤에 식별자가 오길 예상했는데 단순 숫자가 나와버린다. 이런때 문법 오류를 내 뱉고 파싱을 종료한다.

3. Semantic analysis
이전 단계는 토큰이 정해진 순서대로 나열되어 있는지를 확인해 보는 단계였다면, 여기에서는 의미 있게 나열되어있는지를 확인한다. 예를들어 다음과 같은 C함수가 있다고 해보자

int func(){
return y;
}

함수 헤더나 블록도 정확히 문법에 맞게 선언되었고, return 뒤에 식별자가 오고, 세미콜론으로 끝나는 문법적으로 완벽한 c 함수이다. 하지만, 전역변수로 y가 있지 않는 이상 저 return y;는 정상적인 코드가 아니다. 이런 의미적으로 맞지 않는 코드를 찾아낸다.

4. Intermediate code generation
중간 언어 생성. 중간언어는 약간 어셈블리처럼 저수준 언어랑 비슷하지만 장치, 플랫폼에 독립적인 일종의 슈도코드 같은 언어다. 대개는 중간 언어를 최적화 시키는 방법을 사용한다. 최적화된 중간언어를 다시 해석해서, .exe라던가 .out 같은 최종 실행 파일을 만들어 낸다. 그 외에, C같은 경우는 컴파일러가 .exe나 .out 까지 내 뱉지만 (물론 목적파일 만들어서 링크 시키고 하지만) 자바 같은 경우는 '바이트 코드'라는 중간언어 까지 만들어, 배포하고. 사용자의 자바 가상 머신에서 이 바이트 코드를 돌린다. PL/0 에서는 간단한 스택기반 가상머신용 중간언어를 생성하기로 한다. (가상머신 하니까 왠지 복잡해 보이는데, 그냥 구동기를 만든다고 생각하면 된다)

중간코드 생성까지. 최적화는 하지 않겠다. 위의 순서대로 파서를 만들기로 한다. C++이 아니라 C로 진행했다.

일단 전역변수들과 토큰 타입에 대한 열거형을 선언한다.

typedef enum
{
	TYPE_NONE = 0,

	TYPE_IDENTIFIER,	// 식별자
	TYPE_KEYWORD,		// 키워드
	TYPE_NUMBER,		// 숫자
	
	TYPE_ASSIGN,		// :=
	TYPE_GREATER_EQUAL, // <=
	TYPE_LESS_EQUAL,	// >=
	TYPE_NOT_EQUAL,		// <>

	TYPE_PLUS = '+',
	TYPE_MINUS = '-',
	TYPE_MULTIPLY = '*',
	TYPE_DIVIDE = '/',
	
	TYPE_COMMA = ',',
	TYPE_EQUAL = '=',
	TYPE_SEMICOLON = ';',
	TYPE_PERIOD = '.',
	
	TYPE_COLON = ':',
	TYPE_GREATER = '>',
	TYPE_LESS = '<',
	
	TYPE_LPAREN = '(',
	TYPE_RPAREN = ')',

	TYPE_OTHER,

} TOKEN_TYPE;

char keyWords[][10] = { "const", "var", "procedure", "call", 
	"begin", "end", "if", "then", "while", "do", "odd"};

FILE *		fp			= NULL;	// 입력 파일 포인터
char		ch			= '\0';		// current char

TOKEN_TYPE	type		= TYPE_NONE;
char		token[128]	= ""; // 토큰 문자열
int			num			= 0;		// 토큰 타입이 숫자면 이 변수로 숫자 값에 접근

모든 키워드는 TYPE_KEYWORD로 표현한다, 지금 생각해보면 키워드 하나 하나씩 열거형으로 만들어 놨어도 됐었을듯 싶다. (나중에 남의 코드를 찾아보니 대부분 그렇게 하더라) 근데 뭐 그렇게 차이 있는건 아니고.

이제 첫번째로 해야할건 Lexical Analysis, 토큰 자르기다. 이 단계에서 모든 코드들을 전부 토큰으로 조각내버릴 수도 있겠지만, 그럴필요는 없기 때문에, 필요할때마다 토큰 하나씩 읽어서 잘라내기로 한다. 여기에서 토큰을 하나씩 잘라서 token 전역변수에 저장하는 함수가 NextToken이다.

int NextToken()
{
	int tokenIndex = 0;
	token[0] = '\0';

	if( isdigit(ch) )
	{
		while( isdigit(ch) )
		{
			token[tokenIndex++] = ch;
			ch = fgetc(fp);
		}
		token[tokenIndex] = '\0';
		num = atoi(token);
		type = TYPE_NUMBER;
	}
	else if( isalpha(ch) )
	{
		while( isalpha(ch) || isdigit(ch) )
		{
			token[tokenIndex++] = ch;
			ch = fgetc(fp);
		}
		token[tokenIndex] = '\0';

		if(isKeyWord(token))
		{
			type = TYPE_KEYWORD;
		}
		else
		{
			type = TYPE_IDENTIFIER;
		}
	}
	else if( isSpecialChar(ch) )
	{
		char before = ch;
		token[0] = ch;
		token[1] = '\0';
		type = (TOKEN_TYPE)ch;

		ch = fgetc(fp);

		if( before == ':' && ch == '=' )
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_ASSIGN;

			ch = fgetc(fp);
		}
		else if( before == '<' && ch == '=')
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_LESS_EQUAL;

			ch = fgetc(fp);
		}
		else if( before == '>' && ch == '=')
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_GREATER_EQUAL;

			ch = fgetc(fp);
		}
		else if( before == '<' && ch == '>')
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_NOT_EQUAL;

			ch = fgetc(fp);
		}

	}
	else if(ch == EOF)
	{
		return FALSE;
		// error(0);
	}

	else
	{
		// A char i can't parse
		printf("CH : %d(%c)\n", ch, ch);
		type = TYPE_NONE;

		ch = fgetc(fp);
	}

	printf("NEXT token : %s\n", token);

	// eliminate white spaces
	while( isspace(ch) ){ ch = fgetc(fp); }
	return TRUE;
}

우선 첫번째 문자가 숫자면 숫자 타입으로 읽어버리고, 문자면 공백까지 읽은 후에 키워드인지 아닌지 판별, 특수문자인 경우 문자 1개를 읽거나 종류에 따라서 2개를 읽어낸다. 전역변수 'token'에 그 내용을 저장하고 만약 숫자 토큰이라면 num 변수에 숫자값도 저장한다.(매번 atoi하면 귀찮으니까) 마지막으로는 토큰 타입을 반환한다. 나중에 토큰에 접근할때 이 전역변수들을 이용하도록 한다.

그 다음 간단한 Syntax Analysis를 위해 문법 구조를 따와서 함수구조를 만든다. 전체 코드는 아래와 같다.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
//#include <stdbool.h>

#define FALSE 0
#define TRUE 1

typedef enum
{
	TYPE_NONE = 0,

	TYPE_IDENTIFIER,
	TYPE_KEYWORD,
	TYPE_NUMBER,
	
	TYPE_ASSIGN,
	TYPE_GREATER_EQUAL,
	TYPE_LESS_EQUAL,
	TYPE_NOT_EQUAL,

	TYPE_PLUS = '+',
	TYPE_MINUS = '-',
	TYPE_MULTIPLY = '*',
	TYPE_DIVIDE = '/',
	
	TYPE_COMMA = ',',
	TYPE_EQUAL = '=',
	TYPE_SEMICOLON = ';',
	TYPE_PERIOD = '.',
	
	TYPE_COLON = ':',
	TYPE_GREATER = '&gt;',
	TYPE_LESS = '&lt;',
	
	TYPE_LPAREN = '(',
	TYPE_RPAREN = ')',

	TYPE_OTHER,

} TOKEN_TYPE;

char keyWords[][10] = { "const", "var", "procedure", "call", "begin", "end", "if", "then", "while", "do", "odd"};

FILE *		fp			= NULL;
char		ch			= '\0';  // current char

TOKEN_TYPE	type		= TYPE_NONE;
char		token[128]	= "";
int			num			= 0;

void error(int err)
{
	fprintf(stderr, "ERROR %d\n", err);
	exit(-1);
}

int isKeyWord(char * str)
{
	int i = 0;
	for(i = 0; i &lt; sizeof(keyWords) / sizeof(char[10]); i++ )
	{
		if( strcmp(str, keyWords[i]) == 0 )
			return TRUE;
	}
	return FALSE;
}

int isSpecialChar(char c)
{
	if( c == '+' || c == '-' || c == '*' ||	c == '/' || c == ',' || 
		c == '=' || c == ';' || c == '.' || c == '(' || c == ')' ||
		c == ':' || c == '&gt;' || c == '&lt;')
	{
		return TRUE;
	}
	return FALSE;
}

int NextToken()
{
	int tokenIndex = 0;
	token[0] = '\0';

	if( isdigit(ch) )
	{
		while( isdigit(ch) )
		{
			token[tokenIndex++] = ch;
			ch = fgetc(fp);
		}
		token[tokenIndex] = '\0';
		num = atoi(token);
		type = TYPE_NUMBER;
	}
	else if( isalpha(ch) )
	{
		while( isalpha(ch) || isdigit(ch) )
		{
			token[tokenIndex++] = ch;
			ch = fgetc(fp);
		}
		token[tokenIndex] = '\0';

		if(isKeyWord(token))
		{
			type = TYPE_KEYWORD;
		}
		else
		{
			type = TYPE_IDENTIFIER;
		}
	}
	else if( isSpecialChar(ch) )
	{
		char before = ch;
		token[0] = ch;
		token[1] = '\0';
		type = (TOKEN_TYPE)ch;

		ch = fgetc(fp);

		if( before == ':' &amp;&amp; ch == '=' )
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_ASSIGN;

			ch = fgetc(fp);
		}
		else if( before == '&lt;' &amp;&amp; ch == '=')
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_LESS_EQUAL;

			ch = fgetc(fp);
		}
		else if( before == '&gt;' &amp;&amp; ch == '=')
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_GREATER_EQUAL;

			ch = fgetc(fp);
		}
		else if( before == '&lt;' &amp;&amp; ch == '&gt;')
		{
			token[1] = ch;
			token[2] = '\0';
			type = TYPE_NOT_EQUAL;

			ch = fgetc(fp);
		}

	}
	else if(ch == EOF)
	{
		return FALSE;
		// error(0);
	}

	else
	{
		// A char i can't parse
		printf("CH : %d(%c)\n", ch, ch);
		type = TYPE_NONE;

		ch = fgetc(fp);
	}

	printf("NEXT token : %s\n", token);

	// eliminate white spaces
	while( isspace(ch) ){ ch = fgetc(fp); }
	return TRUE;
}

// FWD decl
void Expression();

void Factor()
{
	int i = 0;

	if( type == TYPE_IDENTIFIER )
	{
		// TODO
		NextToken();
	}

	else if( type == TYPE_NUMBER )
	{
		NextToken();
	}

	else if( type == TYPE_LPAREN )
	{
		NextToken();
		Expression();

		if( type == TYPE_RPAREN )
		{
			NextToken();
		}
		else
			error(22);
	}
	else
		error(23);

}

void Term()
{
	Factor();
	while( type == TYPE_MULTIPLY || type == TYPE_DIVIDE )
	{
		NextToken();
		Factor();
	}
}

void Expression()
{
	if( type == TYPE_PLUS || type == TYPE_MINUS )
	{
		NextToken();
		Term();
	}
	else
		Term();

	while( type == TYPE_PLUS || type == TYPE_MINUS )
	{
		NextToken();
		Term();
	}
}

void Condition()
{
	if( strcmp("odd", token) == 0 )
	{
		NextToken();
		Expression();
	}
	else
	{
		Expression();

		if( type != TYPE_EQUAL &amp;&amp; 
			type != TYPE_NOT_EQUAL &amp;&amp;
			type != TYPE_LESS &amp;&amp; 
			type != TYPE_LESS_EQUAL &amp;&amp; 
			type != TYPE_GREATER &amp;&amp; 
			type != TYPE_GREATER_EQUAL )
		{
			error(20);
		}
		else
		{
			NextToken();
			Expression();
		}
	}
}

void Statement()
{
	if( strcmp("call", token) == 0 )
	{
		NextToken();

		if(type != TYPE_IDENTIFIER )
		{
			error(14);
		}
		else
		{
			// TODO : check if symbol alive
			NextToken();
		}
	}

	else if( strcmp("if", token) == 0 )
	{
		NextToken();
		Condition();

		if( strcmp(token, "then") == 0 )
		{
			NextToken();
		}
		else
			error(16);

		Statement();
	}

	else if( strcmp("begin", token) == 0 )
	{
		do
		{
			NextToken();
			Statement();
		}
		while(type == TYPE_SEMICOLON);

		if( strcmp("end", token) == 0 )
		{
			NextToken();
		}
		else
			error(17);
	}

	else if( strcmp("while", token) == 0 )
	{
		NextToken();
		Condition();
		if( strcmp("do", token) == 0 )
		{
			NextToken();
		}
		else
			error(18);

		Statement();
	}

	else if( type == TYPE_IDENTIFIER )
	{
		// TODO : check if symbol alive

		NextToken();
		if( type == TYPE_ASSIGN )
		{
			NextToken();
		}
		else
			error(13);

		Expression();
	}
}

void ConstDeclaration()
{
	if( type == TYPE_IDENTIFIER )
	{
		NextToken();
		if( type == TYPE_EQUAL )
		{
			NextToken();
			if( type == TYPE_NUMBER )
			{
				// SYMTAB 에 insert
				NextToken();
			}
			else
				error(2);
		}
		else
			error(3);
	}
	else
		error(4);

}

void VarDeclaration()
{
	if( type == TYPE_IDENTIFIER )
	{
		// TODO : enter
		NextToken();
	}
	else
		error(4);
}

void Block()
{
	if( strcmp(token, "const") == 0 )
	{
		do
		{
			NextToken();
			ConstDeclaration();
		}
		while( type == TYPE_COMMA );

		if( type == TYPE_SEMICOLON )
		{
			NextToken();
		}
		else
			error(5);
	}

	if( strcmp(token, "var") == 0 )
	{
		do
		{
			NextToken();
			VarDeclaration();
		}while( type == TYPE_COMMA );

		if( type == TYPE_SEMICOLON )
		{
			NextToken();
		}
		else
			error(5);
	}

	while( strcmp(token, "procedure") == 0 )
	{
		NextToken();
		if(type == TYPE_IDENTIFIER)
		{
			// TODO : enter
			NextToken();
		}
		else
			error(4);

		if( type == TYPE_SEMICOLON )
		{
			NextToken();
		}
		else
			error(5);

		Block();
		
		if( type == TYPE_SEMICOLON )
		{
			NextToken();
		}
		else
			error(5);
	}

	Statement();
	return ;
}

void SetUP()
{
	fp = fopen("input.txt", "r");
	while( isspace(ch = fgetc(fp)) ){}
}

void CleanUP()
{
	fclose(fp);
}

int main()
{
	{
		SetUP();
	}

	{
		/* main */
		NextToken();
		Block();

		if( strcmp(".", token) != 0 )
		{
			error(9);
		}
	}

	{
		CleanUP();
	}
	return 0;
}

입력된 코드에서 문법에 맞지 않는 구문을 발견하변 바로 error함수를 호출하고 종료된다. error 함수 호출 없이 끝났다면 문법 문제가 없다는 소리.

저작자표시 비영리

'대학' 카테고리의 다른 글

A* (a-star) 알고리즘 휴리스틱 (1)	2015.03.19
재귀 하강 방식으로 PL/0 파싱,실행하기 (Recursive descent parser) - 1 (0)	2015.01.27

현재글재귀 하강 방식으로 PL/0 파싱,실행하기 (Recursive descent parser) - 2

잡 생각 저장소

til, c#, three.js, fixup, unity, Git, GDC, 책, Troubleshooting, pixi, dictionary, algorithm, enum, Hermite, Math, homogeneous coordinate, rebase, LINQ, 라즈베리파이, autosquash,

Today :
Yesterday :

Log Stash