nút Đưa vào cây phân tích cú pháp mà không nên có mặt ở đó

Question

Tôi viết một phân tích cú pháp cho một ngôn ngữ, và máy quét được thiết kế để

1. một trong hai cũng quay trở lại bến không cần thiết (ví dụ whitespacing) HOẶC
2. không để làm như vậy

dựa trên cờ boolean.

Bây giờ, trong trình phân tích cú pháp, tôi không muốn làm lộn xộn ngữ pháp với tất cả các thiết bị đầu cuối đó, chúng nên được nuốt bằng cách nào đó "tự động" bằng cây phân tích mà tôi đang xây dựng. Để làm điều này "ma thuật", tôi nghĩ rằng tôi sẽ chuỗi các thiết bị đầu cuối (chỉ đơn giản là liên kết danh sách tròn) vì vậy tôi chỉ có thể lặp lại chúng và "điền vào chỗ trống" như giảm xảy ra (Tôi đang sử dụng một LALR (1 Miễn phí) (0)) trình tạo phân tích cú pháp).

Nghe có vẻ như là một ý tưởng lành mạnh, mặc dù có một vấn đề. Hãy nhớ tôi đã nói "để trở về ... hay không"? Trong kịch bản (2), tôi sẽ giải phóng thiết bị đầu cuối, bởi vì ai biết điều gì sẽ xảy ra tiếp theo? Và tôi không muốn bất kỳ rò rỉ bộ nhớ nào.

Nhưng trong trường hợp (1), tôi không thể giải phóng thiết bị đầu cuối, bởi vì dựa trên chúng tôi sẽ quyết định giảm thêm khi quy trình "điền vào chỗ trống" sẽ dừng lại.

Tôi không thể giải phóng điều kiện này, vì cùng một lý do: Tôi không biết điều gì sẽ xảy ra tiếp theo. Điều gì sẽ xảy ra nếu không có bất kỳ quy trình "điền vào chỗ trống nào" được kích hoạt? Điều gì sẽ xảy ra nếu không giảm thêm nữa?

Bạn có gặp sự cố tương tự không? Bạn đã giải quyết nó như thế nào?

Lưu ý: đây là tất cả trong tâm trí của tôi và tôi có thể chưa giải thích rõ ràng, vui lòng hỏi và tôi sẽ chỉnh sửa câu hỏi của mình. Kịch bản thực sự phức tạp hơn một chút, tôi không viết điều này từ đầu, nơi tôi có thể sử dụng trí tưởng tượng của mình, tôi tích hợp nó vào một thứ khác, vì vậy có thể tôi sẽ trả lời với "Tôi không thể làm điều đó vì những hạn chế về môi trường ".

---

Phụ Lục

duy nhất ý tưởng thực sự tốt mà nói đến cái tâm của tôi là đến ngã ba và cải thiện các máy phát điện phân tích cú pháp, mà tôi đã thực hiện ở một số nơi nhỏ ở đây và ở đó, để khắc phục một số những những hạn chế tôi đã đề cập ở trên.

Answer 1

Từ vựng của bạn hơi lạ. Hầu hết các trình phân tích cú pháp được thiết kế để nhận ra cú pháp của ngôn ngữ. thường là định nghĩa ngôn ngữ xác định một số khái niệm về thiết bị đầu cuối và loại trừ một cách rõ ràng "khoảng trống", bao gồm các chuỗi không liên quan giữa văn bản của thiết bị đầu cuối, thường bao gồm khoảng trống, tab và nhiều loại nhận xét tự do khác nhau. Vì vậy, từ "thiết bị đầu cuối" được sử dụng trong phân tích cú pháp thường có nghĩa là "các nguyên tử ngôn ngữ không phải là khoảng trắng". Bạn đã xác định nó hoàn toàn để bao gồm khoảng trắng và tôi nghĩ điều đó đang gây ra nỗi đau của bạn. Từ quan điểm này, cách dễ nhất để tránh việc cắt bỏ định nghĩa ngữ pháp được sử dụng bởi trình phân tích cú pháp của bạn với khoảng trắng, chỉ đơn giản là có lexer không chuyển khoảng trống cho trình phân tích cú pháp. Sau đó ngữ pháp của bạn không cần phải chỉ ra cách chúng được xử lý (và có, ngữ pháp làm như vậy thực sự lộn xộn), trình phân tích cú pháp không phải lo lắng về chúng và chúng không hiển thị trên cây.

Nếu bạn đang xây dựng trình biên dịch hoặc thông dịch viên, thì bỏ qua khoảng trắng là dễ nhất.

Nếu bạn đang xây dựng một trình phân tích cú pháp kỹ thuật lại (xem DMS Software Reengineering Toolkit của chúng tôi, thì ghi chú (ít nhất) trong AST là quan trọng, cuối cùng là một muốn tái tạo văn bản từ các AST bị ràng buộc. [Bạn có thể làm theo cách khác nhưng chúng không dễ dàng như vậy].

Dex lexer tạo ra các thẻ "vi" là khái niệm về thẻ ngôn ngữ, khoảng trống và nhận xét trong nội bộ của bạn. Nó sẽ bỏ đi các thẻ mã thông báo khoảng trắng vì chúng không thêm bất cứ thứ gì (xem phần thảo luận ở trên), nó chuyển các thẻ thông thường tới trình phân tích cú pháp, như bạn mong đợi. loại token và wher e gặp phải; cho C, a/* ... */được nhìn thấy trước khi một mã thông báo được gắn vào nó, và một // ... chú thích được gắn vào mã thông báo trước (với một vài chi tiết tinh tế hơn không được thảo luận ở đây). Sau đó, phân tích cú pháp vẫn chỉ thấy mã thông báo ngôn ngữ, do đó ngữ pháp không cần thiết phức tạp và nếu tất cả thông tin gắn liền với mã thông báo được đặt trong cây thì các nhận xét sẽ đi cùng với chuyến đi.

Hiện tại, mọi người thường muốn có cây cú pháp "Tóm tắt"; họ muốn loại bỏ những thứ như "(" và ")". Đề án tôi mô tả ở trên ý kiến ​​đính kèm để thậm chí cả các thẻ bê tông như thế này. Bây giờ có một biến chứng: nếu bạn để lại (..) mã thông báo ra khỏi cây, các bình luận đính kèm biến mất. Rất tiếc. Vì vậy, các trình phân tích cú pháp DMS thực hiện một điều phức tạp: các chú thích gắn với các thẻ có vị trí hợp lý trong cây nhưng không thực sự ở đó ("các thiết bị đầu cuối bị loại bỏ") được nâng lên nút cây cha với chú thích nói rằng chúng thuộc về mã thông báo con bị thiếu . Có, thực hiện điều này thực sự là một PITA. Tin tốt là chúng tôi chỉ phải làm điều đó một lần trong máy phân tích cú pháp chung của DMS và nó hoạt động với nhiều ngôn ngữ. Nhưng điều này có nghĩa là bạn phải sẵn sàng xây dựng một trình phân tích cú pháp không bình thường ("tái tổ chức") và chúng tôi có động lực thương mại để làm như vậy.

EDIT: Không rõ tại sao OP lại muốn điều này, nhưng anh ta khăng khăng nắm bắt khoảng trống trên cây. Vì anh ấy đã không nói với chúng tôi tại sao, tôi sẽ đoán: anh ấy muốn thông tin cột chính xác cho các nút thẻ/cây. Đó không phải là khó làm: dạy lexer để theo dõi vị trí (dòng/cột), và đóng dấu mỗi mã thông báo (mã thông báo chẳng hạn như nhận xét) với vị trí bắt đầu/kết thúc và để cho cửa hàng phân tích thông tin đó cái cây. Bằng cách này tránh giữ khoảng trắng trong cây, quá. (DMS cũng làm như vậy, vì khi báo cáo vấn đề, thông tin chính xác là hữu ích, và khi tạo lại mã, việc đặt lại mã tại vị trí ban đầu của nó (ít nhất là cùng một cột) thường được mong muốn).

EDIT2: Nếu OP khẳng định khi chụp khoảng trắng, anh ta có thể cân nhắc khám phá scannerless GLR parsing. Điều này giữ mỗi ký tự trong luồng đầu vào, bao gồm khoảng trắng.