Xây dựng một ngôn ngữ lập trình mới trong Ruby:Trình thông dịch

Nguồn đầy đủ trên Github

Bản triển khai hoàn chỉnh của ngôn ngữ lập trình Stoffle có sẵn tại GitHub. Vui lòng mở vấn đề nếu bạn tìm thấy lỗi hoặc có thắc mắc.

Trong bài đăng trên blog này, chúng ta sẽ bắt đầu triển khai trình thông dịch cho Stoffle, một ngôn ngữ lập trình đồ chơi được xây dựng hoàn toàn bằng Ruby. Bạn có thể đọc thêm về dự án này trong phần đầu tiên của loạt bài này.

Trình thông dịch mà chúng tôi sắp xây dựng thường được gọi là trình thông dịch đi bộ trên cây. Trong bài trước của loạt bài này, chúng tôi đã xây dựng một trình phân tích cú pháp để biến đổi một chuỗi mã thông báo phẳng thành cấu trúc dữ liệu dạng cây (cây cú pháp trừu tượng, viết tắt là AST). Như bạn có thể đang tưởng tượng, thông dịch viên của chúng tôi có công việc thông qua AST do trình phân tích cú pháp của chúng tôi tạo ra và đưa cuộc sống vào chương trình Stoffle. Tôi thấy bước cuối cùng này là bước thú vị nhất trong hành trình triển khai ngôn ngữ này. Khi xây dựng trình thông dịch, mọi thứ cuối cùng cũng nhấp chuột và chúng ta có thể thấy các chương trình Stoffle đang chạy thực tế!

Tôi sẽ trình bày và giải thích cách thực hiện của thông dịch viên trong hai phần. Trong phần đầu tiên này, chúng ta sẽ tìm hiểu những điều cơ bản về hoạt động:biến, điều kiện, toán tử một ngôi và nhị phân, kiểu dữ liệu và in ra bảng điều khiển. Chúng tôi đang dự trữ nhiều nội dung quan trọng hơn (định nghĩa hàm, gọi hàm, vòng lặp, v.v.) cho bài đăng thứ hai và cuối cùng về việc triển khai trình thông dịch của chúng tôi.

Bản tóm tắt nhanh về Lexer và Parser

Trước khi đi sâu vào và bắt đầu triển khai trình thông dịch, chúng ta hãy nhanh chóng nhắc nhở bản thân những gì chúng ta đã làm trong các bài viết trước của loạt bài này. Đầu tiên, chúng tôi xây dựng lexer, công cụ này chuyển đổi mã nguồn thô thành mã thông báo. Sau đó, chúng tôi triển khai trình phân tích cú pháp, thành phần chịu trách nhiệm biến mã thông báo thành cấu trúc cây (AST). Tóm lại, đây là những biến đổi mà chúng tôi đã quan sát được cho đến nay:

Trạng thái 0:Nguồn

my_var = 1

Trạng thái 1:Lexer chuyển đổi mã nguồn thô thành mã thông báo

[:identifier, :'=', :number]

Trạng thái 2:Trình phân tích cú pháp chuyển đổi mã thông báo thành Cây cú pháp trừu tượng

Đó là Tất cả về Đi bộ

Bây giờ chúng ta đã có AST, công việc của chúng ta là viết mã để sử dụng cấu trúc này. Chúng tôi phải viết mã Ruby có thể mang lại sự sống cho những gì mỗi nút trong AST của chúng tôi mô tả. Ví dụ:nếu chúng ta có một nút mô tả một ràng buộc biến, nhiệm vụ của chúng ta là viết mã Ruby để bằng cách nào đó có thể lưu trữ kết quả của phía bên phải của biểu thức ràng buộc biến của chúng ta và có không gian lưu trữ này được liên kết với (và có thể truy cập thông qua) tên được đặt cho biến.

Như chúng ta đã làm trong các phần trước của loạt bài này, chúng ta sẽ khám phá việc triển khai bằng cách xem qua tất cả các dòng mã quan trọng liên quan đến việc xử lý một chương trình ví dụ. Đoạn mã Stoffle chúng ta phải giải thích như sau:

num = -2
if num > 0
  println("The number is greater than zero.")
else
  println("The number is less than or equal to zero.")
end

Đây là AST được sản xuất cho cùng một chương trình:

Bước đầu tiên trong chuyến đi của chúng ta

Như bạn có thể nhớ từ bài cuối cùng của loạt bài này, Stoffle AST luôn có gốc là AST::Program nút. Gốc này thường có nhiều con. Một số trong số chúng sẽ nông cạn (hãy nghĩ đến AST được tạo ra cho một phép gán biến đơn giản). Các con khác có thể là gốc của các cây con khá sâu (hãy nghĩ về một vòng lặp với nhiều đường bên trong thân của nó). Đây là mã Ruby mà chúng tôi cần để bắt đầu xem qua AST đã được chuyển cho trình thông dịch của chúng tôi:

module Stoffle
  class Interpreter
    attr_reader :program, :output, :env

    def initialize
      @output = []
      @env = {}
    end

    def interpret(ast)
      @program = ast

      interpret_nodes(program.expressions)
    end

    private

    def interpret_nodes(nodes)
      last_value = nil

      nodes.each do |node|
        last_value = interpret_node(node)
      end

      last_value
    end

    def interpret_node(node)
      interpreter_method = "interpret_#{node.type}"
      send(interpreter_method, node)
    end

    #...

  end
end

Khi một Interpreter mới được khởi tạo, ngay từ khi bắt đầu, chúng tôi tạo hai biến phiên bản:@output và @env . Trách nhiệm của người cũ là lưu trữ, theo trình tự thời gian, mọi thứ mà chương trình của chúng tôi đã in ra. Có sẵn thông tin này rất hữu ích khi viết các bài kiểm tra hoặc gỡ lỗi tự động. Trách nhiệm của @env là một chút khác nhau. Chúng tôi đặt tên nó như một tham chiếu đến "môi trường". Như tên có thể gợi ý, chức năng của nó là giữ trạng thái của chương trình đang chạy của chúng tôi. Một trong những chức năng của nó sẽ là thực hiện liên kết giữa một số nhận dạng (ví dụ:tên biến) và giá trị hiện tại của nó.

#interpret_nodes phương thức lặp qua tất cả các nút con của nút gốc (AST::Program ). Sau đó, nó gọi #interpret_node cho từng nút riêng lẻ.

#interpret_node là đơn giản nhưng vẫn thú vị. Ở đây, chúng tôi sử dụng một chút lập trình chuyển đổi Ruby để gọi phương thức thích hợp để xử lý loại nút hiện đang có. Ví dụ:đối với một AST::VarBinding nút #interpret_var_binding là phương thức được gọi.

Luôn luôn phải nói về các biến

Nút đầu tiên chúng ta phải diễn giải trong AST của chương trình ví dụ mà chúng ta đang xem qua là một AST::VarBinding . @left của nó là một AST::Identifier và @right của nó là một AST::UnaryOperator . Hãy xem xét phương thức chịu trách nhiệm giải thích một ràng buộc biến:

def interpret_var_binding(var_binding)
  env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
end

Như bạn có thể thấy, nó khá đơn giản. Chúng tôi thêm (hoặc ghi đè) một cặp khóa-giá trị vào @env Băm.

Khóa là tên của biến (#var_name_as_str chỉ là một phương thức trợ giúp tương đương với var_binding.left.name ). Hiện tại, tất cả các biến đều là toàn cục. Chúng tôi sẽ xử lý phạm vi trong bài tiếp theo.

Giá trị là kết quả của việc diễn giải biểu thức ở phía bên phải của phép gán. Để làm điều đó, chúng tôi sử dụng #interpret_node lại. Vì chúng tôi có AST::UnaryOperator ở phía bên phải, phương thức tiếp theo được gọi là #interpret_unary_operator :

def interpret_unary_operator(unary_op)
  case unary_op.operator
  when :'-'
    -(interpret_node(unary_op.operand))
  else # :'!'
    !(interpret_node(unary_op.operand))
  end
end

Ngữ nghĩa của các toán tử một ngôi được hỗ trợ của Stoffle (- và ! ) giống như trong Ruby. Do đó, việc triển khai không thể đơn giản hơn:chúng tôi áp dụng - của Ruby toán tử cho kết quả của việc diễn giải toán hạng. Nghi phạm thông thường, #interpret_node , lại xuất hiện ở đây. Như bạn có thể nhớ từ AST của chương trình của chúng tôi, toán hạng cho - là một AST::Number (số 2 ). Điều này có nghĩa là điểm dừng tiếp theo của chúng tôi là #interpret_number :

def interpret_number(number)
  number.value
end

Việc triển khai #interpret_number là một miếng bánh. Quyết định của chúng tôi về việc áp dụng một Ruby float làm đại diện cho các ký tự số (điều này xảy ra trong lexer!) Đã được đền đáp ở đây. @value của AST::Number nút đã giữ biểu diễn nội bộ mong muốn của chúng tôi về các số, vì vậy chúng tôi chỉ cần truy xuất nó.

Sau đó, chúng ta hoàn tất việc diễn giải con trực tiếp đầu tiên của AST::Program . Bây giờ, để kết thúc việc diễn giải chương trình của chúng ta, chúng ta phải xử lý một nút con khác, nhiều lông hơn của nó:một nút thuộc loại AST::Conditional .

Các Điều khoản và Điều kiện Có thể Áp dụng

Quay lại #interpret_nodes , người bạn thân nhất của chúng tôi #interpret_node được gọi lại để diễn giải con trực tiếp tiếp theo của AST::Program .

def interpret_nodes(nodes)
  last_value = nil

  nodes.each do |node|
    last_value = interpret_node(node)
  end

  last_value
end

Phương thức chịu trách nhiệm giải thích một AST::Conditional là #interpret_conditional . Tuy nhiên, trước khi xem xét nó, hãy làm mới ký ức của chúng ta bằng cách xem lại việc triển khai AST::Conditional chính nó:

class Stoffle::AST::Conditional < Stoffle::AST::Expression
  attr_accessor :condition, :when_true, :when_false

  def initialize(cond_expr = nil, true_block = nil, false_block = nil)
    @condition = cond_expr
    @when_true = true_block
    @when_false = false_block
  end

  def ==(other)
    children == other&.children
  end

  def children
    [condition, when_true, when_false]
  end
end

Ok, vậy @condition giữ một biểu thức có thể là true hoặc falsey; @when_true giữ một khối có một hoặc nhiều biểu thức sẽ được thực thi trong trường hợp @condition là sự thật và @when_false (ELSE mệnh đề) giữ khối sẽ được chạy trong trường hợp @condition xảy ra là giả dối.

Bây giờ, hãy xem qua #interpret_condition :

def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)

  # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle.
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?

    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end

Độ tin cậy trong Stoffle cũng giống như trong Ruby. Nói cách khác, trong Stoffle, chỉ nil và false là giả dối. Bất kỳ đầu vào nào khác cho một điều kiện đều là trung thực.

Trước tiên, chúng tôi đánh giá điều kiện bằng cách diễn giải biểu thức được nắm giữ bởi conditional.condition . Hãy cùng xem lại AST của chương trình của chúng tôi để tìm ra nút nào chúng tôi đang xử lý:

Hóa ra chúng ta có AST::BinaryOperator (> được sử dụng trong num > 0 ). Được rồi, lại là cùng một đường dẫn:#interpret_node đầu tiên , gọi #interpret_binary_operator lúc này:

def interpret_binary_operator(binary_op)
  case binary_op.operator
  when :and
    interpret_node(binary_op.left) && interpret_node(binary_op.right)
  when :or
    interpret_node(binary_op.left) || interpret_node(binary_op.right)
  else
    interpret_node(binary_op.left).send(binary_op.operator, interpret_node(binary_op.right))
  end
end

Toán tử logic của chúng tôi (and và or ) có thể được coi là toán tử nhị phân, vì vậy chúng tôi xử lý chúng ở đây. Vì ngữ nghĩa của chúng tương đương với && của Ruby và || , việc triển khai diễn ra đơn giản, như bạn có thể thấy ở trên.

Tiếp theo là phần phương pháp mà chúng tôi tâm đắc nhất; phần này xử lý tất cả các toán tử nhị phân khác (bao gồm > ). Ở đây, chúng ta có thể tận dụng tính năng động của Ruby theo hướng có lợi cho mình và đưa ra một giải pháp rất ngắn gọn. Trong Ruby, các toán tử nhị phân có sẵn dưới dạng các phương thức trong các đối tượng tham gia vào một hoạt động:

-2 > 0           # is equivalent to
-2.send(:'>', 0) # this
# and the following line would be a general solution,
# very similar to what we have in the interpreter
operand_1.send(binary_operator, operand_2)

Triển khai Chi tiết về Toán tử Nhị phân

Như bạn đã thấy, việc triển khai các toán tử nhị phân của chúng tôi rất ngắn gọn. Nếu Ruby không phải là một ngôn ngữ động như vậy, hoặc ngữ nghĩa của các toán tử khác nhau giữa Ruby và Stoffle, chúng tôi không thể mã hóa giải pháp theo kiểu này.

Nếu bạn từng thấy mình ở vị trí như một nhà thiết kế / triển khai ngôn ngữ, bạn luôn có thể quay trở lại với một giải pháp đơn giản (nhưng không phải là thanh lịch):sử dụng cấu trúc chuyển đổi. Trong trường hợp của chúng tôi, việc triển khai sẽ giống như sau:

# ... inside #interpret_binary_operator ...

case binary_op.operator
when :'+'
  interpret_node(binary_op.left) + interpret_node(binary_op.right)
# ... other operators
end

Trước khi quay lại #interpret_conditional , chúng ta hãy đi đường vòng nhanh chóng để đảm bảo rằng không có gì bị bỏ qua. Nếu bạn nhớ chương trình chúng tôi đang thông dịch, thì num biến được sử dụng trong phép so sánh (sử dụng toán tử nhị phân > ) chúng ta vừa cùng nhau khám phá. Làm cách nào để chúng tôi truy xuất toán hạng bên trái (tức là giá trị được lưu trữ trong num biến) của so sánh đó? Phương thức chịu trách nhiệm cho việc đó là #interpret_identifier và việc triển khai nó rất dễ dàng:

def interpret_identifier(identifier)
  if env.has_key?(identifier.name)
    env[identifier.name]
  else
    # Undefined variable.
    raise Stoffle::Error::Runtime::UndefinedVariable.new(identifier.name)
  end
end

Bây giờ, quay lại #interpret_conditional . Trong trường hợp của chương trình nhỏ của chúng tôi, điều kiện được đánh giá là Ruby false giá trị. Chúng tôi sử dụng giá trị này để xác định xem chúng tôi phải thực thi IF hay nhánh ELSE của cấu trúc điều kiện. Chúng tôi tiến hành diễn giải nhánh ELSE, có khối mã liên quan được lưu trữ trong conditional.when_false . Ở đây, chúng ta có AST::Block , rất giống với nút gốc của AST (AST::Program ). Tương tự như vậy, khối có thể có một loạt các biểu thức cần được diễn giải. Vì mục đích này, chúng tôi cũng sử dụng #interpret_nodes .

def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)

  # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle.
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?

    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end

Nút AST tiếp theo mà chúng ta phải xử lý là một AST::FunctionCall . Phương thức chịu trách nhiệm thông dịch một lệnh gọi hàm là #interpret_function_call :

def interpret_function_call(fn_call)
  return if println(fn_call)
end

Như chúng ta đã thảo luận ở phần đầu của bài viết, định nghĩa hàm và gọi hàm sẽ được đề cập trong bài tiếp theo của loạt bài này. Do đó, chúng tôi chỉ thực hiện một trường hợp đặc biệt của việc gọi hàm. Bằng ngôn ngữ đồ chơi nhỏ bé của mình, chúng tôi cung cấp println như một phần của thời gian chạy và triển khai nó trực tiếp trong trình thông dịch tại đây. Đó là một giải pháp đủ tốt, xem xét các mục tiêu và phạm vi dự án của chúng tôi.

def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'

  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end

Đối số đầu tiên và duy nhất của AST::FunctionCall của chúng tôi là một AST::String , được xử lý bởi #interpret_string :

def interpret_string(string)
  string.value
end

Trong #interpret_string , chúng ta có cùng một trường hợp #interpret_number . AST::String đã giữ một giá trị chuỗi Ruby sẵn sàng để sử dụng, vì vậy chúng tôi chỉ cần truy xuất nó.

Bây giờ, quay lại #println :

def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'

  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end

Sau khi lưu trữ đối số hàm (được chuyển đổi thành chuỗi Ruby) trong result , chúng tôi còn hai bước nữa để hoàn thành. Đầu tiên, chúng tôi lưu trữ những gì chúng tôi sắp in vào bảng điều khiển trong @output . Như đã giải thích trước đây, ý tưởng ở đây là có thể dễ dàng kiểm tra những gì đã được in (và theo thứ tự nào). Có sẵn điều này giúp cuộc sống của chúng tôi dễ dàng hơn khi gỡ lỗi hoặc kiểm tra trình thông dịch. Cuối cùng, để thực hiện in một thứ gì đó vào bảng điều khiển, chúng tôi sử dụng puts của Ruby .

Vấn đề Thực thi

Bây giờ chúng ta đã khám phá mọi thứ cần thiết để triển khai phần thô của Stoffle, hãy tạo một tệp thực thi rất cơ bản để xem trình thông dịch của chúng ta đang hoạt động.

#!/usr/bin/env ruby

require_relative '../lib/stoffle'

path = ARGV[0]
source = File.read(path)
lexer = Stoffle::Lexer.new(source)
parser = Stoffle::Parser.new(lexer.start_tokenization)
interpreter = Stoffle::Interpreter.new

interpreter.interpret(parser.parse)

exit(0)

MẸO: Để sử dụng trình thông dịch của Stoffle từ mọi nơi, hãy nhớ thêm tệp thực thi vào PATH của bạn.

Cuối cùng đã đến lúc chạy chương trình của chúng tôi. Nếu mọi thứ hoạt động tốt, chúng ta sẽ thấy chuỗi "Số nhỏ hơn hoặc bằng 0" được in ra bảng điều khiển. Đây chính xác là những gì sẽ xảy ra khi chúng tôi chạy trình thông dịch:

MẸO: Nếu bạn đã cài đặt trình thông dịch, hãy thử thay đổi num trong chương trình mẫu của chúng tôi để nó chứa một số lớn hơn 0. Như mong đợi, bây giờ nhánh IF sẽ được thực thi và chuỗi "Số lớn hơn 0" sẽ được in ra.

Kết thúc

Trong bài đăng này, chúng ta đã thấy sự khởi đầu của trình thông dịch Stoffle. Chúng tôi đã triển khai đủ trình thông dịch để nó xử lý một số kiến ​​thức cơ bản về ngôn ngữ:biến, điều kiện, toán tử đơn phân và nhị phân, kiểu dữ liệu và in ra bảng điều khiển. Trong phần tiếp theo và cuối cùng của trình thông dịch, chúng tôi sẽ giải quyết các bit còn lại cần thiết để chúng tôi có ngôn ngữ đồ chơi nhỏ của chúng tôi hoạt động như thiết kế:phạm vi biến, định nghĩa hàm, gọi hàm và các vòng lặp. Tôi hy vọng bạn đã đọc bài viết vui vẻ (tôi chắc chắn đã rất vui khi viết nó!) Và chúng ta sẽ sớm gặp lại bạn trong bài viết tiếp theo của loạt bài này!