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