用 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

基于谓词的字符序列解析器：

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")      // 成功
pCommand("rotate 30 right") // 成功

关键要点

• 解析器返回 [result, remainder] 或 null，不分析整个文本。
• pSequence 组合子按顺序应用解析器，传递剩余部分。
• pOneOf 按顺序测试选项，返回第一个成功项。
• 基本解析器（pString, pSpanOf）涵盖了大多数原语。
• TypeScript 泛型确保结果的类型安全。

— Editorial Team