Github의 전체 소스
Stoffle 프로그래밍 언어의 완전한 구현은 GitHub에서 사용할 수 있습니다. 버그를 발견하거나 질문이 있는 경우 언제든지 문제를 열어주세요.
이 블로그 게시물에서 우리는 완전히 Ruby로 구축된 장난감 프로그래밍 언어인 Stoffle용 인터프리터 구현을 시작할 것입니다. 이 시리즈의 첫 번째 부분에서 이 프로젝트에 대한 자세한 내용을 읽을 수 있습니다.
우리가 만들 인터프리터는 일반적으로 tree-walk 인터프리터라고 합니다. 이 시리즈의 이전 게시물에서는 토큰의 평면 시퀀스를 트리 데이터 구조(추상 구문 트리 또는 줄여서 AST)로 변환하는 파서를 구축했습니다. 당신이 상상할 수 있듯이, 우리의 인터프리터는 우리의 파서에 의해 생성된 AST를 거쳐 Stoffle 프로그램에 생명을 불어넣는 일을 합니다. 저는 이 마지막 단계가 이 언어 구현 여정에서 가장 흥미진진한 단계라고 생각합니다. 인터프리터를 만들 때 마침내 모든 것이 딸깍 소리를 내며 실제로 실행되는 Stoffle 프로그램을 볼 수 있습니다!
인터프리터의 구현을 두 부분으로 보여주고 설명하겠습니다. 이 첫 번째 부분에서는 변수, 조건문, 단항 및 이항 연산자, 데이터 유형, 콘솔로 인쇄 등의 기본 사항을 알아보겠습니다. 인터프리터 구현에 대한 두 번째이자 마지막 게시물을 위해 더 많은 내용(함수 정의, 함수 호출, 루프 등)을 예약하고 있습니다.
렉서 및 파서 요약
인터프리터 구현을 시작하기 전에 이 시리즈의 이전 게시물에서 수행한 작업을 빠르게 상기해 보겠습니다. 먼저 원시 소스 코드를 토큰으로 변환하는 렉서를 구축했습니다. 그런 다음 토큰을 트리 구조(AST)로 모핑하는 구성 요소인 파서를 구현했습니다. 요약하자면, 지금까지 관찰한 변형은 다음과 같습니다.
상태 0:소스
my_var = 1
상태 1:Lexer가 원시 소스 코드를 토큰으로 변환
[:identifier, :'=', :number]
상태 2:파서는 토큰을 추상 구문 트리로 변환
걷기의 모든 것
이제 AST가 있으므로 이 구조를 안내하는 코드를 작성해야 합니다. AST의 각 노드가 설명하는 내용에 생명을 불어넣을 수 있는 Ruby 코드를 작성해야 합니다. 예를 들어 변수 바인딩을 설명하는 노드가 있는 경우 우리의 작업은 변수 바인딩 표현식의 오른쪽 결과를 어떻게든 저장할 수 있는 Ruby 코드를 작성하고 이 저장 공간을 (및 를 통해 접근 가능) 변수에 주어진 이름.
이 시리즈의 이전 부분에서 했던 것처럼 예제 프로그램을 처리하는 데 관련된 모든 중요한 코드 라인을 살펴봄으로써 구현을 탐색할 것입니다. 해석해야 하는 Stoffle 코드는 다음과 같습니다.
num = -2
if num > 0
println("The number is greater than zero.")
else
println("The number is less than or equal to zero.")
end
다음은 동일한 프로그램에 대해 생성된 AST입니다.
우리 걷기의 첫걸음
이 시리즈의 마지막 게시물에서 기억할 수 있듯이 Stoffle AST는 항상 루트로 AST::Program 마디. 이 루트에는 일반적으로 여러 자식이 있습니다. 그들 중 일부는 얕을 것입니다(단순한 변수 할당을 위해 생성된 AST를 생각하십시오). 다른 자식은 아주 깊은 하위 트리의 루트가 될 수 있습니다(본문 내부에 많은 줄이 있는 루프를 생각해 보세요). 다음은 인터프리터에 전달된 AST를 살펴보는 데 필요한 Ruby 코드입니다.
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
새로운 Interpreter가 인스턴스화됩니다. 처음부터 두 개의 인스턴스 변수를 만듭니다. @output 및 @env . 전자의 책임은 우리 프로그램이 출력한 모든 것을 시간 순서대로 저장하는 것입니다. 이 정보를 가까이에 두는 것은 자동화된 테스트를 작성하거나 디버깅할 때 매우 유용합니다. @env의 책임 조금 다릅니다. 우리는 그것을 "환경"에 대한 참조로 명명했습니다. 이름에서 알 수 있듯이 그 기능은 실행 중인 프로그램의 상태를 유지하는 것입니다. 그 기능 중 하나는 식별자(예:변수 이름)와 현재 값 간의 바인딩을 구현하는 것입니다.
#interpret_nodes 메소드는 루트 노드(AST::Program ). 그런 다음 #interpret_node를 호출합니다. 각 개별 노드에 대해.
#interpret_node 간단하지만 그럼에도 불구하고 흥미롭습니다. 여기에서 현재 사용 중인 노드 유형을 처리하기 위한 적절한 메서드를 호출하기 위해 약간의 Ruby 메타프로그래밍을 사용합니다. 예를 들어 AST::VarBinding의 경우 노드, #interpret_var_binding 메소드가 호출되는 메소드입니다.
항상 우리는 변수에 대해 이야기해야 합니다
우리가 진행 중인 예제 프로그램의 AST에서 해석해야 하는 첫 번째 노드는 AST::VarBinding입니다. . @left AST::Identifier입니다. 및 해당 @right AST::UnaryOperator입니다. . 변수 바인딩 해석을 담당하는 메서드를 살펴보겠습니다.
def interpret_var_binding(var_binding)
env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
end
보시다시피 매우 간단합니다. @env에 키-값 쌍을 추가(또는 덮어쓰기)합니다. 해시.
키는 변수의 이름입니다(#var_name_as_str var_binding.left.name과 동일한 도우미 메서드입니다. ). 현재 모든 변수는 전역 변수입니다. 다음 게시물에서 범위 지정을 다룰 것입니다.
값은 할당의 오른쪽에 있는 표현식을 해석한 결과입니다. 이를 위해 #interpret_node를 사용합니다. 다시. AST::UnaryOperator가 있으므로 오른쪽에서 호출되는 다음 메서드는 #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
Stoffle에서 지원하는 단항 연산자의 의미(- 및 ! )는 Ruby와 동일합니다. 결과적으로 구현이 더 간단할 수 없습니다. Ruby의 - 피연산자를 해석한 결과에 연산자. 일반적인 용의자, #interpret_node , 여기에 다시 나타납니다. 우리 프로그램의 AST에서 기억할 수 있듯이 -의 피연산자는 AST::Number입니다. (숫자 2 ). 이것은 우리의 다음 목적지가 #interpret_number임을 의미합니다. :
def interpret_number(number)
number.value
end
#interpret_number 구현 케이크 조각입니다. Ruby float를 숫자 리터럴의 표현으로 채택하기로 한 결정(이것은 렉서에서 발생합니다!)은 여기에서 효과가 있습니다. @value AST::Number 노드는 이미 원하는 내부 숫자 표현을 보유하고 있으므로 그냥 검색합니다.
이것으로 AST::Program의 첫 번째 직계 자식 해석을 마칩니다. . 이제 프로그램 해석을 끝내기 위해 더 많은 털이 많은 자식인 AST::Conditional 유형의 노드를 처리해야 합니다. .
이용약관이 적용될 수 있음
#interpret_nodes로 돌아가기 , 우리의 가장 친한 친구 #interpret_node AST::Program의 다음 직계 자식을 해석하기 위해 다시 호출됩니다. .
def interpret_nodes(nodes)
last_value = nil
nodes.each do |node|
last_value = interpret_node(node)
end
last_value
end
AST::Conditional 해석을 담당하는 메소드 #interpret_conditional입니다. . 그러나 살펴보기 전에 AST::Conditional 구현을 검토하여 기억을 새로고침해 보겠습니다. 자체:
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
알겠습니다. @condition 참 또는 거짓이 될 표현을 보유합니다. @when_true @condition 진실하고 @when_false (ELSE 절)은 @condition의 경우 실행할 블록을 보유합니다. 허위 사실이 밝혀졌습니다.
이제 #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
Stoffle의 진실성은 Ruby와 동일합니다. 즉, Stoffle에서는 nil만 및 false 거짓이다. 조건에 대한 다른 모든 입력은 사실입니다.
먼저 conditional.condition이 보유한 표현식을 해석하여 조건을 평가합니다. . 어떤 노드를 다루고 있는지 알아보기 위해 프로그램의 AST를 다시 살펴보겠습니다.
AST::BinaryOperator (> num > 0에 사용됨 ). 좋습니다. 다시 같은 경로입니다. 첫 번째 #interpret_node , #interpret_binary_operator를 호출합니다. 이번에:
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
논리 연산자(and 및 or )는 이진 연산자로 간주될 수 있으므로 여기에서도 처리합니다. 그들의 의미는 Ruby의 &&와 동일하기 때문에 및 || , 구현은 위에서 볼 수 있듯이 단순합니다.
다음은 우리가 가장 관심 있는 방법의 섹션입니다. 이 섹션은 다른 모든 이진 연산자(> 포함)를 처리합니다. ). 여기에서 우리는 Ruby의 역동성을 우리에게 유리하게 활용하고 매우 간결한 솔루션을 제시할 수 있습니다. Ruby에서 이항 연산자는 작업에 참여하는 개체의 메서드로 사용할 수 있습니다.
-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)
이진 연산자의 자세한 구현
보시다시피 이진 연산자 구현은 매우 간결합니다. Ruby가 그렇게 동적인 언어가 아니거나 Ruby와 Stoffle 간에 연산자의 의미가 달랐다면 이러한 방식으로 솔루션을 코딩할 수 없었을 것입니다.
언어 디자이너/구현자와 같은 위치에 있는 자신을 발견한 경우에는 항상 간단한(그러나 그렇게 우아하지는 않은) 솔루션인 스위치 구성을 사용하는 것으로 대체할 수 있습니다. 우리의 경우 구현은 다음과 같습니다.
# ... inside #interpret_binary_operator ...
case binary_op.operator
when :'+'
interpret_node(binary_op.left) + interpret_node(binary_op.right)
# ... other operators
end
#interpret_conditional로 돌아가기 전에 , 간과된 것이 없는지 확인하기 위해 빠르게 우회합시다. 우리가 해석하고 있는 프로그램을 기억한다면 num 변수가 비교에 사용됩니다(이항 연산자 > 사용). ) 우리는 방금 함께 탐험했습니다. 왼쪽 피연산자(즉, num에 저장된 값)를 검색하는 방법 변수) 그 비교? 이를 담당하는 메소드는 #interpret_identifier입니다. , 구현이 간편합니다.
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
이제 #interpret_conditional로 돌아갑니다. . 우리의 작은 프로그램의 경우 조건은 Ruby false로 평가되었습니다. 값. 이 값을 사용하여 조건부 구조의 IF 또는 ELSE 분기를 실행해야 하는지 여부를 결정합니다. 관련 코드 블록이 conditional.when_false에 저장되어 있는 ELSE 분기 해석을 진행합니다. . 여기에 AST::Block이 있습니다. , 이는 AST(AST::Program)의 루트 노드와 매우 유사합니다. ). 마찬가지로 블록에는 해석해야 하는 표현식이 많이 있습니다. 이를 위해 #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
처리해야 하는 다음 AST 노드는 AST::FunctionCall입니다. . 함수 호출 해석을 담당하는 메서드는 #interpret_function_call입니다. :
def interpret_function_call(fn_call)
return if println(fn_call)
end
이 기사의 시작 부분에서 논의한 것처럼 함수 정의와 함수 호출은 이 시리즈의 다음 포스트에서 다룰 것입니다. 따라서 우리는 특별한 경우의 함수 호출만을 구현하고 있습니다. 작은 장난감 언어로 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
AST::FunctionCall의 첫 번째이자 유일한 인수 AST::String입니다. , #interpret_string에 의해 처리됩니다. :
def interpret_string(string)
string.value
end
#interpret_string에서 , 우리는 #interpret_number와 똑같은 대소문자를 가집니다. . AST::String 이미 사용할 준비가 된 Ruby 문자열 값을 보유하고 있으므로 검색하기만 하면 됩니다.
이제 #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
result에 함수 인수(Ruby 문자열로 변환)를 저장한 후 , 완료해야 할 두 단계가 더 있습니다. 먼저 콘솔에 인쇄할 내용을 @output에 저장합니다. . 이전에 설명했듯이 여기의 아이디어는 인쇄된 내용(및 순서)을 쉽게 검사할 수 있다는 것입니다. 이것을 가지고 있으면 인터프리터를 디버깅하거나 테스트할 때 우리의 삶이 더 쉬워집니다. 마지막으로 콘솔에 출력하는 것을 구현하기 위해 Ruby의 puts을 사용합니다. .
실행 문제
이제 Stoffle의 기본을 구현하는 데 필요한 모든 것을 살펴보았으므로 인터프리터가 작동하는 모습을 보기 위해 매우 기본적인 실행 파일을 만들어 보겠습니다.
#!/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)
팁: 어디에서나 Stoffle의 인터프리터를 사용하려면 실행 파일을 PATH에 추가하는 것을 잊지 마십시오.
드디어 프로그램을 실행할 시간입니다. 모든 것이 제대로 작동하면 "숫자가 0보다 작거나 같음" 문자열이 콘솔에 인쇄된 것을 볼 수 있습니다. 이것은 우리가 인터프리터를 실행할 때 일어나는 일입니다:
팁: 인터프리터가 설치되어 있으면 num을 변경해 보십시오. 0보다 큰 숫자를 보유하도록 샘플 프로그램에서 변수. 예상대로 이제 IF 분기가 실행되고 "숫자가 0보다 큼" 문자열이 출력됩니다.
마무리
이번 포스팅에서 스토플의 인터프리터의 시작을 알아보았습니다. 변수, 조건문, 단항 및 이진 연산자, 데이터 유형, 콘솔로 인쇄 등 언어의 기본 중 일부를 처리할 수 있도록 인터프리터를 충분히 구현했습니다. 인터프리터에 대한 다음 및 마지막 부분에서는 작은 장난감 언어가 설계된 대로 작동하는 데 필요한 나머지 부분(변수 범위 지정, 함수 정의, 함수 호출 및 루프)을 다룰 것입니다. 글을 재미있게 읽으셨기를 바랍니다(저는 확실히 재미있게 썼습니다!). 그리고 곧 다음 시리즈의 글에서 뵙겠습니다!