[Nox] 스크립트 언어 설계 및 컴파일러 만들기 + α (1)

오랜만에 일과는 전혀 상관이 없는.. 하지만 관련 지식과 기술을 사용한 취미겸 사이드 프로젝트를 지난 3일동안 작업했다. 제목에서도 알 수 있듯이 Nox 라는 RPG 게임에 관련된 프로젝트였는데, 애시당초 이 고전(?) 게임을 왜 들여다 본걸까?

 

Nox

일단 Nox는 Westwood Studios에서 만들고 EA가 배급한 윈도우 용 RPG 게임이다. 스토리가 있는 싱글 플레이 모드도 있었고 PvP 등을 할 수 있는 멀티 플레이도 가능했다. 디아블로1 이후에 영감을 받아 나온 게임으로 꽤나 좋은 평가를 받았지만.. 다섯달 이후에 나온 디아블로2의 대성공 속에 사람들이 기억속에서 잊혀지게 된다 ㅠㅠ.. 하지만 내 룸메이트를 비롯한 매니아 층이 존재했고 그..그들은 16여년이 지난 지금까지도 가끔씩 서버를 운영하며 플레이를 한다는…

나를 포함한 보안쪽에 있는 사람들중 대다수가 그렇듯이 어릴 때 게임 분석을 하면서 자연스레 리버싱에 입문하게 되는 경우가 많은데, 내 룸메이트 역시 고등학교 시절부터 게임에 대한 리버싱 및 알아낸 정보를 이용해 맵 에디터 제작 등, 취미 생활로 이런 저런 툴들을 많이 만들어왔다. 그 중 하나가 맵 스크립트 지원인데, 사실 이때는 리버싱 실력이나 프로그래밍 능력이 지금만큼 없었기 때문에 많이 부족한 (그래도 작동은 얼추 하는?) 결과물을 만들었다고 한다.

 

Current State

최근에 Nox 게임 포럼 (아직도 90년대 스타일 웹사이트.. ㄷㄷ) 에서 몇몇 한국 분들이 아직 맵 제작 및 플레이를 하신다는걸 알게되었고 우리는 사용되고 있는 스크립트 언어 스펙과 열악한 에디터 환경을 보고 경악을 금치 못했..읍읍. 빌트인 함수 하이라이팅 되는거에 감사해야하나 ㅠㅠ..

Old Script Editor

그래서, 주말동안 이 부분을 완전 개혁(!)하기로 마음 먹었다. 정확히는 게임 내부에 있는 스크립팅 엔진에서 돌아갈 bytecode 생성을 위한 컴파일러 개발 및 스크립트 언어 개발 환경을 구축하는 작업이었다. 게임에서 사용되는 맵 파일 마다 퀘스트 이벤트 발생, 이펙트 발생 등의 동적인 요소들을 위한 로직을 담기 위해 bytecode를 삽입할 수 있는데, 사실 이 부분은 게임 개발사에서 내부적으로만 사용하기 위해 넣어둔 기능이기 때문에 WoW와 같은 최신 게임들에서 제공하는 ‘스크립팅’과는 조금 차이가 있다. 따로 API나 스크립트 스펙을 공개하지 않았기 때문에 다 손수 리버싱을 해야한다는 점.

Typical VM Loop

Opcode를 핸들링하는 스크립트 엔진 (vm loop)

 

일단 작업 시작전에 알아두어야 할 점들은 다음과 같았다:

  • 게임 맵에 첨부되는 이 스크립트 코드 (bytecode)는 stack-based VM으로 실행된다. (즉, register-based가 아니란 얘기.)
  • 200여개의 built-in 함수들이 존재한다 — 물론 이에 대한 공개 API는 존재하지 않는다.
  • 지원하는 자료형 type은 int, float, string, 그리고 object이다.
  • 배열, 지역 변수 및 전역 변수를 지원한다.

일단 기존 스크립트 “언어”가 해괴망측(…)했기 때문에 아예 처음부터 새로 설계하기로 했다. 큰 그림을 그려보자면, 세 단계로 구성될 수 있다.

  1. 새로운 스크립트 언어 설계: 사용하기 편하고/친근하고 strict typing을 가진 언어로 만들어야 함 — C-like 언어를 구상.
  2. Parser 구현: 새로 만든 언어로 작성된 소스코드를 파싱할 수 있는 파서를 제작해야 함 — Syntax checking 및 AST 생성을 이 단계에서 한다.
  3. Compiler 구현: 만들어진 AST를 기반으로 올바른 bytecode를 내보내는 컴파일러를 작성해야 함 — 보통은 assembly/assembler 단계를 거치지만, 우리는 그냥 바로 코드를 emit 한다.

우린 둘다 python 빠돌이들이기 때문에 처음부터 끝까지 python을 사용해서 컴파일러 제작을 했다.

 

Nox Script 3.0

초창기에 룸메이트&크루가 만든 스크립트 언어를 1.0이라고 보고, 그 사이에 누군가 언어를 약간 변형시킨것을 2.0이라고 판단하여.. 이번에 작업한 새로운 언어는 3.0이라고 정하게 되었다.

‘C와 비슷하면서 스크립팅에 적합한 훨씬 간략한 언어가 없을까’ 하며 찾아보던 중 “Pwan“이라는 스크립트 언어를 발견하게 되었는데, 언어 특성상 그대로 사용하지는 못하고 여러 부분 영감을 얻어 Nox 스크립트 환경에 맞게 언어를 설계했다.

타입

  • int
  • float
  • string
  • object

우선 언어에서 사용가능한 타입은 총 네가지다. int와 float 타입은 C와 같고, string 타입은 내부적으로는 string table안에 보관되는 문자열을 레퍼런스 한다. 마지막으로 object 타입은 opaque 타입으로서 Nox내의 객체와는 다른 녀석이다. Nox Script에서 게임 객체는 항상 게임 내의 object id (int 타입)를 통해 레퍼런스 된다. 즉, 내부적으로는 object는 int로 관리되지만 잘못 사용하는 경우를 방지하기 위해 strict typing을 통해서 object 타입으로 관리하기로 결정. 이 opaque 타입을 상대로 적용할 수 있는 연산자는 대입 연산자 (=), 동등 연산자 (==), 그리고 비등 연산자 (!=) 뿐이다.

연산자

Supported Operators

int나 float 타입에 대해선 기본적 산술 연산자들 및 비교 연산자들이 사용 가능하고, bitwise나 logical 연산은 int 타입에서만 가능하다. 또한, 문자열을 합칠 수 있는 + 연산자와 += 연산자도 지원한다. 사실 여기서 지원하는 모든 타입/연산자들 각각에 해당하는 VM opcode가 존재하기 때문에, 굳이 컴파일러 단에서 우리가 구현할 필요는 없었다. (맞는 opcode를 emit하고 데이터를 스택에 push 해주기만 하면 되니까)

Literal (리터럴)

Nox Script 3.0에서는 총 세 종류의 리터럴 타입을 제공한다: int, float, 그리고 문자열. 문법은 C와 비슷하다.

int형 리터럴은 8진수, 10진수, 혹은 16진수로 되어있는 숫자이고, 16진수는 0x로 시작하고 8진수는 0으로 시작한다. 또한, true와 false 키워드도 제공하는데, 이는 각각 1과 0의 값을 가진다.

float형 리터럴은 보통의 부동소숫점인 1.0 형태나 e-notation을 사용하는 1.0e2 형태로 사용할 수 있다. float형 리터럴은 항상 소숫점 (.)이 존재해야한다. 타입캐스팅을 지원하지 않기 떄문에 int형과 float형 사이에 모호성을 없애야하기 때문이다.

마지막으로 string 리터럴은 C에서의 스트링과 같다. 한 쌍의 큰 따옴표 (“)로 감싸져 있으며, escape이 필요한 문자는 백슬래쉬(\)를 사용하여 escape가능하다.

변수

C와 마찬가지로 모든 변수는 정적 타입을 가진다. 또한, 전역 혹은 함수 범위 (scope) 내에서 동일한 변수 명은 가질 수 없다. 함수 밖에서 정의된 변수는 전역 변수로 처리되며, 어느 함수에서든 값을 참조하거나 변경할 수 있다. 함수 내의 변수는 block scope (즉, { } 안 마다 새로운 범위 설정)을 가진다.

변수 선언은 타입 변수명; 으로 한다 (예: int var;). 또한, 변수 선언과 동시에 값을 할당할 수 있다: 타입 변수명 = 값;

배열 변수 선언도 가능하다: 타입 변수명[배열크기]; 배열의 크기는 1보다 커야한다 (Nox 내부 구현 때문에..)

함수

모든 함수는 global scope에 정의되며, 함수명은 유니크해야하고 built-in 함수명과 겹칠 수 없다. 함수는 값을 리턴할 수 있고 인자를 받을 수 있다. 함수가 아무것도 리턴하지 않는다면 void 타입으로 명시해야한다.

함수 선언 역시 C와 비슷하다: 타입 함수명(타입 인자1, 타입 인자2, …) { }

정의된 함수는 호출될 수 있고 문법은 다음과 같다: 함수명(인자1, 인자2, …)

만약 호출하는 함수가 값을 리턴한다면 expression 내에서 사용가능하다. (예: if (myFunc(123, “abcd”)) {})

제어 흐름

기본적인 제어문들이 제공된다: if/else문, for문, 그리고 while문. 또한, label 정의와 goto문이 제공되지만 정말 필요할 때가 아니면 사용을 권장하지 않는다.

 

Pyparsing

이제 언어의 스펙을 정했으므로, 이 언어를 파싱할 파서를 제작해야한다. 이번 프로젝트에는 pyparsing을 사용하기로 했다.

Pyparsing의 기본적인 기능들을 나열해보자면:

  • yacc이나 bison 같이 BNF를 기반으로 parser 코드를 생성하는 것과는 다르게, 언어 문법 정의 및 파싱을 동시에 할 수 있다.
  • 파싱된 결과물인 token들을 setParseAction 등의 함수를 통해 처리할 수 있다.
  • Packrat 기능을 활성화 함으로서 내부적으로 memoization을 통해 (간단한 코드의) 파싱 속도를 매우 높일 수 있다.

사용법은 꽤 간단하다.

일단 있는 그대로 읽혀야할 리터럴 캐릭터/문자열들은 Literal로 매칭할 수 있다. Keyword는Literal과 비슷하지만, 바로 이후에 공백문자 (whitespace) 혹은 non-keyword가 와야한다. 이 외에도 Word 나 Regex 등을 통해 변수/함수명 (identifier)를 매칭할 수 있다.

제공하는 연산자는 크게 다음과 같다:

  • | (MatchFirst): 첫번째로 매칭되는 녀석을 반환한다.
  • + (And): 각 expression들이 모두 매칭되어야 하고, 매칭되는 녀석을 통째로 반환한다 (파싱된 각 expression의 내용이 담긴 list).
  •  (And): +와 같지만 backtracking을 하지 않는다 (만약 매칭에 실패했을 경우 다른 룰을 통해 매칭하려고 시도하지 않는다. 에러 표시에 유용).
  • ~ (NotAny): 주어진 expression이 포함되지 않아야 한다.
  • <<: 해당 expression을 Forward를 사용하여 선정의 (forward declaration) 했을 경우에 실제 정의/룰을 추가한다.

연산자 우선 순위가 중요한 operator 같은 경우에는 infixNotation을 사용해서 간단히 처리 가능하다. 하지만, 나중 시리즈에서 얘기하겠지만 이것 때문에 빅엿을 먹는 사태가 발생한다 ㅠㅠ.. 사용하긴 쉽고 직관적이지만 치명적으로 느리다.. (이건 뭐 Packrat으로 해결되는 수준이 아님..) Operator precedence 라인이 한 줄 추가 될 때마다 거의 기하 급수적으로 느려진다. 급기야 1400 여줄 짜리 소스를 파싱하는데만 30초 이상 걸리게 되어서 나중에 이 부분은 다익스트라 횽님이 발명하신 Shunting-yard 알고리즘을 사용해서 구현하게 된다…orz

Group을 사용하면 매칭을 통해 파싱된 녀석들을 한 그룹(list)으로 묶어준다.

Recursive grammar (재귀 문법)을 정의해야할 때, Forward를 이용해서 사용되는 특정 expression을 정의하기 전에 미리 선언할 수 있다.

또한, Suppress로 감싸게 되면 매칭이 되어도 해당 토큰은 반환되지 않는다. 말그대로 그냥 읽씹(?) 당한다. 신택스 상으로는 중요하지만 시맨틱 상에선 중요하지 않은 괄호나 세미콜론 등에 사용하기에 좋다.

간단한 코드로 테스팅을 해보자!

parser.py

우왕! 파싱 성공! +_+

100여줄도 안되는 코드로 C-like (사실 C보다는 훠어어얼씬 간단하지만..) 언어 소스코드를 파싱할 수 있는 파서를 작성 가능하다는 점이 경이롭다. 파이썬 만세. Pyparsing 만세. (하지만 넌 나에게 나중에 똥을 주었지.)

 

Next: Source Code to AST (Abstract Syntax Tree)

몇 번의 시행착오 및 테스팅을 통해 마침내 parser를 완성하고 나면, setParseAction을 통해 파싱된 token들을 가지고 뭘 할건지 정해주어야 한다.

우리는 컴파일러를 만들 계획이므로(!) 파싱 결과를 가지고 AST node들을 만들어줘야 한다.
그렇다. 이제 겨우 시작일 뿐이다. (주륵)

AST node 설계 및 구현은 다음 시리즈에서 계속…!!

 

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *