From e9f3c782bc10d4c5c44faf768aa60cd6bcc66574 Mon Sep 17 00:00:00 2001 From: Kai Stevenson Date: Sun, 2 Nov 2025 18:08:16 -0800 Subject: refactor --- src/lang/core/common.ts | 57 +++++++++++++ src/lang/core/eval.ts | 42 +++++++++ src/lang/core/index.ts | 0 src/lang/core/lexer.ts | 62 ++++++++++++++ src/lang/core/parser.ts | 220 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 381 insertions(+) create mode 100644 src/lang/core/common.ts create mode 100644 src/lang/core/eval.ts create mode 100644 src/lang/core/index.ts create mode 100644 src/lang/core/lexer.ts create mode 100644 src/lang/core/parser.ts (limited to 'src/lang/core') diff --git a/src/lang/core/common.ts b/src/lang/core/common.ts new file mode 100644 index 0000000..c1a1dc3 --- /dev/null +++ b/src/lang/core/common.ts @@ -0,0 +1,57 @@ +export enum TokenType { + OPEN_PAREN = "(", + CLOSE_PAREN = ")", + SPACE = " ", + SEMICOLON = ";", + COMMA = ",", + NAME = "NAME", +} + +export enum TokenSubType { + NA = "NA", + LITERAL = "LITERAL", + REFERENCE = "REFERENCE", +} + +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 { + INT = "INT", + EXT = "EXT", + PARSER_ERROR = "PARSER_ERROR", +} + +export type ASTNode< + Type extends NodeType = NodeType, + Name extends string = string, + Value extends any = any, + Children extends readonly ASTNode[] = readonly ASTNode< + NodeType, + string, + any, + any + >[] +> = { + type: Type; + name: Name; + value: Value; + children: Children; +}; + +export type ParserCtx = { + remainingTokens: readonly Token[]; + lastToken: Token | null; + stack: readonly ASTNode[]; +}; diff --git a/src/lang/core/eval.ts b/src/lang/core/eval.ts new file mode 100644 index 0000000..6a25a6c --- /dev/null +++ b/src/lang/core/eval.ts @@ -0,0 +1,42 @@ +import { + BUILTIN_Add, + BUILTIN_Arr, + BUILTIN_Mul, + BUILTIN_ToString, +} from "../builtin"; +import { ASTNode, NodeType } from "./common"; +import { Lex } from "./lexer"; +import { Parse } from "./parser"; + +export type SENTINEL_NO_BUILTIN = "__NO_BUILTIN__"; +export type MapBuiltins = + Node["children"] extends infer Children extends readonly ASTNode[] + ? { + [Idx in keyof Children]: Children[Idx] extends ASTNode + ? Evaluate + : never; + } extends infer Args extends readonly any[] + ? Node["name"] extends "tostring" + ? BUILTIN_ToString + : Node["name"] extends "arr" + ? BUILTIN_Arr + : Node["name"] extends "add" + ? BUILTIN_Add + : Node["name"] extends "mul" + ? BUILTIN_Mul + : SENTINEL_NO_BUILTIN + : never + : never; + +export type EvalError = `Eval error: ${T}`; + +export type Evaluate = Node["type"] extends NodeType.INT + ? Node["value"] + : Node["type"] extends NodeType.EXT + ? MapBuiltins + : EvalError<`Unhandled node type ${Node["type"]}`>; + +const input = `` as const; +const lex_result = null as unknown as Lex; +const parse_result = null as unknown as Parse; +const eval_result = null as unknown as Evaluate; diff --git a/src/lang/core/index.ts b/src/lang/core/index.ts new file mode 100644 index 0000000..e69de29 diff --git a/src/lang/core/lexer.ts b/src/lang/core/lexer.ts new file mode 100644 index 0000000..33a408a --- /dev/null +++ b/src/lang/core/lexer.ts @@ -0,0 +1,62 @@ +import { LexerCtx, Token, TokenSubType, 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< + Ctx extends LexerCtx, + Tail extends string, + _Token extends Token | null +> = { + next: Tail; + nameCollection: ""; + tokens: _Token extends null + ? [ + ...Ctx["tokens"], + ...(Ctx["nameCollection"] extends "" + ? [] + : [Token]) + ] + : [ + ...Ctx["tokens"], + ...(Ctx["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["tokens"]; + +export type Lex = _Lex<{ + next: `${Raw};`; + tokens: []; + nameCollection: ""; +}>; diff --git a/src/lang/core/parser.ts b/src/lang/core/parser.ts new file mode 100644 index 0000000..79218e9 --- /dev/null +++ b/src/lang/core/parser.ts @@ -0,0 +1,220 @@ +import { + ASTNode, + NodeType, + ParserCtx, + Token, + TokenSubType, + TokenType, +} from "./common"; +import { 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< + NodeType.PARSER_ERROR, + "Error", + T, + [] +>; + +export type PushChild = { + type: Node["type"]; + value: Node["value"]; + 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; + +type NULL_SENTINEL = { + NULL: true; +}; + +export type ParseNumberLiteral = + T extends `${infer Inner extends number}` ? Inner : NULL_SENTINEL; + +export type ParseStringLiteral = + T extends `"${infer Inner extends string}"` ? Inner : NULL_SENTINEL; + +export type ResolveNodeFromToken<_Token extends Token> = ParseNumberLiteral< + _Token["name"] +> extends number + ? ASTNode, []> + : ParseStringLiteral<_Token["name"]> extends string + ? ASTNode, []> + : ASTNode; + +export type _Parse = Ctx["remainingTokens"] extends [ + infer Head extends Token, + ...infer Tail extends readonly Token[] +] + ? Ctx["lastToken"] extends Token + ? Head["type"] extends TokenType.NAME + ? // we already have a lastName + // mutate last element of stack to push lastName as child + // lastName = nextToken + // goto start + _Parse<{ + lastToken: Head; + remainingTokens: Tail; + stack: PushChildToLastElementOfStack< + Ctx["stack"], + ResolveNodeFromToken + >; + }> + : //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<{ + lastToken: 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, + ResolveNodeFromToken + > + > + >; + }> + : Head["type"] extends TokenType.OPEN_PAREN + ? // push lastName onto stack + // goto start + _Parse<{ + lastToken: null; + remainingTokens: Tail; + stack: [...Ctx["stack"], ResolveNodeFromToken]; + }> + : Ctx & Error<`Was not expecting ${Head["type"]}`> + : // expect nextToken to be a name or close paren + Head["type"] extends TokenType.NAME + ? // lastName = nextToken + // goto start + _Parse<{ + lastToken: Head; + remainingTokens: Tail; + stack: Ctx["stack"]; + }> + : Head["type"] extends TokenType.CLOSE_PAREN + ? _Parse<{ + lastToken: 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["lastToken"] extends Token + ? // case where we ended with a name + _Parse<{ + lastToken: null; + remainingTokens: []; + stack: PushChildToLastElementOfStack< + Ctx["stack"], + ResolveNodeFromToken + >; + }> + : Ctx["stack"][0]; + +export type Parse = _Parse<{ + lastToken: null; + remainingTokens: Raw; + stack: [ASTNode]; +}>; + +const test_result = null as unknown as Parse>; -- cgit v1.2.3-70-g09d2