Практика 6.2 — Расширенные комбинаторы regex

Дополнительные задания по комбинаторному и функциональному подходу.

Источник: pr_Python/pr_Python/pract6_2.ipynb

4. Комбинаторы регулярных выражений

Реализуйте простой встроенный язык подмножества регулярных выражений с помощью ФВП. Комбинаторы имеют следующий общий вид:

def comb(param, ...):
    def parse(text, ...):
        ...
        return new_text, ...
    return parse

python

def char(c):
    def parse(text, pos):
        if pos >= len(text) or text[pos] != c:
            return text, pos
        return text, pos + 1
    return parse

def seq(*parsers):
    def parse(text, pos):
        for p in parsers:
            text, pos = p(text, pos)
            if pos == -1:
                return text, pos
        return text, pos
    return parse

def alt(*parsers):
    def parse(text, pos):
        for p in parsers:
            new_text, new_pos = p(text, pos)
            if new_pos != -1:
                return new_text, new_pos
        return text, -1
    return parse

def rep(p):
    def parse(text, pos):
        while pos < len(text):
            text, pos = p(text, pos)
        return text, pos
    return parse

def opt(p):
    def parse(text, pos):
        new_text, new_pos = p(text, pos)
        return new_text, new_pos if new_pos != -1 else pos
    return parse


parse_a = char('a')
parse_b = char('b')

parser = seq(rep(parse_a), opt(parse_b))

result = parser("aaabbaa", 0)
if result[1] == -1:
    print("Failed to parse")
else:
    print("Parsed successfully")

4.1. (уровень сложности: высокий)

Реализуйте комбинаторы sym (разобрать символ) и seq (разобрать последовательность).

Пример использования:

text = 'abc'
re1 = seq(sym('a'), sym('b'), sym('c'))
re2 = seq(sym('a'), sym('z'), sym('c'))

print(re1(text) is not None)
print(re2(text) is not None)

True
False

python

def sym(c):
    def parse(text, pos):
        if pos < len(text) and text[pos] == c:
            return pos + 1
        return None
    return parse

def seq(*parsers):
    def parse(text, pos):
        for p in parsers:
            pos = p(text, pos)
            if pos is None:
                return None
        return pos
    return parse

text = 'abc'
re1 = seq(sym('a'), sym('b'), sym('c'))
re2 = seq(sym('a'), sym('z'), sym('c'))

print(re1(text) is not None)
print(re2(text) is not None)

4.2. (уровень сложности: средний)

Реализуйте комбинатор range_of (разобрать диапазон символов).

Пример использования:

digit = range_of('0', '9')
number = seq(digit, digit)

print(number('42') is not None)
print(number('ab') is not None)

True
False

python

def range_of(start, end):
    def parse(text, pos):
        if pos < len(text) and start <= text[pos] <= end:
            return pos + 1
        return None
    return parse

def seq(*parsers):
    def parse(text, pos):
        for p in parsers:
            pos = p(text, pos)
            if pos is None:
                return None
        return pos
    return parse

digit = range_of('0', '9')
number = seq(digit, digit)

print(number('42') is not None)
print(number('ab') is not None)

4.3. (уровень сложности: высокий)

Реализуйте комбинатор alt (альтернатива).

Пример использования:

digit = range_of('0', '9')
hex_digit = alt(digit, range_of('a', 'f'), range_of('A', 'F'))
space = alt(sym(' '), sym('\n'), sym('\t'))
hex_color = seq(sym('#'), hex_digit, hex_digit, hex_digit, hex_digit, hex_digit, hex_digit)

print(hex_color('#ffaa43') is not None)
print(hex_color('#xxxxxx') is not None)

True
False

python

def alt(*parsers):
    def parse(text, pos):
        for p in parsers:
            new_pos = p(text, pos)
            if new_pos is not None:
                return new_pos
        return None
    return parse

def range_of(start, end):
    def parse(text, pos):
        if pos < len(text) and start <= text[pos] <= end:
            return pos + 1
        return None
    return parse

def sym(char):
    def parse(text, pos):
        if pos < len(text) and text[pos] == char:
            return pos + 1
        return None
    return parse

def seq(*parsers):
    def parse(text, pos):
        for p in parsers:
            pos = p(text, pos)
            if pos is None:
                return None
        return pos
    return parse

digit = range_of('0', '9')
hex_digit = alt(digit, range_of('a', 'f'), range_of('A', 'F'))
space = alt(sym(' '), sym('\n'), sym('\t'))
hex_color = seq(sym('#'), hex_digit, hex_digit, hex_digit, hex_digit, hex_digit, hex_digit)

print(hex_color('#ffaa43') is not None)
print(hex_color('#xxxxxx') is not None)

4.4. (уровень сложности: высокий)

Реализуйте комбинатор group (группировка) для извлечения разобранных фрагментов.

Пример использования:

digit = range_of('0', '9')
hex_digit = alt(digit, range_of('a', 'f'), range_of('A', 'F'))
space = alt(sym(' '), sym('\n'), sym('\t'))
hex_color = seq(sym('#'), group(seq(hex_digit, hex_digit, hex_digit, hex_digit, hex_digit, hex_digit)))
hex_colors = seq(hex_color, sym(' '), hex_color)

print(hex_colors('#ffaa43 #123456', []))

('', ['ffaa43', '123456'])

python

def group(rule):
    def inner(text, start):
        result, end = rule(text, start)
        if result:
            return ([result], end)
        return (result, end)
    return inner

def alt(*args):
    pass

def range_of(start, end):
    pass

def sym(char):
    pass

def seq(*args):
    pass

digit = range_of('0', '9')
hex_digit = alt(digit, range_of('a', 'f'), range_of('A', 'F'))
space = alt(sym(' '), sym('\n'), sym('\t'))
hex_color = seq(sym('#'), group(seq(hex_digit, hex_digit, hex_digit, hex_digit, hex_digit, hex_digit)))
hex_colors = seq(hex_color, sym(' '), hex_color)

def parse_hex_colors(text, start):
    result, end = hex_colors(text, start)
    return ('', result)

print(parse_hex_colors('#ffaa43 #123456', 0))

Практика 6 — Комбинаторы и функциональный стиль