PHÂN TÍCH CÚ PHÁP VÀ CÁC PHƯƠNG PHÁP PHÂN TÍCH CƠ BẢN MỤC ĐÍCH Phân tích cú pháp nhận đầu vào danh sách từ tố chương trình nguồn thành thành phần theo văn phạm biểu diễn cấu trúc phân tích theo cấu trúc tương đương với u cầu từ tố Chương trình nguồn Phân tích từ vựng Phân tích cú pháp Phân tích ngữ nghĩa từ tố Bảng ký hiệu Bộ phân tích cú pháp nhận chuỗi token từ phân tích từ vựng tạo phân tích cú pháp Trong thực tế cịn số nhiệm vụ thu nhập thơng tin token vào bảng ký hiệu, thực kiểm tra kiểu phân tích ngữ nghĩa sinh mã trung gian Các phần trình bày chương kế HOẠT ĐỘNG CỦA BỘ PHÂN TÍCH 2.1.Văn phạm phi ngữ cảnh 2.1.1 Định nghĩa * Định nghĩa: Văn phạm PNC (như trên) * Dạng BNF (Backus – Naur Form) văn phạm phi ngữ cảnh + Các ký tự viết hoa: biểu diễn ký hiệu không kết thúc, (có thể thay xâu đặt dấu ngoặc < > từ in nghiêng) + Các ký tự viết chữ nhỏ dấu toán học: biểu diễn ký hiệu kết thúc (có thể thay xâu đặt cặp dấu nháy kép “ ” từ in đậm) + ký hiệu -> = là: ký hiệu phạm trù cú pháp vế trái giải thích vế phải + ký hiệu | lựa chọn Ví dụ: = | | “(” “)” ToánHạng -> Tên | Số | ( BiểuThức 2.1.2 Đồ thị chuyển biểu diễn văn phạm phi ngữ cảnh: chu cai Start chu cai khac 2* chu cai Hình 2.1: Đồ thị chuyển cho từ tố Tên - Các vòng tròn với ký hiệu bên biểu thị cho trạng thái Các chữ cung biểu thị cho ký hiệu vào Trạng thái vẽ vòng tròn kép trạng thái kết thúc Nếu trạng thái kết thúc có dấu * nghĩa ký hiệu cuối khơng thuộc xâu đốn nhận 2.1.3 Cây suy dẫn 2.1.3.1 Suy dẫn Cho văn phạm G=(T,N,P,S) - Suy dẫn trực tiếp quan hệ hai ký hiệu => tập V* αβγ xâu thuộc V* β->δ sản xuất P, αβγ => αδγ k k - Suy dẫn k bước, ký hiệu => hay α => β tồn dãy α0, α1, , αk cho: α = α0 => α1 => => αk = β ¿ - Xâu α suy dẫn xâu k>=0 ký hiệu α => β + - Xâu α suy dẫn không tầm thường xâu β k>0 ký hiệu α => β 2.1.3.2 Cây phân tích (cây suy dẫn) * Định nghĩa: Cây phân tích văn phạm phi ngữ cảnh G = (T,N,P,S) thỏa mãn điều kiện sau: Mọi nút có nhãn, ký hiệu (T  N  {ε})ε})})) Nhãn gốc S Nếu nút có nhãn X nút X  N Nếu nút n có nhãn X nút theo thứ tự trái qua phải có nhãn Y1, Y2, , Yk X->Y1Y2 Yk sản xuất  P Nút có nhãn thuộc T ε}) * Suy dẫn trái (nói gọn suy dẫn trái), bước suy dẫn, biến thay biến nằm bên trái dạng câu * Suy dẫn phải nhất: (nói gọn suy dẫn phải), bước suy dẫn, biến thay biến nằm bên phải dạng câu 2.1.3.3 Đệ qui * Định nghĩa: Ký hiệu không kết thúc A văn phạm gọi đệ qui + tồn tại: A => αAβ với α, β  V+  Nếu α = ε}) A gọi đệ qui trái  Nếu β = ε}) A gọi đệ qui phải  Nếu α,β  ε}) A gọi đệ qui * Có loại dệ quy trái :  Loại ttrực tiếp: có dạng A  A ( A + A )  Loại gián tiếp: Gây nhiều bước suy dẫn (VÝ dô: S Aa | b; AAc | Sd; S đệ qui trái S Aa Sda) * Loại bỏ đệ qui trái: (loại bỏ suy dẫn A =>+ A ) - Giả sử có luật đệ qui trái A->A |  thay luật luật: A -> A’ A’ -> A’ |  - Tổng qt hố lên ta có: Nếu có luật đệ qui trái: A -> A1 | A2 | | Am | 1 | 2 | | n khơng i bắt đầu A Thay sản xuất sản xuất: A -> 1A’ | 2A’ | | nA’ A’ -> 1A’ | 2A’ | | mA’ |  Ví dụ2: Xét văn phạm biểu thức số học sau: E -> E + T | T ; T -> T * F | F; F -> ( E ) | id Loại bỏ đệ qui trái trực tiếp cho sản xuất E T, ta văn phạm khơng cịn sản xuất có đệ qui trái sau: E -> TE’; E’-> +TE’ | ; T -> FT’; T’ -> *FT’ | ; F -> (E) | id Qui tắc loại bỏ đệ qui trái trực tiếp nằm sản xuất không loại bỏ đệ qui trái nằm dẫn xuất có hai nhiều bước Qui tắc không loại bỏ đệ qui trái khỏi sản xuất A->A Input: Văn phạm khơng tuần hồn e_sx (khơng có dạng Aị+A Ađe) Output: Văn phạm tương đương không đệ qui trái Phương pháp: Sắp xếp ký hiệu không kết thúc theo thứ tự A1, A2 An For i:=1 to n Begin for j:=1 to i-1 Begin Thay luật sinh dạng Aiđ Aj luật sinh Ajđ d 1g | d 2g | |d kg Trong Aj đd1g | d2g | |dky luật sinh End Loại bỏ đệ qui trái trực tiếp số Ai loi End; Với đệ qui trái gián tiếp nói chung đệ qui trái, ta sử dụng giải thuật sau: VÝ dơ : Víi S Aa | b; AAc | Sd Sắp xếp ký hiệu cha kết thúc theo thứ tự S,A Với i=1, khơng có đệ qui trái trực tiếp nên khơng có điều xảy với i=2 , thay luật sinh AđSd AđAc | Aad | bd Loại bỏ đệ qui trái trực tiếp cho A, ta được: SđAa |b; AđbdA'; A'đ cA' | adA' | e * Phép thừa số hoá trái Thừa số hoá trái (left factoring) phép biến đổi văn phạm nhằm sinh văn phạm thích hợp cho việc phân tích cú pháp khơng quay lui Ý tưởng không rõ sản xuất trong hai sản xuất có vế trái A dùng để khai triển A ta viết lại sản xuất nhằm “hoãn lại định”, có đủ thơng tin để đưa định lựa chọn sản xuất - Nếu có hai sản xuất A -> 1 | 2 ta khơng biết phải khai triển A theo 1 hay 2 Khi đó, thay hai sản xuất bằng: A -> A’; A’ -> 1 | 2 Ví dụ: S -> iEtS | iEtSeS | a; E -> b Khi thừa số hoá trái, văn phạm trở thành: S -> iEtSS’ | a; S’ -> eS | ; E -> b cần khai triển S với ký hiệu xâu vào i, lựa chọn iEtSS’ mà khơng phải băn khoăn iEtS iEtSeS văn phạm c Giải thuật tạo thừa số hoá trái (yếu tố trái) cho văn phạm: Input: Output: Vn phm G Văn phạm tương đương với nhân tố trái Phơng pháp: Với ký hiệu chưa kết thúc A, có ký hiệu dẫn đầu vế phải giống nhau, ta tìm chuỗi a chuỗi có độ dài lớn chung cho tất vế phải (a nhân tố trái) Giả sử A  ab1| ab2| | abn | g Trong g khơng có chuỗi dẫn đầu chung với vế phải khác Biến đổi luật sinh thành A  a A' | g A'  b 1| b | | b n 2.1.3.4 Nhập nhằng Một văn phạm G gọi văn phạm nhập nhằng có xâu α kết hai suy dẫn khác G Ngôn ngữ văn phạm sinh gọi ngơn ngữ nhập nhằng Ví dụ: Xét văn phạm G cho sản xuất sau: S -> S + S | S * S | ( S ) | a Với xâu vào w = “a+a*a” ta có: Văn phạm nhập nhằng có hai câu vào w sau: S S a S S * S S + S a a a + S S * a Chúng ta có ví dụ đối suy dẫn trái (đối với đầu tiên) là: S => S * S => S + S => S + S * S => a + S * S => a + a * S => a + a * a suy dẫn phải (đối với ) là: S => S * S => S * a => S + S * a => S + a * a => a + a * a 2.2 phương pháp phân tích S a - Mọi ngơn ngữ lập trình có luật mơ tả cấu trúc cú pháp Một chương trình viết phải tuân theo luật mô tả Phân tích cú pháp để tìm cấu trúc dựa văn phạm chương trình nguồn - Thơng thường có hai chiến lược phân tích: + Phân tích xuống (topdown): Cho văn phạm PNC G = (, , P, S) câu cần phân tích w Xuất phát từ S áp dụng suy dẫn trái, tiến từ trái qua phải thử tạo câu w + Phân tích lên (bottom-up): Cho văn phạm PNC G = (, , P, S) câu cần phân tích w Xuất phát từ câu w áp dụng thu gọn suy dẫn phải, tiến hành từ trái qua phải để tới kí hiệu đầu S Theo cách phân tích Topdown LL(k) phân tích xuống, phân tích Bottom-up phân tích LR(k) phân tích lên * Điều kiện để thuật tốn dừng: + Phân tích xuống dừng G kơng có đệ quy trái + Phân tích lên dừng G khơng chứa suy dẫn A + A sản xuất A * Có phương pháp phân tích 1) Phương pháp phân tích topdown 2) Phương pháp phân tích bottom up 3) Phương pháp phân tích bảng CYK 4) Phương pháp phân tích LL 5) Phương pháp phân tích LR Phương pháp 2: phương pháp bản, hiệu Phương pháp 5,6 phương pháp phân tích hiệu 2.3.1 phân tích topdown Phương pháp phân tích Top-down xây dựng phân tích cho xâu vào cách xuất phát từ ký hiệu bắt đầu làm gốc sử dụng luật sản xuất để từ gốc đến - Đánh dấu thứ tự lựa chọn sản xuất có vế trái Ví dụ sản xuất có dạng S -> aSbS | aS | c aSbS lựa chọn thứ nhất, aS lựa chọn thứ hai c lựa chọn thứ ba việc khai triển S - Tại bước suy diễn, ta cần triển khai ký hiệu không kết thúc A văn phạm có sản xuất có vế trái A A->1 | 2 | | k Khi ta có k thứ tự lựa chọn, đánh dấu thứ tự lựa chọn sản xuất sau khai triển A theo lựa chọn, q trình phân tích khơng thành cơng quay lui vị trí khai triển A theo lựa chọn Phân tích Top-down phương pháp phân tích có quay lui tạo suy dẫn trái Ví dụ: Cho văn phạm S -> aSbS | aS | c Hãy phân tích xâu vào “aacbc” thuật tốn Top-down, vẽ phân tích q trình phân tích quay lui S S a S a S b S a a S b S a* S S b b S b a S a* S b S b S a* S (3) S S S c c (2) S a* (1) S b S S S S a a S b S a b S (4) S S a a S b S b a S S S a* c b S a (6) S b S c* (5) S a S b S S a S a (7) a S a* S S b S a* (8) S b S a S S a a S a* c b c S a S b S S c S (9) c 10 2.3.1.1 Mơ tả thuật tốn phân tích Top-down - Input: Văn phạm PNC G = (, , P, S) không đệ quy trái, xâu w = a1, a2, … an - Output: Cây phân tích từ xuống xâu w (w  L(G)), báo lỗi (w  L(G)) - Method: Dùng trỏ đến xâu vào w Ký hiệu xâu vào trỏ S đến gọi ký hiệu vào 1) Khởi tạo với gốc S, trỏ trỏ đến kí hiệu xâu w a1 2) Nếu nút xét   (là ký hiệu khơng kết thúc) A chọn sản xuất có vế trái A P, giả sử sản xuất A  X1 Xk + Nếu k > 0: lấy nút X1 làm nút xét + Nếu k=0 (sản xuất rỗng) lấy nút bên phải A làm nút xét 3) Nếu nút xét   (là ký hiệu kết thúc) a đối sánh a với ký hiệu vào + Nếu trùng nhau: lấy nút bên phải a làm nút xét, trỏ dịch sang bên phải ký hiệu xâu w + Nếu không: quay lại nút trước lặp lại b2 với thử lựa chọn Thủ tục lặp lại sau hữu hạn bước có khả xảy ra: - Nếu gặp trường hợp đối sánh hết xâu vào khơng cịn nút chưa xét ta phân tích - Nếu quay lui hết tất trường hợp mà không sinh phân tích kết luận xâu vào khơng phân tích văn phạm cho * Điều kiện để văn phạm phi ngữ cảnh phân tích thuật tốn Top-down văn phạm khơng có đệ qui trái (Vì ta phải thực loại bỏ đệ quy trái trước phân tích văn phạm theo phương pháp topdown) * Độ phức tạp thuật toán hàm số mũ n với n độ dài xâu vào 2.3.2 phân ttích bottom - up Phương pháp phân tích Bottom-up tư tưởng ngược lại với phương pháp Topdown - Xây dựng cú pháp cho xâu nhập lên tới gốc Đây trình rút gọn xâu thành kí hiệu mở đầu văn phạm Tại bước rút gọn, xâu xâu phải sản xuất xâu thay vế trái sản xuất (cịn gọi phương pháp gạt thu gọn - shift reduce parsing) Cã vấn đề: xác định handle chọn luật sinh * Cấu tạo: - STACK để lu ký hiệu văn phạm - BUFFER INPUT để giữ chuỗi cần phân tích w - Dùng $ để đánh dấu đáy stack cuối chuỗi nhập * Hoạt động: - Khởi đầu stack rỗng w nằm input buffer Bé ph©n tÝch gạt ký hiệu đầu vào từ trái sang phải vào ngăn xếp đến đạt thu gọn thu gọn (thay vế phải xuất đỉnh ngăn xếp vế trái sản xuất đó).Nếu có nhiều cách thu gọn trạng thái lưu lại cho trình quay lui Quá trình tiếp tục, dừng lại mà chưa đạt đến trạng thái kết thúc quay lại bước quay lui gần - Nếu trình đạt đến trạng thái ngăn xếp $S xâu vào $ trình kết thúc phân tích thành cơng - Nếu xét hết tất trường hợp, tức không quay lui mà chưa đạt đến trạng thái kết thúc dừng lại thơng báo xâu vào khơng phân tích văn phạm cho Ví dụ: S -> aABe; A -> Abc | b; B -> d; q trình phân tích Bottom-up sau: Ngăn xếp $ $a $ab $aA $aAb $aAA $aAAc $aAAcd $aAAcB $aAAcBe $aAAcde $aAbc $aA $aAd $aAB $aABe $S Đầu vào abbcde$ bbcde$ bcde$ bcde$ cde$ cde$ de$ e$ e$ $ $ de$ de$ e$ e$ $ $ Phân tích câu vào “abbcde” Hành động gạt gạt thu gọn A -> b gạt thu gọn A -> b (2) gạt gạt thu gọn B -> d (1) gạt dừng, quay lui (gạt) dừng, quay lui (gạt) thu gọn A -> Abc gạt thu gọn B -> d gạt thu gọn S -> aABe chấp nhận Vẽ cho trình phân tích quay lui trên, có kết sau: A A b b A* b b B* a a A c Quá trình d c e Quá trình d e ... pháp phân tích topdown 2) Phương pháp phân tích bottom up 3) Phương pháp phân tích bảng CYK 4) Phương pháp phân tích LL 5) Phương pháp phân tích LR Phương pháp 2: phương pháp bản, hiệu Phương pháp. .. 2: phương pháp bản, hiệu Phương pháp 5,6 phương pháp phân tích hiệu 2.3.1 phân tích topdown Phương pháp phân tích Top-down xây dựng phân tích cho xâu vào cách xuất phát từ ký hiệu bắt đầu làm gốc... chỗ phương pháp phân tích khơng quay lui - Bộ phân tích tất định: Các thuật tốn phân tích có đặc điểm chung xâu vào quét từ trái sang phải q trình phân tích hồn tồn xác định, ta gọi phân tích