From 8896b33a652563d90cb211a85dd2f7213f42e5d1 Mon Sep 17 00:00:00 2001 From: Kai Stevenson Date: Tue, 28 Oct 2025 22:49:46 -0700 Subject: parse, lex works --- src/lib/core/common.ts | 45 +++++++++++ src/lib/core/index.ts | 0 src/lib/core/lexer.ts | 64 +++++++++++++++ src/lib/core/parser.ts | 212 +++++++++++++++++++++++++++++++++++++++++++++++++ src/lib/core/repl.ts | 3 + 5 files changed, 324 insertions(+) create mode 100644 src/lib/core/common.ts create mode 100644 src/lib/core/index.ts create mode 100644 src/lib/core/lexer.ts create mode 100644 src/lib/core/parser.ts create mode 100644 src/lib/core/repl.ts (limited to 'src/lib/core') diff --git a/src/lib/core/common.ts b/src/lib/core/common.ts new file mode 100644 index 0000000..1283000 --- /dev/null +++ b/src/lib/core/common.ts @@ -0,0 +1,45 @@ +export enum TokenType { + OPEN_PAREN = "(", + CLOSE_PAREN = ")", + SPACE = " ", + SEMICOLON = ";", + COMMA = ",", + UNIQUE_SYMBOL = "UNIQUE_SYMBOL", +} + +export type Token< + Type extends TokenType = TokenType, + Name extends string = string +> = { + type: Type; + name: Name; +}; + +export type LexerCtx = { + next: string; + nameCollection: string; + tokens: readonly Token[]; +}; + +export enum NodeType { + ROOT = "ROOT", + LITERAL = "LITERAL", + CALL = "CALL", + PARSER_ERROR = "PARSER_ERROR", +} + +export type ASTNode< + Type extends NodeType = NodeType, + Name extends string = string, + Children extends ASTNode[] = ASTNode[] +> = { + type: Type; + name: Name; + children: Children; +}; + +export type ParserCtx = { + remainingTokens: readonly Token[]; + lastName: string | null; + stack: readonly ASTNode[]; +}; diff --git a/src/lib/core/index.ts b/src/lib/core/index.ts new file mode 100644 index 0000000..e69de29 diff --git a/src/lib/core/lexer.ts b/src/lib/core/lexer.ts new file mode 100644 index 0000000..3315fb2 --- /dev/null +++ b/src/lib/core/lexer.ts @@ -0,0 +1,64 @@ +import { LexerCtx, Token, TokenType } from "./common"; + +export type BreakingToken = + | TokenType.OPEN_PAREN + | TokenType.CLOSE_PAREN + | TokenType.COMMA + | TokenType.SEMICOLON + | TokenType.SPACE; + +export type IsWhitespace = T extends `${TokenType.SPACE}` + ? true + : T extends `${TokenType.COMMA}` + ? true + : T extends `${TokenType.SEMICOLON}` + ? true + : false; + +export type ProcessNameCollection< + Cur extends LexerCtx, + Tail extends string, + _Token extends Token | null +> = { + next: Tail; + nameCollection: ""; + tokens: _Token extends null + ? [ + ...Cur["tokens"], + ...(Cur["nameCollection"] extends "" + ? [] + : [Token]) + ] + : [ + ...Cur["tokens"], + ...(Cur["nameCollection"] extends "" + ? [_Token] + : [Token, _Token]) + ]; +}; + +export type IsOpen = T extends `${TokenType.OPEN_PAREN}` ? true : false; +export type IsClose = T extends `${TokenType.CLOSE_PAREN}` ? true : false; + +export type _Lex = + Ctx["next"] extends `${infer Head}${infer Tail}` + ? IsWhitespace extends true + ? _Lex> + : IsOpen extends true + ? _Lex>> + : IsClose extends true + ? _Lex>> + : _Lex<{ + next: Tail; + nameCollection: `${Ctx["nameCollection"]}${Head}`; + tokens: Ctx["tokens"]; + }> + : // : Ctx["next"] extends `${infer Head}` + // ? _Lex<{ next: Head; tokens: Ctx["tokens"] }> + Ctx["tokens"]; + +export type Lex = _Lex<{ + next: `${Raw};`; + tokens: []; + nameCollection: ""; +}>; diff --git a/src/lib/core/parser.ts b/src/lib/core/parser.ts new file mode 100644 index 0000000..fbbbdc2 --- /dev/null +++ b/src/lib/core/parser.ts @@ -0,0 +1,212 @@ +import { ASTNode, NodeType, ParserCtx, Token, TokenType } from "./common"; +import { IsWhitespace, Lex } from "./lexer"; + +/* +start +if no 'lastName' +then: + expect nextToken to be a name + lastName = nextToken + goto start + +else: + if nextToken is name + then: + // we already have a lastName + mutate last element of stack to push lastName as child + lastName = nextToken + goto start + + else: + //nextToken is openParen or close paren + if nextToken is closeParen + then: + set last element of stack as child of prev element on stack + pop stack + // [stack[last - 1].children.push(stack.pop) + goto start + else if nextToken is openParen: + push lastName onto stack + goto start + + +finally: + // only one element remains on the stack + return stack[0] + + + CALL ( param, CALL2 ( param2 ) ) + + param2 ret call2 param ret call + + | call + |-- param + |-- | call2 + |-- param2 + + */ + +export type Error = ASTNode; + +export type PushChild = { + type: Node["type"]; + name: Node["name"]; + children: [...Node["children"], Child]; +}; + +export type PushChildToLastElementOfStack< + Stack extends ParserCtx["stack"], + Child extends ASTNode +> = Stack extends [...infer Head, infer Tail extends ASTNode] + ? [...Head, PushChild] + : Stack extends [infer Only extends ASTNode] + ? [PushChild] + : never; + +export type PushChildToSecondLastElementOfStack< + Stack extends ParserCtx["stack"], + Child extends ASTNode +> = Stack extends [ + ...infer Head, + infer Tail extends ASTNode, + infer Final extends ASTNode +] + ? [...Head, PushChild, Final] + : Stack extends [infer Only extends ASTNode, infer Final extends ASTNode] + ? [PushChild, Final] + : never; + +export type GetLastOnStack = Stack extends [ + ...infer Head, + infer Tail extends ASTNode +] + ? Tail + : Stack extends [infer Only extends ASTNode] + ? Only + : never; + +export type StackWithoutLast = Stack extends [ + ...infer Head extends ASTNode[], + infer Tail +] + ? [...Head] + : Stack extends [infer Only extends ASTNode] + ? [] + : never; + +export type _Parse = Ctx["remainingTokens"] extends [ + infer Head extends Token, + ...infer Tail extends readonly Token[] +] + ? Ctx["lastName"] extends string + ? Head["type"] extends TokenType.UNIQUE_SYMBOL + ? // we already have a lastName + // mutate last element of stack to push lastName as child + // lastName = nextToken + // goto start + _Parse<{ + lastName: Head["name"]; + remainingTokens: Tail; + stack: PushChildToLastElementOfStack< + Ctx["stack"], + ASTNode + >; + }> + : //nextToken is openParen or close paren + Head["type"] extends TokenType.CLOSE_PAREN + ? // handle lastName + // set last element of stack as child of prev element on stack + // pop stack + // [stack[last - 1].children.push(stack.pop) + // goto start + _Parse<{ + lastName: null; + remainingTokens: Tail; + // first push the last name onto the children of the top + // then push the top onto the children of the next + // then remove the top + stack: StackWithoutLast< + PushChildToSecondLastElementOfStack< + Ctx["stack"], + PushChild< + GetLastOnStack, + ASTNode + > + > + >; + }> + : Head["type"] extends TokenType.OPEN_PAREN + ? // push lastName onto stack + // goto start + _Parse<{ + lastName: null; + remainingTokens: Tail; + stack: [...Ctx["stack"], ASTNode]; + }> + : Ctx & Error<`Was not expecting ${Head["type"]}`> + : // expect nextToken to be a name or close paren + Head["type"] extends TokenType.UNIQUE_SYMBOL + ? // lastName = nextToken + // goto start + _Parse<{ + lastName: Head["name"]; + remainingTokens: Tail; + stack: Ctx["stack"]; + }> + : Head["type"] extends TokenType.CLOSE_PAREN + ? _Parse<{ + lastName: null; + remainingTokens: Tail; + // push the top onto the children of the next + // then remove the top + stack: StackWithoutLast< + PushChildToSecondLastElementOfStack< + Ctx["stack"], + GetLastOnStack + > + >; + }> + : Ctx & + Error<`Expected nextToken to be a name or close paren at ${Head["type"]}`> + : Ctx["stack"]; + +// v1 +// ? Ctx["isCollecting"] extends true +// ? Head["type"] extends TokenType.CLOSE_PAREN +// ? "return" +// : Head["type"] extends TokenType.UNIQUE_SYMBOL +// ? _Parse<{ +// remainingTokens: Tail; +// isCollecting: true; +// name: Ctx["name"]; +// // fuck, how to do this without advancing seek pointer?? +// ret: [...Ctx["ret"], ASTNode; +// }> +// : Error<"Expected another name, or `)`"> +// : Head["type"] extends TokenType.OPEN_PAREN +// ? _Parse<{ +// remainingTokens: Tail; +// isCollecting: true; +// name: Ctx["name"]; +// ret: Ctx["ret"]; +// }> +// : Error<"Expected open paren"> +// : Ctx["ret"]; + +//v2 +// ? Ctx["previousName"] extends null +// ? Head["type"] extends TokenType.UNIQUE_SYMBOL +// ? _Parse<{ remainingTokens: Tail; previousName: Head; node: Ctx["node"] }> +// : ASTNode +// : IsWhitespace<`${Head["type"]}`> extends true +// ? ASTNode +// : ASTNode +// : Ctx["node"]; + +export type Parse = _Parse<{ + lastName: null; + remainingTokens: Raw; + stack: [ASTNode]; +}>; + +const a = "a" as any as Parse>; diff --git a/src/lib/core/repl.ts b/src/lib/core/repl.ts new file mode 100644 index 0000000..5235a64 --- /dev/null +++ b/src/lib/core/repl.ts @@ -0,0 +1,3 @@ +import { ASTNode } from "./common"; + +export type Evaluate = "Not implemented"; -- cgit v1.2.3-70-g09d2