From 016821207f1f2294dd09935a4c1d14d78ff3aed1 Mon Sep 17 00:00:00 2001 From: Akshay Nair Date: Thu, 13 Jan 2022 21:20:23 +0530 Subject: refactor(parser): reimplements alt parser --- src/eval/index.ts | 19 ++++++----- src/parser/index.ts | 40 ++++++++++------------ src/parser/utils.ts | 17 +++++++--- src/types.ts | 4 +-- tests/basic.spec.ts | 2 +- tests/eval.spec.ts | 33 ++++++------------- tests/parser.spec.ts | 93 +++++++++++++++++++++++++++------------------------- 7 files changed, 103 insertions(+), 105 deletions(-) diff --git a/src/eval/index.ts b/src/eval/index.ts index 0579579..4c47adf 100644 --- a/src/eval/index.ts +++ b/src/eval/index.ts @@ -103,13 +103,20 @@ const checkExpr = ( ) }, - _: _ => [], + // Or: ({ left, right }) => { + // return pipe( + // [], + // skip(1), + // ) + // }, + + _: _ => { throw new Error(`TODO: ${expr.tag} not implemented for match`) }, }), ) } export const matchAll = ( - [startO, exprs, endO]: ListExpr, + [startO, expr, endO]: ListExpr, list: T[], ): MatchGroupResult => { const check = (index: number, ls: T[], expr: Expr): MatchGroupIndexed[] => { @@ -125,14 +132,12 @@ export const matchAll = ( return checkExpr(expr, item, ls, index, next) } - const expr = Expr.Group({ exprs }) - return { groups: check(0, list, expr), } } -export const find = ([startO, exprs, endO]: ListExpr, list: T[]): any => { +export const find = ([startO, expr, endO]: ListExpr, list: T[]): any => { const check = (expr: Expr) => (x: T, i: number, ls: T[]): boolean => { @@ -161,7 +166,5 @@ export const find = ([startO, exprs, endO]: ListExpr, list: T[]): any => { ) } - const cs = exprs.map(check) - - return list.filter((x, i, ls) => cs.every(c => c(x, i, ls))) + return list.filter((x, i, ls) => check(expr)(x, i, ls)) } diff --git a/src/parser/index.ts b/src/parser/index.ts index e815334..1f9da13 100644 --- a/src/parser/index.ts +++ b/src/parser/index.ts @@ -1,5 +1,5 @@ import { flow, pipe } from 'fp-ts/function' -import { chain, left, orElse, right } from 'fp-ts/lib/Either' +import { chain, map as mapE, left, orElse, right } from 'fp-ts/lib/Either' import { delimited, digits, @@ -15,6 +15,7 @@ import { ParserResult, prefixed, satifyChar, + sepBy1, suffixed, symbol, tuple3, @@ -22,7 +23,7 @@ import { } from './utils' import { Expr, ListExpr, Literal } from '../types' import {getOrElse, map} from 'fp-ts/lib/Option' -import {snd} from 'fp-ts/lib/Tuple' +import {mapFst, snd} from 'fp-ts/lib/Tuple' const start = mapTo(symbol('^'), _ => Expr.Start()) const end = mapTo(symbol('$'), _ => Expr.End()) @@ -47,17 +48,6 @@ const wrapQuantifiers: (e: ParserResult) => ParserResult = chain( ), ) -const wrapAlt: (e: ParserResult) => ParserResult = chain( - ([expr, input]) => - pipe( - input, - mapTo(prefixed(symbol('|'), many1(expressionP)), rest => - Expr.Or({ left: expr, right: rest }), - ), - orElse(_ => right([expr, input])), - ), -) - const propRegex = /^[A-Za-z0-9_-]$/ export const propertyName: Parser = pipe( @@ -76,7 +66,7 @@ const objectProperty = (input: string) => pair(propertyName, many0(expressionP)), symbol(']'), ), - ([name, exprs]) => Expr.PropertyMatch({ name, expr: Expr.Group({ exprs }) }), + ([name, exprs]) => Expr.PropertyMatch({ name, expr: exprsToGroup(exprs) }), ), ) @@ -111,13 +101,17 @@ const literalP: Parser = delimited( whitespaces0, ) -const expressionP: Parser = (input: string) => +const expressionP: Parser = (input: string) => pipe( + input, + sepBy1(symbol('|'), groupP), + mapE(mapFst(exprs => exprs.length === 1 ? exprs[0] : Expr.Or({ exprs }))), +) + +const atomP: Parser = (input: string) => pipe( input, or([ - mapTo(delimited(symbol('('), many1(expressionP), symbol(')')), exprs => - Expr.Group({ exprs }), - ), + mapTo(delimited(symbol('('), many1(expressionP), symbol(')')), exprsToGroup), objectProperty, nextItem, anyItem, @@ -129,21 +123,21 @@ const expressionP: Parser = (input: string) => mapTo(literalP, Expr.Literal), ]), wrapQuantifiers, - wrapAlt, + //wrapAlt, ) +const exprsToGroup = (exprs: Expr[]) => exprs.length === 1 ? exprs[0] : Expr.Group({ exprs }) +const groupP: Parser = mapTo(many1(atomP), exprsToGroup) + export const parser: Parser = tuple3( optional(start), - many1(expressionP), + expressionP, optional(end), ) /* - {3,6} => 3 to 6 instances (> 5) => number greater than (< 5) => number less than -[name x] => apply x on property `name` /x/ => match regular expression (string values in list) - */ diff --git a/src/parser/utils.ts b/src/parser/utils.ts index 908405e..cee1de7 100644 --- a/src/parser/utils.ts +++ b/src/parser/utils.ts @@ -1,4 +1,4 @@ -import { constant, flow, pipe } from 'fp-ts/function' +import { flow, pipe } from 'fp-ts/function' import { Either, left, @@ -9,9 +9,10 @@ import { fold, orElseW, } from 'fp-ts/Either' -import { none, some, Option } from 'fp-ts/Option' +import { none, some, Option, getOrElse } from 'fp-ts/Option' import { fst, mapFst, mapSnd, snd } from 'fp-ts/Tuple' import { eq } from '../utils' +import { prepend } from 'fp-ts/lib/Array' export type char = string @@ -25,11 +26,19 @@ export const constP = (inp: string) => right([v, inp]) +export const sepBy1 = (sep: Parser, parser: Parser): Parser => + flow( + parser, + chain(([val, nextInput]) => + pipe(nextInput, many0(prefixed(sep, parser)), map(mapFst(prepend(val)))), + ), + ) + export const many0 = (parser: Parser): Parser> => flow( parser, chain(([a, nextInput]) => - pipe(nextInput, many0(parser), map(mapFst(ls => [a, ...ls]))), + pipe(nextInput, many0(parser), map(mapFst(prepend(a)))), ), orElse( flow( @@ -134,7 +143,7 @@ export const andThen = export const optional = (p: Parser): Parser> => flow( - p, + recoverInput(p), fold( flow( mapFst(_ => none), diff --git a/src/types.ts b/src/types.ts index b09bde5..97ff81d 100644 --- a/src/types.ts +++ b/src/types.ts @@ -18,7 +18,7 @@ export type Expr = Union<{ ZeroOrMore: { expr: Expr }, NextItem: _, AnyItem: _, - Or: { left: Expr, right: Expr[] }, + Or: { exprs: Expr[] }, AnyString: _, AnyNumber: _, AnyBool: _, @@ -32,7 +32,7 @@ export const Expr = constructors() export type ListExpr = [ Option, - Expr[], + Expr, Option, ] diff --git a/tests/basic.spec.ts b/tests/basic.spec.ts index 2d7af37..9336841 100644 --- a/tests/basic.spec.ts +++ b/tests/basic.spec.ts @@ -17,7 +17,7 @@ describe('Basic tests', () => { // jlog(matchAll(/([age \n])+/, [ {}, { age: 1 }, { age: 2 }, { age: 0 }, '' ])) // jlog(matchAll(/\n+/, [ '', 1, 2, 0, '6', 5, '' ])) - //jlog(matchAll(/ -2.05 /, [ 2, -2.05, 5, -2.05, 2.05, 0.05, 'wow', '-2.05', '-2' ])) + jlog(matchAll(/ -2.05|2|true|\s|\T /, [ 2, -2.05, 5, -2.05, 2.05, 0.05, 'wow', '-2.05', '-2' ])) }) describe('matchAll', () => { diff --git a/tests/eval.spec.ts b/tests/eval.spec.ts index f4999b6..ab91948 100644 --- a/tests/eval.spec.ts +++ b/tests/eval.spec.ts @@ -10,13 +10,11 @@ describe('Eval', () => { const liexp: ListExpr = [ none, - [ - Expr.OneOrMore({ - expr: Expr.Group({ - exprs: [Expr.AnyNumber(), Expr.Truthy()], - }), + Expr.OneOrMore({ + expr: Expr.Group({ + exprs: [Expr.AnyNumber(), Expr.Truthy()], }), - ], + }), none, ] @@ -26,10 +24,10 @@ describe('Eval', () => { it('basic evaluation', () => { const list = [0, 1, '2', 3, [4], 5] - const liexp: ListExpr = [none, [Expr.AnyNumber(), Expr.Truthy()], none] + const liexp: ListExpr = [none, Expr.Group({ exprs: [Expr.AnyNumber(), Expr.Truthy()] }), none] expect(find(liexp, list)).toEqual([1, 3, 5]) - const liexp2: ListExpr = [none, [Expr.Falsey(), Expr.Truthy()], none] + const liexp2: ListExpr = [none, Expr.Group({ exprs: [Expr.Falsey(), Expr.Truthy()] }), none] expect(find(liexp2, list)).toEqual([]) }) @@ -38,10 +36,10 @@ describe('Eval', () => { const liexp: ListExpr = [ none, - [ + Expr.Group({ exprs: [ Expr.AnyItem(), Expr.Group({ exprs: [Expr.AnyNumber(), Expr.Truthy()] }), - ], + ] }), none, ] expect(find(liexp, list)).toEqual([1, 3, 5]) @@ -58,7 +56,7 @@ describe('Eval', () => { const liexp: ListExpr = [ none, - [ + Expr.Group({ exprs: [ Expr.PropertyMatch({ name: 'name', expr: Expr.Group({ exprs: [Expr.AnyString(), Expr.Truthy()] }), @@ -67,21 +65,10 @@ describe('Eval', () => { name: 'age', expr: Expr.Group({ exprs: [Expr.AnyNumber()] }), }), - ], + ] }), none, ] expect(find(liexp, list)).toEqual([{ name: 'gello', age: 20 }]) }) - - xit('with groups', () => { - const list = [0, 1, 1, 1, '2', 3, 4, [4], 5, ''] - - const liexp: ListExpr = [ - none, - [Expr.OneOrMore({ expr: Expr.AnyNumber() })], - none, - ] - expect(find(liexp, list)).toEqual([1, 3, 5]) - }) }) diff --git a/tests/parser.spec.ts b/tests/parser.spec.ts index bd71509..510e5bb 100644 --- a/tests/parser.spec.ts +++ b/tests/parser.spec.ts @@ -4,15 +4,26 @@ import { whitespace, whitespaces0, delimited, + sepBy1, + symbol, } from '../src/parser/utils' import { parser } from '../src/parser' import { none, some } from 'fp-ts/Option' import { Expr, Literal } from '../src/types' import { jlog } from '../src/utils' -const wrap = (l: any) => right([[none, l, none], '']) +const wrap = (e: Expr) => + right([[none, e, none], '']) +const grouped = (l: Expr[]) => + wrap(Expr.Group({ exprs: l })) +const groupedAlt = (l: Expr[]) => + wrap(Expr.Or({ exprs: l })) describe('Parser', () => { + it('should do shit', () => { + // jlog(parser(/ -2.05|\n2|true|\s|\T /.source)) + }) + it('should do shit', () => { expect(digits('12901')).toEqual(right(['12901', ''])) expect(digits('12901asas')).toEqual(right(['12901', 'asas'])) @@ -28,18 +39,19 @@ describe('Parser', () => { ) }) - it('should maybeshut', () => { - expect(parser(/^ .\s(\n)\b \T $/.source)).toEqual( + it('should compount expressions', () => { + expect(parser(/^ .\s(\n\b) \T $/.source)).toEqual( right([ [ some(Expr.Start()), - [ - Expr.AnyItem(), - Expr.AnyString(), - Expr.Group({ exprs: [Expr.AnyNumber()] }), - Expr.AnyBool(), - Expr.Truthy(), - ], + Expr.Group({ + exprs: [ + Expr.AnyItem(), + Expr.AnyString(), + Expr.Group({ exprs: [Expr.AnyNumber(), Expr.AnyBool()] }), + Expr.Truthy(), + ], + }), some(Expr.End()), ], '', @@ -50,48 +62,41 @@ describe('Parser', () => { right([ [ some(Expr.Start()), - [ - Expr.ZeroOrMore({ expr: Expr.AnyString() }), - Expr.Optional({ expr: Expr.Truthy() }), - Expr.OneOrMore({ expr: Expr.AnyNumber() }), - ], + Expr.Group({ + exprs: [ + Expr.ZeroOrMore({ expr: Expr.AnyString() }), + Expr.Optional({ expr: Expr.Truthy() }), + Expr.OneOrMore({ expr: Expr.AnyNumber() }), + ], + }), some(Expr.End()), ], '', ]), ) + }) + it('should or expressions', () => { expect(parser(/ \s|\b\T|\n /.source)).toEqual( - right([ - [ - none, - [ - Expr.Or({ - left: Expr.AnyString(), - right: [ - Expr.AnyBool(), - Expr.Or({ - left: Expr.Truthy(), - right: [Expr.AnyNumber()], - }), - ], - }), - ], - none, - ], - '', + groupedAlt([ + Expr.AnyString(), + Expr.Group({ exprs: [Expr.AnyBool(), Expr.Truthy()] }), + Expr.AnyNumber(), ]), ) }) it('object proprtyu', () => { expect(parser(/ [name \s\T] [age \n] /.source)).toEqual( - wrap([ + grouped([ Expr.PropertyMatch({ name: 'name', expr: Expr.Group({ exprs: [Expr.AnyString(), Expr.Truthy()] }), }), - Expr.PropertyMatch({ name: 'age', expr: Expr.Group({ exprs: [Expr.AnyNumber()] }) }), + Expr.PropertyMatch({ + name: 'age', + expr: Expr.AnyNumber(), + }), ]), ) }) @@ -99,35 +104,35 @@ describe('Parser', () => { it('literals', () => { // unsigned numbers expect(parser(/ 0.105 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(0.105))]), + wrap(Expr.Literal(Literal.Number(0.105))), ) expect(parser(/ 9 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(9))]), + wrap(Expr.Literal(Literal.Number(9))), ) expect(parser(/ 23 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(23))]), + wrap(Expr.Literal(Literal.Number(23))), ) // signed numbers expect(parser(/ +23.025 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(23.025))]), + wrap(Expr.Literal(Literal.Number(23.025))), ) expect(parser(/ -23.025 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(-23.025))]), + wrap(Expr.Literal(Literal.Number(-23.025))), ) expect(parser(/ +23 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(23))]), + wrap(Expr.Literal(Literal.Number(23))), ) expect(parser(/ -23 /.source)).toEqual( - wrap([Expr.Literal(Literal.Number(-23))]), + wrap(Expr.Literal(Literal.Number(-23))), ) // boolean expect(parser(/ true /.source)).toEqual( - wrap([Expr.Literal(Literal.Boolean(true))]), + wrap(Expr.Literal(Literal.Boolean(true))), ) expect(parser(/ false /.source)).toEqual( - wrap([Expr.Literal(Literal.Boolean(false))]), + wrap(Expr.Literal(Literal.Boolean(false))), ) }) }) -- cgit v1.3.1