Простой рекурсивный спуск в PyParsing

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

op = oneOf( '+ - / *')
lparen, rparen = Literal('('), Literal(')')

expr = Forward()
expr << ( Word(nums) | ( expr + op + expr ) | ( lparen + expr + rparen) )

Я играл с несколькими различными модификациями этой простой настройки. Обычно, попробуйте что-то вроде:

print(expr.parseString('1+2'))

Вернется ['1']. Хотя я попадаю в глубокую рекурсию с чем-то вроде:

print(expr.parseString('(1+2)'))

Что мне не хватает в отношении простой рекурсии, что я не могу анализировать произвольно арифметические выражения, такие как 1+(2 * 3-(4*(5+6)-(7))...?

Ответы

Ответ 1

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

  • Если мы подавляем открывающие и закрывающие символы круглых скобок и группируем выражение в скобках с помощью Group, то pyparsing будет структурированным результатом, который ближе к AST.

    from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf,Group

def Syntax():
    op = oneOf( '+ - / *')
    lpar  = Literal( '(' ).suppress()
    rpar  = Literal( ')' ).suppress()
    num = Word(nums)
    expr = Forward()
    atom = num | Group( lpar + expr + rpar )
    expr << atom + ZeroOrMore( op + expr )
    return expr

if __name__ == "__main__":
    expr = Syntax()
    def test(s):
        results = expr.parseString( s )
        print s,'->', results

    test( "(9 + 3)" )
    test( "(9 + 3) * (4 / 5)" )

    Дарение:

    (9 + 3) -> [['9', '+', '3']]
(9 + 3) * (4 / 5) -> [['9', '+', '3'], '*', ['4', '/', '5']]

    В противном случае pyparsing просто символизирует, и вам нужно пройти список проанализированных токенов, чтобы найти вложенные выражения.

  • Так как op определяется как только одинOf ( "+ - */" ), приоритет операций не существует. Есть примеры на вики-странице pyparsing для ручного способа определения этого (fourFn.py) или более позднего подхода с использованием помощника operatorPrecedence (simpleArith.py). Опять же, у этого есть pyparsing, добавляющий больше значения, чем просто токенизация.

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

- Пол

Ответ 2

Это более или менее то, что вы хотите...?

from pyparsing import Literal,Word,ZeroOrMore,Forward,nums,oneOf

def Syntax():
    op = oneOf( '+ - / *')
    lpar  = Literal( '(' )
    rpar  = Literal( ')' )
    num = Word(nums)

    expr = Forward()
    atom = num | ( lpar + expr + rpar )
    expr << atom + ZeroOrMore( op + expr )
    return expr


if __name__ == "__main__":

    expr = Syntax()

    def test(s):
        results = expr.parseString( s )
        print s,'->', results

    test( "(9 + 3)" )
    test( "(9 + 3) * (4 / 5)" )

излучающие

(9 + 3) -> ['(', '9', '+', '3', ')']
(9 + 3) * (4 / 5) -> ['(', '9', '+', '3', ')', '*', '(', '4', '/', '5', ')']

? Это "привязывает" рекурсию, отделяя "атом" (число или заключенное в скобки выражение) от "выражения" (одного или нескольких "атомов" с промежуточными операторами).

Ответ 3

Грамматика вроде:

expr :: expr op expr

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

Обычная арифметическая грамматика будет выглядеть примерно так:

expr :: mulxp | mulxp '+' expr
mulxp :: atom | atom '*' expr
atom :: Word(nums) | '(' + expr + ')'

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

Ответ 4

Используйте operatorPrecedence для создания выражений, например, как в примере в http://pyparsing.wikispaces.com/file/view/simpleArith.py/30268305/simpleArith.py. Он построит правильные выражения и позаботится о приоритете оператора, находясь на нем:

num = Word(nums)
plusop = oneOf( '+ -')
multop = oneOf('/ *')
expr = operatorPrecedence(num,
                          [(multop, 2, opAssoc.LEFT),(plusop, 2, opAssoc.LEFT)])

Пример:

>> print parsetime.expr.parseString("1+(2 * 3-(4*(5+6)-(7)))")
[['1', '+', [['2', '*', '3'], '-', [['4', '*', ['5', '+', '6']], '-', '7']]]]