Phân tích cú pháp Pratt trực quan

Bạn đã biết rằng a + b * c + d được tính như a + (b * c) + d. Nhưng làm thế nào để bạn mã hóa kiến thức đó đủ chính xác để một cỗ máy hoạt động trên nó?

Giải pháp phổ biến nhất được sử dụng bởi các trình biên dịch là sử dụng một cây được gọi là cây cú pháp trừu tượng. Trong một AST, mỗi người vận hành ngồi phía trên các toán hạng của nó và đánh giá hoạt động từ dưới lên: giải quyết trẻ em, sau đó áp dụng thao tác.

     +
/ \
   +   d
/ \
 a   *
/ \
   b   c

Cây này mã hóa thứ tự mong muốn (a + (b * c)) + d ở định dạng rất thuận tiện để làm việc theo lập trình.

Nhưng tất nhiên, mọi người (phần lớn) không viết chương trình dưới dạng cây. Điều này có nghĩa là chúng ta phải đối mặt với vấn đề lấy cấu trúc này từ văn bản phẳng.

Điều này được gọi là phân tích cú pháp. Đó là trọng tâm của nhiều thập kỷ nghiên cứu khoa học máy tính. Trong nhiều trường hợp, nó cũng đã trở nên quá phức tạp.

Đơn giản hóa

Khó khăn trong việc phân tích cú pháp nằm ở mức độ ưu tiên hỗn hợp. Để chính xác, các trường hợp ưu tiên thay đổi hướng. Hãy tưởng tượng người dùng của chúng ta chỉ viết các chương trình có mức độ ưu tiên tăng hoặc giảm. Điều đó có ý nghĩa gì đối với đại diện cây cối của chúng ta?

Trong trường hợp mức độ ưu tiên giảm dần, chúng tôi liên tục đánh giá toán tử ngoài cùng bên trái vì nó có mức độ ưu tiên cao hơn - phép nhân trước phép cộng, phép cộng trước khi so sánh, v.v. Người đầu tiên ngồi sâu nhất trên cây, người cuối cùng ngồi nông nhất. Cây kết quả nghiêng sang trái.

Giảm
       <
/ \
     +   d
/ \
   *   c
/ \
 a   b

Bạn có thể tưởng tượng điều gì sẽ xảy ra khi mức độ ưu tiên tăng lên. Nó hoàn toàn ngược lại: toán tử ngoài cùng bên trái bây giờ là nông nhất và xa nhất bên phải là sâu nhất, vì mỗi toán tử phụ thuộc vào kết quả ở bên phải của nó. Cái cây đang nghiêng về bên phải.

Tăng
   >
/ \
 a   +
/ \
   b   *
/ \
     c   d

Bây giờ, mã hóa hợp lý nhất có mức độ ưu tiên bằng nhau là gì?

Nó phụ thuộc vào hoạt động. Hội nghị ủng hộ việc đánh giá từ trái sang phải đối với số học, được gọi là tính liên kết trái. Một số tính năng ngôn ngữ ủng hộ điều ngược lại: ví dụ, bài tập trong C là kết hợp đúng.

Giả sử (bây giờ) rằng tất cả các toán tử đều liên kết trái. Điều này được thể hiện bằng một cây nghiêng trái, vì toán tử ngoài cùng bên trái phải được đánh giá sớm hơn và do đó nằm sâu hơn trong cây.

Chúng ta nên tinh chỉnh các định nghĩa của mình cho phù hợp. Cho một chuỗi các toán tử, hãy để x_i là ưu tiên của toán tử thứ i:

• Giảm: giảm yếu - x_i >= x_{i+1}. Điều này hiện bao gồm trường hợp được ưu tiên ngang nhau.
• Tăng: tăng nghiêm ngặt - x_i < x_{i+1}.

Điều này có nghĩa là bất kỳ hai toán tử tính toán bằng nhau nào cũng được mã hóa chính xác như hai toán tử giảm dần.

Đang mở rộng

Một sự tiếp nối tự nhiên là xem xét các biểu thức với chính xác một thay đổi về hướng. Chúng ta sẽ tập trung vào hai trường hợp thú vị hơn: sự chuyển đổi từ ưu tiên ngày càng tăng sang ưu tiên giảm dần. Điều ngược lại chỉ đơn giản là tiếp tục một cây nghiêng phải từ đầu của cây nghiêng trái hiện có.

Xem xét biểu thức I = (a > b + c * d), được đưa ra bởi cây dưới đây.

   >
/ \
 a   +
/ \
   b   *
/ \
     c   d

Cây nghiêng phải, như mong đợi để tăng mức độ ưu tiên. Bây giờ, giả sử chúng ta mở rộng I với một toán tử mới có mức độ ưu tiên bằng hoặc nhỏ hơn *. Điều này có nghĩa là tài sản ngày càng tăng không còn giữ được nữa, và do đó, việc tiếp tục một cây nghiêng phải sẽ tạo ra một mã hóa không chính xác.

Chúng ta cần một cái cây nghiêng trái ở đâu đó, nhưng ở đâu? Hình dung về từng mức độ ưu tiên có thể có đối với toán tử mới bắt đầu tiết lộ một mẫu:

 [I] * e:
   >
/ \
 a   +
/ \
   b   *
/ \
     *   e
/ \
   c   d
[I] + e:
   >
/ \
 a   +
/ \
   +   e
/ \
 b   *
/ \
   c   d
[I] == e:
     ==
/  \
   >    e
/ \
 a   +
/ \
   b   *
/ \
     c   d

Cây nghiêng trái bắt đầu ở nơi đầu tiên nó có thể: tại một nhà điều hành có mức độ ưu tiên bằng hoặc thấp hơn. Nhà khai thác ưu tiên thấp hơn này phải đánh giá muộn hơn ít nhất là so với hiện tại, nhưng có thể có một số nhà khai thác trước đó cũng phải đánh giá trước. Những người vận hành được tìm thấy dọc theo cột sống của cây nghiêng phải.

Trường hợp == là ví dụ rõ ràng nhất. Tất cả các toán tử trước đó được ưu tiên cao hơn ==, vì vậy toàn bộ cột sống của cây phải đánh giá trước, và do đó phải là con bên trái của nó.

Quan sát như sau: khi chúng ta gặp một nhà điều hành chuyển tiếp, chúng ta phải đi ngược lên cột sống, thu thập mọi nhà điều hành đánh giá trước. Chuỗi được thu thập đó - một cây con nghiêng phải - trở thành con bên trái của toán tử mới, bắt đầu một cây nghiêng trái của riêng nó.

Vì bất kỳ biểu thức nào cũng chỉ là một chuỗi các quá trình chuyển đổi này, đây là tất cả những gì chúng ta cần. Quy trình quay lại này là phân tích cú pháp Pratt.

Phân tích cú pháp

Chúng tôi hy vọng có thể làm cho mọi thứ cụ thể hơn một chút với một số mã giả, mở rộng trường hợp nghiêng phải để xử lý quá trình chuyển đổi như chúng tôi đã làm trước đó.

Nghiêng phải

Một cây nghiêng phải có thể được xây dựng bằng cách tự tái tạo và sau đó xây dựng cây từ dưới lên.

 def parse():
    left = leaf()
    if peek() is not None:
        op = advance()
        right = parse()
        return Node(op, left, right)
    return left

parse() defers đầu tiên thành leaf() để xử lý một chữ như a, tiêu thụ nó từ luồng mã thông báo trước khi kiểm tra mã thông báo tiếp theo bằng peek(). Mã thông báo tiếp theo (một toán tử cho một chương trình hợp lệ) được tiêu thụ bởi advance() để di chuyển trình phân tích cú pháp sang mã thông báo tiếp theo. parse() cuối cùng tự gọi cho phía bên phải.

Trình phân tích cú pháp tiến lên thông qua các mã thông báo khi nó quay trở lại và xây dựng cây khi nó quay trở lại. Đối với cây trước đó của chúng tôi [I]:

-- Down: advance
(1) parse(0)
    a [>] b  +  c  *  d
(2) parse(prec (>))
    a  >  b [+] c  *  d
(3) parse(prec (+))
    a  >  b  +  c [*] d
(4) parse(prec (*))
    a  >  b  +  c  *  d [None]
-- Up: build
(4)  d
(3) [*]
/ \
   c   d
(2) [+]
/ \
   b   *
/ \
     c   d
(1) [>]
/ \
   a   +
/ \
     b   *
/ \
       c   d

Việc sử dụng đệ quy là cách chúng tôi sẽ quay lại để tìm điểm tiếp tục.

Cho đến lúc đó, trình phân tích cú pháp của chúng tôi tạo ra các cây không chính xác để giảm mức độ ưu tiên. Để ngăn chặn các mã thông báo phân tích cú pháp mà chúng ta không nên, chúng ta có thể chuyển tiếp ưu tiên hiện tại đến lệnh gọi con đệ quy:

def parse(prev_prec=0):
    left = leaf()
    if peek() is not None và prec(peek() > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)
    return left

Điều này hoạt động, nhưng chúng ta có thể đơn giản hóa bằng cách cho end-of-file mã thông báo riêng của nó với mức độ ưu tiên thấp nhất - peek() sẽ khiến điều kiện tự nhiên thất bại, cho phép chúng ta bỏ kiểm tra null:

def parse(prev_prec=0):
    left = leaf()
    if prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)
    return left

Nghiêng trái

Khi phân tích cú pháp() lặp lại, nó đẩy một khung lên ngăn xếp cuộc gọi với con bên trái và mức độ ưu tiên tối thiểu. Ngăn xếp cuộc gọi, đại diện cho cột sống chưa được xây dựng, luôn được ưu tiên ngày càng tăng.

Điều này có nghĩa là khi thư giãn, chúng ta truy cập từng cấp độ theo thứ tự giảm dần. Vì vậy, cấp độ đầu tiên nơi peek() có thể liên kết cũng là mức chính xác: mọi cấp độ ở trên đều được ưu tiên thấp hơn và chúng ta đã biết rằng nó không thể đi sâu hơn vì phân tích cú pháp() sẽ không trở lại. Sự lựa chọn tham lam là lựa chọn đúng đắn duy nhất.

Nhưng nếu chỉ có khả năng đưa ra lựa chọn tham lam đó một lần - chúng ta cần phải thực hiện nó mọi lúc, bởi vì bất cứ điều gì khác là không chính xác. Vì vậy, chúng tôi thay thế if bằng while:

def parse(prev_prec=0):
    left = leaf()
    while prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        left = Node(op, left, right)
    return left

Đây là trình phân tích cú pháp Pratt hoàn chỉnh. Vòng lặp while là quy trình walkback mà chúng ta đã mô tả trước đó: khi một toán tử chuyển tiếp xuất hiện, parse() trả về ngăn xếp cuộc gọi cho đến khi nó tìm thấy mức phù hợp, sau đó vòng lặp tiêu thụ nó và tiếp tục với cây con nghiêng trái.

Đây là dấu vết [I] * e, trong đó I = a > b + c * d:

 -- Down: advance
(1) a [>] b  +  c  *  d  *  e
(2) a  >  b [+] c  *  d  *  e
(3) a  >  b  +  c [*] d  *  e
(4) a  >  b  +  c  *  d [*] e  FAIL
-- Up: build
(4)  d
(3)  iteration 1:
     [*]
/ \
    c   d
     iteration 2:
     [*]
/ \
    *   e
/ \
  c   d
(2) [+]
/ \
   b   *
/ \
     *   e
/ \
   c   d
(1) [>]
/ \
   a   +
/ \
     b   *
/ \
       *   e
/ \
     c   d
 

Cây phụ nghiêng trái (c * d) * e được xây dựng hoàn toàn trong vòng lặp while của khung 3.

Sự liên kết đúng đắn

Trong thực tế, mọi toán tử đều có hai loại ưu tiên: trái và phải. Pratt đề cập đến điều này là sức mạnh liên kết trái và phải, hoặc LBP và RBP. Tất cả các nhà khai thác của chúng tôi cho đến nay đều có LBP và RBP bằng nhau.

LBP của một toán tử xác định mức độ thu hút biểu thức ở bên trái của nó - đây là những gì Peek() kiểm tra trong điều kiện while. RBP của nó xác định mức độ thu hút biểu thức ở bên phải của nó - đây là những gì được thông qua là prev_prec cho lệnh gọi đệ quy.

Đối với các toán tử liên kết trái, LBP và RBP bằng nhau. Khi hai * các toán tử gặp nhau, LBP của * thứ hai không lớn hơn * của đầu tiên RBP, do đó parse() không lặp lại mà thay vào đó lặp ở cùng cấp độ để xây dựng bên trái.

phân tích cú pháp def(prev_prec=0):
    trái = lá()
    trong khi lbp(peek()) > prev_prec:
        op = trước()
        đúng = phân tích cú pháp (rbp(op))
        trái = Nút (op, trái, phải)
    trở về trái