토큰만으로는 부족하다
이전 글에서 토크나이저가 코드를 토큰으로 쪼개는 과정을 살펴봤습니다. 하지만 토큰 스트림은 평면적 입니다 — 단순한 나열일 뿐, 코드의 구조를 표현하지 못합니다.
[keyword:let] [identifier:message] [operator:=] [string:"hello"] [punctuation:;]이 토큰들이 "변수 선언문"이라는 것, message가 변수 이름이고 "hello"가 초기값이라는 것은 토큰 스트림만 봐서는 알 수 없습니다. 이 구조적 의미 를 파악하는 것이 파서의 역할입니다.
AST란 무엇인가
파서 (Parser) 는 토큰 스트림을 AST (Abstract Syntax Tree, 추상 구문 트리) 로 변환합니다.
AST는 코드의 구조를 트리로 표현한 것입니다. "추상"이라고 부르는 이유는 괄호나 세미콜론 같은 문법적 장치를 생략 하기 때문입니다 — 트리의 구조 자체가 이미 우선순위와 범위를 표현하므로, 이런 기호들은 더 이상 필요 없습니다.
변수 선언문의 AST
가장 단순한 예시부터 봅시다. 아래 시각화에서 let message = "hello";가 어떤 트리로 변환되는지 단계별로 확인하세요.
주목할 점:
- Program 이 항상 최상위 노드입니다. 모든 코드는 이 안에 들어갑니다
- VariableDeclaration 은 선언의 종류 (
let,const,var) 를 알고 있습니다 - VariableDeclarator 가 "무엇을 = 무엇으로" 라는 관계를 표현합니다
- 세미콜론은 AST에 나타나지 않습니다 — 이것이 "추상"의 의미입니다
함수 선언의 AST
조금 더 복잡한 코드를 봅시다. 함수 선언은 이름, 매개변수, 본문이라는 여러 부분을 트리로 표현해야 합니다.
트리가 깊어졌습니다:
- FunctionDeclaration 이 함수 전체를 감쌉니다
- 매개변수
a,b는 params 배열에 Identifier로 들어갑니다 - BlockStatement 가
{ }로 감싼 함수 본문을 표현합니다 a + b는 BinaryExpression 으로, 연산자와 좌/우 피연산자를 자식으로 갖습니다
파서는 어떻게 트리를 만드는가
파서의 핵심 알고리즘은 재귀 하강 파싱 (Recursive Descent Parsing) 입니다. 이름이 거창하지만 원리는 단순합니다:
1. 현재 토큰을 보고 무엇을 기대할지 결정한다
function 토큰을 만나면 → "함수 선언이 시작되겠구나"
let 토큰을 만나면 → "변수 선언이 시작되겠구나"
return 토큰을 만나면 → "반환문이 시작되겠구나"
2. 기대하는 구조에 맞게 토큰을 소비한다
함수 선언을 기대한다면:
- 이름 (identifier) 을 읽고
(를 확인하고- 매개변수들을 읽고
)를 확인하고{를 확인하고- 본문을 파싱하고 (여기서 재귀 가 일어납니다)
}를 확인합니다
3. 본문 안에서 다시 1번으로 돌아간다
함수 본문 안에서 return을 만나면 반환문 파싱 함수를 호출합니다. 그 안에서 a + b를 만나면 표현식 파싱 함수를 호출합니다. 이런 식으로 함수가 함수를 호출하며 트리를 만들어 갑니다.
연산자 우선순위
a + b * c를 파싱할 때, 파서는 *가 +보다 우선순위가 높다는 것을 알아야 합니다. 결과 AST는 이렇게 됩니다:
BinaryExpression (+)
├── Identifier (a)
└── BinaryExpression (*)
├── Identifier (b)
└── Identifier (c)트리 구조 자체가 우선순위를 표현합니다 — b * c가 먼저 계산되고, 그 결과에 a를 더합니다. 괄호 없이도 순서가 명확합니다.
V8은 이를 위해 Pratt 파싱 (Top-Down Operator Precedence) 이라는 기법을 사용합니다. 각 연산자에 우선순위 숫자를 부여하고, 현재 연산자보다 높은 우선순위의 연산자가 나오면 먼저 처리합니다.
V8의 파서 특징
- Pre-parser — 즉시 실행되지 않는 함수는 얕게만 파싱합니다. 문법 오류가 있는지, 변수가 어떤 스코프에 속하는지 정도만 파악하고, 전체 AST는 만들지 않습니다
- Lazy compilation — 함수가 실제로 호출될 때 비로소 완전한 파싱이 이루어집니다. 대부분의 웹 페이지에서 로드 시점에 실행되는 코드는 전체의 일부이므로, 이 전략은 큰 성능 이점을 줍니다
- 즉시 에러 보고 — ECMAScript 명세에 따라 문법 오류를 만나면 즉시 SyntaxError를 발생시킵니다. IDE의 파서와 달리 여러 오류를 한 번에 보고하지 않습니다
다음 단계
AST는 코드의 의미를 정확하게 표현하지만, CPU가 직접 실행할 수 있는 형태는 아닙니다. 다음 글에서는 V8의 Ignition 인터프리터 가 AST를 바이트코드로 변환하는 과정을 살펴보겠습니다.