코드 표현하기

숲에 사는 사람들에게 거의 모든 종류의 나무는 그 특징만큼이나 목소리를 가지고 있다. 토마스 하디, 《녹림의 나무 아래서》

지난 장에서는 원시 소스 코드를 문자열로 받아 토큰 시퀀스라는 약간 더 높은 수준의 표현으로 변환했습니다. 다음 장에서 작성할 파서는 이 토큰들을 다시 한 번 더 풍부하고 복잡한 표현으로 변환합니다.

이 표현을 생성하기 전에, 먼저 이를 정의해야 합니다. 이번 장의 주제가 바로 이것입니다. 이 과정에서 형식 문법(formal grammars)에 대한 이론을 다루고, 함수형 프로그래밍과 객체 지향 프로그래밍의 차이를 느껴보며, 몇 가지 디자인 패턴을 살펴보고 메타 프로그래밍을 진행할 것입니다.

이 모든 것을 하기 전에, 우선 코드의 표현이라는 주요 목표에 집중해봅시다. 이 표현은 파서가 쉽게 생성하고 인터프리터가 쉽게 소비할 수 있어야 합니다. 아직 파서나 인터프리터를 작성해본 적이 없다면, 이러한 요구사항이 정확히 와닿지 않을 수 있습니다. 여러분의 직관이 도움이 될 수도 있습니다. 여러분이 인간 인터프리터 역할을 할 때 뇌는 무엇을 하고 있나요? 다음과 같은 산술 표현식을 어떻게 머릿속으로 평가하나요?

1 + 2 * 3 - 4

여러분은 연산자 우선순위—오래된 “Please Excuse My Dear Aunt Sally” 같은 규칙—를 이해하고 있기 때문에 곱셈이 덧셈이나 뺄셈보다 먼저 평가된다는 것을 알고 있습니다. 이러한 우선순위를 시각화하는 한 가지 방법은 트리를 사용하는 것입니다. 리프 노드는 숫자이고, 내부 노드는 각 피연산자에 대한 가지를 가진 연산자입니다.

산술 노드를 평가하려면 하위 트리의 숫자 값을 알아야 하므로, 먼저 이들을 평가해야 합니다. 이는 리프에서 루트로 올라가는 방식—즉, 후위 순회(post-order traversal) 방식으로 처리한다는 의미입니다.

산술 표현식을 제공하면 이러한 트리 중 하나를 아주 쉽게 그릴 수 있습니다. 트리가 주어지면 어려움 없이 평가할 수 있습니다. 따라서 직관적으로 우리 코드의 실행 가능한 표현은 언어의 문법 구조—연산자 중첩—와 일치하는 트리인 것 같습니다.

그렇다면 해당 문법이 무엇인지 더 정확히 알아볼 필요가 있습니다. 지난 장의 어휘 문법(lexical grammar)처럼, 구문 문법(syntactic grammar)에도 방대한 이론이 존재합니다. 스캐닝할 때보다 이 이론을 좀 더 깊이 다룰 것입니다. 이는 인터프리터의 많은 부분에서 유용한 도구가 되기 때문입니다. 우리는 촘스키 계층(Chomsky hierarchy)의 한 단계 위로 올라가면서 시작합니다 . . . 

5 . 1문맥 자유 문법

지난 장에서 어휘 문법(lexical grammar)—문자가 토큰으로 그룹화되는 규칙—을 정의하는 데 사용한 형식론은 정규 언어(regular language)라고 불렸습니다. 이는 평평한(flat) 토큰 시퀀스를 내보내는 우리 스캐너에 적합했습니다. 그러나 정규 언어는 임의로 깊게 중첩될 수 있는 표현식을 처리할 만큼 강력하지 않습니다.

우리는 더 큰 망치가 필요하며, 그 망치는 바로 문맥 자유 문법(context-free grammar, CFG)입니다. 이는 형식 문법(formal grammars) 도구 상자에서 다음으로 강력한 도구입니다. 형식 문법은 "알파벳"이라고 부르는 원자적인 조각들의 집합을 사용합니다. 그리고 나서 문법에 "속하는" (대개 무한한) "문자열" 집합을 정의합니다. 각 문자열은 알파벳의 "글자"들의 시퀀스입니다.

이 모든 용어에 따옴표를 사용하는 이유는 어휘 문법에서 구문 문법으로 넘어갈 때 용어들이 조금 혼란스러워지기 때문입니다. 우리 스캐너의 문법에서 알파벳은 개별 문자로 구성되며, 문자열은 유효한 렉심(lexeme)—대략적으로 "단어"입니다. 지금 우리가 논의하는 구문 문법에서는 다른 수준의 세분성을 가집니다. 이제 알파벳의 각 "글자"는 전체 토큰이며, "문자열"은 토큰의 시퀀스—즉, 전체 표현식입니다.

아. 아마 표가 도움이 될 것입니다:

형식 문법의 역할은 어떤 문자열이 유효하고 어떤 문자열이 유효하지 않은지 명시하는 것입니다. 영문법을 정의한다면, "eggs are tasty for breakfast"는 문법에 속하겠지만, "tasty breakfast for are eggs"는 그렇지 않을 것입니다.

5 . 1 . 1문법 규칙

무한한 수의 유효한 문자열을 포함하는 문법을 어떻게 기록할까요? 분명히 모든 것을 나열할 수는 없습니다. 대신, 유한한 규칙 집합을 만듭니다. 이 규칙들을 두 가지 방향 중 하나로 "플레이"할 수 있는 게임이라고 생각할 수 있습니다.

규칙에서 시작하면 이를 사용하여 문법에 속하는 문자열을 생성할 수 있습니다. 이러한 방식으로 생성된 문자열은 문법 규칙에서 유도되었으므로 유도(derivations)라고 불립니다. 게임의 각 단계에서 규칙을 선택하고 지시에 따릅니다. 형식 문법에 대한 대부분의 용어는 이 방향으로 문법을 사용하는 것에서 비롯됩니다. 규칙은 문법에 있는 문자열을 생성하므로 생성 규칙(productions)이라고 불립니다.

문맥 자유 문법의 각 생성 규칙은 머리 (head)—이름—와 몸체 (body)를 가지며, 몸체는 무엇을 생성하는지 기술합니다. 순수한 형태에서 몸체는 단순히 심볼 목록입니다. 심볼은 두 가지 맛있는 종류로 나뉩니다:

• 터미널(terminal)은 문법의 알파벳에 있는 글자입니다. 리터럴 값처럼 생각할 수 있습니다. 우리가 정의하는 구문 문법에서 터미널은 스캐너에서 오는 개별 렉심—예를 들어 if나 1234와 같은 토큰입니다.

  이들은 더 이상 게임에서 "진행"되지 않는 "종점"의 의미에서 "터미널"이라고 불립니다. 단순히 해당 심볼 하나를 생성합니다.

• 논터미널(nonterminal)은 문법 내의 다른 규칙에 대한 이름 붙은 참조입니다. 이는 "그 규칙을 실행하고 거기서 생성되는 모든 것을 여기에 삽입하라"는 의미입니다. 이런 방식으로 문법은 구성됩니다.

마지막으로 한 가지 더 세부 사항이 있습니다. 같은 이름을 가진 여러 규칙이 있을 수 있습니다. 해당 이름의 논터미널에 도달하면, 원하는 대로 그 규칙들 중 아무거나 선택할 수 있습니다.

이를 구체화하기 위해, 이러한 생성 규칙을 기록할 방법이 필요합니다. 사람들은 수천 년 전 산스크리트어 문법을 성문화한 파니니(Pāṇini)의 아슈타디야이(Ashtadhyayi) 시대부터 문법을 명확히 하려고 노력해왔습니다. 존 배커스(John Backus)와 그의 동료들이 ALGOL 58을 명세하기 위한 표기법을 필요로 하여 배커스-나우어 형식(Backus-Naur form, BNF)을 고안하기 전까지는 큰 진전이 없었습니다. 그 이후로 거의 모든 사람들이 자신들의 취향에 맞게 변형된 BNF 형태를 사용하고 있습니다.

저는 깔끔한 방식을 고안하려고 했습니다. 각 규칙은 이름 뒤에 화살표(→), 그 뒤에 심볼 시퀀스가 오고, 마지막으로 세미콜론(;)으로 끝납니다. 터미널은 따옴표로 묶인 문자열이고, 논터미널은 소문자 단어입니다.

이를 사용하여, 다음은 아침 식사 메뉴를 위한 문법입니다:

breakfast  → protein "with" breakfast "on the side" ;
breakfast  → protein ;
breakfast  → bread ;

protein    → crispiness "crispy" "bacon" ;
protein    → "sausage" ;
protein    → cooked "eggs" ;

crispiness → "really" ;
crispiness → "really" crispiness ;

cooked     → "scrambled" ;
cooked     → "poached" ;
cooked     → "fried" ;

bread      → "toast" ;
bread      → "biscuits" ;
bread      → "English muffin" ;

이 문법을 사용하여 무작위 아침 식사를 생성할 수 있습니다. 한 번 시도하여 어떻게 작동하는지 봅시다. 오랜 관습에 따라 게임은 문법의 첫 번째 규칙인 breakfast로 시작합니다. 여기에는 세 가지 생성 규칙이 있으며, 우리는 그중 첫 번째를 무작위로 선택합니다. 결과 문자열은 다음과 같습니다:

protein "with" breakfast "on the side"

첫 번째 논터미널인 protein을 확장해야 하므로, 이에 대한 생성 규칙을 선택합니다. 다음을 선택해 봅시다:

protein → cooked "eggs" ;

다음으로 cooked에 대한 생성 규칙이 필요하며, "poached"를 선택합니다. 이는 터미널이므로 추가합니다. 이제 우리 문자열은 다음과 같습니다:

"poached" "eggs" "with" breakfast "on the side"

다음 논터미널은 breakfast 다시 입니다. 우리가 선택한 첫 번째 breakfast 생성 규칙은 재귀적으로 breakfast 규칙을 다시 참조합니다. 문법에서의 재귀는 정의되는 언어가 정규 언어가 아닌 문맥 자유 언어라는 좋은 신호입니다. 특히, 재귀적인 논터미널이 양쪽에 생성 규칙을 가지는 재귀는 해당 언어가 정규 언어가 아님을 암시합니다.

우리는 계속해서 breakfast의 첫 번째 생성 규칙을 선택하여 "베이컨과 소시지, 스크램블 에그, 베이컨 . . . "과 같은 온갖 종류의 아침 식사를 만들 수 있습니다. 하지만 그렇게 하지 않을 것입니다. 이번에는 bread를 선택할 것입니다. bread에는 세 가지 규칙이 있으며, 각 규칙은 터미널만을 포함합니다. 우리는 "English muffin"을 선택하겠습니다.

그렇게 하여, 문자열의 모든 논터미널은 마침내 터미널만 남을 때까지 확장되었고, 우리는 다음과 같은 결과를 얻었습니다:

여기에 햄과 홀랜다이즈 소스를 추가하면 에그 베네딕트가 됩니다.

여러 생성 규칙을 가진 규칙을 만날 때마다 우리는 임의로 하나를 선택했습니다. 이러한 유연성 덕분에 적은 수의 문법 규칙으로 조합적으로 훨씬 더 많은 문자열 집합을 인코딩할 수 있습니다. 규칙이 자기 자신을 직접 또는 간접적으로 참조할 수 있다는 사실은 이를 더욱 확장하여, 유한한 문법 안에 무한한 수의 문자열을 담을 수 있게 합니다.

5 . 1 . 2표기법 개선하기

몇 개의 규칙 안에 무한한 문자열 집합을 담는 것은 꽤 환상적이지만, 한 걸음 더 나아가봅시다. 현재의 표기법은 작동하지만 지루합니다. 따라서 좋은 언어 설계자라면 누구나 그렇듯이 약간의 문법적 설탕(syntactic sugar)—추가적인 편의 표기법—을 추가할 것입니다. 터미널과 논터미널 외에도, 규칙의 몸체에 몇 가지 다른 종류의 표현식을 허용할 것입니다:

• 각 생성 규칙을 추가할 때마다 규칙 이름을 반복하는 대신, 파이프(|)로 구분된 일련의 생성 규칙을 허용할 것입니다.

  bread → "toast" | "biscuits" | "English muffin" ;
  

• 또한, 그룹화를 위해 괄호를 허용하고, 생성 규칙 중간에서 여러 옵션 중 하나를 선택하기 위해 그 안에 |를 허용할 것입니다.

  protein → ( "scrambled" | "poached" | "fried" ) "eggs" ;
  

• 심볼의 반복 시퀀스를 지원하기 위해 재귀를 사용하는 것은 특정 순수함을 가지고 있지만, 루프를 만들 때마다 별도의 명명된 하위 규칙을 만드는 것은 다소 번거로운 일입니다. 따라서, 우리는 이전 심볼이나 그룹이 0회 이상 반복될 수 있도록 후위 연산자 *를 사용합니다.

  crispiness → "really" "really"* ;
  

• 후위 연산자 +도 비슷하지만, 선행하는 생성 규칙이 최소 한 번 나타나야 합니다.

  crispiness → "really"+ ;
  

• 후위 연산자 ?는 선택적 생성 규칙을 위한 것입니다. 그 앞에 있는 것은 0번 또는 1번 나타날 수 있으며, 그 이상은 안 됩니다.

  breakfast → protein ( "with" breakfast "on the side" )? ;
  

이러한 모든 문법적 편의성 덕분에, 우리 아침 식사 문법은 다음과 같이 압축됩니다:

breakfast → protein ( "with" breakfast "on the side" )?
          | bread ;

protein   → "really"+ "crispy" "bacon"
          | "sausage"
          | ( "scrambled" | "poached" | "fried" ) "eggs" ;

bread     → "toast" | "biscuits" | "English muffin" ;

크게 나쁘지 않으리라 생각합니다. grep이나 텍스트 편집기에서 정규 표현식을 사용하는 데 익숙하다면, 대부분의 구두점은 친숙할 것입니다. 주요 차이점은 여기의 심볼들이 단일 문자가 아니라 전체 토큰을 나타낸다는 점입니다.

이 책의 나머지 부분에서는 Lox의 문법을 정확하게 설명하기 위해 이 표기법을 사용할 것입니다. 프로그래밍 언어를 다루다 보면, 문맥 자유 문법(이 표기법 또는 EBNF나 다른 표기법을 사용하여)이 비공식적인 구문 설계 아이디어를 명확히 하는 데 도움이 된다는 것을 알게 될 것입니다. 또한 다른 언어 개발자들과 문법에 대해 소통하기 위한 유용한 수단이기도 합니다.

Lox를 위해 정의하는 규칙과 생성 규칙은 메모리에서 코드를 표현하기 위해 구현할 트리 자료 구조의 가이드 역할도 합니다. 그 작업을 시작하기 전에, Lox를 위한 실제 문법, 적어도 시작하기에 충분한 문법이 필요합니다.

5 . 1 . 3Lox 표현식 문법

이전 장에서는 Lox의 전체 어휘 문법을 한 번에 다루었습니다. 모든 키워드와 구두점이 거기에 있습니다. 구문 문법은 더 크며, 실제로 인터프리터를 작동시키기 전에 전체를 다 살펴보는 것은 매우 지루한 작업일 것입니다.

대신, 다음 몇 개 장에서는 언어의 부분 집합을 다룰 것입니다. 일단 이 미니 언어를 표현하고 파싱하며 해석한 다음, 이후 장들에서 새로운 문법을 포함하여 새로운 기능을 점진적으로 추가할 것입니다. 지금은 소수의 표현식만 신경 쓸 것입니다:

• 리터럴. 숫자, 문자열, 불리언, 그리고 nil.

• 단항 표현식. 논리 부정 연산자 !와 숫자를 부정하는 -.

• 이항 표현식. 우리가 잘 알고 있는 중위 산술 연산자 (+, -, *, /)와 논리 연산자 (==, !=, <, <=, >, >=).

• 괄호. 표현식을 감싸는 한 쌍의 (와 ).

이를 통해 다음과 같은 표현식에 필요한 충분한 문법을 얻게 됩니다:

1 - (2 * 3) < 4 == false

우리의 유용한 새 표기법을 사용하여, 이에 대한 문법은 다음과 같습니다:

expression     → literal
               | unary
               | binary
               | grouping ;

literal        → NUMBER | STRING | "true" | "false" | "nil" ;
grouping       → "(" expression ")" ;
unary          → ( "-" | "!" ) expression ;
binary         → expression operator expression ;
operator       → "==" | "!=" | "<" | "<=" | ">" | ">="
               | "+"  | "-"  | "*" | "/" ;

여기에는 한 가지 추가적인 메타 문법이 있습니다. 정확한 렉심과 일치하는 터미널을 위한 따옴표로 묶인 문자열 외에도, 텍스트 표현이 달라질 수 있는 단일 렉심인 터미널은 대문자로 표기합니다. NUMBER는 모든 숫자 리터럴을, STRING은 모든 문자열 리터럴을 나타냅니다. 나중에 IDENTIFIER에 대해서도 같은 작업을 할 것입니다.

이 문법은 사실 모호하며, 이를 파싱할 때 확인하게 될 것입니다. 하지만 지금으로서는 충분합니다.

5 . 2구문 트리 구현하기

드디어 코드를 작성할 시간입니다. 그 작은 표현식 문법이 우리의 뼈대입니다. 문법이 재귀적이기 때문에—grouping, unary, binary 모두 expression을 다시 참조하는 방식에 주목하세요—우리의 자료 구조는 트리를 형성할 것입니다. 이 구조가 우리 언어의 구문을 나타내므로, 이를 구문 트리(syntax tree)라고 부릅니다.

우리 스캐너는 모든 종류의 렉심을 표현하기 위해 단일 Token 클래스를 사용했습니다. 서로 다른 종류를 구분하기 위해—숫자 123과 문자열 "123"을 비교한다고 생각해보세요—간단한 TokenType enum을 포함했습니다. 구문 트리는 그렇게 동질적이지 않습니다. 단항 표현식은 하나의 피연산자를 가지고, 이항 표현식은 두 개를 가지며, 리터럴은 아무것도 가지지 않습니다.

이 모든 것을 임의의 자식 목록을 가진 단일 Expression 클래스로 묶을 수도 있습니다. 일부 컴파일러는 그렇게 합니다. 하지만 저는 자바의 타입 시스템을 최대한 활용하는 것을 선호합니다. 따라서 표현식을 위한 기본 클래스를 정의할 것입니다. 그리고 나서 각 종류의 표현식—expression 아래의 각 생성 규칙—마다 해당 규칙에 특정한 논터미널(nonterminal)을 위한 필드를 가진 서브클래스를 생성할 것입니다. 이렇게 하면 예를 들어 단항 표현식의 두 번째 피연산자에 접근하려고 할 때 컴파일 오류를 얻을 수 있습니다.

이와 같습니다:

package com.craftinginterpreters.lox;

abstract class Expr { 
  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }

    final Expr left;
    final Token operator;
    final Expr right;
  }

  // 다른 표현식들...
}

Expr는 모든 표현식 클래스가 상속받는 기본 클래스입니다. Binary에서 볼 수 있듯이, 서브클래스들은 그 안에 중첩되어 있습니다. 이것은 기술적으로 필수는 아니지만, 모든 클래스를 단일 자바 파일에 담을 수 있게 해줍니다.

5 . 2 . 1방향을 잃은 객체

Token 클래스와 마찬가지로, 여기에는 어떤 메서드도 없다는 것을 알 수 있을 것입니다. 이는 단순한(dumb) 구조입니다. 깔끔하게 타입이 지정되었지만, 그저 데이터 묶음에 불과합니다. 이것은 자바와 같은 객체 지향 언어에서는 이상하게 느껴집니다. 클래스가 무언가를 해야 하지 않을까요?

문제는 이러한 트리 클래스들이 어떤 단일 도메인에 속하지 않는다는 점입니다. 트리가 생성되는 곳이니 파싱을 위한 메서드를 가져야 할까요? 아니면 소비되는 곳이니 해석을 위한 메서드를 가져야 할까요? 트리는 이 두 영역의 경계를 넘나들기 때문에, 사실상 어느 쪽에도 속하지 않습니다.

사실, 이 타입들은 파서와 인터프리터가 소통할 수 있도록 존재합니다. 이는 관련 동작이 없는 순수한 데이터 타입에 적합합니다. 이러한 스타일은 리스프(Lisp)나 ML과 같은 함수형 언어에서는 모든 데이터가 동작과 분리되어 있어 매우 자연스럽지만, 자바에서는 어색하게 느껴집니다.

함수형 프로그래밍 애호가들은 지금 당장 "보세요! 객체 지향 언어는 인터프리터에 적합하지 않아요!"라고 외치려고 할 것입니다. 저는 그렇게까지 주장하지는 않을 것입니다. 스캐너 자체는 객체 지향에 놀랍도록 잘 맞았다는 것을 기억할 것입니다. 스캐너는 소스 코드 내에서 위치를 추적하는 모든 가변 상태, 잘 정의된 공개 메서드 집합, 그리고 몇몇 비공개 도우미 메서드를 가지고 있었습니다.

제 생각에는 인터프리터의 각 단계나 부분은 객체 지향 스타일로 잘 작동합니다. 행동이 제거되는 것은 그들 사이를 흐르는 자료 구조들입니다.

5 . 2 . 2트리 메타 프로그래밍

자바는 동작이 없는 클래스를 표현할 수 있지만, 그 점에 특별히 뛰어나다고 말하지는 않겠습니다. 객체에 세 개의 필드를 채워 넣기 위해 11줄의 코드를 작성하는 것은 꽤 지루한 일이며, 모든 작업을 마치면 이런 클래스가 21개나 될 것입니다.

여러분의 시간이나 제 잉크를 낭비하며 이 모든 것을 작성하고 싶지 않습니다. 정말이지, 각 서브클래스의 본질은 무엇일까요? 이름과 타입이 지정된 필드 목록. 그게 전부입니다. 우리는 똑똑한 언어 해커들이잖아요? 자동화합시다.

각 클래스 정의, 필드 선언, 생성자 및 초기화 코드를 지루하게 수동으로 작성하는 대신, 우리를 대신할 스크립트를 함께 만들어봅시다. 이 스크립트에는 각 트리 타입의 설명—이름과 필드—이 포함되어 있으며, 해당 이름과 상태로 클래스를 정의하는 데 필요한 자바 코드를 출력합니다.

이 스크립트는 "Expr.java"라는 파일을 생성하는 작은 자바 명령줄 애플리케이션입니다:

package com.craftinginterpreters.tool;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;

public class GenerateAst {
  public static void main(String[] args) throws IOException {
    if (args.length != 1) {
      System.err.println("Usage: generate_ast <output directory>");
      System.exit(64);
    }
    String outputDir = args[0];
  }
}

이 파일은 .lox 대신 .tool 패키지에 있다는 점에 유의하세요. 이 스크립트는 인터프리터 자체의 일부가 아닙니다. 이는 인터프리터를 개발하는 우리가 직접 실행하여 구문 트리 클래스를 생성하는 도구입니다. 작업이 완료되면, "Expr.java" 파일을 구현의 다른 파일과 마찬가지로 취급합니다. 우리는 단지 그 파일이 작성되는 방식을 자동화하는 것뿐입니다.

클래스를 생성하려면 각 타입과 그 필드에 대한 설명이 필요합니다.

    String outputDir = args[0];

    defineAst(outputDir, "Expr", Arrays.asList(
      "Binary   : Expr left, Token operator, Expr right",
      "Grouping : Expr expression",
      "Literal  : Object value",
      "Unary    : Token operator, Expr right"
    ));

  }

간결함을 위해 표현식 타입에 대한 설명을 문자열 안에 압축했습니다. 각 문자열은 클래스 이름 뒤에 :가 오고, 그 뒤에 쉼표로 구분된 필드 목록이 따릅니다. 각 필드는 타입과 이름을 가집니다.

defineAst()가 가장 먼저 해야 할 일은 기본 Expr 클래스를 출력하는 것입니다.

  private static void defineAst(
      String outputDir, String baseName, List<String> types)
      throws IOException {
    String path = outputDir + "/" + baseName + ".java";
    PrintWriter writer = new PrintWriter(path, "UTF-8");

    writer.println("package com.craftinginterpreters.lox;");
    writer.println();
    writer.println("import java.util.List;");
    writer.println();
    writer.println("abstract class " + baseName + " {");

    writer.println("}");
    writer.close();
  }

이 함수를 호출할 때 baseName은 "Expr"이며, 이는 클래스 이름이자 출력 파일의 이름이기도 합니다. 이름을 하드코딩하는 대신 인수로 전달하는 이유는 나중에 문장(statement)을 위한 별도의 클래스 계열을 추가할 것이기 때문입니다.

기본 클래스 내부에 각 서브클래스를 정의합니다.

    writer.println("abstract class " + baseName + " {");

    // AST 클래스들.
    for (String type : types) {
      String className = type.split(":")[0].trim();
      String fields = type.split(":")[1].trim(); 
      defineType(writer, baseName, className, fields);
    }

    writer.println("}");

해당 코드는 다시 다음을 호출합니다:

  private static void defineType(
      PrintWriter writer, String baseName,
      String className, String fieldList) {
    writer.println("  static class " + className + " extends " +
        baseName + " {");

    // 생성자.
    writer.println("    " + className + "(" + fieldList + ") {");

    // 필드에 매개변수 저장.
    String[] fields = fieldList.split(", ");
    for (String field : fields) {
      String name = field.split(" ")[1];
      writer.println("      this." + name + " = " + name + ";");
    }

    writer.println("    }");

    // 필드.
    writer.println();
    for (String field : fields) {
      writer.println("    final " + field + ";");
    }

    writer.println("  }");
  }

자, 됐습니다. 영광스러운 자바의 상용구 코드가 모두 처리되었습니다. 각 필드를 클래스 몸체에 선언하고, 각 필드에 대한 매개변수를 가진 클래스 생성자를 정의하며, 몸체에서 이를 초기화합니다.

이제 이 자바 프로그램을 컴파일하고 실행하면 수십 줄의 코드를 포함하는 새 ".java" 파일이 생성됩니다. 그 파일은 앞으로 훨씬 더 길어질 것입니다.

5 . 3트리 다루기

잠시 상상의 나래를 펼쳐봅시다. 아직 그 단계는 아니지만, 인터프리터가 구문 트리로 무엇을 할지 생각해 보세요. Lox의 각 표현식 종류는 런타임에 다르게 동작합니다. 이는 인터프리터가 각 표현식 타입을 처리하기 위해 다른 코드 덩어리를 선택해야 한다는 것을 의미합니다. 토큰의 경우, 단순히 TokenType에 따라 스위치할 수 있습니다. 하지만 구문 트리에 대해서는 "타입" enum이 없고, 각 트리에 대해 별도의 자바 클래스만 있습니다.

우리는 길고 긴 타입 검사 체인을 작성할 수 있습니다:

if (expr instanceof Expr.Binary) {
  // ...
} else if (expr instanceof Expr.Grouping) {
  // ...
} else // ...

하지만 이 모든 순차적인 타입 검사는 느립니다. 이름이 알파벳 순으로 뒤에 오는 표현식 타입은 올바른 타입을 찾기 전에 더 많은 if 케이스를 거쳐야 하므로 실행 시간이 더 길어질 것입니다. 그것은 제가 생각하는 우아한 해결책이 아닙니다.

우리는 일련의 클래스들을 가지고 있으며, 각각에 특정 동작 덩어리를 연결해야 합니다. 자바와 같은 객체 지향 언어에서 자연스러운 해결책은 그러한 동작들을 클래스 자체의 메서드에 넣는 것입니다. Expr에 추상 interpret() 메서드를 추가하고, 각 서브클래스가 자신을 해석하기 위해 이를 구현하도록 할 수 있습니다.

이것은 작은 프로젝트에는 괜찮지만, 확장이 어렵습니다. 이전에 언급했듯이, 이 트리 클래스들은 여러 도메인에 걸쳐 있습니다. 최소한 파서와 인터프리터 모두 이들을 다룰 것입니다. 나중에 보겠지만, 이들에 대해 이름 분석(name resolution)을 수행해야 합니다. 만약 우리 언어가 정적으로 타입이 지정되었다면, 타입 검사 단계가 있었을 것입니다.

만약 각 작업마다 인스턴스 메서드를 표현식 클래스에 추가한다면, 여러 다른 도메인을 한데 섞어버리는 꼴이 됩니다. 이는 관심사 분리(separation of concerns) 원칙을 위반하며 유지보수가 어려운 코드로 이어집니다.

5 . 3 . 1표현식 문제 (The Expression Problem)

이 문제는 처음 보이는 것보다 훨씬 근본적입니다. 우리는 소수의 타입과 "해석"과 같은 소수의 고수준 연산을 가지고 있습니다. 각 타입과 연산 쌍에 대해 특정 구현이 필요합니다. 표를 상상해 보세요:

행은 타입이고, 열은 연산입니다. 각 셀은 해당 타입에 대한 해당 연산을 구현하는 고유한 코드 조각을 나타냅니다.

자바와 같은 객체 지향 언어는 한 행의 모든 코드가 자연스럽게 함께 묶여 있다고 가정합니다. 즉, 한 가지 타입으로 수행하는 모든 작업이 서로 관련이 있을 가능성이 높다고 판단하며, 언어는 같은 클래스 내에 메서드로 함께 정의하기 쉽게 만듭니다.

이는 새 행을 추가하여 테이블을 쉽게 확장할 수 있도록 합니다. 단순히 새 클래스를 정의하기만 하면 됩니다. 기존 코드를 건드릴 필요가 없습니다. 하지만 새로운 연산—새로운 열을 추가하고 싶다고 상상해 보세요. 자바에서는 이는 기존 클래스 각각을 열어 새 메서드를 추가해야 한다는 의미입니다.

ML 계열의 함수형 패러다임 언어들은 이를 뒤집습니다. 거기에서는 메서드를 가진 클래스가 없습니다. 타입과 함수는 완전히 분리되어 있습니다. 여러 다른 타입에 대한 연산을 구현하려면 단일 함수를 정의합니다. 해당 함수의 몸체에서는 패턴 매칭(pattern matching)—타입 기반의 강력한 스위치 같은 것—을 사용하여 각 타입에 대한 연산을 한 곳에서 모두 구현합니다.

이러한 방식은 새로운 연산을 추가하는 것을 아주 쉽게 만듭니다—단순히 모든 타입에 대해 패턴 매칭하는 또 다른 함수를 정의하기만 하면 됩니다.

그러나 반대로, 새로운 타입을 추가하는 것은 어렵습니다. 기존의 모든 함수에 있는 모든 패턴 매치에 새로운 케이스를 추가해야 합니다.

각 스타일에는 특정한 "결"이 있습니다. 이는 패러다임 이름이 문자 그대로 말하는 바입니다—객체 지향 언어는 코드의 방향을 타입의 행을 따라 정렬하기를 원합니다. 반면 함수형 언어는 각 열에 해당하는 코드를 함수로 묶도록 권장합니다.

많은 똑똑한 언어 전문가들은 어떤 스타일도 표에 행과 열 모두를 쉽게 추가할 수 없다는 것을 알아차렸습니다. 그들은 이 어려움을 "표현식 문제(expression problem)"라고 불렀는데, 이는—지금 우리가 그렇듯이—컴파일러에서 표현식 구문 트리 노드를 모델링하는 가장 좋은 방법을 찾으려 할 때 처음 이 문제에 부딪혔기 때문입니다.

사람들은 그 문제를 해결하기 위해 온갖 종류의 언어 기능, 디자인 패턴, 프로그래밍 트릭을 시도했지만, 아직 어떤 완벽한 언어도 이를 완전히 해결하지 못했습니다. 그동안 우리가 할 수 있는 최선은 우리가 작성하는 프로그램의 자연스러운 아키텍처적 경계와 일치하는 방향을 가진 언어를 선택하는 것입니다.

객체 지향은 우리 인터프리터의 많은 부분에서 잘 작동하지만, 이러한 트리 클래스들은 자바의 결에 맞지 않습니다. 다행히도, 이 문제에 적용할 수 있는 디자인 패턴이 있습니다.

5 . 3 . 2비지터 패턴

비지터 패턴(Visitor pattern)은 《디자인 패턴》에 나오는 패턴 중 가장 널리 오해받는 패턴입니다. 지난 수십 년간의 과도한 소프트웨어 아키텍처들을 돌아보면 이 말이 정말 심오하게 다가올 것입니다.

문제는 용어에서 시작됩니다. 이 패턴은 "방문(visiting)"에 관한 것이 아니며, 그 안의 "accept" 메서드도 어떤 도움이 되는 이미지를 떠올리게 하지 않습니다. 많은 사람들이 이 패턴이 트리를 순회하는 것과 관련이 있다고 생각하지만, 전혀 그렇지 않습니다. 우리가 트리와 유사한 클래스 집합에 이 패턴을 사용할 것이긴 하지만, 그것은 우연의 일치입니다. 보시다시피, 이 패턴은 단일 객체에도 잘 작동합니다.

비지터 패턴은 사실 OOP 언어 내에서 함수형 스타일을 근사화하는 것입니다. 이는 테이블에 새 열을 쉽게 추가할 수 있도록 해줍니다. 우리는 타입 자체를 건드리지 않고도 한 곳에서 여러 타입에 대한 새로운 연산의 모든 동작을 정의할 수 있습니다. 이는 컴퓨터 과학의 거의 모든 문제를 해결하는 방식과 같습니다: 간접 계층을 추가함으로써 해결합니다.

자동 생성된 Expr 클래스에 적용하기 전에, 더 간단한 예시를 살펴보겠습니다. 두 가지 종류의 패스트리가 있다고 가정해 봅시다: 베녜와 크룰러.

  abstract class Pastry {
  }

  class Beignet extends Pastry {
  }

  class Cruller extends Pastry {
  }

우리는 새로운 패스트리 연산—요리하기, 먹기, 장식하기 등—을 정의할 수 있기를 원하며, 매번 각 클래스에 새 메서드를 추가할 필요가 없도록 하고 싶습니다. 다음은 그 방법입니다. 먼저, 별도의 인터페이스를 정의합니다.

  interface PastryVisitor {
    void visitBeignet(Beignet beignet); 
    void visitCruller(Cruller cruller);
  }

패스트리에 수행될 수 있는 각 연산은 해당 인터페이스를 구현하는 새로운 클래스입니다. 이 클래스는 각 패스트리 타입에 대한 구체적인 메서드를 가집니다. 이는 두 타입에 대한 연산 코드를 모두 한 클래스 안에 아늑하게 함께 유지합니다.

주어진 패스트리를 그 타입에 따라 비지터의 올바른 메서드로 어떻게 라우팅할까요? 다형성(Polymorphism)이 해결책입니다! 다음 메서드를 Pastry에 추가합니다:

  abstract class Pastry {

    abstract void accept(PastryVisitor visitor);

  }

각 서브클래스가 이를 구현합니다.

  class Beignet extends Pastry {

    @Override
    void accept(PastryVisitor visitor) {
      visitor.visitBeignet(this);
    }

  }

그리고:

  class Cruller extends Pastry {

    @Override
    void accept(PastryVisitor visitor) {
      visitor.visitCruller(this);
    }

  }

패스트리에 대한 연산을 수행하려면, 해당 accept() 메서드를 호출하고 실행하려는 연산에 대한 비지터(visitor)를 전달합니다. 패스트리—즉, 특정 서브클래스의 오버라이딩된 accept() 구현—는 다시 비지터의 적절한 visit 메서드를 호출하고 자기 자신을 그 메서드에 전달합니다.

그것이 바로 이 트릭의 핵심입니다. 이는 패스트리 클래스에 대한 다형적 디스패치(polymorphic dispatch)를 사용하여 비지터 클래스에서 적절한 메서드를 선택할 수 있게 합니다. 표에서 각 패스트리 클래스는 행이지만, 단일 비지터의 모든 메서드를 보면 열을 이룹니다.

각 클래스에 하나의 accept() 메서드를 추가했으며, 이 메서드를 원하는 만큼의 비지터에 대해 다시 패스트리 클래스를 건드릴 필요 없이 사용할 수 있습니다. 이것은 영리한 패턴입니다.

5 . 3 . 3표현식을 위한 비지터

좋습니다, 이제 이를 우리 표현식 클래스에 통합해봅시다. 또한 이 패턴을 약간 개선할 것입니다. 패스트리 예시에서 visit 및 accept() 메서드는 아무것도 반환하지 않습니다. 실제로 비지터는 종종 값을 생성하는 연산을 정의하고 싶어 합니다. 하지만 accept()는 어떤 반환 타입을 가져야 할까요? 모든 비지터 클래스가 동일한 타입을 생성한다고 가정할 수 없으므로, 각 구현이 반환 타입을 채워 넣을 수 있도록 제네릭(generics)을 사용할 것입니다.

먼저, 비지터 인터페이스를 정의합니다. 다시 한번, 모든 것을 한 파일에 유지하기 위해 이를 기본 클래스 안에 중첩시킵니다.

    writer.println("abstract class " + baseName + " {");

    defineVisitor(writer, baseName, types);

    // The AST classes.

이 함수는 비지터 인터페이스를 생성합니다.

  private static void defineVisitor(
      PrintWriter writer, String baseName, List<String> types) {
    writer.println("  interface Visitor<R> {");

    for (String type : types) {
      String typeName = type.split(":")[0].trim();
      writer.println("    R visit" + typeName + baseName + "(" +
          typeName + " " + baseName.toLowerCase() + ");");
    }

    writer.println("  }");
  }

여기서 우리는 모든 서브클래스를 순회하며 각각에 대한 visit 메서드를 선언합니다. 나중에 새로운 표현식 타입을 정의할 때, 이것들은 자동으로 포함될 것입니다.

기본 클래스 내부에 추상 accept() 메서드를 정의합니다.

      defineType(writer, baseName, className, fields);
    }

    // 기본 accept() 메서드.
    writer.println();
    writer.println("  abstract <R> R accept(Visitor<R> visitor);");

    writer.println("}");

마지막으로, 각 서브클래스는 이를 구현하고 자신의 타입에 맞는 올바른 visit 메서드를 호출합니다.

    writer.println("    }");

    // 비지터 패턴.
    writer.println();
    writer.println("    @Override");
    writer.println("    <R> R accept(Visitor<R> visitor) {");
    writer.println("      return visitor.visit" +
        className + baseName + "(this);");
    writer.println("    }");

    // Fields.

자, 됐습니다. 이제 클래스나 생성기 스크립트를 건드릴 필요 없이 표현식에 대한 연산을 정의할 수 있습니다. 이 생성기 스크립트를 컴파일하고 실행하여 업데이트된 "Expr.java" 파일을 출력합니다. 이 파일에는 생성된 Visitor 인터페이스와 이를 사용하여 비지터 패턴을 지원하는 표현식 노드 클래스 집합이 포함되어 있습니다.

이 장황한 장을 마치기 전에, 비지터 인터페이스를 구현하고 이 패턴이 어떻게 작동하는지 살펴봅시다.

5 . 4(그리 예쁘지 않은) 예쁜 출력기

파서와 인터프리터를 디버깅할 때, 파싱된 구문 트리를 보고 우리가 예상하는 구조를 가지고 있는지 확인하는 것이 종종 유용합니다. 디버거에서 검사할 수도 있지만, 이는 번거로운 작업일 수 있습니다.

대신, 구문 트리가 주어졌을 때 모호하지 않은 문자열 표현을 생성하는 코드를 원합니다. 트리를 문자열로 변환하는 것은 파서의 반대 개념이며, 소스 언어에서 유효한 구문 텍스트 문자열을 생성하는 것이 목표일 때 종종 "예쁜 출력(pretty printing)"이라고 불립니다.

여기서는 그것이 우리의 목표가 아닙니다. 우리는 문자열이 트리의 중첩 구조를 매우 명시적으로 보여주기를 원합니다. 만약 연산자 우선순위가 올바르게 처리되었는지 디버깅하려는 경우, 1 + 2 * 3을 반환하는 출력기는 크게 도움이 되지 않습니다. 우리는 + 또는 *가 트리 꼭대기에 있는지 알고 싶습니다.

이를 위해, 우리가 생성할 문자열 표현은 Lox 문법이 아닐 것입니다. 대신, 리스프(Lisp)와 매우 유사하게 보일 것입니다. 각 표현식은 명시적으로 괄호로 묶이며, 모든 하위 표현식과 토큰이 그 안에 포함됩니다.

다음과 같은 구문 트리가 주어졌을 때:

다음과 같이 출력됩니다:

(* (- 123) (group 45.67))

정확히 "예쁘다"고 할 수는 없지만, 중첩과 그룹화를 명시적으로 보여줍니다. 이를 구현하기 위해 새로운 클래스를 정의합니다.

package com.craftinginterpreters.lox;

class AstPrinter implements Expr.Visitor<String> {
  String print(Expr expr) {
    return expr.accept(this);
  }
}

보시다시피, 이것은 비지터 인터페이스를 구현합니다. 즉, 지금까지 우리가 가진 각 표현식 타입에 대한 visit 메서드가 필요합니다.

    return expr.accept(this);
  }

  @Override
  public String visitBinaryExpr(Expr.Binary expr) {
    return parenthesize(expr.operator.lexeme,
                        expr.left, expr.right);
  }

  @Override
  public String visitGroupingExpr(Expr.Grouping expr) {
    return parenthesize("group", expr.expression);
  }

  @Override
  public String visitLiteralExpr(Expr.Literal expr) {
    if (expr.value == null) return "nil";
    return expr.value.toString();
  }

  @Override
  public String visitUnaryExpr(Expr.Unary expr) {
    return parenthesize(expr.operator.lexeme, expr.right);
  }

}

리터럴 표현식은 쉽습니다—Lox의 nil을 대신하는 자바의 null을 처리하기 위한 작은 검사를 통해 값을 문자열로 변환합니다. 다른 표현식들은 하위 표현식을 가지므로, parenthesize() 도우미 메서드를 사용합니다:

  private String parenthesize(String name, Expr... exprs) {
    StringBuilder builder = new StringBuilder();

    builder.append("(").append(name);
    for (Expr expr : exprs) {
      builder.append(" ");
      builder.append(expr.accept(this));
    }
    builder.append(")");

    return builder.toString();
  }

이 메서드는 이름과 하위 표현식 목록을 받아 모두 괄호로 묶어 다음과 같은 문자열을 생성합니다:

(+ 1 2)

각 하위 표현식에 대해 accept()를 호출하고 자신을 전달한다는 점에 유의하세요. 이것이 전체 트리를 출력할 수 있게 해주는 재귀적인 단계입니다.

아직 파서가 없으므로 이것이 실제로 작동하는 것을 보기는 어렵습니다. 지금은 트리를 수동으로 인스턴스화하고 출력하는 작은 main() 메서드를 만들어 볼 것입니다.

  public static void main(String[] args) {
    Expr expression = new Expr.Binary(
        new Expr.Unary(
            new Token(TokenType.MINUS, "-", null, 1),
            new Expr.Literal(123)),
        new Token(TokenType.STAR, "*", null, 1),
        new Expr.Grouping(
            new Expr.Literal(45.67)));

    System.out.println(new AstPrinter().print(expression));
  }

모든 것을 올바르게 했다면, 다음과 같이 출력됩니다:

(* (- 123) (group 45.67))

이 메서드는 삭제해도 좋습니다. 더 이상 필요하지 않습니다. 또한, 새로운 구문 트리 타입을 추가할 때마다 AstPrinter에 필요한 visit 메서드를 보여주지 않을 것입니다. 원한다면(그리고 자바 컴파일러가 경고하지 않기를 원한다면) 직접 추가하세요. 이는 다음 장에서 Lox 코드를 구문 트리로 파싱하기 시작할 때 유용할 것입니다. 또는 AstPrinter를 유지하고 싶지 않다면 자유롭게 삭제하세요. 다시 필요 없을 것입니다.