요구 시 스캐닝

문학은 단 26개의 음성 기호, 10개의 아라비아 숫자, 그리고 대략 8개의 구두점으로 이루어진 수평선 상의 특이한 배열이다.

커트 보니것, 하느님과 악수하듯이: 글쓰기에 대한 대화

두 번째 인터프리터인 clox는 스캐너, 컴파일러, 가상 머신의 세 가지 단계를 거칩니다. 각 단계 쌍은 데이터 구조로 연결됩니다. 토큰은 스캐너에서 컴파일러로, 바이트코드 덩어리는 컴파일러에서 VM으로 흐릅니다. 우리는 청크와 VM으로 구현을 거의 끝부분부터 시작했습니다. 이제 처음으로 돌아가 토큰을 생성하는 스캐너를 구축할 것입니다. 다음 장에서는 바이트코드 컴파일러를 사용하여 이 두 끝을 연결할 것입니다.

고백하건대, 이 책에서 가장 흥미진진한 장은 아닐 것입니다. 동일한 언어를 두 번 구현하다 보니 필연적으로 중복되는 부분이 생기기 마련입니다. 하지만 jlox의 스캐너와 비교하여 몇 가지 흥미로운 차이점을 몰래 추가했습니다. 계속 읽어보시면 어떤 차이점인지 알 수 있을 겁니다.

16 . 1인터프리터 가동시키기

이제 프론트엔드를 구축하고 있으니, clox를 실제 인터프리터처럼 실행할 수 있습니다. 더 이상 수동으로 작성한 바이트코드 청크는 없습니다. REPL과 스크립트 로딩을 구현할 때입니다. main() 함수에 있는 대부분의 코드를 제거하고 다음으로 대체합니다.

int main(int argc, const char* argv[]) {
  initVM();

  if (argc == 1) {
    repl();
  } else if (argc == 2) {
    runFile(argv[1]);
  } else {
    fprintf(stderr, "Usage: clox [path]\n");
    exit(64);
  }

  freeVM();

  return 0;
}

실행 파일에 인수를 전달하지 않으면 REPL로 이동합니다. 단일 명령줄 인수는 실행할 스크립트의 경로로 해석됩니다.

몇 가지 시스템 헤더가 필요하므로, 미리 추가해두겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "common.h"

다음으로, REPL을 활성화하고 REPL 기능을 추가하겠습니다.

#include "vm.h"

static void repl() {
  char line[1024];
  for (;;) {
    printf("> ");

    if (!fgets(line, sizeof(line), stdin)) {
      printf("\n");
      break;
    }

    interpret(line);
  }
}

좋은 품질의 REPL은 여러 줄에 걸친 입력을 우아하게 처리하고, 하드코딩된 줄 길이 제한을 두지 않습니다. 여기 있는 REPL은 조금 더, 흠, 절제되어 있지만, 우리의 목적에는 충분합니다.

실제 작업은 interpret()에서 일어납니다. 곧 그 부분에 대해 다룰 것이지만, 먼저 스크립트 로딩부터 처리하겠습니다.

static void runFile(const char* path) {
  char* source = readFile(path);
  InterpretResult result = interpret(source);
  free(source); 

  if (result == INTERPRET_COMPILE_ERROR) exit(65);
  if (result == INTERPRET_RUNTIME_ERROR) exit(70);
}

파일을 읽어 Lox 소스 코드로 이루어진 문자열을 실행합니다. 그리고 그 결과에 따라 적절하게 종료 코드를 설정합니다. 우리는 세심한 도구 개발자이고 그런 작은 세부 사항까지 신경 쓰기 때문입니다.

또한, readFile()이 소스 코드 문자열을 동적으로 할당하고 호출자에게 소유권을 넘기기 때문에 해당 문자열을 해제해야 합니다. 그 함수는 다음과 같습니다.

static char* readFile(const char* path) {
  FILE* file = fopen(path, "rb");

  fseek(file, 0L, SEEK_END);
  size_t fileSize = ftell(file);
  rewind(file);

  char* buffer = (char*)malloc(fileSize + 1);
  size_t bytesRead = fread(buffer, sizeof(char), fileSize, file);
  buffer[bytesRead] = '\0';

  fclose(file);
  return buffer;
}

다른 많은 C 코드처럼, 이 코드는 예상보다 더 많은 노력이 필요합니다. 특히 운영 체제를 위해 명시적으로 설계된 언어치고는 더욱 그렇습니다. 어려운 부분은 파일 전체를 읽을 만큼 충분히 큰 문자열을 할당하고 싶지만, 파일을 읽기 전까지는 파일 크기를 알 수 없다는 점입니다.

여기 있는 코드는 이 문제를 해결하는 고전적인 방법입니다. 파일을 열고, 읽기 전에 fseek()를 사용하여 파일의 맨 끝으로 이동합니다. 그런 다음 ftell()을 호출하여 파일 시작점으로부터 몇 바이트 떨어져 있는지 확인합니다. 파일 끝으로 이동했으므로, 이 값이 파일 크기입니다. 시작점으로 되감고, 해당 크기의 문자열을 할당한 다음, 파일 전체를 한 번에 읽습니다.

자, 이제 끝난 걸까요? 아닙니다. C 표준 라이브러리의 대부분의 호출과 마찬가지로, 이 함수 호출들도 실패할 수 있습니다. 만약 자바였다면, 실패는 예외로 던져지고 스택이 자동으로 해제되므로 굳이 처리할 필요가 없었을 것입니다. 하지만 C에서는 이를 확인하지 않으면 조용히 무시됩니다.

이 책이 좋은 C 프로그래밍 관행에 대한 책은 아니지만, 나쁜 스타일을 조장하고 싶지는 않으므로, 오류를 처리해 보겠습니다. 채소를 먹거나 치실을 사용하는 것처럼 우리에게 좋은 일입니다.

다행히도 실패가 발생하더라도 특별히 영리한 조치를 취할 필요는 없습니다. 사용자 스크립트를 올바르게 읽을 수 없다면, 우리가 할 수 있는 일은 사용자에게 알리고 인터프리터를 정상적으로 종료하는 것뿐입니다. 우선, 파일을 여는 데 실패할 수 있습니다.

  FILE* file = fopen(path, "rb");

  if (file == NULL) {
    fprintf(stderr, "Could not open file \"%s\".\n", path);
    exit(74);
  }

  fseek(file, 0L, SEEK_END);

이런 일은 파일이 존재하지 않거나 사용자에게 접근 권한이 없을 때 발생할 수 있습니다. 꽤 흔한 일입니다—사람들은 항상 경로를 잘못 입력하곤 합니다.

이 실패는 훨씬 드뭅니다.

  char* buffer = (char*)malloc(fileSize + 1);

  if (buffer == NULL) {
    fprintf(stderr, "Not enough memory to read \"%s\".\n", path);
    exit(74);
  }

  size_t bytesRead = fread(buffer, sizeof(char), fileSize, file);

Lox 스크립트를 읽을 메모리조차 할당할 수 없다면, 사용자에게는 아마 더 큰 문제가 있을 테지만, 최소한 그들에게 알려주는 것이 우리의 최선일 것입니다.

마지막으로, 읽기 작업 자체가 실패할 수 있습니다.

  size_t bytesRead = fread(buffer, sizeof(char), fileSize, file);

  if (bytesRead < fileSize) {
    fprintf(stderr, "Could not read file \"%s\".\n", path);
    exit(74);
  }

  buffer[bytesRead] = '\0';

이 또한 가능성이 낮습니다. 사실, fseek(), ftell(), rewind() 호출들도 이론적으로 실패할 수 있지만, 너무 깊이 파고들지는 말자고요.

16 . 1 . 1컴파일 파이프라인 열기

이제 Lox 소스 코드 문자열을 확보했으니, 이를 스캔하고 컴파일하며 실행하는 파이프라인을 설정할 준비가 되었습니다. 이 파이프라인은 interpret() 함수에 의해 구동됩니다. 지금 이 함수는 우리의 오래된 하드코딩된 테스트 청크를 실행하고 있습니다. 이를 최종 모습에 가깝게 변경해 봅시다.

void freeVM();

InterpretResult interpret(const char* source);

void push(Value value);

이전에는 Chunk를 전달했지만, 이제는 소스 코드 문자열을 전달합니다. 새로운 구현은 다음과 같습니다.

InterpretResult interpret(const char* source) {
  compile(source);
  return INTERPRET_OK;

}

이 장에서는 실제 컴파일러를 아직 만들지 않겠지만, 그 구조를 잡아나갈 수 있습니다. 컴파일러는 새로운 모듈에 존재합니다.

#include "common.h"

#include "compiler.h"

#include "debug.h"

현재로서는 그 안에 있는 한 함수가 다음과 같이 선언됩니다.

#ifndef clox_compiler_h
#define clox_compiler_h

void compile(const char* source);

#endif

함수 시그니처는 변경될 것이지만, 일단 시작하는 데는 문제가 없습니다.

컴파일의 첫 번째 단계는 스캐닝입니다—이 장에서 다루는 내용이죠—따라서 현재 컴파일러는 스캐닝 설정을 하는 것만 합니다.

#include <stdio.h>

#include "common.h"
#include "compiler.h"
#include "scanner.h"

void compile(const char* source) {
  initScanner(source);
}

이 또한 이후 장에서 자연스럽게 확장될 것입니다.

16 . 1 . 2스캐너 스캔하기

유용한 코드를 작성하기 전에 세워야 할 발판이 아직 조금 더 남아있습니다. 먼저, 새로운 헤더 파일입니다.

#ifndef clox_scanner_h
#define clox_scanner_h

void initScanner(const char* source);

#endif

그리고 그에 상응하는 구현입니다.

#include <stdio.h>
#include <string.h>

#include "common.h"
#include "scanner.h"

typedef struct {
  const char* start;
  const char* current;
  int line;
} Scanner;

Scanner scanner;

스캐너가 사용자 소스 코드를 처리하면서, 얼마나 진행했는지 추적합니다. VM에서 했던 것처럼, 이 상태를 구조체로 래핑하고 해당 타입의 단일 최상위 모듈 변수를 생성하여 여러 함수에 걸쳐 전달할 필요가 없도록 합니다.

놀랍게도 필드가 거의 없습니다. start 포인터는 현재 스캔 중인 렉심의 시작을 표시하고, current는 현재 살펴보고 있는 문자를 가리킵니다.

오류 보고를 위해 현재 렉심이 몇 번째 줄에 있는지 추적하는 line 필드가 있습니다. 그게 다입니다! 심지어 소스 코드 문자열의 시작 부분에 대한 포인터도 유지하지 않습니다. 스캐너는 코드를 한 번 쭉 훑고 나면 작업이 완료됩니다.

일부 상태가 있으므로 초기화해야 합니다.

void initScanner(const char* source) {
  scanner.start = source;
  scanner.current = source;
  scanner.line = 1;
}

우리는 첫 번째 줄의 첫 번째 문자에서 시작합니다. 마치 출발선에 웅크린 주자처럼요.

16 . 2한 번에 하나의 토큰

jlox에서는 시작 신호가 울리면 스캐너가 빠르게 전체 프로그램을 스캔하고 토큰 목록을 반환했습니다. 하지만 clox에서는 이 방식이 문제가 될 수 있습니다. 토큰을 저장할 수 있는 확장 가능한 배열이나 리스트가 필요할 것이고, 토큰 할당 및 해제와 컬렉션 자체를 관리해야 합니다. 이는 많은 코드와 많은 메모리 오버헤드를 야기합니다.

어떤 시점에서든 컴파일러는 단지 한두 개의 토큰만 필요로 합니다—우리 문법은 한 개의 토큰 미리 보기가 필요하다는 것을 기억하세요—따라서 모든 토큰을 동시에 유지할 필요가 없습니다. 대신, 가장 간단한 해결책은 컴파일러가 토큰을 필요로 할 때까지 스캔하지 않는 것입니다. 스캐너가 토큰을 제공할 때, 값으로 토큰을 반환합니다. 동적으로 아무것도 할당할 필요가 없으며—C 스택에서 토큰을 전달하기만 하면 됩니다.

아쉽게도, 아직 스캐너에게 토큰을 요청할 수 있는 컴파일러가 없으므로, 스캐너는 아무것도 하지 않고 가만히 있을 것입니다. 스캐너를 작동시키기 위해 임시 코드를 작성하여 구동해 보겠습니다.

  initScanner(source);

  int line = -1;
  for (;;) {
    Token token = scanToken();
    if (token.line != line) {
      printf("%4d ", token.line);
      line = token.line;
    } else {
      printf("   | ");
    }
    printf("%2d '%.*s'\n", token.type, token.length, token.start); 

    if (token.type == TOKEN_EOF) break;
  }

}

이것은 무한 루프를 돌게 됩니다. 루프가 한 번 돌 때마다 토큰 하나를 스캔하고 출력합니다. 특별한 "파일 끝" 토큰이나 오류에 도달하면 멈춥니다. 예를 들어, 이 프로그램을 인터프리터로 실행하면 다음과 같이 출력됩니다.

print 1 + 2;

다음과 같이 출력할 것입니다.

   1 31 'print'
   | 21 '1'
   |  7 '+'
   | 21 '2'
   |  8 ';'
   2 39 ''

첫 번째 열은 줄 번호이고, 두 번째 열은 토큰 타입의 숫자 값이며, 마지막으로 렉심입니다. 줄 2의 마지막 빈 렉심은 EOF 토큰입니다.

이 장의 남은 목표는 이 핵심 함수를 구현하여 해당 코드 덩어리가 작동하도록 만드는 것입니다.

void initScanner(const char* source);

Token scanToken();

#endif

각 호출은 소스 코드에서 다음 토큰을 스캔하고 반환합니다. 토큰은 다음과 같이 생겼습니다.

#define clox_scanner_h

typedef struct {
  TokenType type;
  const char* start;
  int length;
  int line;
} Token;

void initScanner(const char* source);

jlox의 Token 클래스와 매우 유사합니다. 숫자, 식별자, + 연산자 등 어떤 종류의 토큰인지 식별하는 열거형이 있습니다. 이 열거형은 jlox의 것과 거의 동일하므로, 전체를 그냥 작성해 보겠습니다.

#ifndef clox_scanner_h
#define clox_scanner_h

typedef enum {
  // 한 글자 토큰.
  TOKEN_LEFT_PAREN, TOKEN_RIGHT_PAREN,
  TOKEN_LEFT_BRACE, TOKEN_RIGHT_BRACE,
  TOKEN_COMMA, TOKEN_DOT, TOKEN_MINUS, TOKEN_PLUS,
  TOKEN_SEMICOLON, TOKEN_SLASH, TOKEN_STAR,
  // 한두 글자 토큰.
  TOKEN_BANG, TOKEN_BANG_EQUAL,
  TOKEN_EQUAL, TOKEN_EQUAL_EQUAL,
  TOKEN_GREATER, TOKEN_GREATER_EQUAL,
  TOKEN_LESS, TOKEN_LESS_EQUAL,
  // 리터럴.
  TOKEN_IDENTIFIER, TOKEN_STRING, TOKEN_NUMBER,
  // 키워드.
  TOKEN_AND, TOKEN_CLASS, TOKEN_ELSE, TOKEN_FALSE,
  TOKEN_FOR, TOKEN_FUN, TOKEN_IF, TOKEN_NIL, TOKEN_OR,
  TOKEN_PRINT, TOKEN_RETURN, TOKEN_SUPER, TOKEN_THIS,
  TOKEN_TRUE, TOKEN_VAR, TOKEN_WHILE,

  TOKEN_ERROR, TOKEN_EOF
} TokenType;

typedef struct {

모든 이름에 TOKEN_ 접두사를 붙인 것 외에는 (C는 열거형 이름을 최상위 네임스페이스에 던져 넣기 때문에) 유일한 차이점은 추가된 TOKEN_ERROR 타입입니다. 이건 무엇을 의미할까요?

스캐닝 중 탐지되는 오류는 두 가지뿐입니다: 종료되지 않은 문자열과 인식할 수 없는 문자입니다. jlox에서는 스캐너가 직접 이를 보고했습니다. clox에서는 스캐너가 해당 오류에 대해 가상의 "오류" 토큰을 생성하고 이를 컴파일러에게 전달합니다. 이런 식으로 컴파일러는 오류가 발생했음을 알고 보고하기 전에 오류 복구를 시작할 수 있습니다.

clox의 Token 타입에서 새로운 부분은 렉심을 표현하는 방식입니다. jlox에서는 각 Token이 렉심을 별개의 작은 자바 문자열로 저장했습니다. clox에서도 그렇게 한다면, 그 문자열들의 메모리를 어떻게 관리해야 할지 알아내야 했을 겁니다. 토큰을 값으로 전달하기 때문에—여러 토큰이 동일한 렉심 문자열을 가리킬 수 있어—이는 특히 어렵습니다. 소유권이 복잡해집니다.

대신, 우리는 원본 소스 문자열을 문자 저장소로 사용합니다. 렉심은 첫 문자에 대한 포인터와 포함된 문자 수로 표현합니다. 이는 렉심을 위한 메모리 관리에 대해 전혀 걱정할 필요가 없으며 토큰을 자유롭게 복사할 수 있다는 의미입니다. 메인 소스 코드 문자열이 모든 토큰보다 오래 살아있는 한 모든 것이 잘 작동합니다.

16 . 2 . 1토큰 스캐닝

이제 토큰을 스캔할 준비가 되었습니다. 다음부터 시작하여 완전한 구현을 향해 나아가겠습니다.

Token scanToken() {
  scanner.start = scanner.current;

  if (isAtEnd()) return makeToken(TOKEN_EOF);

  return errorToken("Unexpected character.");
}

이 함수에 대한 각 호출이 완전한 토큰 하나를 스캔하므로, 함수에 진입할 때 새로운 토큰의 시작점에 있음을 압니다. 따라서 scanner.start를 현재 문자를 가리키도록 설정하여 스캔할 렉심이 어디서 시작하는지 기억합니다.

그런 다음 소스 코드의 끝에 도달했는지 확인합니다. 만약 그렇다면, EOF 토큰을 반환하고 멈춥니다. 이것은 컴파일러에게 더 이상 토큰을 요청하지 말라고 알리는 파수꾼 값입니다.

만약 끝에 도달하지 않았다면, 다음 토큰을 스캔하기 위해  . . . 뭔가를 합니다 . . . . 하지만 그 코드는 아직 작성하지 않았습니다. 곧 다룰 것입니다. 만약 그 코드가 토큰을 성공적으로 스캔하고 반환하지 못한다면, 우리는 함수 끝에 도달하게 됩니다. 이는 스캐너가 인식할 수 없는 문자에 있다는 의미이므로, 해당 문자에 대한 오류 토큰을 반환합니다.

이 함수는 몇 가지 도우미 함수에 의존하는데, 대부분 jlox에서 익숙할 것입니다. 첫 번째는 이겁니다.

static bool isAtEnd() {
  return *scanner.current == '\0';
}

소스 문자열은 좋은 널 종료 C 문자열이어야 합니다. 현재 문자가 널 바이트라면, 끝에 도달한 것입니다.

토큰을 생성하기 위해, 다음 생성자 같은 함수를 사용합니다.

static Token makeToken(TokenType type) {
  Token token;
  token.type = type;
  token.start = scanner.start;
  token.length = (int)(scanner.current - scanner.start);
  token.line = scanner.line;
  return token;
}

스캐너의 start와 current 포인터를 사용하여 토큰의 렉심을 캡처합니다. 몇 가지 다른 명확한 필드를 설정한 다음 토큰을 반환합니다. 오류 토큰을 반환하는 자매 함수도 있습니다.

static Token errorToken(const char* message) {
  Token token;
  token.type = TOKEN_ERROR;
  token.start = message;
  token.length = (int)strlen(message);
  token.line = scanner.line;
  return token;
}

유일한 차이점은 "렉심"이 사용자 소스 코드를 가리키는 대신 오류 메시지 문자열을 가리킨다는 것입니다. 다시 말하지만, 컴파일러가 이를 읽을 만큼 오류 메시지가 충분히 오래 유지되도록 해야 합니다. 실제로는 이 함수를 C 문자열 리터럴과 함께 호출하는 경우가 대부분입니다. 이들은 상수이며 영구적이므로 문제가 없습니다.

지금 우리가 가진 것은 기본적으로 비어 있는 어휘 문법을 가진 언어를 위한 작동하는 스캐너입니다. 문법에 프로덕션이 없으므로 모든 문자가 오류입니다. 이런 언어는 프로그래밍하기에 재미없으니, 이제 규칙을 채워 넣읍시다.

16 . 3Lox를 위한 어휘 문법

가장 간단한 토큰은 단일 문자 토큰입니다. 다음과 같이 인식합니다.

  if (isAtEnd()) return makeToken(TOKEN_EOF);

  char c = advance();

  switch (c) {
    case '(': return makeToken(TOKEN_LEFT_PAREN);
    case ')': return makeToken(TOKEN_RIGHT_PAREN);
    case '{': return makeToken(TOKEN_LEFT_BRACE);
    case '}': return makeToken(TOKEN_RIGHT_BRACE);
    case ';': return makeToken(TOKEN_SEMICOLON);
    case ',': return makeToken(TOKEN_COMMA);
    case '.': return makeToken(TOKEN_DOT);
    case '-': return makeToken(TOKEN_MINUS);
    case '+': return makeToken(TOKEN_PLUS);
    case '/': return makeToken(TOKEN_SLASH);
    case '*': return makeToken(TOKEN_STAR);
  }

  return errorToken("Unexpected character.");

소스 코드에서 다음 문자를 읽은 다음, Lox의 한 글자 렉심 중 어떤 것과 일치하는지 확인하기 위해 간단한 switch 문을 사용합니다. 다음 문자를 읽기 위해 현재 문자를 소비하고 반환하는 새로운 도우미 함수를 사용합니다.

static char advance() {
  scanner.current++;
  return scanner.current[-1];
}

다음은 != 및 >=와 같은 두 글자 구두점 토큰입니다. 이들 각각은 해당되는 한 글자 토큰도 가지고 있습니다. 이는 !와 같은 문자를 볼 때, 다음 문자까지 확인하기 전까지는 ! 토큰인지 != 토큰인지 알 수 없다는 의미입니다. 다음과 같이 처리합니다.

    case '*': return makeToken(TOKEN_STAR);

    case '!':
      return makeToken(
          match('=') ? TOKEN_BANG_EQUAL : TOKEN_BANG);
    case '=':
      return makeToken(
          match('=') ? TOKEN_EQUAL_EQUAL : TOKEN_EQUAL);
    case '<':
      return makeToken(
          match('=') ? TOKEN_LESS_EQUAL : TOKEN_LESS);
    case '>':
      return makeToken(
          match('=') ? TOKEN_GREATER_EQUAL : TOKEN_GREATER);

  }

첫 문자를 소비한 후, =를 찾습니다. 발견하면 이를 소비하고 해당하는 두 글자 토큰을 반환합니다. 그렇지 않으면 현재 문자를 그대로 두고 (다음 토큰의 일부가 될 수 있도록) 적절한 한 글자 토큰을 반환합니다.

두 번째 문자를 조건부로 소비하는 로직은 여기에 있습니다.

static bool match(char expected) {
  if (isAtEnd()) return false;
  if (*scanner.current != expected) return false;
  scanner.current++;
  return true;
}

현재 문자가 원하는 문자라면, 다음으로 이동하고 true를 반환합니다. 그렇지 않으면 일치하지 않았음을 나타내기 위해 false를 반환합니다.

이제 우리 스캐너는 모든 구두점 같은 토큰을 지원합니다. 더 긴 토큰으로 넘어가기 전에, 토큰의 일부가 아닌 문자를 처리하기 위해 잠시 다른 곳으로 가봅시다.

16 . 3 . 1공백

우리 스캐너는 공백, 탭, 개행 문자를 처리해야 하지만, 이 문자들은 어떤 토큰의 렉심에도 포함되지 않습니다. scanToken()의 메인 문자 스위치 안에서 이들을 확인할 수도 있지만, 그렇게 하면 공백 이후의 다음 토큰을 함수가 올바르게 찾아내도록 보장하는 것이 다소 까다로워집니다. 함수 본체 전체를 루프 등으로 감싸야 할 것입니다.

대신, 토큰 스캔을 시작하기 전에 별도의 함수로 이동합니다.

Token scanToken() {

  skipWhitespace();

  scanner.start = scanner.current;

이것은 스캐너를 선행 공백을 건너뛰도록 전진시킵니다. 이 호출이 반환된 후에는 바로 다음 문자가 의미 있는 문자라는 것을 알 수 있습니다 (또는 소스 코드의 끝에 도달했음을 알 수 있습니다).

static void skipWhitespace() {
  for (;;) {
    char c = peek();
    switch (c) {
      case ' ':
      case '\r':
      case '\t':
        advance();
        break;
      default:
        return;
    }
  }
}

이것은 일종의 독립적인 미니 스캐너입니다. 루프를 돌면서 만나는 모든 공백 문자를 소비합니다. 공백이 아닌 문자를 소비하지 않도록 주의해야 합니다. 이를 지원하기 위해 다음을 사용합니다.

static char peek() {
  return *scanner.current;
}

이는 단순히 현재 문자를 반환하지만 소비하지는 않습니다. 이전 코드는 개행 문자를 제외한 모든 공백 문자를 처리합니다.

        break;

      case '\n':
        scanner.line++;
        advance();
        break;

      default:
        return;

이들 중 하나를 소비할 때, 현재 줄 번호도 증가시킵니다.

16 . 3 . 2주석

엄밀히 말하자면 주석은 "공백"이 아니지만, Lox의 관점에서 보면 공백과 마찬가지이므로 주석도 건너뜁니다.

        break;

      case '/':
        if (peekNext() == '/') {
          // 주석은 줄의 끝까지 이어집니다.
          while (peek() != '\n' && !isAtEnd()) advance();
        } else {
          return;
        }
        break;

      default:
        return;

Lox에서 주석은 //로 시작하므로, != 등과 마찬가지로 두 번째 문자를 미리 봐야 합니다. 하지만 !=의 경우 =가 발견되지 않아도 !를 소비하길 원했습니다. 주석은 다릅니다. 두 번째 /를 찾지 못하면, skipWhitespace()는 첫 번째 슬래시도 소비하지 않아야 합니다.

이를 처리하기 위해 다음을 추가합니다.

static char peekNext() {
  if (isAtEnd()) return '\0';
  return scanner.current[1];
}

이것은 peek()와 비슷하지만 현재 문자에서 한 문자 뒤를 보는 것입니다. 현재 문자와 다음 문자가 모두 /라면, 이들을 소비하고 다음 개행 문자 또는 소스 코드 끝에 도달할 때까지 다른 문자를 소비합니다.

우리는 개행 문자를 확인하기 위해 peek()를 사용하지만, 이를 소비하지는 않습니다. 그렇게 하면 skipWhitespace()의 외부 루프 다음 차례에서 개행 문자가 현재 문자가 될 것이고, 우리는 이를 인식하여 scanner.line을 증가시킬 것입니다.

16 . 3 . 3리터럴 토큰

숫자와 문자열 토큰은 런타임 값과 연관되어 있기 때문에 특별합니다. 문자열은 항상 이중 인용 부호로 시작하므로 인식하기 쉽기 때문에 문자열부터 시작하겠습니다.

          match('=') ? TOKEN_GREATER_EQUAL : TOKEN_GREATER);

    case '"': return string();

  }

이는 새로운 함수를 호출합니다.

static Token string() {
  while (peek() != '"' && !isAtEnd()) {
    if (peek() == '\n') scanner.line++;
    advance();
  }

  if (isAtEnd()) return errorToken("Unterminated string.");

  // 닫는 따옴표.
  advance();
  return makeToken(TOKEN_STRING);
}

jlox와 유사하게, 우리는 닫는 따옴표에 도달할 때까지 문자를 소비합니다. 문자열 리터럴 내부의 개행 문자도 추적합니다. (Lox는 여러 줄 문자열을 지원합니다.) 그리고 항상 그랬듯이, 닫는 따옴표를 찾기 전에 소스 코드가 끝나는 경우를 우아하게 처리합니다.

clox에서 주요 변경 사항은 없는 것입니다. 다시 말하지만, 이는 메모리 관리와 관련이 있습니다. jlox에서는 Token 클래스에 리터럴 토큰의 렉심에서 변환된 런타임 값을 저장하는 Object 타입의 필드가 있었습니다.

이를 C로 구현하려면 많은 작업이 필요할 것입니다. 토큰이 문자열 값 또는 double 값을 포함하는지 판별하기 위해 어떤 종류의 유니온과 타입 태그가 필요할 것입니다. 만약 문자열이라면, 문자열의 문자 배열을 위한 메모리를 어떻게든 관리해야 할 것입니다.

스캐너에 그러한 복잡성을 추가하는 대신, 리터럴 렉심을 런타임 값으로 변환하는 작업을 나중으로 미룹니다. clox에서 토큰은 렉심만 저장합니다—사용자 소스 코드에 나타난 그대로의 문자 시퀀스입니다. 컴파일러의 나중 단계에서, 우리는 청크의 상수 테이블에 저장할 준비가 되었을 때 해당 렉심을 런타임 값으로 변환할 것입니다.

다음은 숫자입니다. 숫자를 시작할 수 있는 10개의 각 숫자에 대해 switch case를 추가하는 대신, 여기서 처리합니다.

  char c = advance();

  if (isDigit(c)) return number();

  switch (c) {

이는 이 명확한 유틸리티 함수를 사용합니다.

static bool isDigit(char c) {
  return c >= '0' && c <= '9';
}

다음과 같이 숫자를 스캔하는 것을 마칩니다.

static Token number() {
  while (isDigit(peek())) advance();

  // 소수점 부분을 찾습니다.
  if (peek() == '.' && isDigit(peekNext())) {
    // "."를 소비합니다.
    advance();

    while (isDigit(peek())) advance();
  }

  return makeToken(TOKEN_NUMBER);
}

jlox 버전과 거의 동일하지만, 다시 말하지만, 아직 렉심을 double로 변환하지 않습니다.

16 . 4식별자와 키워드

마지막 토큰 묶음은 식별자인데, 사용자 정의 식별자와 예약된 식별자 모두를 포함합니다. 이 섹션은 흥미로울 것입니다—clox에서 키워드를 인식하는 방식은 jlox에서 했던 방식과 상당히 다르며, 몇 가지 중요한 데이터 구조를 다룹니다.

하지만 먼저 렉심을 스캔해야 합니다. 이름은 문자 또는 밑줄로 시작합니다.

  char c = advance();

  if (isAlpha(c)) return identifier();

  if (isDigit(c)) return number();

우리는 다음을 사용하여 이들을 인식합니다.

static bool isAlpha(char c) {
  return (c >= 'a' && c <= 'z') ||
         (c >= 'A' && c <= 'Z') ||
          c == '_';
}

식별자를 찾으면, 여기서 나머지 부분을 스캔합니다.

static Token identifier() {
  while (isAlpha(peek()) || isDigit(peek())) advance();
  return makeToken(identifierType());
}

첫 문자 이후에는 숫자도 허용하며, 더 이상 알파벳 또는 숫자가 없을 때까지 계속 소비합니다. 그런 다음 적절한 타입의 토큰을 생성합니다. 그 "적절한" 타입을 결정하는 것이 이 장의 독특한 부분입니다.

static TokenType identifierType() {
  return TOKEN_IDENTIFIER;
}

네, 아직은 그다지 흥미롭지 않죠. 예약어가 전혀 없을 때의 모습입니다. 키워드를 어떻게 인식해야 할까요? jlox에서는 모든 키워드를 자바 Map에 넣고 이름으로 찾았습니다. clox에는 아직 해시 테이블 구조가 없습니다.

어차피 해시 테이블은 과잉일 것입니다. 해시 테이블에서 문자열을 찾으려면, 문자열을 따라가며 해시 코드를 계산하고, 해시 테이블에서 해당 버킷을 찾은 다음, 그곳에서 발견되는 모든 문자열에 대해 문자 단위로 일치 비교를 수행해야 합니다.

식별자 "gorgonzola"를 스캔했다고 가정해 봅시다. 이것이 예약어인지 판별하기 위해 얼마나 많은 작업을 해야 할까요? Lox 키워드 중 "g"로 시작하는 것은 없으므로, 첫 글자만 봐도 아니라고 확실히 답할 수 있습니다. 이는 해시 테이블 조회보다 훨씬 간단합니다.

그렇다면 "cardigan"은 어떨까요? Lox에는 "c"로 시작하는 키워드 "class"가 있습니다. 하지만 "cardigan"의 두 번째 문자 "a"는 이를 배제시킵니다. "forest"는 어떨까요? "for"가 키워드이므로, 예약어가 아님을 확정하기 전에 문자열을 더 깊이 살펴봐야 합니다. 하지만 대부분의 경우, 한두 문자만으로도 사용자 정의 이름임을 알 수 있습니다. 우리는 이를 인식하고 빠르게 실패할 수 있어야 합니다.

여기서 분기되는 문자 검사 로직을 시각적으로 표현한 것입니다.

우리는 루트 노드부터 시작합니다. 렉심의 첫 번째 문자와 일치하는 문자를 가진 자식 노드가 있다면, 해당 노드로 이동합니다. 그런 다음 렉심의 다음 문자에 대해 반복합니다. 어떤 시점에서든 렉심의 다음 문자가 자식 노드와 일치하지 않는다면, 식별자는 키워드가 아니므로 중단합니다. 만약 이중선 상자에 도달하고 렉심의 마지막 문자에 있다면, 키워드를 찾은 것입니다.

16 . 4 . 1트라이와 상태 머신

이 트리 다이어그램은 트라이(trie)라고 불리는 것의 예시입니다. 트라이는 문자열 집합을 저장합니다. 문자열을 저장하는 대부분의 다른 데이터 구조는 원시 문자 배열을 포함하고, 더 빠르게 검색하는 데 도움이 되는 더 큰 구조체로 이를 감쌉니다. 트라이는 다릅니다. 트라이 내에서는 전체 문자열을 찾을 수 없습니다.

대신, 트라이가 "포함하는" 각 문자열은 위에서 탐색한 것처럼 문자 노드 트리를 통한 경로로 표현됩니다. 문자열의 마지막 문자와 일치하는 노드에는 특별한 표시—그림의 이중선 상자—가 있습니다. 이런 방식으로, 만약 트라이가 "banquet"과 "ban"을 포함하고 있다면, "banque"는 포함하지 않는다는 것을 알 수 있습니다—"e" 노드에는 해당 표시가 없고, "n" 및 "t" 노드에는 표시가 있을 것이기 때문입니다.

트라이는 더욱 근본적인 데이터 구조인 결정적 유한 오토마타(deterministic finite automaton, DFA)의 특별한 경우입니다. 여러분은 이를 유한 상태 머신(finite state machine) 또는 단순히 상태 머신(state machine)이라는 다른 이름으로도 알고 있을 수 있습니다. 상태 머신은 멋집니다. 게임 프로그래밍에서 네트워킹 프로토콜 구현에 이르기까지 모든 곳에서 유용하게 사용됩니다.

DFA에서는 상태 집합과 그 사이에 전이(transition)가 있어 그래프를 형성합니다. 어느 시점에서든 머신은 정확히 하나의 상태에 "있게" 됩니다. 전이를 따라 다른 상태로 이동합니다. 어휘 분석에 DFA를 사용할 때, 각 전이는 문자열에서 일치하는 문자이고, 각 상태는 허용되는 문자 집합을 나타냅니다.

우리의 키워드 트리는 Lox 키워드를 인식하는 DFA와 정확히 일치합니다. 하지만 DFA는 단순한 트리보다 더 강력한데, 임의의 그래프가 될 수 있기 때문입니다. 전이는 상태 간에 순환을 형성할 수 있습니다. 이를 통해 임의로 긴 문자열을 인식할 수 있습니다. 예를 들어, 다음은 숫자 리터럴을 인식하는 DFA입니다.

가독성을 높이기 위해 10개의 숫자에 해당하는 노드들을 하나로 묶었지만, 기본 과정은 동일하게 작동합니다—렉심에서 해당 문자를 소비할 때마다 경로를 따라 노드로 진입합니다. 만약 우리가 원한다면, Lox의 모든 어휘 분석을 수행하는 하나의 거대한 DFA를 구성할 수 있을 것입니다. 필요한 모든 토큰을 인식하고 뱉어내는 단일 상태 머신 말이죠.

하지만 그 거대한 DFA를 수동으로 만드는 것은 어려울 것입니다. 그래서 Lex가 만들어졌습니다. Lex에 어휘 문법에 대한 간단한 텍스트 설명—일련의 정규 표현식—을 제공하면, 자동으로 DFA를 생성하고 이를 구현하는 C 코드 덩어리를 만들어줍니다.

우리는 그 길을 가지 않을 것입니다. 이미 완벽하게 쓸만한 수동으로 만든 스캐너가 있습니다. 키워드를 인식하기 위한 작은 트라이만 있으면 됩니다. 이것을 코드로 어떻게 매핑해야 할까요?

가장 간단한 해결책은 각 노드에 대해 각 분기에 대한 case를 가진 switch 문을 사용하는 것입니다. 루트 노드부터 시작하여 쉬운 키워드들을 처리할 것입니다.

static TokenType identifierType() {

  switch (scanner.start[0]) {
    case 'a': return checkKeyword(1, 2, "nd", TOKEN_AND);
    case 'c': return checkKeyword(1, 4, "lass", TOKEN_CLASS);
    case 'e': return checkKeyword(1, 3, "lse", TOKEN_ELSE);
    case 'i': return checkKeyword(1, 1, "f", TOKEN_IF);
    case 'n': return checkKeyword(1, 2, "il", TOKEN_NIL);
    case 'o': return checkKeyword(1, 1, "r", TOKEN_OR);
    case 'p': return checkKeyword(1, 4, "rint", TOKEN_PRINT);
    case 'r': return checkKeyword(1, 5, "eturn", TOKEN_RETURN);
    case 's': return checkKeyword(1, 4, "uper", TOKEN_SUPER);
    case 'v': return checkKeyword(1, 2, "ar", TOKEN_VAR);
    case 'w': return checkKeyword(1, 4, "hile", TOKEN_WHILE);
  }

  return TOKEN_IDENTIFIER;

이들은 단일 키워드에 해당하는 초기 문자들입니다. "s"를 본다면, 식별자가 될 수 있는 유일한 키워드는 super입니다. 하지만 아닐 수도 있으므로, 나머지 문자들도 확인해야 합니다. 트리 다이어그램에서 이것은 기본적으로 "s"에서 뻗어 나온 직선 경로입니다.

각 노드에 대해 switch 문을 작성하지 않을 것입니다. 대신, 잠재적인 키워드의 렉심의 나머지를 테스트하는 유틸리티 함수를 사용합니다.

static TokenType checkKeyword(int start, int length,
    const char* rest, TokenType type) {
  if (scanner.current - scanner.start == start + length &&
      memcmp(scanner.start + start, rest, length) == 0) {
    return type;
  }

  return TOKEN_IDENTIFIER;
}

우리는 트리 내에서 분기되지 않는 모든 경로에 이 함수를 사용합니다. 오직 하나의 예약어일 수 있는 접두사를 찾으면, 두 가지를 확인해야 합니다. 렉심은 키워드와 정확히 같은 길이어야 합니다. 첫 글자가 "s"라도 렉심이 "sup" 또는 "superb"일 수 있습니다. 그리고 나머지 문자들도 정확히 일치해야 합니다—"supar"는 충분하지 않습니다.

만약 올바른 수의 문자를 가지고 있고, 우리가 원하는 문자라면, 그것은 키워드이고 해당 토큰 타입을 반환합니다. 그렇지 않다면, 일반 식별자여야 합니다.

트리가 첫 글자 다음에 다시 분기되는 키워드가 몇 개 있습니다. 렉심이 "f"로 시작한다면, false, for 또는 fun일 수 있습니다. 따라서 "f" 노드에서 뻗어 나오는 분기들을 위한 또 다른 switch 문을 추가합니다.

    case 'e': return checkKeyword(1, 3, "lse", TOKEN_ELSE);

    case 'f':
      if (scanner.current - scanner.start > 1) {
        switch (scanner.start[1]) {
          case 'a': return checkKeyword(2, 3, "lse", TOKEN_FALSE);
          case 'o': return checkKeyword(2, 1, "r", TOKEN_FOR);
          case 'u': return checkKeyword(2, 1, "n", TOKEN_FUN);
        }
      }
      break;

    case 'i': return checkKeyword(1, 1, "f", TOKEN_IF);

스위치하기 전에 두 번째 글자가 있는지 확인해야 합니다. 어쨌든 "f" 자체도 유효한 식별자입니다. 분기되는 다른 글자는 "t"입니다.

    case 's': return checkKeyword(1, 4, "uper", TOKEN_SUPER);

    case 't':
      if (scanner.current - scanner.start > 1) {
        switch (scanner.start[1]) {
          case 'h': return checkKeyword(2, 2, "is", TOKEN_THIS);
          case 'r': return checkKeyword(2, 2, "ue", TOKEN_TRUE);
        }
      }
      break;

    case 'v': return checkKeyword(1, 2, "ar", TOKEN_VAR);

그게 다입니다. 몇 개의 중첩된 switch 문입니다. 이 코드는 간단할 뿐만 아니라, 매우 빠릅니다. 키워드를 감지하는 데 필요한 최소한의 작업을 수행하며, 식별자가 예약어가 아님을 알 수 있는 즉시 작업을 중단합니다.

이로써 우리 스캐너가 완성되었습니다.