На этом шаге мы рассмотрим реализвцию такого парсера.

Задача

Вам нужно распарсить текст в соответствии с грамматическими правилами и выполнить действия или построить абстрактное синтаксическое дерево, представляющее входные данные.

Решение

В этой задаче мы сосредоточены на парсинге текста в соответствии с некоторой определенной грамматикой. Чтобы это сделать, вы должны начать с формальной спецификации грамматики в форме BNF (БНФ, форма Бэкуса-Наура) или EBNF (РБНФ, расширенная форма Бэкуса-Наура). Например, грамматика для простых арифметических выражений может выглядеть так:

expr ::= expr + term 
     | expr - term 
     | term

term ::= term * factor 
     | term / factor 
     | factor

factor ::= ( expr )
     | NUM

А вот альтернативная форма РБНФ:

expr ::= term { (+|-) term }*

term ::= factor { (*|/) factor }*

factor ::= ( expr )
     | NUM

В EBNF части правил, заключенные в { ... }*, являются необязательными. * означает ноль и более повторений (то есть имеет такое значение, как и в регулярных выражениях).

Теперь, если вы незнакомы с механизмом работы BNF, думайте о ней как об определении правил замены или подстановки, где символы слева могут быть заменены символами справа (или наоборот). В общем, во время парсинга вы пытаетесь сопоставить входящий текст с грамматикой, делая различные подстановки и расширения с использованием BNF. Чтобы проиллюстрировать это, предположим, что вы парсите выражение 3 + 4 * 5. Это выражение должно быть сначала разбито на поток токенов с использованием описанных в предыдущем рецепте приемов. Результатом будет последовательность токенов:

NUM + NUM * NUM

С этого момента парсинг начинает пытаться сопоставить грамматику с входящими токенами, делая подстановки:

expr
expr ::= term { (+|-) term }*
expr ::= factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM { (*|/) factor }* { (+|-) term }*
expr ::= NUM { (+|-) term }*
expr ::= NUM + term { (+|-) term }*
expr ::= NUM + factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM { (*|/) factor}* { (+|-) term }*
expr ::= NUM + NUM * factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM * NUM { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM * NUM { (+|-) term }*
expr ::= NUM + NUM * NUM

Чтобы пройти по всем шагам подстановки и разобраться, придется потратить время, но в целом они работают так: смотрят на входящие данные и пытаются сопоставить их с правилами грамматики. Первый входящий токен - это NUM, поэтому подстановки сначала сосредоточиваются на поиске совпадений с этой частью. Когда совпадение найдено, внимание переходит к следующему токену + и т. д. Некоторые части правой стороны (например, { (*/) factor }*) исчезают, когда определено, что они не совпадают со следующим токеном. Парсинг проходит успешно, если правая сторона достаточно полна, чтобы охватить все входящие токены.

Со всей вышеизложенной вводной информацией перейдем к простому рецепту построения парсера выражений, работающего по методу рекурсивного спуска:

import re
import collections

# Определение токенов
NUM = r'(?P<NUM>\d+)'
PLUS = r'(?P<PLUS>\+)'
MINUS = r'(?P<MINUS>-)'
TIMES = r'(?P<TIMES>\*)'
DIVIDE = r'(?P<DIVIDE>/)'
LPAREN = r'(?P<LPAREN>\()'
RPAREN = r'(?P<RPAREN>\))'
WS = r'(?P<WS>\s+)'
master_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES,
                                  DIVIDE, LPAREN, RPAREN, WS]))
# Токенизатор
Token = collections.namedtuple('Token', ['type', 'value'])


def generate_tokens(text):
    scanner = master_pat.scanner(text)
    for m in iter(scanner.match, None):
        tok = Token(m.lastgroup, m.group())
        if tok.type != 'WS':
            yield tok


# Парсер
class ExpressionEvaluator:
    '''
    Реализация парсера на базе рекурсивного спуска.
    Каждый метод реализует одно правило грамматики.
    Использует метод ._accept(), чтобы протестировать
    и принять текущий токен предварительного просмотра.
    Использует метод ._expect() для точного совпадения
    и отбрасывания следующего токена на входе
    (или возбуждает SyntaxError, если он не совпадает).
   '''

    def parse(self, text):
        self.tokens = generate_tokens(text)
        # Последний потребленный символ
        self.tok = None
        # Следующий токенизированный символ
        self.nexttok = None
        # Загрузить первый токен предварительного просмотра
        self._advance()
        return self.expr()

    def _advance(self):
        'Продвинуться на один токен вперед'
        self.tok, self.nexttok = self.nexttok, next(self.tokens, None)

    def _accept(self, toktype):
        'Проверить и потребить следующий токен, если он совпадает с toktype'
        if self.nexttok and self.nexttok.type == toktype:
            self._advance()
            return True
        else:
            return False

    def _expect(self, toktype):
        'Потребить следующий токен, если он совпадает с toktype, или возбудить SyntaxError'
        if not self._accept(toktype):
            raise SyntaxError('Expected ' + toktype)

    # Далее следуют правила грамматики
    def expr(self):
        "expression ::= term { ('+'|'-') term }*"
        exprval = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term()
            if op == 'PLUS':
                exprval += right
            elif op == 'MINUS':
                exprval -= right
        return exprval

    def term(self):
        "term ::= factor { ('*'|'/') factor }*"
        termval = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor()
            if op == 'TIMES':
                termval *= right
            elif op == 'DIVIDE':
                termval /= right
        return termval

    def factor(self):
        "factor ::= NUM | ( expr )"
        if self._accept('NUM'):
            return int(self.tok.value)
        elif self._accept('LPAREN'):
            exprval = self.expr()
            self._expect('RPAREN')
            return exprval
        else:
            raise SyntaxError('Expected NUMBER or LPAREN')


e = ExpressionEvaluator()
print(e.parse('2'))
print(e.parse('2 + 3'))
print(e.parse('2 + 3 * 4'))
print(e.parse('2 + (3 + 4) * 5'))
print(e.parse('2 + (3 + * 4)'))

Архив с файлом можно взять здесь.

Результат выполнения приложения:

2
5
14
37
Traceback (most recent call last):
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 108, in <module>
    print(e.parse('2 + (3 + * 4)'))
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 47, in parse
    return self.expr()
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 72, in expr
    right = self.term()
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 81, in term
    termval = self.factor()
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 96, in factor
    exprval = self.expr()
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 72, in expr
    right = self.term()
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 81, in term
    termval = self.factor()
  File "C:\Users\...\PycharmProjects\Recipes\pr41_1.py", line 100, in factor
    raise SyntaxError('Expected NUMBER or LPAREN')
SyntaxError: Expected NUMBER or LPAREN

Если вы хотите сделать что-то другое, а не только произвести простое вычисление, вам нужно изменить класс ExpressionEvaluator. Например, вот альтернативная реализация, которая конструирует простое дерево парсинга:

class ExpressionTreeBuilder(ExpressionEvaluator):
    def expr(self):
        "expression ::= term { ('+'|'-') term }"
        exprval = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term()
            if op == 'PLUS':
                exprval = ('+', exprval, right)
            elif op == 'MINUS':
                exprval = ('-', exprval, right)
        return exprval

    def term(self):
        "term ::= factor { ('*'|'/') factor }"
        termval = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor()
            if op == 'TIMES':
                termval = ('*', termval, right)
            elif op == 'DIVIDE':
                termval = ('/', termval, right)
        return termval

    def factor(self):
        'factor ::= NUM | ( expr )'
        if self._accept('NUM'):
            return int(self.tok.value)
        elif self._accept('LPAREN'):
            exprval = self.expr()
            self._expect('RPAREN')
            return exprval
        else:
            raise SyntaxError('Expected NUMBER or LPAREN')


e = ExpressionTreeBuilder()
print(e.parse('2 + 3'))
print(e.parse('2 + 3 * 4'))
print(e.parse('2 + (3 + 4) * 5'))
print(e.parse('2 + 3 + 4'))

Архив с файлом можно взять здесь.

Результат работы приложения:

('+', 2, 3)
('+', 2, ('*', 3, 4))
('+', 2, ('*', ('+', 3, 4), 5))
('+', ('+', 2, 3), 4)

На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг