@takker/parser
やったこと
classを捨てる
bundle size圧縮のため
4.1kBから3.2kBくらいには減らせた
inputをgenericに
v0.1.2時点だとまだうまくいっていないところがある
やりたいこと
inputに対応できる型を増やす
すぐ入力を受け取れないことがあるから、await pop(stream, length)みたいにlength以上取得するまで待機するような函数が必要
v0.1.2では、bread-n-butterと同様、the current parsing indexからstr文字列の長さだけsliceして等値比較している iteratorだとランダムアクセスできないので、これが不可
常に先頭がthe current parsing indexになるようにデータを保持する？
ただその前のデータを持たないと、choiceやorを評価できない
or(a, b)でaが失敗したとき、一旦aをparseする前の位置まで戻ってbを実行しないといけない
orやchoiceなど、一旦解析位置を戻さなければならないparser combinatorは、内部にbufferをもたせるようにしないとだめか
Contextにbufferも持たせればいい？
code:ts
type Context = [
Input, // rest sources
InternalSourceLocation, // the current parsing position
Input | undefined, // internal buffer for backtrack
]
いや、どのときにbufferを貯めるかを判定しないといけない
buffer自体ではなく、bufferに詰め込む函数を与えればいいか
code:ts
type Context = [
Input, // rest sources
InternalSourceLocation, // the current parsing position
((chunk: Input) => void | Promise<void>) | undefined
]
orやchoiceなど、消費した入力データを記憶しなければならないcombinatorを通る時、Context[2]にbufferへデータを送る函数を設定する
bufferはそれぞれのcombinatorで管理する
combinatorを抜けるとき、自分が管理しているbufferを廃棄する
一番最初に現れたcombinatorでbufferを管理する
例：const parser = or(or(a, b), c)
一番外側のor内部でbufferを作り、それへデータを入れる函数をContext[2]に格納する
内側のor(a, b)では、すでに外側のorで消費したデータを記憶しているため、bufferはつくらない
Context[2]がundefinedかどうかで判定可能
例：const parser = and(or(a, b), or(c, d))
or(a, b)を抜けた時にbufferを解放する
消費したデータを全て破棄する
or(c, d)でまた新たにbufferを作る
peekなど、スコープを抜けるときに廃棄できないパターンもあるか
(未実装)peek(p): pにマッチした時成功するが、文字を消費しない
とすると、internal bufferもContextにいれるべきか
peek()
bufferをContextに作って、成功したらそのままスコープを抜ける
or()
bufferをContextに作って、スコープを抜ける時bufferを消す
他のparserは、bufferがあるならそこに消費したデータを保存する
これだと他のparserでpeek()が作ったbufferかor()が作ったbufferか判定できないtakker.icon
やっぱりbufferに保存する函数save()を登録させるか
peek(p)
1. すでにsave()があればそれを一時変数に退避させる
pSave()とする
2. 新しいbufferとsave()を作り、save()をContextにわたす
3. pを実行
4. 成功したら、bufferをContext[0]に戻す
この処理をする仕組みを別途作る必要あり
元に戻すmethodを実装したobjectで入力をwrapすればいいか
5. 失敗したら、bufferをpSave()に渡して、失敗値を返す
pSave()がなければ、bufferをContext[0]に戻す
ok(p, q)
1. すでにsave()があればそれを一時変数に退避させる
pSave()とする
2. 新しいbufferとsave()を作り、save()をContextにわたす
3. pを実行
4. 成功したら、bufferをpSave()に渡して、成功値を返す
pSave()がなければ破棄する
これはp`までの解析結果が確定したことと同義
parse resultを逐次返却させたいときは、この確定のタイミングでそれまでのデータを返すようにすればいい
5. 失敗したら、bufferをContext[0]に戻す
6. qを実行
7. 成功したら、(以下4.と同じ)
8. 失敗したら、bufferをpSave()に渡して、失敗値を返す
pSave()がなければ、bufferをContext[0]に戻す
その他のparser
save()があれば、そこに消費したデータを保存する
なければそのまま破棄
「save()がない=親階層にor()やpeek()などのbacktrackingするparsers or combinatorsがいない」ということだから、破棄して問題ない この設計でとりあえずやってみるかtakker.icon
code:ts
interface Cursor<T> {
input: Iterator<T> | AsyncIterator<T>;
/** rewindを実行したときに受け取ったchunksを入れる */
buffer: T[];
index: number;
line: number;
column: number;
}
indexを動かす必要あり
popやrewindの内部で動かすか？
popのほうは、カーソルを動かしたものを新しく作って返せばいい
pop: (...) => [Iterable<T>, Cursor<T>]みたいなかんじ
const [iter, cursor] = pop(input, buffer, index, line, column, minSize)
rewindはcolumnやlineの元の値も与えなければ復元できない
これもconst rewindedCursor = rewind(input, buffer, index, line, column, chunks)みたいなかんじで新規作成すればいいか
Cursorのdesign
type Cursor<T> = [Iterator<T>, T[], number, number, number]とすればbundle sizeを節約できるかな
const [iter, newCursor] = pop(...cursor, minSize);やconst rewindedCursor = rewind(...cursor, chunks)とできる
code:ts
const rewind = <T>(cursor: Cursor<T>, chunks: T[]) => cursor.buffer.push(...chunks);
code:ts
// Iterable<T>だった場合
const pop = <T>(cursor: Cursor<T>, minSize: number): Iterable<T> => ({
let size = 0;
if (minSize <= 0) return;
while (cursor.buffer.length >0) {
const chunk = cursor.buffer.pop()!; // T = undefinedな場合も考慮して、pop()の返り値では個数判定しない
size += size(chunk);
yield chunk;
if (size > minSize) return;
}
for (const chunk of input) {
size += size(chunk);
yield chunk;
if (size > minSize) return;
}
}
});
const size = (chunk: unknown): number => "length" in chunk ? chunk.length : 1;
特殊化
BufferSourceが単独で渡されたときも特殊な処理にする
TypedArrayでthe current parsing positionに合わせたviewを作って渡す 効率化のために、メモリは消費させない
rev.1
code:ts
type SyncCursor<T> = readonly [
Iterator<T>;
/** rewindを実行したときに受け取ったchunksを入れる */
T[];
/** chunkの長さを数える函数
*
* T = ArrayLike<unknown>のときは(chunk) => chunk.lengthを渡す
*/
(chunk: T) => number;
[
number;
number;
/** 書記素単位で数えた列数, T = stringのときのみ */
number;
]
];
const rewind = <T>(...cursor: Cursor<T>, chunks: T[]): Cursor<T> => {
return cursor;
};
iteratorが進むごとにcursor位置も変わるため、都度Cursorを再作成して返す必要がある
code:ts
type Pop = <T>(...cursor: Cursor<T>, minSize: number) => Generator<T, Cursor<T>, void, unknown>; const pop: Pop =function*(input, buffer, size, initPos, minSize) {
if (minSize <= 0) return;
let size = 0;
while (buffer.length >0) {
// T = undefinedな場合も考慮して、pop()の返り値では個数判定しない
const chunk = buffer.pop()!;
size += size(chunk);
yield chunk;
if (size >= minSize) return;
}
for (const chunk of input) {
size += size(chunk);
yield chunk;
if (size >= minSize) return;
}
throw new Error("Lack of input data");
};
cusorの位置どうしようかなtakker.icon
size(chunk) !== 1だった時が問題
例えば長さ3のchunkを受け取り、長さ2まで消費したとしたら、残りの長さ1をrewindで返さないといけない
stringならsliceして終わり
Uint8Arrayの場合、sliceするとデータのコピーが発生するので、できれば避けたい
この場合は[new Uint8Array(chunk.buffer, 2, 1)]をrewindに渡せばいいか
columnは外そうかな
文字列の解析でしか使わない
うーん、ここまで状態の持ち回しが複雑だと、素直にclassで実装したほうが楽そうtakker.icon
popの挙動を型に応じて変えたい
rev.2
code:rev2.ts
interface Context<T, U extends Iterable<T>, Cursor> {
readonly pop: (size: number) => U;
readonly rewind: (chunks: T[], cursor: Cursor) => void;
readonly cursor: Cursor;
}
constructor(input: string) {
this.#input = input;
}
rewind = (chunks, cursor) => {
this.cursor.splice(0, 3, ...cursor);
this.#input = chunks.join("") + this.#input;
}
pop = (size) => {
const s = this.#input;
if (size <= 0 || s == "") return "";
const result = s.slice(0, size);
this.#input = s.slice(size);
index += result.length;
for (const char of result) {
if (char == "\n") {
line++;
column = 1;
} else {
column++;
}
}
this.cursor.splice(0, 3, index, line, column);
return result;
}
}
いやいや、コード大きすぎtakker.icon
やっぱり函数ベースにするか
popを型ごとに変えるのも、外部からpopを注入するようにすれば解決する
rev3
code:rev3.ts
type PlainContext<Data extends unknown[], Cursor> = [...Data, Cursor]; type Pop<Data extends unknown[], Cursor, U> = (
context: PlainContext<Data, Cursor>,
size: number,
type Rewind<Data extends unknown[], Cursor, T> = (
chunks: T[],
cursor: Cursor,
) => PlainContext<Data, Cursor>;
type IsFinish<Data extends unknown[], Cursor> = (
context: PlainContext<Data, Cursor>,
) => boolean;
type Context<Data extends unknown[], Cursor, T> = [
...PlainContext<Data, Cursor>,
Pop<Data, Cursor, T>,
Rewind<Data, Cursor, T>,
IsFinish<Data, Cursor>,
];
acessor
code:rev3.ts
const rest = <Data extends unknown[]>(
context: Context<Data, unknown, unknown> | PlainContext<Data, unknown>,
const cursor = <Data extends unknown[], Cursor, T>(
context: Context<Data, Cursor, T> | PlainContext<Data, Cursor>,
const pop = <Data extends unknown[], Cursor, T>(
context: Context<Data, Cursor, T>,
size: number,
};
const rewind = <Data extends unknown[], Cursor, T>(
context: Context<Data, Cursor, T>,
chunks: T[],
cursor: Cursor,
): Context<Data, Cursor, T> => {
const plain = rewind(data, chunks, cursor);
};
const isFinish = <Data extends unknown[], Cursor, T>(
context: Context<Data, Cursor, T>,
): boolean => {
};
こんな単純な形でなんとかなるのか？
まあものは試しか
text
code:rev3.ts
const defaultTextContext = (initInput: string): TextContext => [
(context, size) => {
let input], [index, line, column = context;
if (size <= 0 || input == "") return context;
const result = input.slice(0, size);
input = input.slice(size);
index += result.length;
for (const char of result) {
if (char == "\n") {
line++;
column = 1;
} else {
column++;
}
}
},
(context) => rest(context)0 == "", ];
Uint8Array
Cursorには初期のinput.byteOffsetからのoffsetを入れる
code:rev3.ts
type ByteContext = Context<Uint8Array, number, Uint8Array>; const defaultByteContext = (initInput: Uint8Array): ByteContext => {
const initOffset = initInput.byteOffset;
const initLength = initInput.length;
return [
0,
// 先頭からsize以下の長さのviewを作って返す
(context, size) => {
const [input, index] = context; size = Math.min(size, input.length);
const result = input.subarray(0, size);
const offset = input.byteOffset + size;
const next = new Uint8Array(input.buffer, offset, input.length - size);
return [result, next], index + size;
},
// 以前の位置にviewを戻す
index = Math.min(Math.max(index, 0), initLength);
return [
index,
];
},
(context) => rest(context)0.length == 0, ];
};
parser type
code:rev3.ts
type Parser<A, Data extends unknown[], Cursor, T> = (
context: Context<Data, Cursor, T>,
) => ActionResult<A, Data, Cursor, T>;
type ActionResult<A, Data extends unknown[], Cursor, T> =
| ActionOk<A, Data, Cursor, T>
| ActionFail<Data, Cursor, T>;
type ActionOk<A, Data extends unknown[], Cursor, T> = [
true,
A,
Context<Data, Cursor, T>,
];
type ActionFail<Data extends unknown[], Cursor, T> = [
false,
Context<Data, Cursor, T>,
string[],
];
parsers and combinators
code:rev3.ts
const text = <T extends string, S extends T, Data extends unknown[], Cursor>(
string: S,
): Parser<S, Data, Cursor, T> =>
(context) => {
if (sliced == string) {
}
const rewinded = rewind(next, sliced, cursor(context)); return [false, rewinded, string]; };
const and = <A, B, Data extends unknown[], Cursor, T>(
parserA: Parser<A, Data, Cursor, T>,
parserB: Parser<B, Data, Cursor, T>,
): Parser<A, B, Data, Cursor, T> => (context) => {
const a = parserA(context);
const valueA, nextA = a;
const b = parserB(nextA);
return [true, [valueA, b1], b2]; };
const ok = <A, Data extends unknown[], Cursor, T, U>(
value: A,
): Parser<A, Data, Cursor, T> =>
const chain = <A, B, Data extends unknown[], Cursor, T>(
parser: Parser<A, Data, Cursor, T>,
fn: (value: A) => Parser<B, Data, Cursor, T>,
): Parser<B, Data, Cursor, T> =>
(context) => {
const a = parser(context);
};
const map = <A, B, Data extends unknown[], Cursor, T>(
parser: Parser<A, Data, Cursor, T>,
fn: (value: A) => B,
): Parser<B, Data, Cursor, T> => chain(parser, (a) => ok(fn(a)));
const skip = <A, B, Data extends unknown[], Cursor, T>(
parserA: Parser<A, Data, Cursor, T>,
parserB: Parser<B, Data, Cursor, T>,
): Parser<A, Data, Cursor, T> => map(and(parserA, parserB), (a) => a); const eof = <Data extends unknown[], Cursor, T>(
context: Context<Data, Cursor, T>,
): ActionResult<"<EOF>", Data, Cursor, T> =>
const parse = <A, Data extends unknown[], Cursor, T>(
parser: Parser<A, Data, Cursor, T>,
context: Context<Data, Cursor, T>,
) => {
const result = skip(parser, eof)(context);
return { ok: true, value: result1 }; }
return {
ok: false,
location: cursor(result1), };
};
test
code:rev3.ts
type TextParser<A> = Parser<
A,
string
;
const hello: TextParser<"hello"> = text("hello");
const world: TextParser<"world"> = text("world");
console.log(parse(and(hello, world), defaultTextContext("helloworld")));
console.log(parse(and(hello, world), defaultTextContext("hello world")));
20:06:32 型チェックは通った
実行して期待通りの値もでた
まあ簡単な条件しか試してないけど
rev4
戻し方
任意位置に戻れる必要はない。むしろバグる
不正な位置を渡される
不正なchunkを渡される
あらかじめ戻る位置、リスボーン地点を登録させる
rewindを呼び出すと、最後に登録した地点まで巻き戻る
複数の地点をstackで保存することで、入れ子のorなどを表現できる
データ
Dataを配列で指定する必要はない
任意の型を使えるようにする
parser側では、データの詳細は知らなくていい
popやrewindにしかアクセスしないから
reader
DataやCursorを操作する純粋函数をまとめたもの
inputとは無関係に作成させる
popやrewindの作成時にinputに依存させると純粋でなくなる
cursor
これもDataに含める
どう管理するかはreaderに任せる
parser
入力はDataとReader
出力はparse正否、parseして作った値、残りのData
Readerは返却不要
parserで書き換えられるのを防ぐ
Readerの函数
pop
mark
backtrackingの開始&位置登録
名前は検討中
backtracking周りでいい感じの用語ないかな
rewind
markで記録したcursorでの状態まで巻き戻す
location
DataからCursorを取り出す
init
inputを受け取って初期Dataを作る
たとえば、文字列を受け取って、文字列と初期のcursor位置を含んだobjectを作るなど
isFinish
データ末尾までparseし終えたらtrue
format
cursorを文字列に変換する
debug用
うーん、やっぱりclassのほうがすっきりするような……
でも函数を一個ずつ指定させたほうが、純粋性を保てるか
<...>にいれる型定義が膨大で見にくいtakker.icon
型を取り出すときは、適宜型函数を使って取り出す
code:type.ts
interface TextRecorderMapping{
new: (input: Input<TextRecorder>) => State<TextRecorder>;
pop: (state: State<TextRecorder>, size: number) => [Data<TextRecorder>, State<TextRecorder>;
save: (state: State<TextRecorder>) => State<TextRecorder>;
discard: (state: State<TextRecorder>) => State<TextRecorder>;
restore: (state: State<TextRecorder>) => State<TextRecorder>;
isFinish: (state: State<TextRecorder>) => State<TextRecorder>;
parseState: [Data<TextRecorder>, Pointer<TextRecorder>, Pointer<TextRecorder>[]]
data: string;
// 内部で使う位置データ
location: L; // must extend Location
input: string;
}
type Input<R> = R extends { input: infer I } ? I : never;
type State<R> = R extends { parseState: infer S } ? S : never;
type Pointer<R> = R extends { pointer: infer P } ? P : never;
// Parserの入力
type ParseInput<...> = ...
// Parserの出力
type ParseOutput<...> = ...
// 最上位のParserの出力
// human-readableなobjectにして結果を取り出すときに使う
type ParseResult<...> = ...
interface Location {
/** 1 based */
line?: number;
/* 1 based */
column?: number;
/** 0 based */
offset: number;
}
型をobjctで持たせてeasily documentedにしつつ、実態は配列にしてproperty nameを節約する & Readonly<T>制約をかける