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

Question

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

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))...?

Answer 1

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

1. Если мы подавим символы открывающих и закрывающих скобок и сгруппируем выражение в скобках, используя Группирование, 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 + atom)
       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)" )
   

   * +1007 * Предоставление:

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

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

2. Поскольку op определяется как просто oneOf ("+ - * /"), приоритет операций отсутствует. В репозитории pyparsing есть примеры https://github.com/pyparsing/pyparsing/tree/master/examples ручного способа определения этого (fourFn.py) или более поздний подход с использованием помощника infixNotation (simpleArith.py). Опять же, это приводит к добавлению большего значения, чем просто к токенизации.

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

- Пол

Answer 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', ')']

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

Answer 3

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

expr :: expr op expr

С

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

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

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

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

Answer 4

Используйте operatorPrecedence для построения выражений. Он создаст правильные выражения и позаботится о приоритете операторов, пока у него:

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']]]]