Làm cách nào để triển khai các tham chiếu chuyển tiếp trong trình biên dịch?

Question

Tôi đang tạo một trình biên dịch với Lex và YACC (thực sự là Flex và Bison). Ngôn ngữ cho phép tham chiếu chuyển tiếp không giới hạn tới bất kỳ biểu tượng nào (như C#). Vấn đề là không thể phân tích ngôn ngữ mà không biết mã định danh là gì.

Giải pháp duy nhất tôi biết là lex toàn bộ nguồn và sau đó thực hiện phân tích "đầu tiên", vì vậy các cấp cao hơn như khai báo lớp và khai báo hàm được phân tích cú pháp trước các hàm sử dụng chúng. Tuy nhiên, điều này sẽ mất một lượng lớn bộ nhớ cho các tệp lớn và sẽ khó xử lý với YACC (tôi sẽ phải tạo các ngữ pháp riêng cho từng loại khai báo/thân). Tôi cũng sẽ phải viết tay lexer (đó không phải là một vấn đề lớn).

Tôi không quan tâm nhiều về hiệu quả (mặc dù nó vẫn quan trọng), bởi vì tôi sẽ tự viết lại trình biên dịch khi tôi hoàn thành nó, nhưng tôi muốn phiên bản đó nhanh (vì vậy nếu có là bất kỳ kỹ thuật chung nhanh nào không thể thực hiện được trong Lex/YACC nhưng có thể được thực hiện bằng tay, hãy đề nghị chúng cũng được). Vì vậy, ngay bây giờ, dễ phát triển là yếu tố quan trọng nhất.

Có giải pháp nào tốt cho vấn đề này không? Điều này thường được thực hiện như thế nào trong các trình biên dịch cho các ngôn ngữ như C# hoặc Java?

Answer 1

Hoàn toàn có thể phân tích cú pháp. Mặc dù có sự mơ hồ giữa số nhận dạng và từ khóa, lex sẽ vui vẻ đối phó với điều đó bằng cách ưu tiên từ khóa.

Tôi không thấy có vấn đề gì khác. Bạn không cần xác định xem số nhận dạng có hợp lệ trong giai đoạn phân tích cú pháp hay không. Bạn đang xây dựng một cây phân tích cú pháp hoặc một cây cú pháp trừu tượng (sự khác biệt là tinh tế, nhưng không thích hợp cho các mục đích của cuộc thảo luận này) khi bạn phân tích cú pháp. Sau đó, bạn xây dựng các cấu trúc bảng biểu tượng lồng nhau của bạn bằng cách thực hiện vượt qua AST bạn đã tạo trong khi phân tích cú pháp. Sau đó, bạn thực hiện một lần vượt qua AST để kiểm tra các số nhận dạng được sử dụng có hợp lệ hay không. Thực hiện theo điều này với một hoặc nhiều phân tích cú pháp bổ sung trên AST để tạo mã đầu ra, hoặc một số cơ sở dữ liệu trung gian khác và bạn đã hoàn tất!

EDIT: Nếu bạn muốn xem làm thế nào nó được thực hiện, kiểm tra mã nguồn cho cáC# biên dịch Mono C. Điều này thực sự được viết bằng C# thay vì C hoặc C++, nhưng nó sử dụng cổng .NET của Jay rất giống với yacc.

Answer 2

Một lựa chọn là để đối phó với sự tham khảo về phía trước bằng cách chỉ quét và bộ nhớ đệm tokens cho đến khi bạn nhấn một cái gì đó bạn biết làm thế nào để thực sự với (loại giống như "hoảng loạn chế độ" phục hồi lỗi). Một khi bạn đã chạy nghĩ rằng tập tin đầy đủ, quay trở lại và cố gắng phân tích lại các bit mà không phân tích cú pháp trước.

Khi phải viết tay từ vựng; không, sử dụng lex để tạo một trình phân tích cú pháp thông thường và chỉ đọc từ nó thông qua một shim viết tay cho phép bạn quay trở lại và cung cấp cho trình phân tích cú pháp từ bộ nhớ cache cũng như những gì mà lex tạo ra.

Như để làm cho nhiều văn phạm tiếng, một chút vui vẻ với một tiền xử lý trên file yacc và bạn sẽ có thể để làm cho tất cả chúng ra của cùng một nguồn gốc