파싱 (Parsing) - tokenization, recursive descent, expression

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 2분 · 751자/단어 #algorithm #string #parsing #tokenization #recursive-descent

정의

파싱 은 입력 문자열을 구조화된 표현 (AST) 으로 변환하는 과정. 컴파일러/인터프리터의 첫 단계. 세 단계: Tokenization (lexing) → Parsing (AST) → Evaluation.

문제 상황과 동기

"3 + 5 * (2 - 1)" 계산. 단순 좌→우 읽으면 (3+5)*2-1 = 15 (오답).

naive: 연산자 우선순위와 괄호 처리 불가.
Recursive descent: 문법 규칙 (BNF) 을 재귀 함수로 변환. 각 parse 함수가 자신의 우선순위를 처리.

핵심 통찰: BNF 문법을 그대로 재귀 함수로 옮기면, 우선순위와 결합법칙이 함수 호출 순서로 자연 해결.

시각화

핵심 아이디어

Tokenization

입력: "3 + 5 * (2 - 1)"
토큰: [NUM(3), '+', NUM(5), '*', '(', NUM(2), '-', NUM(1), ')']

BNF Grammer

expr    → term (('+' | '-') term)*
term    → factor (('*' | '/') factor)*
factor  → NUMBER | '(' expr ')'

Recursive Descent

parse_expr():
    left = parse_term()
    while peek in ('+', '-'):
        op = consume()
        right = parse_term()
        left = Node(op, left, right)
    return left

parse_term():
    left = parse_factor()
    while peek in ('*', '/'):
        op = consume(); right = parse_factor()
        left = Node(op, left, right)
    return left

parse_factor():
    if peek == NUM: return Leaf(consume().val)
    if peek == '(': consume('('); node = parse_expr(); consume(')'); return node

invariant: 각 parse 함수는 자신의 우선순위 노드를 소비. 다음 토큰은 더 높은 우선순위의 첫 토큰.

구현

// Recursive descent expression parser
#include <bits/stdc++.h>
using namespace std;
struct Token { enum { NUM, OP, LP, RP } type; char op; int val; };
vector<Token> tokenize(const string& s) {
  vector<Token> res;
  for (size_t i = 0; i < s.size(); i++) {
      if (s[i] == ' ') continue;
      if (isdigit(s[i])) {
          int v = 0;
          while (i < s.size() && isdigit(s[i])) v = v*10 + (s[i++]-'0');
          res.push_back({Token::NUM, 0, v}); i--;
      } else if (s[i] == '(') res.push_back({Token::LP, 0, 0});
      else if (s[i] == ')') res.push_back({Token::RP, 0, 0});
      else res.push_back({Token::OP, s[i], 0});
  }
  return res;
}
struct Node { char op; int val; Node *l, *r;
  Node(int v) : op(0), val(v), l(0), r(0) {}
  Node(char o, Node* a, Node* b) : op(o), val(0), l(a), r(b) {}
};
int eval(Node* n) {
  if (!n->op) return n->val;
  int l = eval(n->l), r = eval(n->r);
  if (n->op == '+') return l+r; if (n->op == '-') return l-r;
  if (n->op == '*') return l*r; return l/r;
}
class Parser {
  vector<Token> t; int pos = 0;
  Token peek() { return t[pos]; }
  Token consume() { return t[pos++]; }
  Node* expr();
  Node* term();
  Node* factor();
public:
  Parser(vector<Token> tok) : t(tok) {}
  int run() { return eval(expr()); }
};
Node* Parser::expr() {
  Node* left = term();
  while (peek().type == Token::OP && (peek().op == '+' || peek().op == '-'))
      { char op = consume().op; left = new Node(op, left, term()); }
  return left;
}
Node* Parser::term() {
  Node* left = factor();
  while (peek().type == Token::OP && (peek().op == '*' || peek().op == '/'))
      { char op = consume().op; left = new Node(op, left, factor()); }
  return left;
}
Node* Parser::factor() {
  if (peek().type == Token::NUM) return new Node(consume().val);
  consume(); Node* n = expr(); consume(); return n;
}
int main() {
  string s; getline(cin, s);
  cout << Parser(tokenize(s)).run() << "\n";
}

# Recursive descent expression parser
import sys
def tokenize(s):
  tokens, i = [], 0
  while i < len(s):
      if s[i] == ' ': i += 1; continue
      if s[i].isdigit():
          j = i
          while j < len(s) and s[j].isdigit(): j += 1
          tokens.append(('NUM', int(s[i:j]))); i = j
      else: tokens.append(('OP', s[i])); i += 1
  return tokens
class Parser:
  def __init__(self, tok): self.tok = tok; self.pos = 0
  def peek(self):
      return self.tok[self.pos] if self.pos < len(self.tok) else None
  def consume(self): t = self.tok[self.pos]; self.pos += 1; return t
  def parse_expr(self):
      left = self.parse_term()
      while self.peek() and self.peek()[1] in '+-':
          op = self.consume()[1]; right = self.parse_term()
          left = (op, left, right)
      return left
  def parse_term(self):
      left = self.parse_factor()
      while self.peek() and self.peek()[1] in '*/':
          op = self.consume()[1]; right = self.parse_factor()
          left = (op, left, right)
      return left
  def parse_factor(self):
      t = self.peek()
      if t[0] == 'NUM': return ('NUM', self.consume()[1])
      self.consume(); node = self.parse_expr(); self.consume(); return node
def eval_ast(n):
  if n[0] == 'NUM': return n[1]
  l, r = eval_ast(n[1]), eval_ast(n[2])
  if n[0] == '+': return l+r;  if n[0] == '-': return l-r
  if n[0] == '*': return l*r;  return l//r
s = sys.stdin.readline().strip()
print(eval_ast(Parser(tokenize(s)).parse_expr()))

stdin

3 + 5 * (2 - 1)

결과

복잡도

항목	값
Tokenization	O(L) 시간, O(L) 공간
Recursive Descent	O(L) 시간, O(D) 호출 스택 (D = nesting depth)
전체	O(L) 시간, O(L) 공간

변형 / 활용

1. Pratt Parsing

Recursive descent 일반화. 각 토큰에 binding power (precedence) 할당. 연산자 추가가 쉽고 코드 중복 적음.

2. Shunting Yard (Dijkstra)

중위 → 후위 표기법 변환. 연산자 스택만 사용. Recursive descent 없이 O(L).

3. PEG / Packrat

Parsing Expression Grammar. | 에 순서가 있어 모호성 해결. Memoization 으로 O(L) 보장.

4. LR / LALR (Yacc, Bison)

Bottom-up. 더 넓은 문법 클래스 허용. 대규모 언어 (C, Java) 에 사용.

함정

1. 좌측 재귀 (Left Recursion)

expr → expr '+' term 은 recursive descent 에서 무한 재귀. expr → term ('+' term)* 로 변환 필요.

2. 연산자 우선순위 누락

expr/term/factor 분리 안 하면 3 + 5 * 2 를 (3+5)*2 = 16 으로 계산.

3. 괄호 불일치

닫는 괄호 누락 시 stack overflow. consume(')') 에서 검증 필요.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1918	후위 표기식	35.2%	kokoa-lab
BOJ 1935	후위 표기식 2	42.1%	kokoa-lab
BOJ 1662	압축	28.7%	kokoa-lab
BOJ 2504	괄호의 값	30.5%	kokoa-lab

참고

이 글의 용어 (3개)

문자열 (String)algorithm: 정의 문자열 (String) 은 문자(character)의 순서 있는 나열. 프로그래밍에서는 연속된 메모리에 저장된 문자 배열 로 구현되며, 각 문자는 ASCII(7비트) 또는 …
스택 (Stack)algorithm: 정의 스택 (Stack) 은 LIFO (Last In, First Out) 순서로 원소를 관리하는 추상 자료구조입니다. , , 세 연산만 제공하며, 가장 최근 삽입된 원소만 접근…
정규 표현식 (Regular Expression, Regex)algorithm: 정의 정규 표현식 (Regular Expression) 은 문자열 패턴을 형식 언어로 표현한 표기법. Stephen Kleene 이 1956년 정규 언어 (regular lang…