From 6639605b395ceb1355c95e06ff0e1470adc54101 Mon Sep 17 00:00:00 2001 From: Akshay Nair Date: Fri, 7 Jan 2022 18:13:40 +0530 Subject: refactor: simplifies quantifier logic + moves stuff around --- src/index.ts | 106 +--------------------------------- src/parser.ts | 162 ---------------------------------------------------- src/parser/index.ts | 81 ++++++++++++++++++++++++++ src/parser/utils.ts | 162 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/types.ts | 17 ++++++ tests/basic.spec.ts | 60 ++++++++++--------- 6 files changed, 290 insertions(+), 298 deletions(-) delete mode 100644 src/parser.ts create mode 100644 src/parser/index.ts create mode 100644 src/parser/utils.ts create mode 100644 src/types.ts diff --git a/src/index.ts b/src/index.ts index 2ea40eb..82eefe8 100644 --- a/src/index.ts +++ b/src/index.ts @@ -1,106 +1,2 @@ -import { constant, pipe } from 'fp-ts/function' -import { chain, fold, right } from 'fp-ts/lib/Either' -import { match } from './utils' -import { - delimited, - many1, - mapTo, - optional, - or, - Parser, - ParserResult, - symbol, - tuple3, -} from './parser' -export const start = mapTo(symbol('^'), constant({ tag: 'Start' } as Expr)) -export const end = mapTo(symbol('$'), constant({ tag: 'End' } as Expr)) -export const anyItem = mapTo(symbol('.'), constant({ tag: 'AnyItem' } as Expr)) -export const nextItem = mapTo( - symbol(','), - constant({ tag: 'NextItem' } as Expr) -) -export const anyString = mapTo( - symbol('\\s'), - constant({ tag: 'AnyString' } as Expr) -) -export const anyNumber = mapTo( - symbol('\\n'), - constant({ tag: 'AnyNumber' } as Expr) -) -export const anyBool = mapTo( - symbol('\\b'), - constant({ tag: 'AnyBool' } as Expr) -) -export const truthy = mapTo(symbol('\\T'), constant({ tag: 'Truthy' } as Expr)) -export const falsey = mapTo(symbol('\\F'), constant({ tag: 'Falsey' } as Expr)) - -type Expr = - | { tag: 'Start' } - | { tag: 'End' } - | { tag: 'Optional'; expr: Expr } - | { tag: 'OneOrMore'; expr: Expr } - | { tag: 'ZeroOrMore'; expr: Expr } - | { tag: 'NextItem' } - | { tag: 'AnyItem' } - | { tag: 'Or' } - | { tag: 'AnyString' } - | { tag: 'AnyNumber' } - | { tag: 'AnyBool' } - | { tag: 'Truthy' } - | { tag: 'Falsey' } - | { tag: 'Group'; exprs: Expr[] } - -export const wrapQuantifiers: (e: ParserResult) => ParserResult = - chain(([expr, input]) => - pipe( - input, - or([symbol('*'), symbol('+'), symbol('?')]), - fold( - () => right([expr, input]), - ([c, inp]) => - pipe( - c, - match({ - '*': () => ({ tag: 'ZeroOrMore', expr }), - '+': () => ({ tag: 'OneOrMore', expr }), - '?': () => ({ tag: 'Optional', expr }), - _: () => expr, - }), - (ex) => right([ex, inp]) - ) - ) - ) - ) - -export const expressionP: Parser = (input: string) => - pipe( - input, - or([ - mapTo( - delimited(symbol('('), many1(expressionP), symbol(')')), - (exprs) => ({ tag: 'Group', exprs } as Expr) - ), - nextItem, - anyItem, - anyString, - anyNumber, - anyBool, - truthy, - falsey, - ]), - wrapQuantifiers - ) - -export const parser = tuple3(optional(start), many1(expressionP), optional(end)) - -/* - -{3,6} => 3 to 6 instances -(> 5) => number greater than -(< 5) => number less than -[name x] => apply x on property `name` -| => or -/x/ => match regular expression (string values in list) - -*/ +export * from './parser'; diff --git a/src/parser.ts b/src/parser.ts deleted file mode 100644 index a7d6528..0000000 --- a/src/parser.ts +++ /dev/null @@ -1,162 +0,0 @@ -import { constant, flow, pipe } from 'fp-ts/function' -import { - Either, - left, - right, - map, - chain, - orElse, - fold, - orElseW, -} from 'fp-ts/Either' -import { none, some, Option } from 'fp-ts/Option' -import { mapFst, mapSnd, snd } from 'fp-ts/Tuple' -import { eq } from './utils' - -export type char = string - -export type ParserState = [T, string] -export type ParserError = [string, string] -export type ParserResult = Either> -export type Parser = (input: string) => ParserResult - -export const constP = - (v: T): Parser => - (inp: string) => - right([v, inp]) - -export const many0 = (parser: Parser): Parser> => - flow( - parser, - chain(([a, nextInput]) => - pipe(nextInput, many0(parser), map(mapFst((ls) => [a, ...ls]))) - ), - orElse( - flow( - mapFst((_) => [] as T[]), - right - ) - ) - ) - -export const many1 = (parser: Parser): Parser> => - flow( - many0(parser), - chain(([res, inp]) => - res.length > 0 - ? right([res, inp]) - : left([`many1 failed to parse at ${inp}`, inp]) - ) - ) - -const recoverInput = - (p: Parser): Parser => - (input: string) => - pipe( - input, - p, - orElseW( - flow( - mapSnd((_) => input), - left - ) - ) - ) - -export const prefixed = (a: Parser, b: Parser): Parser => - recoverInput(flow(a, chain(flow(snd, b)))) - -export const suffixed = (a: Parser, b: Parser): Parser => - recoverInput( - flow( - a, - chain(([out, inp]) => pipe(inp, b, map(mapFst((_) => out)))) - ) - ) - -export const delimited = ( - p: Parser, - a: Parser, - s: Parser -): Parser => suffixed(prefixed(p, a), s) - -export const satifyChar = - (f: (c: char) => boolean): Parser => - (input: string) => { - const c = input.charAt(0) - if (f(c)) return right([c, input.slice(1)]) - return left([`Expected to satisfy ${f}, got "${c}"`, input]) - } - -export const digit = satifyChar((c) => /^[0-9]$/g.test(c)) - -export const integer: Parser = flow( - many1(digit), - map(mapFst((ds) => parseInt(ds.join(''), 10))) -) - -export const or = (parsers: Parser[]): Parser => { - const run = ([p, ...ps]: Parser[]) => - flow( - p, - orElse(([_, inp]) => or(ps)(inp)) - ) - - return parsers.length > 0 - ? run(parsers) - : (inp: string) => left(['unable to match', inp]) -} - -export const matchChar = (ch: char): Parser => satifyChar(eq(ch)) - -export const space = matchChar(' ') -export const newline = matchChar('\n') -export const tab = matchChar('\t') - -export const whitespace = or([space, newline, tab]) -export const whitespaces0 = many0(whitespace) - -export const matchString = - (s: string): Parser => - (input: string) => - input.slice(0, s.length) === s - ? right([s, input.slice(s.length)]) - : left([`Expected ${s} but got ${input.slice(0, 1)}`, input]) - -export const symbol = (s: string): Parser => - delimited(whitespaces0, matchString(s), whitespaces0) - -export const mapTo = (p: Parser, f: (p: I) => R): Parser => - flow(p, map(mapFst(f))) - -export const andThen = - (f: (p: I) => Parser) => - (p: Parser): Parser => - flow( - p, - chain(([v, inp]) => f(v)(inp)) - ) - -export const optional = (p: Parser): Parser> => - flow( - p, - fold( - flow( - mapFst((_) => none), - right - ), - flow(mapFst(some), right) - ) - ) - -export const pair = (a: Parser, b: Parser): Parser<[A, B]> => - pipe( - a, - andThen((ra) => mapTo(b, (rb) => [ra, rb])) - ) - -export const tuple3 = ( - a: Parser, - b: Parser, - c: Parser -): Parser<[A, B, C]> => mapTo(pair(pair(a, b), c), ([[a, b], c]) => [a, b, c]) diff --git a/src/parser/index.ts b/src/parser/index.ts new file mode 100644 index 0000000..f522214 --- /dev/null +++ b/src/parser/index.ts @@ -0,0 +1,81 @@ +import { constant, pipe } from 'fp-ts/function' +import { chain, orElse, right } from 'fp-ts/lib/Either' +import { + delimited, + many1, + mapTo, + optional, + or, + Parser, + ParserResult, + symbol, + tuple3, +} from './utils' +import { Expr } from '../types' + +export const start = mapTo(symbol('^'), constant({ tag: 'Start' } as Expr)) +export const end = mapTo(symbol('$'), constant({ tag: 'End' } as Expr)) +export const anyItem = mapTo(symbol('.'), constant({ tag: 'AnyItem' } as Expr)) +export const nextItem = mapTo( + symbol(','), + constant({ tag: 'NextItem' } as Expr) +) +export const anyString = mapTo( + symbol('\\s'), + constant({ tag: 'AnyString' } as Expr) +) +export const anyNumber = mapTo( + symbol('\\n'), + constant({ tag: 'AnyNumber' } as Expr) +) +export const anyBool = mapTo( + symbol('\\b'), + constant({ tag: 'AnyBool' } as Expr) +) +export const truthy = mapTo(symbol('\\T'), constant({ tag: 'Truthy' } as Expr)) +export const falsey = mapTo(symbol('\\F'), constant({ tag: 'Falsey' } as Expr)) + +export const wrapQuantifiers: (e: ParserResult) => ParserResult = + chain(([expr, input]) => + pipe( + input, + or([ + mapTo(symbol('*'), (_) => ({ tag: 'ZeroOrMore', expr } as Expr)), + mapTo(symbol('+'), (_) => ({ tag: 'OneOrMore', expr } as Expr)), + mapTo(symbol('?'), (_) => ({ tag: 'Optional', expr } as Expr)), + ]), + orElse(() => right([expr, input])) + ) + ) + +export const expressionP: Parser = (input: string) => + pipe( + input, + or([ + mapTo( + delimited(symbol('('), many1(expressionP), symbol(')')), + (exprs) => ({ tag: 'Group', exprs } as Expr) + ), + nextItem, + anyItem, + anyString, + anyNumber, + anyBool, + truthy, + falsey, + ]), + wrapQuantifiers + ) + +export const parser = tuple3(optional(start), many1(expressionP), optional(end)) + +/* + +{3,6} => 3 to 6 instances +(> 5) => number greater than +(< 5) => number less than +[name x] => apply x on property `name` +| => or +/x/ => match regular expression (string values in list) + +*/ diff --git a/src/parser/utils.ts b/src/parser/utils.ts new file mode 100644 index 0000000..00b50f8 --- /dev/null +++ b/src/parser/utils.ts @@ -0,0 +1,162 @@ +import { constant, flow, pipe } from 'fp-ts/function' +import { + Either, + left, + right, + map, + chain, + orElse, + fold, + orElseW, +} from 'fp-ts/Either' +import { none, some, Option } from 'fp-ts/Option' +import { mapFst, mapSnd, snd } from 'fp-ts/Tuple' +import { eq } from '../utils' + +export type char = string + +export type ParserState = [T, string] +export type ParserError = [string, string] +export type ParserResult = Either> +export type Parser = (input: string) => ParserResult + +export const constP = + (v: T): Parser => + (inp: string) => + right([v, inp]) + +export const many0 = (parser: Parser): Parser> => + flow( + parser, + chain(([a, nextInput]) => + pipe(nextInput, many0(parser), map(mapFst((ls) => [a, ...ls]))) + ), + orElse( + flow( + mapFst((_) => [] as T[]), + right + ) + ) + ) + +export const many1 = (parser: Parser): Parser> => + flow( + many0(parser), + chain(([res, inp]) => + res.length > 0 + ? right([res, inp]) + : left([`many1 failed to parse at ${inp}`, inp]) + ) + ) + +const recoverInput = + (p: Parser): Parser => + (input: string) => + pipe( + input, + p, + orElseW( + flow( + mapSnd((_) => input), + left + ) + ) + ) + +export const prefixed = (a: Parser, b: Parser): Parser => + recoverInput(flow(a, chain(flow(snd, b)))) + +export const suffixed = (a: Parser, b: Parser): Parser => + recoverInput( + flow( + a, + chain(([out, inp]) => pipe(inp, b, map(mapFst((_) => out)))) + ) + ) + +export const delimited = ( + p: Parser, + a: Parser, + s: Parser +): Parser => suffixed(prefixed(p, a), s) + +export const satifyChar = + (f: (c: char) => boolean): Parser => + (input: string) => { + const c = input.charAt(0) + if (f(c)) return right([c, input.slice(1)]) + return left([`Expected to satisfy ${f}, got "${c}"`, input]) + } + +export const digit = satifyChar((c) => /^[0-9]$/g.test(c)) + +export const integer: Parser = flow( + many1(digit), + map(mapFst((ds) => parseInt(ds.join(''), 10))) +) + +export const or = (parsers: Parser[]): Parser => { + const run = ([p, ...ps]: Parser[]) => + flow( + p, + orElse(([_, inp]) => or(ps)(inp)) + ) + + return parsers.length > 0 + ? run(parsers) + : (inp: string) => left(['unable to match', inp]) +} + +export const matchChar = (ch: char): Parser => satifyChar(eq(ch)) + +export const space = matchChar(' ') +export const newline = matchChar('\n') +export const tab = matchChar('\t') + +export const whitespace = or([space, newline, tab]) +export const whitespaces0 = many0(whitespace) + +export const matchString = + (s: string): Parser => + (input: string) => + input.slice(0, s.length) === s + ? right([s, input.slice(s.length)]) + : left([`Expected ${s} but got ${input.slice(0, 1)}`, input]) + +export const symbol = (s: string): Parser => + delimited(whitespaces0, matchString(s), whitespaces0) + +export const mapTo = (p: Parser, f: (p: I) => R): Parser => + flow(p, map(mapFst(f))) + +export const andThen = + (f: (p: I) => Parser) => + (p: Parser): Parser => + flow( + p, + chain(([v, inp]) => f(v)(inp)) + ) + +export const optional = (p: Parser): Parser> => + flow( + p, + fold( + flow( + mapFst((_) => none), + right + ), + flow(mapFst(some), right) + ) + ) + +export const pair = (a: Parser, b: Parser): Parser<[A, B]> => + pipe( + a, + andThen((ra) => mapTo(b, (rb) => [ra, rb])) + ) + +export const tuple3 = ( + a: Parser, + b: Parser, + c: Parser +): Parser<[A, B, C]> => mapTo(pair(pair(a, b), c), ([[a, b], c]) => [a, b, c]) diff --git a/src/types.ts b/src/types.ts new file mode 100644 index 0000000..21e9517 --- /dev/null +++ b/src/types.ts @@ -0,0 +1,17 @@ + +export type Expr = + | { tag: 'Start' } + | { tag: 'End' } + | { tag: 'Optional'; expr: Expr } + | { tag: 'OneOrMore'; expr: Expr } + | { tag: 'ZeroOrMore'; expr: Expr } + | { tag: 'NextItem' } + | { tag: 'AnyItem' } + | { tag: 'Or' } + | { tag: 'AnyString' } + | { tag: 'AnyNumber' } + | { tag: 'AnyBool' } + | { tag: 'Truthy' } + | { tag: 'Falsey' } + | { tag: 'Group'; exprs: Expr[] } + diff --git a/tests/basic.spec.ts b/tests/basic.spec.ts index 4e0a938..59ce573 100644 --- a/tests/basic.spec.ts +++ b/tests/basic.spec.ts @@ -1,18 +1,12 @@ import { left, right } from 'fp-ts/Either' import { - many0, - digit, integer, whitespace, - suffixed, - prefixed, whitespaces0, delimited, - symbol, - optional, -} from '../src/parser' -import { parser } from '../src' -import {some} from 'fp-ts/lib/Option' +} from '../src/parser/utils' +import { parser } from '../src/parser' +import { some } from 'fp-ts/Option' describe('Foobar', () => { it('should do shit', () => { @@ -31,32 +25,36 @@ describe('Foobar', () => { }) it('should maybeshut', () => { - expect(parser(/^ .\s(\n)\b \T $/.source)).toEqual(right([ - [ - some({ tag: 'Start' }), + expect(parser(/^ .\s(\n)\b \T $/.source)).toEqual( + right([ [ - { tag: 'AnyItem' }, - { tag: 'AnyString' }, - { tag: 'Group', exprs: [{ tag: 'AnyNumber' },] }, - { tag: 'AnyBool' }, - { tag: 'Truthy' }, + some({ tag: 'Start' }), + [ + { tag: 'AnyItem' }, + { tag: 'AnyString' }, + { tag: 'Group', exprs: [{ tag: 'AnyNumber' }] }, + { tag: 'AnyBool' }, + { tag: 'Truthy' }, + ], + some({ tag: 'End' }), ], - some({ tag: 'End' }), - ], - '' - ])) + '', + ]) + ) - expect(parser(/^ \s* \T? \n+ $/.source)).toEqual(right([ - [ - some({ tag: 'Start' }), + expect(parser(/^ \s* \T? \n+ $/.source)).toEqual( + right([ [ - { tag: 'ZeroOrMore', expr: { tag: 'AnyString' } }, - { tag: 'Optional', expr: { tag: 'Truthy' } }, - { tag: 'OneOrMore', expr: { tag: 'AnyNumber' } }, + some({ tag: 'Start' }), + [ + { tag: 'ZeroOrMore', expr: { tag: 'AnyString' } }, + { tag: 'Optional', expr: { tag: 'Truthy' } }, + { tag: 'OneOrMore', expr: { tag: 'AnyNumber' } }, + ], + some({ tag: 'End' }), ], - some({ tag: 'End' }), - ], - '' - ])) + '', + ]) + ) }) }) -- cgit v1.3.1