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

Question

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

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

Грамматика как:

expr :: expr op expr 

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

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

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

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

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

Вау, я думаю, что 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 + 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 просто tokenizing, и вы должны ходить список проанализированных маркеров, чтобы найти вложенные выражения.

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

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

- Пол

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