» » » Парсеры, обработка текста. Просто о сложном. CFG, BNF, LL(k), LR(k), PEG и другие страшные слова

 

Парсеры, обработка текста. Просто о сложном. CFG, BNF, LL(k), LR(k), PEG и другие страшные слова

Автор: admin от 5-02-2018, 15:55, посмотрело: 145

Наверное, каждому программисту приходилось сталкиваться с задачами вида «прочитать что-то в формате А и произвести с ним некие манипуляции». Будь то json, логи nginx, cfg, sql, yaml, csv или что-то еще. Хорошо, когда можно воспользоваться библиотекой, однако, по разным причинам, это удается не всегда. Тогда и встает вопрос создания собственного парсера для заданного формата. И это, как говорят англичане, часто оказывается PITA (болью в ...). В этой статье я постараюсь облегчить эту боль. Кому интересно, добро пожаловать.
находим их много.


  • Используем parglare. Это библиотека/cli-tool на Python, реализующий LR/GLR парсер c достаточно широким спектром возможностей (инлайн-функции, приоритизация, деревья, внятный анализ грамматики, визуализатор КА, получающегося при обработке грамматики).

    pip install parglare

    Переформулируем наш калькулятор так, как просит parglare

    OPERATOR        : "+ "| "-" | "*" | "/" | =
        STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT
        FLOAT           : INT "." INT
        INT             : (POSITIVE_DIGIT INT | DIGIT ) | DIGIT
        POSITIVE_DIGIT  : "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
        DIGIT           : POSITIVE_DIGIT | "0"

    Достаточно? Сохраним в calc.pg и воспользуемся cli-tool

    pglr --debug check calc.pg
    Error in file "/home/survivor/tests/calc.pg" at position 1,42 => "" | "/" | *=nSTMT    ". Expected: Name or StrTerm or RegExTerm
    

    Упс! кажется, что-то лишнее. Бинго! я зачем-то вставил | = после “/” (нет, я-то знаю, откуда он там (но к теме статьи это не относится) ). Главное в том, что программа нам четко на это указала. Далее после исправления программа поругается еще на отсутствие; в конце обозначения нетерминала и на скобочку в правиле INT. Переформулированный вариант будет выглядеть так:

    STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT | INT;
    OPERATOR        : "+ "| "-" | "*" | "/";
    FLOAT           : INT "." INT;
    INT             : POSITIVE_DIGIT INT | POSITIVE_DIGIT DIGIT | DIGIT;
    POSITIVE_DIGIT  : "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9";
    DIGIT           : POSITIVE_DIGIT | "0";

    В итоге, pglr все нравится и он нам скажет:

    Grammar ok! 

    НО:

    There are 4 Shift/Reduce conflicts.
    Either use 'prefer_shifts' parser mode, try to resolve manually or use GLR parsing.
    There are 7 Reduce/Reduce conflicts.
    Try to resolve manually or use GLR parsing.
    

    Ну, а выше по выводу debug можно прочитать их красивое (и понятное) описание. Ну что ж, давайте подумаем. Во первых, давайте не будем самыми умными и выкинем нафиг positive_digit. Если кто-то напишет 0034 — во первых, он сам себе злобный буратино, а во вторых, большинство ЯП, в том числе Python при конвертации этого в число не скажут нам ничего и просто выдадут 34. Прекрасно, это сильно поможет. Во-вторых, нафиг отсюда разделение на int/float, для простоты предположим что все числа с плавающей точкой. Также, pglr понимает регулярные выражения в BNF, воспользуемся этим. Получим:

     STMT            : "(" STMT ")" | STMT OPERATOR STMT | FLOAT;
    OPERATOR        : "+ "| "-" | "*" | "/";
    FLOAT           : /d+(.d+)?/;

    и по-прежнему

    There are 4 Shift/Reduce conflicts.
    Either use 'prefer_shifts' parser mode, try to resolve manually or use GLR parsing.

    Ну, как бы то ни было, грамматика

    *** GRAMMAR ***
    Terminals:
    +  EOF ) ( FLOAT STOP * / - d+(.d+)? EMPTY
    NonTerminals:
    OPERATOR S' STMT
    Productions:
    0: S' = STMT STOP
    1: STMT = STMT OPERATOR STMT
    2: STMT = ( STMT )
    3: STMT = FLOAT
    4: OPERATOR = + 
    5: OPERATOR = -
    6: OPERATOR = *
    7: OPERATOR = /

    Попробуем реально распарсить что-нибудь.

    from parglare import Grammar
    from parglare import Parser
    
    grammar = Grammar.from_file(‘calc.pg’)
    parser = Parser(grammar, build_tree=True, prefer_shifts=True)
    result = parser.parse('1 + 2 / (3 - 1 + 5)')

    Получаем:

    result
    <NonTerm(start=0, end=19, sym=STMT)>

    можем получить result.children и далее по дереву. Можем заодно подсчитать итоговое выражение, но делать это здесь не будем. Важно, что мы получили доступ к дереву объектов, для терминальных символов так же их “значение” и можем делать с этим все, что пожелаем.

    Если мы хотим поправить конфликтные ситуации, как еще можно разрешить конфликты грамматики?

    Есть несколько вариантов:


    • Решить задачу переформулировав грамматику
      Например, так:

      STMT : TERM | STMT ADDOP TERM ;
      TERM : FACTOR | FACTOR MULOP FACTOR ;
      FACTOR : "(" STMT ")" | NUMBER;
      ADDOP : "+" | "-";
      MULOP : "*"|"/"; 
      NUMBER: /d+(.d+)?/;

      Как видим, задача усложнилась, но не слишком. Тем более, если мы будем делать разбор именно такого дерева, нам будет проще.

    • Использовать средства самого parglare

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

      STMT :  STMT ADDOP STMT {1, left}
      	|  STMT MULOP STMT {2, left}
      | "(" STMT ")" | NUMBER;
      ADDOP : "+" | "-";
      MULOP : "*"|"/"; 
      NUMBER: /d+(.d+)?/;

      Парсится, но работает не правильно. Например, для

      1 + 2 / (3 - 1 + 5)

      получаем (при не-древовидном парсинге)

      ['1', u'+', ['2', u'/', [u'(', ['3', u'-', ['1', u'+', '5']], u')']]]

      что, очевидно, не соответствует ожидаемому результату:

      ['1', u'+', ['2', u'/', [u'(', [['3', u'-', '1'], u'+', '5'], u')']]]



    Мораль — лучше использовать стандартные описанные в BNF моменты. Блестящие и прикольные штуки блестят и прикольны, но не всегда работают. Или я не умею их готовить. А большинство библиотек парсинга — имеют версию alpha | beta.

    По словам автора об этом баге, он происходит из-за того, что, по сути своей, ассоциативность (left) парсера на уровне алгоритма означает — предпочитать reduce, а не shift. То есть, по сути, если есть возможность “обрубить” правило, или продолжить в его рамках — лучше обрубить. Поскольку парсинг идет слева направо, это и означает левую ассоциативность. Причина же ошибки в том, что не определена приоритетность для правил внутри ADDOP/MULOP, что ломает все правило.

    Однако, даже если мы зададим приоритетность (например:

    ADDOP: “+” {1}
    | “-” {1}
    ), работать все равно не будет, уже из-за другой ошибки.

    Напоследок пример с инлайн-функциями, привязываемыми непосредственно к правилам, из документации parglare.

    from parglare import Parser, Grammar
    
    grammar = r"""
    E: E '+' E  {left, 1}
    | E '-' E  {left, 1}
    | E '*' E  {left, 2}
    | E '/' E  {left, 2}
    | E '^' E  {right, 3}
    | '(' E ')'
    | number;
    number: /d+(.d+)?/;
    """
    
    # Define inline functions bound to grammar rule
    actions = {
        "E": [lambda _, nodes: nodes[0] + nodes[2], # for rule[0]  “+”
              lambda _, nodes: nodes[0] - nodes[2], # for rule[1]  “-”
              lambda _, nodes: nodes[0] * nodes[2], # for rule[2]  “*”
              lambda _, nodes: nodes[0] / nodes[2], # for rule[3]  “/”
              lambda _, nodes: nodes[0] ** nodes[2], # for rule[4]  “^”
              lambda _, nodes: nodes[1], # for rule[5]  “()” - just get the middle
              lambda _, nodes: nodes[0]],  # for rule[6]  just get node
        "number": lambda _, value: float(value), # for rule - convert to float
    }
    
    g = Grammar.from_string(grammar)
    parser = Parser(g, debug=True, actions=actions)
    
    result = parser.parse("34 + 4.6 / 2 * 4^2^2 + 78")
    
    print("Result = ", result)
    
    # Output
    # -- Debuging/tracing output with detailed info about grammar, productions,
    # -- terminals and nonterminals, DFA states, parsing progress,
    # -- and at the end of the output:
    # Result = 700.8


  • Дальше попробуем standalone-инструмент ANTLR.

    Установка довольно простая, для linux это

    $ cd /usr/local/lib
    $ curl -O http://www.antlr.org/download/antlr-4.7.1-complete.jar
    $ export CLASSPATH=".:/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH"
    $ alias antlr4='java -Xmx500M -cp "/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH" org.antlr.v4.Tool'
    $ alias grun='java org.antlr.v4.gui.TestRig'

    Для того, чтобы работать на python2, нужно еще доустановить

    pip install antlr4-python2-runtime

    Дальше попробуем сделать для него грамматику. У него чуть отличается формат, поэтому двойные кавычки заменим на одинарные и чуть перепишем регулярное выражение, а так же добавим обозначение для WS, который в предыдущем инструменте задавался по умолчанию. Левую рекурсию в нашем случае можно устранить просто переписав на правую.

    Важный момент! В ANTLR есть правила парсера и грамматические правила. К появлению узла в результирующем AST ведут правила парсинга. Кроме того, существует некоторое различие, что можно/нельзя в грамматических/правилах парсинга. В частности, в правилах парсинга нет регулярных выражений. Кроме того, парсер должен получить входное правило, стартовый нетерминал (вообще, все несколько сложнее, но в нашем случае вполне хватает и этого). Вообще, стоит заметить, что ANTLR имеет довольно мощный синтаксис, так же поддерживает инлайн функции (пусть и несколько в ином формате) и “не попадающие в дерево” нетерминалы и кое-что еще. В итоге, наша грамматика выглядит так:

    grammar calc;
    stmt : term | term addop stmt ;
    term : factor | factor mulop factor ;
    factor : '(' stmt ')' | NUMBER;
    addop : '+' | '-';
    mulop : '*'|'/'; 
    NUMBER: [0-9]+|[0-9]+.[0-9]+;
    WS : [ trn]+  skip ;

    Файл при этом называется calc.g4 (Это важно! название файла должно совпадать с названием грамматики внутри).

    Создадим java-парсер.

    antlr4 calc.g4
    javac calc*.java
    grun calc stmt -gui

    Дальше даем ему какой-то инпут (например, 1 + 2 / (3 - 1 + 5)) и нажимаем конец строки (ctrl-d на *nix, ctrl-z на windows) и смотрим на результат. Нам показали красивое дерево разбора, еще и интерактивное. Можно посмотреть, покрутить узлы, подумать, экспортировать в качестве картинки.

    Создадим python2-парсер:

    antlr4 -Dlanguage=Python2 calc.g4


    Далее, мы можем навесить на грамматику листенеры и наслаждаться.

    import sys
    from antlr4 import *
    from calc_bakLexer import calc_bakLexer
    from calc_bakListener import calc_bakListener
    from calc_bakParser import calc_bakParser
    
    
    class StmtPrinter(calc_bakListener):
        def __init__(self):
            self.map_results = {}
            self.result = 0
    
        def exitStmt(self, ctx):
            print("Oh, a stmt! {}".format(ctx.getText()))
    
    
    
    def main(argv):
        input = FileStream(argv[1])
        print(input)
        lexer = calc_bakLexer(input)
        stream = CommonTokenStream(lexer)
        parser = calc_bakParser(stream)
        tree = parser.stmt()
        printer = StmtPrinter()
        walker = ParseTreeWalker()
        walker.walk(printer, tree)
    
    if __name__ == '__main__':
        main(sys.argv)

    … Наслаждаться неправильно работающей программой. Вернее, правильно, но неожиданно.

    python ./calc_antlr_min.py ./example.antlr 
    1 + 2 / (3 - 1 + 5)
    
    Oh, a stmt! 5
    Oh, a stmt! 1+5
    Oh, a stmt! 3-1+5
    Oh, a stmt! 2/(3-1+5)
    Oh, a stmt! 1+2/(3-1+5)
    

    Как видно, ассоциативность здесь “правая”. А операции сложения-вычитания, умножения-деления — левые. Я честно пытался несколько дней (sic!) найти решение (разумеется, я занимался этим не все время, но в сумме убил на это часов 12-15). Маркеры ассоциативности, кучи мануалов, переформулирование грамматики…. Не получилось. Я уверен, что решение есть. Более того, пример грамматики калькулятора есть здесь. Но я хотел найти своё решение, по возможности, в терминах общей грамматики. В конце концов, целью было НАУЧИТЬСЯ, а не решить задачу.

    И я признаю свою неудачу. Да, задача решаема. Но пользуясь только документацией и поиском на общие темы, мне её решить не удалось. Причины… Во-первых, исключая книгу по ANTLR, доступные в сети источники не отличаются подробностью и выразительностью. Во-вторых, в сети масса материалов по разным (не совместимым) версиям ANTLR. Нет, я все понимаю, развитие и прочее. Но почему-то в процессе знакомства с инструментом у меня сложилось ощущение, что о понятии обратной совместимости автор даже не слышал. В общем, грустно.


  • PEG


    По сути, являются упрощенной формой BNF, но знать об этом программисту, в целом, не обязательно. В отличие от BNF, изначально больше похожи на регулярные выражения. По сути, можно было бы сказать, что это BNF с возможностью использовать регулярные выражения “по стандарту” (причем, что приятно, не только внутри нетерминальной строки, но и в некоторой степени в самом выражении (PEG поддерживает конструкции вида A = B ( X C)* или, к примеру Z = R (K)?, читаемые как “A состоит из B и любого количества повторений X и C, стоящих последовательно” и “Z состоит из R и следующего за ним K 0 или 1 раз”). Но, на мой взгляд, это все же не главное. Главное в том, что PEG изначально спроектирован, как грамматики ПАРСЕРА. А с какой главной проблемой сталкиваются парсеры, в том числе BNF? Неоднозначность выбора! Для решения этой проблемы в PEG присутствует замечательный оператор последовательного или “/”. В отличие от оператора “|”, который описывает равнозначные альтернативы, “/” четко указывает порядок разрешения правила. Например, A / B / C / D указывает: сравнить с A, если не подходит, сравнить с B, если не подходит, сравнить с C и т.д. По этой причине, оперирование PEG-грамматиками ПРОЩЕ. И еще, рекомендация — если вам безразличен порядок выполнения сравнения, лучше писать “/”. Это уменьшит количество неоднозначных для парсера ситуаций. Однако, как и с любым инструментом, с этим следует обращаться с осторожностью.
    Еще, будьте внимательны, создатели PEG-парсеров ещё более подвержены желанию понимать стандарт так, как им хочется, поэтому лексика разных реализаций может существенно различаться.

    Итак, перейдем к практике.

    Используем Arpeggio от автора parglare:

    pip install arpeggio

    Дальше разбираемся с документацией и узнаем, что рекомендованным для работы с AST для этой библиотеки является шаблон посетитель (visitor), весьма похожий на рекомендованный в ANTLR слушатель (listener). К счастью, здесь для всего эксперимента мне хватило часа, все оказалось не сложно:

    from arpeggio.cleanpeg import ParserPEG
    from arpeggio import PTNodeVisitor, EOF, visit_parse_tree
    # Setting up our simple grammar
    calc_grammar = """
    number = r'd+(.d+)?'
    factor = number / "(" stmt ")"
    term = factor (mulop factor)*
    stmt = term (addop term)*
    addop = "+" / "-"
    mulop = "*" / "/"
    calc = stmt EOF
    """
    
    #Creating a visitor class to calculate the result
    class CalcVisitor(PTNodeVisitor):
    
        def visit_number(self, node, children):
            return float(node.value)
    
        def visit_factor(self, node, children):
            # Children are list-like structure of VISITED node results
            # visits are made from depth to top
            return children[0]
    
        def visit_term(self, node, children):
            # For such rules you may use, for example children["factor"]
            # Though, you need to know, that children["factor"] is a list of ALL
            # factor's of this term
            if len(children) == 1:
                return children[0]
            else:
                res = children[0]
                for i in xrange(len(children) / 2):
                    if children[2 * i + 1] == '*':
                        res *= children[2 * (i + 1)]
                    else:
                        res /= children[2 * (i + 1)]
                return res
    
        def visit_stmt(self, node, children):
            if len(children) == 1:
                return children[0]
            else:
                res = children[0]
                for i in xrange(len(children) / 2):
                    if children[2 * i + 1] == '+':
                        res += children[2 * (i + 1)]
                    else:
                        res -= children[2 * (i + 1)]
                return res
    
    # Don’t forget about root rule for your parser, as it will be produced as
    # a parsing result
    parser = ParserPEG(calc_grammar, "calc")
    input_expr = "(4-1)*5+(2+4.67)+5.89/(1.2+7)"
    print(input_expr)
    parse_tree = parser.parse(input_expr)
    
    result = visit_parse_tree(parse_tree, CalcVisitor(
        #debug=True
    ))
    print(result)
    input_expr = "1 + 2 / (3 - 1 + 5)"
    print(input_expr)
    parse_tree = parser.parse(input_expr)
    
    result = visit_parse_tree(parse_tree, CalcVisitor(
        #debug=True
    ))
    print(result)
    
    

    При запуске выведет следующее:
    python ./calc_arpeggio.py 
    (4-1)*5+(2+4.67)+5.89/(1.2+7)
    22.3882926829
    1 + 2 / (3 - 1 + 5)
    1.28571428571

    Если есть желание посмотреть, как посетитель обходит дерево, можно раскомментировать debug

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

    Общие выводы


    На самом деле, выводов несколько:


    • Не так страшен чёрт, как его малюют. Создание парсера с помощью инструмента, дело, в общем, посильное. Достаточно изучить общие принципы и потратить полдня на изучение конкретного инструмента, после чего в дальнейшем все уже будет намного проще. А вот велосипеды изобретать — не надо. Особенно, если вам не особенно важна скорость парсинга и оптимизации.

    • Грамматики имеют собственную ценность. Имея перед глазами грамматику, гораздо проще оценить, будут ли при использовании составленного по ней парсера возникать ошибки.

    • Инструмент можно найти всегда. Возможно, не на самом привычном языке, но почти на всех они есть. Если не повезло, и его все-таки нет, можно взять что-нибудь легко используемое (что-то на js, python, lua или ruby — тут уж кому что больше нравится). Да, получится “почти stand-alone в рамках проекта”, но в большинстве случаев этого достаточно.

    • Все инструменты (немного) различаются. Иногда это “:” вместо “=” в BNF, иногда различия более обширны. Не надо этого пугаться. В крайнем случае, переделка грамматики под другой инструмент займет у вас минут 20. Так что если есть возможность достать где-то грамматику, а не писать её самому, лучше это сделать. Но перед использованием все равно лучше её проверьте. Все мы люди, всем нам свойственно ошибаться…

    • При прочих равных, лучше используйте более “разговорчивый” инструмент. Это поможет избежать ошибок составления грамматики и оценить, что и как будет происходить.

    • Если для вас в первую очередь важна скорость разбора, боюсь, вам придется либо пользоваться инструментом для C (например, Bison), либо решать проблему “в лоб”. Так же, следует задуматься о том, нужен ли вам именно парсинг (об этом стоит задуматься в любом случае, но в случае скоростных ограничений — особенно). В частности, для многих задач подходит токенизация — разбиение строки на подстроки с использованием заданного разделителя или их набора. Возможно, это ваш случай.


    Заключение


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

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

    Как и обещал, несколько полезных ссылок по теме статьи:


    • В википедии, на английском (на русском статьи существенно меньше):
      СFG
      BNF
      LL
      LR
      PEG

    • Если кому-то нужно более серьёзное чтиво, тоже для человека “без математического бекграунда”, могу посоветовать книгу А. Аxo, Дж. Ульман “Теория синтаксического анализа, перевода и компиляции”. Есть, например, здесь. При желании находится достаточно легко, в русском переводе.



    Источник: Хабрахабр

    Категория: Программирование » Game Development

    Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
    Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

    Добавление комментария

    Имя:*
    E-Mail:
    Комментарий:
    Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
    Введите два слова, показанных на изображении: *