Thiết kế trình biên dịch - Trình phân tích cú pháp từ trên xuống

Chúng ta đã học trong chương trước rằng kỹ thuật phân tích cú pháp từ trên xuống phân tích dữ liệu đầu vào và bắt đầu xây dựng một cây phân tích cú pháp từ nút gốc dần dần di chuyển xuống các nút lá. Các loại phân tích cú pháp từ trên xuống được mô tả bên dưới:

Phân tích cú pháp đi xuống đệ quy

Recursive descent là một kỹ thuật phân tích cú pháp từ trên xuống để xây dựng cây phân tích cú pháp từ trên xuống và đầu vào được đọc từ trái sang phải. Nó sử dụng các thủ tục cho mọi thực thể đầu cuối và không đầu cuối. Kỹ thuật phân tích cú pháp này phân tích cú pháp đệ quy đầu vào để tạo một cây phân tích cú pháp, có thể có hoặc không yêu cầu theo dõi ngược. Nhưng ngữ pháp liên quan đến nó (nếu không được tính đến) không thể tránh được việc theo dõi ngược. Một dạng phân tích cú pháp gốc đệ quy không yêu cầu bất kỳ theo dõi ngược nào được gọi làpredictive parsing.

Kỹ thuật phân tích cú pháp này được coi là đệ quy vì nó sử dụng ngữ pháp không có ngữ cảnh mà bản chất là đệ quy.

Theo dõi lại

Bộ phân tích cú pháp từ trên xuống bắt đầu từ nút gốc (ký hiệu bắt đầu) và khớp chuỗi đầu vào theo quy tắc sản xuất để thay thế chúng (nếu khớp). Để hiểu điều này, hãy lấy ví dụ sau về CFG:

S → rXd | rZd
X → oa | ea
Z → ai

Đối với một chuỗi đầu vào: read, một trình phân tích cú pháp từ trên xuống, sẽ hoạt động như sau:

Nó sẽ bắt đầu bằng S từ các quy tắc sản xuất và sẽ khớp sản lượng của nó với chữ cái ngoài cùng bên trái của đầu vào, tức là 'r'. Chính sản xuất S (S → rXd) phù hợp với nó. Vì vậy, trình phân tích cú pháp từ trên xuống chuyển sang chữ cái đầu vào tiếp theo (tức là 'e'). Trình phân tích cú pháp cố gắng mở rộng 'X' không phải đầu cuối và kiểm tra sản xuất của nó từ bên trái (X → oa). Nó không khớp với ký hiệu đầu vào tiếp theo. Vì vậy, trình phân tích cú pháp từ trên xuống sẽ lùi lại để thu được quy tắc sản xuất tiếp theo của X, (X → ea).

Bây giờ trình phân tích cú pháp khớp với tất cả các chữ cái đầu vào theo cách có thứ tự. Chuỗi được chấp nhận.

Trình phân tích cú pháp dự đoán

Bộ phân tích cú pháp dự đoán là bộ phân tích cú pháp gốc đệ quy, có khả năng dự đoán sản xuất nào sẽ được sử dụng để thay thế chuỗi đầu vào. Trình phân tích cú pháp dự đoán không bị backtracking.

Để hoàn thành nhiệm vụ của mình, trình phân tích cú pháp tiên đoán sử dụng một con trỏ nhìn trước, trỏ tới các ký hiệu đầu vào tiếp theo. Để làm cho trình phân tích cú pháp trở lại theo dõi miễn phí, trình phân tích cú pháp tiên đoán đặt một số ràng buộc đối với ngữ pháp và chỉ chấp nhận một lớp ngữ pháp được gọi là ngữ pháp LL (k).

Phân tích cú pháp dự đoán sử dụng ngăn xếp và bảng phân tích cú pháp để phân tích cú pháp đầu vào và tạo cây phân tích cú pháp. Cả ngăn xếp và đầu vào đều chứa ký hiệu kết thúc$để biểu thị rằng ngăn xếp trống và đầu vào đã được tiêu thụ. Trình phân tích cú pháp đề cập đến bảng phân tích cú pháp để đưa ra bất kỳ quyết định nào về kết hợp phần tử đầu vào và ngăn xếp.

Trong phân tích cú pháp gốc đệ quy, trình phân tích cú pháp có thể có nhiều hơn một sản xuất để lựa chọn cho một phiên bản đầu vào, trong khi trong phân tích cú pháp tiên đoán, mỗi bước có nhiều nhất một sản xuất để chọn. Có thể có những trường hợp không có sản phẩm khớp với chuỗi đầu vào, làm cho quy trình phân tích cú pháp không thành công.

LL Parser

Trình phân tích cú pháp LL chấp nhận ngữ pháp LL. Ngữ pháp LL là một tập hợp con của ngữ pháp không có ngữ cảnh nhưng với một số hạn chế để có được phiên bản đơn giản hóa, nhằm dễ dàng triển khai. Ngữ pháp LL có thể được thực hiện bằng cả hai thuật toán cụ thể là, hướng xuống đệ quy hoặc hướng bảng.

Bộ phân tích cú pháp LL được ký hiệu là LL (k). Chữ L đầu tiên trong LL (k) đang phân tích dữ liệu đầu vào từ trái sang phải, chữ L thứ hai trong LL (k) là viết tắt của từ cực trái và bản thân k đại diện cho số lần nhìn về phía trước. Nói chung k = 1, vì vậy LL (k) cũng có thể được viết là LL (1).

Thuật toán phân tích cú pháp LL

Chúng ta có thể dựa vào LL (1) xác định để giải thích phân tích cú pháp, vì kích thước của bảng tăng theo cấp số nhân với giá trị của k. Thứ hai, nếu một văn phạm nhất định không phải là LL (1), thì thông thường, nó không phải là LL (k), với bất kỳ k đã cho.

Dưới đây là một thuật toán cho LL (1) Phân tích cú pháp:

Input: 
   string ω 
   parsing table M for grammar G

Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol)
   ω$ in the input buffer

SET ip to point the first symbol of ω$.

repeat
   let X be the top stack symbol and a the symbol pointed by ip.

   if X∈ V_t or $
      if X = a
         POP X and advance ip.
      else
         error()
      endif
      
   else	/* X is non-terminal */
      if M[X,a] = X → Y1, Y2,... Yk    
         POP X
         PUSH Yk, Yk-1,... Y1 /* Y1 on top */
         Output the production X → Y1, Y2,... Yk 
      else
         error()
      endif
   endif
until X = $	/* empty stack */

Văn phạm G là LL (1) nếu A → α | β là hai sản phẩm khác biệt của G:

đối với không có đầu cuối, cả α và β đều suy ra các chuỗi bắt đầu bằng a.
nhiều nhất một trong số α và β có thể suy ra chuỗi rỗng.
nếu β → t, thì α không suy ra bất kỳ chuỗi nào bắt đầu bằng đầu cuối trong FOLLOW (A).