diff options
Diffstat (limited to 'src/parser')
| -rw-r--r-- | src/parser/index.ts | 81 | ||||
| -rw-r--r-- | src/parser/utils.ts | 162 |
2 files changed, 243 insertions, 0 deletions
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<Expr>) => ParserResult<Expr> = + 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<Expr> = (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> = [T, string] +export type ParserError = [string, string] +export type ParserResult<T> = Either<ParserError, ParserState<T>> +export type Parser<T> = (input: string) => ParserResult<T> + +export const constP = + <T>(v: T): Parser<T> => + (inp: string) => + right([v, inp]) + +export const many0 = <T>(parser: Parser<T>): Parser<Array<T>> => + flow( + parser, + chain(([a, nextInput]) => + pipe(nextInput, many0(parser), map(mapFst((ls) => [a, ...ls]))) + ), + orElse( + flow( + mapFst((_) => [] as T[]), + right + ) + ) + ) + +export const many1 = <T>(parser: Parser<T>): Parser<Array<T>> => + flow( + many0(parser), + chain(([res, inp]) => + res.length > 0 + ? right([res, inp]) + : left([`many1 failed to parse at ${inp}`, inp]) + ) + ) + +const recoverInput = + <T>(p: Parser<T>): Parser<T> => + (input: string) => + pipe( + input, + p, + orElseW( + flow( + mapSnd((_) => input), + left + ) + ) + ) + +export const prefixed = <T>(a: Parser<any>, b: Parser<T>): Parser<T> => + recoverInput(flow(a, chain(flow(snd, b)))) + +export const suffixed = <T>(a: Parser<T>, b: Parser<any>): Parser<T> => + recoverInput( + flow( + a, + chain(([out, inp]) => pipe(inp, b, map(mapFst((_) => out)))) + ) + ) + +export const delimited = <T>( + p: Parser<any>, + a: Parser<T>, + s: Parser<any> +): Parser<T> => suffixed(prefixed(p, a), s) + +export const satifyChar = + (f: (c: char) => boolean): Parser<char> => + (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<number> = flow( + many1(digit), + map(mapFst((ds) => parseInt(ds.join(''), 10))) +) + +export const or = <T>(parsers: Parser<T>[]): Parser<T> => { + const run = ([p, ...ps]: Parser<T>[]) => + 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<char> => 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<string> => + (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<string> => + delimited(whitespaces0, matchString(s), whitespaces0) + +export const mapTo = <I, R>(p: Parser<I>, f: (p: I) => R): Parser<R> => + flow(p, map(mapFst(f))) + +export const andThen = + <I, R>(f: (p: I) => Parser<R>) => + (p: Parser<I>): Parser<R> => + flow( + p, + chain(([v, inp]) => f(v)(inp)) + ) + +export const optional = <T>(p: Parser<T>): Parser<Option<T>> => + flow( + p, + fold( + flow( + mapFst((_) => none), + right + ), + flow(mapFst(some), right) + ) + ) + +export const pair = <A, B>(a: Parser<A>, b: Parser<B>): Parser<[A, B]> => + pipe( + a, + andThen((ra) => mapTo(b, (rb) => [ra, rb])) + ) + +export const tuple3 = <A, B, C>( + a: Parser<A>, + b: Parser<B>, + c: Parser<C> +): Parser<[A, B, C]> => mapTo(pair(pair(a, b), c), ([[a, b], c]) => [a, b, c]) |