Rubyでのプログラミング言語の構築：パーサー

前のセクションで、 #parse_function_paramsを見ました #parse_function_definition内で呼び出されます 。パーサーの実行フローと状態を要約した表に戻ると、 #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の最初の部分 簡単です。有効な構文がある場合（の後に少なくとも1つの識別子： ）、ポインタを2つの位置に移動することになります：

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

これで、解析される最初のパラメーター（：identifier タイプのトークン）に座っています。 ）。予想どおり、 AST ::Identifierを作成します そして、それを、潜在的に、まだ解析されていない他の複数のパラメーターの配列にプッシュします。 #parse_function_paramsの次のビット 、パラメータセパレータ（つまり、タイプ：'、' のトークン）がある限り、パラメータの解析を続行します ）。ローカル変数identifiersを返すことでメソッドを終了します 、複数の AST ::Identityを含む可能性のある配列 ノード。それぞれが1つのパラメータを表します。ただし、この場合、この配列には1つの要素しかありません。

関数本体はどうですか？

それでは、関数定義の解析の最後の部分である、その本体の処理について詳しく見ていきましょう。 #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 関数。 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 キーワード。 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 関数）。 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 ノード。 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: