完成品
モチベーション
- 深夜のノリ
- 初めて字句解析、構文解析したので忘れないように
全体的な流れ
- 字句解析
- 構文解析
字句解析
トークン定義
各種トークンを定義します。
論理値、文字列、数値はジェネリクスを使って値も持っておけるようにします
type LeftBraceToken = { kind: "left-brace" };
type RightBraceToken = { kind: "right-brace" };
type LeftBracketToken = { kind: "left-bracket" };
type RightBracketToken = { kind: "right-bracket" };
type CommaToken = { kind: "comma" };
type ColonToken = { kind: "colon" };
type NullToken = { kind: "null" };
type BooleanToken<T extends boolean> = { kind: "boolean"; value: T };
type StringToken<T extends string> = { kind: "string"; value: T };
type NumberToken<T extends number> = { kind: "number"; value: T };
type Token =
| LeftBraceToken
| RightBraceToken
| LeftBracketToken
| RightBracketToken
| CommaToken
| ColonToken
| NullToken
| BooleanToken<boolean>
| StringToken<string>
| NumberToken<number>;
トークナイザー
トークナイザーの基本的な形は以下の通りです。
左側に出てきたトークンを Tokens に詰めて、再帰的に呼び出し、空文字列になるまで続けます。
空文字列になったら Tokens を返します
いずれのトークンにもマッチしなかったら never を返すことで失敗を表現します
type Tokenize<T extends string, Tokens extends Token[] = []> =
T extends '' ? Tokens
: T extends `トークン1${infer Rest}` ? Tokenize<Rest, [...Tokens, トークン1]>
: T extends `トークン2${infer Rest}` ? Tokenize<Rest, [...Tokens, トークン2]>
: never
例えば LeftBraceToken 、 RightBraceToken の場合はこんな感じです。
type Tokenize<T extends string, Tokens extends Token[] = []> =
T extends '' ? Tokens
+ : T extends `{${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBraceToken]>
+ : T extends `}${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBraceToken]>
: never
type Tokenized = Tokenize<'{}'>
// ^? [LeftBraceToken, RightBraceToken]
LeftBraceToken 、 RightBraceToken 、 LeftBracketToken 、 RightBracketToken 、 CommaToken 、 ColonToken 、 NullToken まではこの方法でトークナイズできます
空白文字
JSON では空白文字は特に意味を持たないので今回は無視することにします。
+ type WhiteSpace = ' ' | '\t' | '\n' | '\r'
type Tokenize<T extends string, Tokens extends Token[] = []> =
T extends '' ? Tokens
+ : T extends `${WhiteSpace}${infer Rest}` ? Tokenize<Rest, Tokens>
: T extends `{${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBraceToken]>
: T extends `}${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBraceToken]>
: T extends `[${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBracketToken]>
: T extends `]${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBracketToken]>
: T extends `,${infer Rest}` ? Tokenize<Rest, [...Tokens, CommaToken]>
: T extends `:${infer Rest}` ? Tokenize<Rest, [...Tokens, ColonToken]>
: T extends `null${infer Rest}` ? Tokenize<Rest, [...Tokens, NullToken]>
: never
論理値
論理値は BooleanToken<T> にそれぞれ値を詰めてあげます。
true の場合は BooleanToken<true>
false の場合は BooleanToken<false>
type Tokenize<T extends string, Tokens extends Token[] = []> =
T extends '' ? Tokens
: T extends `${WhiteSpace}${infer Rest}` ? Tokenize<Rest, Tokens>
: T extends `{${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBraceToken]>
: T extends `}${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBraceToken]>
: T extends `[${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBracketToken]>
: T extends `]${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBracketToken]>
: T extends `,${infer Rest}` ? Tokenize<Rest, [...Tokens, CommaToken]>
: T extends `:${infer Rest}` ? Tokenize<Rest, [...Tokens, ColonToken]>
: T extends `null${infer Rest}` ? Tokenize<Rest, [...Tokens, NullToken]>
+ : T extends `true${infer Rest}` ? Tokenize<Rest, [...Tokens, BooleanToken<true>]>
+ : T extends `false${infer Rest}` ? Tokenize<Rest, [...Tokens, BooleanToken<false>]>
: never
文字列
エスケープされた " があると "${infer Value extends string}"${string} で正しく判定できないので、別な手段を使います
type Tokenized = '"aa\\"a"' extends `"${infer Value extends string}"${string}` ? Value : never
// ^? "aa\\"
見つけた値を持っておく Value と状態を保持しておく IsStarted を使って、与えられた文字列の左側にある文字列を取ってきます。
成功した場合は、見つけた値と残りの文字列をタプルで返します。
失敗した場合は、never を返します。
状態遷移は以下の通りです。
type TryParseString<T extends string, Value extends string = '', IsStarted extends boolean = false> =
[IsStarted, T] extends [false, `"${infer Rest}`] ? TryParseString<Rest, Value, true>
: [IsStarted, T] extends [true, `"${infer Rest}`] ? [Value, Rest]
: [IsStarted, T] extends [true, `\\"${infer Rest}`] ? TryParseString<Rest, `${Value}\"`, IsStarted>
: [IsStarted, T] extends [true, `${infer Char}${infer Rest}`] ? TryParseString<Rest, `${Value}${Char}`, IsStarted>
: never
タプルをうまく使って T が "${string} に型推論できて、かつ TryParseString<T> が文字列の値と残りの文字列に型推論できたら、トークン列に追加するようにします。
type Tokenize<T extends string, Tokens extends Token[] = []> =
T extends '' ? Tokens
: T extends `${WhiteSpace}${infer Rest}` ? Tokenize<Rest, Tokens>
: T extends `{${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBraceToken]>
: T extends `}${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBraceToken]>
: T extends `[${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBracketToken]>
: T extends `]${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBracketToken]>
: T extends `,${infer Rest}` ? Tokenize<Rest, [...Tokens, CommaToken]>
: T extends `:${infer Rest}` ? Tokenize<Rest, [...Tokens, ColonToken]>
: T extends `null${infer Rest}` ? Tokenize<Rest, [...Tokens, NullToken]>
: T extends `true${infer Rest}` ? Tokenize<Rest, [...Tokens, BooleanToken<true>]>
: T extends `false${infer Rest}` ? Tokenize<Rest, [...Tokens, BooleanToken<false>]>
+ : [T, TryParseString<T>] extends [`"${string}`, [infer Value extends string, infer Rest extends string]] ? Tokenize<Rest, [...Tokens, StringToken<Value>]>
: never
数値
数値も文字列と同じようなことをします。
見つけた値を持っておく Value と状態を保持しておく HasFlotingPoint を使って、与えられた文字列の左側にある数値を取ってきます。
成功した場合は、見つけた値と残りの文字列をタプルで返します。
失敗した場合は、never を返します。
状態遷移は以下の通りです。
type TryParseNumber<T extends string, Value extends string = '', HasFlotingPoint extends boolean = false> =
[Value, T] extends ['', `-${infer Rest}`] ? TryParseNumber<Rest, '-'>
: [Value, HasFlotingPoint, T] extends [`${number}`, false, `.${infer D extends number}${infer Rest}`] ? TryParseNumber<Rest, `${Value}.${D}`>
: T extends `${infer D extends number}${infer Rest}` ? TryParseNumber<Rest, `${Value}${D}`>
: Value extends `-0` ? [0, T]
: Value extends `${infer Value extends number}` ? [Value, T]
: never
最後に -0 の場合は 0 として、値が number に型推論できたら返します。
値が空文字列や - のみのときは never を返します。
今回はマイナス符号と浮動小数点数のみサポートしました。
自然対数もサポートする場合はもう少し改良が必要です。
type Tokenize<T extends string, Tokens extends Token[] = []> =
T extends '' ? Tokens
: T extends `${WhiteSpace}${infer Rest}` ? Tokenize<Rest, Tokens>
: T extends `{${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBraceToken]>
: T extends `}${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBraceToken]>
: T extends `[${infer Rest}` ? Tokenize<Rest, [...Tokens, LeftBracketToken]>
: T extends `]${infer Rest}` ? Tokenize<Rest, [...Tokens, RightBracketToken]>
: T extends `,${infer Rest}` ? Tokenize<Rest, [...Tokens, CommaToken]>
: T extends `:${infer Rest}` ? Tokenize<Rest, [...Tokens, ColonToken]>
: T extends `null${infer Rest}` ? Tokenize<Rest, [...Tokens, NullToken]>
: T extends `true${infer Rest}` ? Tokenize<Rest, [...Tokens, BooleanToken<true>]>
: T extends `false${infer Rest}` ? Tokenize<Rest, [...Tokens, BooleanToken<false>]>
: [T, ParseLeftString<T>] extends [`"${string}`, [infer Value extends string, infer Rest extends string]] ? Tokenize<Rest, [...Tokens, StringToken<Value>]>
+ : TryParseNumber<T> extends never ? never
+ : TryParseNumber<T> extends [infer Value extends number, infer Rest extends string] ? Tokenize<Rest, [...Tokens, NumberToken<Value>]>
: never
今回は雑に TryParseNumber<T> が never に推論されたとき、never を返すようにしました。
下の方なので問題ないですが、本当だったら T の左側に - か 0 ~ 9 のいずれかがあるときのみ TryParseNumber<T> をしたほうがよいです。
構文解析
構文解析器の基本的な形は以下のとおりです。
Tokens[] を受け取って、解析済みの値と残りのトークン列のタプルを返します。
type ValueParse<T extends Token[]> =
T extends [トークン1, ...infer Rest] ? [値1, Rest]
: T extends [トークン2, ...infer Rest] ? [値2, Rest]
: never
プリミティブ型は以下のように書けます。
type ValueParse<T extends Token[]> =
+ T extends [NullToken, ...infer Rest] ? [null, Rest]
+ : T extends [BooleanToken<infer Value>, ...infer Rest] ? [Value, Rest]
+ : T extends [StringToken<infer Value>, ...infer Rest] ? [Value, Rest]
+ : T extends [NumberToken<infer Value>, ...infer Rest] ? [Value, Rest]
: never
配列型
トークン配列を受け取り、解析済みの値を持つ Values と状態の State を使って構文解析します。
成功した場合は、配列の値と残りのトークン列を返します。
失敗した場合は、never を返します。
type ArrayParseState = 'expect-start'|'start'|'value'|'comma'
type ArrayParse<T extends Token[], Values extends unknown[] = [], State extends ArrayParseState = 'expect-start'> =
[State, T] extends ['expect-start', [{ kind: 'left-bracket' }, ...infer Rest extends Token[]]] ? ArrayParse<Rest, [], 'start'>
: [State, T] extends ['start'|'value', [RightBracketToken, ...infer Rest extends Token[]]] ? [Values, Rest]
: [State, ValueParse<T>] extends ['start'|'comma', [infer U, infer Rest extends Token[]]] ? ArrayParse<Rest, [...Values, U], 'value'>
: [State, T] extends ['value', [CommaToken, ...infer Rest extends Token[]]] ? ArrayParse<Rest, Values, 'comma'>
: never
type ValueParse<T extends Token[]> =
T extends [NullToken, ...infer Rest] ? [null, Rest]
: T extends [BooleanToken<infer Value>, ...infer Rest] ? [Value, Rest]
: T extends [StringToken<infer Value>, ...infer Rest] ? [Value, Rest]
: T extends [NumberToken<infer Value>, ...infer Rest] ? [Value, Rest]
+ : T extends [LeftBracketToken, ...Token[]] ? ArrayParse<T>
: never
オブジェクト型
配列型と同じように構文解析します。
オブジェクトのキーが見つかった状態は {key: string} として、キー名を持っておけるようにします
type ObjectParseState = 'expect-start'|'start'|{key: string}|'value'|'comma'
type ObjectParse<T extends Token[], Value extends {} = {}, State extends ObjectParseState = 'expect-start'> =
[State, T] extends ['expect-start', [LeftBraceToken, ...infer Rest extends Token[]]] ? ObjectParse<Rest, {}, 'start'>
: [State, T] extends ['start'|'value', [RightBraceToken, ...infer Rest extends Token[]]] ? [Prettify<Value>, Rest]
: [State, T] extends ['start'|'comma', [StringToken<infer Key>, ColonToken, ...infer Rest extends Token[]]] ? ObjectParse<Rest, Value, {key: Key}>
: [State, ValueParse<T>] extends [{key: string}, never] ? never
: [State, ValueParse<T>] extends [{key: infer Key extends string}, [infer U, infer Rest extends Token[]]] ? ObjectParse<Rest, Value & {[key in Key]: U}, 'value'>
: [State, T] extends ['value', [CommaToken, ...infer Rest extends Token[]]] ? ObjectParse<Rest, Value, 'comma'>
: never
構文解析できたオブジェクトは Prettify<T> を通すことでオブジェクトの交差型から一つのオブジェクトにまとめます
type Prettify<T extends {}> = {
[K in keyof T]: T[K];
} & {}
type ValueParse<T extends Token[]> =
T extends [NullToken, ...infer Rest] ? [null, Rest]
: T extends [BooleanToken<infer Value>, ...infer Rest] ? [Value, Rest]
: T extends [StringToken<infer Value>, ...infer Rest] ? [Value, Rest]
: T extends [NumberToken<infer Value>, ...infer Rest] ? [Value, Rest]
: T extends [LeftBracketToken, ...Token[]] ? ArrayParse<T>
+ : T extends [LeftBraceToken, ...Token[]] ? ObjectParse<T>
: never
最終結果
type JsonParse<T extends string> =
Tokenize<T> extends infer Tokens extends Token[]
? ValueParse<Tokens> extends never ? never
: ValueParse<Tokens> extends [infer Parsed, []] ? Parsed : never
: never
まず字句解析を行い、その後構文解析を行います。
構文解析の結果、残りのトークン列が空配列になったら構文解析完了とします。