Biểu thức đệ quy với pyparsing

Question

Tôi đang cố gắng tìm ra cách để thực hiện một biểu thức liên kết bên trái, trong đó các biểu thức đệ quy (không kèm theo trong bất kỳ) nào là có thể. Ví dụ, tôi muốn làm:

expr + OP + expr 

rằng phân tích 2 hoạt động như 1 x 2 x 3 vào (expr OP expr) OP expr kết quả.

Nếu tôi cố gắng để ngăn chặn expr phân tích cú pháp từ đệ quy vô hạn, tôi có thể làm một cái gì đó như:

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

nhưng sau đó tôi muốn có được kết quả expr OP (expr OR expr).

Làm cách nào để buộc ràng buộc bên trái?

Chỉnh sửa: Tôi biết về operatorPrecedence nhưng khi nhà điều hành là "IS" + Optional("NOT") hoặc tương tự, có vẻ như nó không phù hợp.

Answer 1

Dưới đây là một ví dụ hành động phân tích cú pháp sẽ đưa danh sách phẳng của thẻ và làm tổ họ như thể phân tích cú pháp trái đệ quy:

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] 

Prints:

(bình thường)

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

(dạng LR)

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

Answer 2

Pyparsing tạo ra các cây phân tích trái. Thêm hành động ngữ nghĩa để chỉnh sửa cây phân tích cú pháp ngay sau expr đã được phân tích cú pháp.