ANTLR4 lỗi lẫn nhau trái đệ quy khi phân tích cú pháp

Question

Tôi có ANTLR này 4 ngữ pháp:

constantFixedExpresion : term (('+'|'-') term)+; 

term : factor (('*'|'//'|'REM')factor)+; 

factor : ('+'|'-')* 
      (wholeNumberConstant 
      | constantFixedExpresion 
      | 'TOFIXED' (stringConstant | bitCodeConstant)  
      | identifier) 
     ('FIT'constantFixedExpresion)*; 

tôi nhận được lỗi sau:

error(119): LanguageA.g4::: The following sets of rules are mutually left-recursive [constantFixedExpresion, factor, term]

tôi đã cố gắng rất nhiều cách nhưng không thể sửa chữa nó. Vấn đề là gì và tôi có thể giải quyết nó như thế nào?

Answer 1

Antlr là một trình phân tích cú pháp LL (*), theo nhiều cách "tốt hơn" so với LL(k) parser, nhưng vẫn có nhiều sự không thích hợp. Một trong số đó là thực tế nó không thể đối phó với đệ quy trái (thực tế, phiên bản 4 có thể đối phó với đệ quy trái trong cùng một quy tắc). Những gì các lỗi được nói là bạn có một đệ quy trái của một ngữ pháp, một lệnh cấm cho các phân tích cú pháp LL.

này là do xây dựng này trong ngữ pháp của bạn:

constantFixedExpression: term ...; 
term: factor ...; 
factor: ('+' | '-')* (constantFixedExpression | ...) ...; 

Kể từ khi các nhà điều hành * nghĩa 0 hoặc nhiều hơn, tôi có thể nhanh chóng nó với 0, do đó phân tích cú pháp sẽ làm điều này: "thử constantFixedExpression, vì vậy nó cần phải thử term, vì vậy nó cần phải thử factor, vì vậy nó cần phải thử constantFixedEXpression, vì vậy nó [...] "và bạn đã có cho mình một vòng lặp vô hạn.

---

May mắn thay, ngữ pháp chính thức không có bối cảnh có phép chuyển đổi tương đương để xóa bỏ đệ quy trái! Nó có thể được bày tỏ quát theo:

A -> Aa | b 
-- becomes -- 
A -> bR 
R -> aA | ε 

Hoặc trong ký hiệu ANTLR:

A: Aa | b; 
// becomes 
A: bR; 
R: (aA)?; 

Thông tin thêm về quá trình này có thể được tìm thấy trong automaton/văn phạm sách hoặc trong Wikipedia.

---

Tôi sẽ sửa lại ngữ pháp của bạn với việc tái cấu trúc để xóa đệ quy trái như tác phẩm của bạn. Tuy nhiên, tôi muốn chạm vào một điểm khác: Antlr 4 có thể thực hiện phép đệ quy trái! Như tôi đã đề cập, phiên bản 4 có thể xử lý đệ quy trái trong cùng một quy tắc. Có nhiều cách để chỉ ra sự ưu tiên và tính kết hợp của các toán tử khác với trực tiếp trong phân tích cú pháp, như bạn đang làm, trong Antlr4. Hãy xem cách hoạt động:

expr: NUMBER 
     |<assoc=right> expr '^' expr 
     | expr '*' expr 
     | expr '/' expr 
     | expr '+' expr 
     | expr '-' expr; 

Đây là ví dụ về ngữ pháp máy tính cơ bản. Các toán tử ở trên cùng là những người có quyền ưu tiên cao nhất, và những người có quyền ưu tiên thấp hơn. Điều này có nghĩa là 2+2*3 sẽ được phân tích cú pháp là 2+(2*3) thay vì (2+2)*3. Cấu trúc <assoc=right> có nghĩa là toán tử ở bên phải, vì vậy 1^2^3 sẽ được phân tích cú pháp là 1^(2^3) thay vì (1^2)^3.

Như bạn có thể thấy, việc xác định toán tử với đệ quy trái dễ dàng hơn rất nhiều, vì vậy Antlr 4 là trợ giúp lớn trong những khoảnh khắc này! Tôi khuyên bạn nên viết lại ngữ pháp của mình để sử dụng tính năng này.