Prett Parsing — метод Вогана Пратта для разбора выражений

    В тему компиляций и вычислений выражений.

    В далёком 1973 году Воган Прэтт (Vaughan Pratt) предложил простой и эффективный метод разбора выражений, не использующий ни автоматы, ни грамматику как таковую.

    Идея заключается в том, что каждый символ (token) наделяется свойствами:
    lbp = приоритет связывания символа слева,
    nud = функция, определяющая результат применения оператора в начале выражения,
    led = функция, определяющая результат применения в середине выражения.

    Основной разбор осуществляется по схеме:
    разбор(приоритет продолжения):
        вытолкнуть символ из входного потока
        результат = вызов nud этого символа
        пока приоритет lbp следующего в потоке символа > приоритета продолжения:
            вытолкнуть символ из входного потока
            результат = применени led этого символа к текущему результату
    

    Константы и переменные имеют приоритет связывания 0, а функция nud возвращает их значение (или ссылку). Поэтому применение разбора к константам сразу возратит их значение.
    Для бинарных операторов функция led рекурсивно вызывает продолжение разбора (справа) вплоть до более низкого приоритета, и делает что-нибудь с уже накопленым (слева) результатом, и полученным рекурсивно.
    Результат применения оператора аггрегируется для внешнего вызова.
    Много-арные операторы — получают аргументы дополнительным вызовом функции разбора.
    Префиксные операторы делаются с помощью определения для них функции nud.
    Для правостороннего связывания меняется приоритет продолжения рекурсивного разбора.

    На сайте effbot.org приводится подробная реализация на питоне.
    Там же есть ссылки для жаваскрипта и схемы.

    operators = { # приоритеты и функции led
        '+': [1, lambda left: "(%s + %s)" % (left, parse(1))],
        '*': [2, lambda left: "(%s * %s)" % (left, parse(2))],
        '^': [3, lambda left: "(%s ^ %s)" % (left, parse(3))],
        '$': [0]
        }
    
    def lbp(t):
        try:
            return operators[t][0]
        except KeyError:
            return 0
        
    def nud(t):
        return t
    
    def led(t,left):
        return operators[t][1](left)
    
    # можно соорудить класс для каждого оператора, но это очень больше строчек получится.
    
    def parse(rbp=0):
        global tokens
        tok = tokens.pop(0)
        result = nud(tok)
        while lbp(tokens[0]) > rbp:
            tok = tokens.pop(0)
            result = led(tok,result)
        return result
    
    def evaluate(expr):
        global tokens
        tokens = expr.split(" ") + ['$']
        parse()
    

    Примеры работы:
    >>> evaluate("a + b * c ^ d * e + f")
       a|+,b,*,c,^,d,*,e,+,f,$
     = a
       +|b,*,c,^,d,*,e,+,f,$
         b|*,c,^,d,*,e,+,f,$
       = b
         *|c,^,d,*,e,+,f,$
           c|^,d,*,e,+,f,$
         = c
           ^|d,*,e,+,f,$
             d|*,e,+,f,$
           = d
         = (c ^ d)
       = (b * (c ^ d))
         *|e,+,f,$
           e|+,f,$
         = e
       = ((b * (c ^ d)) * e)
     = (a + ((b * (c ^ d)) * e))
       +|f,$
         f|$
       = f
     = ((a + ((b * (c ^ d)) * e)) + f)
    >>>
    >>> evaluate("a * b + c ^ d + e * f")
       a|*,b,+,c,^,d,+,e,*,f,$
     = a
       *|b,+,c,^,d,+,e,*,f,$
         b|+,c,^,d,+,e,*,f,$
       = b
     = (a * b)
       +|c,^,d,+,e,*,f,$
         c|^,d,+,e,*,f,$
       = c
         ^|d,+,e,*,f,$
           d|+,e,*,f,$
         = d
       = (c ^ d)
     = ((a * b) + (c ^ d))
       +|e,*,f,$
         e|*,f,$
       = e
         *|f,$
           f|$
         = f
       = (e * f)
     = (((a * b) + (c ^ d)) + (e * f))
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 15
    • 0
      спасибо, познавательно
      • 0
        Для чего этот разбор выражений?
        • НЛО прилетело и опубликовало эту надпись здесь
          • +1
            У вас на выходе полная скобочная структура выражения, можно ее решить методом Рутисхаузера, как раз и предназначенный для решения полных скобочных выражений. А, может еще для чего пригодится, мало ли сколько задач в жизни бывает.
            • +2
              например, в компилятор играть
              • 0
                для общего развития. Я как то разбирал алгоритм рекурсивного спуска, интересно было прочитать про этот метод
                • 0
                  Сейчас, например, мне необходимо сделать формализованное описание кинематической и пространственной структуры манипулятора робота в виде некоторого выражения. Вот для похожих задач и необходим разбор выражений!!!
                  • 0
                    13 месяцев спустя :)
                    Техническая Кибернетика? :)
                    мы своих «роботов» (АИ) писали на 5 курсе, что бы препятствия обходил, образы распознавал :) весело было
                    • 0
                      Писал для защиты так называемой «магистерской» работы
                      Была задача для реальных роботов. Там еще нужно было реализовать обход препятствий (станков, подающих устройств)… С чем я и справился.

                      А описание пространственной и кинематической структуры было новшевством в этой работе (там типа робот описывался набором примитивом с условием, где может быть поворот или линейное перемещение).

                      Насчет 13 месяцев — думаю, никогда не поздно написать комментарий )))
                    • 0
                      а чем этот метод эффективнее других?

                      сам я уже забыл зачем он мне нужен был,
                      и вообще даже удивился с чего это мне прилетают комменты к какому-то чужому и невнятному непонятному посту :)
                  • 0
                    Спасибо, интересно. а можно спросить… для каких типов грамматик он применим?
                    • 0
                      как видно, алгоритм танцует не от грамматики, а от связываемости символов.
                      а классификация грамматик, тогоже Хомского, основана на теории автоматов, которая тут никак не используются.
                      как одно с другим связано — так просто не скажешь.

                      исходная публикация, к сожалению, доступна только за 100$, потомучто ACM.

                      а по ссылкам можно найти примеры разбора грамматики питоновских выражений,
                      в том числе оператора «not in» и прочих завитушек.
                    • 0
                      А есть какие-нибудь соображения по поводу эффективности в сравнении с классическим рекурсивным спуском?
                      И присоединяюсь к вопросу Xronos о типах грамматик. Или там накладываются совсем другие ограничения?
                      • 0
                        Извиняюсь, за ссылки на совсем другого пользователи и другой коментарий :)
                        Я конечно имел в виду этот
                        • 0
                          видимо, другие ограничения. но какие — непонятно :)

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

                        Самое читаемое