การสร้างภาษาโปรแกรมใน Ruby:The Parser

[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof]

ตารางด้านล่างแสดงลำดับการเรียกวิธีการที่สำคัญที่สุดเมื่อเราแยกวิเคราะห์โทเค็นด้านบน โปรดทราบว่านี่เป็นการทำให้เข้าใจง่าย และหากคุณต้องการเข้าใจขั้นตอนที่แน่นอนของการดำเนินการ parser จริงๆ ฉันขอแนะนำให้ใช้โปรแกรมแก้ไขข้อบกพร่อง Ruby เช่น Byebug และเลื่อนทีละบรรทัดขณะที่โปรแกรมดำเนินการ

ตัวแยกวิเคราะห์ของเราภายใต้กล้องจุลทรรศน์

มีการทดสอบที่ใช้ตัวอย่างที่เรากำลังสำรวจซึ่งมีอยู่ในแหล่งที่มาของ Stoffle คุณสามารถค้นหาได้ใน spec/lib/stoffle/parser_spec.rb; เป็นการทดสอบที่ใช้ตัวอย่างชื่อ complex_program_ok_2.sfe .

หากต้องการสำรวจการดำเนินการ parser ทีละขั้นตอน คุณสามารถแก้ไขแหล่งที่มาและเพิ่มการเรียกไปที่ byebug ที่จุดเริ่มต้นของ Parser#parse ให้รันเฉพาะการทดสอบดังกล่าวด้วย RSpec จากนั้นใช้ ขั้นตอน ของ Byebug คำสั่งให้เลื่อนโปรแกรมทีละบรรทัด

ดูข้อมูลเพิ่มเติมเกี่ยวกับวิธีการทำงานของ Byebug และคำสั่งที่มีอยู่ทั้งหมดโดยไปที่ไฟล์ README ของโครงการที่ GitHub

ตอนนี้เรามีแนวคิดทั่วไปแล้วว่ามีการเรียกเมธอดใด เช่นเดียวกับลำดับ มาศึกษาวิธีการแยกวิเคราะห์บางวิธีที่เรายังไม่ได้เห็นในรายละเอียดมากกว่านี้

วิธี #parse_function_definition

เมธอด #parse_function_definition ถูกเรียกเมื่อโทเค็นปัจจุบันคือ :fn และอันต่อไปคือ :identifier :

def parse_function_definition
  return unless consume_if_nxt_is(build_token(:identifier))
  fn = AST::FunctionDefinition.new(AST::Identifier.new(current.lexeme))

  if nxt.type != :"\n" && nxt.type != :':'
    unexpected_token_error
    return
  end

  fn.params = parse_function_params if nxt.type == :':'

  return unless consume_if_nxt_is(build_token(:"\n", "\n"))
  fn.body = parse_block

  fn
end

#consume_if_nxt_is - อย่างที่คุณอาจเดาได้ - เลื่อนตัวชี้ของเราหากโทเค็นถัดไปเป็นประเภทที่กำหนด มิฉะนั้น จะเพิ่มข้อผิดพลาดใน @errors . #consume_if_nxt_is มีประโยชน์มาก - และใช้ในวิธี parser มากมาย - เมื่อเราต้องการตรวจสอบโครงสร้างของโทเค็นเพื่อตรวจสอบว่าเรามีไวยากรณ์ที่ถูกต้องหรือไม่ หลังจากทำเช่นนั้น โทเค็นปัจจุบันจะเป็นประเภท :identifier (เรากำลังจัดการ 'double' ชื่อของฟังก์ชัน) และเราสร้าง AST::Identifier และส่งไปยังคอนสตรัคเตอร์เพื่อสร้างโหนดเพื่อแสดงนิยามฟังก์ชัน (AST::FunctionDefinition ). เราจะไม่ดูรายละเอียดที่นี่ แต่โดยพื้นฐานแล้ว AST::FunctionDefinition โหนดคาดหวังชื่อฟังก์ชัน อาจเป็นอาร์เรย์ของพารามิเตอร์และเนื้อหาของฟังก์ชัน

ขั้นตอนต่อไปใน #parse_function_definition คือการตรวจสอบว่าโทเค็นถัดไปหลังจากตัวระบุเป็นตัวยุตินิพจน์ (เช่น ฟังก์ชันที่ไม่มีพารามิเตอร์) หรือโคลอน (เช่น ฟังก์ชันที่มีพารามิเตอร์หนึ่งตัวหรือหลายตัว) หากเรามีพารามิเตอร์เช่นเดียวกับ double ฟังก์ชันที่เรากำหนด เราเรียก #parse_function_params เพื่อแยกวิเคราะห์พวกเขา เราจะตรวจสอบวิธีการนี้ในอีกสักครู่ แต่ก่อนอื่นเรามาทำการสำรวจ #parse_function_definition ให้เสร็จสิ้นก่อน .

ขั้นตอนสุดท้ายคือการตรวจสอบไวยากรณ์อื่นเพื่อตรวจสอบว่ามีตัวสิ้นสุดหลังจากชื่อฟังก์ชัน + params จากนั้นให้ดำเนินการแยกวิเคราะห์เนื้อหาของฟังก์ชันโดยเรียก #parse_block . สุดท้าย เราคืน fn ซึ่งเก็บ AST::FunctionDefinition . ที่สร้างขึ้นอย่างสมบูรณ์ของเรา เช่น มีชื่อฟังก์ชัน พารามิเตอร์ และเนื้อหาครบถ้วน

การแยกวิเคราะห์ถั่วและสลักเกลียวของพารามิเตอร์ฟังก์ชัน

ในส่วนที่แล้ว เราเห็นว่า #parse_function_params ถูกเรียกภายใน #parse_function_definition . หากเรากลับไปที่ตารางของเราเพื่อสรุปขั้นตอนการดำเนินการและสถานะของ parser เราจะเห็นว่าเมื่อ #parse_function_params เริ่มทำงาน โทเค็นปัจจุบันเป็นประเภท :identifier และอันต่อไปคือ :":" (เช่น เราเพิ่งแยกวิเคราะห์ชื่อฟังก์ชันเสร็จ) เมื่อคำนึงถึงสิ่งนี้แล้ว มาดูโค้ดเพิ่มเติมกัน:

def parse_function_params
  consume
  return unless consume_if_nxt_is(build_token(:identifier))

  identifiers = []
  identifiers << AST::Identifier.new(current.lexeme)

  while nxt.type == :','
    consume
    return unless consume_if_nxt_is(build_token(:identifier))
    identifiers << AST::Identifier.new(current.lexeme)
  end

  identifiers
end

ก่อนที่ฉันจะอธิบายแต่ละส่วนของวิธีนี้ มาสรุปโทเค็นที่เราต้องดำเนินการและเราอยู่ในงานนี้:

[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof]
      # here ▲

ส่วนแรกของ #parse_function_params ตรงไปตรงมา หากเรามีไวยากรณ์ที่ถูกต้อง (อย่างน้อยหนึ่งตัวระบุหลัง : ) ในที่สุดเราก็เลื่อนตัวชี้ไปสองตำแหน่ง:

[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof]
                         # ▲

ตอนนี้ เรากำลังนั่งอยู่ที่พารามิเตอร์แรกที่จะแยกวิเคราะห์ (โทเค็นประเภท :identifier ). ตามที่คาดไว้ เราสร้าง AST::Identifier และส่งไปยังอาร์เรย์ของพารามิเตอร์อื่น ๆ ที่อาจยังไม่ได้แยกวิเคราะห์ ในบิตถัดไปของ #parse_function_params เราแยกวิเคราะห์พารามิเตอร์ต่อไปตราบใดที่ยังมีตัวคั่นพารามิเตอร์ (เช่น โทเค็นประเภท :',' ). เราสิ้นสุดวิธีการโดยส่งคืน var identifiers . ในเครื่อง อาร์เรย์ที่มี AST::Identifier หลายตัว โหนด แต่ละโหนดแทนหนึ่งพารามิเตอร์ อย่างไรก็ตาม ในกรณีของเรา อาร์เรย์นี้มีเพียงองค์ประกอบเดียว

แล้วเนื้อหาเกี่ยวกับฟังก์ชันล่ะ

ตอนนี้ มาเจาะลึกในส่วนสุดท้ายของการแยกวิเคราะห์นิยามฟังก์ชัน:การจัดการกับเนื้อหา เมื่อ #parse_block เรียกว่าเรากำลังนั่งอยู่ที่เทอร์มิเนเตอร์ที่ทำเครื่องหมายจุดสิ้นสุดของรายการพารามิเตอร์ฟังก์ชัน:

[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof]
                                      # ▲

And, here's the implementation of #parse_block :

def parse_block
  consume
  block = AST::Block.new
  while current.type != :end && current.type != :eof && nxt.type != :else
    expr = parse_expr_recursively
    block << expr unless expr.nil?
    consume
  end
  unexpected_token_error(build_token(:eof)) if current.type == :eof

  block
end

AST::Block is the AST node for representing, well, a block of code. In other words, AST::Block just holds a list of expressions, in a very similar fashion as the root node of our program, an AST::Program node (as we saw at the beginning of this post). To parse the block (i.e., the function body), we continue advancing through unprocessed tokens until we encounter a token that marks the end of the block.

To parse the expressions that compose the block, we use our already-known #parse_expr_recursively . We will step into this method call in just a moment; this is the point in which we will start parsing the product operation happening inside our double function. Following this closely will allow us to understand the use of precedence values inside #parse_expr_recursively and how an infix operator (the * in our case) gets dealt with. Before we do that, however, let's finish our exploration of #parse_block .

Before returning an AST node representing our block, we check whether the current token is of type :eof . If this is the case, we have a syntax error since Stoffle requires a block to end with the end keyword. To wrap up the explanation of #parse_block , I should mention something you have probably noticed; one of the conditions of our loop verifies whether the next token is of type :else . This happens because #parse_block is shared by other parsing methods, including the methods responsible for parsing conditionals and loops. Pretty neat, huh?!

Parsing Infix Operators

The name may sound a bit fancy, but infix operators are, basically, those we are very used to seeing in arithmetic, plus some others that we may be more familiar with by being software developers:

module Stoffle
  class Parser
    # ...

    BINARY_OPERATORS = [:'+', :'-', :'*', :'/', :'==', :'!=', :'>', :'<', :'>=', :'<='].freeze
    LOGICAL_OPERATORS = [:or, :and].freeze

    # ...
  end
end

They are expected to be used infixed when the infix notation is used, as is the case with Stoffle, which means they should appear in the middle of their two operands (e.g., as * appears in num * 2 in our double function). Something worth mentioning is that although the infix notation is pretty popular, there are other ways of positioning operators in relation to their operands. If you are curious, research a little bit about "Polish notation" and "reverse Polish notation" methods.

To finish parsing our double function, we have to deal with the * operator:

fn double: num
  num * 2
end

In the previous section, we mentioned that parsing the expression that composes the body of double starts when #parse_expr_recursively is called within #parse_block . When that happens, here's our position in @tokens :

[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof]
                                      # ▲

And, to refresh our memory, here's the code for #parse_expr_recursively again:

def parse_expr_recursively(precedence = LOWEST_PRECEDENCE)
  parsing_function = determine_parsing_function
  if parsing_function.nil?
    unrecognized_token_error
    return
  end
  expr = send(parsing_function)
  return if expr.nil? # When expr is nil, it means we have reached a \n or a eof.

  # Note that here, we are checking the NEXT token.
  while nxt_not_terminator? && precedence < nxt_precedence
    infix_parsing_function = determine_infix_function(nxt)
    return expr if infix_parsing_function.nil?

    consume
    expr = send(infix_parsing_function, expr)
  end

  expr
end

In the first part of the method, we will use the same #parse_identifier method we used to parse the num variable. Then, for the first time, the conditions of the while loop will evaluate to true; the next token is not a terminator, and the precedence of the next token is greater than the precedence of this current execution of parse_expr_recursively (precedence is the default, 0, while nxt_precedence returns 6 since the next token is of type :'*' ). This indicates that the node we already built (an AST::Identifier representing num ) will probably be deeper in our AST (i.e., it will be the child of a node yet to be built). We enter the loop and call #determine_infix_function , passing to it the next token (the * ):

def determine_infix_function(token = current)
  if (BINARY_OPERATORS + LOGICAL_OPERATORS).include?(token.type)
    :parse_binary_operator
  elsif token.type == :'('
    :parse_function_call
  end
end

Since * is a binary operator, running #determine_infix_function will result in :parse_binary_operator . Back in #parse_expr_recursively , we will advance our tokens pointer by one position and then call #parse_binary_operator , passing along the value of expr (the AST::Identifier representing num ):

[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof]
                                                          #▲

def parse_binary_operator(left)
  op = AST::BinaryOperator.new(current.type, left)
  op_precedence = current_precedence

  consume
  op.right = parse_expr_recursively(op_precedence)

  op
end

class Stoffle::AST::BinaryOperator < Stoffle::AST::Expression
  attr_accessor :operator, :left, :right

  def initialize(operator, left = nil, right = nil)
    @operator = operator
    @left = left
    @right = right
  end

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

  def children
    [left, right]
  end
end

At #parse_binary_operator , we create an AST::BinaryOperator (its implementation is shown above if you are curious) to represent * , setting its left operand to the identifier (num ) we received from #parse_expr_recursively . Then, we save the precedence value of * at the local var op_precedence and advance our token pointer. To finish building our node representing * , we call #parse_expr_recursively again! We need to proceed in this fashion because the right-hand side of our operator will not always be a single number or identifier; it can be a more complex expression, such as something like num * (2 + 2) .

One thing of utmost importance that happens here at #parse_binary_operator is the way in which we call #parse_expr_recursively back again. We call it passing 6 as a precedence value (the precedence of * , stored at op_precedence ). Here we observe an important aspect of our parsing algorithm, which was mentioned previously. By passing a relatively high precedence value, it seems like * is pulling the next token as its operand. Imagine we were parsing an expression like num * 2 + 1; in this case, the precedence value of * passed in to this next call to #parse_expr_recursively would guarantee that the 2 would end up being the right-hand side of * and not an operand of + , which has a lower precedence value of 5 .

After #parse_expr_recursively returns an AST::Number node, we set it as the right-hand size of * and, finally, return our complete AST::BinaryOperator node. At this point, we have, basically, finished parsing our Stoffle program. We still have to parse some terminator tokens, but this is straightforward and not very interesting. At the end, we will have an AST::Program instance at @ast with expressions that could be visually represented as the tree we saw at the beginning of this post and in the introduction to the second section of the post:

Wrapping Up

In this post, we covered the principal aspects of Stoffle's parser. If you understand the bits we explored here, you shouldn't have much trouble understanding other parser methods we were not able to cover, such as parsing conditionals and loops. I encourage you to explore the source code of the parser by yourself and tweak the implementation if you are feeling more adventurous! The implementation is accompanied by a comprehensive test suite, so don't be afraid to try things out and mess up with the parser.

In subsequent posts in this series, we will finally breathe life into our little monster by implementing the last bit we are missing:the tree-walk interpreter. I can't wait to be there with you as we run our first Stoffle program!