오토마타와 컴파일러 09 - 추상 구문 트리
파스 트리의 한계
파서가 토큰 스트림을 문법 규칙에 따라 분석하면 파스 트리(Parse Tree, 구문 트리)가 만들어진다. 파스 트리는 문법의 모든 유도 과정을 충실히 반영하므로 문법적 정확성을 검증하는 데는 유용하다. 하지만 컴파일러의 이후 단계에서 직접 사용하기에는 불필요한 정보가 너무 많다.
2 + 3 * 4라는 수식의 파스 트리를 생각해 보자. 좌재귀를 제거한 문법을 사용하면 파스 트리에는 E, E', T, T', F 같은 비단말 기호와 괄호 같은 구분 기호가 모두 포함된다. 하지만 컴파일러가 실제로 필요로 하는 정보는 "2와 3*4를 더한다"는 연산 구조뿐이다. 문법을 LL(1)에 맞추기 위해 도입한 E'이나 T' 같은 보조 비단말 기호는 언어의 의미와는 무관한 것이다.
이러한 이유로 컴파일러는 파스 트리 대신 추상 구문 트리(Abstract Syntax Tree, AST)를 사용한다. AST는 파스 트리에서 문법적 세부사항을 제거하고 프로그램의 의미적 구조만을 남긴 트리이다.
파스 트리와 AST의 차이
같은 수식 2 + 3 * 4에 대해 두 트리를 비교해 보자.
파스 트리: AST:
E +
/ | \ / \
T + E 2 *
| | / \
F T 3 4
| / | \
2 F * T'
| |
3 F
|
4파스 트리에는 문법 규칙의 모든 비단말 기호가 존재하지만, AST에는 연산자와 피연산자만 남아 있다. 괄호도 AST에는 나타나지 않는다. (2 + 3) * 4에서 괄호의 역할은 트리 구조 자체가 대신하기 때문이다. AST에서 *의 왼쪽 자식이 + 노드라면, 그것만으로 덧셈이 먼저 수행된다는 의미가 전달되는 것이다.
이러한 추상화는 컴파일러의 나머지 단계를 단순하게 만든다. 의미 분석, 최적화, 코드 생성 단계 모두 AST를 기반으로 동작하므로, AST의 설계가 컴파일러 전체의 품질에 직접적인 영향을 미친다.
AST 노드 설계
AST를 구현하려면 먼저 노드 타입을 설계해야 한다. 각 언어 구성 요소에 대응하는 노드 타입을 정의하되, 문법적 세부사항은 제외하고 의미적으로 필요한 정보만 포함시키는 것이다.
간단한 언어에 대한 AST 노드 타입을 다음과 같이 정의할 수 있다.
from dataclasses import dataclass
from typing import List, Optional
@dataclass
class NumberLit:
value: int
@dataclass
class Identifier:
name: str
@dataclass
class BinaryOp:
op: str # '+', '-', '*', '/'
left: 'Expr'
right: 'Expr'
@dataclass
class UnaryOp:
op: str # '-', '!'
operand: 'Expr'
@dataclass
class Assignment:
target: Identifier
value: 'Expr'
@dataclass
class IfStmt:
condition: 'Expr'
then_body: List['Stmt']
else_body: Optional[List['Stmt']]
@dataclass
class WhileStmt:
condition: 'Expr'
body: List['Stmt']
@dataclass
class FuncDecl:
name: str
params: List[str]
body: List['Stmt']
@dataclass
class FuncCall:
name: str
args: List['Expr']
@dataclass
class ReturnStmt:
value: Optional['Expr']각 노드 타입은 해당 언어 구성 요소를 표현하는 데 필요한 최소한의 정보만 담고 있다. IfStmt에는 괄호나 then 키워드가 없고, 조건과 본문만 있다. BinaryOp에는 우선순위 정보가 없고, 트리의 구조 자체가 연산 순서를 결정한다.
파싱 중 AST 구축
AST는 파서가 문법 규칙을 적용하는 과정에서 함께 구축된다. 재귀 하강 파서에서는 각 파싱 함수가 AST 노드를 반환하도록 작성하면 된다.
def parse_expr(self):
left = self.parse_term()
while self.peek() and self.peek()[0] in ('PLUS', 'MINUS'):
op_token = self.consume(self.peek()[0])
right = self.parse_term()
left = BinaryOp(
op=op_token[1],
left=left,
right=right
)
return left
def parse_term(self):
left = self.parse_factor()
while self.peek() and self.peek()[0] in ('STAR', 'SLASH'):
op_token = self.consume(self.peek()[0])
right = self.parse_factor()
left = BinaryOp(
op=op_token[1],
left=left,
right=right
)
return left
def parse_factor(self):
token = self.peek()
if token[0] == 'NUMBER':
self.consume('NUMBER')
return NumberLit(value=int(token[1]))
elif token[0] == 'IDENT':
self.consume('IDENT')
return Identifier(name=token[1])
elif token[0] == 'LPAREN':
self.consume('LPAREN')
node = self.parse_expr()
self.consume('RPAREN')
return node
raise SyntaxError('Unexpected token')이 코드에서 주목할 점이 두 가지이다. 첫째, while 루프를 사용하여 좌결합 연산을 올바르게 처리한다. 2 + 3 + 4는 BinaryOp('+', BinaryOp('+', 2, 3), 4)로 구성되어 왼쪽부터 계산되는 구조를 만드는 것이다. 둘째, 괄호를 만나면 내부 수식을 파싱한 결과를 그대로 반환하므로 괄호 자체는 AST에 나타나지 않는다.
파서 생성기에서는 각 문법 규칙의 액션으로 AST 노드 생성 코드를 작성한다. Yacc/Bison에서 $$ = new BinaryOp('+', $1, $3);와 같은 형태로 리듀스 시 AST 노드를 만드는 것이 이에 해당한다.
구문 단위별 AST 예시
프로그래밍 언어의 주요 구성 요소가 AST에서 어떻게 표현되는지 살펴보자.
수식: a + b * c
BinaryOp('+')
/ \
Identifier('a') BinaryOp('*')
/ \
Identifier('b') Identifier('c')트리 구조 자체가 *가 +보다 먼저 계산됨을 나타낸다.
조건문: if (x > 0) { return x; } else { return -x; }
IfStmt
├── condition: BinaryOp('>')
│ ├── Identifier('x')
│ └── NumberLit(0)
├── then_body: [ReturnStmt(Identifier('x'))]
└── else_body: [ReturnStmt(UnaryOp('-', Identifier('x')))]함수 선언: function add(a, b) { return a + b; }
FuncDecl
├── name: "add"
├── params: ["a", "b"]
└── body: [ReturnStmt(BinaryOp('+',
Identifier('a'),
Identifier('b')))]이처럼 AST는 소스 코드의 구문적 장식을 모두 벗겨내고 프로그램의 논리적 구조를 명확하게 드러낸다.
비지터 패턴을 이용한 트리 순회
AST가 구축된 후에는 다양한 목적으로 트리를 순회해야 한다. 타입 검사, 최적화, 코드 생성 등 각 단계가 AST를 순회하면서 정보를 수집하거나 트리를 변환하는 것이다.
이때 가장 널리 사용되는 설계 패턴이 비지터 패턴(Visitor Pattern)이다. 노드 타입에 대한 처리 로직을 트리 구조 자체와 분리함으로써, 새로운 분석 단계를 추가할 때 기존 AST 노드 클래스를 수정할 필요가 없게 만드는 것이다.
class ASTVisitor:
def visit(self, node):
method_name = f'visit_{type(node).__name__}'
visitor = getattr(self, method_name, self.generic_visit)
return visitor(node)
def generic_visit(self, node):
raise NotImplementedError(f'No visitor for {type(node).__name__}')
class Evaluator(ASTVisitor):
def visit_NumberLit(self, node):
return node.value
def visit_BinaryOp(self, node):
left = self.visit(node.left)
right = self.visit(node.right)
if node.op == '+': return left + right
if node.op == '-': return left - right
if node.op == '*': return left * right
if node.op == '/': return left // right
class PrettyPrinter(ASTVisitor):
def visit_NumberLit(self, node):
return str(node.value)
def visit_BinaryOp(self, node):
left = self.visit(node.left)
right = self.visit(node.right)
return f'({left} {node.op} {right})'Evaluator와 PrettyPrinter는 같은 AST를 순회하지만 완전히 다른 결과를 생성한다. 새로운 분석 단계가 필요하면 ASTVisitor를 상속받는 새 클래스를 작성하기만 하면 된다. AST 노드 클래스를 변경할 필요가 없으므로, 컴파일러의 각 단계가 독립적으로 개발되고 유지될 수 있는 것이다.
프론트엔드와 백엔드의 다리
AST는 컴파일러 아키텍처에서 프론트엔드와 백엔드를 연결하는 핵심적인 역할을 한다. 프론트엔드(렉서, 파서, 의미 분석)는 소스 코드를 AST로 변환하고, 백엔드(최적화, 코드 생성)는 AST에서 출발하여 목적 코드를 생성한다.
소스 코드 → [렉서] → [파서] → AST → [의미 분석] → 수식 AST → [최적화] → [코드 생성] → 목적 코드이 구조의 장점은 프론트엔드와 백엔드를 독립적으로 교체할 수 있다는 것이다. 같은 백엔드에 다른 언어의 프론트엔드를 연결하면 새로운 언어를 지원할 수 있고, 같은 프론트엔드에 다른 백엔드를 연결하면 다른 아키텍처용 코드를 생성할 수 있다. LLVM이 수십 개의 언어와 수십 개의 타겟 아키텍처를 지원할 수 있는 것이 바로 이 원리 덕분이다.
실제로는 AST에서 바로 목적 코드를 생성하기보다, AST를 더 낮은 수준의 중간 표현(Intermediate Representation, IR)으로 변환한 뒤 최적화와 코드 생성을 수행하는 것이 일반적이다. 하지만 AST 자체가 소스 수준의 가장 중요한 중간 표현이라는 점은 변함이 없다.
다음 포스트에서는 AST에 대해 수행되는 의미 분석(Semantic Analysis)을 살펴본다.