pc.py

from __future__ import annotations
from typing import *

@no_type_check
def forward(f):
    resolved = None
    def c(*args, **kwargs):
        if not resolved:
            resolved = f()
        return resolved(*args, **kwargs)
    return c

# S denotes the type of a token in the input sequence
S = TypeVar('S')

# T, U are the type variables for produced values
T = TypeVar('T')
U = TypeVar('U')

# A map that maps a sequence of tokens of type S to a tuple that consists of
# a produced value T and a remaining sequence of tokens of type S is a parser.
Parser = Callable[[Sequence[S]], Tuple[T, Sequence[S]]]

class ParseException(Exception, Generic[S]):
    def __init__(self, got: Sequence[S], expected: str, rule:Optional[str] = None) -> None:
        self.got = got
        self.expected = expected
        self.rule = rule

# Generic combinators

def pure(r: T) -> Parser[S, T]:
    def _parser(s: Sequence[S]) -> Tuple[T, Sequence[S]]:
        return r, s
    return _parser

def any(seq: Sequence[S]) -> Tuple[S, Sequence[S]]:
    try:
        return seq[0], seq[1:]
    except IndexError:
        pass
    raise ParseException('<eof>', '<any>', 'any')

def eof(seq: Sequence[S]) -> Tuple[None, Sequence[S]]:
    try:
        got = seq[0:1]
    except IndexError:
        return None, seq
    else:
        raise ParseException(got, '<eof>', 'eof')

def chain(*parsers: Parser[S, T]) -> Parser[S, List[T]]:
    def _parser(seq: Sequence[S]) -> Tuple[List[T], Sequence[S]]:
        ret = []
        for parser in parsers:
            res, seq = parser(seq)
            ret.append(res)
        return ret, seq
    return _parser

def options(*parsers: Parser[S, T]) -> Parser[S, T]:
    def _parser(seq: Sequence[S]) -> Tuple[T, Sequence[S]]:
        for parser in parsers:
            try:
                return parser(seq)
            except ParseException:
                pass
        raise ParseException(seq, '<options>', 'options{self.parsers!r}')
    return _parser

def satisfy(c: Callable[[S], bool]) -> Parser[S, S]:
    def _parser(seq: Sequence[S]) -> Tuple[S, Sequence[S]]:
        r, seq_new = any(seq)
        if not c(r):
            raise ParseException(seq, f'<satisfy {c!r}>', f'satisfy({c!r})')
        return r, seq_new
    return _parser

def many(parser: Parser[S, T]) -> Parser[S, List[T]]:
    def _parser(seq: Sequence[S]) -> Tuple[List[T], Sequence[S]]:
        ret = []
        try:
            while True:
                res, seq = parser(seq)
                ret.append(res)
        except ParseException:
            pass
        return ret, seq
    return _parser

def some(parser: Parser[S, T]) -> Parser[S, List[T]]:
    def _parser(seq: Sequence[S]) -> Tuple[List[T], Sequence[S]]:
        res, seq = parser(seq)
        ret = [res]
        try:
            while True:
                res, seq = parser(seq)
                ret.append(res)
        except ParseException:
            pass
        return ret, seq
    return _parser

def exact_n(parser: Parser[S, T], n: int) -> Parser[S, List[T]]:
    def _parser(seq: Sequence[S]) -> Tuple[List[T], Sequence[S]]:
        ret = []
        for i in range(n):
            res, seq = parser(seq)
            ret.append(res)
        _, seq = fail_if(parser)(seq)
        return ret, seq
    return _parser

def fail_if(parser: Parser[S, T]) -> Parser[S, None]:
    def _parser(seq: Sequence[S]) -> Tuple[None, Sequence[S]]:
        try:
            _, seq_new = parser(seq)
        except ParseException:
            return None, seq
        raise ParseException(seq, f'<not {parser!r}>', f'fail_if({parser!r})')
    return _parser

def lookahead(parser: Parser[S, T]) -> Parser[S, T]:
    def _parser(seq: Sequence[S]) -> Tuple[T, Sequence[S]]:
        res, _ = parser(seq)
        return res, seq
    return _parser

def sep_by(parser: Parser[S, T], sep: Parser[S, U]) -> Parser[S, List[T]]:
    def _parser(seq: Sequence[S]) -> Tuple[List[T], Sequence[S]]:
        res, seq = parser(seq)
        ret = [res]
        try:
            while True:
                _, seq = sep(seq)
                res, seq = parser(seq)
                ret.append(res)
        except ParseException:
            pass
        return ret, seq
    return _parser

# str-specific combinators

alpha = satisfy(str.isalpha)
space = satisfy(str.isspace)
numeric = satisfy(str.isnumeric)

optional = lambda parser: options(parser, pure(None))

def token(parser: Parser[str, T]) -> Parser[str, T]:
    def _parser(seq: Sequence[str]) ->  Tuple[T, Sequence[str]]:
        res: T
        res, seq = parser(seq)
        try:
            while True:
                _, seq = space(seq)
        except ParseException:
            pass
        return res, seq
    return _parser