Bài giảng Xây dựng chương trình dịch: Bài 8 - Nguyễn Thị Thu Hương

Bài giảng "Xây dựng chương trình dịch - Bài 8: Văn phạm LL(k)" trình bày các nội dung: Phân cấp các ngôn ngữ phi ngữ cảnh, ngôn ngữ LL (k), văn phạm LL(k), văn phạm LL(k) đơn giản. Đây là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Xây dựng chương trình dịch: Bài 8 - Nguyễn Thị Thu Hương 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) Xem trước k ký hiệu trên xâu vào để quyết định sản xuất được sử dụng „ Được sinh ra nhờ văn phạm LL(k) „ FIRSTk(α) Đị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) 1 21/1/2010 FIRSTk(α) FOLLOWk(α) Định nghĩa : Cho văn phạm G = (Σ, Δ, P, S), số nguyên dương g 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)) Đặc biệt , khi A là ký hiệu không kết thúc, S suy dẫn ra bA thì FOLLOW1(A) ={ε} Văn phạm LL(k) FOLLOWk(α) FOLLOWk(α) = {x ∈ Σ* | S ⇒* βαδ và x∈ FIRSTk(δ)} Đặc biệt , khi α =A Đặ A ∈ Δ* , S FOLLOW1(A) ={ε} k ký hiệu kết thúc đầu tiên tiếp sau xâu được suy dẫn từ α. ⇒** βA thì Đị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 ọ cặp ặp suyy dẫn trái mọi S => xAα => xβ1α => xZ1 S => xAα => xβ2α => xZ2 Nếu FIRSTk(Z1) = FIRSTk(Z2) thì β1 = β2 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 Văn phạm G với các sản xuất : S → aAS | b A → bSA | a „ Đị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 „ A → α1 | α2 | . . . . | αn , n ≥ 2 thoả mãn FIRST1(αi) ∩ FIRST1(αj) = ∅ „ Nếu αi ⇒ * ε thì FIRST1(αi) ∩ FOLLOW1(A) =∅ , i ≠ j Ở mỗi lối rẽ, các nhánh phải bắt đầu bằng các ký hiệu khác nhau „ Nếu biểu đồ có chứa một đường rỗng thì mọi ký hiệu đứng sau ký hiệu được biểu diễn bởi biểu đồ phải khác các ký hiệu đứng đầu các nhánh của sơ đồ „ 3 21/1/2010 Văn phạm KPL là LL(1) A FIRST(A) FOLLOW(A) Block CONST, VAR,TYPE, PROCEDURE,BEGIN .,; Unsignedconst ident, number,’ Constant +,-,’,ident,number T Type id t i t ident,integer, char,array h Statement ident, CALL, BEGIN, WHILE,FOR .,;, END Expression +,-,(,ident,number .,;, END,TO,THEN,DO,),,.),=,=,!= Term ident,number, ( .,;,END,TO,THEN,DO,),,=,=,!= Factor ident, number, ( .,;,END,TO,THEN, DO, +, -, *,/,) ,=,=,!= 4