Wyrażenia rekursywne z pyparstwem

Question

Próbuję dowiedzieć się, jak wykonać wyrażenie lewostronne, gdzie możliwe są wyrażenia rekurencyjne (niesklasyfikowane w cokolwiek). Na przykład, chciałbym zrobić:

expr + OP + expr 

że analizuje 2 operacje jak 1 x 2 x 3 do (expr OP expr) OP expr wyniku.

Jeśli staram się zapobiec expr parsowania z nieskończonej rekurencji, mogę zrobić coś takiego:

expr -> Group(simple_expr + OP + expr) 
     | simple_expr 

ale wtedy bym uzyskać wynik expr OP (expr OR expr).

Jak wymusić wiązanie po lewej stronie?

Edytuj: Wiem o operatorPrecedence, ale gdy operator jest "IS" + Optional("NOT") lub podobny, nie wydaje się pasować poprawnie.

Answer 1

Oto przykład działania parse że weźmie płaskich wykazy tokenów oraz gniazdo nich jakby analizowany lewej rekurencyjnie:

from pyparsing import * 

# parse action -maker 
def makeLRlike(numterms): 
    if numterms is None: 
     # None operator can only by binary op 
     initlen = 2 
     incr = 1 
    else: 
     initlen = {0:1,1:2,2:3,3:5}[numterms] 
     incr = {0:1,1:1,2:2,3:4}[numterms] 

    # define parse action for this number of terms, 
    # to convert flat list of tokens into nested list 
    def pa(s,l,t): 
     t = t[0] 
     if len(t) > initlen: 
      ret = ParseResults(t[:initlen]) 
      i = initlen 
      while i < len(t): 
       ret = ParseResults([ret] + t[i:i+incr]) 
       i += incr 
      return ParseResults([ret]) 
    return pa 


# setup a simple grammar for 4-function arithmetic 
varname = oneOf(list(alphas)) 
integer = Word(nums) 
operand = integer | varname 

# ordinary opPrec definition 
arith1 = operatorPrecedence(operand, 
    [ 
    (None, 2, opAssoc.LEFT), 
    (oneOf("* /"), 2, opAssoc.LEFT), 
    (oneOf("+ -"), 2, opAssoc.LEFT), 
    ]) 

# opPrec definition with parseAction makeLRlike 
arith2 = operatorPrecedence(operand, 
    [ 
    (None, 2, opAssoc.LEFT, makeLRlike(None)), 
    (oneOf("* /"), 2, opAssoc.LEFT, makeLRlike(2)), 
    (oneOf("+ -"), 2, opAssoc.LEFT, makeLRlike(2)), 
    ]) 

# parse a few test strings, using both parsers 
for arith in (arith1, arith2): 
    print arith.parseString("A+B+C+D+E")[0] 
    print arith.parseString("A+B+C*D+E")[0] 
    print arith.parseString("12AX+34BY+C*5DZ+E")[0] 

Wydruki:

(normalny)

['A', '+', 'B', '+', 'C', '+', 'D', '+', 'E'] 
['A', '+', 'B', '+', ['C', '*', 'D'], '+', 'E'] 
[['12', 'A', 'X'], '+', ['34', 'B', 'Y'], '+', ['C', '*', ['5', 'D', 'Z']], '+', 'E'] 

(LR-like)

[[[['A', '+', 'B'], '+', 'C'], '+', 'D'], '+', 'E'] 
[[['A', '+', 'B'], '+', ['C', '*', 'D']], '+', 'E'] 
[[[[['12', 'A'], 'X'], '+', [['34', 'B'], 'Y']], '+', ['C', '*', [['5', 'D'], 'Z']]], '+', 'E'] 

Answer 2

Pyparsing produkuje pozostawione parsowanie drzew. Dodaj działanie semantyczne, aby edytować drzewo analizowania zaraz po przeanalizowaniu expr.