프로그래밍 언어 개발 2-2
다음으로는 토큰화와 마킹입니다.
토른화란 무엇일까요?
이전에 우리가 수행했던 print함수 구현하기 과제에서 각각 NAME상태, PARAM상태로 나누었던것을 기억할것입니다.
이때 NAME / PARAM / ENDL 으로 나눈것이 바로 토큰화라고 하고, 일반적으로 다음과 같이 표기합니다.
<name>(<param>);
<와 > 사이에 들어간 내용은 변한다고 볼 수 있겠네요!
이런식으로 수식도 토큰화를 진행하자면 다음과 같습니다.
132+-75.3을 먼저 for문으로 분석할 수 있도록 문자배열로 나타내고 어떠한 규칙에 맞게 상태를 표기하여 다음과 같이 묶습니다.
<digit>+<digit> 또는 <digit><oper><-digit> 또는 <int><oper><float>
위처럼 개발자마다 다양한 형태가 존재할 수 있습니다.
그리고 이 구분된 토큰을 리스트(큐)에 집어넣으면 토큰 리스트가 완성되어 집니다.
이때 만들어진 토큰리스트는 나중에 앞쪽부터 차례대로 쓰이게 됩니다. (그렇기 때문에 꼭 queue로 구현하여야 합니다)
마킹은 look forward라고도 불리는 기법입니다.
전체 구문을 분석하다가 되돌아오기 위해 사용하는 기법인데, 예를들어 숫자가 들어오면 int라고 토큰화 하다가, 중간에 소숫점('.')이 나오면 첫 숫자로 돌아가서 float이라고 토큰화 한다고 가정합니다.
아까의 132+-75.3에서는 첫 문자가 ‘-’이므로 해당 위치의 인덱스를 어딘가에 기억해놓으면 되겠군요!
하지만 돌아갈 위치가 여러개라면 변수를 여러개 만들어야하는 상황이 생깁니다.
그래서 우리는 stack을 사용하게 됩니다.
stack을 사용하게되면 스택의 성질에 의해 마치 ctrl+z(실행취소)와 같이 최근에 저장된것 부터 상태를 되돌리게 됩니다.
그렇다면 본격적으로 수식처리를 해봅시다.
프로그래밍 언어의 8할은 연산으로 구성되어 있다고 해도 과언이 아닙니다.
그 이유는 초창기 컴퓨터의 이름에서도 살펴볼 수 있듯이 “Compute”해주는 기계 즉, 계산기라고 볼 수 있습니다.
컴퓨터가 하는 연산중에 대표적인게 수식처리, 함수처리, 변수처리, 논리처리 등 다양한것이 있는데, 그중 가장 기초가 되는 수식처리를 살펴보도록 하겠습니다.
컴퓨터의 출발은 사람이 일일히 계산하기 어려운 복잡한 수식을 빠르고 정확하게(오류없이) 계산하는것을 목적으로 출발하였습니다. 하지만 이를 컴퓨터가 이해할 수 있게 표현하려면 기계어로 기술할 수 밖에 없습니다.
하지만 요즘의 프로그래밍 언어들은 거의 다 사람이 작성하는 “1+1″과 같은 표현식을 이해하고 있습니다.
과연 어떻게 그렇게 될까요?
바로 그 비밀은 수식트리에 있습니다.
수식트리는 방금전에 배운 “토큰화 기법”을 이용하여 구성할 수 있는데 다음과 같은 형식입니다.
이렇게 구성된 수식트리는 다음과 같은 속성을 가집니다.
1. 가장 먼저 처리될 연산은 가장 하위에 위치한다. 2. 가장 나중에 처리될 연산은 맨 위(최상단, root)에 위치한다. 3. 연산자의 left와 right 는 항상 존재한다. (노드가 full인 상태라고 한다.) 4. 숫자에는 left와 right가 존재하지 않는다. 5. 부호는 연산자로 취급되어지지 않고, 숫자에 포함되어 취급된다.
왜 이렇게 수식트리를 구성하여 계산할까요?
마찬가지로 방금전에 배운 후위처리방식(postorder)와 연관이 되어있습니다.
수식트리를 postorder로 출력한다면 다음과 같이 보이게 됩니다.
1 3 + 5 -
평소 보던 수식과는 많이 다릅니다! 바로 이런 수식 형태를 RPN (Reverse Polish Notation) 이라고 합니다.
컴퓨터의 메모리는 기본적으로 STACK구조를 띄고 있습니다. (프로그래밍 입문시간때 stack 메모리와 heap 메모리가 있다는 점에서도 알 수 있듯이)
연산을 처리하기 위해서는 먼저 어떤 값을 연산할지 “피연산자"를 알고 있어야 합니다. 즉, 이는 메모리상에 피연산자(연산값)이 미리 올라가 있음을 뜻합니다.
그래서 피연산자들을 먼저 명시 한 후, 연산을 수행하게 되는 것이죠.
RPN해석의 규칙을 살펴봅시다.
1. 숫자는 메모리 스택에 push 한다. 2. 연산자는 메모리 스택에서 2개의 값을 pop하여 연산을 수행한다. 3. 연산을 수행 한 후 결과값을 다시 메모리에 push 한다.
그렇다면 1 3 + 5 - 로 구성된 수식은 어떻게 처리될까요?
#1 - stack : [1] <- push 1 #2 - stack : [1, 3] <- push 2 #3 - stack : [] <- pop 3 as a, pop 1 as b #4 - stack : [4] <- push add b, a #5 - stack : [4, 5] <- push 5 #6 - stack : [] <- pop 5 as a pop 4 as b #7 - stack : [-1] <- push sub b, a
연산을 모두 마치고 스택에 남은 값이 -1이므로 위 수식의 결과는 “-1″이 됩니다. 여기서 주의할점은 연산은 항상 b - a, b + a 와 같이 b, a의 순서로 진행된다는 점입니다.
그렇다면 +, - 연산이 아닌 (, ) 가 들어가거나, *, / 와 같이 우선순위가 다른 연산들은 어떻게 연산자 우선순위를 구현할 수 있을까요?
바로 수식트리를 구현하면서 아래와 같은 규칙을 따르면 됩니다.
자! 그렇다면 이제 연습문제로 아래의 내용을 각각 과제로 풀어오면 됩니다.
1) 수식트리로 표현하고 (규칙 맞춰서), step by step 으로 설명하기 2) RPN으로 표현하고 step by step 으로 결과 계산하기
다음시간에는 C++로 직접 수식트리를 구현해보도록 하겠습니다.