Làm cách nào để triển khai ngăn xếp có cấu trúc biểu đồ?

Question

Ok, vì vậy tôi muốn tạo một trình tạo trình phân tích cú pháp GLR. Tôi biết có tồn tại các chương trình như vậy tốt hơn những gì tôi có thể sẽ làm, nhưng tôi đang làm điều này để vui chơi/học tập vì vậy điều đó không quan trọng.

Tôi đã đọc về phân tích cú pháp GLR và tôi nghĩ rằng tôi có một sự hiểu biết mức độ cao về nó ngay bây giờ. Nhưng bây giờ là lúc để làm quen.

Ngăn xếp có cấu trúc biểu đồ (GSS) là cấu trúc dữ liệu chính để sử dụng trong trình phân tích cú pháp GLR. Về mặt khái niệm, tôi biết GSS hoạt động như thế nào, nhưng không có nguồn nào tôi xem xét cho đến nay giải thích cách triển khai GSS. Tôi thậm chí không có danh sách hoạt động có thẩm quyền để hỗ trợ. Ai đó có thể chỉ cho tôi một số mã mẫu/hướng dẫn mẫu tốt cho GSS không? Google đã không giúp đỡ cho đến nay. Tôi hy vọng câu hỏi này không quá mơ hồ.

Answer 1

Câu hỏi mà bạn đang đặt ra không đáng kể. Tôi thấy hai cách chính để thực hiện việc này:

1. Biểu diễn trực tiếp. Cấu trúc dữ liệu của bạn được biểu diễn trong bộ nhớ dưới dạng các đối tượng/cấu trúc nút, trong đó mỗi nút có một tham chiếu/con trỏ tới các cấu trúc bên dưới nó trên ngăn xếp (cũng có thể làm cho tham chiếu hai hướng, thay thế). Đây là cách danh sách và cây thường được biểu diễn trong bộ nhớ. Nó phức tạp hơn một chút trong trường hợp này, bởi vì không giống như một cây hoặc danh sách, nơi người ta chỉ cần duy trì một tham chiếu đến nút gốc hoặc nút đầu để theo dõi cây, ở đây chúng ta cần phải duy trì một danh sách các tham chiếu đến tất cả các nút 'cấp cao nhất'.

2. Biểu diễn danh sách kề. Điều này tương tự như cách mà các nhà toán học thích nghĩ về đồ thị: G = (V, E). Bạn duy trì một danh sách các cạnh, được lập chỉ mục bởi các đỉnh là điểm xuất phát và điểm kết thúc cho mỗi cạnh.

Tùy chọn đầu tiên có lợi thế là việc truyền tải có thể nhanh hơn, miễn là GSS không quá phẳng. Nhưng cấu trúc hơi khó làm việc hơn. Bạn sẽ phải cuộn rất nhiều thuật toán của riêng bạn.

Tùy chọn thứ hai có lợi thế là đơn giản hơn để làm việc. Hầu hết các thuật toán trong sách giáo khoa dường như giả định một số loại đại diện danh sách kề, điều này làm cho việc áp dụng sự giàu có của các thuật toán đồ thị trở nên dễ dàng hơn.

Một số tài nguyên:

Có nhiều loại danh sách kề nhau, ví dụ: bảng băm dựa trên, mảng dựa trên, vv Các wikipedia adjacency list trang là một nơi tốt để bắt đầu.

Here's a blog post từ người nào đó đang vật lộn với cùng một vấn đề. Mã là clojure, có thể có hoặc không quen thuộc, nhưng các cuộc thảo luận là đáng xem, ngay cả khi không.

Tôi nên đề cập rằng tôi muốn có thêm thông tin về đại diện cho Đồ thị tuần hoàn được chỉ định (hoặc Graph Structured Stacks, nếu bạn thích), với ứng dụng rộng rãi của loại mô hình này. Tôi nghĩ rằng có chỗ cho các giải pháp tốt hơn để được tìm thấy.

Answer 2

Trước tiên, nếu bạn chưa có, bạn nên đọc bài báo của McPeak về GLR http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps. Đây là một tài liệu học thuật, nhưng nó cung cấp các chi tiết tốt về GSS, GLR và các kỹ thuật được sử dụng để thực hiện chúng. Nó cũng giải thích một số vấn đề về lông với việc thực hiện một trình phân tích cú pháp GLR.

Bạn có ba phần để triển khai ngăn xếp có cấu trúc biểu đồ.

I. Cấu trúc dữ liệu biểu đồ chính nó

II. Ngăn xếp

III. GLR sử dụng GSS

Bạn nói đúng, google không giúp được gì nhiều. Và trừ khi bạn thích đọc các sách thuật toán, chúng cũng sẽ không giúp được gì nhiều.

I. Cấu trúc dữ liệu biểu đồ

Câu trả lời của Rob về "trình bày trực tiếp" sẽ dễ triển khai nhất. Nó giống như một danh sách liên kết, ngoại trừ mỗi nút có danh sách các nút tiếp theo thay vì chỉ một nút.

Cấu trúc dữ liệu này là đồ thị được chỉ dẫn, nhưng như là trạng thái McPeak, GSS có thể có chu kỳ cho ngữ pháp epsilon.

II. Ngăn xếp

Ngăn xếp có cấu trúc biểu đồ chỉ là một danh sách các ngăn xếp thông thường. Đối với một ngữ pháp rõ ràng, bạn chỉ cần một ngăn xếp. Bạn cần nhiều ngăn xếp hơn khi có xung đột phân tích cú pháp để bạn có thể thực hiện cả hai hành động phân tích cú pháp cùng một lúc và duy trì trạng thái khác nhau mà cả hai hành động đều tạo. Sử dụng biểu đồ cho phép bạn tận dụng lợi thế của thực tế là các ngăn xếp chia sẻ các yếu tố này.

Có thể giúp hiểu cách triển khai một ngăn xếp đơn lẻ với danh sách được liên kết trước. Người đứng đầu danh sách được liên kết là đầu của ngăn xếp. Đẩy một phần tử vào ngăn xếp chỉ là tạo một cái đầu mới và chỉ nó vào đầu cũ. Popping một yếu tố ra khỏi ngăn xếp chỉ là di chuyển con trỏ đến đầu-> tiếp theo.

Trong GSS, nguyên tắc là như nhau. Đẩy một phần tử chỉ là tạo một nút đầu mới và trỏ nó đến đầu cũ. Nếu bạn có hai thao tác dịch chuyển, bạn sẽ đẩy hai phần tử lên đầu cũ và sau đó có hai nút đầu. Về mặt khái niệm, đây chỉ là hai ngăn xếp khác nhau xảy ra khi chia sẻ mọi phần tử ngoại trừ các yếu tố hàng đầu. Popping một phần tử chỉ di chuyển con trỏ đầu xuống ngăn xếp bằng cách làm theo từng nút tiếp theo.

III. GLR sử dụng GSS

Đây là nơi mà giấy của McPeak là một tài liệu hữu ích.

Thuật toán GLR tận dụng lợi thế của GSS bằng cách hợp nhất các đầu ngăn xếp có cùng phần tử trạng thái. Điều này có nghĩa là một phần tử trạng thái có thể có nhiều hơn một đứa trẻ. Khi giảm, thuật toán GLR sẽ phải khám phá tất cả các đường dẫn có thể có từ đầu ngăn xếp.

Bạn có thể tối ưu hóa GLR bằng cách duy trì độ sâu xác định của mỗi nút. Đây chỉ là khoảng cách từ sự phân chia trong ngăn xếp. Bằng cách này, bạn không phải luôn luôn tìm kiếm một ngăn xếp ngăn xếp.

Đây là một nhiệm vụ khó khăn! Vậy thì chúc may mắn!