summaryrefslogtreecommitdiff
path: root/src/lang
diff options
context:
space:
mode:
Diffstat (limited to 'src/lang')
-rw-r--r--src/lang/builtin/index.ts34
-rw-r--r--src/lang/core/common.ts57
-rw-r--r--src/lang/core/eval.ts42
-rw-r--r--src/lang/core/index.ts0
-rw-r--r--src/lang/core/lexer.ts62
-rw-r--r--src/lang/core/parser.ts220
-rw-r--r--src/lang/index.ts1
-rw-r--r--src/lang/util/index.ts3
-rw-r--r--src/lang/util/number.ts34
-rw-r--r--src/lang/util/string.ts17
-rw-r--r--src/lang/util/utils.ts8
11 files changed, 478 insertions, 0 deletions
diff --git a/src/lang/builtin/index.ts b/src/lang/builtin/index.ts
new file mode 100644
index 0000000..373f54a
--- /dev/null
+++ b/src/lang/builtin/index.ts
@@ -0,0 +1,34 @@
+import {
+ AddNumbers,
+ AddStrings,
+ Multiply,
+ ToString,
+ UnarrayIfOnlyHead,
+} from "../util";
+
+export type FnError<T extends string> = `Function execution error: ${T}`;
+
+export type BUILTIN_Arr<Args extends readonly any[]> = Args;
+
+export type BUILTIN_ToString<Args extends readonly any[]> = ToString<
+ UnarrayIfOnlyHead<{
+ [Idx in keyof Args]: ToString<Args[Idx]>;
+ }>
+>;
+
+export type BUILTIN_Add<Args extends readonly any[]> =
+ Args extends readonly string[]
+ ? AddStrings<Args>
+ : Args extends readonly number[]
+ ? AddNumbers<Args>
+ : FnError<`Cannot add operands ${ToString<Args>}`>;
+
+export type BUILTIN_Mul<Args extends readonly any[]> = Args extends [
+ infer A,
+ infer B,
+ infer C
+]
+ ? FnError<`Can only multiply [number, number], but got ${ToString<Args>}`>
+ : Args extends [infer M extends number, infer N extends number]
+ ? Multiply<M, N>
+ : FnError<`Can only multiply [number, number], but got ${ToString<Args>}`>;
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 extends ASTNode> =
+ Node["children"] extends infer Children extends readonly ASTNode[]
+ ? {
+ [Idx in keyof Children]: Children[Idx] extends ASTNode
+ ? Evaluate<Children[Idx]>
+ : never;
+ } extends infer Args extends readonly any[]
+ ? Node["name"] extends "tostring"
+ ? BUILTIN_ToString<Args>
+ : Node["name"] extends "arr"
+ ? BUILTIN_Arr<Args>
+ : Node["name"] extends "add"
+ ? BUILTIN_Add<Args>
+ : Node["name"] extends "mul"
+ ? BUILTIN_Mul<Args>
+ : SENTINEL_NO_BUILTIN
+ : never
+ : never;
+
+export type EvalError<T extends string> = `Eval error: ${T}`;
+
+export type Evaluate<Node extends ASTNode> = Node["type"] extends NodeType.INT
+ ? Node["value"]
+ : Node["type"] extends NodeType.EXT
+ ? MapBuiltins<Node>
+ : EvalError<`Unhandled node type ${Node["type"]}`>;
+
+const input = `` as const;
+const lex_result = null as unknown as Lex<typeof input>;
+const parse_result = null as unknown as Parse<typeof lex_result>;
+const eval_result = null as unknown as Evaluate<typeof parse_result>;
diff --git a/src/lang/core/index.ts b/src/lang/core/index.ts
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/lang/core/index.ts
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 string> = 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<TokenType.NAME, Ctx["nameCollection"]>])
+ ]
+ : [
+ ...Ctx["tokens"],
+ ...(Ctx["nameCollection"] extends ""
+ ? [_Token]
+ : [Token<TokenType.NAME, Ctx["nameCollection"]>, _Token])
+ ];
+};
+
+export type IsOpen<T> = T extends `${TokenType.OPEN_PAREN}` ? true : false;
+export type IsClose<T> = T extends `${TokenType.CLOSE_PAREN}` ? true : false;
+
+export type _Lex<Ctx extends LexerCtx> =
+ Ctx["next"] extends `${infer Head}${infer Tail}`
+ ? IsWhitespace<Head> extends true
+ ? _Lex<ProcessNameCollection<Ctx, Tail, null>>
+ : IsOpen<Head> extends true
+ ? _Lex<ProcessNameCollection<Ctx, Tail, Token<TokenType.OPEN_PAREN>>>
+ : IsClose<Head> extends true
+ ? _Lex<ProcessNameCollection<Ctx, Tail, Token<TokenType.CLOSE_PAREN>>>
+ : _Lex<{
+ next: Tail;
+ nameCollection: `${Ctx["nameCollection"]}${Head}`;
+ tokens: Ctx["tokens"];
+ }>
+ : Ctx["tokens"];
+
+export type Lex<Raw extends string> = _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<T extends string> = ASTNode<
+ NodeType.PARSER_ERROR,
+ "Error",
+ T,
+ []
+>;
+
+export type PushChild<Node extends ASTNode, Child extends ASTNode> = {
+ 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<Tail, Child>]
+ : Stack extends [infer Only extends ASTNode]
+ ? [PushChild<Only, Child>]
+ : 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<Tail, Child>, Final]
+ : Stack extends [infer Only extends ASTNode, infer Final extends ASTNode]
+ ? [PushChild<Only, Child>, Final]
+ : never;
+
+export type GetLastOnStack<Stack extends ParserCtx["stack"]> = Stack extends [
+ ...infer Head,
+ infer Tail extends ASTNode
+]
+ ? Tail
+ : Stack extends [infer Only extends ASTNode]
+ ? Only
+ : never;
+
+export type StackWithoutLast<Stack extends ParserCtx["stack"]> = 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 string> =
+ T extends `${infer Inner extends number}` ? Inner : NULL_SENTINEL;
+
+export type ParseStringLiteral<T extends string> =
+ T extends `"${infer Inner extends string}"` ? Inner : NULL_SENTINEL;
+
+export type ResolveNodeFromToken<_Token extends Token> = ParseNumberLiteral<
+ _Token["name"]
+> extends number
+ ? ASTNode<NodeType.INT, "", ParseNumberLiteral<_Token["name"]>, []>
+ : ParseStringLiteral<_Token["name"]> extends string
+ ? ASTNode<NodeType.INT, "", ParseStringLiteral<_Token["name"]>, []>
+ : ASTNode<NodeType.EXT, _Token["name"], null, []>;
+
+export type _Parse<Ctx extends ParserCtx> = 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<Ctx["lastToken"]>
+ >;
+ }>
+ : //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<Ctx["stack"]>,
+ ResolveNodeFromToken<Ctx["lastToken"]>
+ >
+ >
+ >;
+ }>
+ : Head["type"] extends TokenType.OPEN_PAREN
+ ? // push lastName onto stack
+ // goto start
+ _Parse<{
+ lastToken: null;
+ remainingTokens: Tail;
+ stack: [...Ctx["stack"], ResolveNodeFromToken<Ctx["lastToken"]>];
+ }>
+ : 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["stack"]>
+ >
+ >;
+ }>
+ : 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["lastToken"]>
+ >;
+ }>
+ : Ctx["stack"][0];
+
+export type Parse<Raw extends readonly Token[]> = _Parse<{
+ lastToken: null;
+ remainingTokens: Raw;
+ stack: [ASTNode<NodeType.EXT, "arr", null, []>];
+}>;
+
+const test_result = null as unknown as Parse<Lex<`test(135)`>>;
diff --git a/src/lang/index.ts b/src/lang/index.ts
new file mode 100644
index 0000000..8d119de
--- /dev/null
+++ b/src/lang/index.ts
@@ -0,0 +1 @@
+export * from "./core";
diff --git a/src/lang/util/index.ts b/src/lang/util/index.ts
new file mode 100644
index 0000000..00a3e54
--- /dev/null
+++ b/src/lang/util/index.ts
@@ -0,0 +1,3 @@
+export * from "./number";
+export * from "./utils";
+export * from "./string";
diff --git a/src/lang/util/number.ts b/src/lang/util/number.ts
new file mode 100644
index 0000000..132994b
--- /dev/null
+++ b/src/lang/util/number.ts
@@ -0,0 +1,34 @@
+export type NumberToArray<
+ Number extends number,
+ Carry extends readonly any[] = []
+> = Number extends Carry["length"]
+ ? Carry
+ : NumberToArray<Number, [...Carry, any]>;
+
+export type NumbersToArray<
+ Numbers extends readonly number[],
+ Carry extends readonly any[] = []
+> = Numbers extends [
+ infer Head extends number,
+ ...infer Tail extends readonly number[]
+]
+ ? NumbersToArray<Tail, [...Carry, ...NumberToArray<Head>]>
+ : Carry;
+
+export type AddNumbers<Numbers extends readonly number[]> =
+ NumbersToArray<Numbers> extends infer T extends readonly any[]
+ ? T["length"]
+ : never;
+
+export type MultiplyInner<
+ N extends number,
+ MS extends readonly any[],
+ Carry extends number = 0
+> = MS extends [infer Head extends number, ...infer Tail extends readonly any[]]
+ ? MultiplyInner<N, Tail, AddNumbers<[Carry, N]>>
+ : Carry;
+
+export type Multiply<M extends number, N extends number> = MultiplyInner<
+ M,
+ NumberToArray<N>
+>;
diff --git a/src/lang/util/string.ts b/src/lang/util/string.ts
new file mode 100644
index 0000000..5772f40
--- /dev/null
+++ b/src/lang/util/string.ts
@@ -0,0 +1,17 @@
+export type AddStrings<
+ Strings extends readonly string[],
+ Carry extends string = ""
+> = Strings extends [infer Head extends string, ...infer Tail extends string[]]
+ ? AddStrings<Tail, `${Carry}${Head}`>
+ : Carry;
+
+export type ToString<T, Carry extends string = ""> = T extends string | number
+ ? `${T}`
+ : T extends readonly any[]
+ ? T extends readonly [infer Head, ...infer Tail]
+ ? `${ToString<
+ Tail,
+ `${Carry extends "" ? "" : `${Carry}, `}${ToString<Head>}`
+ >}`
+ : `[${Carry}]`
+ : never;
diff --git a/src/lang/util/utils.ts b/src/lang/util/utils.ts
new file mode 100644
index 0000000..ac36ca1
--- /dev/null
+++ b/src/lang/util/utils.ts
@@ -0,0 +1,8 @@
+export type UnarrayIfOnlyHead<T extends readonly any[]> = T extends [
+ infer Head,
+ infer Next
+]
+ ? T
+ : T extends [infer Head]
+ ? Head
+ : T;
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 15:01:57 +0000