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] Liệt kê tập lựa chọn SELECT của từng luật sinh

    Để xây dựng bảng phân tích cú pháp LL(1)LL(1)LL(1), với mỗi luật sinh A→αA \to \alphaA→α ta cần tính tập lựa chọn: SELECT(A→α)=(FIRST(α)∖{ε})∪{FOLLOW(A)neˆˊu ε∈FIRST(α)∅ngược lại\text{SELECT}(A \to \alpha) = \big(\text{FIRST}(\alpha) \setminus \{\varepsilon\}\big) \cup \begin{cases}\text{FOLLOW}(A) & \text{nếu } \varepsilon \in \text{FIRST}(\alpha)\\ \emptyset & \text{ngược lại}\end{cases}SELECT(A→α)=(FIRST(α)∖{ε})∪{FOLLOW(A)∅​neˆˊu ε∈FIRST(α)ngược lại​ Đây chính là hàng — cột trong bảng phân tích M[A,a]M[A, a]M[A,a] ứng với sản xuất đó: với mọi a∈SELECT(A→α)a \in \text{SELECT}(A \to \alpha)a∈SELECT(A→α), ô M[A,a]M[A, a]M[A,a] sẽ chứa luật sinh A→αA \to \alphaA→α (nếu văn phạm là LL(1)LL(1)LL(1) thì mỗi ô có tối đa một luật sinh).

    Cho văn phạm GGG gồm nnn luật sinh được đánh số 1,2,…,n1, 2, \dots, n1,2,…,n theo đúng thứ tự xuất hiện trong input, hãy in ra SELECT\text{SELECT}SELECT của TỪNG luật sinh (không quan tâm văn phạm có phải LL(1)LL(1)LL(1) hay không — nếu có xung đột giữa hai luật sinh, chúng vẫn có SELECT riêng, cứ in ra bình thường).

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

    E -> T X
X -> + T X
X -> eps
T -> id

    (luật sinh 1: E→TXE \to TXE→TX, 2: X→+TXX \to {+}TXX→+TX, 3: X→εX \to \varepsilonX→ε, 4: T→idT \to idT→id), ta có SELECT(1)={id}\text{SELECT}(1) = \{id\}SELECT(1)={id}, SELECT(2)={+}\text{SELECT}(2) = \{+\}SELECT(2)={+}, \text{SELECT}(3) = \text{FOLLOW}(X) = \{\},, ,\text{SELECT}(4) = {id}$.

    • Định dạng đầu vào:
      • Dòng đầu tiên chứa số nguyên nnn (1≤n≤2001 \le n \le 2001≤n≤200) — số luật sinh (production) của văn phạm.
      • nnn dòng tiếp theo, mỗi dòng có dạng A -> X1 X2 ... Xk (giữa A và ->, giữa -> và X1X_1X1​, giữa các XiX_iXi​ luôn có khoảng trắng); AAA là kí hiệu ở vế trái, X1,…,XkX_1,\dots,X_kX1​,…,Xk​ là các kí hiệu ở vế phải. Nếu vế phải là chuỗi rỗng ε\varepsilonε, dòng có dạng A -> eps (đúng một kí hiệu eps).
      • Một kí hiệu là kí hiệu CHƯA KẾT THÚC (nonterminal) nếu nó xuất hiện ở vế trái của ít nhất một trong nnn luật sinh; mọi kí hiệu khác xuất hiện trong văn phạm (khác eps) là kí hiệu KẾT THÚC (terminal). Kí hiệu bắt đầu (start symbol) của văn phạm là vế trái của luật sinh ở dòng đầu tiên (dòng thứ hai của input). Có thể có nhiều luật sinh cùng vế trái, nằm ở các dòng khác nhau, không nhất thiết liền kề.
      • Kí hiệu kết thúc chuỗi vào (end-of-input marker), dùng khi tính FOLLOW, được kí hiệu là $.
    • Định dạng đầu ra:

      In ra đúng nnn dòng, dòng thứ iii (1≤i≤n1 \le i \le n1≤i≤n, theo đúng thứ tự luật sinh trong input) có dạng i: s1 s2 ... sm trong đó s1<s2<…s_1 < s_2 < \dotss1​<s2​<… là các phần tử của SELECT\text{SELECT}SELECT của luật sinh thứ iii, sắp xếp tăng dần theo thứ tự từ điển thông thường, cách nhau đúng một khoảng trắng — RIÊNG kí hiệu $ (nếu có) luôn được in ở CUỐI dòng bất kể thứ tự từ điển. Nếu tập SELECT rỗng, in dòng i: không có khoảng trắng thừa phía sau.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    1: ( id
2: +
3: ) $
4: ( id
5: *
6: ) + $
7: (
8: id

    Đầu vào:

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

    Đầu ra:

    1: id
2: +
3: $
4: id

    Đang tải editor...