ANTLR: Làm cách nào để giải thích hành vi của ngữ pháp nhận ra hậu tố của mã Java?

Question

Một tuần trước, tôi bắt đầu dự án sau: ngữ pháp nhận ra hậu tố của mã Java.

Tôi đã sử dụng chính thức ANTLR ngữ pháp cho Java (Java.g4) làm đường cơ sở và bắt đầu thêm một số quy tắc. Tuy nhiên, những quy tắc mới này cũng giới thiệu phép đệ quy trái mà tôi cũng phải giải quyết.

Sau một vài ngày làm việc, tôi có số following code. Khi tôi bắt đầu thử nghiệm, tôi nhận thấy một điều gì đó bất thường mà tôi vẫn không thể giải thích. Khi được nhập { } trình phân tích cú pháp cho tôi biết no viable alternative at input '<EOF>' nhưng khi tôi chuyển đổi thứ tự các đầu cuối ở phía bên tay phải của quy tắc s2, đặc biệt nếu chúng ta thay đổi phía bên tay phải từ v2_1 | v2_2 | v2_3 ... thành v2_36 | v2_1 | v2_2 ... (thiết bị đầu cuối v2_36 vị trí đầu tiên), trình tự { } được chấp nhận.

suy nghĩ đầu tiên của tôi là rằng Antlr không quay lại vì tôi nhận thấy rằng với sự đóng góp { } phiên bản đầu tiên của bộ phân tích bắt đầu làm theo các quy tắc v2_3 và chỉ báo cáo rằng không có gì được tìm thấy và không cố gắng để xem xét các lựa chọn khác (đó là những gì tôi nghĩ nhưng có lẽ nó không đúng) như v2_36 cung cấp cho chính xác câu trả lời tích cực.

Nhưng sau một số nghiên cứu, tôi phát hiện ra rằng ANTLR thực sự quay lại nhưng chỉ khi mọi thứ khác không thành công. Ít nhất điều này là đúng cho v3.3 (đọc nó trong chính thức ANTLR giấy) nhưng tôi đoán nó cũng đúng cho v4. Bây giờ tôi có chút bối rối. Sau khi dành quá nhiều giờ cho dự án này, tôi sẽ cảm thấy thực sự khủng khiếp nếu tôi không làm cho nó hoạt động. Ai đó có thể đưa ra một số loại tip hay cái gì đó? Nó sẽ được đánh giá cao, cảm ơn.

EDIT

Managed để cô lập các vấn đề để

grammar Java; 
@parser::members {String ruleName; } 

start : compilationUnitSuf EOF; 

compilationUnitSuf 
    : {ruleName = "typeDeclarationSuf"; } s2 
    ; 

s2: '{' '}' v2_81 | '{' '}'; 
v2_81 : {ruleName.equals("enumBodyDeclarationsSuf")}? t173 | t173 '}'; 
t173: '}' | '{'*; 

LBRACKET: '{'; 
RBRACKET: '}'; 

WS : [ \t\r\n\u000C]+ -> skip 
    ; 

Vậy tại sao các thuật toán tiên đoán gợi ý cho tôi đi theo s2 -> v'{' '}' v2_81 -> ... thay vì s2 -> '{' '}'?

Answer 1

Tôi nghĩ rằng bạn sẽ thấy rằng nó không phải là backtracking theo cách mà bạn mong đợi. Lý do là nó tìm thấy các {} và sau đó hy vọng sẽ thấy một v2_181, mà nó không tìm thấy. bởi vì nó không quay lại, nó không tìm thấy sự thay thế mà bạn muốn. Cách khác là chỉ cần thực hiện tùy chọn v2_181, sau đó bạn không cần quay lại. Một cái gì đó như sau:

grammar Java; 
@parser::members {String ruleName; } 

start : compilationUnitSuf EOF; 

compilationUnitSuf 
    : {ruleName = "typeDeclarationSuf"; } s2 
    ; 

s2: '{' '}' v2_81?; 
v2_81 : {ruleName.equals("enumBodyDeclarationsSuf")}? t173 | t173 '}'; 
t173: '}' | '{'*; 

LBRACKET: '{'; 
RBRACKET: '}'; 

WS : [ \t\r\n\u000C]+ -> skip 
    ;