Mini calc compiler with TS template string types

mini_calc_interpreter.ts

/**
 * 
 * Mini calc with TypeScript template string types
 * 
 * EBNF
 * 
 * ```
 * expr    = mul ("+" mul)*
 * mul     = primary ("*" primary)*
 * primary = num | "(" expr ")"
 * num     = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "10" | ...
 * ```
 */

type Tokenized = Tokenize<"(1 + 1) * (2 + 0) + 10">;
type AST = Parse<Tokenized>;
type EvalResultAsPeanoInt = Evaluate<AST>;
type EvalResultAsNumber = P2N<EvalResultAsPeanoInt>; // this type should be "14" 

/* Integer Utilities */
type PeanoNat = { s: PeanoNat | null }; // e.g. "2" should be reperesented by { s: s: { null } }
type PeanoInt = PeanoNat | null;

// Binary arithmetic operations
type Add<T extends PeanoInt, S extends PeanoInt> = S extends { s: infer U } ? U extends PeanoInt ? { s: Add<T, U> } : never : T;
type Multiply<T extends PeanoInt, S extends PeanoInt> =
    T extends null ? null : S extends null ? null :
    T extends { s: null } ? S :
    T extends { s: infer T2 } ? T2 extends PeanoInt ? Add<Multiply<T2, S>, S> : never : never;

// number to Peano interger
type N2P<N extends number, Y extends PeanoInt = null, X extends null[] = []> = X["length"] extends N ? Y : { s: N2P<N, Y, [null, ...X]> };

// Peano integer to number
type P2NInner<P extends PeanoInt, X extends null[] = []> = P extends null ? X : P extends { s: infer P2 } ? P2 extends PeanoInt ? [null, ...P2NInner<P2>] : never : never;
type P2N<P extends PeanoInt> = P2NInner<P> extends infer X ? X extends any[] ? X["length"] : never : never;

type Repeat<T1 extends PeanoInt, N extends number, X extends null[] = [], T2 extends PeanoInt = T1, T3 extends PeanoInt = null> = X["length"] extends N ? T3 : Repeat<Add<T1, T2>, N, [null, ...X], T2, T1>;
type ShiftLeft<S extends PeanoNat | null, T extends PeanoNat | null> = S extends null ? T : Add<Repeat<S, 10>, T>;

/* Tokenizer */
// Token kinds
type LPToken = { type: "LeftParenthesis" };
type RPToken = { type: "RightParenthesis" };
type PlusToken = { type: "Plus" };
type TimesToken = { type: "Times" };
type NatToken = { type: "Natural Number", value: PeanoInt };
type Token = LPToken | RPToken | PlusToken | TimesToken | NatToken;

type Tokens = [head: Token, rest: Tokens] | [];

type Tokenize<T extends string, N extends NatToken | null = null> =
    T extends "" ? N extends NatToken ? [N, []] : [] :
    T extends ` ${infer S}` ? N extends NatToken ? [N, Tokenize<S>] : Tokenize<S> :
    T extends `(${infer S}` ? N extends NatToken ? [N, [LPToken, Tokenize<S>]] : [LPToken, Tokenize<S>] :
    T extends `)${infer S}` ? N extends NatToken ? [N, [RPToken, Tokenize<S>]] : [RPToken, Tokenize<S>] :
    T extends `+${infer S}` ? N extends NatToken ? [N, [PlusToken, Tokenize<S>]] : [PlusToken, Tokenize<S>] :
    T extends `*${infer S}` ? N extends NatToken ? [N, [TimesToken, Tokenize<S>]] : [TimesToken, Tokenize<S>] :
    T extends `0${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<0>> : N2P<0> }> :
    T extends `1${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<1>> : N2P<1> }> :
    T extends `2${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<2>> : N2P<2> }> :
    T extends `3${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<3>> : N2P<3> }> :
    T extends `4${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<4>> : N2P<4> }> :
    T extends `5${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<5>> : N2P<5> }> :
    T extends `6${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<6>> : N2P<6> }> :
    T extends `7${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<7>> : N2P<7> }> :
    T extends `8${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<8>> : N2P<8> }> :
    T extends `9${infer S}` ? Tokenize<S, { type: "Natural Number", value: N extends NatToken ? ShiftLeft<N["value"], N2P<9>> : N2P<9> }> :
    never;

/* Parser */

// Node kinds
type NumberLiteralNode = {
    kind: "NumberLiteral";
    value: PeanoInt;
};
type TimesNode = {
    kind: "Times";
    left: ExpressionNode;
    right: ExpressionNode;
};
type PlusNode = {
    kind: "Plus";
    left: ExpressionNode;
    right: ExpressionNode;
};
type ExpressionNode = NumberLiteralNode | PlusNode | TimesNode;

type ParseResult = {
    node: ExpressionNode;
    tokens: Tokens;
};

type Prim<T extends Tokens> =
    T extends [LPToken, infer T2] ? (
        T2 extends Tokens ? Expr<T2>["tokens"] extends [RPToken, infer T3] ? T3 extends Tokens ? {
            node: Expr<T2>["node"];
            tokens: T3;
        } : never : never : never
    ) : T extends [infer H, infer R] ? (
        H extends NatToken ? R extends Tokens ? {
            node: { kind: "NumberLiteral", value: H["value"] };
            tokens: R;
        } : never : never
    ) : never;


type Mul<T extends Tokens, LHS = Prim<T>> = LHS extends ParseResult ? MulLoop<LHS> : never;
type MulLoop<PR extends ParseResult> = PR["tokens"] extends [infer H, infer R] ? H extends TimesToken ? R extends Tokens ? MulLoop<{
    node: { kind: "Times", left: PR["node"], right: Prim<R>["node"] };
    tokens: Prim<R>["tokens"],
}> : never : PR : PR;

type Expr<T extends Tokens, LHS = Mul<T>> = LHS extends ParseResult ? ExprLoop<LHS> : never;
type ExprLoop<PR extends ParseResult> = PR["tokens"] extends [infer H, infer R] ? H extends PlusToken ? R extends Tokens ? ExprLoop<{
    node: { kind: "Plus", left: PR["node"], right: Mul<R>["node"] };
    tokens: Mul<R>["tokens"];
}> : never : PR : PR;

type Parse<T extends Tokens, PR = Expr<T>> = PR extends ParseResult ? PR["node"] : never;

/* Evaluator */
type Evaluate<T extends ExpressionNode> =
    T extends NumberLiteralNode ? T["value"] :
    T extends PlusNode ? Evaluate<T["left"]> extends infer L ? Evaluate<T["right"]> extends infer R ? L extends PeanoInt ? R extends PeanoInt ? Add<L, R> : never : never : never : never :
    T extends TimesNode ? Evaluate<T["left"]> extends infer L ? Evaluate<T["right"]> extends infer R ? L extends PeanoInt ? R extends PeanoInt ? Multiply<L, R> : never : never : never : never :
    never;