Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Mô phỏng phân tích cú pháp LL(1) dùng ngăn xếp

    Quy ước biểu diễn văn phạm phi ngữ cảnh (dùng chung cho các câu hỏi cùng chủ đề):

    • Dòng đầu tiên là số nguyên nnn — số sản xuất (production).
    • nnn dòng tiếp theo, mỗi dòng có dạng A -> X1 X2 ... Xk, trong đó các ký hiệu cách nhau đúng 1 khoảng trắng:
      • A là ký hiệu chưa kết thúc (nonterminal): đúng 1 chữ cái in HOA (A-Z).
      • Mỗi Xi là một token — hoặc là 1 ký hiệu chưa kết thúc (chữ in hoa đã/ sẽ xuất hiện ở vế trái sản xuất nào đó), hoặc là 1 ký hiệu kết thúc (terminal): đúng 1 ký tự bất kỳ không phải chữ in hoa (chữ thường, chữ số, hoặc ký hiệu như + * ( ) , ; ...). Đảm bảo không ký hiệu kết thúc nào là $, #, hay trùng chuỗi eps.
      • Nếu vế phải là chuỗi rỗng ε\varepsilonε, dòng ghi A -> eps (đúng 1 token eps, không kèm ký hiệu nào khác).
    • Ký hiệu bắt đầu của văn phạm là vế trái của sản xuất ở dòng thứ 2 của input (sản xuất đầu tiên).
    • Các sản xuất được đánh số 1..n theo đúng thứ tự xuất hiện trong input.
    • Văn phạm luôn hợp lệ: mọi ký hiệu chưa kết thúc đều dẫn xuất được ra ít nhất một chuỗi hữu hạn (gồm terminal, có thể là ε\varepsilonε), không có ký hiệu chưa kết thúc "chết" (không thể dẫn xuất ra gì).

    Ràng buộc bổ sung cho bài này: văn phạm đã cho được đảm bảo là LL(1) (không có ô xung đột nào trong bảng phân tích, xây dựng theo đúng quy tắc chuẩn ở các bài trước cùng chủ đề) và không đệ quy trái (trực tiếp lẫn gián tiếp), nên việc mô phỏng dưới đây luôn dừng.

    Cho thêm một dòng biểu diễn chuỗi ký hiệu kết thúc đầu vào cần phân tích (các token cách nhau bởi khoảng trắng; nếu chuỗi rỗng thì dòng ghi eps). Mô phỏng bộ phân tích cú pháp LL(1) dùng ngăn xếp (stack) theo thuật toán chuẩn:

    • Ngăn xếp ban đầu chứa [\, S]vớivớivớiSlaˋkyˊhiệuba˘ˊtđa^ˋu( là ký hiệu bắt đầu (laˋkyˊ​hiệuba˘ˊtđa^ˋu(S$ ở đỉnh ngăn xếp).
    • Con trỏ đọc đầu vào bắt đầu tại ký hiệu đầu tiên; cuối chuỗi đầu vào được xem như có thêm $.
    • Lặp: gọi ttt là ký hiệu đỉnh ngăn xếp, ccc là ký hiệu đầu vào hiện tại.
      • Nếu $t = c = $$: dừng, chấp nhận (ACCEPT).
      • Nếu ttt là terminal (hoặc $): nếu t=ct = ct=c thì bỏ ttt khỏi ngăn xếp và dịch con trỏ đầu vào sang phải 1 vị trí; nếu t≠ct \ne ct=c thì dừng, từ chối (REJECT).
      • Nếu ttt là nonterminal: tra ô M[t,c]M[t, c]M[t,c] của bảng LL(1); nếu ô rỗng thì dừng, REJECT; nếu ô có sản xuất t→γt \to \gammat→γ (chỉ số iii), ghi nhận đã áp dụng sản xuất iii, bỏ ttt khỏi ngăn xếp rồi đẩy các ký hiệu của γ\gammaγ vào ngăn xếp theo đúng thứ tự (ký hiệu bên trái của γ\gammaγ nằm gần đỉnh hơn — tức đẩy γ\gammaγ theo thứ tự từ phải sang trái); nếu γ=ε\gamma = \varepsilonγ=ε thì không đẩy gì cả.

    Ví dụ: Với văn phạm biểu thức số học kinh điển đã loại đệ quy trái

    4
E -> T X
X -> + T X
X -> eps
T -> i

    và chuỗi nhập i + i, dãy sản xuất được áp dụng là 1, 4, 2, 4, 3 rồi ACCEPT.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên nnn (1≤n≤1001 \le n \le 1001≤n≤100).
      • nnn dòng tiếp theo: các sản xuất theo quy ước chung (đảm bảo LL(1), không đệ quy trái).
      • Dòng cuối: chuỗi token đầu vào (các terminal cách nhau bởi khoảng trắng), hoặc eps nếu chuỗi rỗng.
    • Định dạng đầu ra:

      In ra mỗi chỉ số sản xuất (1-based) đã áp dụng, theo đúng thứ tự áp dụng, mỗi số một dòng. Sau khi liệt kê hết, in thêm 1 dòng cuối cùng: ACCEPT nếu quá trình phân tích kết thúc thành công, hoặc REJECT nếu gặp lỗi (không khớp terminal hoặc ô bảng rỗng).

    Ví dụ:

    Đầu vào:

    1
S -> a
a

    Đầu ra:

    1
ACCEPT

    Đầu vào:

    8
E -> T X
X -> + T X
X -> eps
T -> F Y
Y -> * F Y
Y -> eps
F -> ( E )
F -> i
i + i * i

    Đầu ra:

    1
4
8
6
2
4
8
5
8
6
3
ACCEPT

    Đang tải editor...