Log Stash

A* 알고리즘은 게임 프로그래밍 해본 사람이라면 꽤나 많이 들어본 길찾기 알고리즘일것이라고 생각한다. 좌표를 이용해서 탐색할 수 있기도 해서 그런건 아닐까. 구현하기도 많이 어려운것도 아니고. 알고리즘에 대한 자세한 설명은 다른 블로그에서도 많이 하니까 넘기고. 간단히 설명하자면 A* 알고리즘에서는 출발좌표에서 시작해서 주변 좌표마다(8방위, 4방위 마음대로) 평가값을 매기고, 가장 작은 평가값을 가진쪽으로 이동하고, 거기에서 또 주변 좌표의 평가값을 매기고... 를 목표 좌표에 닿을때 까지 하는 알고리즘이다. 평가값을 구하는 평가함수를 A*에선 다음과 같은 함수를 사용한다. g(n)은 출발 좌표부터의 현재까지의 거리(비용) h(n)은 현재 좌표에서의 목적지 까지의 예상 거리(비용) 을 나타낸다. 대부분..

컴파일러가 코드를 해석하는 일을 약간 교과서적인 방법으로 몇가지 뭉텅이로 나눠서 생각해보자. 왠만한 컴파일러 관련 책이라면 이런 그림이 들어가 있을거다. 1.Lexical analysis 하나의 긴 복잡한 문자열이라고 볼 수 있는 코드를 의미있는 토큰 단위로 조각조각내는 단계. 예를들어, begin x := m; y := n; call multiply; end. 위의 코드를 토큰들로 나누면 "begin", "x", ":=", ";", "y", ":=", "n", ";", "call", "multiply", ";", "end", ".' 이런 문자열들이 되겠다. 여기에서 의미 없는 문자열들은 전부 무시한다. 공백, 개행, 주석 처럼. 2. Syntax analysis 문법 오류를 검사하는 단계이다. 토큰을 ..

컴파일러 시간에 첫번째 과제로 제출했던 '재귀 하강 파서(Recursive descent parser)로 PL/0 파싱 및 실행'에 대해 정리해놓으려고 한다. 과제를 진행한 순서로 정리한 글이라 초반에 생각을 잘못해서 나중에 좀 괴랄한 방법으로 구현된 부분도 있고, 함수 이름이 중간에 바뀌기도 하고 그렇다. 과제 후기라고 생각하면 될듯. #PL/0 링크 걸어놓은 위키에서도 설명하고 있지만 PL/0는 2가지 언어를 가리키는데, 그 중 하나는 IBM에서 만든 PL/I 언어의 부분집합이고, 다른 하나는 파스칼 언어에서 몇가지 복잡한 기능을 삭제한 연습용 언어이다. 이 중에서 후자를 파싱해보도록 한다. PL/0은 Algorithms + Data Structures = Programs 라는 책에서 처음으로 소개되..