#langdev02

[k09089]

프로그래밍 언어 개발 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++로 직접 수식트리를 구현해보도록 하겠습니다.

[k09089]

프로그래밍 언어 개발 2-1

* 2015년 경희대학교 DASOM 동아리에서 진행된 스터디 내용입니다.

지난시간에 여러 과제들이 나갔습니다.

단어조사는 충분히 했으리라 믿고, FSM과제에 대해서 해설하도록 하겠습니다.

위 그림은 모범답안은 아니지만, 단순하게 표현된 다이어그램이라고 볼 수 있습니다.

앞에서 보여줬던 isN, is I, is C, is E 로 NICE를 판별하는것 보다, 중간중간에 위치한 핵심 어구 (이 경우에는 ‘(’, ‘)’)를 통하여 여기서부터 저기까지는 NAME 상태, 저기서부터는 PARAM상태와 같이 단위를 묶어서 표현하는것이 일반적인 방법입니다.

그리고 이런 문자를 “심볼”이라고 합니다.

자, 그렇다면 다음 과제는 스택과, 큐, 트리에 대해서 조사하는것이였습니다.

스택은 위와 같습니다.

LIFO (Last in, First out)의 성질을 가지는데, 이것은 입출구가 하나인 파이프와도 같습니다.

예를 들자면 프링글스통에 구슬을 집어넣는다고 하면, 첫번째로 집어넣은 구슬을 뽑아내기 위해 마지막에 넣은 구슬부터 차례대로 빼내야 할겁니다.

이때 프링글스 통에 구슬을 집어넣는 행동은 “push” 라고 합니다.

그리고 마지막에 넣은 순서대로 꺼내는 행동을 “pop”이라고 합니다.

C++에서는 pop을 하게되면 꺼낸 아이템이 날아가므로, “top”을 이용해 통의 맨 위에 무엇이 있는지 확인하여야 합니다. 

다음으로 큐 입니다.

아까와 동일하지만 다른 점은 FIFO라는 점입니다.

FIFO는 입출구가 두개라, 각각 한곳은 입구를, 다른곳은 출구를 담당합니다.

이런경우 스택과는 다르게 먼저들어온 아이템은 먼저 나가는 선입선출 구조라는 점입니다.

마찬가지로 아이템을 넣는 행동을 enqueue, 빼는 행동을 dequeue, 가장 끝에 있는 아이템을 front 함수를 이용해 구할 수 있습니다.

마지막으로 트리인데 트리는 스택과 큐와는 조금은 다른 자료구조 입니다.

트리는 left와 right, parent라는 속성을 가지고 있는데, 각각 왼쪽노드, 오른쪽노드, 상위노드(부모노드)를 가르킵니다.

트리를 출력할때는 inorder 출력방식, preorder 출력방식, postorder 출력방식이 존재하는데 각각

왼쪽, 현재, 오른쪽 노드를 출력하는것이 inorder (중위)출력방식

현재, 왼쪽, 오른쪽 노드를 출력하는것이 preorder (전위)출력방식

왼쪽, 오른쪽, 현재 노드를 출력하는것이 postorder(후위) 출력방식입니다.

이중 후위출력방식은 앞으로의 내용에서도 쓰이니 꼭 외워두길 바랍니다.