<commit_before># -*- coding: utf-8 -*-

# Copyright (c) 2008/2011 <NAME>
#
# Permission is hereby granted, free of charge, to any person obtaining
# a copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, sublicense, and/or sell copies of the Software, and to
# permit persons to whom the Software is furnished to do so, subject to
# the following conditions:
#
# The above copyright notice and this permission notice shall be included
# in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

'''A recurisve descent parser library based on functional combinators.

Basic combinators are taken from Harrison's book ["Introduction to Functional
Programming"][1] and translated from ML into Python. See also [a Russian
translation of the book][2].

  [1]: http://www.cl.cam.ac.uk/teaching/Lectures/funprog-jrh-1996/
  [2]: http://code.google.com/p/funprog-ru/

A parser `p` is represented by a function of type:

    p :: Sequence(a), State -> (b, State)

that takes as its input a sequence of tokens of arbitrary type `a` and a
current parsing state and return a pair of a parsed token of arbitrary type
`b` and the new parsing state.

The parsing state includes the current position in the sequence being parsed and
the position of the rightmost token that has been consumed while parsing.

Parser functions are wrapped into an object of the class `Parser`. This class
implements custom operators `+` for sequential composition of parsers, `|` for
choice composition, `>>` for transforming the result of parsing. The method
`Parser.parse` provides an easier way for invoking a parser hiding details
related to a parser state:

    Parser.parse :: Parser(a, b), Sequence(a) -> b

Altough this module is able to deal with a sequences of any kind of objects, the
recommended way of using it is applying a parser to a `Sequence(Token)`.
`Token` objects are produced by a regexp-based tokenizer defined in
`funcparserlib.lexer`. By using it this way you get more readable parsing error
messages (as `Token` objects contain their position in the source file) and good
separation of lexical and syntactic levels of the grammar. See examples for more
info.
'''

__all__ = [
    'some', 'a', 'many', 'fwd', 'eof', 'maybe', 'skip', 'oneplus', 'pure',
    'name_parser_vars', 'SyntaxError', 'ParserError',
]

from funcparserlib.util import SyntaxError

class ParserError(SyntaxError):
    '''User-visible parsing error.'''
    pass

class GrammarError(Exception):
    '''Raised when the grammar definition itself contains errors.'''
    pass

class NoParseError(Exception):
    '''Internal no-parse exception for backtracking.'''

    def __init__(self, msg='', state=None):
        self.msg = msg
        self.state = state

    def __unicode__(self):
        return self.msg

    def __str__(self):
        return self.msg.encode()

class Parser(object):
    '''A callable parser object that defines some operators for parser
    composition and the `parse()` function as its external interface.
    '''

    def parse(self, tokens):
        '''Applies the parser to the tokens producing a parsing result.

        It provides a way to invoke a parser hiding details related to the
        parser state. Also it makes error messages more readable by specifying
        the position of the rightmost token that has been reached.
        '''
        p = non_halting(self)
        if p:
            raise GrammarError("parser '%s' does not halt, please fix your "
                               'grammar; see the FAQ for details' %
                               ebnf_rule(p))
        try:
            (tree, _) = self(tokens, State())
            return tree
        except NoParseError, e:
            max = e.state.max
            tok = tokens[max] if max < len(tokens) else '<EOF>'
            raise ParserError(u'%s: %s' % (e.msg, tok),
                              getattr(tok, 'pos', None))

    def __call__(self, tokens, s):
        return GrammarError('an abstract parser cannot be called')

    def __add__(self, other):
        '''A sequential composition of parsers.

        The resulting parser merges the parsed sequence into a single `_Tuple`
        unless the user explicitely prevents it. See also `skip()` and `>>`
        combinators.
        '''
        return _Seq(self, other)

    def __or__(self, other):
        '''A choice composition of two parsers.'''
        return _Alt(self, other)

    def __rshift__(self, f):
        '''An interpreting parser.

        Given a function from `b` to `c`, transforms a parser of `b` into a
        parser of `c`. It is useful for transorming a parser value into another
        value for making it a part of a parse tree or an AST.
        '''
        return _Map(self, f)

    def __str__(self):
        return getattr(self, 'name', self.ebnf())

    def named(self, name):
        'Specifies the name of the parser.'
        self.name = name
        return self

    def ebnf(self):
        'The EBNF grammar expression for the parser.'
        return GrammarError('no EBNF expression for an abstract parser')

class _Map(Parser):
    '''An interpreting parser.'''

    def __init__(self, p, f):
        self.p = p
        self.f = f

    def __call__(self, tokens, s):
        (v, s2) = self.p(tokens, s)
        return (self.f(v), s2)

    def ebnf(self):
        return str(self.p)

class _Seq(Parser):
    '''A sequential composition of parsers.'''

    def __init__(self, p1, p2):
        if isinstance(p1, _Seq):
            self.ps = p1.ps + [p2]
        else:
            self.ps = [p1, p2]

    def __call__(self, tokens, s):
        def magic(v1, v2):
            vs = [v for v in [v1, v2] if not isinstance(v, _Ignored)]
            length = len(vs)
            if length == 1:
                return vs[0]
            elif length == 2:
                if isinstance(vs[0], _Tuple):
                    return _Tuple(v1 + (v2,))
                else:
                    return _Tuple(vs)
            else:
                return _Ignored(())
        vs = []
        for p in self.ps:
            (v, s) = p(tokens, s)
            vs.append(v)
        return (reduce(magic, vs), s)

    def ebnf(self):
        return ', '.join(ebnf_brackets(str(x)) for x in self.ps)

class _Alt(Parser):
    '''A choice composition of parsers.'''

    def __init__(self, p1, p2):
        if isinstance(p1, _Alt):
            self.ps = p1.ps + [p2]
        else:
            self.ps = [p1, p2]

    def __call__(self, tokens, s):
        e = NoParseError('no error', s)
        for p in self.ps:
            try:
                return p(tokens, s)
            except NoParseError, npe:
                e = npe
                s = State(s.pos, e.state.max)
                continue
        raise e
<commit_msg>Replaced reduce() with an imperative-style fold<commit_after># -*- coding: utf-8 -*-

# Copyright (c) 2008/2011 <NAME>
#
# Permission is hereby granted, free of charge, to any person obtaining
# a copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, sublicense, and/or sell copies of the Software, and to
# permit persons to whom the Software is furnished to do so, subject to
# the following conditions:
#
# The above copyright notice and this permission notice shall be included
# in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

'''A recurisve descent parser library based on functional combinators.

Basic combinators are taken from Harrison's book ["Introduction to Functional
Programming"][1] and translated from ML into Python. See also [a Russian
translation of the book][2].

  [1]: http://www.cl.cam.ac.uk/teaching/Lectures/funprog-jrh-1996/
  [2]: http://code.google.com/p/funprog-ru/

A parser `p` is represented by a function of type:

    p :: Sequence(a), State -> (b, State)

that takes as its input a sequence of tokens of arbitrary type `a` and a
current parsing state and return a pair of a parsed token of arbitrary type
`b` and the new parsing state.

The parsing state includes the current position in the sequence being parsed and
the position of the rightmost token that has been consumed while parsing.

Parser functions are wrapped into an object of the class `Parser`. This class
implements custom operators `+` for sequential composition of parsers, `|` for
choice composition, `>>` for transforming the result of parsing. The method
`Parser.parse` provides an easier way for invoking a parser hiding details
related to a parser state:

    Parser.parse :: Parser(a, b), Sequence(a) -> b

Altough this module is able to deal with a sequences of any kind of objects, the
recommended way of using it is applying a parser to a `Sequence(Token)`.
`Token` objects are produced by a regexp-based tokenizer defined in
`funcparserlib.lexer`. By using it this way you get more readable parsing error
messages (as `Token` objects contain their position in the source file) and good
separation of lexical and syntactic levels of the grammar. See examples for more
info.
'''

__all__ = [
    'some', 'a', 'many', 'fwd', 'eof', 'maybe', 'skip', 'oneplus', 'pure',
    'name_parser_vars', 'SyntaxError', 'ParserError',
]

from funcparserlib.util import SyntaxError

class ParserError(SyntaxError):
    '''User-visible parsing error.'''
    pass

class GrammarError(Exception):
    '''Raised when the grammar definition itself contains errors.'''
    pass

class NoParseError(Exception):
    '''Internal no-parse exception for backtracking.'''

    def __init__(self, msg='', state=None):
        self.msg = msg
        self.state = state

    def __unicode__(self):
        return self.msg

    def __str__(self):
        return self.msg.encode()

class Parser(object):
    '''A callable parser object that defines some operators for parser
    composition and the `parse()` function as its external interface.
    '''

    def parse(self, tokens):
        '''Applies the parser to the tokens producing a parsing result.

        It provides a way to invoke a parser hiding details related to the
        parser state. Also it makes error messages more readable by specifying
        the position of the rightmost token that has been reached.
        '''
        p = non_halting(self)
        if p:
            raise GrammarError("parser '%s' does not halt, please fix your "
                               'grammar; see the FAQ for details' %
                               ebnf_rule(p))
        try:
            (tree, _) = self(tokens, State())
            return tree
        except NoParseError, e:
            max = e.state.max
            tok = tokens[max] if max < len(tokens) else '<EOF>'
            raise ParserError(u'%s: %s' % (e.msg, tok),
                              getattr(tok, 'pos', None))

    def __call__(self, tokens, s):
        return GrammarError('an abstract parser cannot be called')

    def __add__(self, other):
        '''A sequential composition of parsers.

        The resulting parser merges the parsed sequence into a single `_Tuple`
        unless the user explicitely prevents it. See also `skip()` and `>>`
        combinators.
        '''
        return _Seq(self, other)

    def __or__(self, other):
        '''A choice composition of two parsers.'''
        return _Alt(self, other)

    def __rshift__(self, f):
        '''An interpreting parser.

        Given a function from `b` to `c`, transforms a parser of `b` into a
        parser of `c`. It is useful for transorming a parser value into another
        value for making it a part of a parse tree or an AST.
        '''
        return _Map(self, f)

    def __str__(self):
        return getattr(self, 'name', self.ebnf())

    def named(self, name):
        'Specifies the name of the parser.'
        self.name = name
        return self

    def ebnf(self):
        'The EBNF grammar expression for the parser.'
        return GrammarError('no EBNF expression for an abstract parser')

class _Map(Parser):
    '''An interpreting parser.'''

    def __init__(self, p, f):
        self.p = p
        self.f = f

    def __call__(self, tokens, s):
        (v, s2) = self.p(tokens, s)
        return (self.f(v), s2)

    def ebnf(self):
        return str(self.p)

class _Seq(Parser):
    '''A sequential composition of parsers.'''

    def __init__(self, p1, p2):
        if isinstance(p1, _Seq):
            self.ps = p1.ps + [p2]
        else:
            self.ps = [p1, p2]

    def __call__(self, tokens, s):
        def magic(v1, v2):
            vs = [v for v in [v1, v2] if not isinstance(v, _Ignored)]
            length = len(vs)
            if length == 1:
                return vs[0]
            elif length == 2:
                if isinstance(vs[0], _Tuple):
                    return _Tuple(v1 + (v2,))
                else:
                    return _Tuple(vs)
            else:
                return _Ignored(())
        (p, ps) = (self.ps[0], self.ps[1:])
        (res, s) = p(tokens, s)
        for p in ps:
            (v, s) = p(tokens, s)
            res = magic(res, v)
        return (res, s)

    def ebnf(self):
        return ', '.join(ebnf_brackets(str(x)) for x in self.ps)

class _Alt(Parser):
    '''A choice composition of parsers.'''

    def __init__(self, p1, p2):
        if isinstance(p1, _Alt):
            self.ps = p1.ps + [p2]
        else:
            self.ps = [p1, p2]

    def __call__(self, tokens, s):
        e = NoParseError('no error', s)
        for p in self.ps:
            try:
                return p(tokens, s)
            except NoParseError, npe:
                e = npe
                s = State(s.pos, e.state.max)
                continue
        raise e

{'fraction_non_alphanumeric': 0.0944384739387426, 'fraction_numerical': 0.005910800644814616, 'mean_word_length': 2.4754901960784315, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2238870', 'n_tokens_mistral': 4310, 'n_tokens_neox': 4080, 'n_words': 1781}