5일만에 뚝딱 스크립트 언어 만들기 PGLight (1/5)

오랜만에 PG어 관련해서 글을 쓰네요.

몇년전에 컴파일러나 파싱 이론 같은거 아무것도 모를때 그냥 왠지 언어 새로 만드는게 그렇게 멋있어 보여서 밑천도 없이 달려들엇던게 기억이 납니다. 언어 이름은 간지나게 PG어. 왜 PG어인지는...

예전에 PG어 컴파일러 비스무리한거까지 만들고 구현체도 있긴 있었습니다만, 제가 원하던 이상적인 언어 모습이 아니라서 그냥 버려버렸습니다. 그런데 갑자기 포니게임을 개발하던 도중, 엔진에서 사용할 스크립트언어가 필요하단 것을 깨닫고 PG어를 경량화시킨 PGLight를 개발하게 됐어요. 원래는 Lua를 스크립트 언어로 사용할 예정이었는데 다음과 같은 문제점 때문에 Lua를 버리고 자체개발하게 되었습니다.

1. 이해할수 없는 가비지 컬렉션 : 버그인지 몰라도 함수가 자주 호출되다 보면 스택이 쌓이고... 그러다가 일정 수준을 넘으면 가비지 컬렉션이 시작되는데, 이놈이 때때로 무한루프에 빠져버립니다. 그래서 종종 게임을 멈추게 만들었죠.

2. 루아 함수를 c언어 쪽에서 다룰 방법이 없음 : 루아함수를 c언어쪽에서 호출하는 방법은 오직 글로벌에 선언된 함수를 이름을 이용해서 가지고 와서 호출하는 것 밖에 없습니다. 저는 트리거링 함수로 루아의 익명함수를 인자로 넘겨주고 싶었는데, c언어쪽에서는 익명함수로 된 객체를 받을 방법이 없었기에 좌절했죠.

3. 딱히 없음... : 실은 Lua가 C/C++에 붙여쓰기에는 너무 편했기에 저것만 해결되면 여차저차 써보려고했는데 끄끝내 해결 못해서 결국 자체 스크립트 언어 개발에 들어갔습니다. (이게 다 잉여기때문이다)

서론이 길었구요, 언어 파서와 실행기를 짜는건 생각보다 어려운 일이 아닙니다. (잘 만드는게 어렵죠. 그냥 만드는 건...) 개발한 과정을 글로 기록해서 남겨보려고합니다. 혹시나 스크립트 언어 개발하시는 분들에게 참고가 될지도 모르니.

제일 먼저 한 일은 언어컨셉을 잡는거였습니다.

원래 PG어는 컴파일 형식 언어로 정적타이핑을 기반으로 하고 있었는데요, 아시다시피 스크립트 언어에 정적타이핑은 잘 어울리지 않죠. (그리고 정적타이핑보다는 동적타이핑이 훨씬 컴파일러 짜기 쉬워요. 타입 검사 따위를 안해도 되니까요) 그래서 동적타입으로 결정.

처음에는 LLVM이나 기타 백엔드를 이용해서 아예 JIT로 컴파일해버리는 것까지도 생각했는데, 너무 시간 오래걸릴까봐 생략하고 깔끔하게, 바이트코드로 컴파일하고 스택가상머신에서 작동시키기로 했어요.

(사실 어지간한건 루아에서 다 배워왔어요.)

자, 이제 문법을 설정해야죠. BNF 표기법으로 표기하면 불명확하던 언어 문법이 상세하게 정리됩니다.

배커스 나우어 표기법을 모르시는 분들은 아쉽지만 공부하고 오셔야할거에요. 

워낙 c style빠인지라, 문법은 c언어 비슷하게 짰습니다.

안 궁금하신 분들을 위해 가려놨어요

<name_type> ::= <identifier> ("as" <type>)?

<decl_var> ::= "var" <name_type> ("=" <expr>)?

<decl_var_semi> ::= <decl_var> ";"

<decl_func> ::= "function" <identifier> "(" (<name_type> ( "," <name_type>)*)? ")" ("as" <type>)?
    "{" <sentence>* "}"

<simple_sentence> ::= <call>
    | <assign>

<sentence> ::= <if>
    | <for>
    | <while>
    | <return>
    | <yield>
    | <continue>
    | <break>
    | <decl_var_semi>
    | <decl_func>
    | <simple_sentence>

<assign> ::= <lexpr> "=" <expr> ";"

<lexpr> ::= <par_lexpr>  ( ("[" <expr> "]") | ("." <identifier>) )*

<par_lexpr> ::= <identifier> | '(' <lexpr> ')'

<call> ::= <expr> ";"

<return> ::= "return" <expr> ";"

<yield> ::= "yield" <expr> ";"

<continue> ::= "continue" <literal>? ";"

<break> ::= "break" <literal>? ";"

<if> ::= "if" "(" <expr> ")" "{" <sentence>* "}"
    ("else" "if" "(" <expr> ")" "{" <sentence>* "}")*
    ("else" "{" <sentence>* "}")?

<while> ::= "while" "(" <simple_sentence> ")"
    "{" <sentence>* "}"
    ("done" "{" <sentence>* "}")?
    ("else" "{" <sentence>* "}")?

<for_basic> ::= <decl_var> ";" <expr> ";" <simple_sentence>
<for_iter> ::= <decl_var> "in" <expr>

<for> ::= "for" "(" <for_basic> | <for_iter> ")"
    "{" <sentence>* "}"


<expr> ::= <not_expr>

<not_expr> ::= <or_expr>
    | "not" <not_expr>

<or_expr> ::= <and_expr> ("or" <and_expr>)*

<and_expr> ::= <cmp_expr> ("and" <cmp_expr>)*

<cmp_op> ::= "=="
    | "!="
    | ">"
    | "<"
    | ">="
    | "<="

<cmp_expr> ::= <add_expr> ( <cmp_op> <add_expr>)?

<add_expr> ::= <mul_expr> ( ("+" | "-") <mul_expr>)*

<mul_expr> ::= <sign_expr> ( ("*" | "/")  <sign_expr>)*

<sign_expr> ::= <pow_expr>
    | "-"? <sign_exp>

<pow_expr> ::= (<a_expr> "^")* <a_expr>

<a_expr> ::= <par_expr>
    ( ("[" <expr> "]") | ("." <identifier>) | ( "(" ( <expr> ("," <expr>)* )? ")" ))*

<par_expr> ::= <literal> | <identifier> | "this"
    | '(' <expr> ')' | <lambda_expr> | <function_expr>

<literal> ::= <simple_literal>
    | <array_literal>
    | <dict_literal>

<array_literal> ::= "[" ( <expr> ("," <expr>)* )? "]"

<dict_literal> ::= "{" ( <expr> '=' <expr> ("," <expr> '=' <expr>)* )? "}"

<lambda_expr> ::= <name_type>  | ( "(" (<name_type> ( "," <name_type>)*)? ")" )  ":" <expr>

<function_expr> ::= "function" "(" (<name_type> ( "," <name_type>)*)? ")" ("as" <type>)?
    "{" <sentence>* "}"

실은 BNF표기법은 별로 어려운거 없어요. 정규표현식만 잘 안다면...

정규표현식을 모르더라도 ? * | 만 알면 거의 다 이해가능하고, 표현가능하지요.

a | b 는 a 혹은 b와 일치한다는 거에요.

a? 는 a 와 일치하거나 혹은 공백과 일치한다는 것이구요,

a* 는 a가 0번 이상 반복(즉 공백이거나 a, aa, aaa, aaaa ...)된다

a+  는 a가 1번 이상 반복(a, aa, aaa, aaaa ...)된다는 뜻.

예를 들어 변수 선언을 볼까요?

변수 선언은 var 이름 [as 타입] [= 초기화값]; 과 같은 형태로 쓰이니깐([]안은 생략가능) 다음과 같이 BFN로 표기할 수 있습니다.

<decl_var> ::= "var" <identifier> ("as" <type>)? ("=" <expr>)? ";"

이와 같은 방법으로 온갖 자잘한 부분까지 다 BFN로 작성하다보면 위처럼 방대해지게 됩니다. (실은 저것도 짧은 편이죠...)

변수 선언은 var 이름 as 타입; 으로 하구요, 함수 선언은 function 이름(인자...) as 타입 {...}으로 합니다.

원래는 as 타입 부분으로 타입을 명시할 수도 있게 하려고 했는데 구현하다보니 귀찮아서 버렸습니다.

특이할 만한 건, 함수 객체와 람다 표현식을 지원한다는 겁니다. 함수형 프로그래밍 언어의 성격을 대폭 가지고 있는 PG어 특성상 당연한 거지만, 얘는 경량화 버전이다보니 구현시에 까다로운(실은 귀찮은) 타입 유추나 함수 합성 같은 기능은 버렸어요.

x: x 1 처럼 한줄로 익명 함수를 선언할 수도 있고, 자바스크립트에서 쓰이는것마냥 function(){~~} 처럼 여러줄로 익명함수를 선언할 수도 있습니다.

예시코드ㅋ

function complex(r, i) { var t = 1; var ret = {}; ret.r = r; ret.i = i; ret.print = function(a) { print(this.r, " + ", this.i, "i"); print(a, t, "\n"); }; ret.norm = function() { return this.r^2 + this.i^2; }; ret.abs = function() { return this.norm() ^ 0.5; }; ret.arg = function() { return math.atan2(this.r, this.i); }; return ret; } var th = thread(function() { var a = 3; var b = 4; /*while(true) {*/ var c = complex(a, b); print(c.norm(), "\n"); print(c.abs(), "\n"); print(c.arg(), "\n"); a = a + 1; b = b + 1; yield null; /*}*/ }); print(th.status(), ", ", th.resume(), "\n"); print(th.status(), ", ", th.resume(), "\n"); print(th.status(), ", ", th.resume(), "\n");

코드만 보니 굉장히 javascript 비슷하네요. (뭔가 새로운거 도입하는거 보다는 그냥 늘 쓰던거랑 비슷한게 좋아서...)

자, BNF 스타일로 언어 문법을 정리했다면 이제 그대로 파서를 짜면됩니다. 쉽죠? 파서를 짜는건 꽤나 기계적인 작업이라서 아예 자동화한 툴(lex & yacc)도 있습니다만, 영웅은 도구따위 쓰지 않으므로, 맨땅에 헤딩하듯 파서를 짜봤습니다.

파서 짜는 이야기는 다음으로.