표현식 파싱

왕까지도 통제하는 문법.

몰리에르

이 장은 이 책의 첫 번째 주요 이정표입니다. 우리 중 많은 이들이 정규 표현식과 부분 문자열 연산을 뒤섞어 텍스트 더미에서 의미를 추출하곤 했습니다. 그 코드는 아마 버그 투성이였고 유지보수하기가 매우 어려웠을 것입니다. 괜찮은 오류 처리, 일관된 내부 구조, 그리고 정교한 문법을 견고하게 처리할 수 있는 능력을 갖춘 *진정한* 파서를 작성하는 것은 드물고 인상적인 기술로 여겨집니다. 이 장에서 여러분은 그 기술을 습득하게 될 것입니다.

이것은 생각보다 쉽습니다. 부분적으로는 지난 장에서 많은 어려운 작업을 미리 처리해 두었기 때문입니다. 여러분은 이미 형식 문법에 익숙합니다. 구문 트리에 익숙하며, 이를 표현할 몇 가지 Java 클래스도 가지고 있습니다. 남은 유일한 조각은 파싱입니다. 즉, 토큰 시퀀스를 구문 트리 중 하나로 변환하는 것입니다.

일부 컴퓨터 과학 교과서에서는 파서에 대해 거창하게 설명합니다. 1960년대, 컴퓨터 과학자들은—당연히 어셈블리 언어로 프로그래밍하는 것에 지쳐—포트란(Fortran)과 알골(ALGOL)처럼 더 정교하고 인간 친화적인 언어를 설계하기 시작했습니다. 아쉽게도, 당시의 초보적인 컴퓨터에는 *기계* 친화적이지 않았습니다.

이 개척자들은 자신들이 컴파일러를 어떻게 작성해야 할지조차 확신하지 못했던 언어들을 설계했고, 그 후 오래되고 작은 기계에서 이 새롭고 거대한 언어들을 처리할 수 있는 파싱 및 컴파일 기술을 발명하는 혁신적인 작업을 수행했습니다.

고전적인 컴파일러 서적들은 이 영웅들과 그들의 도구에 대한 아첨하는 성인 전기처럼 읽힙니다. *Compilers: Principles, Techniques, and Tools* 책 표지에는 문자 그대로 '컴파일러 설계의 복잡성'이라고 라벨링된 용이 'LALR 파서 생성기'와 '구문 지향 번역'이라는 문구가 새겨진 검과 방패를 든 기사에 의해 살해당하는 모습이 그려져 있습니다. 그들은 과장해서 표현했습니다.

약간의 자축은 당연하지만, 사실 현대적인 기계에서 고품질 파서를 뚝딱 만들어내기 위해 그 모든 것을 알 필요는 없습니다. 늘 그렇듯, 나중에 지식을 넓혀 배우는 것을 권장하지만, 이 책에서는 불필요한 내용들을 생략하겠습니다.

6 . 1모호성과 파싱 게임

지난 장에서, 저는 문자열을 *생성하기* 위해 컨텍스트 프리 문법을 게임처럼 '플레이'할 수 있다고 말했습니다. 파서는 그 게임을 역으로 수행합니다. 문자열(토큰의 연속)이 주어지면, 해당 토큰을 문법의 터미널에 매핑하여 어떤 규칙이 그 문자열을 생성했을지 알아냅니다.

'생성했을 수 있다'는 부분은 흥미롭습니다. 서로 다른 프로덕션(생성 규칙) 선택이 동일한 문자열로 이어질 수 있는 *모호한* 문법을 만드는 것은 전적으로 가능합니다. 문법을 사용하여 문자열을 *생성*할 때는 그것이 크게 중요하지 않습니다. 일단 문자열을 얻고 나면, 어떻게 얻었는지는 누가 신경 쓰겠습니까?

파싱할 때, 모호성은 파서가 사용자의 코드를 오해할 수 있음을 의미합니다. 파싱하는 동안, 우리는 단순히 문자열이 유효한 Lox 코드인지 여부를 판단하는 것뿐만 아니라, 어떤 규칙이 어떤 부분에 일치하는지 추적하여 각 토큰이 언어의 어느 부분에 속하는지 파악합니다. 다음은 지난 장에서 우리가 함께 만든 Lox 표현식 문법입니다.

expression     → literal
               | unary
               | binary
               | grouping ;

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

이것은 그 문법에서 유효한 문자열입니다.

하지만 이를 생성할 수 있는 방법은 두 가지입니다. 한 가지 방법은 다음과 같습니다.

1. `expression`에서 시작하여 `binary`를 선택합니다.
2. 왼쪽 `expression`에 대해 `NUMBER`를 선택하고 `6`을 사용합니다.
3. 연산자에 대해 `/`를 선택합니다.
4. 오른쪽 `expression`에 대해 다시 `binary`를 선택합니다.
5. 중첩된 `binary` 표현식에서 `3 - 1`을 선택합니다.

다른 방법은 다음과 같습니다.

1. `expression`에서 시작하여 `binary`를 선택합니다.
2. 왼쪽 `expression`에 대해 다시 `binary`를 선택합니다.
3. 중첩된 `binary` 표현식에서 `6 / 3`을 선택합니다.
4. 바깥쪽 `binary`로 돌아와 연산자에 대해 `-`를 선택합니다.
5. 오른쪽 `expression`에 대해 `NUMBER`를 선택하고 `1`을 사용합니다.

이들은 동일한 *문자열*을 생성하지만, 동일한 *구문 트리*를 생성하지는 않습니다.

다시 말해, 이 문법은 표현식을 `(6 / 3) - 1` 또는 `6 / (3 - 1)`로 볼 수 있게 합니다. `binary` 규칙은 피연산자가 원하는 방식으로 중첩될 수 있도록 합니다. 이는 파싱된 트리를 평가하는 결과에 영향을 미칩니다. 수학자들이 칠판이 처음 발명된 이래로 이 모호성을 해결해 온 방법은 우선순위와 결합 방향에 대한 규칙을 정의하는 것입니다.

• **우선순위(Precedence)**는 서로 다른 연산자가 혼합된 표현식에서 어떤 연산자가 먼저 평가될지 결정합니다. 우선순위 규칙은 위 예시에서 `-`보다 `/`를 먼저 평가해야 한다고 알려줍니다. 우선순위가 높은 연산자는 우선순위가 낮은 연산자보다 먼저 평가됩니다. 마찬가지로, 우선순위가 높은 연산자는 '더 강하게 결합한다(bind tighter)'고 말합니다.

• **결합 방향(Associativity)**은 *동일한* 연산자가 연속될 때 어떤 연산자가 먼저 평가될지 결정합니다. 연산자가 **좌측 결합(left-associative)**일 때 (즉, '왼쪽에서 오른쪽으로'를 생각하면), 왼쪽에 있는 연산자가 오른쪽에 있는 연산자보다 먼저 평가됩니다. `-`는 좌측 결합이므로, 이 표현식은 다음과 같습니다.

  5 - 3 - 1
  

  다음과 같습니다.

  (5 - 3) - 1
  

  반면에 할당 연산자는 **우측 결합(right-associative)**입니다. 이 표현식은 다음과 같습니다.

  a = b = c
  

  다음과 같습니다.

  a = (b = c)
  

잘 정의된 우선순위와 결합 방향 없이는 여러 연산자를 사용하는 표현식은 모호해집니다. 이는 서로 다른 구문 트리로 파싱될 수 있으며, 결과적으로 다른 평가 결과를 낼 수 있습니다. 우리는 C와 동일한 우선순위 규칙을 적용하여 Lox에서 이 문제를 해결할 것입니다. 가장 낮은 우선순위부터 가장 높은 우선순위로 나열됩니다.

현재, 문법은 모든 표현식 타입을 단일 `expression` 규칙에 밀어 넣습니다. 그 동일한 규칙은 피연산자에 대한 비터미널로 사용되며, 우선순위 규칙이 허용하는지 여부와 관계없이 어떤 종류의 표현식도 하위 표현식으로 허용하게 합니다.

우리는 문법을 계층화하여 이를 수정합니다. 각 우선순위 레벨에 대해 별도의 규칙을 정의합니다.

expression     → ...
equality       → ...
comparison     → ...
term           → ...
factor         → ...
unary          → ...
primary        → ...

여기서 각 규칙은 해당 우선순위 레벨 이상의 표현식만 일치시킵니다. 예를 들어, `unary`는 `!negated`와 같은 단항 표현식이나 `1234`와 같은 기본 표현식과 일치합니다. 그리고 `term`은 `1 + 2`뿐만 아니라 `3 * 4 / 5`도 일치시킬 수 있습니다. 최종 `primary` 규칙은 가장 높은 우선순위 형태인 리터럴과 괄호로 묶인 표현식을 다룹니다.

우리는 이제 각 규칙에 대한 프로덕션을 채워 넣기만 하면 됩니다. 쉬운 것부터 먼저 하겠습니다. 최상위 `expression` 규칙은 어떤 우선순위 레벨의 어떤 표현식과도 일치합니다. `equality`가 가장 낮은 우선순위를 가지므로, 이를 일치시키면 모든 것을 포함하게 됩니다.

expression     → equality

우선순위 테이블의 다른 한쪽 끝에는 기본 표현식(primary expression)이 모든 리터럴과 그룹화 표현식을 포함합니다.

primary        → NUMBER | STRING | "true" | "false" | "nil"
               | "(" expression ")" ;

단항 표현식은 단항 연산자로 시작하고 그 뒤에 피연산자가 옵니다. 단항 연산자는 중첩될 수 있으므로(`!!true`는 유효하지만 이상한 표현식입니다), 피연산자 자체가 단항 연산자일 수 있습니다. 재귀 규칙이 이를 잘 처리합니다.

unary          → ( "!" | "-" ) unary ;

하지만 이 규칙에는 문제가 있습니다. 결코 종료되지 않습니다.

기억하세요, 각 규칙은 해당 우선순위 레벨 *이상*의 표현식과 일치해야 하므로, 이 규칙이 기본 표현식(primary expression)과도 일치하도록 허용해야 합니다.

unary          → ( "!" | "-" ) unary
               | primary ;

이것은 작동합니다.

남은 규칙들은 모두 이항 연산자입니다. 곱셈과 나눗셈에 대한 규칙부터 시작하겠습니다. 첫 번째 시도는 다음과 같습니다.

factor         → factor ( "/" | "*" ) unary
               | unary ;

이 규칙은 왼쪽 피연산자를 일치시키기 위해 재귀합니다. 이를 통해 규칙은 `1 * 2 / 3`과 같은 일련의 곱셈 및 나눗셈 표현식을 일치시킬 수 있습니다. 재귀 프로덕션을 왼쪽에, `unary`를 오른쪽에 두면 이 규칙은 좌측 결합(left-associative)이 되고 모호하지 않게 됩니다.

이 모든 것이 정확하지만, 규칙 본문의 첫 번째 기호가 규칙의 헤드와 동일하다는 사실은 이 프로덕션이 **좌측 재귀(left-recursive)**임을 의미합니다. 우리가 사용할 파싱 기술을 포함한 일부 파싱 기술은 좌측 재귀에 문제가 있습니다. ( `unary`에서 보이는 재귀나 `primary`에서 그룹화를 위한 간접 재귀는 문제가 되지 않습니다.)

동일한 언어와 일치하는 많은 문법을 정의할 수 있습니다. 특정 언어를 모델링하는 방법에 대한 선택은 부분적으로는 취향의 문제이고 부분적으로는 실용적인 문제입니다. 이 규칙은 정확하지만, 우리가 파싱하려는 방식에는 최적이지 않습니다. 좌측 재귀 규칙 대신 다른 규칙을 사용하겠습니다.

factor         → unary ( ( "/" | "*" ) unary )* ;

우리는 인수 표현식(factor expression)을 곱셈과 나눗셈의 평탄한 *시퀀스*로 정의합니다. 이것은 이전 규칙과 동일한 구문에 일치하지만, Lox를 파싱하기 위해 작성할 코드와 더 잘 부합합니다. 우리는 다른 모든 이항 연산자 우선순위 레벨에 동일한 구조를 사용하여 이 완전한 표현식 문법을 얻습니다.

expression     → equality ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" ) unary )* ;
unary          → ( "!" | "-" ) unary
               | primary ;
primary        → NUMBER | STRING | "true" | "false" | "nil"
               | "(" expression ")" ;

이 문법은 이전에 우리가 가졌던 것보다 더 복잡하지만, 그 대가로 이전 문법의 모호성을 제거했습니다. 이것이 바로 파서를 만드는 데 필요한 전부입니다.

6 . 2재귀 하향 파싱

파싱 기법에는 LL(k), LR(1), LALR처럼 주로 'L'과 'R'의 조합으로 이루어진 이름들이 많으며, 파서 컴비네이터, 얼리 파서, 셔플링 야드 알고리즘, 팩랫 파싱과 같은 더 이국적인 기법들도 있습니다. 첫 번째 인터프리터에는 한 가지 기법으로도 충분합니다: **재귀 하향 파싱(recursive descent)**.

재귀 하향 파싱은 파서를 구축하는 가장 간단한 방법이며, Yacc, Bison 또는 ANTLR과 같은 복잡한 파서 생성 도구를 사용할 필요가 없습니다. 필요한 것은 간단한 수작업 코드뿐입니다. 하지만 그 단순함에 속지 마세요. 재귀 하향 파서는 빠르고 견고하며, 정교한 오류 처리를 지원할 수 있습니다. 실제로 GCC, V8 (크롬의 JavaScript VM), Roslyn (C#으로 작성된 C# 컴파일러) 및 다른 많은 대규모 실제 언어 구현체들이 재귀 하향 파싱을 사용합니다. 정말 훌륭합니다.

재귀 하향 파서는 가장 상위 또는 가장 바깥쪽 문법 규칙(여기서는 `expression`)에서 시작하여 중첩된 하위 표현식으로 내려간 다음 최종적으로 구문 트리의 리프(leaf)에 도달하기 때문에 **하향식 파서(top-down parser)**로 간주됩니다. 이는 기본 표현식부터 시작하여 점점 더 큰 구문 덩어리로 구성해 나가는 LR과 같은 상향식 파서(bottom-up parser)와 대조됩니다.

재귀 하향 파서는 문법 규칙을 명령형 코드로 문자 그대로 번역한 것입니다. 각 규칙은 함수가 됩니다. 규칙의 본문은 대략 다음과 같은 코드로 번역됩니다.

이 하향식(descent)은 문법 규칙이 직접적 또는 간접적으로 자기 자신을 참조할 때 재귀 함수 호출로 변환되기 때문에 '재귀적(recursive)'이라고 설명됩니다.

6 . 2 . 1파서 클래스

각 문법 규칙은 이 새로운 클래스 내부의 메서드가 됩니다.

package com.craftinginterpreters.lox;

import java.util.List;

import static com.craftinginterpreters.lox.TokenType.*;

class Parser {
  private final List<Token> tokens;
  private int current = 0;

  Parser(List<Token> tokens) {
    this.tokens = tokens;
  }
}

스캐너와 마찬가지로, 파서는 평탄한 입력 시퀀스를 소비합니다. 단, 이제 우리는 문자 대신 토큰을 읽습니다. 토큰 목록을 저장하고 `current`를 사용하여 다음으로 파싱될 토큰을 가리킵니다.

이제 표현식 문법을 곧바로 살펴보고 각 규칙을 Java 코드로 번역할 것입니다. 첫 번째 규칙인 `expression`은 단순히 `equality` 규칙으로 확장되므로 간단합니다.

  private Expr expression() {
    return equality();
  }

문법 규칙을 파싱하는 각 메서드는 해당 규칙에 대한 구문 트리를 생성하고 호출자에게 반환합니다. 규칙의 본문에 비터미널(다른 규칙에 대한 참조)이 포함될 때, 우리는 그 다른 규칙의 메서드를 호출합니다.

동등성(equality) 규칙은 조금 더 복잡합니다.

equality       → comparison ( ( "!=" | "==" ) comparison )* ;

Java로 변환하면 다음과 같습니다.

  private Expr equality() {
    Expr expr = comparison();

    while (match(BANG_EQUAL, EQUAL_EQUAL)) {
      Token operator = previous();
      Expr right = comparison();
      expr = new Expr.Binary(expr, operator, right);
    }

    return expr;
  }

한 단계씩 살펴보겠습니다. 본문 내의 첫 번째 `comparison` 비터미널은 메서드의 `comparison()`에 대한 첫 번째 호출로 변환됩니다. 우리는 그 결과를 가져와 지역 변수에 저장합니다.

그 다음, 규칙의 `( ... )*` 루프는 `while` 루프로 매핑됩니다. 우리는 언제 그 루프를 종료해야 할지 알아야 합니다. 우리는 규칙 내부에서 먼저 `!=` 또는 `==` 토큰 중 하나를 찾아야 함을 알 수 있습니다. 따라서 만약 이 토큰 중 하나도 보이지 *않는다면*, 동등성 연산자 시퀀스가 끝났다는 뜻입니다. 우리는 편리한 `match()` 메서드를 사용하여 이 확인을 표현합니다.

  private boolean match(TokenType... types) {
    for (TokenType type : types) {
      if (check(type)) {
        advance();
        return true;
      }
    }

    return false;
  }

이것은 현재 토큰이 주어진 타입들 중 하나를 가지고 있는지 확인합니다. 만약 그렇다면, 토큰을 소비하고 `true`를 반환합니다. 그렇지 않으면 `false`를 반환하고 현재 토큰을 그대로 둡니다. `match()` 메서드는 두 가지 더 기본적인 연산을 기반으로 정의됩니다.

`check()` 메서드는 현재 토큰이 주어진 타입이면 `true`를 반환합니다. `match()`와 달리, 이것은 토큰을 소비하지 않고 단지 확인만 합니다.

  private boolean check(TokenType type) {
    if (isAtEnd()) return false;
    return peek().type == type;
  }

`advance()` 메서드는 현재 토큰을 소비하고 반환합니다. 이는 스캐너의 해당 메서드가 문자를 탐색했던 방식과 유사합니다.

  private Token advance() {
    if (!isAtEnd()) current++;
    return previous();
  }

이 메서드들은 마지막 몇 가지 기본 연산에 기반을 둡니다.

  private boolean isAtEnd() {
    return peek().type == EOF;
  }

  private Token peek() {
    return tokens.get(current);
  }

  private Token previous() {
    return tokens.get(current - 1);
  }

`isAtEnd()`는 파싱할 토큰이 모두 소진되었는지 확인합니다. `peek()`는 아직 소비하지 않은 현재 토큰을 반환하고, `previous()`는 가장 최근에 소비된 토큰을 반환합니다. 후자는 `match()`를 사용한 다음 방금 일치된 토큰에 접근하는 것을 더 쉽게 만듭니다.

이것이 우리가 필요로 하는 대부분의 파싱 인프라입니다. 어디까지 했죠? 맞아요, `equality()`의 `while` 루프 안에 있다면, 우리는 `!=` 또는 `==` 연산자를 찾았고 동등성 표현식을 파싱하고 있음을 알 수 있습니다. 일치된 연산자 토큰을 가져와 어떤 종류의 동등성 표현식인지 추적할 수 있습니다. 그런 다음 `comparison()`을 다시 호출하여 오른쪽 피연산자를 파싱합니다. 연산자와 두 피연산자를 새로운 `Expr.Binary` 구문 트리 노드로 결합한 다음 루프를 다시 시작합니다. 각 반복마다, 결과 표현식을 동일한 `expr` 지역 변수에 다시 저장합니다. 일련의 동등성 표현식을 처리하면서, 그것은 좌측 결합(left-associative) 이항 연산자 노드의 중첩된 트리를 생성합니다.

파서는 동등성 연산자가 아닌 토큰을 만나면 루프에서 벗어납니다. 마지막으로 표현식을 반환합니다. 파서가 동등성 연산자를 전혀 만나지 않으면, 루프에 들어가지 않는다는 점에 유의하세요. 이 경우, `equality()` 메서드는 사실상 `comparison()`을 호출하고 그 결과를 반환합니다. 이런 식으로, 이 메서드는 동등성 연산자 *또는 그보다 우선순위가 높은 어떤 것*이든 일치시킵니다.

다음 규칙으로 넘어가겠습니다. . . . 

comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;

Java로 변환하면 다음과 같습니다.

  private Expr comparison() {
    Expr expr = term();

    while (match(GREATER, GREATER_EQUAL, LESS, LESS_EQUAL)) {
      Token operator = previous();
      Expr right = term();
      expr = new Expr.Binary(expr, operator, right);
    }

    return expr;
  }

이 문법 규칙은 `equality`와 사실상 동일하며, 해당 코드도 마찬가지입니다. 유일한 차이점은 우리가 일치시키는 연산자의 토큰 타입과 피연산자에 대해 호출하는 메서드입니다. 이제 `comparison()` 대신 `term()`을 호출합니다. 남은 두 이항 연산자 규칙도 같은 패턴을 따릅니다.

우선순위 순서대로, 먼저 덧셈과 뺄셈입니다.

  private Expr term() {
    Expr expr = factor();

    while (match(MINUS, PLUS)) {
      Token operator = previous();
      Expr right = factor();
      expr = new Expr.Binary(expr, operator, right);
    }

    return expr;
  }

그리고 마지막으로, 곱셈과 나눗셈입니다.

  private Expr factor() {
    Expr expr = unary();

    while (match(SLASH, STAR)) {
      Token operator = previous();
      Expr right = unary();
      expr = new Expr.Binary(expr, operator, right);
    }

    return expr;
  }

이것으로 모든 이항 연산자가 올바른 우선순위와 결합 방향으로 파싱되었습니다. 우리는 우선순위 계층을 위로 올라가고 있으며, 이제 단항 연산자에 도달했습니다.

unary          → ( "!" | "-" ) unary
               | primary ;

이 코드는 조금 다릅니다.

  private Expr unary() {
    if (match(BANG, MINUS)) {
      Token operator = previous();
      Expr right = unary();
      return new Expr.Unary(operator, right);
    }

    return primary();
  }

다시, 우리는 파싱 방법을 결정하기 위해 현재 토큰을 살펴봅니다. 만약 `!` 또는 `-`라면, 우리는 단항 표현식을 가지고 있을 것입니다. 이 경우, 우리는 토큰을 가져온 다음 `unary()`를 다시 재귀적으로 호출하여 피연산자를 파싱합니다. 그 모든 것을 단항 표현식 구문 트리로 묶으면 작업이 완료됩니다.

그렇지 않다면, 우리는 가장 높은 우선순위 수준인 기본 표현식(primary expressions)에 도달했을 것입니다.

primary        → NUMBER | STRING | "true" | "false" | "nil"
               | "(" expression ")" ;

이 규칙의 대부분의 경우는 단일 터미널이므로, 파싱은 간단합니다.

  private Expr primary() {
    if (match(FALSE)) return new Expr.Literal(false);
    if (match(TRUE)) return new Expr.Literal(true);
    if (match(NIL)) return new Expr.Literal(null);

    if (match(NUMBER, STRING)) {
      return new Expr.Literal(previous().literal);
    }

    if (match(LEFT_PAREN)) {
      Expr expr = expression();
      consume(RIGHT_PAREN, "Expect ')' after expression.");
      return new Expr.Grouping(expr);
    }
  }

흥미로운 분기는 괄호 처리 부분입니다. 여는 `(`를 일치시키고 그 안의 표현식을 파싱한 후에는 닫는 `)` 토큰을 *반드시* 찾아야 합니다. 그렇지 않으면 오류입니다.

6 . 3구문 오류

파서는 사실 두 가지 작업을 수행합니다.

1. 유효한 토큰 시퀀스가 주어지면, 해당 구문 트리를 생성합니다.

2. *유효하지 않은* 토큰 시퀀스가 주어지면, 모든 오류를 감지하고 사용자에게 그들의 실수를 알려줍니다.

두 번째 작업이 얼마나 중요한지 과소평가하지 마세요! 현대 IDE와 편집기에서는 파서가 구문 강조 및 자동 완성 같은 기능을 지원하기 위해 코드를 계속해서 재파싱합니다. 사용자가 아직 코드를 편집하는 중에도 말이죠. 이는 파서가 항상 불완전하거나 반쯤 틀린 상태의 코드를 마주하게 될 것임을 의미합니다.

사용자가 구문이 틀렸다는 것을 인식하지 못할 때, 올바른 길로 안내하는 것은 파서의 역할입니다. 파서가 오류를 보고하는 방식은 언어의 사용자 인터페이스의 큰 부분을 차지합니다. 좋은 구문 오류 처리는 어렵습니다. 정의상 코드가 잘 정의된 상태가 아니므로, 사용자가 무엇을 작성하려고 *했는지* 알 수 있는 확실한 방법은 없습니다. 파서는 여러분의 마음을 읽을 수 없습니다.

파서가 구문 오류를 만났을 때 몇 가지 엄격한 요구 사항이 있습니다. 파서는 다음을 수행해야 합니다.

• **오류를 감지하고 보고해야 합니다.** 만약 오류를 감지하지 못하고 잘못 형성된 구문 트리를 인터프리터에 전달한다면, 온갖 끔찍한 일들이 벌어질 수 있습니다.

• **충돌하거나 멈추는 것을 피해야 합니다.** 구문 오류는 피할 수 없는 현실이며, 언어 도구는 이에 대해 견고해야 합니다. 세그먼트 오류가 발생하거나 무한 루프에 빠지는 것은 허용되지 않습니다. 소스가 유효한 *코드*는 아닐지라도, 사용자들이 파서를 통해 허용되는 구문을 배우기 때문에 여전히 *파서에 대한 유효한 입력*입니다.

이것들은 파서 게임에 참여하기 위한 기본 요건이지만, 실제로는 그 이상을 목표로 해야 합니다. 괜찮은 파서는 다음을 수행해야 합니다.

• **빨라야 합니다.** 컴퓨터는 파서 기술이 처음 발명되었을 때보다 수천 배 더 빠릅니다. 커피 한 잔 마시는 동안 전체 소스 파일을 처리할 수 있도록 파서를 최적화해야 했던 시대는 지났습니다. 하지만 프로그래머의 기대치는 그만큼 빠르게, 아니면 더 빠르게 높아졌습니다. 그들은 키보드를 누를 때마다 편집기가 파일을 밀리초 단위로 재파싱하기를 기대합니다.

• **존재하는 만큼의 모든 개별 오류를 보고해야 합니다.** 첫 번째 오류 후 중단하는 것은 구현하기 쉽지만, 사용자들이 파일의 유일한 오류라고 생각한 것을 고칠 때마다 새로운 오류가 나타나면 짜증을 유발합니다. 그들은 모든 오류를 보고 싶어 합니다.

• **연쇄(cascaded) 오류를 최소화해야 합니다.** 하나의 오류가 발견되면, 파서는 더 이상 실제로 무슨 일이 일어나고 있는지 알지 못합니다. 파서는 스스로 정상 궤도로 돌아와 계속 진행하려고 노력하지만, 혼란스러워지면 코드 내의 다른 실제 문제를 나타내지 않는 수많은 유령 오류를 보고할 수 있습니다. 첫 번째 오류가 수정되면, 그러한 유령 오류들은 사라집니다. 이는 단순히 파서 자체의 혼란을 반영하기 때문입니다. 연쇄 오류는 사용자가 자신의 코드가 실제보다 더 나쁜 상태라고 생각하게 만들 수 있기 때문에 짜증을 유발합니다.

마지막 두 가지 요점은 서로 상충됩니다. 우리는 가능한 한 많은 개별 오류를 보고하고 싶지만, 단순히 이전 오류의 부작용인 오류는 보고하고 싶지 않습니다.

파서가 오류에 대응하고 계속해서 이후 오류를 찾는 방식을 **오류 복구(error recovery)**라고 합니다. 이것은 1960년대에 뜨거운 연구 주제였습니다. 그 당시에는 천공 카드 더미를 비서에게 건네주고 다음 날 컴파일러가 성공했는지 확인하러 돌아오곤 했습니다. 그렇게 느린 반복 주기에서는 한 번의 실행으로 코드의 모든 오류를 *정말로* 찾아내고 싶었을 것입니다.

오늘날, 파서가 타이핑을 마치기도 전에 작업을 완료하므로, 이는 덜 문제가 됩니다. 간단하고 빠른 오류 복구면 충분합니다.

6 . 3 . 1패닉 모드 오류 복구

과거에 고안된 모든 복구 기술 중에서 시간의 시험을 가장 잘 견뎌낸 것은 다소 놀랍게도 **패닉 모드(panic mode)**라고 불리는 것입니다. 파서가 오류를 감지하는 즉시 패닉 모드에 진입합니다. 파서는 문법 프로덕션 스택 중간의 현재 상태를 고려할 때 적어도 하나의 토큰이 말이 되지 않는다는 것을 압니다.

파싱으로 돌아가기 전에, 파서는 다음 토큰이 파싱 중인 규칙과 일치하도록 자신의 상태와 앞으로 올 토큰 시퀀스를 정렬해야 합니다. 이 과정을 **동기화(synchronization)**라고 합니다.

이를 위해 우리는 문법에서 동기화 지점을 표시할 특정 규칙을 선택합니다. 파서는 중첩된 모든 프로덕션에서 벗어나 해당 규칙으로 돌아갈 때까지 파싱 상태를 수정합니다. 그런 다음 토큰 스트림을 동기화하기 위해, 규칙의 해당 지점에 나타날 수 있는 토큰에 도달할 때까지 토큰들을 버립니다.

버려진 토큰에 숨겨진 추가적인 실제 구문 오류는 보고되지 않지만, 이는 또한 초기 오류의 부작용인 잘못된 연쇄 오류도 *거짓으로* 보고되지 않음을 의미합니다. 이는 합리적인 절충안입니다.

문법에서 동기화하는 전통적인 위치는 문장(statement) 사이입니다. 우리는 아직 문장을 가지고 있지 않으므로, 이 장에서는 실제로 동기화하지 않을 것이지만, 나중에 사용할 메커니즘을 미리 마련해 둘 것입니다.

6 . 3 . 2패닉 모드 진입하기

오류 복구에 대한 이 여담으로 빠지기 전, 우리는 괄호로 묶인 표현식을 파싱하는 코드를 작성하고 있었습니다. 표현식을 파싱한 후, 파서는 `consume()`을 호출하여 닫는 `)`를 찾습니다. 여기, 마침내 그 메서드가 있습니다.

  private Token consume(TokenType type, String message) {
    if (check(type)) return advance();

    throw error(peek(), message);
  }

이것은 다음 토큰이 예상된 타입인지 확인한다는 점에서 `match()`와 유사합니다. 만약 그렇다면, 토큰을 소비하고 모든 것이 순조롭게 진행됩니다. 다른 토큰이 있다면, 오류가 발생한 것입니다. 우리는 다음을 호출하여 이를 보고합니다.

  private ParseError error(Token token, String message) {
    Lox.error(token, message);
    return new ParseError();
  }

먼저, 다음을 호출하여 사용자에게 오류를 보여줍니다.

  static void error(Token token, String message) {
    if (token.type == TokenType.EOF) {
      report(token.line, " at end", message);
    } else {
      report(token.line, " at '" + token.lexeme + "'", message);
    }
  }

이것은 주어진 토큰 위치에서 오류를 보고합니다. 이는 토큰의 위치와 토큰 자체를 보여줍니다. 우리는 인터프리터 전체에서 코드 내 위치를 추적하기 위해 토큰을 사용하므로, 이것은 나중에 유용할 것입니다.

오류를 보고한 후, 사용자는 자신의 실수를 알게 되지만, *파서*는 다음에 무엇을 할까요? `error()`로 돌아와, 우리는 이 새로운 클래스의 인스턴스인 ParseError를 생성하고 반환합니다.

class Parser {

  private static class ParseError extends RuntimeException {}

  private final List<Token> tokens;

이것은 파서를 되감기(unwind)하기 위해 사용하는 간단한 센티넬 클래스입니다. `error()` 메서드는 오류를 *던지는(throwing)* 대신 *반환*합니다. 왜냐하면 파서 내부의 호출 메서드가 되감을지 말지를 결정하도록 허용하고 싶기 때문입니다. 일부 파싱 오류는 파서가 이상한 상태에 빠질 가능성이 없는 곳에서 발생하며, 우리는 동기화할 필요가 없습니다. 그런 곳에서는 단순히 오류를 보고하고 계속 진행합니다.

예를 들어, Lox는 함수에 전달할 수 있는 인수의 수를 제한합니다. 너무 많은 인수를 전달하면 파서는 그 오류를 보고해야 하지만, 당황하여 패닉 모드에 빠지는 대신 추가 인수를 계속 파싱할 수 있고 또 그래야 합니다.

하지만 우리의 경우, 구문 오류가 심각하여 패닉하고 동기화하기를 원합니다. 토큰을 버리는 것은 꽤 쉽지만, 파서 자체의 상태를 어떻게 동기화할까요?

6 . 3 . 3재귀 하향 파서 동기화하기

재귀 하향 파싱에서는 파서의 상태(즉, 어떤 규칙을 인식하는 중인지)가 필드에 명시적으로 저장되지 않습니다. 대신, 우리는 자바 자체의 호출 스택을 사용하여 파서가 무엇을 하고 있는지 추적합니다. 파싱 중인 각 규칙은 스택의 호출 프레임입니다. 그 상태를 재설정하기 위해서는 해당 호출 프레임들을 비워야 합니다.

자바에서 이를 수행하는 자연스러운 방법은 예외(exception)입니다. 동기화하고 싶을 때, 우리는 그 ParseError 객체를 *던집니다(throw)*. 우리가 동기화하려는 문법 규칙에 대한 메서드의 더 높은 곳에서 이를 잡을(catch) 것입니다. 우리는 문장 경계에서 동기화하므로, 거기서 예외를 잡을 것입니다. 예외가 잡힌 후, 파서는 올바른 상태가 됩니다. 남은 것은 토큰을 동기화하는 것입니다.

우리는 다음 문장의 시작 부분에 도달할 때까지 토큰을 버리고 싶습니다. 그 경계는 찾기 매우 쉽습니다. 이것이 우리가 그 경계를 선택한 주요 이유 중 하나입니다. 세미콜론 *뒤*에는, 우리는 아마도 문장이 끝났을 것입니다. 대부분의 문장은 `for`, `if`, `return`, `var` 등과 같은 키워드로 시작합니다. *다음* 토큰이 그 중 하나라면, 우리는 아마 문장을 시작하려 할 것입니다.

이 메서드는 그 논리를 캡슐화합니다.

  private void synchronize() {
    advance();

    while (!isAtEnd()) {
      if (previous().type == SEMICOLON) return;

      switch (peek().type) {
        case CLASS:
        case FUN:
        case VAR:
        case FOR:
        case IF:
        case WHILE:
        case PRINT:
        case RETURN:
          return;
      }

      advance();
    }
  }

이것은 문장 경계를 찾았다고 생각할 때까지 토큰을 버립니다. ParseError를 잡은 후, 이 메서드를 호출하면 바라건대 다시 동기화될 것입니다. 제대로 작동하면, 어차피 연쇄 오류를 유발했을 가능성이 있는 토큰들을 버렸고, 이제 다음 문장에서 시작하여 파일의 나머지 부분을 파싱할 수 있습니다.

아쉽게도, 아직 문장이 없으므로 이 메서드의 작동을 볼 수는 없습니다. 그것은 몇 장 뒤에 다루겠습니다. 지금은 오류가 발생하면 패닉하고 맨 위까지 되감은 다음 파싱을 중단할 것입니다. 어차피 단일 표현식만 파싱할 수 있으므로, 큰 손실은 아닙니다.

6 . 4파서 연결하기

이제 표현식 파싱은 거의 완료되었습니다. 오류 처리를 조금 더 추가해야 할 곳이 한 군데 더 있습니다. 파서가 각 문법 규칙에 대한 파싱 메서드를 거쳐 내려가다 보면, 결국 `primary()`에 도달합니다. 그곳의 어떤 경우도 일치하지 않는다면, 이는 표현식을 시작할 수 없는 토큰 위에 우리가 있다는 의미입니다. 그 오류도 처리해야 합니다.

    if (match(LEFT_PAREN)) {
      Expr expr = expression();
      consume(RIGHT_PAREN, "Expect ')' after expression.");
      return new Expr.Grouping(expr);
    }

    throw error(peek(), "Expect expression.");

  }

이것으로, 파서에 남은 것은 시작을 위한 초기 메서드를 정의하는 것뿐입니다. 그 메서드는 당연하게도 `parse()`라고 불립니다.

  Expr parse() {
    try {
      return expression();
    } catch (ParseError error) {
      return null;
    }
  }

이 메서드는 나중에 언어에 문장을 추가할 때 다시 다룰 것입니다. 지금은 단일 표현식을 파싱하고 반환합니다. 또한 패닉 모드를 종료하는 임시 코드도 있습니다. 구문 오류 복구는 파서의 역할이므로, ParseError 예외가 인터프리터의 나머지 부분으로 퍼지는 것을 원치 않습니다.

구문 오류가 발생하면 이 메서드는 `null`을 반환합니다. 그것은 괜찮습니다. 파서는 유효하지 않은 구문에서 충돌하거나 멈추지 않겠다고 약속하지만, 오류가 발견될 경우 *사용 가능한 구문 트리*를 반환하겠다고 약속하지는 않습니다. 파서가 오류를 보고하는 즉시 `hadError`가 설정되고, 이후 단계는 건너뛰어집니다.

마지막으로, 새로 만든 파서를 메인 Lox 클래스에 연결하고 시험해 볼 수 있습니다. 아직 인터프리터가 없으므로, 지금은 구문 트리로 파싱한 다음 지난 장의 AstPrinter 클래스를 사용하여 표시할 것입니다.

스캔된 토큰을 출력하는 이전 코드를 삭제하고 다음으로 대체하세요.

    List<Token> tokens = scanner.scanTokens();

    Parser parser = new Parser(tokens);
    Expr expression = parser.parse();

    // Stop if there was a syntax error.
    if (hadError) return;

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

  }

축하합니다, 임계점을 넘으셨습니다! 이것이 파서를 직접 작성하는 데 필요한 전부입니다. 나중에 할당, 문장(statement) 등과 같은 다른 것들로 문법을 확장할 것이지만, 그 어느 것도 여기서 다룬 이항 연산자보다 더 복잡하지는 않습니다.

인터프리터를 실행하고 몇 가지 표현식을 입력해 보세요. 우선순위와 결합 방향을 정확하게 처리하는 것을 확인했나요? 200줄 미만의 코드로 이 정도면 나쁘지 않습니다.

if (flags & FLAG_MASK == SOME_FLAG) { ... } // Wrong.
if ((flags & FLAG_MASK) == SOME_FLAG) { ... } // Right.