Ruby로 프로그래밍 언어 구축:파서

Github의 전체 소스

Stoffle 프로그래밍 언어의 완전한 구현은 GitHub에서 사용할 수 있습니다. 이 참조 구현에는 코드를 더 쉽게 읽을 수 있도록 많은 주석이 있습니다. 버그를 발견하거나 질문이 있는 경우 언제든지 문제를 열어주세요.

이 블로그 게시물에서 우리는 완전히 Ruby로 구축된 장난감 프로그래밍 언어인 Stoffle용 파서를 구현할 것입니다. 이 시리즈의 첫 번째 부분에서 이 프로젝트에 대한 자세한 내용을 읽을 수 있습니다.

처음부터 파서를 구축하면서 예상치 못한 통찰력과 지식을 얻을 수 있었습니다. 이 경험은 개인마다 다를 수 있지만 이 기사를 읽은 후 다음 중 적어도 하나에 대한 지식을 습득하거나 심화할 것이라고 가정하는 것이 안전하다고 생각합니다.

• 소스 코드를 다르게 보고 부인할 수 없는 나무와 같은 구조를 발견하게 될 것입니다. 훨씬 더 쉽게;
• 구문 설탕에 대해 더 깊이 이해할 수 있습니다. Stoffle, Ruby 또는 기타 프로그래밍 언어에 관계없이 모든 곳에서 볼 수 있습니다.

나는 파서가 파레토 원리의 완벽한 예라고 생각합니다. 멋진 오류 메시지와 같은 멋진 기능을 만드는 데 필요한 작업의 양은 기본을 시작하고 실행하는 데 필요한 노력에 비해 분명히 더 많고 불균형합니다. 우리는 본질적인 부분에 집중하고 개선 사항은 독자 여러분께 도전 과제로 남길 것입니다. 이 시리즈의 이후 기사에서 더 흥미로운 추가 기능을 다룰 수도 있고 다루지 않을 수도 있습니다.

구문 설탕

구문 설탕은 언어를 사용하기 쉽게 만드는 구문을 나타내는 데 사용되는 표현이지만, 제거해도 프로그래밍 언어의 기능이 손실되지는 않습니다. 좋은 예는 Ruby의 elsif입니다. 건설하다. Stoffle에는 그러한 구조가 없으므로 동일하게 표현하기 위해 더 장황하게 설명해야 합니다.

if some_condition
  # ...
else # oops, no elsif available
  if another_condition
    # ...
  end
end

파서란 무엇입니까?

원시 문자 시퀀스인 소스 코드로 시작합니다. 그런 다음 이 시리즈의 이전 기사에서 볼 수 있듯이 렉서는 이러한 문자를 토큰이라고 하는 합리적인 데이터 구조로 그룹화합니다. 그러나 여전히 소스 코드의 중첩된 특성을 적절하게 나타내지 못하는 완전히 평평한 데이터가 남아 있습니다. 따라서 파서는 이 문자 시퀀스에서 트리를 만드는 작업을 수행합니다. 작업이 완료되면 프로그램의 각 부분이 중첩되고 서로 관련되는 방식을 마침내 표현할 수 있는 데이터로 끝납니다.

파서에 의해 생성된 트리는 일반적으로 추상 구문 트리(AST)라고 합니다. 이름에서 알 수 있듯이, 루트는 프로그램 자체를 나타내고 이 프로그램 노드의 자식은 프로그램을 구성하는 많은 표현식인 트리 데이터 구조를 다루고 있습니다. 추상이라는 단어 AST에서 추상화하는 능력을 나타냅니다. 이전 단계에서 명시적으로 존재했던 부품. 좋은 예는 표현 종결자(Stoffle의 경우 새 줄)입니다. AST를 구축할 때 고려되지만 종료자를 나타내기 위해 특정 노드 유형이 필요하지 않습니다. 그러나 명시적인 토큰이 있음을 기억하십시오. 종결자를 나타냅니다.

예제 AST의 시각화가 있으면 유용하지 않을까요? 당신의 소원은 주문입니다! 다음은 이 게시물의 뒷부분에서 단계별로 구문 분석할 간단한 Stoffle 프로그램과 해당 추상 구문 트리입니다.

fn double: num
  num * 2
end

소스에서 AST로의 첫 번째 예

게시물의 이 섹션에서는 파서가 매우 변수 바인딩이 표현되는(즉, 변수에 값을 할당하는) 한 줄로 구성된 간단한 Stoffle 프로그램입니다. 다음은 소스, 렉서에 의해 생성된 토큰의 단순화된 표현(이 토큰은 파서에 제공되는 입력입니다) 및 마지막으로 프로그램을 나타내기 위해 생성할 AST의 시각적 표현입니다.

출처

my_var = 1

토큰(렉서의 출력, 파서의 입력)

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

파서 출력의 시각적 표현(추상 구문 트리)

상상할 수 있듯이 파서의 핵심은 렉서의 핵심과 매우 유사합니다. 렉서의 경우 처리해야 할 문자가 많았습니다. 이제 컬렉션을 반복해야 하지만 파서의 경우 lexer 친구가 생성한 토큰 목록을 살펴보겠습니다. 단일 포인터(@next_p ) 토큰 수집에서 우리의 위치를 ​​추적합니다. 이 포인터는 다음을 표시합니다. 처리할 토큰입니다. 이 단일 포인터만 있지만 필요에 따라 사용할 수 있는 다른 많은 "가상" 포인터가 있습니다. 구현을 진행하면서 나타날 것입니다. 그러한 "가상" 포인터 중 하나는 current입니다. (기본적으로 @next_p - 1의 토큰 ).

#parse @ast에서 사용할 수 있는 AST로 토큰을 변환하기 위해 호출하는 메서드입니다. 인스턴스 변수. #parse 구현 간단합니다. #consume을 호출하여 컬렉션을 계속 진행합니다. @next_p 이동 처리할 토큰이 더 이상 없을 때까지(즉, next_p < tokens.length 동안) ). #parse_expr_recursively AST 노드를 반환하거나 전혀 반환하지 않을 수 있습니다. 예를 들어 AST에서 종결자를 나타낼 필요가 없음을 기억하십시오. 루프의 현재 반복에서 노드가 빌드된 경우 @ast에 추가합니다. 계속하기 전에. #parse_expr_recursively @next_p도 이동 중입니다. 특정 구성의 시작을 표시하는 토큰을 찾으면 현재 구문 분석 중인 것을 완전히 나타내는 노드를 마침내 빌드할 수 있을 때까지 여러 번 진행해야 하기 때문입니다. if를 나타내는 노드를 구축하기 위해 얼마나 많은 토큰을 소비해야 하는지 상상해 보십시오. .

module Stoffle
  class Parser
    attr_accessor :tokens, :ast, :errors

    # ...

    def initialize(tokens)
      @tokens = tokens
      @ast = AST::Program.new
      @next_p = 0
      @errors = []
    end

    def parse
      while pending_tokens?
        consume

        node = parse_expr_recursively
        ast << node if node != nil
      end
    end

    # ...
  end
end

위의 스니펫에서 처음으로 파서 구현의 일부인 여러 유형의 AST 노드 중 하나가 제공되었습니다. 아래에 AST::Program의 전체 소스 코드가 있습니다. 노드 유형. 짐작하시겠지만 이것은 전체 프로그램을 나타내는 트리의 루트입니다. 가장 흥미로운 부분을 자세히 살펴보겠습니다.

• Stoffle 프로그램은 @expressions로 구성됩니다.; #children입니다. AST::Program 노드;
• 다시 보게 되겠지만 모든 노드 유형은 #==를 구현합니다. 방법. 결과적으로 두 개의 간단한 노드와 전체 프로그램을 쉽게 비교할 수 있습니다! 두 개의 프로그램(또는 두 개의 복잡한 노드)을 비교할 때, 그들의 평등은 모든 자식의 평등, 모든 자식의 모든 자식의 평등 등에 의해 결정됩니다. #==에서 사용하는 이 간단하면서도 강력한 전략 구현을 테스트하는 데 매우 유용합니다.

class Stoffle::AST::Program
  attr_accessor :expressions

  def initialize
    @expressions = []
  end

  def <<(expr)
    expressions << expr
  end

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

  def children
    expressions
  end
end

표현식 대 명령문

일부 언어에서는 많은 구문이 값을 생성하지 않습니다. 조건부는 전형적인 예입니다. 이를 문이라고 합니다. . 그러나 다른 구문은 값으로 평가됩니다(예:함수 호출). 이를 표현식이라고 합니다. . 그러나 다른 언어에서는 모든 것이 표현식이며 값을 생성합니다. Ruby는 이러한 접근 방식의 한 예입니다. 예를 들어, 다음 스니펫을 IRB에 입력하여 메서드 정의가 평가하는 값을 알아보세요.

irb(main):001:0> def two; 2; end

IRB를 시작하고 싶지 않다면 소식을 전하겠습니다. Ruby에서 메소드 정의 표현식 기호(메소드 이름)로 평가됩니다. 아시다시피 Stoffle은 Ruby에서 많은 영감을 얻었습니다. 그래서 우리의 작은 장난감 언어에서는 모든 것이 표현이기도 합니다.

이러한 정의는 실용적인 목적에는 충분하지만 실제로 합의가 이루어지지 않았으며 다른 곳에서 진술과 표현이라는 용어가 다르게 정의되는 것을 볼 수 있습니다.

더 깊이 파고들기:#parse_expr_recursively 구현 시작

위의 스니펫에서 방금 보았듯이 #parse_expr_recursively 잠재적으로 새로운 AST 노드를 구축하기 위해 호출되는 메서드입니다. #parse_expr_recursively 구문 분석 프로세스에서 다른 더 작은 방법을 많이 사용하지만 이것이 우리 구문 분석기의 실제 엔진이라고 조용히 말할 수 있습니다. 그리 길지는 않지만 이 방법은 소화하기가 더 어렵습니다. 그러므로 우리는 그것을 두 부분으로 나눌 것입니다. 게시물의 이 섹션에서는 Stoffle 프로그래밍 언어의 일부 간단한 부분을 구문 분석할 만큼 이미 강력한 초기 세그먼트부터 시작하겠습니다. 복습으로 단일 변수 바인딩 표현식으로 구성된 간단한 프로그램을 구문 분석하는 데 필요한 단계를 거치고 있음을 기억하십시오.

출처

my_var = 1

토큰(렉서의 출력, 파서의 입력)

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

처리해야 하는 토큰을 살펴보고 렉서 출력이 다른 유사한 간단한 표현식에 대해 어떻게 될지 상상한 후에 토큰 유형을 특정 구문 분석 방법과 연결하는 것이 좋은 생각인 것 같습니다.

def parse_expr_recursively
  parsing_function = determine_parsing_function
  if parsing_function.nil?
    unrecognized_token_error
    return
  end
  send(parsing_function)
end

#parse_expr_recursively의 초기 구현에서 , 그것이 바로 우리가 하는 일입니다. 상당히 있을 것이기 때문에 처리해야 하는 다양한 토큰 유형의 경우 이 의사 결정 프로세스를 별도의 메서드로 추출하는 것이 좋습니다. -#determine_parsing_function , 잠시 후에 보게 될 것입니다.

완료되면 인식하지 못하는 토큰이 없어야 하지만 보호 차원에서 구문 분석 기능이 현재 토큰과 연결되어 있는지 확인합니다. 그렇지 않은 경우 인스턴스 변수 @errors에 오류를 추가합니다. , 구문 분석 중에 발생한 모든 문제를 보유합니다. 여기에서 자세히 다루지는 않겠지만, 궁금한 점이 있으면 GitHub에서 파서의 전체 구현을 확인할 수 있습니다.

#determine_parsing_function 호출할 구문 분석 방법의 이름을 나타내는 기호를 반환합니다. Ruby의 send를 사용합니다. 즉석에서 적절한 메서드를 호출합니다.

파싱 방법 결정 및 변수 바인딩 파싱

다음으로 #determine_parsing_function을 살펴보겠습니다. Stoffle의 다른 구성을 구문 분석하기 위해 특정 메서드를 호출하는 이 초기 메커니즘을 이해합니다. #determine_parsing_function 이진 연산자를 제외한 모든 항목(예:키워드 및 단항 연산자)에 사용됩니다. 나중에 이항 연산자의 경우에 사용되는 기술을 살펴보겠습니다. 지금은 #determine_parsing_function을 확인해 보겠습니다. :

def determine_parsing_function
  if [:return, :identifier, :number, :string, :true, :false, :nil, :fn,
      :if, :while].include?(current.type)
    "parse_#{current.type}".to_sym
  elsif current.type == :'('
    :parse_grouped_expr
  elsif [:"\n", :eof].include?(current.type)
    :parse_terminator
  elsif UNARY_OPERATORS.include?(current.type)
    :parse_unary_operator
  end
end

앞서 설명했듯이 #current 가상입니다. 현재 처리 중인 토큰에 대한 포인터입니다. #determine_parsing_function 구현 매우 간단합니다. 현재 토큰(특히 유형 ) 호출할 적절한 메서드를 나타내는 기호를 반환합니다.

변수 바인딩(my_var = 1 ), 그래서 우리가 처리하는 토큰 유형은 [:identifier, :'=', :number]입니다. . 현재 토큰 유형은 :identifier입니다. , 그래서 #determine_parsing_function :parse_identifier를 반환합니다. , 당신이 짐작할 수 있듯이. 다음 단계인 #parse_identifier를 살펴보겠습니다. 방법:

def parse_identifier
  lookahead.type == :'=' ? parse_var_binding : AST::Identifier.new(current.lexeme)
end

여기에서 기본적으로 다른 모든 구문 분석 메서드가 수행하는 작업에 대한 매우 간단한 표현이 있습니다. #parse_identifier에서 - 그리고 다른 구문 분석 방법에서 - 우리는 토큰을 확인하여 우리가 기대하는 구조가 실제로 존재하는지 여부를 결정합니다. 식별자가 있다는 것을 알고 있지만 다음 토큰 유형이 :'='인 경우에 해당하는 변수 바인딩을 처리하는지 여부를 결정하기 위해 다음 토큰을 살펴봐야 합니다. , 또는 식별자 자체가 있거나 더 복잡한 표현식에 참여하는 경우. 예를 들어, 변수에 저장된 값을 조작하는 산술 표현식을 상상해 보십시오.

:'='가 있으므로 다음은 #parse_var_binding입니다. 호출됩니다:

def parse_var_binding
  identifier = AST::Identifier.new(current.lexeme)
  consume(2)

  AST::VarBinding.new(identifier, parse_expr_recursively)
end

여기에서 현재 처리 중인 식별자를 나타내는 새 AST 노드를 만드는 것으로 시작합니다. AST::Identifier의 생성자 식별자 토큰의 어휘를 예상합니다(즉, 문자 시퀀스, 문자열 "my_var" 우리의 경우), 그래서 그것이 우리가 그것에 공급하는 것입니다. 그런 다음 처리 중인 토큰 스트림에서 두 지점을 진행하여 :number 유형의 토큰을 만듭니다. 다음 분석 대상. [:identifier, :'=', :number]를 다루고 있음을 기억하십시오. .

마지막으로 변수 바인딩을 나타내는 AST 노드를 빌드하고 반환합니다. AST::VarBinding의 생성자 식별자 AST 노드(바인딩 표현식의 왼쪽)와 유효한 표현식(오른쪽)의 두 가지 매개변수가 필요합니다. 여기서 주목해야 할 한 가지 중요한 사항이 있습니다. 변수 바인딩 표현식의 오른쪽을 생성하기 위해 #parse_expr_recursively를 호출합니다. 다시 . 이것은 처음에는 조금 이상하게 느껴질 수 있지만 변수는 우리 예의 경우와 같이 단순한 숫자뿐만 아니라 매우 복잡한 표현식에 바인딩될 수 있음을 명심하십시오. 파싱 ​​전략을 한 단어로 정의하자면 재귀적입니다. . 이제 #parse_expr_recursively 이름이 있습니다.

이 섹션을 마치기 전에 AST::Identifier 및 AST::VarBinding . 먼저 AST::Identifier :

class Stoffle::AST::Identifier < Stoffle::AST::Expression
  attr_accessor :name

  def initialize(name)
    @name = name
  end

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

  def children
    []
  end
end

여기에 멋진 것은 없습니다. 노드가 변수의 이름을 저장하고 자식이 없다는 점을 언급할 가치가 있습니다.

이제 AST::VarBinding :

class Stoffle::AST::VarBinding < Stoffle::AST::Expression
  attr_accessor :left, :right

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

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

  def children
    [left, right]
  end
end

왼쪽은 AST::Identifier입니다. 마디. 오른쪽은 식별자가 바인딩된 표현식을 나타내는 거의 모든 가능한 노드 유형입니다. #children 변수 바인딩은 @left에 있는 AST 노드입니다. 및 @right .

소스에서 AST로의 두 번째 예

#parse_expr_recursively의 현재 구현 은(는) 이전 섹션에서 본 것처럼 이미 몇 가지 간단한 표현식을 구문 분석할 수 있습니다. 이 섹션에서는 이진 및 논리 연산자와 같은 더 복잡한 엔터티도 구문 분석할 수 있도록 구현을 완료합니다. 여기에서 우리는 파서가 함수를 정의하는 프로그램을 어떻게 처리하는지 단계별로 탐구할 것입니다. 다음은 렉서에서 생성된 토큰의 단순화된 표현인 소스와 첫 번째 섹션에서와 같이 프로그램을 나타내기 위해 생성할 AST의 시각적 표현입니다.

출처

fn double: num
  num * 2
end

토큰(렉서의 출력, 파서의 입력)

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

파서 출력의 시각적 표현(추상 구문 트리)

계속 진행하기 전에 한 걸음 뒤로 물러나서 연산자 우선 순위 규칙에 대해 이야기해 보겠습니다. 이는 수학적 규칙을 기반으로 합니다. 수학에서 그것들은 단지 관례일 뿐이며 실제로 우리가 익숙한 연산자 우선 순위를 초래하는 근본적인 것은 없습니다. 또한 이러한 규칙을 통해 표현식을 평가하기 위한 올바른 순서를 결정할 수 있으며 이 경우에는 먼저 구문 분석할 수 있습니다. 각 연산자의 우선 순위를 정의하기 위해 단순히 맵(예:Hash ) 토큰 유형 및 정수. 숫자가 높을수록 운영자가 먼저 처리되어야 함을 의미합니다. :

# We define these precedence rules at the top of Stoffle::Parser.
module Stoffle
  class Parser
    # ...

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

    LOWEST_PRECEDENCE = 0
    PREFIX_PRECEDENCE = 7
    OPERATOR_PRECEDENCE = {
      or:   1,
      and:  2,
      '==': 3,
      '!=': 3,
      '>':  4,
      '<':  4,
      '>=': 4,
      '<=': 4,
      '+':  5,
      '-':  5,
      '*':  6,
      '/':  6,
      '(':  8
    }.freeze

    # ...
  end
end

#parse_expr_recursively에 사용된 기술 컴퓨터 과학자 Vaughan Pratt가 1973년 논문 "Top Down Operator Precedence"에서 발표한 유명한 파서 알고리즘을 기반으로 합니다. 보시다시피 알고리즘은 매우 간단하지만 완전히 이해하기는 조금 어렵습니다. 약간 마법 같은 느낌이라고 할 수 있습니다. 이 기술의 작동 방식을 직관적으로 이해하기 위해 이 게시물에서 할 일은 위에서 언급한 Stoffle 스니펫을 구문 분석할 때 일어나는 일을 단계별로 살펴보는 것입니다. 따라서 더 이상 고민하지 않고 다음은 #parse_expr_recursively의 완성된 버전입니다. :

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

#parse_expr_recursively 이제 매개변수인 precedence를 허용합니다. . 메서드의 주어진 호출에서 고려되는 우선 순위 "수준"을 나타냅니다. 또한 메서드의 첫 번째 부분은 거의 동일합니다. 그런 다음 – 이 첫 번째 부분에서 표현식을 작성할 수 있다면 – 방법의 새로운 부분이 나옵니다. 다음 토큰은 종결자가 아니지만(즉, 줄 바꿈 또는 파일의 끝) 우선 순위(precedence param)이 다음 토큰의 우선 순위보다 낮으면 잠재적으로 토큰 스트림을 계속 사용할 수 있습니다.

while 내부를 살펴보기 전에 , 두 번째 조건(precedence < nxt_precedence ). 다음 토큰의 우선 순위가 더 높으면 방금 작성한 표현식(expr 지역 변수)는 아마도 아직 구축되지 않은 노드의 자식일 것입니다(우리는 추상 구문 tree인 AST를 구축하고 있음을 기억하십시오. ). Stoffle 스니펫의 구문 분석을 진행하기 전에 간단한 산술 표현식의 구문 분석을 살펴보겠습니다. 2 + 2 . 이 표현식을 구문 분석할 때 메서드의 첫 번째 부분은 AST::Number를 빌드합니다. 첫 번째 2를 나타내는 노드 expr에 저장 . 그런 다음 while 다음 토큰(:'+' )는 기본 우선 순위보다 높습니다. 그런 다음 AST::Number를 전달하여 호출된 합계를 처리하는 구문 분석 메서드가 있습니다. 노드 및 이진 연산자를 나타내는 노드 수신(AST::BinaryOperator ). 마지막으로 덮어쓰기 expr에 저장된 값 , 첫 번째 2를 나타내는 노드 2 + 2에서 , 이 새 노드는 더하기 연산자를 나타냅니다. 결국 이 알고리즘을 통해 노드를 재배열할 수 있었습니다.; 우리는 AST::Number 빌드로 시작했습니다. 노드를 생성하고 AST::BinaryOperator의 자식 중 하나로 트리에서 더 깊은 노드가 되었습니다. 노드.

함수 정의를 단계별로 구문 분석

#parse_expr_recursively에 대한 전반적인 설명을 살펴보았습니다. , 간단한 함수 정의로 돌아가 보겠습니다.

fn double: num
  num * 2
end

이 스니펫을 구문 분석할 때 파서 실행에 대한 간략한 설명을 살펴보는 것조차 지루하게 느껴질 수 있지만(그리고 실제로 그럴 수도 있습니다!), #parse_expr_recursively 및 특정 비트의 구문 분석(함수 정의 및 곱 연산자). 먼저 처리할 토큰 유형은 다음과 같습니다(아래는 @tokens.map(&:type)에 대한 출력입니다. , 렉서가 방금 본 스니펫 토큰화를 마친 후 파서 내부):

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

아래 표는 위의 토큰을 구문 분석할 때 가장 중요한 메서드가 호출되는 순서를 보여줍니다. 이것은 단순화라는 점을 명심하십시오. 파서 실행의 모든 ​​정확한 단계를 실제로 이해하려면 Byebug와 같은 Ruby 디버거를 사용하고 프로그램이 실행될 때 한 줄씩 진행하는 것이 좋습니다. <블록 인용>

현미경 분석기

Stoffle 소스에서 사용할 수 있는 이 정확한 스니펫을 사용하는 테스트가 있습니다. spec/lib/stoffle/parser_spec.rb에서 찾을 수 있습니다. complex_program_ok_2.sfe라는 스니펫을 사용하는 테스트입니다. .

파서 실행을 단계별로 탐색하려면 소스를 편집하고 byebug에 대한 호출을 추가할 수 있습니다. Parser#parse 시작 부분 , RSpec으로 앞서 언급한 테스트만 실행한 다음 Byebug의 step을 사용하세요. 프로그램을 한 번에 한 줄씩 진행하는 명령입니다.

GitHub에서 프로젝트의 README 파일을 방문하여 Byebug의 작동 방식과 사용 가능한 모든 명령에 대한 자세한 정보를 확인하세요.

이제 어떤 메서드가 호출되는지와 순서에 대한 일반적인 개념이 있으므로 아직 보지 못한 몇 가지 구문 분석 메서드를 더 자세히 살펴보겠습니다.

#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 우리가 유효한 구문을 가지고 있는지 확인하기 위해 토큰의 구조를 확인하고자 할 때 매우 유용하며 많은 파서 메소드에서 사용됩니다. 그렇게 한 후 현재 토큰은 :identifier 유형입니다. (우리는 'double'을 처리하고 있습니다. , 함수 이름), AST::Identifier를 빌드합니다. 함수 정의(AST::FunctionDefinition)를 나타내는 노드를 생성하기 위해 생성자에 전달합니다. ). 여기서는 자세히 다루지 않겠지만 기본적으로 AST::FunctionDefinition 노드는 함수 이름, 잠재적으로 매개변수 배열 및 함수 본문을 예상합니다.

#parse_function_definition의 다음 단계 식별자 뒤의 다음 토큰이 표현식 종결자(즉, 매개변수가 없는 함수)인지 콜론(즉, 하나 이상의 매개변수가 있는 함수)인지 확인하는 것입니다. double의 경우와 같이 매개변수가 있는 경우 우리가 정의하는 함수, 우리는 #parse_function_params를 호출합니다 그들을 파싱합니다. 잠시 후 이 방법을 확인하겠지만 먼저 계속해서 #parse_function_definition 탐색을 마치겠습니다. .

마지막 단계는 다른 구문 검사를 수행하여 함수 이름 + 매개변수 뒤에 종결자가 있는지 확인한 다음 #parse_block을 호출하여 함수 본문을 구문 분석하는 것입니다. . 마지막으로 fn을 반환합니다. , 완전히 빌드된 AST::FunctionDefinition 인스턴스, 함수 이름, 매개변수 및 본문으로 완료됩니다.

함수 매개변수 구문 분석의 핵심

이전 섹션에서 #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의 첫 번째 부분 간단합니다. 유효한 구문이 있는 경우(: 뒤에 하나 이상의 식별자가 있음) ), 포인터를 두 위치만큼 이동합니다.

[: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!