Ruby 템플릿 심층 탐구: 파서(Parser) 구현하기

Ruby 템플릿(Templating) 시리즈에 돌아왔습니다. 지난 시간에 렉서(lexer)를 완성했으니, 이제 다음 단계인 파서(parser)로 넘어가 보겠습니다.

지난 글에서는 문자열 보간(string interpolation)을 살펴본 후, 나만의 템플릿 언어를 만드는 작업에 착수했습니다. 그 첫걸음으로 템플릿을 읽어 토큰(token) 스트림으로 변환하는 렉서를 구현했죠. 오늘은 이와 짝을 이루는 파서를 직접 구현하면서, 약간의 언어 이론도 함께 맛보겠습니다.

그럼 시작해 볼까요?

추상 구문 트리(Abstract Syntax Tree)

먼저 간단한 예제 템플릿인 Welcome to {{name}}을 다시 살펴보겠습니다. 렉서로 이 문자열을 토큰화하면 다음과 같은 토큰 목록이 만들어집니다.

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

궁극적으로 우리가 원하는 것은 템플릿을 평가(evaluate)해서 표현식을 실제 값으로 치환하는 것입니다. 여기에 난이도를 더하기 위해 반복문과 조건문을 지원하는 복잡한 블록 표현식(block expression)까지 평가할 수 있어야 합니다.

이를 위해서는 템플릿의 논리적 구조를 기술하는 추상 구문 트리(AST)를 생성해야 합니다. 이 트리는 다른 노드를 참조하거나 토큰에서 가져온 추가 데이터를 저장하는 노드들로 구성됩니다.

앞선 간단한 예제에서 원하는 추상 구문 트리는 다음과 같은 모습입니다.

문법(Grammar) 정의하기

문법을 정의하려면 먼저 언어의 이론적 기반부터 짚고 넘어가야 합니다. 다른 프로그래밍 언어와 마찬가지로 우리의 템플릿 언어도 문맥 자유 언어(context-free language)이므로, 문맥 자유 문법으로 기술할 수 있습니다. (위키백과의 상세한 수학적 표기법에 겁먹지 마세요. 개념 자체는 꽤 단순하며, 문법을 표기하는 더 개발자 친화적인 방법도 있습니다.)

문맥 자유 문법은 한 언어의 모든 가능한 문자열이 어떻게 구성되는지를 설명하는 규칙들의 집합입니다. EBNF 표기법으로 작성한 우리 템플릿 언어의 문법을 살펴보겠습니다.

template = statements;
statements = { statement };
statement = CONTENT | expression | block_expression;
expression = OPEN_EXPRESSION, IDENTIFIER, arguments, CLOSE;
block_expression = OPEN_BLOCK, IDENTIFIER, arguments, CLOSE, statements, [ OPEN_INVERSE, CLOSE, statements ], OPEN_END_BLOCK, IDENTIFIER, CLOSE;
arguments = { IDENTIFIER };

각 할당문이 하나의 규칙(rule)을 정의합니다. 왼쪽에는 규칙의 이름이, 오른쪽에는 다른 규칙들(소문자) 또는 렉서가 만들어낸 토큰들(대문자)이 위치합니다. 규칙과 토큰은 콤마 ,로 연결하거나 파이프 | 기호로 대안(alternation)을 표현할 수 있습니다. 중괄호 { ... } 안의 항목은 여러 번 반복될 수 있고, 대괄호 [ ... ] 안의 항목은 선택 사항(optional)입니다.

위 문법은 간결하게 요약하면 다음을 의미합니다. 템플릿은 문장(statements)의 집합이며, 하나의 문장(statement)은 CONTENT 토큰, 표현식(expression), 혹은 블록 표현식(block expression) 중 하나입니다. 표현식은 OPEN_EXPRESSION 토큰 뒤에 IDENTIFIER 토큰, 인자(arguments), 그리고 CLOSE 토큰이 이어지는 형태입니다. 그리고 블록 표현식은 이를 자연어로 설명하려 들지 말고 위와 같은 표기법을 쓰는 것이 훨씬 낫다는 걸 보여주는 완벽한 예시입니다.

사실 이런 문법 정의로부터 파서를 자동 생성해 주는 도구들도 있습니다. 하지만 Ruby Magic의 전통에 따라, 재미있게 직접 파서를 만들어 보면서 그 과정에서 몇 가지를 배워보겠습니다.

파서 빌드하기

언어 이론은 여기까지 하고, 실제로 파서를 만들어 보겠습니다. 더욱 미니멀하지만 여전히 유효한 템플릿인 Welcome to Ruby Magic부터 시작해 보죠. 이 템플릿에는 표현식이 없고, 토큰 목록도 단 하나의 요소만 담고 있습니다.

[[:CONTENT, "Welcome to Ruby Magic"]]

먼저 파서 클래스의 기본 골격을 세팅합니다.

module Magicbars
  class Parser
    def self.parse(tokens)
      new(tokens).parse
    end
 
    attr_reader :tokens
 
    def initialize(tokens)
      @tokens = tokens
    end
 
    def parse
      # Parsing starts here
    end
  end
end

이 클래스는 토큰 배열을 받아 저장하며, 토큰을 AST로 변환하는 parse라는 단 하나의 public 메서드만 가집니다.

앞서 정의한 문법에서 최상위 규칙은 template입니다. 따라서 파싱 과정이 시작될 때 parse 메서드는 Template 노드를 반환해야 합니다.

노드(node)는 자체적인 동작이 없는 단순한 클래스입니다. 다른 노드들을 연결하거나 토큰에서 가져온 값을 저장하는 역할만 하죠. Template 노드는 다음과 같습니다.

module Magicbars
  module Nodes
    class Template
      attr_reader :statements
 
      def initialize(statements)
        @statements = statements
      end
    end
  end
end

예제를 동작하게 만들려면 Content 노드도 필요합니다. 이 노드는 토큰에서 가져온 텍스트 콘텐츠("Welcome to Ruby Magic")를 저장하기만 합니다.

module Magicbars
  module Nodes
    class Content
      attr_reader :content
 
      def initialize(content)
        @content = content
      end
    end
  end
end

이제 Template 인스턴스와 Content 인스턴스를 생성해 올바르게 연결하는 parse 메서드를 구현해 보겠습니다.

def parse
  Magicbars::Nodes::Template.new(parse_content)
end
 
def parse_content
  return unless tokens[0][0] == :CONTENT
 
  Magicbars::Nodes::Content.new(tokens[0][1])
end

파서를 실행하면 올바른 결과가 나옵니다.

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007fe90e939410 @statements=#<Magicbars::Nodes::Content:0x00007fe90e939578 @content="Welcome to Ruby Magic">>

물론 이 코드는 콘텐츠 노드가 하나뿐인 아주 단순한 예제에서만 동작합니다. 이번에는 실제로 표현식을 포함하는 좀 더 복잡한 예제인 Welcome to {{name}}으로 넘어가 보겠습니다.

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

이를 위해 Expression 노드와 Identifier 노드가 필요합니다. Expression 노드는 식별자(identifier)와 인자들(문법에 따르면 0개 이상의 Identifier 노드 배열)을 저장합니다. 다른 노드들과 마찬가지로 특별할 것은 없습니다.

module Magicbars
  module Nodes
    class Expression
      attr_reader :identifier, :arguments
 
      def initialize(identifier, arguments)
        @identifier = identifier
        @arguments = arguments
      end
    end
  end
end
 
module Magicbars
  module Nodes
    class Identifier
      attr_reader :value
 
      def initialize(value)
        @value = value.to_sym
      end
    end
  end
end

새 노드들이 준비되었으니, 일반 콘텐츠와 표현식을 모두 처리하도록 parse 메서드를 수정해 보겠습니다. 값이 반환되는 동안 계속 parse_statement를 호출하는 parse_statements 메서드를 도입하는 방식입니다.

def parse
  Magicbars::Nodes::Template.new(parse_statements)
end
 
def parse_statements
  results = []
 
  while result = parse_statement
    results << result
  end
 
  results
end

parse_statement 자체는 먼저 parse_content를 호출하고, 값이 반환되지 않으면 parse_expression을 호출합니다.

def parse_statement
  parse_content || parse_expression
end

눈치채셨나요? parse_statement 메서드가 문법의 statement 규칙과 점점 비슷해지고 있습니다. 사전에 문법을 명시적으로 작성해 두면 올바른 방향을 가는 데 큰 도움이 되는 지점입니다.

다음으로 parse_content 메서드가 첫 번째 토큰만 보지 않도록 수정하겠습니다. 초기화 과정에서 @position 인스턴스 변수를 추가하고, 이를 사용해 현재 토큰을 가져오는 방식입니다.

attr_reader :tokens, :position
 
def initialize(tokens)
  @tokens = tokens
  @position = 0
end
 
# ...
 
def parse_content
  return unless token = tokens[position]
  return unless token[0] == :CONTENT
 
  @position += 1
 
  Magicbars::Nodes::Content.new(token[1])
end

이제 parse_content 메서드는 현재 토큰을 확인하고 타입을 검사합니다. 토큰이 CONTENT 타입이라면 위치를 하나 증가시키고(현재 토큰이 성공적으로 파싱되었으므로), 토큰의 내용으로 Content 노드를 생성합니다. 현재 토큰이 없거나(토큰의 끝에 도달한 경우) 타입이 일치하지 않으면 메서드는 조기 종료되며 nil을 반환합니다.

개선된 parse_content 메서드가 준비되었으니, 새로운 parse_expression 메서드를 구현해 보겠습니다.

def parse_expression
  return unless token = tokens[position]
  return unless token[0] == :OPEN_EXPRESSION
 
  @position += 1
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  if !tokens[position] || tokens[position][0] != :CLOSE
    raise "Unexpected token #{tokens[position][0]}. Expected :CLOSE."
  end
 
  @position += 1
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

먼저 현재 토큰이 존재하고 그 타입이 OPEN_EXPRESSION인지 확인합니다. 맞다면 다음 토큰으로 진행한 뒤, parse_identifier와 parse_arguments를 각각 호출해 식별자와 인자를 파싱합니다. 두 메서드는 해당 노드를 반환하면서 현재 토큰을 앞당깁니다. 그다음 현재 토큰이 존재하고 :CLOSE 토큰인지 확인하고, 아니라면 에러를 발생시킵니다. 문제가 없다면 위치를 마지막으로 한 번 더 증가시킨 후 새로 만든 Expression 노드를 반환합니다.

여기까지 오니 몇 가지 패턴이 보이기 시작합니다. 다음 토큰으로 진행하는 동작이 여러 번 반복되고, 현재 토큰의 존재 여부와 타입을 검사하는 코드도 계속 등장합니다. 이런 코드는 다소 번거롭기 때문에 두 개의 헬퍼 메서드를 도입해 보겠습니다.

def expect(*expected_tokens)
  upcoming = tokens[position, expected_tokens.size]
 
  if upcoming.map(&:first) == expected_tokens
    advance(expected_tokens.size)
    upcoming
  end
end
 
def advance(offset = 1)
  @position += offset
end

expect 메서드는 가변 개수의 토큰 타입을 받아 토큰 스트림의 다음 토큰들과 비교합니다. 모두 일치하면 일치한 토큰들을 건너뛴 후 해당 토큰들을 반환합니다. advance 메서드는 @position 인스턴스 변수를 주어진 오프셋만큼 증가시킵니다.

다음에 올 토큰에 대한 유연성이 전혀 없는 경우를 위해, 토큰이 일치하지 않으면 깔끔한 에러 메시지를 발생시키는 메서드도 추가합니다.

def need(*required_tokens)
  upcoming = tokens[position, required_tokens.size]
  expect(*required_tokens) or raise "Unexpected tokens. Expected #{required_tokens.inspect} but got #{upcoming.inspect}"
end

이 헬퍼 메서드들을 활용하면 parse_content와 parse_expression이 훨씬 깔끔하고 읽기 좋아집니다.

def parse_content
  if content = expect(:CONTENT)
    Magicbars::Nodes::Content.new(content[0][1])
  end
end
 
def parse_expression
  return unless expect(:OPEN_EXPRESSION)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

마지막으로 parse_identifier와 parse_arguments도 살펴보겠습니다. 헬퍼 메서드 덕분에 parse_identifier는 parse_content만큼이나 단순합니다. 유일한 차이점은 다른 노드 타입을 반환한다는 것뿐입니다.

def parse_identifier
  if identifier = expect(:IDENTIFIER)
    Magicbars::Nodes::Identifier.new(identifier[0][1])
  end
end

parse_arguments 메서드를 구현하다 보면 parse_statements 메서드와 거의 동일하다는 것을 알게 됩니다. 유일한 차이는 parse_statement 대신 parse_identifier를 호출한다는 점이죠. 중복 로직은 또 다른 헬퍼 메서드를 도입해 제거할 수 있습니다.

def repeat(method)
  results = []
 
  while result = send(method)
    results << result
  end
 
  results
end

repeat 메서드는 send를 사용해 주어진 메서드 이름을 노드가 더 이상 반환되지 않을 때까지 호출합니다. 그 시점이 되면 수집된 결과(혹은 빈 배열)를 반환합니다. 이 헬퍼가 있으면 parse_statements와 parse_arguments 모두 한 줄짜리 메서드가 됩니다.

def parse_statements
  repeat(:parse_statement)
end
 
def parse_arguments
  repeat(:parse_identifier)
end

모든 변경 사항이 적용되었으니, 이제 토큰 스트림을 파싱해 보겠습니다.

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007f91a602f910
#     @statements=
#      [#<Magicbars::Nodes::Content:0x00007f91a58802c8 @content="Welcome to ">,
#       #<Magicbars::Nodes::Expression:0x00007f91a602fcd0
#        @arguments=[],
#        @identifier=
#         #<Magicbars::Nodes::Identifier:0x00007f91a5880138 @value=:name>  >

조금 읽기 어렵긴 하지만, 실제로 올바른 추상 구문 트리입니다. Template 노드는 Content 문장과 Expression 문장을 가지며, Content 노드의 값은 "Welcome to ", Expression 노드의 식별자는 값이 :name인 Identifier 노드입니다.

블록 표현식 파싱하기

파서 구현을 완성하려면 아직 블록 표현식의 파싱을 구현해야 합니다. 기억을 환기시키기 위해 파싱할 템플릿을 다시 보겠습니다.

Welcome to {{name}}!
 
{{#if subscribed}}
  Thank you for subscribing to our mailing list.
{{else}}
  Please sign up for our mailing list to be notified about new articles!
{{/if}}
 
Your friends at {{company_name}}

이를 위해 먼저 BlockExpression 노드를 도입하겠습니다. 이 노드는 조금 더 많은 데이터를 저장하지만, 그 외에는 아무것도 하지 않기 때문에 크게 흥미로울 것은 없습니다.

module Magicbars
  module Nodes
    class BlockExpression
      attr_reader :identifier, :arguments, :statements, :inverse_statements
 
      def initialize(identifier, arguments, statements, inverse_statements)
        @identifier = identifier
        @arguments = arguments
        @statements = statements
        @inverse_statements = inverse_statements
      end
    end
  end
end

Expression 노드처럼 식별자와 인자들을 저장하며, 추가로 블록 내부의 문장들과 역블록(inverse block)의 문장들도 함께 저장합니다.

문법을 다시 보면, 블록 표현식을 파싱하려면 parse_statements 메서드에 parse_block_expression 호출을 추가해야 함을 알 수 있습니다. 수정 후에는 문법의 규칙과 똑같은 모습이 됩니다.

def parse_statement
  parse_content || parse_expression || parse_block_expression
end

parse_block_expression 메서드 자체는 조금 더 복잡하지만, 헬퍼 메서드 덕분에 여전히 충분히 읽기 좋습니다.

def parse_block_expression
  return unless expect(:OPEN_BLOCK)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  statements = parse_statements
 
  if expect(:OPEN_INVERSE, :CLOSE)
    inverse_statements = parse_statements
  end
 
  need(:OPEN_END_BLOCK)
 
  if identifier.value != parse_identifier.value
    raise("Error. Identifier in closing expression does not match identifier in opening expression")
  end
 
  need(:CLOSE)
 
  Magicbars::Nodes::BlockExpression.new(identifier, arguments, statements, inverse_statements)
end

첫 부분은 parse_expression 메서드와 매우 유사합니다. 식별자와 인자를 포함한 여는 블록 표현식을 파싱한 뒤, parse_statements를 호출해 블록 내부를 파싱합니다.

그다음 OPEN_INVERSE 토큰 뒤에 CLOSE 토큰이 이어지는 형태로 식별되는 {{else}} 표현식이 있는지 확인합니다. 두 토큰이 모두 발견되면 parse_statements를 다시 호출해 역블록을 파싱하고, 없다면 그 부분은 그냥 건너뜁니다.

마지막으로, 여는 블록 표현식과 동일한 식별자를 사용하는 닫는 블록 표현식이 있는지 확인합니다. 식별자가 일치하지 않으면 에러를 발생시키고, 일치하면 새로운 BlockExpression 노드를 생성해 반환합니다.

블록 표현식 템플릿의 토큰으로 파서를 호출하면 해당 템플릿의 AST가 반환됩니다. 출력 결과가 거의 읽을 수 없는 수준이라 예제는 생략하고, 대신 생성된 AST를 시각화한 그림으로 대신하겠습니다.

parse_block_expression 내부에서 parse_statements를 호출하기 때문에, 블록과 역블록 모두 더 많은 표현식, 블록 표현식, 그리고 일반 콘텐츠를 포함할 수 있습니다.

여정은 계속됩니다…

나만의 템플릿 언어를 구현하는 여정에서 꽤 큰 진전을 이루었습니다. 언어 이론을 잠깐 들여다본 후, 템플릿 언어의 문법을 정의하고 이를 바탕으로 파서를 처음부터 직접 구현했습니다.

렉서와 파서가 모두 준비되었으니, 이제 템플릿으로부터 보간된 문자열을 생성하는 인터프리터(interpreter)만 남았습니다. 이 부분은 다음 Ruby Magic 에디션에서 다룰 예정입니다. 발행 소식을 받아보려면 Ruby Magic 메일링 리스트를 구독하세요.