tailieunhanh - 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. | 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| 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, +, -, *,/,) .
đang nạp các trang xem trước
