X-Git-Url: https://git.kianting.info/?a=blobdiff_plain;f=src%2Findex.ts;h=46c4a7205501d288c574df83980d0e910e4bfd63;hb=4fd4c8a4b69464bf1ac74af920175308656e6f6b;hp=883d94b742145129ff948e0325d94457b274b8f1;hpb=5fbb467bdf501dee03c78817242581d962547c4f;p=clo diff --git a/src/index.ts b/src/index.ts index 883d94b..46c4a72 100644 --- a/src/index.ts +++ b/src/index.ts @@ -1,362 +1,476 @@ var fs = require('fs'); - -export type Some = { _tag: "Some"; value: T }; -export type None = {_tag: "None"}; - +import { argv, resourceUsage } from 'node:process'; +import * as tk from './tokenize.js'; +import * as util from 'util'; +import { drawEllipsePath, reduceRotation } from 'pdf-lib'; +import { isAnyArrayBuffer, isTypedArray } from 'node:util/types'; +import { error } from 'node:console'; +import { isUndefined } from 'node:util'; /** - * wrap a x in a `Some(T)` - * @param x : variable to be wrapped. - * @returns wrapped `x`. + * debug reprensenting */ -function toSome(x: T): Some{ - return { _tag: "Some", value: x}; -} +let repr = (x : any)=>{return util.inspect(x, {depth: null})}; + /** - * @description Like the `Some(a)` and `None` in Rust. - * - * @example - * ```ts - * let exam1 : Maybe = { _tag: "Some", value: 12 }; - * let exam2 : Maybe = None; - * ``` + * token tree type. */ -export type Maybe = Some | None; - +type tkTree = tkTree[] | tk.Token /** - * @description - * the pair of the string to be matched later and the string that have been matched - * @var matched : have been matched - * @var remained : will be tested whether it'll be matched. - * @var matched_type (optional): the type of the matched string -*/ -export interface MatcheePair { - matched : string - remained : string - matched_type?: TokenType + * concated 2 `tkTree`s + * @param x the array to be concated + * @param y the item or array to ve concated + * @returns concated tkTree array, or thrown error if can't be concated. + */ +function concat(x: tkTree, y:tkTree): tkTree[] { + if (Array.isArray(x)){ + return x.concat(y); + }else{ + throw new Error("the tkTree can't be concated, because it's not an array."); + + } +} + +function slice(x: tkTree, index?:number, end?:number): tkTree[] { + if (Array.isArray(x)){ + return x.slice(index,end); + }else{ + throw new Error("the tkTree can't be concated, because it's not an array."); + + } } /** - * The types of Token - * NL, // newline + * TokenMatcheePair for tokens' parser combinator + * + * matched: the matched (now and before) tokens * - * SP, // half-width space and tab + * remained: tokens to be matched * - * ID, // identifier - * - * STR, // string - * - * OP, // operator or something like it - * - * FLO, // float num - * - * INT, // Integer + * ast: abstract syntax tree */ -export enum TokenType{ - NL, // newlinw - SP, // half-width space and tab - ID, // identifier - STR, // string - OP, // operator - FLO, // float num - INT, // integer +export interface TokenMatcheePair { + matched: tk.Token[] + remained: tk.Token[] + ast : tkTree[] } /** - * tokenized token. - * @var text : the content text - * @var type (optional): the type of the token - * @var col : the column number - * @var ln : the line number + * convert a `tkTree` AST to S-expr string + * @param t the `tkTree` + * @returns S-expr String */ -export interface Token{ - text: string, - type?: TokenType, - col: number, - ln: number, +export function tkTreeToSExp(t: tkTree): string{ + var str = ""; + + if (Array.isArray(t)){ + let strArray = t.map((x)=>tkTreeToSExp(x)); + str = "(" + strArray.join(" ") + ")"; + }else{ + if (t=== undefined){ + str = "%undefined" + }else{ + str = t.text; + } + } + + return str; } /** * @description - * it returns a function which test if the first char of the `remained` part of - * the argument of the function is `c`, if it's true, update the `MatchedPair` wrapped + * match one token type. + * + * it returns a function which test if the type of first token of the `remained` part of + * the argument of the function is `typ` , if it's true, update the `TokenMatcheePair` wrapped * in `Some`. Otherwise, it returns `None`. - * * @param c : the char to be test. - * @returns the updated `MatchedPair` wrapped in `Some(x)` or `None`. + * * @param typ : the type to be test. + * @returns the updated `TokenMatcheePair` wrapped in `Some(x)` or `None`. */ -export function match1Char(c : string) : (m: MatcheePair) => Maybe { - return (m : MatcheePair)=>{ - if (m.remained.length == 0){ +export function m1TType(typ: tk.TokenType): + (m: TokenMatcheePair) => tk.Maybe { + return (m: TokenMatcheePair) => { + if (m.remained.length == 0) { return { _tag: "None" }; } - const charToBeMatched = m.remained[0]; - if (charToBeMatched === c){ - return {_tag: "Some", value :{ - matched : m.matched + charToBeMatched, - remained : m.remained.substring(1)}}; + /** + * token to be matched + * */ + const ttbm = m.remained[0]; + + if (ttbm.type == typ) { + let new_matched = m.matched.concat(ttbm); + let result : tk.Some = { + _tag: "Some", value: { + matched: new_matched, + remained: m.remained.slice(1), + ast: ([ttbm]), + } + }; + return result; } - else{ - return {_tag: "None"}; + else { + return { _tag: "None" }; } } }; /** - * - * @param m : the `MatcheePair` to be consumed. - * @returns if the length of `m.remained` >= 1; consumes the matchee by 1 char and wraps it in `Some`, - * otherwise, returns `None`. + * type int */ -export function matchAny(m : MatcheePair) : Maybe{ - if (m.remained.length >= 1){ - return {_tag: "Some", value :{ - matched : m.matched + m.remained[0], - remained : m.remained.substring(1)}}; - }else{ - return {_tag: "None"}; - } -} +let tInt = m1TType(tk.TokenType.INT); +let tId = m1TType(tk.TokenType.ID); + + +let tAdd = m1TType(tk.TokenType.I_ADD); +let tSub = m1TType(tk.TokenType.I_SUB); +let tMul = m1TType(tk.TokenType.I_MUL); +let tDiv = m1TType(tk.TokenType.I_DIV); +let tLParen = m1TType(tk.TokenType.L_PAREN); +let tRParen = m1TType(tk.TokenType.R_PAREN); +let tComma = m1TType(tk.TokenType.COMMA); +let toSome = tk.toSome; + + +argv.forEach((val, index) => { + console.log(`${index}=${val}`); +}); -/** - * @description - * it returns a function which test if the first char of the `remained` part of - * the argument of the function is between `l` and `u`, if it's true, update the `MatchedPair` wrapped - * in `Some`. Otherwise, it returns `None`. - * * @param l : lower bound char, 1-char string - * * @param u : upper bound char, 1-char string - * @returns the updated `MatchedPair` wrapped in `Some(x)` or `None`. - */ -export function matchRange(l : string, u : string) : (m: MatcheePair) => Maybe { - let lCodepoint = charToCodepoint(l); - let uCodepoint = charToCodepoint(u); - if (l > u){ - throw new Error("Error: the codepoint of `"+l+"` is not smaller than `"+u+"`)"); - } - return (m : MatcheePair)=>{ - if (m.remained.length < 1){ - return {_tag : "None"}; - } - const charToBeMatched = m.remained[0]; - const codePointToBeMatched = charToCodepoint(charToBeMatched); - if (codePointToBeMatched >= lCodepoint && codePointToBeMatched <= uCodepoint){ - return {_tag: "Some", value :{ - matched : m.matched + charToBeMatched, - remained : m.remained.substring(1)}}; - } - else{ - return {_tag: "None"}; - } - } -}; /** - * convert the one-char string to codepoint. - * @param s : the string to code point. - * @returns if `s.length > 1` return error; otherwise, return the codepoint of `s`. + * like `m ==> f` in ocaml + * @param m matchee wrapped + * @param f matching function + * @returns wrapped result */ -export function charToCodepoint(s : string): number{ - if (s.length > 1){ - throw new Error("Error: the length of input string for "+s+ "is "+s.length+`, - however, it should be 1.`); +function thenDo(m : tk.Maybe, f : Function){ + if (m._tag == "None"){ + return m; }else{ - return s.charCodeAt(0); + var a : tk.Maybe = f(m.value); + if (a._tag == "Some"){ + a.value.ast = concat(m.value.ast, a.value.ast); + } + + return a; } } /** - * @description thendo(input, f, ...) like - * a ==> f - * @param input: the wrapped input. - * @param f: the function to be applied. - * - * @returns:the applied wrapped result `MatcheePair`. + * like `f1 | f2` in regex + * @param f1 the first tried function + * @param f2 the second tried function + * @returns wrapped result */ -export function thenDo(input : Maybe, f : Function) : Maybe{ - if (input._tag == "None"){ - return input; - } - else{ - let inner = input.value; - return f(inner); - } +function orDo(f1 : Function, f2 : Function){ + return (x : TokenMatcheePair) =>{ + let res1 : tk.Maybe = f1(x); + if (res1._tag == "Some"){ + return res1; + }else{ + let res2 : tk.Maybe = f2(x); + return res2; + } + } } + /** - * @description "or", like the regex `( f1 | f2 )` . - * It returns a function `f` of which the argument is`x`. - * if `f1(x)` is None, then `f` returns `f2(x)`. Otherwise, - * `F` returns `f1(x)`. - * @param f1 : 1st function to be compared - * @param f2 : 2nd function to be compared - * @returns:the combined function + * + * @param m : the `MatcheePair` to be consumed. + * @returns if the length of `m.remained` >= 1; consumes the matchee by 1 token + * and wraps it in `Some`, + * otherwise, returns `None`. */ -export function orDo(f1 : Function, f2: Function) : (x : T ) => Maybe{ - return (x) => { - let f1x : Maybe = (f1(x)); - { - if (f1x._tag == "None"){ - return f2(x); - } - else{ - return f1x; +export function matchAny(m: TokenMatcheePair): tk.Maybe { + if (m.remained.length >= 1) { + return { + _tag: "Some", value: { + matched: m.matched.concat(m.remained[0]), + remained: m.remained.slice(1), + ast : [m.remained[0]], } - } - }; + }; + } else { + return { _tag: "None" }; + } } - /** + * Danger : Maybe it's not enough to work. * @description repeating matching function `f` * zero or more times, like the asterisk `*` in regex `f*` . * @param f : the function to be repeated 0+ times. * @returns:the combined function */ -export function zeroOrMoreDo(f : Function): (x : T) => Maybe{ - return (x)=>{ - var wrapped_old_x : Maybe = {_tag: "Some", value : x}; - var wrapped_new_x : Maybe = wrapped_old_x; - - while (wrapped_new_x._tag != "None"){ - wrapped_old_x = wrapped_new_x; - wrapped_new_x = thenDo(wrapped_old_x, f); - }; +export function OnceOrMoreDo(f: Function): (x: TokenMatcheePair) => + tk.Maybe { + return (x) => { + var wrappedOldX: tk.Maybe = { _tag: "Some", value: x }; + var wrappedNewX: tk.Maybe = wrappedOldX; - return wrapped_old_x; - }; -} + var counter = -1; + + while (wrappedNewX._tag != "None") { + wrappedOldX = wrappedNewX; + wrappedNewX = thenDo(wrappedOldX, f); + counter += 1; -/** -* @description Not. like the `^` inside regex of [^f]. -* returns a function `F(x)` such that if `f(x)` is `None`, -* returns the x consuming a char; if `f(x)` is not None, F(x) -* returns `None`. -* @param f: the function forbidden to be matched. -* @returns: combined function `F`. -*/ -export function notDo(f : Function): (x : T) => Maybe{ - return (x)=>{ - let wrapped_x : Maybe = { - _tag : "Some", - value : x }; - let f_x = thenDo(wrapped_x, f); - - if (f_x._tag != "None"){ - return {_tag:"None"}; - }else{ - return thenDo(wrapped_x, matchAny); + + if (counter <= 0){ + return { _tag: "None"}; } - }; + let ast = wrappedOldX.value.ast ; + wrappedOldX.value.ast =ast.slice(ast.length-counter); + console.log(repr(wrappedOldX.value.ast)); + + return wrappedOldX; }; } /** - * if `x` is matched by `f` once, returns `f(x)`. Otherwise, - * returns x - * similar to `?` in regex `f?`. - * @param f : the function to be matched - * @returns return wrapped f(x) + * aux function for midfix operator + * @param f function + * @param signal the rule name + * @returns */ -export function zeroOrOnceDo(f : Function): (x : T) => Maybe{ - return (x)=>{ - var wrapped_old_x : Maybe = {_tag: "Some", value : x}; - var wrapped_new_x = thenDo(wrapped_old_x, f); +let midfix = (f : Function, signal? : string) => (x : TokenMatcheePair)=>{ + var a = f(x); + if (a._tag == "Some"){ + let ast_tail : tkTree[] = slice(a.value.ast,a.value.ast.length-3); + let new_ast = [ast_tail]; + a.value.ast = new_ast; - if (wrapped_new_x._tag != "None"){ - return wrapped_new_x; - }else{ - return wrapped_old_x; + // console.log("+"+signal+"+"+repr(a)); + + + } + return a; +} + +let circumfix = (f : Function, signal? : string) => (x : TokenMatcheePair)=>{ + var a : tk.Maybe = f(x); + if (a._tag == "Some"){ + console.log("$$$"+repr(a.value.ast)); + let inner = a.value.ast[a.value.ast.length-2]; + var ast_middle : tkTree[]; + // the list should not be (%list) (%apply) (%lambda) etc. + if (Array.isArray(inner)){ + if ('text' in inner[0] && (inner[0].text.slice(0,1) != "%")){ + ast_middle = inner; + } + else{ + ast_middle = [inner]; + } } - }; + else{ + ast_middle = [inner]; + } + let new_ast = [ast_middle]; + a.value.ast = new_ast; + } + return a; } +/** single1 = tInt | "(" expr ")"*/ +let single1 = circumfix((x : TokenMatcheePair) => + thenDo(thenDo(thenDo(toSome(x), tLParen), expr), tRParen), "fac1"); +let single2= tInt; +let single = orDo(single1, single2); + +/** args = single "," args | single */ +let args1 = (x: TokenMatcheePair)=>{ + var ret = thenDo(thenDo(thenDo(toSome(x), single), tComma), args); + if (ret._tag == "Some"){ + let retLength = ret.value.ast.length; + ret.value.ast = [[ret.value.ast[retLength-3]].concat(ret.value.ast[retLength-1])]; + console.log("$$"+repr(ret.value.ast)); + } + return ret; +}; -export function tokenize(input : string){ - var input_matchee_pair : Maybe = toSome( - {matched:"", - remained: input}); +let args2 = single; - // integer = ([+]|[-])?\d\d* - let integer = (x : MatcheePair) => - { let wrapped_x = toSome(x); - let plusMinus = orDo(match1Char('+'), match1Char('-')); // ([+]|[-]) - let d = matchRange('0','9'); // \d - var result = thenDo(thenDo(thenDo(wrapped_x, - zeroOrOnceDo(plusMinus)),d), - zeroOrMoreDo(d)); - - if (result._tag == "Some"){ - result.value.matched_type = TokenType.INT; - } - return result; - } - let space = (x : MatcheePair) =>{ - let wrapped_x = toSome(x); - let s_aux = orDo(match1Char(' '), match1Char('\t')); // (" " | "\t") - var result = thenDo(thenDo(wrapped_x, s_aux), zeroOrMoreDo(s_aux)); - if (result._tag == "Some"){ - result.value.matched_type = TokenType.SP; - } - return result; +let args = orDo(args1, args2); + + +/** callees = "(" args ")" | "(" ")" */ + + +let callees1 = circumfix((x : TokenMatcheePair) => + thenDo(thenDo(thenDo(toSome(x), tLParen), args), tRParen), "callees1"); +let callees2 = (x: TokenMatcheePair)=>{ + let ret = thenDo(thenDo(toSome(x), tLParen), tRParen); + if (ret._tag == "Some"){ + let new_ast : tkTree[] = [[]]; + ret.value.ast = new_ast; } - let newline = (x : MatcheePair) =>{ - let wrapped_x = toSome(x); - // nl = \r?\n - let result = thenDo(thenDo(wrapped_x, - zeroOrOnceDo(match1Char('\r'))), match1Char('\n')); - if (result._tag == "Some"){ - result.value.matched_type = TokenType.NL; - } - return result; + + return ret}; + +let callees = orDo(callees1, callees2); + + + +/** %apply R combinating token */ +let applyToken = { + text: "%apply", + type: tk.TokenType.ID, + col: 0, + ln: 0, +} + +/** facAux = callees facAux | callees */ +let facAux1 = (x: TokenMatcheePair)=>{ + var ret = thenDo(thenDo(toSome(x), callees), facAux); + if (ret._tag == "Some"){ + console.log("1232345"+repr(tkTreeToSExp(ret.value.ast[ret.value.ast.length-1]))); + let last1 = ret.value.ast[ret.value.ast.length-1]; + let last2 = ret.value.ast[ret.value.ast.length-2]; + + + let b : tkTree[] = [applyToken]; + ret.value.ast = [b.concat([last2, last1])]; + console.log("11111"+repr(tkTreeToSExp(ret.value.ast))); + + }; + +return ret;} +let facAux2 = callees; +let facAux = orDo(facAux1, facAux2); + + + +/** fac = single facAux | single + * Issue1 to be fixed. + */ +let fac1 = (x: TokenMatcheePair)=>{ + var ret = thenDo(thenDo(toSome(x), single),facAux); + if(ret._tag == "Some"){ + console.log("777"+repr(tkTreeToSExp(ret.value.ast))); + ret.value.ast = [applyToken, ret.value.ast[ret.value.ast.length-2], + ret.value.ast[ret.value.ast.length-1]]; + ret.value.ast; + rearrangeTree(ret.value.ast); + console.log("888"+repr(tkTreeToSExp(ret.value.ast))); + } - let term = (token_list : Array, x : Some)=>{ - var ln = 1; - var col = 0; - var old_x = x; - let term_list = [newline, space, integer]; - let term_aux = term_list.reduce((x,y)=> orDo(x,y)); - - var new_x : Maybe = thenDo(old_x, term_aux); - while (new_x._tag != "None"){ - if (new_x.value.matched_type != TokenType.NL){ - col += new_x.value.matched.length; - token_list.push({text : new_x.value.matched, - type: new_x.value.matched_type, - ln : ln, - col : col}); - - } - else{ - col = 0; - ln += 1; + return ret;}; +let fac2 = single; +let fac = orDo(fac1, fac2); - token_list.push({text : new_x.value.matched, - type: new_x.value.matched_type, - ln : ln, - col : col}); + +/** + * rearrangeTree : for applyToken subtree from right-combination to + * left-combination + * @input x a ast + * @return another ast + */ +function rearrangeTree(x: any) : any { + if (x !== undefined){ + for (var i=1;i + thenDo(thenDo(thenDo(toSome(x), fac), orDo(tMul,tDiv)), fac), "term1"); + + +/** + * + * term2 = int MUL int + */ +let term2 = fac; + +/** + * term = term1 | term2 + */ +let term = orDo(term1, term2); + + +/** + * + * expr1 = term ADD term + */ +let expr1 = midfix((x : TokenMatcheePair)=> + thenDo(thenDo(thenDo(toSome(x), term), orDo(tAdd,tSub)), term), "expr1"); +/** + * expr2 = term + */ +let expr2 = term; + +/** + * expr = expr1 | expr2 + */ +let expr = orDo(expr1, expr2); + + + +let tokens = tk.tokenize("1"); +let tokens2 = tk.tokenize("1(2)"); +let tokens3 = tk.tokenize("1(2)(3)"); +let tokens4 = tk.tokenize("2()(4)(5,6)(7,8,9,10)"); + +//let tokens = tk.tokenize("(4-(3/4))"); +//tk.tokenize(argv[2]); + +let tokensFiltered = tokens4.filter( + (x)=>{return (x.type != tk.TokenType.NL + && x.type != tk.TokenType.SP)}); + + + +let beta = expr({ + matched : [] , + remained : tokensFiltered, + ast : []}); + - console.log(term([], input_matchee_pair)); - // TODO: id, string, space, basic operator, 3 marks: @, {, }. +if (beta._tag == "Some"){ + beta.value.ast = rearrangeTree(beta.value.ast); + console.log(tkTreeToSExp(beta.value.ast)); } +console.log("RESULT="+repr(beta));