렉서

토큰

렉서는 토크나이저 또는 스캐너라고도 불리며, 소스 텍스트를 토큰으로 변환하는 책임을 맡습니다.
이 토큰들은 나중에 파서에서 소비되므로 원본 텍스트의 공백과 주석에 대해 걱정할 필요가 없습니다.

단순하게 시작해 + 하나의 텍스트를 토큰으로 변환해봅시다.

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// 토큰 종류
    pub kind: Kind,

    /// 소스 내 시작 오프셋
    pub start: usize,

    /// 소스 내 종료 오프셋
    pub end: usize,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Kind {
    Eof, // 파일 끝
    Plus,
}

단일 +로 얻는 결과는 다음과 같습니다:

[
    Token { kind: Kind::Plus, start: 0, end: 1 },
    Token { kind: Kind::Eof,  start: 1, end: 1 }
]

문자열을 반복 처리하려면 인덱스를 추적하면서 마치 C 코드를 작성하는 방식을 취할 수도 있지만,
문자열 문서를 살펴보면 Chars 반복자를 사용할 수 있습니다.

INFO

Chars 반복자는 인덱스 추적과 경계 확인을 추상화하여 안전한 느낌을 줍니다.

chars.next()를 호출하면 Option<char>를 반환합니다.
하지만 주의할 점은 char가 0-255의 아스키 값이 아니라, 범위가 0에서 0x10FFFF까지인 유니코드 포인트 값이라는 것입니다.

이제 시작용 렉서 추상화를 정의해 봅시다.

use std::str::Chars;

struct Lexer<'a> {
    /// 소스 텍스트
    source: &'a str,

    /// 남아 있는 문자들
    chars: Chars<'a>
}

impl<'a> Lexer<'a> {
    pub fn new(source: &'a str) -> Self {
        Self {
            source,
            chars: source.chars()
        }
    }
}

INFO

여기서 'a 라이프타임은 반복자가 어디를 참조하는지를 나타냅니다. 이 경우 &'a str를 참조합니다.

소스 텍스트를 토큰으로 변환하려면 계속해서 chars.next()를 호출하고 반환된 char들을 매칭하면 됩니다.
마지막 토큰은 항상 Kind::Eof가 됩니다.

impl<'a> Lexer<'a> {
    fn read_next_kind(&mut self) -> Kind {
        while let Some(c) = self.chars.next() {
            match c {
              '+' => return Kind::Plus,
              _ => {}
            }
        }
        Kind::Eof
    }

    fn read_next_token(&mut self) -> Token {
        let start = self.offset();
        let kind = self.read_next_kind();
        let end = self.offset();
        Token { kind, start, end }
    }

    /// 소스 텍스트로부터의 오프셋 길이 (유니코드 바이트 단위)
    fn offset(&self) -> usize {
        self.source.len() - self.chars.as_str().len()
    }
}

fn offset 내부의 .len() 및 .as_str().len() 메서드 호출은 비슷하게 O(n)처럼 보입니다.
그러나 좀 더 깊게 들여다보겠습니다.

.as_str()는 문자열 슬라이스에 대한 포인터를 반환합니다.

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/iter.rs#L112-L115

pub fn as_str(&self) -> &'a str {
    // SAFETY: `Chars`는 항상 문자열에서 만들어지므로 유효한 UTF-8임이 보장됨
    unsafe { from_utf8_unchecked(self.iter.as_slice()) }
}

슬라이스는 포인터와 길이로 표현된 메모리 블록의 뷰입니다.
.len() 메서드는 슬라이스 내부에 저장된 메타데이터를 반환합니다.

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/mod.rs#L157-L159

pub const fn len(&self) -> usize {
    self.as_bytes().len()
}

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/str/mod.rs#L323-L325

pub const fn as_bytes(&self) -> &[u8] {
    // SAFETY: const 안정성은 같은 구조를 가진 두 타입 간의 전환 가능함
    unsafe { mem::transmute(self) }
}

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/slice/mod.rs#L129-L138

pub const fn len(&self) -> usize {
    // FIXME: `crate::ptr::metadata(self)`가 상수 안정적이 되면 이 부분을 교체해야 함.
    // 현재는 "상수 안정 함수는 다른 상수 안정 함수만 호출할 수 있다"라는 오류 발생.

    // SAFETY: *const T와 PtrComponents<T>는 동일한 메모리 레이아웃을 가지므로,
    // `PtrRepr` 유니온에서 값을 접근하는 것은 안전함. 이 보장을 할 수 있는 곳은 단지 `std`뿐임.
    unsafe { crate::ptr::PtrRepr { const_ptr: self }.components.metadata }
}

위 코드들은 모두 하나의 데이터 접근으로 컴파일되므로, .as_str().len()은 실제로는 O(1)입니다.

미리 보기

++ 또는 +=와 같은 다문자 연산자를 토큰화하기 위해 peek라는 보조 함수가 필요합니다:

fn peek(&self) -> Option<char> {
    self.chars.clone().next()
}

원래의 chars 반복자를 앞으로 진행시키지 않기 때문에 반복자를 복제하고 인덱스를 앞으로 이동시킵니다.

INFO

소스 코드를 들여다보면 clone은 저렴합니다.
반복자 자체의 추적 및 경계 인덱스만 복사되기 때문입니다.

// https://github.com/rust-lang/rust/blob/b998821e4c51c44a9ebee395c91323c374236bbb/library/core/src/slice/iter.rs#L148-L152

impl<T> Clone for Iter<'_, T> {
    fn clone(&self) -> Self {
        Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
    }
}

peek와 chars.next()의 차이는 앞자는 항상 같은 다음 char를 반환하지만,
후자는 다음 char로 이동하며 서로 다른 char를 반환한다는 점입니다.

예를 들어 abc 문자열을 생각해 봅시다:

• 반복적인 peek() 호출은 Some(a), Some(a), Some(a), ...를 반환합니다.
• 반복적인 chars.next() 호출은 Some('a'), Some('b'), Some('c'), None을 반환합니다.

peek 기능을 갖추면 ++와 +=의 토큰화는 중첩된 if 문만으로 가능합니다.

jsparagus에서 실제 사용된 구현 예시입니다:

// https://github.com/mozilla-spidermonkey/jsparagus/blob/master/crates/parser/src/lexer.rs#L1769-L1791

'+' => match self.peek() {
    Some('+') => {
        self.chars.next();
        return self.set_result(
            TerminalId::Increment,
            SourceLocation::new(start, self.offset()),
            TokenValue::None,
        );
    }
    Some('=') => {
        self.chars.next();
        return self.set_result(
            TerminalId::AddAssign,
            SourceLocation::new(start, self.offset()),
            TokenValue::None,
        );
    }
    _ => return self.set_result(
        TerminalId::Plus,
        SourceLocation::new(start, self.offset()),
        TokenValue::None,
    ),
},

위 로직은 모든 연산자에 적용될 수 있으므로, 이제 자바스크립트 토큰화에 대한 지식을 확장해 봅시다.

자바스크립트

라스트로 작성된 렉서는 다소 딱딱하게 느껴집니다. 마치 쓰레기같은 장황한 if 문을 연속적으로 작성하는 것처럼 느껴지죠.
이런 시도는 결국 각 char를 검사하고 그에 따라 토큰을 반환하는 형태로 끝납니다.

하지만 자바스크립트를 토큰화하기 시작하면 진짜 재미가 생깁니다.

자바스크립트 언어 사양을 열어보고 다시 자바스크립트를 배워봅시다.

TIP

처음 사양 문서를 열고 작은 구석에 앉아 고통스럽게 울었던 기억이 아직도 납니다.
이해되지 않는 전문 용어들이 여기저기 넘쳐나기 때문이죠.
만약 이해되지 않는다면, 사양 문서 읽는 방법 가이드로 이동하세요.

주석

주석은 의미적 의미가 없으며, 런타임을 작성할 경우 건너뛸 수 있습니다.
하지만 린터나 번들러를 만들 때는 반드시 고려해야 합니다.

식별자 및 유니코드

우리는 대부분 아스키로 코드를 작성하지만,
장 11 자바스크립트 언어: 소스 텍스트에서는 소스 텍스트가 유니코드여야 한다고 명시하고 있습니다.
또한 장 12.6 이름과 키워드에서는 식별자는 유니코드 표준 첨부 #31에 제시된 기본 식별자 구문에 따라 해석되어야 한다고 설명합니다.

구체적으로:

IdentifierStartChar ::
    UnicodeIDStart

IdentifierPartChar ::
    UnicodeIDContinue

UnicodeIDStart ::
    유니코드 속성이 “ID_Start”인 모든 유니코드 코드 포인트

UnicodeIDContinue ::
    유니코드 속성이 “ID_Continue”인 모든 유니코드 코드 포인트

즉, var ಠ_ಠ와 같이 작성할 수 있지만 var 🦀는 불가능합니다.
ಠ는 유니코드 속성 "ID_Start"를 가지지만, 🦀는 그렇지 않습니다.

INFO

이 정확한 목적을 위해 unicode-id-start 패키지를 발표했습니다.
unicode_id_start::is_id_start(char) 및 unicode_id_start::is_id_continue(char) 함수를 호출해 유니코드를 검사할 수 있습니다.

키워드

if, while, for와 같은 모든 키워드는 토큰화되어 전체적으로 해석되어야 합니다.
이러한 키워드는 토큰 종류 열거형에 추가되어야 하며, 파서에서 문자열 비교를 피할 수 있습니다.

pub enum Kind {
    Identifier,
    If,
    While,
    For
}

TIP

undefined는 키워드가 아니며, 여기에 추가할 필요가 없습니다.

키워드 토큰화는 위의 식별자 매칭과 동일합니다.

fn match_keyword(&self, ident: &str) -> Kind {
    // 모든 키워드는 1 < 길이 <= 10
    if ident.len() == 1 || ident.len() > 10 {
        return Kind::Identifier;
    }
    match ident {
        "if" => Kind::If,
        "while" => Kind::While,
        "for" => Kind::For,
        _ => Kind::Identifier
    }
}

토큰 값

컴파일러 단계 후반에서는 식별자, 숫자, 문자열을 비교해야 하는 경우가 많습니다.
예를 들어 린터 내에서 식별자와 비교할 때 등.

현재 이러한 값들은 순수한 소스 텍스트에 존재합니다.
이를 러스트 타입으로 변환해 사용하기 쉽게 만듭시다.

pub enum Kind {
    Eof, // 파일 끝
    Plus,
    Identifier,
    Number,
    String,
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Token {
    /// 토큰 종류
    pub kind: Kind,

    /// 소스 내 시작 오프셋
    pub start: usize,

    /// 소스 내 종료 오프셋
    pub end: usize,

    pub value: TokenValue,
}

#[derive(Debug, Clone, PartialEq)]
pub enum TokenValue {
    None,
    Number(f64),
    String(String),
}

식별자 foo 또는 문자열 "bar"가 토큰화되면 다음과 같은 결과를 얻습니다:

Token { kind: Kind::Identifier, start: 0, end: 2, value: TokenValue::String("foo") }
Token { kind: Kind::String, start: 0, end: 4, value: TokenValue::String("bar") }

이를 러스트 문자열로 변환하려면 let s = self.source[token.start..token.end].to_string()를 호출하고, token.value = TokenValue::String(s)로 저장하면 됩니다.

숫자 1.23을 토큰화하면 Token { start: 0, end: 3 }라는 토큰을 얻습니다.
이를 러스트 f64로 변환하려면 문자열 parse 메서드를 사용합니다.
self.source[token.start..token.end].parse::<f64>()를 호출하고, 그 결과를 token.value에 저장하면 됩니다.
이진수, 옥트럴, 정수의 경우는 jsparagus에서 파싱 기법을 참고할 수 있습니다.

러스트 최적화

더 작은 토큰

Kind 열거형 내에 토큰 값을 넣는 것이 매력적일 수 있습니다.
이렇게 하면 코드가 더 단순하고 안전해질 수 있겠죠.

pub enum Kind {
    Number(f64),
    String(String),
}

하지만 러스트의 열거형 크기는 모든 버전의 합집합 크기라는 점을 알고 있습니다.
이 열거형은 원래 1바이트였던 것보다 훨씬 많은 바이트를 포함하게 됩니다.
이 Kind 열거형은 파서에서 자주 사용되므로, 1바이트 열거형을 다루는 것이 다바이트 열거형을 다루는 것보다 분명히 빠릅니다.

문자열 통합

컴파일러에서 String을 사용하는 것은 성능상 좋지 않습니다. 주요 이유는 다음과 같습니다:

• String은 힙에 할당된 객체입니다.
• 문자열 비교는 O(n) 작업입니다.

String Interning은 캐시에 각 고유한 문자열 값에 대해 하나의 복사본과 고유 식별자를 저장함으로써 이러한 문제를 해결합니다.
고유한 식별자나 문자열마다 힙 할당이 단 한 번만 이루어지고, 문자열 비교는 O(1)로 빨라집니다.

crates.io에는 다양한 장단점이 있는 여러 문자열 통합 라이브러리가 있습니다.

충분히 시작할 수 있는 선택은 string-cache를 사용하는 것입니다.
이 라이브러리는 Atom 타입과 컴파일 시간 atom!("string") 인터페이스를 제공합니다.

string-cache를 사용하면 TokenValue는 다음과 같이 변합니다:

#[derive(Debug, Clone, PartialEq)]
pub enum TokenValue {
    None,
    Number(f64),
    String(Atom), 
}

그리고 문자열 비교는 matches!(value, TokenValue::String(atom!("string")))로 수행됩니다.