Computer >> Máy Tính >  >> Lập trình >> Ruby

Tìm hiểu sâu hơn về Ruby Templating:Trình phân tích cú pháp

Hôm nay, chúng ta tiếp tục cuộc hành trình vào Ruby Templating. Với trình phân tích cú pháp, hãy chuyển sang bước tiếp theo:Trình phân tích cú pháp.

Lần trước, chúng tôi đã xem xét nội suy chuỗi và sau đó, đi sâu vào việc tạo ra ngôn ngữ tạo mẫu của riêng chúng tôi. Chúng tôi bắt đầu bằng cách triển khai lexer đọc một mẫu và chuyển nó thành một dòng mã thông báo. Hôm nay, chúng tôi sẽ triển khai trình phân tích cú pháp kèm theo. Chúng tôi cũng sẽ nhúng ngón chân của mình vào một chút lý thuyết ngôn ngữ.

Bắt đầu!

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

Hãy nhìn lại mẫu ví dụ đơn giản của chúng tôi cho Welcome to {{name}} . Sau khi sử dụng lexer để mã hóa chuỗi, chúng tôi nhận được danh sách các mã thông báo như thế này. 

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

Cuối cùng, chúng tôi muốn đánh giá mẫu và thay thế biểu thức bằng các giá trị thực. Để làm cho mọi thứ trở nên khó khăn hơn một chút, chúng tôi cũng muốn đánh giá các biểu thức khối phức tạp, cho phép lặp lại và các điều kiện.

Để làm điều này, chúng ta phải tạo một cây cú pháp trừu tượng (AST) mô tả cấu trúc logic của khuôn mẫu. Cây bao gồm các nút có thể tham chiếu đến các nút khác hoặc lưu trữ dữ liệu bổ sung từ các mã thông báo.

Đối với ví dụ đơn giản của chúng tôi, cây cú pháp trừu tượng mong muốn trông giống như sau:

Xác định ngữ pháp

Để xác định ngữ pháp, hãy bắt đầu với cơ sở lý thuyết của một ngôn ngữ. Giống như các ngôn ngữ lập trình khác, ngôn ngữ tạo mẫu của chúng tôi là ngôn ngữ không có ngữ cảnh và do đó có thể được mô tả bằng ngữ pháp không có ngữ cảnh. (Đừng để các ký hiệu toán học trong phần mô tả chi tiết của Wikipedia làm bạn sợ hãi. Khái niệm này khá dễ hiểu và có nhiều cách thân thiện với nhà phát triển hơn để ghi chú ngữ pháp.)

Ngữ pháp không có ngữ cảnh là một tập hợp các quy tắc mô tả cách tất cả các chuỗi có thể có của một ngôn ngữ được xây dựng. Hãy xem ngữ pháp cho ngôn ngữ tạo mẫu của chúng ta trong ký hiệu EBNF:

template = statements;
statements = { statement };
statement = CONTENT | expression | block_expression;
expression = OPEN_EXPRESSION, IDENTIFIER, arguments, CLOSE;
block_expression = OPEN_BLOCK, IDENTIFIER, arguments, CLOSE, statements, [ OPEN_INVERSE, CLOSE, statements ], OPEN_END_BLOCK, IDENTIFIER, CLOSE;
arguments = { IDENTIFIER };

Mỗi phép gán xác định một quy tắc. Tên của quy tắc ở bên trái và một loạt các quy tắc khác (chữ thường) hoặc mã thông báo (chữ hoa) từ lexer của chúng tôi ở bên phải. Các quy tắc và mã thông báo có thể được nối bằng cách sử dụng dấu phẩy , hoặc xen kẽ bằng cách sử dụng dấu ngoặc kép | Biểu tượng. Quy tắc và mã thông báo bên trong dấu ngoặc nhọn { ... } có thể được lặp lại nhiều lần. Khi chúng nằm bên trong dấu ngoặc nhọn [ ... ] , chúng được coi là tùy chọn.

Ngữ pháp trên là một cách ngắn gọn để mô tả rằng một mẫu bao gồm các câu lệnh. Một câu lệnh là một CONTENT mã thông báo, một biểu thức hoặc một biểu thức khối. Một biểu thức là một OPEN_EXPRESSION mã thông báo, theo sau là IDENTIFIER mã thông báo, theo sau là đối số, theo sau là CLOSE mã thông báo. Và biểu thức khối là ví dụ hoàn hảo về lý do tại sao tốt hơn nên sử dụng ký hiệu như ký hiệu ở trên thay vì cố gắng mô tả nó bằng ngôn ngữ tự nhiên.

Có những công cụ tự động tạo trình phân tích cú pháp từ các định nghĩa ngữ pháp như công cụ ở trên. Nhưng theo truyền thống Ruby Magic thực sự, chúng ta hãy vui vẻ và tự xây dựng trình phân tích cú pháp, hy vọng sẽ học được một hoặc hai điều trong quá trình này.

Xây dựng trình phân tích cú pháp

Bỏ lý thuyết ngôn ngữ sang một bên, chúng ta hãy bắt đầu thực sự xây dựng trình phân tích cú pháp. Hãy bắt đầu với một mẫu thậm chí tối thiểu hơn, nhưng vẫn hợp lệ:Welcome to Ruby Magic . Mẫu này không có bất kỳ biểu thức nào và danh sách mã thông báo chỉ bao gồm một phần tử. Đây là những gì nó trông như thế nào:

[[:CONTENT, "Welcome to Ruby Magic"]]

Đầu tiên, chúng tôi thiết lập lớp phân tích cú pháp của chúng tôi. Nó trông như thế này:

module Magicbars
  class Parser
    def self.parse(tokens)
      new(tokens).parse
    end
 
    attr_reader :tokens
 
    def initialize(tokens)
      @tokens = tokens
    end
 
    def parse
      # Parsing starts here
    end
  end
end

Lớp nhận một mảng các mã thông báo và lưu trữ nó. Nó chỉ có một phương thức công khai được gọi là parse chuyển đổi các mã thông báo thành AST.

Nhìn lại ngữ pháp của chúng tôi, quy tắc hàng đầu là template . Điều đó ngụ ý rằng parse , khi bắt đầu quá trình phân tích cú pháp, sẽ trả về một Template nút.

Các nút là các lớp đơn giản không có hành vi của riêng chúng. Họ chỉ kết nối các nút khác hoặc lưu trữ một số giá trị từ các mã thông báo. Đây là nội dung của Template nút trông giống như:

module Magicbars
  module Nodes
    class Template
      attr_reader :statements
 
      def initialize(statements)
        @statements = statements
      end
    end
  end
end

Để làm cho ví dụ của chúng tôi hoạt động, chúng tôi cũng cần một Content nút. Nó chỉ lưu trữ nội dung văn bản ("Welcome to Ruby Magic" ) từ mã thông báo. 

module Magicbars
  module Nodes
    class Content
      attr_reader :content
 
      def initialize(content)
        @content = content
      end
    end
  end
end

Tiếp theo, hãy triển khai phương thức phân tích cú pháp để tạo một bản sao của Template và một bản sao của Content và kết nối chúng một cách chính xác. 

def parse
  Magicbars::Nodes::Template.new(parse_content)
end
 
def parse_content
  return unless tokens[0][0] == :CONTENT
 
  Magicbars::Nodes::Content.new(tokens[0][1])
end

Khi chúng tôi chạy trình phân tích cú pháp, chúng tôi nhận được kết quả chính xác:

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007fe90e939410 @statements=#<Magicbars::Nodes::Content:0x00007fe90e939578 @content="Welcome to Ruby Magic">>

Phải thừa nhận rằng điều này chỉ hoạt động đối với ví dụ đơn giản của chúng tôi chỉ có một nút nội dung. Hãy chuyển sang một ví dụ phức tạp hơn thực sự bao gồm một biểu thức:Welcome to {{name}} . 

Magicbars::Lexer.tokenize("Welcome to {{name}}")
# => [[:CONTENT, "Welcome to "], [:OPEN_EXPRESSION], [:IDENTIFIER, "name"], [:CLOSE]]

Đối với điều này, chúng tôi cần một Expression và một Identifier nút. Expression nút lưu trữ số nhận dạng cũng như bất kỳ đối số nào (theo ngữ pháp, là một mảng không hoặc nhiều hơn Identifier điểm giao). Cũng như các nút khác, không có nhiều thứ để xem ở đây. 

module Magicbars
  module Nodes
    class Expression
      attr_reader :identifier, :arguments
 
      def initialize(identifier, arguments)
        @identifier = identifier
        @arguments = arguments
      end
    end
  end
end
 
module Magicbars
  module Nodes
    class Identifier
      attr_reader :value
 
      def initialize(value)
        @value = value.to_sym
      end
    end
  end
end

Với các nút mới, hãy sửa đổi parse phương pháp xử lý cả nội dung thông thường cũng như các biểu thức. Chúng tôi thực hiện điều đó bằng cách giới thiệu parse_statements phương thức tiếp tục gọi parse_statement miễn là nó trả về một giá trị. 

def parse
  Magicbars::Nodes::Template.new(parse_statements)
end
 
def parse_statements
  results = []
 
  while result = parse_statement
    results << result
  end
 
  results
end

parse_statement chính nó đầu tiên gọi parse_content và nếu điều đó không trả về bất kỳ giá trị nào, nó sẽ gọi parse_expression . 

def parse_statement
  parse_content || parse_expression
end

Bạn có nhận thấy rằng parse_statement phương thức bắt đầu trông rất giống với câu lệnh statement quy tắc trong ngữ pháp? Đây là lúc dành thời gian để viết rõ ràng ngữ pháp trước sẽ giúp rất nhiều để đảm bảo rằng chúng ta đang đi đúng hướng.

Tiếp theo, hãy sửa đổi parse_content để nó không chỉ nhìn vào mã thông báo đầu tiên. Chúng tôi thực hiện việc này bằng cách giới thiệu thêm một @position biến phiên bản trong trình khởi tạo và sử dụng nó để tìm nạp mã thông báo hiện tại. 

attr_reader :tokens, :position
 
def initialize(tokens)
  @tokens = tokens
  @position = 0
end
 
# ...
 
def parse_content
  return unless token = tokens[position]
  return unless token[0] == :CONTENT
 
  @position += 1
 
  Magicbars::Nodes::Content.new(token[1])
end

parse_content bây giờ phương thức xem xét mã thông báo hiện tại và kiểm tra loại của nó. Nếu đó là CONTENT mã thông báo, nó tăng vị trí (vì mã thông báo hiện tại đã được phân tích cú pháp thành công) và sử dụng nội dung của mã thông báo để tạo Content nút. Nếu không có mã thông báo hiện tại (vì chúng tôi đang ở cuối mã thông báo) hoặc loại không khớp, phương thức sẽ thoát sớm và trả về nil .

Với parse_content được cải tiến tại chỗ, hãy giải quyết parse_expression mới phương pháp. 

def parse_expression
  return unless token = tokens[position]
  return unless token[0] == :OPEN_EXPRESSION
 
  @position += 1
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  if !tokens[position] || tokens[position][0] != :CLOSE
    raise "Unexpected token #{tokens[position][0]}. Expected :CLOSE."
  end
 
  @position += 1
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

Trước tiên, chúng tôi kiểm tra xem có mã thông báo hiện tại không và loại của nó là OPEN_EXPRESSION . Nếu đúng như vậy, chúng tôi chuyển sang mã thông báo tiếp theo và phân tích cú pháp mã định danh cũng như các đối số bằng cách gọi parse_identifier và parse_arguments , tương ứng. Cả hai phương pháp sẽ trả về các nút tương ứng và nâng cấp mã thông báo hiện tại. Khi điều đó hoàn tất, chúng tôi đảm bảo rằng mã thông báo hiện tại tồn tại và là một :CLOSE mã thông báo. Nếu không, chúng tôi đưa ra một lỗi. Nếu không, chúng tôi nâng cấp vị trí lần cuối trước khi trả lại Expression mới được tạo nút.

Tại thời điểm này, chúng tôi thấy một số mô hình nổi lên. Chúng tôi đang chuyển sang mã thông báo tiếp theo nhiều lần và chúng tôi cũng đang kiểm tra xem có mã thông báo hiện tại và loại của nó hay không. Vì mã cho điều đó hơi rườm rà, hãy giới thiệu hai phương pháp trợ giúp. 

def expect(*expected_tokens)
  upcoming = tokens[position, expected_tokens.size]
 
  if upcoming.map(&:first) == expected_tokens
    advance(expected_tokens.size)
    upcoming
  end
end
 
def advance(offset = 1)
  @position += offset
end

expect phương thức nhận một số loại mã thông báo thay đổi và kiểm tra chúng với các mã thông báo tiếp theo trong luồng mã thông báo. Nếu tất cả chúng đều khớp, nó sẽ vượt qua các mã thông báo phù hợp và trả lại chúng. advance phương thức chỉ tăng @position biến phiên bản bằng giá trị bù đã cho.

Đối với những trường hợp không có tính linh hoạt liên quan đến mã thông báo dự kiến ​​tiếp theo, chúng tôi cũng giới thiệu một phương pháp đưa ra thông báo lỗi tốt khi mã thông báo không khớp. 

def need(*required_tokens)
  upcoming = tokens[position, required_tokens.size]
  expect(*required_tokens) or raise "Unexpected tokens. Expected #{required_tokens.inspect} but got #{upcoming.inspect}"
end

Bằng cách sử dụng các phương thức trợ giúp này, parse_content và parse_expression hiện sạch hơn và dễ đọc hơn. 

def parse_content
  if content = expect(:CONTENT)
    Magicbars::Nodes::Content.new(content[0][1])
  end
end
 
def parse_expression
  return unless expect(:OPEN_EXPRESSION)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  Magicbars::Nodes::Expression.new(identifier, arguments)
end

Cuối cùng, hãy cũng xem xét parse_identifier và parse_arguments . Nhờ các phương thức trợ giúp, parse_identifier phương thức đơn giản như parse_content phương pháp. Sự khác biệt duy nhất là nó trả về một loại nút khác. 

def parse_identifier
  if identifier = expect(:IDENTIFIER)
    Magicbars::Nodes::Identifier.new(identifier[0][1])
  end
end

Khi triển khai parse_arguments , chúng tôi nhận thấy rằng nó gần giống với parse_statements phương pháp. Sự khác biệt duy nhất là nó gọi parse_identifier thay vì parse_statement . Chúng tôi có thể loại bỏ logic trùng lặp bằng cách giới thiệu một phương pháp trợ giúp khác. 

def repeat(method)
  results = []
 
  while result = send(method)
    results << result
  end
 
  results
end

repeat phương thức sử dụng send để gọi tên phương thức đã cho cho đến khi nó không còn trả về một nút nào nữa. Khi điều đó xảy ra, các kết quả được thu thập (hoặc chỉ là một mảng trống) sẽ được trả về. Với trình trợ giúp này, cả parse_statements và parse_arguments trở thành các phương thức một dòng. 

def parse_statements
  repeat(:parse_statement)
end
 
def parse_arguments
  repeat(:parse_identifier)
end

Với tất cả những thay đổi này, hãy thử và phân tích cú pháp luồng mã thông báo:

Magicbars::Parser.parse(tokens)
# => #<Magicbars::Nodes::Template:0x00007f91a602f910
#     @statements=
#      [#<Magicbars::Nodes::Content:0x00007f91a58802c8 @content="Welcome to ">,
#       #<Magicbars::Nodes::Expression:0x00007f91a602fcd0
#        @arguments=[],
#        @identifier=
#         #<Magicbars::Nodes::Identifier:0x00007f91a5880138 @value=:name>  >

Hơi khó đọc nhưng trên thực tế, đây là cây cú pháp trừu tượng chính xác. Template nút có Content và một Expression bản tường trình. Content giá trị của nút là "Welcome to " và Expression định danh của nút là Identifier nút với :name như giá trị của nó.

Biểu thức khối phân tích cú pháp

Để hoàn thành việc triển khai trình phân tích cú pháp, chúng ta vẫn phải triển khai phân tích cú pháp các biểu thức khối. Xin nhắc lại, đây là mẫu chúng tôi muốn phân tích cú pháp:

Welcome to {{name}}!
 
{{#if subscribed}}
  Thank you for subscribing to our mailing list.
{{else}}
  Please sign up for our mailing list to be notified about new articles!
{{/if}}
 
Your friends at {{company_name}}

Để thực hiện việc này, trước tiên chúng ta hãy giới thiệu một BlockExpression nút. Mặc dù nút này lưu trữ nhiều dữ liệu hơn một chút, nhưng nó không làm bất cứ điều gì khác và do đó không thú vị lắm. 

module Magicbars
  module Nodes
    class BlockExpression
      attr_reader :identifier, :arguments, :statements, :inverse_statements
 
      def initialize(identifier, arguments, statements, inverse_statements)
        @identifier = identifier
        @arguments = arguments
        @statements = statements
        @inverse_statements = inverse_statements
      end
    end
  end
end

Giống như Expression , nó lưu trữ mã định danh cũng như bất kỳ đối số nào. Ngoài ra, nó cũng lưu trữ các câu lệnh của khối và của khối nghịch đảo.

Nhìn lại ngữ pháp, chúng tôi nhận thấy rằng để phân tích cú pháp các biểu thức khối, chúng tôi phải sửa đổi parse_statements phương thức có lệnh gọi tới parse_block_expression . Bây giờ nó trông giống như quy tắc trong ngữ pháp. 

def parse_statement
  parse_content || parse_expression || parse_block_expression
end

parse_block_expression phương pháp tự nó phức tạp hơn một chút. Nhưng nhờ các phương pháp trợ giúp của chúng tôi, nó vẫn khá dễ đọc. 

def parse_block_expression
  return unless expect(:OPEN_BLOCK)
 
  identifier = parse_identifier
  arguments = parse_arguments
 
  need(:CLOSE)
 
  statements = parse_statements
 
  if expect(:OPEN_INVERSE, :CLOSE)
    inverse_statements = parse_statements
  end
 
  need(:OPEN_END_BLOCK)
 
  if identifier.value != parse_identifier.value
    raise("Error. Identifier in closing expression does not match identifier in opening expression")
  end
 
  need(:CLOSE)
 
  Magicbars::Nodes::BlockExpression.new(identifier, arguments, statements, inverse_statements)
end

Phần đầu tiên rất giống với parse_expression phương pháp. Nó phân tích cú pháp biểu thức khối mở với số nhận dạng và các đối số. Sau đó, nó gọi parse_statements để phân tích cú pháp bên trong khối.

Sau khi hoàn tất, chúng tôi sẽ kiểm tra {{else}} biểu thức, được xác định bởi một OPEN_INVERSE mã thông báo theo sau là CLOSE mã thông báo. Nếu cả hai mã thông báo được tìm thấy, chúng tôi gọi là parse_statements một lần nữa để phân tích cú pháp khối nghịch đảo. Nếu không, chúng tôi chỉ bỏ qua hoàn toàn phần đó.

Cuối cùng, chúng tôi đảm bảo rằng có một biểu thức khối kết thúc sử dụng cùng một định danh với biểu thức khối mở. Nếu các số nhận dạng không khớp, chúng tôi sẽ phát sinh lỗi. Nếu không, chúng tôi tạo một BlockExpression mới và trả về.

Việc gọi trình phân tích cú pháp với các mã thông báo của mẫu biểu thức khối nâng cao sẽ trả về AST cho mẫu. Tôi sẽ không bao gồm đầu ra ví dụ ở đây, vì nó hầu như không thể đọc được. Thay vào đó, đây là bản trình bày trực quan về AST đã tạo.

Bởi vì chúng tôi đang gọi parse_statements bên trong parse_block_expression , cả khối và khối nghịch đảo có thể bao gồm nhiều biểu thức hơn, biểu thức khối, cũng như nội dung thông thường.

Hành trình tiếp tục…

Chúng tôi đã đạt được nhiều tiến bộ trong hành trình hướng tới việc triển khai ngôn ngữ tạo mẫu của riêng mình. Sau một thời gian ngắn nghiên cứu lý thuyết ngôn ngữ, chúng tôi đã xác định ngữ pháp cho ngôn ngữ tạo mẫu của mình và sử dụng nó để triển khai trình phân tích cú pháp cho nó từ đầu.

Với cả lexer và trình phân tích cú pháp, chúng tôi chỉ thiếu một trình thông dịch để tạo chuỗi nội suy từ mẫu của chúng tôi. Chúng tôi sẽ trình bày phần này trong một ấn bản sắp tới của RubyMagic. Đăng ký danh sách gửi thư của Ruby Magic để nhận thông báo khi nó xuất hiện.