Viết trình thông dịch bằng Python

Điều thu hút tôi nhất với khoa học máy tính ở trường đại học là trình biên dịch. Tôi nghĩ thật kỳ diệu khi các trình biên dịch có thể đọc ngay cả mã nguồn được viết kém của tôi và tạo ra các chương trình phức tạp. Cuối cùng, khi tôi tham gia một khóa học về trình biên dịch, tôi thấy quá trình này đơn giản hơn tôi tưởng rất nhiều

Trong loạt bài viết này, tôi sẽ cố gắng nắm bắt một số điều đơn giản này bằng cách viết một trình thông dịch cho một ngôn ngữ mệnh lệnh cơ bản có tên là IMP. Trình thông dịch sẽ được viết bằng Python vì đây là ngôn ngữ đơn giản, được biết đến rộng rãi. Mã Python trông giống như mã giả, vì vậy ngay cả khi bạn không biết Python, bạn vẫn có thể hiểu nó. Việc phân tích cú pháp sẽ được thực hiện với một bộ tổ hợp trình phân tích cú pháp đơn giản được tạo từ đầu (được giải thích trong phần tiếp theo của loạt bài này). Không có thư viện bên ngoài nào được sử dụng ngoại trừ

if x = 1 then 
  y := 2 
else 
  y := 3
end

if x = 1 then 
  y := 2 
else 
  y := 3
end

if x = 1 then 
  y := 2 
else 
  y := 3
end

Ngôn ngữ IMP

Trước khi bắt đầu viết, hãy thảo luận về ngôn ngữ mà chúng ta sẽ phiên dịch. IMP là một ngôn ngữ mệnh lệnh tối thiểu với các cấu trúc sau

Câu lệnh gán (tất cả các biến là toàn cục và chỉ có thể lưu số nguyên)

x := 1

Câu điều kiện

if x = 1 then 
  y := 2 
else 
  y := 3
end

Vòng lặp While

while x < 10 do 
  x := x + 1
end

Câu lệnh ghép (cách nhau bởi dấu chấm phẩy)

x := 1; 
y := 2

Được rồi, vì vậy nó chỉ là một ngôn ngữ đồ chơi, nhưng bạn có thể dễ dàng mở rộng nó thành thứ gì đó hữu ích hơn như Lua hoặc Python. Tôi muốn giữ mọi thứ đơn giản nhất có thể cho hướng dẫn này

Đây là một ví dụ về chương trình tính giai thừa

n := 5;
p := 1;
while n > 0 do
  p := p * n;
  n := n - 1
end

IMP không cung cấp cách đọc đầu vào, vì vậy trạng thái ban đầu phải được đặt bằng một loạt câu lệnh gán ở đầu chương trình. Cũng không có cách nào để in kết quả nên trình thông dịch sẽ in giá trị của tất cả các biến ở cuối chương trình

Cấu trúc của trình thông dịch

Cốt lõi của trình thông dịch là biểu diễn trung gian (IR). Đây là cách chúng tôi đại diện cho các chương trình IMP trong bộ nhớ. Vì IMP là một ngôn ngữ đơn giản, biểu diễn trung gian sẽ tương ứng trực tiếp với cú pháp của ngôn ngữ; . Trong một ngôn ngữ phức tạp hơn, bạn không chỉ muốn biểu diễn cú pháp mà còn muốn biểu diễn ngữ nghĩa dễ phân tích hoặc thực thi hơn

Trình thông dịch sẽ thực hiện trong ba giai đoạn

1. Tách các ký tự trong mã nguồn thành các mã thông báo
2. Sắp xếp các mã thông báo thành một cây cú pháp trừu tượng (AST). AST là đại diện trung gian của chúng tôi
3. Đánh giá AST và in trạng thái ở cuối

Quá trình tách các ký tự thành mã thông báo được gọi là lexing và được thực hiện bởi một lexer. Mã thông báo là các chuỗi ngắn, dễ hiểu, chứa các phần cơ bản nhất của chương trình như số, mã định danh, từ khóa và toán tử. Từ vựng sẽ loại bỏ khoảng trắng và nhận xét, vì chúng bị trình thông dịch bỏ qua

Quá trình tổ chức mã thông báo thành một cây cú pháp trừu tượng (AST) được gọi là phân tích cú pháp. Trình phân tích cú pháp trích xuất cấu trúc của chương trình thành một dạng mà chúng ta có thể đánh giá

Quá trình thực sự thực thi AST được phân tích cú pháp được gọi là đánh giá. Đây thực sự là phần đơn giản nhất của trình thông dịch

Bài viết này sẽ chỉ tập trung vào từ vựng. Chúng ta sẽ viết một thư viện lexer chung, sau đó sử dụng nó để tạo một lexer cho IMP. Các bài tiếp theo sẽ tập trung vào bộ phân tích cú pháp và bộ đánh giá

thư viện lexer

Hoạt động của lexer khá đơn giản. Nó chủ yếu dựa trên các biểu thức chính quy, vì vậy nếu bạn không quen thuộc với chúng, bạn có thể muốn đọc thêm. Tóm lại, một biểu thức chính quy là một chuỗi được định dạng đặc biệt mô tả các chuỗi khác. Bạn có thể sử dụng chúng để khớp các chuỗi như số điện thoại hoặc địa chỉ email hoặc trong trường hợp của chúng tôi là các loại mã thông báo khác nhau

Đầu vào của từ vựng sẽ chỉ là một dòng ký tự. Để đơn giản, chúng tôi sẽ đọc toàn bộ tệp đầu vào vào bộ nhớ. Đầu ra sẽ là một danh sách các mã thông báo. Mỗi mã thông báo bao gồm một giá trị (chuỗi mà nó đại diện) và một thẻ (để cho biết đó là loại mã thông báo nào). Trình phân tích cú pháp sẽ sử dụng cả hai để quyết định cách tạo AST

Vì hoạt động của một từ vựng đối với bất kỳ ngôn ngữ nào cũng khá giống nhau, nên chúng tôi sẽ tạo một từ vựng chung lấy danh sách các biểu thức chính quy và các thẻ tương ứng. Đối với mỗi biểu thức, nó sẽ kiểm tra xem văn bản nhập có khớp với vị trí hiện tại không. Nếu tìm thấy kết quả phù hợp, văn bản phù hợp sẽ được trích xuất thành mã thông báo, cùng với thẻ của biểu thức chính quy. Nếu biểu thức chính quy không có thẻ liên kết với nó, văn bản sẽ bị loại bỏ. Điều này cho phép chúng tôi loại bỏ các ký tự rác, như nhận xét và khoảng trắng. Nếu không có biểu thức chính quy phù hợp, chúng tôi sẽ báo lỗi và thoát. Quá trình này được lặp lại cho đến khi không còn ký tự nào khớp

Đây là mã từ thư viện lexer

Lưu ý rằng thứ tự chúng ta chuyển vào biểu thức chính quy là quan trọng.

if x = 1 then 
  y := 2 
else 
  y := 3
end

if x = 1 then 
  y := 2 
else 
  y := 3
end

Từ vựng IMP

Với hàm

if x = 1 then 
  y := 2 
else 
  y := 3
end

while x < 10 do 
  x := x + 1
end

while x < 10 do 
  x := x + 1
end

while x < 10 do 
  x := x + 1
end

if x = 1 then 
  y := 2 
else 
  y := 3
end

Tiếp theo, chúng tôi xác định các biểu thức mã thông báo sẽ được sử dụng trong từ vựng. Hai biểu thức đầu tiên khớp với khoảng trắng và nhận xét. Chúng không có thẻ, vì vậy

if x = 1 then 
  y := 2 
else 
  y := 3
end

if x = 1 then 
  y := 2 
else 
  y := 3
end

Sau đó, chúng tôi có tất cả các toán tử và các từ dành riêng. Hãy nhớ rằng, "r" trước mỗi biểu thức chính quy có nghĩa là chuỗi "thô"; . Điều này cho phép chúng tôi bao gồm dấu gạch chéo ngược trong chuỗi, được sử dụng bởi công cụ biểu thức chính quy để thoát khỏi các toán tử như "+" và "*"

if x = 1 then 
  y := 2 
else 
  y := 3
end

Cuối cùng, chúng ta có các biểu thức cho số nguyên và số nhận dạng. Lưu ý rằng biểu thức chính quy cho số nhận dạng sẽ khớp với tất cả các từ dành riêng ở trên, vì vậy điều quan trọng là từ này xuất hiện sau cùng

if x = 1 then 
  y := 2 
else 
  y := 3
end

Bây giờ các biểu thức chính quy của chúng ta đã được xác định, chúng ta cần tạo một hàm lexer thực tế

if x = 1 then 
  y := 2 
else 
  y := 3
end

Nếu bạn tò mò muốn thử điều này, đây là một số mã trình điều khiển để kiểm tra nó

if x = 1 then 
  y := 2 
else 
  y := 3
end

Còn tiếp

Trong phần tiếp theo của loạt bài này, tôi sẽ thảo luận về các tổ hợp trình phân tích cú pháp và mô tả cách sử dụng chúng để xây dựng một cây cú pháp trừu tượng từ danh sách các mã thông báo do từ vựng tạo ra

Làm cách nào để tạo trình thông dịch trong Python?

Bạn có thể viết trình thông dịch Python bằng Python không?

Ví dụ trình thông dịch Python là gì?

Mã trình thông dịch Python là gì?