パーサコンビネータ

parser-combinator.ts

type Parser<T> = (target: string, pos: number) => ParseResult<T>;
type ParseResult<T> = [true, T, number] | [false, null, number];

const lazy = <T>(fn: () => Parser<T>) => (target: string, pos: number) =>
  fn()(target, pos);

const oneOf = <T>(parsers: Parser<T>[]): Parser<T> => (target, pos) => {
  for (const parser of parsers) {
    const res = parser(target, pos);
    if (res[0]) {
      return res;
    }
  }

  return [false, null, pos];
};

const terminate = (str: string): Parser<string> => (target, pos) =>
  target.startsWith(str, pos)
    ? [true, str, pos + str.length]
    : [false, null, pos];

type ParserSequence<T> = {
  [K in keyof T]: Parser<T[K]>
};

const seq = <T extends any[]>(parsers: ParserSequence<T>): Parser<T> => (
  target,
  pos,
) => {
  const results: T = [] as any;
  for (const parser of parsers) {
    const [ok, ast, pos2] = parser(target, pos);
    if (ok) {
      results.push(ast);
      pos = pos2;
    } else {
      return [false, null, pos];
    }
  }

  return [true, results, pos];
};

const many = <T>(parser: Parser<T>): Parser<T[]> => (target, pos) => {
  const results: T[] = [] as any;
  while (true) {
    const res = parser(target, pos);
    if (res[0]) {
      results.push(res[1]);
      pos = res[2];
    } else {
      return [true, results, pos];
    }
  }
};

const map = <T, U>(parser: Parser<T>, mapFn: (val: T) => U): Parser<U> => (
  target,
  pos,
) => {
  const result = parser(target, pos);
  if (result[0]) {
    return [result[0], mapFn(result[1]), result[2]];
  } else {
    return result;
  }
};

const divMultOp = () => oneOf(['*', '/'].map(s => terminate(s)));

const addSubOp = () => oneOf(['+', '-'].map(s => terminate(s)));

const oneNine = (): Parser<string> =>
  oneOf(['1', '2', '3', '4', '5', '6', '7', '8', '9'].map(s => terminate(s)));

const digitChar = () => oneOf([oneNine(), terminate('0')]);
const intLitNoSign = map(
  seq<[string, string]>([
    oneNine(),
    map(many(digitChar()), res => res.join('')),
  ]),
  ([fst, rest]): number => parseInt(fst + rest, 10),
);

const intLit = () =>
  oneOf([
    map(
      seq<[string, number]>([terminate('-'), intLitNoSign]),
      ([, num]) => -num,
    ),
    intLitNoSign,
  ]);

type Term = BinopExpr | number;
type BinopExpr = {op: string; lhs: Term; rhs: Term};

const term = (): Parser<Term> =>
  oneOf<Term>([
    map(
      seq<[string, Term, string]>([terminate('('), lazy(expr), terminate(')')]),
      ([, binopExpr]) => binopExpr,
    ),
    intLit(),
  ]);

const divMultExpr = (): Parser<Term> =>
  oneOf([
    map(
      seq<[Term, string, Term]>([term(), divMultOp(), lazy(divMultExpr)]),
      ([lhs, op, rhs]) => ({op, lhs, rhs}),
    ),
    term(),
  ]);

const addSubExpr = (): Parser<Term> =>
  oneOf([
    map(
      seq<[Term, string, Term]>([divMultExpr(), addSubOp(), lazy(addSubExpr)]),
      ([lhs, op, rhs]) => ({op, lhs, rhs}),
    ),
    divMultExpr(),
  ]);

const expr = addSubExpr;

const parse = (s: string) => expr()(s, 0);

const evaluate = (ast: Term): number => {
  if (typeof ast === 'number') {
    return ast;
  } else {
    const {op, lhs, rhs} = ast;
    switch(op) {
      case '*': return evaluate(lhs) * evaluate(rhs);
      case '/': return evaluate(lhs) / evaluate(rhs);
      case '+': return evaluate(lhs) + evaluate(rhs);
      case '-': return evaluate(lhs) - evaluate(rhs);
      default: return NaN;
    }
  }
};

const source = '-12+23';
const [ok, ast, pos] = parse(source);
if (!ok || pos !== source.length) {
  // show error
  console.log(source);
  console.log(' '.repeat(pos) + '^', 'unexpected char');
} else if (ast !== null) {
  // evaluate ast
  console.log(ast);
  console.log(evaluate(ast));
}