Phân tích cú pháp (PARSING)

Phân tích cú pháp từ trên xuống (Top - Down Parsing)

Xét văn phạm sinh ra một tập con các kiểu dữ liệu của Pascal

Phân tích trên xuống bắt đầu bởi nút gốc, nhãn là ký hiệu chưa kết thúc bắt đầu và lặp lại việc thực hiện hai bước sau đây:

1. Tại nút n, nhãn là ký hiệu chưa kết thúc A, chọn một trong những luật sinh của A và xây dựng các con của n cho các ký hiệu trong vế phải của luật sinh.
2. Tìm nút kế tiếp mà tại đó một cây con sẽ được xây dựng. Ðối với một số văn phạm, các bước trên được cài đặt bằng một phép quét (scan) dòng nhập từ trái qua phải.

Ví dụ 2.10: Với các luật sinh của văn phạm trên, ta xây dựng cây cú pháp cho dòng nhập: array [num .. num] of integer

Mở đầu ta xây dựng nút gốc với nhãn type. Ðể xây dựng các nút con của typeta chọn luật sinh type → array [simple] of type. Các ký hiệu nằm bên phải của luật sinh này là array, [, simple, ], of, type do đó nút gốc type có 6 con có nhãn tương ứng (áp dụng bước 1)

Trong các nút con của type, từ trái qua thì nút con có nhãn simple (một ký hiệu chưa kết thúc) do đó có thể xây dựng một cây con tại nút simple (bước 2)

Trong các luật sinh có vế trái là simple, ta chọn luật sinh simple → num .. num để xây dựng. Nói chung, việc chọn một luật sinh có thể được xem như một quá trình thử và sai (trial - and - error). Nghĩa là một luật sinh được chọn để thử và sau đó quay lại để thử một luật sinh khác nếu luật sinh ban đầu không phù hợp. Một luật sinh là không phù hợp nếu sau khi sử dụng luật sinh này chúng ta không thể xây dựng một cây hợp với dòng nhập. Ðể tránh việc lần ngược, người ta đưa ra một phương pháp gọi là phương pháp phân tích cú pháp dự đoán.

2. Phân tích cú pháp dự đoán (Predictive Parsing)

Phương pháp phân tích cú pháp đệ qui xuống (recursive-descent parsing) là một phương pháp phân tích trên xuống, trong đó chúng ta thực hiện một loạt thủ tục đệ qui để xử lý chuỗi nhập. Mỗi một thủ tục kết hợp với một ký hiệu chưa kết thúc của văn phạm. Ở đây chúng ta xét một trường hợp đặc biệt của phương pháp đệ qui xuống là phương pháp phân tích dự đoán trong đó ký hiệu dò tìm sẽ xác định thủ tục được chọn đối với ký hiệu chưa kết thúc. Chuỗi các thủ tục được gọi trong quá trình xử lý chuỗi nhập sẽ tạo ra cây phân tích cú pháp.

Ví dụ 2.11: Xét văn phạm như trên, ta viết các thủ tục type và simple tương ứng với các ký hiệu chưa kết thúc type và simple trong văn phạm. Ta còn đưa thêm thủ tục match để đơn giản hóa đoạn mã cho hai thủ tục trên, nó sẽ dịch tới ký hiệu kế tiếp nếu tham số t của nó so khớp với ký hiệu dò tìm tại đầu đọc (lookahead).

Phân tích cú pháp bắt đầu bằng lời gọi tới thủ tục cho ký hiệu bắt đầu type. Với dòng nhập array [num .. num] of integer thì đầu đọc lookahead bắt đầu sẽ đọc token array. Thủ tục type sau đó sẽ thực hiện chuỗi lệnh: match(array); match(‘[‘); simple; match(‘]’); match(of); type. Sau khi đã đọc được array và [ thì ký hiệu hiện tại là num. Tại điểm này thì thủ tục simple và các lệnh match(num); match(dotdot); match(num) được thực hiện.

Xét luật sinh type → simple. Luật sinh này có thể được dùng khi ký hiệu dò tìm sinh ra bởi simple, chẳng hạn ký hiệu dò tìm là integer mặc dù trong văn phạm không có luật sinh type → integer, nhưng có luật sinh simple → integer, do đó luật sinh type → simple được dùng bằng cách trong type gọi simple.

3. Thiết kế bộ phân tích cú pháp dự đoán

Bộ phân tích dự đoán là một chương trình bao gồm các thủ tục tương ứng với các ký hiệu chưa kết thúc. Mỗi thủ tục sẽ thực hiện hai công việc sau:

1. Luật sinh mà vế phải α của nó sẽ được dùng nếu ký hiệu dò tìm thuộc FIRST(α). Nếu có một sự đụng độ giữa hai vế phải đối với bất kỳ một ký hiệu dò tìm nào thì không thể dùng phương pháp này. Một luật sinh với ε nằm bên vế phải được dùng nếu ký hiệu dò tìm không thuộc tập hợp FIRST của bất kỳ vế phải nào khác.
2. Một ký hiệu chưa kết thúc tương ứng lời gọi thủ tục, một token phải phù hợp với ký hiệu dò tìm. Nếu token không phù hợp với ký hiệu dò tìm thì có lỗi.

4. Loại bỏ đệ qui trái

Một bộ phân tích cú pháp đệ quy xuống có thể sẽ dẫn đến một vòng lặp vô tận nếu gặp một luật sinh đệ qui trái dạng E → E + T bởi vì ký hiệu trái nhất bên vế phải cũng giống như ký hiệu chưa kết thúc bên vế trái của luật sinh.

Ðể giải quyết được vấn đề này chúng ta phải loại bỏ đệ qui trái bằng cách thêm vào một ký hiệu chưa kết thúc mới. Chẳng hạn với luật sinh dạng A → Aα | β.Ta thêm vào một ký hiệu chưa kết thúc R để viết lại thành tập luật sinh như sau :

A → β R

R → α R | ε

Ví dụ 2.14: Xét luật sinh đệ quy trái : E → E + T | T

Sử dụng quy tắc khử đệ quy trái nói trên với : A ≅ E, α ≅ + T, β≅ T .

Luật sinh trên có thể biến đổi tương đương thành tập luật sinh :

E → T R

R → + T R | ε