LALR Parser Generator Implementation Problem

Question

Tôi hiện đang cố gắng triển khai trình tạo trình phân tích cú pháp LALR như được mô tả trong "các kỹ thuật và công cụ nguyên tắc biên dịch" (còn được gọi là "cuốn sách rồng").

Rất nhiều thứ đã hoạt động. Trình tạo trình phân tích cú pháp hiện có thể tạo ra biểu đồ goto đầy đủ.

Example Grammar: 
        S' --> S 
        S --> C C 
        C --> c C 
        C --> d 

Nonterminals: S', S, C 
Terminals: c, d 
Start: S' 

Các goto-graph:

I[0]---------------+  I[1]-------------+ 
| S' --> . S , $ |--S-->| S' --> S . , $ | 
| S --> . C C , $ |  +----------------+ 
| C --> . c C , c | 
| C --> . c C , d |  I[2]--------------+ 
| C --> . d , c |  | S --> C . C , $ |  I[3]--------------+ 
| C --> . d , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ | 
+------------------+  | C --> . d , $ |  +-----------------+ 
    | |     +-----------------+ 
    | |   +--c--+ |  | 
    | |   |  | c  | 
    | |   |  v v  | 
    | |  I[4]--------------+ | 
    | c  | C --> c . C , c | | 
    | |  | C --> c . C , d | | 
    | |  | C --> c . C , $ | d 
    | |  | C --> . c C , c | | 
    | +---->| C --> . c C , d | | 
    |  | C --> . c C , $ | | 
    d  | C --> . d , c |--+ | 
    | +-----| C --> . d , d | | | 
    | |  | C --> . d , $ | | | 
    | |  +-----------------+ | | 
    | C       | | 
    | |  I[6]--------------+ | | 
    | |  | C --> c C . , c | d | 
    | +---->| C --> c C . , d | | | 
    |  | C --> c C . , $ | | | 
    |  +-----------------+ | | 
    |        | | 
    |  I[5]------------+ | | 
    |  | C --> d . , c |<---+ | 
    +------->| C --> d . , d |  | 
      | C --> d . , $ |<-----+ 
      +---------------+ 

Tôi có trubbles với việc thực hiện các thuật toán để tạo ra các hành động bàn! thuật toán của tôi tính toán đầu ra sau đây:

state | action  
     | c | d | $ 
------------------------ 
    0 | s4 | s5 | 
------------------------ 
    1 |  |  | acc 
------------------------ 
    2 | s4 | s5 | 
------------------------ 
    3 |  |  | r? 
------------------------ 
    4 | s4 | s5 | 
------------------------ 
    5 | r? | r? | r? 
------------------------ 
    6 | r? | r? | r? 

sx ... chuyển sang trạng thái x
rx ... giảm trạng thái x

Các r? có nghĩa là tôi không biết làm thế nào để có được trạng thái (?) mà trình phân tích cú pháp sẽ giảm. Có ai biết một thuật toán để có được? sử dụng biểu đồ goto ở trên?

Nếu bất cứ điều gì được mô tả không đủ rõ ràng, vui lòng hỏi và tôi sẽ cố gắng giải thích tốt hơn! Cảm ơn sự giúp đỡ của bạn!

Answer 1

Mục nhập thay đổi được quy định bởi trạng thái tiếp theo, nhưng mục nhập giảm cho biết sản xuất.

Khi bạn thay đổi, bạn đẩy tham chiếu trạng thái lên ngăn xếp của mình và chuyển sang trạng thái tiếp theo.

Khi bạn giảm, điều này là dành cho một quá trình sản xuất cụ thể. Việc sản xuất chịu trách nhiệm chuyển các trạng thái n sang ngăn xếp của bạn, trong đó n là số lượng các ký hiệu trong quá trình sản xuất đó. Ví dụ. một cho S ', hai cho S, và hai hoặc một cho C (tức là cho thay thế đầu tiên hoặc thứ hai cho C).

Sau khi n mục được bật ra khỏi ngăn xếp, bạn quay lại trạng thái nơi bạn bắt đầu xử lý sản xuất đó. Đối với trạng thái đó và không có kết quả từ việc sản xuất, bạn tra cứu bảng goto để tìm trạng thái tiếp theo, sau đó được đẩy.

Vì vậy, các mục giảm sẽ xác định sản xuất. Trong thực tế nó có thể là đủ để biết nonterminal kết quả, và số lượng các biểu tượng để bật.

bảng của bạn như vậy, nên đọc

state | action  | goto 
     | c | d | $ | C | S 
------------------------------------ 
    0 | s4 | s5 |  | 2 | 1 
------------------------------------ 
    1 |  |  | acc |  | 
------------------------------------ 
    2 | s4 | s5 |  | 3 | 
------------------------------------ 
    3 |  |  | r0 |  | 
------------------------------------ 
    4 | s4 | s5 |  |  | 6 
------------------------------------ 
    5 | r3 | r3 | r3 |  | 
------------------------------------ 
    6 | r2 | r2 | r2 |  | 

nơi rx chỉ giảm sản xuất x.

Answer 2

Bạn cần bật ngăn xếp và tìm trạng thái tiếp theo từ đó.

Answer 3

Phương tiện rx: giảm sử dụng sản xuất với số x!
Sau đó mọi thứ trở nên rõ ràng! Đơn giản bật cơ thể của sản xuất và chuyển đầu trở lại lên trên!