JS 제너레이터로 스택오버플로 피하기
“모나딕 파서”글에서 만든 파서 같은 형태를 Recursive Descent Parser 라고 한다. 재귀적 문법 구조를 처리하는 파서를 직접 만든다고 했을 때 제일 구현하기 쉬운 방법 중 하나다. 문법에 따라 거의 기계적으로 만들 수 있기 때문이다.
그런데 이름에도 드러나듯 이 방법은 재귀 호출을 사용하고, 파싱하고자 하는 입력이 깊게 중첩된 경우 스택오버플로 에러를 유발할 수도 있다. 회피 방법은 RD 스타일의 파서 대신 직접 스택 처리를 해주면 되는데, 이렇게 되면 RD 파서 만큼의 직관적인 코드 대신 조금 더 복잡해진다.
여기도 JS 제너레이터를 등장시킬 수 있다. 직접 스택을 관리하는 건 맞는데 RD 파서 형태를 유지할 수 있어서 두 마리 토끼를 잡는 셈이다.
먼저 재귀호출로 인한 스택오버플로를 재현하기 위해 간단한 RD 파서를 하나 만들어보자. 파서가 처리할 입력은 간단한 재귀 문법으로 [], (), {}, [()], {()()[]} 처럼 쌍이 맞는 괄호 문자열이다. (이번에는 모나딕 파서 대신 일반적인 명령형 스타일로 작성할 것이다.)
아래는 중첩괄호 문장의 문법이다. (문법은 Parsing Expression Grammer 표기를 빌렸다.)
parens <- paren* -- zero or more
paren <- p1 / p2 / p3 -- choice
p1 <- '(' parens ')' -- sequence
p2 <- '[' parens ']'
p3 <- '{' parens '}'문법 룰을 좀더 간결하게 한 줄로 나타낼 수도 있겠지만 재귀 호출 스택에 압박을 가하기 위해 여러 단계로 나눠봤다.
각 룰은 파싱 함수 하나로 쉽게 변환 가능하다. parens <- paren*룰에 해당하는 parens()함수는 paren() 함수를 반복 호출하여 그 결과를 모으면 된다.
function parens() {
let result = [];
while (true) {
const r = paren();
if (r === FAIL) break;
result.push(r);
}
return result;
}paren <- p1 / p2 / p3 라는 규칙은 괄호의 세 종류 중 하나를 나타내는데, 왼쪽 우선순위가 있다. 이 경우 paren() 함수는 각 파서를 순서대로 호출하되 처음으로 성공한 것을 선택하면 된다.
function paren() {
let r;
r = p1();
if (r !== FAIL) return r;
r = p2();
if (r !== FAIL) return r;
return p3();
}p1 <- ‘(‘ parens ‘)’ 라는 규칙이 재귀적으로 괄호 안에 또다른 괄호들이 들어올 수 있음을 나타낸다. 여는 괄호 문자가 일치한 다음 재귀적으로 parens() 를 호출하고, 그 다음에 닫는 괄호가 나와야 전체가 성공한다. 여기서는 마지막 단계에서 실패했을 때 전체가 실패하므로 파싱 중인 상태를 처음으로 되돌리는 것만 조심하면 된다.
function p1() {
const p = _pos; // parsing position 을 저장한다.
let r;
let result = [];
r = char('(');
if (r !== FAIL) {
result.push(r);
r = parens(); // 바로 여기 재귀 호출!
if (r !== FAIL) {
result.push(r);
r = char(')');
if (r !== FAIL) {
result.push(r);
return result;
}
}
}
_pos = p;
return FAIL;
}글자 하나가 일치하는지 확인하는 char(c) 함수는 현재 파싱 위치에 해당 문자가 있는지 확인하면 된다.
function char(c) {
if (_pos < _input.length && _input[_pos] === c) {
_pos++;
return c;
}
return FAIL;
}p2(), p3() 도 위처럼 구현하고 나면 끝이다. 모두 문법으로부터 기계적으로 옮긴 수준이다. 물론 p1(), p2(), p3() 에 나타난 중복은 seq(() => char('('), parens, () => char(')') 와 같이 순차적 연결을 처리하는 seq 도움 함수를 만들어서 단순하게 만들 수 있다.
문법의 root 규칙인 parens에 해당하는 함수를 호출하는 드라이버 함수를 만들어서 동작을 확인해보자.
const FAIL = {};
let _pos;
let _input;function parse(input) {
_input = input;
_pos = 0; const r = parens();
if (r === FAIL || _pos !== _input.length)
throw new Error("parse error");
return r;
}
작은 입력에 대해서 잘 동작한다. 하지만 괄호가 한번 중첩할 때마다 다음처럼 호출 스택이 자라난다.
parse() // 입력: (((((((((((((((...
parens()
paren()
p1() // 첫괄호
parens()
paren()
p1() // 두번째 괄호
parens()
paren()
p1() // 세번째 괄호
...대개 수천 정도의 호출 깊이를 지원하므로 입력 길이만 키우면 쉽게 스택오버플로를 만들 수 있다. (코드#1)
function long(nest) {
let s = "";
for (let i=0; i<nest; i++) s = '(' + s + ')';
return s;
}
console.log(parse(long(10000)));RangeError: Maximum call stack size exceeded
at paren (rd.js:21:15)
at parens (rd.js:15:15)
at p1 (rd.js:36:9)
at paren (rd.js:23:7)
at parens (rd.js:15:15)
at p1 (rd.js:36:9)
at paren (rd.js:23:7)
힘들게 파서까지 만들어서 문제를 재현했다. 이제 해결 방안을 찾아보자.
이렇게 호출 스택이 쌓이는 것을 회피하는 방법 중 하나가 트램폴리닝이다. 트램폴리닝은 결과 대신 반환된 함수를 드라이버 함수가 실행시켜주는 방식이다. 예를 들어 쉽게 루프로 변환할 수 없는 상호 재귀 함수 even/odd 를 보자. 물론 이렇게 짝수/홀수를 판별할 일은 없지만, even(100000)으로 쉽게 스택오버플로를 만들 수 있다. (코드 #2)
function even(n) {
if (n === 0) return true;
else return odd(n-1);
}
function odd(n) {
if (n === 0) return false;
else return even(n-1);
}위 함수는 트램폴리닝을 적용하면 다음처럼 바뀐다.
function even(n) {
if (n === 0) return true;
else return () => odd(n-1);
}
function odd(n) {
if (n === 0) return false;
else return () => even(n-1);
}이 경우는 트램폴린을 튕겨줄 드라이버 함수가 필요하다. (코드 #3)
function trampoline(f) {
while (typeof f === 'function') {
f = f();
}
return f;
}그런데 트램폴리닝은 꼬리 호출을 변환하기는 쉬워도 다른 경우는 변형하기 어렵다. 우리가 구현한 파서의 parens() 함수는 paren()을 꼬리호출하는 대신 중간에 반복 호출하여 배열에 값을 쌓아간다. 즉 실제로 “스택” 역할을 할 무언가가 필요하다. 그런데 트램폴리닝의 드라이버 함수는 스택은 나몰라라 하므로 적용할 수 없다.
(업데이트: 트램폴린 비슷하게 CPS로 바꿔서 해결할 수도 있다. 하지만 모양이 많이 바뀐다.)
제너레이터를 이용해보자. 제너레이터는 자신의 로컬 상태를 저장하면서 멈출 수 있다. 그리고 필요에 따라 멈출 지점에서 실행을 이어갈 수 있다.
parens() 파싱 함수가 직접 paren()을 호출하는 것은 호출 스택에 로컬 상태를 저장하며 스택이 한 층 자라나게 되지만, parens() 파싱 함수를 제너레이터로 만들면 paren() 을 호출해야 하는 지점에서 yield로 멈추고 부모 함수로 돌아갈 수 있다. 호출 스택이 자라나지 않게 된다. yield를 처리할 드라이버는 parens() 가 결과를 반환하는 대신 다른 파싱 함수인 paren()을 yield 한 것을 확인하여 직접 paren()으로 진입한다. 이 때 paren()이 결과를 반환하면 드라이버는 자신이 직접 관리하는 스택에서 parens() 를 꺼내어 paren()의 결과로 실행을 재개한다. 제너레이터로 구현한 parens() 파싱함수를 보자.
function* parens() {
let result = [];
while (true) {
const r = yield paren();
if (r === FAIL) break;
result.push(r);
}
return result;
}원래의 parens() 와 바뀐 부분을 찾아보자. 함수 대신 제너레이터 함수가 되었고, paren() 호출 앞에 yield가 하나 붙었을 뿐이다.
다른 파싱 함수들(p1(), p2(), … 등)도 이렇게 제너레이터 함수로 바꾸고 다른 파싱 함수를 호출할 일이 있으면 그 앞에 yield 만 붙이면 된다. 원래 RD 파서의 장점이 그대로 유지된다.
(주의! “모나딕 파서”에서도 파서 함수를 제너레이터 함수로 만들었다. 그런데, 거기서 제너레이터의 역할은 지연 리스트 효과를 위한 것. 즉 Non-deterministic 파서를 만들기 위한 것이었다. 여기서 파서 함수들을 제너레이터로 만든 것은 콜스택 대신 코루틴처럼 사용하기 위한 것이다. 모나딕 파서에서는 드라이버가 따로 필요없었다.)
그러면 이렇게 바뀐 파싱 함수를 호출하는 드라이버를 살펴보자. (코드 #4)
function parse(input) {
_input = input;
_pos = 0; let stack = [parens()]; // 초기 스택
let result;
while (stack.length) {
let parser = stack[stack.length - 1];
const { value, done } = parser.next(result);
if (done) {
stack.pop();
result = value;
} else {
stack.push(value); // 콜스택 대신 직접 스택에 푸시
result = undefined;
}
} if (result === FAIL || _pos < _input.length) {
throw new Error('parse error');
}
return result;
}
기본적으로는 트램폴리닝 방법과 동일하지만 스택을 직접 관리하고 있다. Callee의 결과를 Caller에게 전달하는 것도 담당한다. 이제 실제 함수 호출스택은 자라나지 않는다. 스택 대신 힙을 사용할 뿐이다.
(업데이트: 콜 관계의 함수들을 제너레이터로 바꾸다보니 하위 함수에서 예외를 던져도 상위 함수에서 이를 잡을 수 없다. 예외를 사용하고 싶다면 디스패치 루프에서 이것까지 추가로 고려해줘야 한다. 참고)
예를 들어 char()파서에서 콜스택을 확인해보자.
function* char(c) {
throw new Error(); at char (rd-parser.js:94:9)
at char.next (<anonymous>)
at parse (rd-parser.js:14:36)
at Object.<anonymous> (rd-parser.js:110:13)
at Module._compile (module.js:612:30)
at Object.Module._extensions..js (module.js:623:10)
at Module.load (module.js:531:32)
at tryModuleLoad (module.js:494:12)
at Function.Module._load (module.js:486:3)
at Function.Module.runMain (module.js:653:10)
원래의 호출 관계는 parser() → parens() → paren() → p1() → char() 순서인데, 호출 스택을 보면 parse()에서 바로 char.next()로 진입하는 것을 확인할 수 있다.
이제 Recursive Descent Parser를 사용한다고 해서 스택오버플로를 걱정할 필요는 없다.
