[js] 식처리기의 제작 # 1 / 3

이 전에 작성했던 포스팅인 자바스크립트의 식과 문 1, 2, 3 에서 언제 한 번 식처리기를 만들어보면 여러가지를 알게 된다는 언급을 한 적이 있습니다.

s60스터디를 하다보니 정말로 식처리기를 만드는 일이 일어났습니다.

실은 SASS의 scss파서를 만들다가 작성하게 된 소스입니다. 해당 소스는 다음의 깃헙에서 내려받을 수 있습니다.

https://github.com/projectBS/bsSass/blob/gh-pages/bsSass.0.2.js

해서 이번 포스팅에서는 식처리를 간단히 살펴보면서 구현해가도록 하겠습니다. 이 포스팅은 자바스크립트의 문, 식에 대한 이해가 있다는 것을 가정하고 있습니다.

만약 자바스크립트 문법에 익숙하지 않다면 상당히 어려운 내용이 될 수 있으니 선행해서 문법공부를 먼저 하시기 권장합니다.

식 처리기는 제법 분량이 방대하므로 총 3회에 걸처 순차적으로 구현해가겠습니다.

1회차에서는 기본적인 값처리와 연산식의 처리를 다룹니다.
그 다음으로는 함수의 호출, 괄호연산자, 배열 등이 일으키는 스택처리기를 공부합니다.
마지막으로 값객체를 도입하여 식처리기를 다양하게 확장하고 나만의 데이터타입을 식처리기에 어떻게 넣는지를 배우게 됩니다.

식 처리기의 형태 결정

식처리기를 직접 만드는 이상 구지 자바스크립트와 동일한 형태로 만들 필요도 없을 뿐더러, 기능을 넣는 것도 자유입니다 (scss용으로 제작된 식처리기도 css에 대응하는 다양한 속성을 갖고 있습니다)

자바스크립트의 식처리기에 비해 다음과 같이 간략화된 버전을 구현할 예정입니다.

학습을 위해 식처리기를 제작하게 되므로 우선 할당을 식에서 제외합니다.
할당을 처리하려면 식처리기가 매우 복잡해지는데 이유는 왼쪽에서 오른쪽으로 해석되지 않고 오른쪽에서 왼쪽으로 해석되는 예외를 만들어야하기 때문입니다.
따라서 변수나 함수는 미리 주어지는 것으로 정리하고 식 내에서의 정의는 불가능하도록 작성하죠.
사칙연산자만 지원합니다.
우선 사칙연산자의 처리를 배우고 나면 다른 연산자는 자연스레 적응할 수 있게 됩니다. 물론 연산자 우선순위는 그대로 유지됩니다.
값객체는 재정의합니다.
특별한 VO(Value Object)를 정의하여 다양한 형태로 활용하게 됩니다. 값객체는 식 해석 중에는 값으로 해석되지만 다양한 속성을 갖을 수 있는 객체입니다. 예를들어 컬러값의 경우 외부에는 하나의 rgb값으로 표시되지만 내부에는 r, g, b속성을 따로 갖고 있다던가하는 식입니다.
객체속성을 지원하지 않습니다.
점(.)을 이용한 객체속성을 지원하지 않습니다. 특별한 이유는 없고 간략히 구현하기 위함이므로 향후 별도로 추가해가면 됩니다.

위의 화이트리스트를 통해 구현되므로 사칙연산자 외에 수많은 단항연산자, 컴마연산자 등 전부 지원하지 않습니다..귀찮 ^^;

리터럴 처리

어떤 식을 문자열로 주어졌을 때 그 문자열이 단일한 값이라면 그 값으로 변형해서 반환하면 됩니다. 예를들어 문자열로 “1” 이라고 보내면 1이라는 숫자를 반환하면 되는 것이죠. 이러한 처리기를 ex라고 하면 다음과 같은 결과를 예상해볼 수 있습니다.

ex("1"); //1
ex("null"); //null
ex("undefined"); //undefined
ex("true"); //true
ex(" 'string' "); // string문자열

이렇듯 더 이상 쪼갤 수 없는 가장 기본적인 토큰 중 값으로 인식되는 것을 언어적으로는 리터럴(literal)이라 부릅니다. 위의 요소는 각각 숫자리터럴, null리터럴, undefined리터럴, 불린리터럴, 문자열리터럴 등으로 부를 수 있겠죠.

따라서 최초의 식처리기는 인자로 주어진 문자열이 리터럴인 경우를 먼저 털어내는 기능을 갖춰야합니다. 이 중 null, false, true, undefined 등은 그 문자열이 오면 즉시 그 값을 반환하면 그만이므로 해쉬맵에 잡아두면 될 것입니다.

var literal = {'true':true, 'false':false, 'null':null, 'undefined':undefined};

var ex = function( v ){
	//리터럴에 걸리면 곧장 반환
	if( v in literal ) return literal[v];
}

숫자와 문자열의 경우는 어떻게 인식할까요? 간단히 정규식을 작성해서 처리하면 됩니다. 사실 숫자인식은 매우 정교한 정규식이 필요하지만 여기서는 간단히 구현하고 문자열의 경우도 이스케이핑을 지원하지 않는 간략한 형태로 구현해보죠.

//숫자정규식
var rnum = /^[-]?[0-9.]+$/;

//문자열정규식
var rstr = /^(["][^"]*["]|['][^']*['])$/;

var ex = function( v ){
	if( v in literal ) return literal[v];

	//숫자에 걸리면 숫자로
	if( rnum.test(v) ) return parseFloat(v);

	//문자열에 걸리면 앞뒤 따옴표뗀 문자열로
	if( rstr.test(v) ) return v.substring( 1, v.length - 1 );
}

이제 어느 정도 기본값은 처리할 수 있는 식처리기가 되었습니다.

변수처리기

변수처리기를 작성할 건데 미리 정의된 변수를 식에 연동하려면 그 값이 변수명과 일치하는지 확인해야 합니다. 자바스크립트와 마찬가지로 변수명에 특별한 제약을 두지 않는다라면 _$를 포함한 영문자로 시작할 수 있는 변수명 규칙을 그대로 적용하면 되고 변수를 관리하는 VAR 해쉬맵에서 찾아보면 될 것입니다.

var VAR = {a:3, b:5}; //a,b라는 변수가 정의되어있는 경우

//변수정규식
var rvar = /^[A-Za-z$_][A-Za-z$_0-9]*$/

var ex = function( v ){
	if( v in literal ) return literal[v];
	if( rnum.test(v) ) return parseFloat(v);
	if( rstr.test(v) ) return v.substring( 1, v.length - 1 );

	//변수처리
	if( rvar.test(v) ) return VAR[v];
}

console.log( ex('a') ); //3
console.log( ex('c') ); //undefined

이번에 구현할 식처리기는 할당을 구현하지 않으므로 VAR는 미리 정의되어있어야 합니다. 이렇듯 어떤 식이 처리될 때 변수를 찾는 별도의 공간이 주어지게 마련인데 위의 ex는 VAR에서 변수를 찾아 매칭하게 됩니다. 이러한 변수가 정의되어있는 메모리공간을 자바스크립트에서는 어휘환경(Lexical Environment)라고 부르는데 어떤 언어가 되었든 식이나 문에 등장한 변수를 해석하려면 반드시 그 변수이름에 이용해(혹은 포인터를 이용해) 값을 참조할 수 있는 메모리 공간이 필요합니다.

각 식마다 접근할 수 있는 변수공간을 상황에 맞춰 다르게 주거나 격리할 수 있는 이는 식처리기를 어떻게 구현하는가에 달려있습니다. 이를 변수의 유효범위(Scope) 라 합니다. 위의 식처리기는 중첩된 상황내에서의 식처리를 하지 않으므로 단일한 VAR객체 하나로 변수를 사용하고 있지만 만약 어휘환경을 중첩해서 주거나 포함관계로 주는 것을 구현하려면 프로토타입체인을 이용해 구현해야합니다.

연산식 처리

이제 식처리기의 꽃인 연산자 처리기를 해결해보겠습니다. 여태까지 구현한 ex함수는 순차적으로 리터럴, 숫자, 문자열, 변수인 경우를 인지하여 값으로 환원해 돌려줬습니다. 이 경우에 해당되지 않는다면 드디어 연산을 할 차례가 된거죠.

정규식으로 연산식의 토큰을 나눌 수도 있겠지만 학습도 할겸해서 순차적으로 문자하나하나를 검사해가는 스타일을 사용해보겠습니다. 우선 식처리기가 인식할 연산자와 해당 연산자의 우선순위를 정의해야합니다.

var op = {'+':1,'-':1,'*':2,'/':2};

이렇게 네가지 연산자와 우선 순위를 정의했습니다. 이후 더 많은 연산자를 정의하는 것은 자유입니다.

2항 연산자의 경우 인자를 두 개 받는 함수로 인식할 수 있는데, 예를 들어 1 + 2 라는 식은 plug( 1, 2 ) 로 인식할 수 있습니다. 따라서 2항을 받는 형태의 함수로 각 연산자를 정의할 수 있습니다.

var opf = {
	'+':function(a,b){return a+b;},
	'-':function(a,b){return a-b;},
	'*':function(a,b){return a*b;},
	'/':function(a,b){return a/b;}
};

이제 재료가 다 모였으니 토크나이저를 작성해보죠. 토크나이저의 아이디어를 정리하면 다음과 같습니다.

빈 배열을 만든다.
문자열의 길이만큼 루프를 돌면서 한자한자 검사한다.
만약 i번째 문자가 연산자라면 그 직전까지의 문자열을 잘라내어 배열에 넣고,
연산자도 배열에 넣고
다음 문자열을 자를 시작위치를 연산자 다음으로 옮겨둔다
마지막까지를 전진하고 나면 남은 문자열을 배열에 넣어준다.

머 요정도죠. 이를 “1 + 2 * 3” 정도로시뮬레이션 해볼까요?

빈 배열 생성 result = [];
최초 루프를 돌다가 +발견!
직전까지의 문자열을 배열에 삽입 result = [‘1’];
연산자도 배열에 넣음 result = [‘1’, ‘+’];
그 다음에 문자열을 자를 때는 +자리 이후부터
이를 마지막까지 반복하면 result = [‘1’, ‘+’, ‘2’, ‘*’];
남은 문자열 ‘3’을 넣어준다 result = [‘1’, ‘+’, ‘2’, ‘*’, ‘3’];

이렇게 되어 토크나이저의 결과는 이쁘게 [‘1’, ‘+’, ‘2’, ‘*’, ‘3’] 나옵니다.

헌데 여기서 1, 2, 3의 경우는 리터럴에 해당됩니다. 따라서 ex함수에게 주면 숫자로 환원될 것입니다. 따라서 위의 3번 절차는 다음과 같이 고쳐쓸 수 있습니다.

만약 i번째 문자가 연산자라면 그 직전까지의 문자열을 잘라 ex함수에 넘겨준 결과를 배열에 넣고,

라고 할 수 있죠, 그럼 결과배열도 [ex(‘1’), ‘+’, ex(‘2’), ‘‘, ex(‘3’)] 이렇게 되어 결과적으로 [1, ‘+’, 2, ‘‘, 3] 라는 숫자가 제대로 들어있는 상태가 됩니다.

이상을 코드로 보죠.

var op = {'+':1,'-':1,'*':2,'/':2};
var opf = {'+': function(a,b){return a+b;},... },

var ex = function(v){

	//...리터럴 처리기

	var result, i, j, k, operator;

	for( result = [], i = k = 0, j = v.length ; i < j ; i++ ){

		//연산자라면..
		if( op[operator = v.charAt(i)] ){

			//3번상황
			result[result.length] = ex( v.substring( k, i ) );

			//4번상황
			result[result.length] = operator;

			//5번상황
			k = i + 1;
		}

	}

	//6번상황
	result[result.length] = ex( v.substr(k) );
};

토큰을 얻었으니 이제 실제 연산을 해야할 차례입니다. 연산은 연산자 우선순위로 이뤄져야하므로 연산자의 우선순위를 루프돌아야합니다.

연산자 우선순위가 높은 순에서 낮은 순으로 루프를 돌며
토큰의 연산자가 해당 순위에 걸리면
그 연산자를 기준으로 앞, 뒤에 있는 숫자 배열요소를 인자로 보내 계산한뒤
원래있던 값, 연산자, 값의 요소 세개를 결과값 하나로 대체한다.
연산자 우선순위가 끝날 때까지 반복

이것도 간단히 [1, ‘+’, 2, ‘*’, 3] 으로 시뮬레이션 해보죠.

우선 가장 높은 연산자 우선 순위는 2입니다(var op = {‘+’:1,’-‘:1,’*’:2,’/’:2};)
따라서 2를 기준으로 토큰을 루프돌면 ‘+’는 1이므로 해당사항이 없으므로 스킵하고 ‘*’는 2이므로 해당됩니다.
이제 ‘*’를 기준으로 앞뒤 요소를 보니 2와 3입니다. 이를 opf[‘*’]( 2, 3 ) 을 통해 보내면 6이 나옵니다.
원래 있던 2, ‘*’, 3 을 6으로 대체하여 토큰 배열은 [1, ‘+’, 6 ] 이 되었습니다.
이제 연산자 우선순위는 하나 낮아진 1이 되고 +가 이에 해당되어 마찬가지 과정을 거쳐 최종적으로 [7] 이 됩니다.

마지막으로는 토큰 배열의 [0]번 요소를 반환하면 됩니다. 이상을 코드로 보죠.

var op = {'+':1,'-':1,'*':2,'/':2};
var opf = {'+': function(a,b){return a+b;},... },
var ex = function(v){
	var result, i, j, k, operator;
	for( result = [], i = k = 0, j = v.length ; i < j ; i++ ){
		if( op[operator = v.charAt(i)] ){
			result[result.length] = ex( v.substring( k, i ) );
			result[result.length] = operator;
			k = i + 1;
		}
	}
	result[result.length] = ex( v.substr(k) );

	//연산식 처리기
	for( i = 2 ; i > 0 ; i-- ){

		// 1번요소부터 2개씩 건너뛰면서,
		j = 1;

		while( j < result.length ){

			operation = result[j];

			//현재 우선순위와 일치한다면..
			if( op[operation] == i ){

				//세 개를 제거하고,
				result.splice( j - 1, 3,

					//그 자리에 앞 뒤 요소를
					//연산 함수에게 넘긴 결과를 넣는다.
					opf[operation]( result[j-1], result[j+1] )
				);

			}else j += 2; // 아니면 그냥 전진
		}
	}

	//최종적으로 0번 요소 반환
	return result[0];
};

의외로 별거 아닌게 연산자 우선 순위 처리입니다.

결론

이제 모든 조각그림을 맞춰 간단히 사칙연산을 할 수 있는 식처리기를 만들었습니다. 다음과 같은 게 됩니다.

console.log( ex( "1 + 2 * 3") ); //7

머 이제 시작입니다. 다음 시간에는 식의 꽃인 스택처리기를 보도록 살펴보겠습니다.

여태까지 설명한 것을 머지한 코드는 다음과 같습니다.

var VAR = {a:3, b:5};
var op = {'+':1,'-':1,'*':2,'/':2};
var opf = {
	'+':function(a,b){return a+b;},
	'-':function(a,b){return a-b;},
	'*':function(a,b){return a*b;},
	'/':function(a,b){return a/b;}
};
var literal = {'true':true, 'false':false, 'null':null, 'undefined':undefined};
var rnum = /^[-]?[0-9.]+$/;
var rstr = /^(["][^"]*["]|['][^']*['])$/;
var rvar = /^[A-Za-z$_][A-Za-z$_0-9]*$/

var ex = function( v ){
	var result, operator, i, j, k;
	if( v in literal ) return literal[v];
	if( rnum.test(v) ) return parseFloat(v);
	if( rstr.test(v) ) return v.substring( 1, v.length - 1 );
	if( rvar.test(v) ) return VAR[v];
	for( result = [], i = k = 0, j = v.length ; i < j ; i++ ){
		if( op[operator = v.charAt(i)] ){
			result[result.length] = ex( v.substring( k, i ) );
			result[result.length] = operator;
			k = i + 1;
		}
	}
	result[result.length] = ex( v.substr(k) );
	for( i = 2 ; i > 0 ; i-- ){
		j = 1;
		while( j < result.length ){
			operation = result[j];
			if( op[operation] == i )
				result.splice( j - 1, 3, opf[operation]( result[j-1], result[j+1] ) );
			else j += 2; // 아니면 그냥 전진
		}
	}
	return result[0];
};

[js] 식처리기의 제작 # 1 / 3

식 처리기의 형태 결정

리터럴 처리

변수처리기

연산식 처리

결론

이것이 좋아요:

댓글 남기기 응답 취소

[∞] ECMAScript2015 관련 사이트

[책] UML실전에서는 이것만 쓴다 외 6권

[CodeSpitz85] 거침없는 자바스크립트(마감)

[WebGL] WebGL #4 – WebGL 작동 방법의 이해 1

카테고리

recent comment

recent top 5

식 처리기의 형태 결정

리터럴 처리

변수처리기

연산식 처리

결론

이 글 공유하기:

이것이 좋아요:

댓글 남기기 응답 취소

[∞] ECMAScript2015 관련 사이트

[책] UML실전에서는 이것만 쓴다 외 6권

[CodeSpitz85] 거침없는 자바스크립트(마감)

[WebGL] WebGL #4 – WebGL 작동 방법의 이해 1

카테고리

recent comment

recent top 5