21/1/2010 Phân cấp các ngôn ngữ phi ngữ cảnh Bài 8. Văn phạm LL(k) Ngôn ngữ LL(k) FIRSTk(α) „ Xem trước k ký hiệu trên xâu vào để quyết Định nghĩa : Cho văn phạm G phi ngữ cảnh, số nguyên dương k , a là một xâu bao gồm ký hiệu kết thúc và không kết thúc FIRSTk(α) là tập các xâu x gồm k ký hiệu kết thúc trái nhất của các xâu suy dẫn từ α (Kể cả trường hợp x không có đủ k ký hiệu nhưng α suy dẫn ra x , không còn ký hiệu nào sau x) định sản xuất được sử dụng „ Được sinh ra nhờ văn phạm LL(k) fb.com/groups/ 1 21/1/2010 FIRSTk(α) FOLLOWk(α) Định nghĩa : Cho văn phạm G = (Σ, Δ, P, S), số nguyên dương k , α ∈ V* FIRSTk(α) = { x ∈ Σ* | α xβ và |x| = k hoặc α x và |x| < k} ( Tập các xâu x ∈Σ* có k ký hiệu trái nhất suy dẫn từ α ( Kể cả trường hợp x không có đủ k ký hiệu nhưng α x , không còn ký hiệu nào sau x)) k ký hiệu kết thúc đầu tiên tiếp sau xâu được suy dẫn từ α. Đặc biệt , khi A là ký hiệu không kết thúc, S suy dẫn ra bA thì FOLLOW1(A) ={ε} FOLLOWk(α) Văn phạm LL(k) FOLLOWk(α) = {x ∈ Σ* | S ⇒* βαδ và x∈ FIRSTk(δ)} Định nghĩa văn phạm phi ngữ cảnh G = (Σ, Δ, P, S) là LL(k) với k cho trước nếu với mọi cặp suy dẫn trái S => xAα => xβ1α => xZ1 S => xAα => xβ2α => xZ2 Nếu FIRSTk(Z1) = FIRSTk(Z2) thì β1 = β2 Đặc biệt , khi α =A ∈ Δ* , S FOLLOW1(A) ={ε} ⇒* βA thì fb.com/groups/ 2 21/1/2010 Ví dụ Văn phạm LL(1) đơn giản là LL(1) Văn phạm G = (Σ, Δ, P, S) là LL(1) đơn giản nếu mọi sản xuất của văn phạm có dạng A → a1α1 | a2α2 |. . . . anα, ai ∈ Σ 1≤ i ≤ n Trong đó ai ≠ aj với i ≠ j Điều kiện nhận biết văn phạm LL(1) Điều kiện LL(1) trên sơ đồ cú pháp Định lý Văn phạm G = (Σ, Δ, P, S) là LL(1) khi và chỉ khi mọi tập A- sản xuất trong P có dạng „ Ở mỗi lối rẽ, các nhánh phải bắt đầu bằng Văn phạm G với các sản xuất : S → aAS | b A → bSA | a „ „ A → α1 | α2 | . . . . | αn , n ≥ 2 thoả mãn FIRST1(αi) ∩ FIRST1(αj) = ∅ „ Nếu αi ⇒ * ε thì FIRST1(αi) ∩ FOLLOW1(A) =∅ , i ≠ j các ký hiệu khác nhau „