Mọi người có ý gì khi nói C++ có "ngữ pháp không thể giải quyết"?

Question

Mọi người có ý gì khi họ nói điều này? Các hàm ý cho lập trình viên và trình biên dịch là gì?

Answer 1

Điều này liên quan đến thực tế là hệ thống mẫu của C++ là Turing complete. Điều này có nghĩa là (theo lý thuyết) bạn có thể tính toán bất cứ điều gì tại thời gian biên dịch với các mẫu mà bạn có thể sử dụng bất kỳ ngôn ngữ hoặc hệ thống hoàn chỉnh nào khác.

Điều này có tác dụng phụ mà một số chương trình C++ hợp lệ dường như không thể được biên dịch; trình biên dịch sẽ không bao giờ có thể quyết định xem chương trình có hợp lệ hay không. Nếu trình biên dịch có thể quyết định tính hợp lệ của tất cả các chương trình, nó sẽ có thể giải quyết Halting problem.

Lưu ý rằng điều này không liên quan gì đến sự mơ hồ của ngữ pháp C++.

---

Edit: Josh Haberman chỉ ra trong các ý kiến ​​dưới đây và trong một blog post với một ví dụ tuyệt vời mà xây dựng một cây phân tích cú pháp cho C++ thực sự là undecideable. Do sự mơ hồ của ngữ pháp, không thể phân tích cú pháp tách biệt khỏi phân tích ngữ nghĩa, và vì phân tích ngữ nghĩa là không thể phân tích, nên phân tích cú pháp.

Xem thêm (liên kết từ bài của Josh):

• C++ grammar: the type name vs object name issue
• C++ grammar: type vs object and template specializations

Answer 2

Điều này có thể có nghĩa là ngữ pháp C++ không rõ ràng về cú pháp, bạn có thể viết ra một số mã có thể có nghĩa là những thứ khác nhau, tùy thuộc vào ngữ cảnh. (Ngữ pháp là một mô tả về cú pháp của một ngôn ngữ. Đó là điều xác định rằng a + b là một hoạt động bổ sung, liên quan đến các biến a và b.)

Ví dụ, foo bar(int(x));, như được viết, có thể là một khai báo bar, kiểu foo, với int (x) là một initializer. Nó cũng có thể là một tuyên bố của một hàm gọi là bar, lấy một int, và trả về một foo. Điều này được định nghĩa trong ngôn ngữ, nhưng không phải là một phần của ngữ pháp.

Ngữ pháp của ngôn ngữ lập trình là quan trọng. Đầu tiên, đó là một cách để hiểu ngôn ngữ, và, thứ hai, đó là một phần của việc biên dịch có thể được thực hiện nhanh chóng. Do đó, các trình biên dịch C++ khó viết và chậm hơn để sử dụng nếu C++ có ngữ pháp rõ ràng. Ngoài ra, nó dễ dàng hơn để làm cho một số lớp lỗi, mặc dù một trình biên dịch tốt sẽ cung cấp đủ manh mối.

Answer 3

Hàm ý cho những người sử dụng ngôn ngữ đó là các thông báo lỗi có thể rất lạ, rất nhanh (trong thực tế điều này không phải là một vấn đề lớn như vậy. Lỗi thư viện STL thường tồi tệ hơn những thứ bạn kết thúc với do ngữ pháp ngôn ngữ).

Ý nghĩa của những người viết trình biên dịch là họ phải dành nhiều thời gian và công sức để biên dịch ngôn ngữ.

Answer 4

Nếu "một số người" bao gồm Yossi Kreinin, sau đó dựa trên những gì ông viết here ...

Hãy xem xét ví dụ sau:

x * y(z); 

trong hai hoàn cảnh khác nhau:

int main() { 
    int x, y(int), z; 
    x * y(z); 
} 

và

int main() { 
    struct x { x(int) {} } *z; 
    x * y(z); 
} 

... ông có nghĩa là "Bạn không thể quyết định bằng cách nhìn tại x * y (z) cho dù tôi t là một biểu thức hoặc một khai báo. " Trong trường hợp đầu tiên, nó có nghĩa là "gọi hàm y với đối số z, sau đó gọi toán tử * (int, int) với x và giá trị trả về của hàm gọi và cuối cùng loại bỏ kết quả." Trong trường hợp thứ hai, nó có nghĩa là "y là một con trỏ tới một cấu trúc x, được khởi tạo để trỏ đến cùng một địa chỉ (garbage & time-bomb) cũng như z."

Giả sử bạn có sự phù hợp của COBOLmania và đã thêm DECLARE vào ngôn ngữ. Sau đó, giây thứ hai sẽ trở thành

int main() { 
    DECLARE struct x { x(int) {} } *z; 
    DECLARE x * y(z); 
} 

và quyền quyết định sẽ xuất hiện. Lưu ý rằng được decidable không làm cho vấn đề con trỏ đến rác đi xa.

Answer 5

'Ngữ pháp không thể giải quyết' là một lựa chọn rất kém của từ. Một ngữ pháp thực sự không thể giải quyết là như vậy mà không tồn tại không có phân tích cú pháp cho ngữ pháp sẽ chấm dứt trên tất cả các đầu vào có thể. Những gì họ có thể có nghĩa là ngữ pháp C++ không phải là ngữ cảnh miễn phí, nhưng ngay cả điều này có phần là một vấn đề của hương vị: Nơi để vẽ đường giữa cú pháp và ngữ nghĩa? Bất kỳ trình biên dịch nào cũng chỉ chấp nhận một tập hợp con thích hợp của các chương trình vượt qua giai đoạn phân tích cú pháp mà không có lỗi cú pháp và chỉ một tập hợp con thích hợp của các chương trình đó thực sự không có lỗi, do đó không có ngôn ngữ nào thực sự không có ngữ cảnh hoặc thậm chí có thể giải mã được (có thể là một số ngôn ngữ bí truyền) .