복원력 있는 LL/Pratt 스타일 파서에서 토큰을 소비하지 않아 생기는 무한 루프/재귀를, 파서가 실제로 전진했는지 단언(assert)하는 간단한 API로 빠르게 잡아내는 방법.
2025년 12월 28일
크리스마스 연휴에 흔히 그렇듯, 또 하나의 장난감 파서를 쓰고 있다. 대략적으로는 Resilient LL Parsing Tutorial을 따른다. 내가 복원력(resilience)이 꼭 필요해서라기보다는, 첫 오류에서 바로 중단(bail out)하는 것보다 구문 트리와 진단(diagnostics) 모음을 만들어 내는 쪽이 문제에 더 자연스럽게 맞는다고 느끼기 때문이다.
이 접근법에서 실용적으로 조심해야 할 함정 하나는 무한 루프/재귀다. 복원력은 때때로 토큰을 _소비하지 않는 것_을 의미하고, 그걸 루프나 Pratt 재귀 호출에서 해버리면 디버그하기 짜증 나는 오류를 만나게 된다:
running 1 test from ./src/corpus_test.ts
corpus ...Task test deno test --allow-read=./src/corpus --allow-write=./src/corpus "--" "--update"
Check src/corpus_test.ts
<--- Last few GCs --->
4,[26641:0x9d1574000] 7390 ms: Mark-Compact (reduce) 3924.9 (3927.3) -> 3924.9 (3926.3) MB, pooled: 0.0 MB, 1224.00 / 0.00 ms (+ 0.3 ms in 1 steps since start of marking, biggest step 0.3 ms, walltime since start of marking 1232 ms) (average mu = 0.200,[26641:0x9d1574000] 8804 ms: Mark-Compact (reduce) 4009.9 (4011.3) -> 4009.9 (4011.3) MB, pooled: 0.0 MB, 1294.67 / 0.00 ms (+ 0.2 ms in 1 steps since start of marking, biggest step 0.2 ms, walltime since start of marking 1302 ms) (average mu = 0.141,
#
# Fatal JavaScript out of memory: Ineffective mark-compacts near heap limit
#
==== C stack trace ===============================
0 deno 0x0000000102ce8404 v8::base::debug::StackTrace::StackTrace() + 24
1 deno 0x0000000102ceeb9c v8::platform::(anonymous namespace)::PrintStackTrace() + 24
2 deno 0x0000000102ce4094 v8::base::FatalOOM(v8::base::OOMType, char const*) + 68
3 deno 0x0000000102d3a7a8 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, v8::OOMDetails const&) + 296
4 deno 0x0000000102f37378 v8::internal::Heap::stack() + 0
5 deno 0x0000000102f3581c v8::internal::Heap::CheckMemoryPressure() + 0
6 deno 0x0000000102ead4f8 v8::internal::StackGuard::HandleInterrupts(v8::internal::StackGuard::InterruptLevel) + 504
7 deno 0x000000010335fe44 v8::internal::Runtime_HandleNoHeapWritesInterrupts(int, unsigned long*, v8::internal::Isolate*) + 304
8 deno 0x00000001043887b4 Builtins_CEntry_Return1_ArgvOnStack_NoBuiltinExit + 84
9 ??? 0x0000000126997874 0x0 + 4942559348
10 ??? 0x000000012698a758 0x0 + 4942505816
...
구체적인 예로, 함수 인자 목록을 아래 같은 코드로 파싱한다고 하자:
const result: ast.Expression[] = [];
p.expect("(");
while (!p.eof() && !p.at(")")) {
result.push(expression(p));
if (!p.at(")")) p.expect(",");
}
p.expect(")");
return result;
여기에는 암묵적인 계약이 있다. 즉 expression은 소스 코드에 오류가 있더라도 최소 한 개의 토큰은 소비해야 한다. 만약 어떤 토큰 때문에 expression이 아무것도 소비하지 않은 채로 빠져나온다면, 위 코드는 영원히 루프를 돌게 되고, 스택 트레이스를 보려면 디버거가 필요해진다!
전통적으로 나는 이 문제를 두 가지 기법의 조합으로 해결해 왔다:
연료(Fuel): 파서는 fuel: Cell<u32> 필드를 갖고, “읽기 전용(readonly)” 룩어헤드 메서드들조차 이 값을 감소시키며, 파서가 토큰을 소비할 때마다 연료를 다시 채운다. Fuel은 파서를 어느 정도 깔끔하게 크래시 내는 데는 도움이 되지만, 보통 크래시는 문제가 있는 함수에서 여러 스택 프레임 떨어진 곳에서 발생한다.
두 번째 기법은, 입력 토큰을 항상 최소 1개 소비하는 함수들과 아무것도 소비하지 않고 빠져나올 수도 있는 함수들의 정신적 지도(mental map)를 유지하는 것이다. 그리고 루프나 재귀 호출을 작성할 때마다 이 지도를 참고해 최소 하나의 “토큰 소비” 함수를 호출하도록 확인한다. 어렵고 실수하기 쉽다!
그런데 오늘, 더 나은 방법을 찾은 것 같다! 기대한 대로 파서가 전진했는지를 단언(assert)할 수 있다. 여기서 작은 이점은 파서가 전진하지 않았다면 즉시 오류가 난다는 점이다. 더 큰 이점은, 이 단언들이 “전진하는 함수들의 정신적 지도”를 소스 코드 안에 실체화해 준다는 것이다. 더 이상 머릿속에만 두지 않아도 된다!
지금 보면 당연한 아이디어처럼 보이지만, 글쎄, 이걸 깨닫는 데 파서를 한두 번 이상은 써야 했다!
구체적으로, 나는 다음과 같은 기본 파서 API를 떠올렸다:
class Parser {
private tokens: ast.Token[];
private index: number = 0;
private advances: number[] = [];
advance_push() {
this.advances.push(this.index);
}
advance_pop() {
const advance = this.advances.pop();
assert(advance !== undefined);
assert(advance < this.index);
}
advance_drop() {
const advance = this.advances.pop();
assert(advance !== undefined);
}
}
그리고 글 처음의 오류로 이어진 버그가 있는 함수는 이것이다:
function expression_pratt(
p: Parser,
left: ast.TokenTag,
): ast.Expression {
let lhs: ast.Expression = expression_delimited(p);
while (p.at("(")) {
lhs = expression_call(p, lhs);
}
while (true) {
const right = p.token();
if (expression_pratt_right_binds_tighter(left, right.tag)) {
const rhs = expression_pratt(p, right.tag);
lhs = {
tag: "ExpressionBinary",
location: right.location,
operator: right.tag as ast.BinaryOperation,
lhs,
rhs,
};
} else {
return lhs;
}
}
}
같은 함수인데, 전진(assertion) 단언을 추가한 버전:
function expression_pratt(
p: Parser,
left: ast.TokenTag,
): ast.Expression {
let lhs: ast.Expression = expression_delimited(p);
while (p.at("(")) {
lhs = expression_call(p, lhs);
}
while (true) {
p.advance_push();
const right = p.token();
if (expression_pratt_right_binds_tighter(left, right.tag)) {
const rhs = expression_pratt(p, right.tag);
lhs = {
tag: "ExpressionBinary",
location: right.location,
operator: rhs.tag as ast.BinaryOperation,
lhs,
rhs,
};
} else {
p.advance_drop();
return lhs;
}
p.advance_pop();
}
}
새로운 오류 메시지:
running 1 test from ./src/corpus_test.ts
corpus ... FAILED (11ms)
ERRORS
corpus => ./src/corpus_test.ts:47:6
error: Error: assertion failed
if (!condition) throw new Error("assertion failed");
^
at assert (./src/stdx.ts:2:25)
at Parser.advance_pop (./src/parse.ts:132:5)
at expression_pratt (./src/parse_grammar.ts:169:7)
at expression (./src/parse_grammar.ts:143:10)
at expression_block (./src/parse_grammar.ts:305:21)
at declaration_fun (./src/parse_grammar.ts:73:7)
at declaration (./src/parse_grammar.ts:25:12)
at Module.file (./src/parse_grammar.ts:10:15)
at Module.parse (./src/parse.ts:13:18)
at ast_dump (./src/corpus_test.ts:85:22)
그리고 수정:
while (true) {
p.advance_push();
const right = p.token();
if (expression_pratt_right_binds_tighter(left, right.tag)) {
p.bump();
const rhs = expression_pratt(p, right.tag);
lhs = {
tag: "ExpressionBinary",
location: right.location,
operator: rhs.tag as ast.BinaryOperation,
lhs,
rhs,
};
} else {
p.advance_drop();
return lhs;
}
p.advance_pop();
}