BetaS (Minsu Kim) @k09089 - Tumblr Blog

프로그래밍 언어 개발 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(후위) 출력방식입니다.

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

#언어개발 #langdev #langdev02

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

다음으로는 토큰화와 마킹입니다.

토른화란 무엇일까요?

이전에 우리가 수행했던 print함수 구현하기 과제에서 각각 NAME상태, PARAM상태로 나누었던것을 기억할것입니다.

이때 NAME / PARAM / ENDL 으로 나눈것이 바로 토큰화라고 하고, 일반적으로 다음과 같이 표기합니다.

<name>(<param>);

<와 > 사이에 들어간 내용은 변한다고 볼 수 있겠네요!

이런식으로 수식도 토큰화를 진행하자면 다음과 같습니다.

132+-75.3을 먼저 for문으로 분석할 수 있도록 문자배열로 나타내고 어떠한 규칙에 맞게 상태를 표기하여 다음과 같이 묶습니다.

위처럼 개발자마다 다양한 형태가 존재할 수 있습니다.

그리고 이 구분된 토큰을 리스트(큐)에 집어넣으면 토큰 리스트가 완성되어 집니다.

이때 만들어진 토큰리스트는 나중에 앞쪽부터 차례대로 쓰이게 됩니다. (그렇기 때문에 꼭 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++로 직접 수식트리를 구현해보도록 하겠습니다.

#언어개발 #langdev #langdev02

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

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

언어는 어떤 사회에서 보편적으로 널리 통용되는 의사소통 수단이라고 볼 수 있습니다.

예를 들자면 한국사회에서는 한국어가 통용되고, 영어문화권 사회에서는 영어가 통용되는것 처럼 말이죠.

그렇다면 프로그래밍 언어는 무엇일까요?

프로그래밍 + 언어가 합쳐진 말이라는것은 초등 국어수준만 되어도 쉽게 알 수 있을겁니다.

프로그래밍은 쉽게 말해서 프로그램을 짜는것이라고 볼 수 있고, 언어는 위에서 설명 했습니다.

그렇다면 프로그램을 짜기 위해서 필요한 언어가 프로그래밍 언어라고 볼 수 있겠네요!

다시 정리해보자면 프로그램을 짜기 위해서는 컴퓨터 내지는 기계에게 명령을 내려야 합니다.(프로그래밍의 기본 정의) 그렇기 때문에 컴퓨터와 의사소통을 위해서 정의된 언어라고 볼 수 있습니다.

컴퓨터에 명령을 내리는 방법은 사실 “기계어”나 “어셈블리어”를 통해 직접 명령을 내리는 방법 밖에는 존재하지 않습니다. (사실 그 예전에는 천공카드기법이나 여러가지가 있었을 겁니다.)

하지만 어셈블리어는 어렵고, 기계어는 더더욱 어렵죠, 프로그래밍 하기에도 어렵지만 이미 짜여있는 코드를 분석하기에는 더욱 어렵습니다.

그래서 탄생한게 고급언어의 존재입니다.

고급언어에는 C, C++로 대표되는 C계열 언어와 Java, Python등 많은 언어도 존재하고, 발전하면서 함수형 언어, 이벤트 지향 언어, 객체 지향 언어등 많은 변종이 생겨납니다.

결국 이들의 공통점은 예전에는 그러한 일을 수행하기 위해 코드가 수십줄이 필요하거나, 지원이 안됬지만, 새로 구현하여 지원되게 만들었다는 점 입니다.

즉, 프로그래밍 언어도 우리들의 언어와 마찬가지로 진화와 퇴보를 거친다는점이죠, C가 진화해서 C++이 되었고, C도 그 이전에 여러 언어들 (가령 Ada 등)의 영향을 받아 탄생하게 됩니다.

퇴보의 대표적인 예로는 pointer문법이 있습니다.

C나 C++에서는 포인터 개념으로 쉽게 물리적장치에 접근하고, 메모리 관리를 했습니다.

하지만 경력이 얼마 없는 초보 개발자들에게는 지옥과 다름없었죠, 포인터는 잘못 건드리면 프로그램이 뻗는 주 원인중에 하나이거든요 (하지만 찾아내기도 어렵습니다.)

그래서 Java와 같은 이후 세대 언어들은 과감하게! 포인터나 동적할당 같은 내용을 빼버리고, 내부에서 메모리에 관련된 내용들을 관리하게 됩니다.

그렇기 때문에 최근에는 콜 바이 레퍼런스, 함수 포인터, 동적할당과 할당된 메모리에 해제(free)에 대해서 이해하지 않고, 신경쓰지 않고 쉽게 코딩을 할 수 있게 된거죠 (물론 좋은 프로그래머가 되어서 자신이 짜고있는 코드의 이해도를 높이기 위해서는 배워야할 개념입니다!)

#언어개발 #langdev #langdev01

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

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

이번에는 이런 고급언어들이 어떻게 해서 컴퓨터에 명령을 내리는지 살펴보겠습니다.

컴퓨터가 고급언어들을 이해하기 위해서는 기계어(또는 어셈블리어)로 번역해줄 일종의 “번역가”가 필요합니다.

이런 번역기는 “프로그램”으로써 정의되어 지는데, 우리가 C++을 짤때 사용하는 Visual Studio도 컴파일러라는 번역기를 내장하고 있고, Java도 javac라는 자바 컴파일러가 내장되어있습니다. python도 python인터프리터를 내장하고 있고요

이런 번역프로그램들은 크게 “컴파일러”와 “인터프리터”로 나뉘어 집니다.

컴파일러는 프로그램 제작시점 또는 컴파일 시점에 프로그램을 전부 기계가 이해할 수 있는 문장으로 번역하는 것이고, 인터프리터는 소스코드를 실행파일으로, 기계에 바로 명령을 내리게 됩니다.

컴파일의 대표적 예는 위에서 언급한 C/C++이 있고 인터프리팅의 대표적 예는 Python이 해당됩니다.

컴파일의 경우 인터프리팅에 비해 속도가 매우 빠릅니다. (런타임, 즉 수행시간에 문법을 분석하지 않고 바로바로 실행 가능하기 때문에), 또한 인터프리팅은 소스코드를 그대로 공개하여야 하기 때문에 보안에도 취약한 편이죠.

하지만 인터프리팅 언어도 쉽다는 장점이나, 가벼운 언어를 구성할 수 있다는 장점이 존재하기에 이 두 방법이 널리 쓰이고, 때론 혼용되어서 쓰이기도 합니다.

이번 클래스에서는 컴파일러를 구성하기에는 난이도가 있으므로, 단순한 형태의 인터프리터를 구현하는것을 목표로 하겠습니다.

그렇다면 본격적인 구현에 앞서 우리가 무엇무엇을 구현해야 하는지 살펴 봅시다.

현대의 프로그래밍 언어는 기본적으로 위의 속성들을 가지고 있다고 볼 수 있습니다.

우선 입력과 출력은 기본적으로 되어야합니다, 사용자가 프로그램과 상호작용 하기 위해서는 아주 필수적인 요소이죠.

마찬가지로 연산이 가능해야 합니다.

이런 연산이 가능하기 위해서는 저장공간도 필요하고,

적당히 때에 따라 연산을 달리 수행하려면 로직도 필요합니다.

그리고 프로그램의 구현을 간소화 시켜줄 함수도 당연히 필요합니다.

하지만 이런것들을 전부 지원해도 매번 Ctrl+C, Ctrl+V로 짜야한다면 불편하겠죠?

모듈화, 모듈삽입을 지원하여 반복적인 개발작업을 단순화 시켜야 합니다.

우리는 이 클래스에서 이러한 속성을 가진 언어를 개발할 예정입니다.

언어의 개발은 C++로 이루어 질 태니 C++에 대해 기본적인 문법적 이해가 필요합니다.

여기서는 가볍게 훑는 느낌으로 진행하니 디테일한 내용은 여러 전공서적이나, 온라인 강의등을 추천하는 바입니다.

아래의 내용의 문법을 모른다면 먼저 공부하고 와야합니다!

1. 기본입출력과 파일입출력이 필요합니다. 2. if, else if, else 등의 분기문이 필요합니다. 3. for, while, do~while 등의 반복문이 필요합니다. (특히 for문은 자유자재로 다룰 수 있어야 합니다.) 4. 함수의 선언과 호출이 가능해야하고, parameter와 return value의 이해도 필요합니다. 5. string 헤더의 std string을 이해하고 쓸 수 있어야 합니다. 6. 다차원 배열과 동적할당을 이해할 수 있어야 합니다. 7. 상태 다이어그램에 대해서 이해하여야 합니다.

위 내용중 1~6번은 블로그나 책에서 많이 찾아볼 수 있고, 이 강의에서는 7번 항목만 설명하도록 하겠습니다.