TypeScript로 처음부터 파서 콤비네이터 구현

파서 콤비네이터: TypeScript 로 처음부터 구현하기

파서는 입력 문자열의 시작 부분을 분석하여 성공적으로 인식된 조각과 나머지 텍스트를 반환하거나 오류를 반환하는 함수입니다. 파싱 결과는 ParseResult<T> = [T, string] | null 타입으로 표현됩니다. 성공은 추출된 데이터와 문자열의 나머지 부분을 의미하며, 실패는 null 을 의미합니다.

간단한 숫자 파서의 동작 예시:

parseDigit("1")     // ["1", ""] 
parseDigit("1cm")   // ["1", "cm"]
parseDigit("123")   // ["1", "23"]
parseDigit("hello") // null

파서는 전체 텍스트를 확인하지 않고 시작 부분만 확인합니다. 나머지는 체인의 다음 파서로 전달됩니다.

기본 파서: 문자열 및 문자 범위

첫 번째 파서는 입력 시작 부분에서 정확한 문자열 일치를 찾습니다:

type ParseResult<T> = [T, string] | null;
type Parser<T> = (input: string) => ParseResult<T>;

function pString(str: string): Parser<string> {
    return (input: string) => {
        if (input.startsWith(str))
            return [str, input.substring(str.length)]
        else
            return null
    }
}

예시:

• pString("hello")("hello") → ["hello", ""]
• pString("hello")("hello, world!") → ["hello", ", world!"]
• pString("hello")("hi!") → null

술어 (predicate) 기반 문자 시퀀스 파서:

function pSpanOf(predicate: (char: string) => boolean): Parser<string> {
    return (input: string) => {
        let i = 0;
        while (i < input.length) {
            if (!predicate(input[i])) break
            i++
        }
        return [input.substring(0, i), input.substring(i)]
    }
}

function pNonEmptySpanOf(predicate: (char: string) => boolean): Parser<string> { 
    return (input: string) => {
        const result = pSpanOf(predicate)(input)
        if (result == null || result[0].length == 0) return null;
        return result
    }
}

자연수와 공백에 대한 적용:

const pNatural = pNonEmptySpanOf(char => "0123456789".includes(char));
const pSpace = pSpanOf(char => char == " ");

pNatural("123")     // ["123", ""]
pNatural("123cm")   // ["123", "cm"]
pSpace("   123")    // ["   ", "123"]

시퀀스 조합자

pSequence 조합자는 파서들을 체인으로 결합하여 이전 파서의 나머지에 순차적으로 적용합니다:

function pSequence<T>(...parsers: Parser<T>[]): Parser<T[]> {
    return (input: string) => {
        const results: T[] = []
        let current = input
        for (const parser of parsers) {
            const result = parser(current)
            if (result == null) return null
            results.push(result[0])
            current = result[1]
        }
        return [results, current]
    }
}

로봇 명령 forward 45 에 대한 예시:

const pForward = pSequence(
    pString("forward"),
    pSpace,
    pNatural
);

pForward("forward 45")    // [["forward", " ", "45"], ""]
pForward("forward")       // null
pForward("forward45")     // [["forward", "", "45"], ""]

각 파서는 이전 파서의 나머지를 사용하여 작동합니다. 단계에서 오류가 발생하면 전체 시퀀스가 중단됩니다.

선택 조합자

pOneOf 는 파서들을 순서대로 시도하여 첫 번째 성공 결과를 반환합니다:

function pOneOf<T>(...parsers: Parser<T>[]): Parser<T> {
    return (input: string) => {
        for (const parser of parsers) {
            const result = parser(input)
            if (result != null) return result;
        }
        return null;
    }
}

로봇 명령 문법 확장:

const pCommand = pOneOf(
    pSequence(pString("forward"), pSpace, pNatural),
    pSequence(pString("backward"), pSpace, pNatural),
    pSequence(
        pString("rotate"),
        pSpace, pNatural,
        pSpace,
        pOneOf(pString("left"), pString("right"))
    )
);

pCommand("forward 45")      // Success
pCommand("rotate 30 right") // Success

핵심 요약

• 파서는 전체 텍스트를 분석하지 않고 [결과, 나머지] 또는 null 을 반환합니다.
• pSequence 조합자는 나머지를 전달하면서 파서를 순차적으로 적용합니다.
• pOneOf 는 옵션을 순서대로 테스트하여 첫 번째 성공을 반환합니다.
• 기본 파서 (pString, pSpanOf) 는 대부분의 기본 요소를 커버합니다.
• TypeScript 제네릭은 결과에 대한 타입 안전성을 보장합니다.

— Editorial Team