Шаг 42.
Python: сборник рецептов. Строки и текст. Написание простого парсера на основе метода рекурсивного спуска (окончание)

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

Обсуждение

    Парсинг - это обширная тема, освоение которой обычно занимает у студентов первые три недели курса изучения компиляторов. Если вы ищете, где бы почерпнуть знания о грамматиках, алгоритмах парсинга и прочую подобную информацию, обратитесь к книгам о компиляторах. Нет нужды говорить, что все это втиснуть сюда просто невозможно.

    Тем не менее общая идея парсера на основе рекурсивного спуска проста. Для начала вы берете каждое правило грамматики и превращаете его в функцию или метод. Если ваша грамматика выглядит так: 

expr ::= term { ('+'|'-') term }* 
term ::= factor { ('*'|'/') factor }* 
factor ::= '(' expr ')'
     | NUM
то вы начинаете с превращения ее в такой набор методов: 
class ExpressionEvaluator:
    .   .   .   .
    def expr(self):
         .   .   .   .
    def term(self):
         .   .   .   .
    def factor(self):
         .   .   .   .

    Задача каждого метода проста: он должен пройти слева направо по каждой части грамматического правила, потребляя токены в процессе. Цель метода - либо потребить правило, либо сгенерировать синтаксическую ошибку в случае застревания. Чтобы реализовать это, применяются следующие приемы:

    Хотя здесь мы показали простой пример, парсеры на основе рекурсивного спуска могут быть использованы для создания весьма сложных парсеров. Например, код самого Python интерпретируется парсером на основе метода рекурсивного спуска. Если вы заинтересовались, то можете залезть в файл Grammar/Grammar в исходном коде Python и взглянуть на лежащую в основе грамматику. При всем при этом, конечно, в ручном создании парсеров множество ограничений и ловушек.

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

items ::= items ',' item 
     | item

    Чтобы сделать это, вы могли бы использовать метод items(): 

def items(self):
    itemsval = self.items() 
    if itemsval and self._accept(','): 
        itemsva1.append(self.item()) 
    else:
        itemsval = [self.item()]

    Единственная проблема в том, что это не работает. Такой код вылетит с ошибкой бесконечной рекурсии.

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

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

factor ::= '(' expression ')'
      | NUM

    Эта грамматика технически "работает", но она не соблюдает стандартные правила порядка вычисления арифметических выражений. Например, для выражения "3 + 4 * 5" оно выдаст результат 35 вместо правильного 23. Чтобы решить эту проблему, нужно использовать отдельные правила expr и term.

    Для по-настоящему сложных грамматик лучше использовать инструменты парсинга типа PyParsing (https://pypi.org/project/pyparsing/) или PLY (http://www.dabeaz.com/ply/index.html). Вот как выглядит код "вычислителя" выражений, созданный с применением PLY: 

from ply.lex import lex
from ply.yacc import yacc

# Список токенов
tokens = ['NUM', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN']
# Игнорируемые символы
t_ignore = ' \t\n'
# Определения токенов (в форме регулярных выражений)
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'


# Функции обработки токенов
def t_NUM(t):
    r'\d+'
    t.value = int(t.value)
    return t


# Обработчик ошибок
def t_error(t):
    print('Bad character: {!r}'.format(t.value[0]))
    t.skip(1)


# Создание лексера
lexer = lex()


# Правила грамматики и функции-обработчики
def p_expr(p):
    '''
    expr : expr PLUS term
    | expr MINUS term
    '''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]


def p_expr_term(p):
    '''
    expr : term
    '''
    p[0] = p[1]


def p_term(p):
    '''
    term : term TIMES factor
    | term DIVIDE factor
    '''
    if p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]


def p_term_factor(p):
    '''
    term : factor
    '''
    p[0] = p[1]


def p_factor(p):
    '''
    factor : NUM
    '''
    p[0] = p[1]


def p_factor_group(p):
    '''
    factor : LPAREN expr RPAREN
    '''
    p[0] = p[2]


def p_error(p):
    print('Syntax error')


parser = yacc()
print(parser.parse('2'))
print(parser.parse('2+3'))
print(parser.parse('2+(3+4)*5'))
Архив с файлом можно взять здесь.

    В этой программе вы обнаружите, что все определено так же, как и в ранее написанном парсере, но на намного более высоком уровне. Вы просто пишете регулярные выражения для токенов и высокоуровневые функции-обработчики, которые выполняются, когда возникают совпадения по различным правилам грамматики. А вся механика работы парсера, приема токенов и т. д. полностью реализована в библиотеке.

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

2
5
37

    Если вы хотите сделать свою жизнь более захватывающей, начните писать парсеры и компиляторы. Повторимся, книги про компиляторы предлагают кучу низкоуровневых подробностей и тонны теории. Множество полезных ресурсов и всякой информации вы также найдете в сети. А в Python есть модуль ast, на который тоже стоит посмотреть.

    На следующем шаге мы рассмотрим выполнение текстовых операций над байтовыми строками.




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