Tại sao không thể phân tích cú pháp C++ bằng trình phân tích cú pháp LR (1)?

Question

Tôi đã đọc về phân tích cú pháp và máy phát phân tích cú pháp và thấy tuyên bố này trong -page LR phân tích wikipedia của:

Nhiều ngôn ngữ lập trình có thể được phân tích cú pháp sử dụng một số biến thể của một phân tích cú pháp LR. Một ngoại lệ đáng chú ý là C++.

Tại sao lại như vậy? Đặc tính nào của C++ làm cho nó không thể phân tích cú pháp với các trình phân tích cú pháp LR?

Sử dụng google, tôi chỉ thấy rằng C có thể được phân tích cú pháp hoàn toàn với LR (1) nhưng C++ yêu cầu LR (∞).

Answer 1

Có một chuỗi thú vị trên Lambda the Ultimate thảo luận về số LALR grammar for C++.

Nó bao gồm một liên kết đến một PhD thesis bao gồm một cuộc thảo luận về C++ phân tích cú pháp, trong đó nêu rằng:

"C++ ngữ pháp là mơ hồ, bối cảnh phụ thuộc và có khả năng đòi hỏi lookahead vô hạn để giải quyết một số mơ hồ ".

Nó tiếp tục đưa ra một số ví dụ (xem trang 147 của pdf).

Các ví dụ là:

int(x), y, *const z; 

nghĩa

int x; 
int y; 
int *const z; 

So sánh với:

int(x), y, new int; 

nghĩa

(int(x)), (y), (new int)); 

(biểu thức được phân cách bằng dấu phẩy).

Hai chuỗi mã thông báo có cùng chuỗi ban đầu nhưng các cây phân tích cú pháp khác nhau, tùy thuộc vào phần tử cuối cùng. Có thể có nhiều mã thông báo tùy ý trước một thẻ.

Answer 2

Tôi nghĩ bạn khá gần với câu trả lời.

LR (1) có nghĩa là phân tích cú pháp từ trái sang phải chỉ cần một mã thông báo để xem trước ngữ cảnh, trong khi LR (∞) có nghĩa là một cái nhìn vô hạn. Nghĩa là, trình phân tích cú pháp sẽ phải biết mọi thứ đang đến để tìm ra nó đang ở đâu.

Answer 3

Trình phân tích cú pháp LR không thể xử lý các quy tắc ngữ pháp không rõ ràng, theo thiết kế. (Làm cho lý thuyết trở lại dễ dàng hơn vào những năm 1970 khi các ý tưởng được đưa ra).

C và C++ cả cho phép tuyên bố sau:

x * y ; 

Nó có hai phân tích khác nhau:

1. Nó có thể là việc kê khai của y, như con trỏ đến gõ x
2. Nó có thể là một nhân của x và y, ném đi câu trả lời.

Bây giờ, bạn có thể nghĩ điều sau là ngu ngốc và nên bỏ qua. Hầu hết sẽ đồng ý với bạn; tuy nhiên, có những trường hợp có thể có tác dụng phụ (ví dụ: nếu nhân bị quá tải). nhưng đó không phải là vấn đề. Vấn đề là có là hai phân tích cú pháp khác nhau và do đó chương trình có thể có nghĩa là những thứ khác nhau tùy thuộc vào cách nên này đã được phân tích cú pháp.

Trình biên dịch phải chấp nhận thích hợp trong các trường hợp thích hợp và không có bất kỳ thông tin nào khác (ví dụ: kiến ​​thức về loại x) phải thu thập cả hai để quyết định sau phải làm gì. Vì vậy, một ngữ pháp phải cho phép điều này. Và điều đó làm cho ngữ pháp trở nên mơ hồ.

Do đó việc phân tích cú pháp LR thuần túy không thể xử lý việc này. Cũng không phải nhiều trình tạo phân tích cú pháp có sẵn rộng rãi khác, như Antlr, JavaCC, YACC, hoặc Bison truyền thống, hoặc thậm chí các trình phân tích cú pháp kiểu PEG, được sử dụng theo cách "thuần khiết". Có rất nhiều trường hợp phức tạp hơn (cú pháp khuôn mẫu phân tích cú pháp đòi hỏi tùy ý, trong khi LALR (k) có thể nhìn về phía trước ở hầu hết các mã thông báo k), nhưng chỉ có một ví dụ để quay xuống tinh khiết LR (hoặc những người khác) phân tích cú pháp.

C++ Hầu hết các phân tích cú pháp/thực C xử lý ví dụ này bằng cách sử dụng một số loại phân tích cú pháp xác định với thêm một hack: họ xen lẫn vào nhau phân tích với bảng biểu tượng bộ sưu tập ... để đến thời gian "x" là gặp, sự trình phân tích cú pháp biết nếu x là một kiểu hay không, và do đó có thể chọn giữa hai phân tích cú pháp tiềm năng. Nhưng một trình phân tích cú pháp thực hiện điều này không phải là ngữ cảnh tự do và các trình phân tích cú pháp LR (các trình đơn thuần túy, v.v.) là ngữ cảnh hoàn toàn miễn phí.

Người ta có thể gian lận và thêm kiểm tra ngữ nghĩa theo thời gian giảm quy tắc trong các trình phân tích cú pháp đến LR để thực hiện việc định hướng này. (Mã này thường không đơn giản). Hầu hết các loại trình phân tích cú pháp khác có một số phương tiện để thêm kiểm tra ngữ nghĩa tại các điểm khác nhau trong phân tích cú pháp, có thể được sử dụng để thực hiện việc này.

Và nếu bạn lừa đủ, bạn có thể làm cho trình phân tích cú pháp LR hoạt động cho C và C++. Các anh chàng GCC đã làm trong một thời gian, nhưng đã cho nó cho phân tích cú pháp bằng tay, tôi nghĩ bởi vì họ muốn chẩn đoán lỗi tốt hơn.

Có một cách tiếp cận khác, tuy nhiên, tốt đẹp và sạch sẽ và phân tích C và C++ tốt mà không có bất kỳ bảng biểu tượng hackery: GLR parsers. Đây là các trình phân tích ngữ cảnh hoàn toàn miễn phí (có hiệu quả vô hạn lookahead).Trình phân tích cú pháp GLR chỉ cần chấp nhận cả hai phân tích, tạo một "cây" (thực tế là biểu đồ tuần hoàn hướng chủ yếu là cây) đại diện cho phân tích không rõ ràng. Đoạn sau phân tích cú pháp có thể giải quyết sự mơ hồ.

Chúng tôi sử dụng kỹ thuật này trong C và C++ trước kết thúc cho DMS Phần mềm Tái cấu trúc Toolkit của chúng tôi (tính đến tháng 6 năm 2017 những xử lý đầy đủ C++ 17 trong MS và GNU tiếng địa phương). Chúng đã được sử dụng để xử lý hàng triệu dòng của các hệ thống C và C++ lớn, với các phân tích đầy đủ, chính xác tạo ra các AST với đầy đủ chi tiết về mã nguồn. (Xem the AST for C++'s most vexing parse.)

Answer 4

Như bạn có thể thấy trong answer here tôi, C++ chứa cú pháp mà không thể được deterministically phân tích bởi một LL hoặc phân tích cú pháp LR do giai đoạn loại độ phân giải (thường là bài phân tích cú pháp) thay đổi thứ tự hoạt động, và do đó hình dạng cơ bản của AST (thường được dự kiến ​​sẽ được cung cấp bởi phân tích giai đoạn đầu tiên).

Answer 5

Vấn đề là không bao giờ được định nghĩa như thế này, trong khi đó nó sẽ hứng thú:

gì là tập nhỏ nhất của sửa đổi C++ ngữ pháp đó sẽ là cần thiết để ngữ pháp mới này có thể được phân tích một cách hoàn hảo bởi một "phi "trình phân tích cú pháp yacc" không có ngữ cảnh? (Tận dụng duy nhất của một 'Hack': các định hướng typename/nhận dạng, phân tích cú pháp thông báo cho lexer của mỗi typedef/lớp/struct)

tôi nhìn thấy một vài người:

1. Type Type; bị cấm. Mã định danh được khai báo dưới dạng tên tệp không thể trở thành mã định danh không phải tên tệp (lưu ý rằng struct Type Type không rõ ràng và có thể vẫn được cho phép).

   Có 3 loại names tokens:

   • types: BUILTIN kiểu hoặc vì một typedef/lớp/struct
   • mẫu chức năng
   • định: chức năng/phương pháp và các biến/đối tượng

   Xem xét các hàm mẫu làm mã thông báo khác nhau giải quyết sự mơ hồ func<. Nếu func là tên mẫu chức năng, thì < phải là bắt đầu của danh sách tham số mẫu, nếu không func là con trỏ hàm và < là toán tử so sánh.

2. Type a(2); là một đối tượng khởi tạo. Type a(); và Type a(int) là các nguyên mẫu chức năng.

3. int (k); là hoàn toàn bị cấm, nên được viết int k;

4. typedef int func_type(); và typedef int (func_type)(); cấm.

   Một chức năng typedef phải là một typedef con trỏ hàm: typedef int (*func_ptr_type)();

5. mẫu đệ quy được giới hạn đến 1024, nếu không một tối đa tăng lên có thể được thông qua như là một tùy chọn để trình biên dịch.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); có thể bị cấm quá, thay thế bằng int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   một dòng cho mỗi chức năng nguyên mẫu hoặc khai báo con trỏ hàm.

   Một thay thế rất ưa thích sẽ được thay đổi cú pháp con trỏ hàm khủng khiếp,

   int (MyClass::*MethodPtr)(char*);

   được resyntaxed như:

   int (MyClass::*)(char*) MethodPtr;

   này là chặt chẽ với các nhà điều hành cast (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; cũng có thể bị cấm: một dòng cho mỗi typedef. Do đó nó sẽ trở thành

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long long và đồng. có thể được khai báo trong mỗi tệp nguồn. Như vậy, mỗi nguồn tập tin làm cho việc sử dụng loại int nên bắt đầu với

   #type int : signed_integer(4)

   và unsigned_integer(4) sẽ bị cấm ở bên ngoài mà #type chỉ đây sẽ là một bước tiến lớn vào ngu ngốc sizeof int mơ hồ có mặt trong rất nhiều Tiêu đề C++

Trình biên dịch thực hiện C++ được phân loại lại nếu gặp phải nguồn C++ sử dụng cú pháp không rõ ràng, di chuyển source.cpp quá ambiguous_syntax thư mục và sẽ tự động tạo một bản dịch rõ ràng source.cpp trước khi biên dịch.

Vui lòng thêm cú pháp C++ không rõ ràng của bạn nếu bạn biết một số!