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] Dựng toàn bộ bảng phân tích LL(1)

    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ì).

    Xây dựng toàn bộ bảng phân tích cú pháp LL(1) MMM theo đúng quy tắc chuẩn (xem hai bài trước cùng chủ đề về cách điền bảng LL(1)): hàng là mọi ký hiệu chưa kết thúc của văn phạm, cột là mọi ký hiệu kết thúc xuất hiện ở vế phải ít nhất một sản xuất nào đó trong văn phạm, cộng thêm cột $.

    Với mỗi ô M[A,a]M[A, a]M[A,a] không rỗng: nếu chỉ có đúng 1 sản xuất được đặt vào đó, ô đó là bình thường; nếu có từ 2 sản xuất trở lên, đó là ô xung đột (conflict) và văn phạm không phải LL(1).

    Ví dụ: Với văn phạm

    2
S -> a
S -> a b

    cột terminal của văn phạm là a, b (cộng $); ô M[S,a]M[S,a]M[S,a] chứa cả sản xuất 1 và 2 ⇒\Rightarrow⇒ xung đột.

    • Đị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.
    • Định dạng đầu ra:

      In ra mỗi ô không rỗng của bảng MMM trên một dòng, duyệt theo thứ tự: hàng AAA tăng dần theo alphabet (A-Z); trong mỗi hàng, cột aaa theo thứ tự: các terminal xuất hiện trong văn phạm sắp xếp tăng dần theo mã ASCII, rồi đến cột $ (cuối cùng). Bỏ qua các ô rỗng (không sản xuất nào được đặt vào). Định dạng mỗi dòng:

      • Nếu ô chỉ có 1 sản xuất: A a: i (với iii là chỉ số 1-based sản xuất đó).
      • Nếu ô xung đột (nhiều sản xuất): A a: i1,i2,... CONFLICT (các chỉ số sản xuất, tăng dần, cách nhau dấu phẩy, rồi khoảng trắng và chữ CONFLICT).

      Sau khi liệt kê hết các ô không rỗng, in thêm 1 dòng cuối cùng: LL(1) nếu không có ô xung đột nào trong toàn bảng, ngược lại NOT LL(1).

    Ví dụ:

    Đầu vào:

    5
Start -> X Y
X -> a
X -> a b
Y -> c
Y -> c d

    Đầu ra:

    Start a: 1
X a: 2,3 CONFLICT
Y c: 4,5 CONFLICT
NOT LL(1)

    Đầu vào:

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

    Đầu ra:

    E (: 1
E i: 1
F (: 7
F i: 8
T (: 4
T i: 4
X ): 3
X +: 2
X $: 3
Y ): 6
Y *: 5
Y +: 6
Y $: 6
LL(1)

    Đang tải editor...