Bảng phân tích LL(1) là một bảng hai chiều Table[A,a] với A là non-terminal và a là terminal (hoặc \$$), trong đó ô Table[A,a]chứaluậtsinhA \to \alpha(ne^ˊucoˊ)saochoa \in SELECT(A \to \alpha)(địnhnghı~aSELECT$ như các bài trước).
Với văn phạm LL(1) hợp lệ, mỗi ô có TỐI ĐA một luật sinh; nhưng nếu văn phạm KHÔNG phải LL(1), một ô có thể chứa từ 2 luật sinh trở lên (xung đột). Cho một truy vấn (X,a) (không giả định trước văn phạm là LL(1)), hãy cho biết trạng thái của ô Table[X,a]:
Các luật sinh được đánh số 1,2,…,n theo thứ tự trong input.
Ví dụ, với văn phạm biểu thức số học kinh điển và truy vấn (Y, \):Ycoˊ2luậtsinh,‘Y−>∗FY‘(SELECT={*})vaˋ‘Y−>e‘(SELECT= FOLLOW(Y) = {), +, $});chỉluậtsinhthứhaicoˊ$$ trong SELECT. Kết quả in ra: Y -> e.
A -> X1 X2 ... Xk (hoặc A -> e).X a gồm hai token cách nhau bởi khoảng trắng — X là một non-terminal của văn phạm, a là một terminal của văn phạm hoặc ký hiệu $ (đại diện ký hiệu kết thúc đầu vào).Đảm bảo mọi non-terminal xuất hiện ở vế phải đều có ít nhất một luật sinh định nghĩa nó.
EMPTY.X -> Y1 Y2 ... Yk (các ký hiệu cách nhau đúng một khoảng trắng), hoặc X -> e nếu α=ε.CONFLICT m i1,i2,...,im với i1<i2<…<im là các chỉ số luật sinh liên quan (cách nhau bởi dấu phẩy, không khoảng trắng), và m cách CONFLICT cùng danh sách chỉ số bởi đúng một khoảng trắng.Ví dụ:
Đầu vào:
E
8
E -> T X
X -> + T X
X -> e
T -> F Y
Y -> * F Y
Y -> e
F -> ( E )
F -> id
E (
Đầu ra:
E -> T X
Đầu vào:
E
8
E -> T X
X -> + T X
X -> e
T -> F Y
Y -> * F Y
Y -> e
F -> ( E )
F -> id
F +
Đầu ra:
EMPTY
Đang tải editor...