Viết phân tích cú pháp đệ quy với pyparsing

Question

Tôi đang cố gắng hiểu phần tử Forward() từ pyparsing. Giả sử tôi có BNF đơn giản này:

identifier = 
    "a..z,$,_" < "a..z,$,_,0..9" > 

package_name = 
    identifier 
/(package_name "." identifier) 

và tôi cố gắng phân tích một gói đơn giản như java.lang.String tôi nhận được một trong hai chỉ java như kết quả hoặc không bao giờ trở về từ đệ quy. Tôi đã thử nó như thế này:

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal 

identifier=Word(alphas+"$_",alphanums+"$_") 
dot=Literal(".") 

package_name = Forward() 
definition = package_name+dot+identifier 
package_name << Group(identifier+ZeroOrMore(definition)) 

package_name.parseString("java.lang.String") 

sẽ in [[ 'java']]

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal 

identifier=Word(alphas+"$_",alphanums+"$_") 
dot=Literal(".") 

package_name = Forward() 
definition = identifier^package_name+dot+identifier 
package_name << definition 

package_name.parseString("java.lang.String") 

sẽ đạt đệ quy giới hạn

cách làm việc Forward giữ chỗ này?

Answer 1

Vấn đề không phải là với Forward nhưng với ngữ pháp của bạn vốn đã bị hạn chế quá sớm hoặc đệ quy theo cách không thể xác định bằng trình phân tích cú pháp đệ quy ngây thơ như Pyparsing.

Bạn có thế này:

package_name = identifier | (package_name "." identifier) 

Nếu bạn kết hợp trái sang phải, điều này sẽ luôn luôn phù hợp với một định danh duy nhất và sau đó dừng lại, không cố gắng để phù hợp với một giai đoạn sau. Nếu bạn chuyển đổi đơn hàng để khớp với số identifier cuối cùng:

package_name = (package_name "." identifier) | identifier 

. . . sau đó nó sẽ vô hạn recurse, bởi vì để quyết định nếu package_name phù hợp, điều đầu tiên nó phải làm là quyết định xem package_name phù hợp. Đây là ngữ pháp left-recursive, một trình phân tích cú pháp đệ quy đơn giản như Pyparsing không thể xử lý. Pyparsing không nhìn về phía trước để xem trận đấu sẽ ảnh hưởng như thế nào đến các trận đấu tiếp theo. Nó chỉ cố gắng các trận đấu trái sang phải.

Bạn có thể lấy một ví dụ đơn giản về cách Forward hoạt động bằng cách thay đổi cách thức recurses ngữ pháp của bạn:

identifier = pyp.Word(pyp.alphas+"$_", pyp.alphanums+"$_") 
package_name = pyp.Forward() 
package_name << ((identifier + '.' + package_name) | identifier) 

>>> package_name.parseString("java.lang.String") 
[u'java', u'.', u'lang', u'.', u'String'], {}) 

Ở đây, đệ quy sẽ xảy ra ở bên phải, chứ không phải ở bên trái, vì vậy Pyparsing có thể phù hợp với nó incremenetally.

(Việc bạn sử dụng ZeroOrMore là cá trích màu đỏ. Nếu bạn có ngữ pháp đệ quy như thế này, bạn không muốn sử dụng ZeroOrMore, vì định nghĩa đệ quy đã cho phép biểu thức phụ của bạn khớp với nhiều lần Như tôi đã gợi ý trong nhận xét của mình, tuy nhiên, việc định nghĩa loại ngữ pháp này mà không cần đệ quy lại đơn giản hơn nhiều.)