표현식 컴파일하기

우리 인생길 한가운데서
나는 올바른 길을 잃어버린 어두운 숲 속에 있음을 깨달았다.

단테 알리기에리, 신곡 지옥편

이 장은 한 가지, 두 가지가 아닌 무려 세 가지 이유로 매우 흥미로운 장입니다. 첫째, VM 실행 파이프라인의 마지막 부분을 제공합니다. 이 부분을 구현하면 사용자의 소스 코드를 스캔부터 실행까지 완전히 연결할 수 있습니다.

둘째, 우리는 실제로 진정한 컴파일러를 작성하게 됩니다. 소스 코드를 파싱하고 저수준 이진 명령어로 출력하는 컴파일러입니다. 물론 칩의 네이티브 명령어 집합이 아닌 바이트코드이지만, jlox보다 훨씬 더 하드웨어에 가깝습니다. 이제 우리는 진정한 언어 해커가 될 것입니다.

셋째이자 마지막으로, 제가 가장 좋아하는 알고리즘 중 하나인 Vaughan Pratt의 "하향식 연산자 우선순위 파싱(top-down operator precedence parsing)"을 보여드릴 수 있게 됩니다. 제가 아는 한 표현식을 파싱하는 가장 우아한 방법입니다. 전위 연산자, 후위 연산자, 중위 연산자, *혼합 연산자(mixfix)* 등 모든 종류의 연산자를 우아하게 처리합니다. 우선순위와 결합성을 전혀 문제없이 다룹니다. 정말 마음에 듭니다.

평소와 같이, 재미있는 부분을 시작하기 전에 몇 가지 준비 작업을 해야 합니다. 디저트를 먹기 전에 채소를 먹어야 하는 것과 같습니다. 먼저, 스캐너 테스트를 위해 작성했던 임시 코드를 더 유용한 것으로 교체합시다.

InterpretResult interpret(const char* source) {

  Chunk chunk;
  initChunk(&chunk);

  if (!compile(source, &chunk)) {
    freeChunk(&chunk);
    return INTERPRET_COMPILE_ERROR;
  }

  vm.chunk = &chunk;
  vm.ip = vm.chunk->code;

  InterpretResult result = run();

  freeChunk(&chunk);
  return result;

}

새로운 빈 청크를 생성하고 이를 컴파일러로 전달합니다. 컴파일러는 사용자 프로그램을 받아 청크를 바이트코드로 채울 것입니다. 적어도, 프로그램에 컴파일 오류가 없는 경우에 그렇게 할 것입니다. 만약 오류가 발생하면 compile()은 false를 반환하고, 우리는 사용할 수 없는 청크를 버립니다.

그렇지 않은 경우, 완성된 청크를 VM으로 보내 실행합니다. VM이 완료되면 청크를 해제하고 작업이 끝납니다. 보시다시피 compile()의 시그니처가 변경되었습니다.

#define clox_compiler_h

#include "vm.h"

bool compile(const char* source, Chunk* chunk);

#endif

컴파일러가 코드를 작성할 청크를 전달하고, compile()은 컴파일 성공 여부를 반환합니다. 구현 파일에서도 시그니처를 동일하게 변경합니다.

#include "scanner.h"

bool compile(const char* source, Chunk* chunk) {

  initScanner(source);

initScanner() 호출만 이 장에서 살아남는 유일한 줄입니다. 스캐너 테스트를 위해 작성했던 임시 코드를 제거하고 이 세 줄로 교체하세요.

  initScanner(source);

  advance();
  expression();
  consume(TOKEN_EOF, "Expect end of expression.");

}

advance() 호출은 스캐너의 "펌프를 시동"합니다. 이 기능이 곧 무엇을 하는지 볼 것입니다. 그런 다음 단일 표현식을 파싱합니다. 아직 구문(statement)을 다루지는 않을 것이므로, 현재 지원하는 문법의 유일한 부분입니다. 이 부분은 나중에 구문을 추가할 때 다시 다룰 것입니다. 표현식 컴파일 후에는 소스 코드의 끝에 도달해야 하므로, 종료 EOF 토큰을 확인합니다.

우리는 이 함수의 작동, 특히 작은 expression() 호출을 위해 이 장의 나머지 부분을 할애할 것입니다. 보통은 해당 함수 정의로 바로 들어가 위에서 아래로 구현을 진행할 것입니다.

하지만 이번 장은 다릅니다. 프랫의 파싱 기법은 모든 것을 머릿속에 넣고 나면 놀랍도록 간단하지만, 작은 조각으로 나누기가 약간 어렵습니다. 물론 재귀적이라는 것이 문제의 일부입니다. 하지만 거대한 데이터 테이블에도 의존합니다. 알고리즘을 구축하면서 이 테이블은 추가 열로 확장됩니다.

테이블을 확장할 때마다 40여 줄의 코드를 다시 작성하고 싶지는 않습니다. 그래서 우리는 파서의 핵심 부분으로 외부에서부터 접근하여, 핵심 부분에 도달하기 전에 주변의 모든 비트를 다룰 것입니다. 이 작업은 다른 장보다 약간 더 많은 인내와 정신적 여유 공간을 요구할 것이지만, 제가 할 수 있는 최선입니다.

17 . 1단일 패스 컴파일

컴파일러는 대략 두 가지 역할을 합니다. 먼저 사용자 소스 코드를 파싱하여 그 의미를 이해합니다. 그런 다음 그 지식을 활용하여 동일한 의미를 생성하는 저수준 명령어를 출력합니다. 많은 언어는 이 두 가지 역할을 구현에서 두 개의 별도 패스로 나눕니다. 파서는 jlox와 마찬가지로 AST를 생성하고, 코드 생성기가 AST를 순회하며 대상 코드를 출력합니다.

clox에서는 구식 접근 방식을 사용하여 이 두 패스를 하나로 병합합니다. 과거에는 컴퓨터에 전체 소스 파일의 AST를 저장할 만큼 충분한 메모리가 없었기 때문에 언어 해커들이 이렇게 했습니다. 우리는 C로 프로그래밍할 때 진정한 자산인 컴파일러를 더 간단하게 유지하기 위해 이 방식을 사용합니다.

우리가 만들 단일 패스 컴파일러는 모든 언어에 잘 작동하지는 않습니다. 컴파일러가 코드를 생성하는 동안 사용자 프로그램에 대한 제한된 시야(peephole view)만 가지기 때문에, 언어는 구문의 한 부분을 이해하는 데 많은 주변 컨텍스트가 필요하지 않도록 설계되어야 합니다. 다행히 작고 동적 타이핑을 사용하는 Lox는 이러한 요구 사항에 잘 맞습니다.

실용적인 측면에서 이것이 의미하는 바는, 우리의 "컴파일러" C 모듈이 토큰 소비, 예상 토큰 타입 일치 등 jlox에서 보았던 파싱 기능을 가지고 있다는 것입니다. 그리고 바이트코드 생성 및 대상 청크에 상수 추가와 같은 코드 생성 기능도 가지고 있습니다. (그리고 이 장과 이후 장들에서 "파싱"과 "컴파일"을 상호 교환적으로 사용할 것입니다.)

먼저 파싱 및 코드 생성 부분을 만들 것입니다. 그런 다음 프랫의 기술을 사용하여 Lox의 특정 문법을 파싱하고 올바른 바이트코드를 출력하는 중간 코드로 이들을 연결할 것입니다.

17 . 2토큰 파싱하기

먼저 컴파일러의 전반부입니다. 이 함수의 이름은 익숙하게 들릴 것입니다.

#include "scanner.h"

static void advance() {
  parser.previous = parser.current;

  for (;;) {
    parser.current = scanToken();
    if (parser.current.type != TOKEN_ERROR) break;

    errorAtCurrent(parser.current.start);
  }
}

jlox에서처럼 토큰 스트림을 한 단계씩 진행합니다. 스캐너에게 다음 토큰을 요청하고 나중에 사용하기 위해 저장합니다. 그렇게 하기 전에, 이전 current 토큰을 previous 필드에 저장합니다. 이는 토큰을 일치시킨 후 렉심에 접근하는 데 유용할 것입니다.

다음 토큰을 읽는 코드는 루프 안에 래핑되어 있습니다. clox의 스캐너는 어휘 오류를 보고하지 않는다는 것을 기억하세요. 대신, 특별한 *오류 토큰(error tokens)*을 생성하고 파서에게 보고하도록 맡깁니다. 우리는 여기서 그렇게 합니다.

오류가 아닌 토큰을 만나거나 끝에 도달할 때까지 토큰을 읽고 오류를 보고하는 루프를 계속 돌립니다. 그렇게 하면 파서의 나머지 부분은 유효한 토큰만 보게 됩니다. 현재 및 이전 토큰은 이 구조체에 저장됩니다.

#include "scanner.h"

typedef struct {
  Token current;
  Token previous;
} Parser;

Parser parser;

static void advance() {

다른 모듈에서 했던 것처럼, 이 구조체 타입의 단일 전역 변수를 가지고 있어 컴파일러의 함수 간에 상태를 전달할 필요가 없습니다.

17 . 2 . 1문법 오류 처리

스캐너가 오류 토큰을 넘겨주면, 우리는 사용자에게 실제로 알려야 합니다. 이는 다음을 사용하여 이루어집니다:

static void errorAtCurrent(const char* message) {
  errorAt(&parser.current, message);
}

오류가 발생한 위치를 사용자에게 알리기 위해 현재 토큰에서 위치 정보를 가져와 errorAt()으로 전달합니다. 더 자주, 우리는 방금 소비한 토큰 위치에서 오류를 보고할 것이므로, 이 다른 함수에 더 짧은 이름을 부여합니다:

static void error(const char* message) {
  errorAt(&parser.previous, message);
}

실제 작업은 여기서 일어납니다:

static void errorAt(Token* token, const char* message) {
  fprintf(stderr, "[line %d] Error", token->line);

  if (token->type == TOKEN_EOF) {
    fprintf(stderr, " at end");
  } else if (token->type == TOKEN_ERROR) {
    // Nothing.
  } else {
    fprintf(stderr, " at '%.*s'", token->length, token->start);
  }

  fprintf(stderr, ": %s\n", message);
  parser.hadError = true;
}

먼저 오류가 발생한 위치를 출력합니다. 렉심이 사람이 읽을 수 있는 형태이면 보여주려고 노력합니다. 그런 다음 오류 메시지 자체를 출력합니다. 그 후 hadError 플래그를 설정합니다. 이는 컴파일 중에 오류가 발생했는지 기록합니다. 이 필드는 파서 구조체에도 있습니다.

  Token previous;

  bool hadError;

} Parser;

앞서 compile()이 오류 발생 시 false를 반환해야 한다고 말했습니다. 이제 그렇게 만들 수 있습니다.

  consume(TOKEN_EOF, "Expect end of expression.");

  return !parser.hadError;

}

오류 처리를 위해 또 다른 플래그를 소개할 것입니다. 우리는 오류 연쇄(error cascades)를 피하고 싶습니다. 사용자가 코드에 실수를 하여 파서가 문법에서 어디에 있는지 혼동할 경우, 첫 번째 오류 이후에 의미 없는 오류 더미를 쏟아내지 않도록 하고 싶습니다.

jlox에서는 패닉 모드 오류 복구를 사용하여 이를 해결했습니다. 자바 인터프리터에서는 예외를 발생시켜 모든 파서 코드를 해제하고 토큰을 건너뛰고 다시 동기화할 수 있는 지점으로 돌아갔습니다. C에는 예외가 없습니다. 대신, 약간의 눈속임을 사용할 것입니다. 현재 패닉 모드인지 추적하기 위한 플래그를 추가합니다.

  bool hadError;

  bool panicMode;

} Parser;

오류가 발생하면 이 플래그를 설정합니다.

static void errorAt(Token* token, const char* message) {

  parser.panicMode = true;

  fprintf(stderr, "[line %d] Error", token->line);

그 후에는 오류가 전혀 발생하지 않은 것처럼 정상적으로 컴파일을 계속 진행합니다. 바이트코드는 절대 실행되지 않으므로 계속 진행해도 무해합니다. 요령은 패닉 모드 플래그가 설정되어 있는 동안에는 감지되는 다른 모든 오류를 단순히 억제하는 것입니다.

static void errorAt(Token* token, const char* message) {

  if (parser.panicMode) return;

  parser.panicMode = true;

파서가 엉망이 될 가능성이 높지만, 오류가 모두 무시되기 때문에 사용자는 알 수 없을 것입니다. 패닉 모드는 파서가 동기화 지점에 도달하면 종료됩니다. Lox의 경우 구문(statement) 경계를 선택했으므로, 나중에 컴파일러에 구문을 추가할 때 거기서 플래그를 해제할 것입니다.

이 새로운 필드들은 초기화되어야 합니다.

  initScanner(source);

  parser.hadError = false;
  parser.panicMode = false;

  advance();

그리고 오류를 표시하기 위해 표준 헤더가 필요합니다.

#include <stdio.h>

#include <stdlib.h>

#include "common.h"

마지막 파싱 함수가 하나 더 있습니다. jlox에서 보았던 또 다른 오래된 친구입니다.

static void consume(TokenType type, const char* message) {
  if (parser.current.type == type) {
    advance();
    return;
  }

  errorAtCurrent(message);
}

이 함수는 다음 토큰을 읽는다는 점에서 advance()와 유사합니다. 하지만 토큰이 예상되는 타입을 가지고 있는지 또한 검증합니다. 그렇지 않으면 오류를 보고합니다. 이 함수는 컴파일러의 대부분의 구문 오류의 기초가 됩니다.

이제 프런트엔드에 대한 설명은 충분합니다.

17 . 3바이트코드 생성하기

사용자 프로그램의 한 부분을 파싱하고 이해한 후, 다음 단계는 이를 일련의 바이트코드 명령어로 변환하는 것입니다. 가장 쉬운 단계부터 시작합니다: 청크에 단일 바이트를 추가하는 것입니다.

static void emitByte(uint8_t byte) {
  writeChunk(currentChunk(), byte, parser.previous.line);
}

이런 간단한 함수를 통해 위대한 것들이 흘러나올 것이라고 믿기 어려울 것입니다. 이 함수는 주어진 바이트를 작성하는데, 이는 opcode 또는 명령어의 피연산자일 수 있습니다. 이전 토큰의 라인 정보를 보내서 런타임 오류가 해당 라인과 연결되도록 합니다.

우리가 작성하는 청크는 compile()로 전달되지만, emitByte()까지 전달되어야 합니다. 이를 위해 이 중간 함수에 의존합니다.

Parser parser;

Chunk* compilingChunk;

static Chunk* currentChunk() {
  return compilingChunk;
}

static void errorAt(Token* token, const char* message) {

현재 청크 포인터는 다른 전역 상태와 마찬가지로 모듈 수준 변수에 저장됩니다. 나중에 사용자 정의 함수를 컴파일하기 시작하면 "현재 청크" 개념이 더 복잡해집니다. 많은 코드를 되돌아가서 변경하는 것을 피하기 위해, 이 논리를 currentChunk() 함수로 캡슐화합니다.

이 새로운 모듈 변수는 바이트코드를 작성하기 전에 초기화합니다.

bool compile(const char* source, Chunk* chunk) {
  initScanner(source);

  compilingChunk = chunk;

  parser.hadError = false;

그런 다음, 마지막에 청크 컴파일이 끝나면 작업을 마무리합니다.

  consume(TOKEN_EOF, "Expect end of expression.");

  endCompiler();

  return !parser.hadError;

이것은 다음을 호출합니다:

static void endCompiler() {
  emitReturn();
}

이 장에서는 VM이 표현식만 다룹니다. clox를 실행하면 단일 표현식을 파싱, 컴파일, 실행한 다음 결과를 출력합니다. 이 값을 출력하기 위해 임시로 OP_RETURN 명령어를 사용합니다. 그래서 컴파일러가 청크 끝에 이를 추가합니다.

static void emitReturn() {
  emitByte(OP_RETURN);
}

여기서 백엔드에 있는 김에 우리의 삶을 더 편하게 만듭시다.

static void emitBytes(uint8_t byte1, uint8_t byte2) {
  emitByte(byte1);
  emitByte(byte2);
}

시간이 지남에 따라 opcode 뒤에 1바이트 피연산자를 작성해야 하는 경우가 많아져서 이 편의 함수를 정의할 가치가 있습니다.

17 . 4전위 표현식 파싱하기

파싱 및 코드 생성 유틸리티 함수들을 모두 모았습니다. 빠진 부분은 이들을 연결하는 중간 코드입니다.

compile()에서 아직 구현해야 할 유일한 단계는 이 함수입니다.

static void expression() {
  // What goes here?
}

우리는 아직 Lox의 모든 종류의 표현식을 구현할 준비가 되지 않았습니다. 심지어 불리언도 없습니다. 이 장에서는 네 가지에 대해서만 다룰 것입니다.

• 숫자 리터럴: 123
• 그룹화를 위한 괄호: (123)
• 단항 부정: -123
• 산술의 네 가지 연산: +, -, *, /

각 표현식 종류를 컴파일하는 함수들을 살펴보면서, 이러한 함수들을 호출하는 테이블 기반 파서의 요구 사항도 함께 구성할 것입니다.

17 . 4 . 1토큰용 파서

지금은 단일 토큰으로만 구성된 Lox 표현식에 초점을 맞춰봅시다. 이 장에서는 숫자 리터럴만 해당하지만, 나중에 더 많아질 것입니다. 다음은 이를 컴파일하는 방법입니다:

각 토큰 타입을 다른 종류의 표현식에 매핑합니다. 각 표현식에 대해 적절한 바이트코드를 출력하는 함수를 정의합니다. 그런 다음 함수 포인터 배열을 만듭니다. 배열의 인덱스는 TokenType 열거형 값에 해당하며, 각 인덱스의 함수는 해당 토큰 타입의 표현식을 컴파일하는 코드입니다.

숫자 리터럴을 컴파일하기 위해 TOKEN_NUMBER 인덱스의 배열에 다음 함수에 대한 포인터를 저장합니다.

static void number() {
  double value = strtod(parser.previous.start, NULL);
  emitConstant(value);
}

숫자 리터럴에 해당하는 토큰이 이미 소비되어 previous에 저장되어 있다고 가정합니다. 해당 렉심을 가져와 C 표준 라이브러리를 사용하여 double 값으로 변환합니다. 그런 다음 다음 함수를 사용하여 해당 값을 로드하는 코드를 생성합니다.

static void emitConstant(Value value) {
  emitBytes(OP_CONSTANT, makeConstant(value));
}

먼저 값을 상수 테이블에 추가한 다음, 런타임에 스택에 푸시하는 OP_CONSTANT 명령어를 생성합니다. 상수 테이블에 항목을 삽입하기 위해 다음 함수를 사용합니다.

static uint8_t makeConstant(Value value) {
  int constant = addConstant(currentChunk(), value);
  if (constant > UINT8_MAX) {
    error("Too many constants in one chunk.");
    return 0;
  }

  return (uint8_t)constant;
}

대부분의 작업은 이전 장에서 정의했던 addConstant()에서 발생합니다. 이 함수는 주어진 값을 청크의 상수 테이블 끝에 추가하고 해당 인덱스를 반환합니다. 이 새로운 함수의 주된 역할은 너무 많은 상수가 생성되지 않도록 하는 것입니다. OP_CONSTANT 명령어는 인덱스 피연산자에 단일 바이트를 사용하므로, 하나의 청크에 최대 256개의 상수만 저장하고 로드할 수 있습니다.

기본적으로 이 모든 것이 필요합니다. TOKEN_NUMBER 토큰을 소비하고, 함수 포인터 배열에서 number()를 찾아 호출하는 적절한 코드가 있다면, 이제 숫자 리터럴을 바이트코드로 컴파일할 수 있습니다.

17 . 4 . 2그룹화를 위한 괄호

아직 상상 속에 있는 파싱 함수 포인터 배열은 모든 표현식이 단일 토큰으로만 구성되어 있다면 훌륭할 것입니다. 하지만 대부분의 표현식은 더 깁니다. 그러나 많은 표현식은 특정 토큰으로 *시작*합니다. 우리는 이것들을 *전위 표현식(prefix expressions)*이라고 부릅니다. 예를 들어, 표현식을 파싱하다가 현재 토큰이 (이면, 괄호로 묶인 그룹화 표현식을 보고 있다는 것을 알 수 있습니다.

함수 포인터 배열은 이러한 경우도 처리합니다. 표현식 타입에 대한 파싱 함수는 일반적인 재귀 하강 파서처럼 원하는 만큼 추가 토큰을 소비할 수 있습니다. 괄호가 작동하는 방식은 다음과 같습니다.

static void grouping() {
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after expression.");
}

다시 말하지만, 초기 (는 이미 소비되었다고 가정합니다. 괄호 안의 표현식을 컴파일하기 위해 재귀적으로 expression()을 호출한 다음, 끝에 닫는 )를 파싱합니다.

백엔드 관점에서 그룹화 표현식은 문자 그대로 아무것도 하지 않습니다. 유일한 기능은 구문적인 것입니다. 즉, 더 높은 우선순위가 예상되는 곳에 더 낮은 우선순위 표현식을 삽입할 수 있도록 합니다. 따라서 자체적으로 런타임 의미론이 없으며 어떤 바이트코드도 생성하지 않습니다. expression() 내부 호출이 괄호 안의 표현식에 대한 바이트코드 생성을 처리합니다.

17 . 4 . 3단항 부정

단항 마이너스 또한 전위 표현식이므로, 우리의 모델과 잘 작동합니다.

static void unary() {
  TokenType operatorType = parser.previous.type;

  // 피연산자 컴파일.
  expression();

  // 연산자 명령어 생성.
  switch (operatorType) {
    case TOKEN_MINUS: emitByte(OP_NEGATE); break;
    default: return; // 도달할 수 없음.
  }
}

선행 - 토큰은 이미 소비되었고 parser.previous에 있습니다. 우리는 어떤 단항 연산자를 처리하고 있는지 확인하기 위해 거기서 토큰 타입을 가져옵니다. 지금은 불필요하지만, 다음 장에서 ! 연산자를 컴파일하는 데 이 동일한 함수를 사용할 때 더 이해하기 쉬울 것입니다.

grouping()에서처럼, 피연산자를 컴파일하기 위해 expression()을 재귀적으로 호출합니다. 그 후, 부정을 수행하는 바이트코드를 생성합니다. -가 왼쪽에 나타나므로 피연산자의 바이트코드 *다음에* 부정 명령어를 작성하는 것이 다소 이상하게 보일 수 있지만, 실행 순서 측면에서 생각해보세요.

1. 먼저 피연산자를 평가하고 그 값을 스택에 남깁니다.

2. 그런 다음 그 값을 꺼내 부정하고 결과를 푸시합니다.

따라서 OP_NEGATE 명령어는 마지막에 생성되어야 합니다. 이것은 컴파일러의 역할 중 일부입니다. 즉, 소스 코드에 나타나는 순서대로 프로그램을 파싱하고, 실행되는 순서대로 재배열하는 것입니다.

하지만 이 코드에는 한 가지 문제가 있습니다. 호출하는 expression() 함수는 우선순위에 관계없이 피연산자에 대한 모든 표현식을 파싱할 것입니다. 이진 연산자 및 다른 구문을 추가하면 잘못된 동작을 초래할 수 있습니다. 다음을 고려해보세요.

-a.b + c;

여기서 -의 피연산자는 a.b 표현식이어야 하고, 전체 a.b + c가 아니어야 합니다. 그러나 unary()가 expression()을 호출하면, 후자는 +를 포함한 나머지 모든 코드를 기꺼이 처리할 것입니다. 이는 -를 +보다 낮은 우선순위로 잘못 처리할 것입니다.

단항 -의 피연산자를 파싱할 때, 우리는 특정 우선순위 레벨 이상인 표현식만 컴파일해야 합니다. jlox의 재귀 하강 파서에서는 이를 허용하려는 가장 낮은 우선순위 표현식에 대한 파싱 메서드(이 경우 call())를 호출하여 달성했습니다. 특정 표현식을 파싱하는 각 메서드는 또한 더 높은 우선순위의 표현식도 파싱하여, 우선순위 테이블의 나머지 부분을 포함했습니다.

clox의 number()나 unary()와 같은 파싱 함수는 다릅니다. 각 함수는 정확히 한 가지 타입의 표현식만 파싱합니다. 더 높은 우선순위 표현식 타입을 포함하도록 연쇄적으로 호출되지 않습니다. 우리는 다른 해결책이 필요하며, 그것은 다음과 같습니다.

static void parsePrecedence(Precedence precedence) {
  // What goes here?
}

이 함수는 일단 구현되면, 현재 토큰에서 시작하여 주어진 우선순위 레벨 이상의 모든 표현식을 파싱합니다. 이 함수의 본문을 작성하기 전에 다른 설정들을 거쳐야 하지만, 제가 계속 이야기했던 파싱 함수 포인터 테이블을 사용할 것이라는 것을 짐작할 수 있을 것입니다. 지금은 어떻게 작동하는지 너무 걱정하지 마세요. "precedence"를 매개변수로 받기 위해 숫자적으로 정의합니다.

} Parser;

typedef enum {
  PREC_NONE,
  PREC_ASSIGNMENT,  // =
  PREC_OR,          // or
  PREC_AND,         // and
  PREC_EQUALITY,    // == !=
  PREC_COMPARISON,  // < > <= >=
  PREC_TERM,        // + -
  PREC_FACTOR,      // * /
  PREC_UNARY,       // ! -
  PREC_CALL,        // . ()
  PREC_PRIMARY
} Precedence;

Parser parser;

이것들은 Lox의 모든 우선순위 레벨로, 가장 낮은 것부터 가장 높은 것 순서입니다. C는 열거형에 순차적으로 더 큰 숫자를 암묵적으로 부여하므로, 이는 PREC_CALL이 PREC_UNARY보다 수치적으로 더 크다는 것을 의미합니다. 예를 들어, 컴파일러가 다음과 같은 코드 덩어리에 있다면:

-a.b + c

parsePrecedence(PREC_ASSIGNMENT)를 호출하면, +가 할당보다 높은 우선순위를 가지므로 전체 표현식을 파싱합니다. 대신 parsePrecedence(PREC_UNARY)를 호출하면 -a.b를 컴파일하고 거기서 멈춥니다. 덧셈이 단항 연산자보다 낮은 우선순위를 가지므로 +를 통해 계속 진행하지 않습니다.

이 함수를 사용하여 expression()의 빠진 본문을 쉽게 채울 수 있습니다.

static void expression() {

  parsePrecedence(PREC_ASSIGNMENT);

}

가장 낮은 우선순위 레벨을 파싱하며, 이는 모든 높은 우선순위 표현식도 포함합니다. 이제 단항 표현식의 피연산자를 컴파일하기 위해, 이 새로운 함수를 호출하고 적절한 레벨로 제한합니다.

  // Compile the operand.

  parsePrecedence(PREC_UNARY);

  // Emit the operator instruction.

우리는 단항 연산자의 자체 PREC_UNARY 우선순위를 사용하여 !!doubleNegative와 같은 중첩된 단항 표현식을 허용합니다. 단항 연산자는 매우 높은 우선순위를 가지므로, 이진 연산자 같은 것들을 올바르게 제외합니다. 그건 그렇고 . . . 

17 . 5중위 표현식 파싱하기

이진 연산자는 이전 표현식들과 다릅니다. 왜냐하면 *중위(infix)* 연산자이기 때문입니다. 다른 표현식들의 경우, 첫 번째 토큰만으로 무엇을 파싱하는지 알 수 있습니다. 중위 표현식의 경우, 왼쪽 피연산자를 파싱하고 나서 중간에 연산자 토큰을 만나기 전까지는 이진 연산자의 중간에 있다는 것을 알 수 없습니다.

다음은 예시입니다:

1 + 2

지금까지 배운 것을 바탕으로 이를 컴파일하려고 시도하는 과정을 살펴봅시다.

1. expression()을 호출합니다. 그러면 parsePrecedence(PREC_ASSIGNMENT)를 호출합니다.

2. 이 함수(구현되면)는 선행 숫자 토큰을 보고 숫자 리터럴을 파싱하고 있음을 인식합니다. 제어권을 number()로 넘깁니다.

3. number()는 상수를 생성하고, OP_CONSTANT를 생성한 다음, parsePrecedence()로 돌아갑니다.

이제 어떻게 될까요? parsePrecedence() 호출은 전체 덧셈 표현식을 소비해야 하므로, 어떤 식으로든 계속 진행해야 합니다. 다행히 파서는 우리가 필요한 위치에 있습니다. 선행 숫자 표현식을 컴파일했으므로, 다음 토큰은 +입니다. 이것은 parsePrecedence()가 중위 표현식의 중간에 있음을 감지하고, 이미 컴파일한 표현식이 실제로는 그 연산자의 피연산자임을 깨닫는 데 필요한 정확한 토큰입니다.

따라서 이 가상의 함수 포인터 배열은 주어진 토큰으로 시작하는 표현식을 파싱하는 함수만 나열하는 것이 아닙니다. 대신, 함수 포인터의 *테이블*입니다. 한 열은 전위 파서 함수를 토큰 타입과 연결합니다. 두 번째 열은 중위 파서 함수를 토큰 타입과 연결합니다.

TOKEN_PLUS, TOKEN_MINUS, TOKEN_STAR, TOKEN_SLASH에 대한 중위 파서로 사용할 함수는 다음과 같습니다.

static void binary() {
  TokenType operatorType = parser.previous.type;
  ParseRule* rule = getRule(operatorType);
  parsePrecedence((Precedence)(rule->precedence + 1));

  switch (operatorType) {
    case TOKEN_PLUS:          emitByte(OP_ADD); break;
    case TOKEN_MINUS:         emitByte(OP_SUBTRACT); break;
    case TOKEN_STAR:          emitByte(OP_MULTIPLY); break;
    case TOKEN_SLASH:         emitByte(OP_DIVIDE); break;
    default: return; // 도달할 수 없음.
  }
}

전위 파서 함수가 호출될 때, 선행 토큰은 이미 소비되었습니다. 중위 파서 함수는 *사건의 한가운데(in medias res)*에 훨씬 더 깊이 들어갑니다. 전체 왼쪽 피연산자 표현식이 이미 컴파일되었고, 그 다음 중위 연산자가 소비되었습니다.

왼쪽 피연산자가 먼저 컴파일되는 사실은 잘 작동합니다. 이는 런타임에 해당 코드가 먼저 실행된다는 의미입니다. 실행될 때 생성되는 값은 스택에 쌓일 것입니다. 이는 중위 연산자가 필요로 하는 바로 그 위치입니다.

그런 다음 우리는 나머지 산술 연산자를 처리하기 위해 binary()로 옵니다. 이 함수는 unary()가 자체 후행 피연산자를 컴파일하는 방식과 매우 유사하게 오른쪽 피연산자를 컴파일합니다. 마지막으로 이진 연산을 수행하는 바이트코드 명령어를 생성합니다.

실행되면 VM은 왼쪽 및 오른쪽 피연산자 코드를 순서대로 실행하여 해당 값들을 스택에 남깁니다. 그런 다음 연산자에 대한 명령어를 실행합니다. 이는 두 값을 팝하고 연산을 계산한 다음 결과를 푸시합니다.

여기서 아마도 눈에 띄는 코드는 getRule() 줄일 것입니다. 오른쪽 피연산자를 파싱할 때 다시 우선순위를 고려해야 합니다. 다음과 같은 표현식을 생각해 보세요:

2 * 3 + 4

* 표현식의 오른쪽 피연산자를 파싱할 때 3 + 4가 아닌 3만 캡처해야 합니다. 왜냐하면 +는 *보다 낮은 우선순위를 가지기 때문입니다. 각 이진 연산자마다 별도의 함수를 정의할 수 있습니다. 각 함수는 parsePrecedence()를 호출하고 피연산자에 대한 올바른 우선순위 레벨을 전달할 것입니다.

하지만 그것은 좀 지루합니다. 각 이진 연산자의 오른쪽 피연산자 우선순위는 자체 우선순위보다 한 레벨 높습니다. 곧 다룰 getRule()을 사용하여 동적으로 이를 찾을 수 있습니다. 이를 사용하여 이 연산자의 레벨보다 한 레벨 높은 우선순위로 parsePrecedence()를 호출합니다.

이런 방식으로, 우리는 서로 다른 우선순위를 가짐에도 불구하고 모든 이진 연산자에 대해 단일 binary() 함수를 사용할 수 있습니다.

17 . 6프랫 파서

이제 컴파일러의 모든 구성 요소를 갖추었습니다. 각 문법 생성 규칙에 대한 함수가 있습니다: number(), grouping(), unary(), binary(). 아직 parsePrecedence()와 getRule()을 구현해야 합니다. 또한 토큰 타입이 주어졌을 때 다음을 찾을 수 있는 테이블이 필요하다는 것을 알고 있습니다.

• 해당 타입의 토큰으로 시작하는 전위 표현식을 컴파일하는 함수,

• 왼쪽 피연산자 다음에 해당 타입의 토큰이 오는 중위 표현식을 컴파일하는 함수,

• 해당 토큰을 연산자로 사용하는 중위 표현식의 우선순위.

이 세 가지 속성을 작은 구조체로 묶어 파서 테이블의 단일 행을 나타냅니다.

} Precedence;

typedef struct {
  ParseFn prefix;
  ParseFn infix;
  Precedence precedence;
} ParseRule;

Parser parser;

ParseFn 타입은 인수를 받지 않고 아무것도 반환하지 않는 함수 타입에 대한 간단한 typedef입니다.

} Precedence;

typedef void (*ParseFn)();

typedef struct {

전체 파서를 구동하는 테이블은 ParseRule의 배열입니다. 오랫동안 이에 대해 이야기했지만, 드디어 여러분이 보게 됩니다.

ParseRule rules[] = {
  [TOKEN_LEFT_PAREN]    = {grouping, NULL,   PREC_NONE},
  [TOKEN_RIGHT_PAREN]   = {NULL,     NULL,   PREC_NONE},
  [TOKEN_LEFT_BRACE]    = {NULL,     NULL,   PREC_NONE}, 
  [TOKEN_RIGHT_BRACE]   = {NULL,     NULL,   PREC_NONE},
  [TOKEN_COMMA]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_DOT]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_MINUS]         = {unary,    binary, PREC_TERM},
  [TOKEN_PLUS]          = {NULL,     binary, PREC_TERM},
  [TOKEN_SEMICOLON]     = {NULL,     NULL,   PREC_NONE},
  [TOKEN_SLASH]         = {NULL,     binary, PREC_FACTOR},
  [TOKEN_STAR]          = {NULL,     binary, PREC_FACTOR},
  [TOKEN_BANG]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_BANG_EQUAL]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_EQUAL]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_EQUAL_EQUAL]   = {NULL,     NULL,   PREC_NONE},
  [TOKEN_GREATER]       = {NULL,     NULL,   PREC_NONE},
  [TOKEN_GREATER_EQUAL] = {NULL,     NULL,   PREC_NONE},
  [TOKEN_LESS]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_LESS_EQUAL]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_IDENTIFIER]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_STRING]        = {NULL,     NULL,   PREC_NONE},
  [TOKEN_NUMBER]        = {number,   NULL,   PREC_NONE},
  [TOKEN_AND]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_CLASS]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_ELSE]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_FALSE]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_FOR]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_FUN]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_IF]            = {NULL,     NULL,   PREC_NONE},
  [TOKEN_NIL]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_OR]            = {NULL,     NULL,   PREC_NONE},
  [TOKEN_PRINT]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_RETURN]        = {NULL,     NULL,   PREC_NONE},
  [TOKEN_SUPER]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_THIS]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_TRUE]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_VAR]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_WHILE]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_ERROR]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_EOF]           = {NULL,     NULL,   PREC_NONE},
};

grouping과 unary가 각각의 토큰 타입에 대한 전위 파서 열에 어떻게 배치되는지 볼 수 있습니다. 다음 열에서는 binary가 네 가지 산술 중위 연산자에 연결되어 있습니다. 이 중위 연산자들은 마지막 열에 우선순위가 설정되어 있습니다.

이것들 외에, 테이블의 나머지는 NULL과 PREC_NONE으로 가득 차 있습니다. 이 빈 셀들의 대부분은 해당 토큰과 관련된 표현식이 없기 때문입니다. 예를 들어 else로 표현식을 시작할 수 없으며, }는 상당히 혼란스러운 중위 연산자가 될 것입니다.

하지만, 우리는 아직 전체 문법을 채우지 않았습니다. 이후 장에서 새로운 표현식 타입을 추가하면서, 이 슬롯들 중 일부에 함수들이 채워질 것입니다. 이 파싱 접근 방식의 장점 중 하나는 어떤 토큰이 문법에서 사용되고 어떤 토큰이 사용 가능한지 매우 쉽게 알 수 있다는 것입니다.

이제 테이블을 만들었으니, 드디어 이를 사용하는 코드를 작성할 준비가 되었습니다. 여기서 우리의 프랫 파서가 생명을 얻습니다. 가장 쉽게 정의할 수 있는 함수는 getRule()입니다.

static ParseRule* getRule(TokenType type) {
  return &rules[type];
}

이 함수는 단순히 주어진 인덱스에 있는 규칙을 반환합니다. binary()에서 현재 연산자의 우선순위를 조회하기 위해 호출됩니다. 이 함수는 C 코드의 선언 순환을 처리하기 위해 존재합니다. binary()는 규칙 테이블 *전에* 정의되어야 테이블이 이를 가리키는 포인터를 저장할 수 있습니다. 이는 binary()의 본문이 테이블에 직접 접근할 수 없다는 것을 의미합니다.

대신, 우리는 조회 작업을 함수로 감쌉니다. 이렇게 하면 binary() 정의 전에 getRule()을 선언하고, 그 다음 테이블 뒤에 getRule()을 *정의*할 수 있습니다. 문법이 재귀적이라는 사실을 처리하기 위해 몇 가지 다른 선행 선언이 필요하므로, 모두 미리 처리해 둡시다.

  emitReturn();
}

static void expression();
static ParseRule* getRule(TokenType type);
static void parsePrecedence(Precedence precedence);

static void binary() {

만약 clox를 직접 구현하고 있다면, 이 코드 조각들을 어디에 넣어야 할지 알려주는 작은 주석에 세심한 주의를 기울이세요. 하지만 걱정 마세요. 잘못 넣으면 C 컴파일러가 기꺼이 알려줄 것입니다.

17 . 6 . 1우선순위를 이용한 파싱

이제 재미있는 부분입니다. 우리가 정의한 모든 파싱 함수를 조율하는 마에스트로는 parsePrecedence()입니다. 먼저 전위 표현식 파싱부터 시작해봅시다.

static void parsePrecedence(Precedence precedence) {

  advance();
  ParseFn prefixRule = getRule(parser.previous.type)->prefix;
  if (prefixRule == NULL) {
    error("Expect expression.");
    return;
  }

  prefixRule();

}

다음 토큰을 읽고 해당하는 ParseRule을 찾습니다. 만약 전위 파서가 없다면, 그 토큰은 구문 오류일 것입니다. 오류를 보고하고 호출자에게 돌아갑니다.

그렇지 않으면, 해당 전위 파서 함수를 호출하여 제 역할을 하게 합니다. 전위 파서는 필요한 다른 토큰을 소비하며 나머지 전위 표현식을 컴파일하고 이곳으로 돌아옵니다. 우선순위가 작용하는 중위 표현식에서부터 흥미로워집니다. 구현은 놀랍도록 간단합니다.

  prefixRule();

  while (precedence <= getRule(parser.current.type)->precedence) {
    advance();
    ParseFn infixRule = getRule(parser.previous.type)->infix;
    infixRule();
  }

}

이게 다입니다. 정말로요. 전체 함수는 이렇게 작동합니다: parsePrecedence() 시작 시, 현재 토큰에 대한 전위 파서를 찾습니다. 첫 번째 토큰은 정의상 항상 어떤 종류의 전위 표현식에 속합니다. 하나 이상의 중위 표현식 안에 피연산자로 중첩될 수도 있지만, 코드를 왼쪽에서 오른쪽으로 읽을 때 처음 만나는 토큰은 항상 전위 표현식에 속합니다.

이를 파싱한 후(이는 더 많은 토큰을 소비할 수 있음), 전위 표현식은 완료됩니다. 이제 다음 토큰에 대한 중위 파서를 찾습니다. 만약 중위 파서를 찾았다면, 우리가 이미 컴파일한 전위 표현식이 그 연산자의 피연산자일 수 있다는 의미입니다. 하지만 parsePrecedence() 호출의 precedence가 해당 중위 연산자를 허용할 만큼 충분히 낮을 때만 그렇습니다.

다음 토큰의 우선순위가 너무 낮거나, 아예 중위 연산자가 아니라면, 작업은 완료됩니다. 우리는 가능한 한 많은 표현식을 파싱한 것입니다. 그렇지 않으면 연산자를 소비하고 찾은 중위 파서에게 제어권을 넘깁니다. 중위 파서는 필요한 다른 토큰(보통 오른쪽 피연산자)을 소비하고 parsePrecedence()로 돌아옵니다. 그런 다음 다시 루프를 돌며 *다음* 토큰도 전체 선행 표현식을 피연산자로 취할 수 있는 유효한 중위 연산자인지 확인합니다. 중위 연산자와 그 피연산자를 처리하면서 계속 반복하다가, 중위 연산자가 아니거나 우선순위가 너무 낮은 토큰을 만나면 멈춥니다.

설명이 장황하지만, Vaughan Pratt와 진정으로 하나 되어 알고리즘을 완전히 이해하고 싶다면, 디버거에서 파서가 몇 가지 표현식을 처리하는 과정을 단계별로 살펴보세요. 어쩌면 그림이 도움이 될 수도 있습니다. 함수는 소수에 불과하지만, 놀랍도록 복잡하게 얽혀 있습니다:

나중에 할당을 처리하기 위해 이 장의 코드를 수정해야 할 것입니다. 하지만, 그 외에는 우리가 작성한 코드가 이 책의 나머지 부분에서 필요한 모든 표현식 컴파일 요구 사항을 충족합니다. 새로운 종류의 표현식을 추가할 때 테이블에 추가 파싱 함수를 추가할 것이지만, parsePrecedence()는 완성되었습니다.

17 . 7청크 덤프하기

컴파일러의 핵심부에 있는 동안, 우리는 몇 가지 계측 도구를 설치해야 합니다. 생성된 바이트코드를 디버그하는 데 도움이 되도록, 컴파일러가 완료된 후 청크를 덤프하는 기능을 추가할 것입니다. 이전에 수동으로 청크를 작성했을 때 임시 로그가 있었지만, 이제는 우리가 원할 때마다 활성화할 수 있도록 실제 코드를 넣을 것입니다.

이것은 최종 사용자용이 아니므로, 플래그 뒤에 숨겨 둡니다.

#include <stdint.h>

#define DEBUG_PRINT_CODE

#define DEBUG_TRACE_EXECUTION

이 플래그가 정의되면, 우리는 기존 "debug" 모듈을 사용하여 청크의 바이트코드를 출력합니다.

  emitReturn();

#ifdef DEBUG_PRINT_CODE
  if (!parser.hadError) {
    disassembleChunk(currentChunk(), "code");
  }
#endif

}

코드가 오류가 없을 때만 이 작업을 수행합니다. 구문 오류 후에도 컴파일러는 계속 진행하지만, 다소 이상한 상태가 되어 깨진 코드를 생성할 수 있습니다. 이는 실행되지 않으므로 무해하지만, 우리가 이를 읽으려고 하면 혼란만 초래할 것입니다.

마지막으로, disassembleChunk()에 접근하려면 해당 헤더를 포함해야 합니다.

#include "scanner.h"

#ifdef DEBUG_PRINT_CODE
#include "debug.h"
#endif

typedef struct {

해냈습니다! 이것이 우리 VM의 컴파일 및 실행 파이프라인에 설치할 마지막 주요 섹션이었습니다. 우리 인터프리터는 겉보기에는 별것 아닌 것 같지만, 내부적으로는 스캔, 파싱, 바이트코드로 컴파일, 그리고 실행을 모두 수행하고 있습니다.

VM을 실행하고 표현식을 입력해 보세요. 모든 것을 올바르게 했다면, 결과가 계산되어 출력될 것입니다. 이제 우리는 매우 과도하게 설계된 산술 계산기를 가지게 되었습니다. 다가오는 장들에서 추가할 언어 기능이 많지만, 기초는 마련되었습니다.