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

지난 포스팅에서는 우리가 만든 언어로 만들어진 프로그램을 파싱하는 parser를 만들었다. 이번 포스팅에서는 파싱된 token들을 가지고 AST를 만드는 과정을 소개한다. 또한, 만들어진 AST를 기반으로 bytecode를 emit하는 컴파일러도 제작한다.

 

Abstract Syntax Tree

먼저 AST를 만들기 전에 이 tree의 노드가 될 녀석들을 먼저 구현해야한다. 결과적으로 소스코드가 표현하는 “프로그램”을 나타내는 트리 구조의 AST를 만드는 것이 목표이다. 트리의 각 노드는 프로그램 구성 요소를 나타낸다.

AST Nodes

기본적으로 base class인 Node class를 만들어준다:

Node 클래스는 꽤 간단한데, 해당 노드의 자식 노드들을 담고 있는 children 프로퍼티, 현재 노드에서의 scope를 관장하는 _scope 프로퍼티 등을 가지고 있고, pre-order와 post-order 트리 순회 (tree traversal)를 위한 static method도 제공한다. 또한, 이 Node class를 상속하는 sub class 들도 만들어준다.

Node Class Description Node Class Description
LiteralNode 리터럴 노드. 해당 literal의 값과 올바른 타입을 보관한다. LabelNode 레이블 노드. 해당 label을 보관한다.
VarNode 변수 노드. 해당 변수의 이름을 보관한다. 변수의 타입은 DeclNode 생성시 scope에 추가되어 관리된다. DeclNode 변수 선언 노드. 선언시 타입 및 변수명을 보관한다. 또한, 배열 변수라면 배열의 크기를 저장한다.
BinOpNode 이항 연산자 노드. 해당 이항 연산의 연산자 (op)와 피연산자들 (lhs & rhs)을 보관한다. SubscriptNode 배열 참조 노드. 참조하는 배열의 이름과 인덱스를 나타내는 expression을 보관한다.
AssignNode 대입 연산자 노드. BinOpNode를 상속한다. 해당 대입 연산자에 대한 정보(lhs & rhs)를 기록하고, 대입 동시에 선언하는 경우에는 선언 타입 또한 기록한다. IfNode If 노드. 해당 if문의 조건식, then에 해당하는 노드, 그리고 (존재한다면) else에 해당하는 노드를 보관한다.
UnOpNode 단항 연산자 노드. 해당 단항 연산의 연산자 (op)와 피연산자를 보관한다. WhileNode While 노드. 해당 while문의 조건식과 loop body에 해당하는 노드를 보관한다.
CallNode 함수 호출 노드. Callee와 파라미터들을 보관한다. ForNode For 노드. 해당 for문의 초기화, 조건식, 증감식, 그리고 loop body에 해당하는 노드를 보관한다.
ReturnNode 리턴 노드. 리턴 값을 보관한다. BlockNode Block 노드. { 와 } 사이에 감싸진 코드 블럭을 나타내며 해당 블럭에 포함되는 0개 이상의 노드를 보관한다.
BreakNode Break 노드. BuiltinNode 내장 함수 노드. 녹스 게임 내에 있는 built-in 함수 정보를 보관한다 (함수 번호, 리턴 타입, 함수명, 파라미터).
ContinueNode Continue 노드. FuncNode 함수 노드. 함수 선언시 해당 함수의 리턴 타입, 함수명, 파라미터, 그리고 함수 body를 보관한다.
GotoNode Goto노드. goto 문의 타겟 label을 보관한다. (언어 자체에선 지원하지 않지만, 컴파일 시 흐름제어문 처리를 위해 condition을 보관하여 조건부 goto를 지원한다).  GlobalNode 사실 ProgramNode가 더 정확한 표현이겠지만, 컴파일하는 프로그램 자체를 나타내는 노드. gen_ast 메소드가 리턴하는 wrapper 라고 보면 된다.

Scope

유효범위. 즉, 어떠한 변수나 함수를 선언했을 때 갖는 유효 범위를 알맞게 구성해주어야 한다. 이를 관리하기 위해 각 노드마다 _scope를 가지고 있고, 새로운 변수가 선언될 때마다 추가해주고 새로운 함수가 선언/정의될 때 그에 맞는 새로운 (empty) scope를 지정해주어야 한다. Base class 노드에서도 볼 수 있듯이, 대개는 자신만의 유효범위를 가지지 않고 부모 (parent) 노드의 scope를 상속한다. 사실 scope는 프로그램 전체를 나타내는 AST가 만들어지기 전까지는 완벽하게 알 수 없기 때문에, AST 생성 후 추가적인 pass를 돌려서 scope을 수정한다. 그렇다! 우리 컴파일러는 멀티패스 컴파일러인것이다! -_-b

Scope pass는 다음과 같다:

BUILTINS는 builtins.py에서 pycparser를 이용해서 builtins.h 헤더파일을 파싱해서 빌트인 함수들의 signature를 추출해서 global scope에 넣어준다. builtins.h 파일은 컴파일러 뿐만 아니라 나중에 Visual Studio Code 에디터에서 Nox Script 3.0 언어 지원과 (빌트인 함수 자동완성 및 signature help 기능) doxygen을 이용한 built-in 함수 API 레퍼런스 documentation을 자동생성 하기 위해 독립적인 파일로 관리한다.

Utility/Helper

마지막으로, 만들어지는 AST를 한 눈에 보거나 디버깅하기 쉽게 하기 위해 print_ast 같은 헬퍼 메소드를 만들어주면 유용하다. 구현은 코드에도 나와있지만 간단한 tree visitor를 만들어서 pre-order로 프린트를 해준다.

위의 내용을 토대로 완성된 ast.py는 여기서 확인 가능하다. (이후에 decompiler를 구현할 때 필요한 메타 정보/함수들도 포함 되어있지만 크게 상관 없다.)

 

Parser to AST

이제 필요한 부품(?)들이 (parser + AST 구현체) 다 모였으니 조립을 해야한다.

앞서 말했듯이 pyparsing을 사용하면 이 작업이 무척이나 수월해지는데, 프로세스를 원하는 expression마다 setParseAction으로 콜백을 등록해주면 된다. Parser에게 받는 token들을 이용해서 바로 AST node들로 전환하기 위해, 각 노드 클래스 마다 from_tokens라는 메소드를 구현해놨다. 딱히 뭐 하는건 없고, token들을 읽어 들인 후 알맞게 해당 노드 클래스 오브젝트를 만들어서 반환한다.

여기서 잠깐 이전 포스팅에서 말했던 infixNotation에 대해서 언급할까 한다. Pyparsing은 되부름 하향 구문 분석 (-_-..혹은 recursive descent)이라고 불리는 방식의 parser이다. 이 방식은 문법 정의는 매우 편하고 빠르게 개발할 수 있지만, 문법이 복잡해지면 겁나게 느려진다는 단점이 있다. 이항 연산자 (binary operator) 같은 문법이 이러한 파서를 극한으로 몰고가는 주범인데, 사실 복잡한 문법을 지원하고 싶다면 LR parser를 사용하는게 맞다. 하지만, LR parser는 보통 BNF 등으로 정의된 언어 문법을 토대로 parser 코드를 자동 생성하는 방식으로 사용하기 때문에 솔직히 parser 코드 자체를 사람이 이해하기는 매우 힘들다.. 그리고 parser만 따로 ship할 수 있는게 아니고 parser generator에 대한 의존성이 생겨버리므로, 피할 수 있다면 피하는게 건강에 좋다. 그리고 무엇보다.. 기껏 짜놓은거 버리고 새로 룰을 작성하고 삽질하기가 귀찮았다 (…).

그래서 기존의 pyparsing 내장 infixNotation을 버리고, Shunting-yard 알고리즘으로 대체했다. 이전 포스팅에서 봤던 parser 코드와 이번 코드에 확연한 차이가 보여서 어리둥절 했다면 그 때문일것이다. 완성된 parser.py는 여기서 확인하자.

AST output

AST output of a simple test script

아주 이쁘다. 후훗.

AST Compiler Passes

이대로 완성된 AST를 가져다가 compile할 수 있으면 좋겠지만, 몇 가지 작업을 더 해주어야 한다 ㅠ_ㅠ..

위에서 소개된 scope pass말고도 컴파일하는데 도움을 주는 pass 몇 가지를 더 돌려야 하는데, (dead code elimination과 같은) 코드 최적화는 아니더라도 컴파일 타임 에러 등을 찾기 위한 validation 패스와 if, for, while 등의 흐름제어 노드들을 goto와 label로 바꾸어서 (어떻게 보면 어셈블리처럼) flatten 시켜주는 패스가 필요하다. 두가지 pass 모두 AST traversal을 통해 pre-order와 post-order에 각각 필요한 visitor들을 등록해서 처리한다.

Validation 패스는 우리가 AST 노드들을 만들때 구현해둔 validate 함수를 노드마다 호출하여 exception이 발생하지 않는지 확인하고, flatten 패스는 흐름 제어 노드들을 방문하며 다음과 같은 치환한다:

  • if
    • if (cond) { then_body }
      • goto end_label on cond
      • then_body
      • end_label
    • if (cond) { then_body } else { else_body }
      • goto else_label on cond
      • then_body
      • goto end_label (unconditional)
      • else_label
      • else_body
      • end_label
  • while
    • while (cond) { loop_body }
      • begin_label
      • goto end_label on cond
      • loop_body
      • goto begin_label (unconditional)
      • end_label
  • for
    • for (init; cond; inc) { loop_body }
      • init (init이 존재한다면)
      • begin_label
      • goto end_label on cond
      • loop_body
      • inc_label
      • inc (inc가 존재한다면)
      • goto begin_label (unconditional)
      • end_label

Note: 여기서 cond일 때 점프(goto)하는 이유는, 우리 컴파일러가 bytecode를 emit할 때 jz (jump if zero; 즉, false이면 점프) 코드를 내보낼것이기 때문이다.

Continue는 현재 포함된 loop을 찾은 이후에 for loop 이라면 루프의 inc_label로 가는 goto 노드로 치환해주고 while loop이라면 루프의 begin_label로 가는 goto 노드로 치환해준다. Break는 현재 포함된 loop을 찾은 이후에 루프의 end_label로 가는 goto 노드로 치환해준다.

코드를 다 포함하려면 블로그 글이 너무 길어지니 완성된 passes.py는 여기서 확인하자.

 

AST to Bytecode!

이제 드디어 대망의 시간이다. 바로 녹스 게임 내 엔진이 실행 가능한 bytecode를 생성하는 단계!

사실 어떤 opcode가 어떤 작업을 하는지, 인자로는 어떤것들을 얼마나 받는지 등 리버싱하는것 자체가 꽤나 큰 일이다.. (CTF 많이 해본 사람들은 이 노가다가 얼마나 귀찮은지 알테지.) 하지만 다행히도(?) 룸메이트가 이미 이 작업은 수 년전에 끝내놨기 때문에 ㅋㅋ 이미 만들어져있는 테이블을 보고 쉽게 python으로 만들어나갈 수 있었다.

녹스 맵 파일에 내장되는 스크립트 오브젝트는 bytecode만 있는건 아니다. 함수명 테이블, 스트링 테이블 등의 정보를 담고 있는 헤더가 동봉된다. 스크립트 오브젝트의 포맷은 다음과 같다:

  • “SCRIPT03”
  • “STRG”
  • string 갯수 (DWORD)
  • [string 길이 (DWORD) + string] * string갯수
  • “CODE”
  • 함수 갯수 (DWORD)
  • [
    “FUNC” +
    함수명 길이 (DWORD) + 함수명 +
    0 또는 1 (DWORD, 리턴값이 있으면 1 없으면 0) +
    인자 갯수 (DWORD) +
    “SYMB” +
    지역변수 갯수 +
    0 (DWORD, unused) +
    [지역변수 크기 (DWORD)] * 지역변수 갯수 +
    “DATA” +
    함수 코드 (bytecode) 길이 (DWORD) +
    함수 코드 bytecode data
    ] * 함수 갯수

녹스 스크립트 오브젝트의 bytecode opcode들은 모두 4-byte이다. 이것도 이거지만, 데이터를 패킹하는걸 보면 정말 비효율적이라는것을 알 수 있다 -_-ㅋㅋ

자, 그럼 이제 bytecode를 emit하는 일만 남았으니 시작해보자!

일단 단항 연산과 이항 연산을 하는 opcode 들은 dictionary로 따로 빼둔다 (UOPS_MAP, OPS_MAP 참고).

gen_ast를 통해 AST의 루트 노드를 얻어오고, 위에서 언급한 AST pass들 부터 적용한다:

  • scope_pass: 프로그램 내부의 scope 정의
  • validate_pass: 프로그램 컴파일 타임 오류 체크 (type mismatch 등)
  • flatten_pass: 프로그램 내의 conditional과 loop 치환

녹스 스크립트 오브젝트에서는 함수들마다 고유 인덱스가 있는데 0번 함수에는 항상 사용되지 않는 dummy 함수 하나와 1번 함수에 GLOBAL이라는 함수가 존재해야한다. 스트링 테이블에는 보통 스크립트 내에서 선언된 문자열이 들어가지만, 우리가 컴파일할 떄는 원본 소스코드를 쉽게 추출하기 위해서 0번째 문자열은 항상 소스코드 원본을 담았다.

컴파일을 하면서 각 함수에 대한 정보와 변수에 대한 정보를 알아야 하기 때문에, 관련 정보를 담을 class를 선언하고 사용한다 (Function, Variable 참고).

다음 순서대로 컴파일을 진행한다.

  • 함수 생성 / 정보 수집 (create_func_pass)
    • Pre-order visitor를 통해 AST를 탐색하며 FuncNode를 찾을 때 마다 컴파일러 컨텍스트에 Function 오브젝트를 만들어 넣어준다.
    • 함수명, 함수번호, 인자 갯수, 리턴타입을 기록한다.
  • 전역변수 생성 /정보 수집 (create_globals_pass)
    • Post-order visitor를 통해 DeclNode (예: int x;)나 선언과 동시에 대입하는 AssignNode (예: int x = 7;)에 한해서 해당 노드의 func 프로퍼티 (변수가 속해 있는 함수)가 비어있다면, 즉 global variable (전역변수)라면 GLOBAL 함수로 옮겨준다. (녹스 내부에서는 GLOBAL 함수에서 선언된 변수들이 전역변수가 된다.)
  • 지역변수 생성 / 정보 수집 (create_locals_pass)
    • 전역변수 패스와 마찬가지로 Pre-order visitor를 통해  DeclNode와 AssignNode를 탐색하며 해당 노드가 속한 함수의 locals에 Variable 오브젝트를 만들어 넣어준다.
    • 변수 번호와 크기를 기록한다.
  • 함수 컴파일 / bytecode emit (compile_func_pass)
    • Pre-order visitor로 FuncNode들을 탐색하며 각 함수 노드마다 컴파일 한다.
    • 함수 컴파일 시, 함수 안에 있는 노드들을 탐색하며 각 노드 타입마다 적절한 opcode와 인자값을 사용하여 bytecode를 만든다.

이렇게 스크립트 내에서 정의된 모든 함수들의 bytecode를 emit하고 나서는 위의 오브젝트 파일 포맷대로 데이터를 쓰면 된다.

컴파일러를 사용하기 쉽도록 아래와 같은 간단한 wrapper CLI를 만들어서 돌려준다.

Output

Compiler output

Compiler output

우왓~ 컴파일 완료!!

이제 이 완성된 스크립트 오브젝트를 맵에 첨부시키기만 하면 된다.

mapedit

맵 에디터에서 테스트 용으로 간단한 Wall 오브젝트들을 만들고, 그 중 (7, 7) 좌표에 있는 벽 오브젝트에 Scripted 라는 속성을 주었다. 이렇게 하면 이 벽의 “행동”을 스크립트를 통해 조종할 수 있게 된다. Open 체크박스에 체크를 안했으므로 이 “비밀벽”은 닫힌채로 시작한다.

Demo

compressed

 

성공! 데모를 위해서 맵이 초기화 된 지 3초 정도 이후에 WallOpen을 부르도록 스크립트를 살짝 수정했지만, 위의 데모에서 볼 수 있듯이 닫혀있던 (7, 7) 벽이 열렸다. 맵 에디터에서 우리의 스크립트 오브젝트 파일을 import/export 하는 기능을 추가했는데 이건 컴파일러와는 크게 상관 없으니 넘어가도록 한다.

다음 시리즈에서는 Nox Script 3.0 언어로 스크립트 개발을 쉽고 빠르게 할 수 있도록 Visual Studio Code의 language extension을 이용해서 VS Code에서 우리 언어의 syntax highlighting, auto-completion, function signature help 등등의 기능을 추가해주는 익스텐션을 만들어본다.

 

You may also like...

1 Response

  1. 패닉 says:

    안녕하세요, 녹스유저 패닉입니다.
    이곳에 버그를 제보해도 될지 모르겠습니다.
    ^= &= |= 연산자도 지원되는 것으로 되어 있는데 막상 컴파일러 단에서는 에러가 나기 때문에 사용할 수가 없군요.

Leave a Reply to 패닉 Cancel reply

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