Thiết kế trình biên dịch: Phân tích cụ pháp

Trong hướng dẫn trước, bạn đã tìm hiểu chi tiết về giai đoạn phân tích từ vựng (Lexical Analysis) trong thiết kế trình biên dịch. Nếu bỏ lỡ hướng dẫn này thì bạn có thể xem tại đây:

Thiết kế trình biên dịch: Phân tích từ vựng
Trong hướng dẫn này, bạn sẽ tìm hiểu chi tiết giai đoạn phân tích từ vựng trong thiết kế trình biên dịch.

Phân tích cú pháp (Syntax Analysis hoặc Parsing) là giai đoạn thứ hai của trình biên dịch. Trong hướng dẫn này, chúng ta sẽ tìm hiểu các khái niệm cơ bản được sử dụng trong việc xây dựng một trình phân tích cú pháp.

Chúng ta đã thấy rằng một trình phân tích từ vựng có thể xác định các mã thông báo với sự trợ giúp của các biểu thức chính quy và các quy tắc mẫu.

Nhưng một bộ phân tích từ vựng không thể kiểm tra cú pháp của một câu đã cho do những hạn chế của cụm từ thông dụng. Biểu thức chính quy không thể kiểm tra các mã thông báo cân bằng, chẳng hạn như dấu ngoặc đơn.

Do đó, giai đoạn này sử dụng ngữ pháp không theo ngữ cảnh (CFG), được nhận dạng bởi dữ liệu tự động đẩy xuống.

Mặt khác, CFG là một tập hợp siêu ngữ pháp thông thường, như được mô tả bên dưới:

Thiết kế trình biên dịch: Phân tích cụ pháp

Nó ngụ ý rằng mọi ngữ pháp thông thường cũng không theo ngữ cảnh, nhưng tồn tại một số vấn đề, nằm ngoài phạm vi của ngữ pháp thông thường. CFG là một công cụ hữu ích trong việc mô tả cú pháp của các ngôn ngữ lập trình.

Ngữ pháp không theo ngữ cảnh

Trong phần này, trước tiên chúng ta sẽ xem định nghĩa của ngữ pháp không theo ngữ cảnh và giới thiệu các thuật ngữ được sử dụng trong công nghệ phân tích cú pháp.

Ngữ pháp không theo ngữ cảnh có bốn thành phần:

  • Non-terminal (V): Non-terminal là các biến cú pháp để biểu thị tập hợp các chuỗi. Non-terminal xác định tập hợp các chuỗi giúp xác định ngôn ngữ do ngữ pháp tạo ra.
  • Terminal (Σ): Terminal là các ký hiệu cơ bản mà từ đó các chuỗi được hình thành.
  • Production (P): Production của một ngữ pháp xác định cách thức mà các terminal và non-terminal có thể được kết hợp để tạo thành chuỗi. Mỗi production bao gồm một non-terminal được gọi là phía bên trái của production, một mũi tên và một chuỗi các mã thông báo và / hoặc terminal, được gọi là phía bên phải của production.
  • Start (S): Một trong các non-terminals được chỉ định là ký hiệu bắt đầu (S); từ nơi bắt đầu sản phẩm.

Các chuỗi có nguồn gốc từ ký hiệu bắt đầu bằng cách thay thế nhiều lần một non-terminal (ban đầu là ký hiệu bắt đầu) ở phía bên phải của một production cho non-terminal đó.

Ví dụ:

Chúng ta gặp vấn đề về ngôn ngữ palindrome, ngôn ngữ này không thể được mô tả bằng biểu thức chính quy. Tức là, L = {w | w = w R } không phải là một ngôn ngữ thông thường. Nhưng nó có thể được mô tả bằng CFG, như minh họa bên dưới:

G = ( V, Σ, P, S )

Ở đây:

V = { Q, Z, N } 
Σ = { 0, 1 } 
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 } 
S = { Q }

Ngữ pháp này mô tả ngôn ngữ palindrome, chẳng hạn như: 1001, 11100111, 00100, 1010101, 11111, v.v.

Trình phân tích cú pháp

Trình phân tích cú pháp (syntax analyzer hoặc parser) lấy đầu vào từ trình phân tích từ vựng dưới dạng các luồng mã thông báo.

Trình phân tích cú pháp phân tích mã nguồn (dòng mã thông báo) dựa trên các quy tắc xử lý để phát hiện bất kỳ lỗi nào trong mã. Đầu ra của giai đoạn này là một cây phân tích cú pháp.

Các loại phân tích cú pháp

Trình phân tích cú pháp tuân theo các quy tắc xử lý được xác định bằng ngữ pháp không theo ngữ cảnh.

Cách thực hiện các quy tắc xử lý (dẫn xuất) chia phân tích cú pháp thành hai loại: phân tích cú pháp từ trên xuống và phân tích cú pháp từ dưới lên.

Các loại phân tích cú pháp

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

Khi trình phân tích cú pháp bắt đầu xây dựng cây phân tích cú pháp từ ký hiệu bắt đầu và sau đó cố gắng chuyển đổi ký hiệu bắt đầu thành đầu vào, nó được gọi là phân tích cú pháp từ trên xuống.

  • Đệ quy đi xuống: Đây là một dạng phân tích cú pháp từ trên xuống phổ biến. Nó được gọi là đệ quy đi xuống vì nó sử dụng các thủ tục đệ quy để xử lý đầu vào. Nó không có theo dõi ngược (back-tracking).
  • Theo dõi ngược: Có nghĩa là, nếu một dẫn xuất của một sản phẩm không thành công, trình phân tích cú pháp sẽ khởi động lại quy trình bằng cách sử dụng các quy tắc khác nhau của cùng một sản phẩm. Kỹ thuật này có thể xử lý chuỗi đầu vào nhiều lần để xác định sản phẩm phù hợp.

Phân tích cú pháp từ dưới lên (Bottom-Up)

Như tên phương pháp cho thấy, phân tích cú pháp từ dưới lên bắt đầu với các ký hiệu đầu vào và cố gắng xây dựng cây phân tích cú pháp lên đến ký hiệu bắt đầu.

Ví dụ:

Chuỗi đầu vào là: a + b * c

Quy tắc xử lý:

S → E
E → E + T
E → E * T
E → T
T → id

Chúng ta hãy bắt đầu phân tích cú pháp từ dưới lên:

a + b * c

Đọc đầu vào và kiểm tra xem có sản phẩm nào khớp với đầu vào không:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S

Trình phân tích cú pháp từ trên xuống

Chúng ta đã học trong phần 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 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á.

Loại phân tích cú pháp từ trên xuống được mô tả bên dưới:

Trình phân tích cú pháp từ trên xuống

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

Đệ quy đi xuống 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 (terminal) và thông thường (non-terminal).

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 được liên kết với nó (nếu không được tính vào yếu tố) không thể tránh được việc theo dõi ngược.

Một dạng phân tích cú pháp đệ quy đi xuống không yêu cầu bất kỳ theo dõi ngược nào được gọi là phân tích cú pháp dự đoán.

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 theo ngữ cảnh mà bản chất là đệ quy.

Theo dõi ngược (Back-tracking)

Trình 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 với các quy tắc xử lý để thay thế chúng (nếu khớp). Để hiểu điều này, hãy lấy ví dụ sau về CFG (Context Free Grammar):

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

Đối với một chuỗi đầu vào: 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 xử lý và sẽ khớp sản phẩm 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'. Nhiều sản phẩm của 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 tiến tới ký tự đầ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 non-terminal 'X' và kiểm tra sản phẩm 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 xử lý 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.

Back TrackingBack TrackingBack TrackingBack Tracking

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

Trình phân tích cú pháp dự đoán là trình phân tích cú pháp gốc đệ quy, có khả năng dự đoán sản phẩm 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 có theo dõi ngược (back-tracking).

Để hoàn thành nhiệm vụ của mình, trình phân tích cú pháp dự đoán sử dụng một con trỏ, trỏ đến các ký hiệu đầu vào tiếp theo. Để làm cho trình phân tích cú pháp không có theo dõi ngược, trình phân tích cú pháp dự đ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).

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

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 sử dụng.

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.

Lược đồ trình phân tích cú pháp từ trên xuống

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 phẩm để lựa chọn cho một phiên bản đầu vào, trong khi trong trình phân tích cú pháp dự đoán, mỗi bước có nhiều nhất một sản phẩm để lựa 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.

Trình phân tích cú pháp LL (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 là đệ quy đi xuống và hướng bảng.

Trình phân tích cú pháp LL được ký hiệu là LL(k). Chữ L đầu tiên trong LL(k) sẽ 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 dẫn xuất ngoài cùng bên 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).

Trình phân tích cú pháp LL (LL Parser)

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

Chúng ta có thể bám vào cách xác định LL(1) để giải thích phân tích cú pháp, vì kích thước của bảng tăng lên theo cấp số nhân với giá trị của k. Thứ hai, nếu một ngữ pháp 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 phân tích cú pháp LL(1):

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∈ Vt 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 */

Ngữ pháp 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).

Trình phân tích cú pháp từ dưới lên

Phân tích cú pháp từ dưới lên bắt đầu từ các nút lá của cây và hoạt động theo hướng đi lên cho đến khi nó đến nút gốc.

Ở đây, chúng ta bắt đầu từ một câu và sau đó áp dụng các quy tắc xử lý theo cách ngược lại để đạt được biểu tượng bắt đầu.

Hình ảnh dưới đây mô tả trình phân tích cú pháp từ dưới lên.

Trình phân tích cú pháp từ dưới lên

Phân tích cú pháp Shift-Reduce

Phân tích cú pháp Shift-Reduce sử dụng hai bước để phân tích cú pháp từ dưới lên. Các bước này được gọi là bước dịch chuyển và bước giảm.

  • Bước dịch chuyển: Bước dịch chuyển đề cập đến sự tiến của con trỏ đầu vào tới ký hiệu đầu vào tiếp theo, được gọi là ký hiệu đã dịch chuyển. Ký hiệu này được đẩy lên ngăn xếp. Ký hiệu được dịch chuyển được coi như một nút duy nhất của cây phân tích cú pháp.
  • Bước giảm: Khi trình phân tích cú pháp tìm thấy một quy tắc ngữ pháp hoàn chỉnh (RHS) và thay thế nó thành (LHS), nó được gọi là bước giảm. Điều này xảy ra khi trên cùng của ngăn xếp có một chốt. Để giảm bớt, một chức năng POP được thực hiện trên ngăn xếp và thay thế nó bằng ký hiệu không phải đầu cuối LHS.

Trình phân tích cú pháp LR

Trình phân tích cú pháp LR là trình phân tích cú pháp không đệ quy, Shift-Reduce, từ dưới lên.

Nó sử dụng nhiều loại ngữ pháp không có ngữ cảnh, điều này làm cho nó trở thành kỹ thuật phân tích cú pháp hiệu quả nhất.

Trình phân tích cú pháp LR còn được gọi là trình phân tích cú pháp LR(k), trong đó L là viết tắt của việc quét từ trái sang phải của luồng đầu vào; R là viết tắt của việc xây dựng phát sinh phần lớn bên phải, và k biểu thị số lượng ký hiệu nhìn trước để đưa ra quyết định.

Có ba thuật toán được sử dụng rộng rãi có sẵn để xây dựng trình phân tích cú pháp LR:

SLR(1) - Trình phân tích cú pháp LR đơn giản:

  • Hoạt động trên lớp ngữ pháp nhỏ nhất.
  • Rất ít trạng thái, do đó bảng rất nhỏ.
  • Triển khai đơn giản và nhanh chóng.

LR(1) - Trình phân tích cú pháp LR:

  • Làm việc trên bộ ngữ pháp LR(1) hoàn chỉnh.
  • Tạo bảng lớn và số lượng lớn các trạng thái.
  • Triển khai chậm.

LALR(1) - Trình phân tích cú pháp LR nhìn trước:

  • Hoạt động trên kích thước trung bình của ngữ pháp.
  • Số lượng trạng thái giống như trong SLR(1)

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

Ở đây chúng tôi mô tả một thuật toán khung của trình phân tích cú pháp LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL so với LR

LL LR
Có một dẫn xuất ngoài cùng bên trái. Có một dẫn xuất ngoài cùng bên phải.
Bắt đầu với định danh gốc trên ngăn xếp. Kết thúc với định danh gốc trên ngăn xếp.
Kết thúc khi ngăn xếp trống. Bắt đầu khi ngăn xếp trống.
Sử dụng ngăn xếp để chỉ định những gì vẫn được mong đợi. Sử dụng ngăn xếp để chỉ định những gì đã thấy.
Xây dựng cây 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ừ dưới lên.
Liên tục đẩy ra một định danh ra khỏi ngăn xếp và đưa vào phía bên phải tương ứng. Cố gắng nhận ra một phía bên phải trên ngăn xếp, bật nó và đẩy danh nghĩa tương ứng.
Mở rộng các đầu cuối. Giảm các đầu cuối.
Đọc các đầu cuối khi nó đẩy một đầu ra khỏi ngăn xếp. Đọc các đầu cuối trong khi nó đẩy chúng vào ngăn xếp.
Thiết lập trước trình duyệt của cây phân tích cú pháp. Duyệt theo thứ tự của cây phân tích cú pháp.

Phục hồi lỗi

Một trình phân tích cú pháp sẽ có thể phát hiện và báo cáo bất kỳ lỗi nào trong chương trình. Điều mong đợi khi gặp lỗi là trình phân tích cú pháp sẽ có thể xử lý nó và tiếp tục phân tích cú pháp phần còn lại của đầu vào.

Nó được mong đợi chủ yếu từ trình phân tích cú pháp để kiểm tra lỗi nhưng lỗi có thể gặp phải ở các giai đoạn khác nhau của quá trình biên dịch.

Một chương trình có thể có các loại lỗi sau ở các giai đoạn khác nhau:

  • Từ vựng: tên của một số định danh được gõ sai.
  • Cú pháp: thiếu dấu chấm phẩy hoặc dấu ngoặc đơn không cân đối.
  • Ngữ nghĩa: gán giá trị không tương thích.
  • Logic: không thể truy cập mã, vòng lặp vô hạn.

Có bốn chiến lược phục hồi lỗi phổ biến có thể được thực hiện trong trình phân tích cú pháp để xử lý các lỗi trong mã.

Panic mode

Khi trình phân tích cú pháp gặp lỗi ở bất kỳ đâu trong câu lệnh, nó sẽ bỏ qua phần còn lại của câu lệnh bằng cách không xử lý đầu vào sai.

Đây là cách dễ nhất để phục hồi lỗi và nó cũng ngăn trình phân tích cú pháp phát triển các vòng lặp vô hạn.

Statement mode

Khi trình phân tích cú pháp gặp lỗi, trình phân tích cú pháp sẽ cố gắng thực hiện các biện pháp sửa chữa để phần còn lại của các đầu vào của câu lệnh cho phép trình phân tích cú pháp phân tích cú pháp trước.

Ví dụ, chèn một dấu chấm phẩy bị thiếu, thay thế dấu phẩy bằng dấu chấm phẩy, v.v.

Các nhà thiết kế trình phân tích cú pháp phải cẩn thận ở đây vì một lần sửa sai có thể dẫn đến một vòng lặp vô hạn.

Error productions

Các nhà thiết kế trình biên dịch đã biết một số lỗi phổ biến có thể xảy ra trong mã.

Ngoài ra, các nhà thiết kế có thể tạo ngữ pháp tăng cường để sử dụng, như các sản phẩm tạo ra các cấu trúc sai khi gặp những lỗi này.

Global correction

Trình phân tích cú pháp xem xét toàn bộ chương trình và cố gắng tìm ra chương trình dự định làm gì và cố gắng tìm ra kết quả phù hợp nhất cho chương trình mà không có lỗi.

Khi một đầu vào (câu lệnh) X có lỗi được cung cấp, nó sẽ tạo một cây phân tích cú pháp cho một số câu lệnh không có lỗi gần nhất Y.

Điều này có thể cho phép trình phân tích cú pháp thực hiện các thay đổi tối thiểu trong mã nguồn, nhưng do độ phức tạp (thời gian và không gian) của chiến lược này vẫn chưa được thực hiện trong thực tế.

Cây cú pháp trừu tượng

Các biểu diễn cây phân tích cú pháp không dễ dàng được trình biên dịch phân tích cú pháp, vì chúng chứa nhiều chi tiết hơn thực tế cần thiết. Lấy cây phân tích cú pháp sau làm ví dụ:

cây phân tích cú pháp

Nếu quan sát kỹ, chúng ta thấy hầu hết các nút lá là con đơn lẻ đối với các nút cha của chúng. Thông tin này có thể được loại bỏ trước khi chuyển sang giai đoạn tiếp theo. Bằng cách ẩn thông tin bổ sung, chúng ta có thể có được một cây như hình dưới đây:

cây phân tích cú pháp

Cây trừu tượng có thể được biểu diễn dưới dạng:

AST là cấu trúc dữ liệu quan trọng trong trình biên dịch với ít thông tin không cần thiết nhất. Các AST nhỏ gọn hơn một cây phân tích cú pháp và có thể dễ dàng sử dụng bởi trình biên dịch.

Ở hướng dẫn tiếp theo, bạn sẽ tìm hiểu chi tiết về phân tích ngữ nghĩa và trình phân tích ngữ nghĩa trong thiết kế trình biên dịch.

Thiết kế trình biên dịch: Phân tích ngữ nghĩa
Trong hướng dẫn này, bạn sẽ tìm hiểu chi tiết về phân tích ngữ nghĩa và trình phân tích ngữ nghĩa trong thiết kế trình biên dịch.
Trình Biên Dịch
Bài Viết Liên Quan:
Thiết kế trình biên dịch: Môi trường thực thi
Trung Nguyen 07/04/2021
Thiết kế trình biên dịch: Môi trường thực thi

Trong hướng dẫn này, bạn sẽ tìm hiểu chi tiết về môi trường thực thi, nơi chương trình sau khi biên dịch sẽ được thực thi.

Thiết kế trình biên dịch: Bảng ký hiệu
Trung Nguyen 07/04/2021
Thiết kế trình biên dịch: Bảng ký hiệu

Trong hướng dẫn này, bạn sẽ tìm hiểu bảng ký hiệu là gì? Cách trình biên dịch sử dụng bảng ký hiệu trong thiết kế trình biên dịch.

Thiết kế trình biên dịch: Tối ưu hóa mã
Trung Nguyen 07/04/2021
Thiết kế trình biên dịch: Tối ưu hóa mã

Trong hướng dẫn này, bạn sẽ tìm hiểu chi tiết các phương pháp để tối ưu mã trong thiết kế trình biên dịch.

Thiết kế trình biên dịch: Tạo mã
Trung Nguyen 07/04/2021
Thiết kế trình biên dịch: Tạo mã

Trong hướng dẫn này, bạn sẽ tìm hiểu tạo mã và trình tạo mã trong thiết kế trình biên dịch.