프로그래밍 「 추천 편」나만의 프로그래밍 언어 만들기 — 쉬운 방법

지난 한 달 동안 저는 취미로 제 자신의 프로그래밍 언어를 구현하기 위해 노력해 왔습니다. 이 프로젝트는 주로 Robert Nystrom의 Crafting Interpreters라는 책을 따라가는 것입니다. 제가 개발 작업해온 프로그래밍 언어는 Lox입니다. Robert Nystrom이 설계하고 구현했으며 이 책은 기본적으로 자신의 언어를 만드는 단계에 대한 단계별 가이드입니다. 이 언어에 대한 통역사를 직접 작성하면서 많은 것을 따라가는 것이 즐거웠고 많은 것을 배웠습니다!

Lox는 함수형 프로그래밍과 객체 지향 프로그래밍 패러다임을 모두 지원하는 동적 유형 프로그래밍 언어입니다. 이 책은 이 프로그래밍 언어에 대한 두 가지 구현(하나는 Java로 작성됨, 다른 하나는 C)을 다룹니다. Java 인터프리터는 매우 간단하고 간단한 구현으로, Lox 코드를 거의 사용하고 JVM을 사용하여 실행합니다. 이런 식으로 구현하는 것은 매우 비효율적이며 언어를 매우 느리게 만듭니다. 이 Java 인터프리터는 제가 작업해온 인터프리터이며 기사의 내용입니다. 그러나 C 인터프리터는 좀 더 복잡합니다. Lox 코드를 바이트 코드로 변환하고 가상 머신에서 실행하므로 성능이 크게 향상됩니다.

이미지 크레딧 : Robert Nystrom — 통역사 제작

 

언어의 맛

언어의 구문은 이해하기 매우 쉽습니다. 변수 선언은 var 키워드를 사용하고, 함수 선언은 fun 키워드를 사용하고, 클래스 선언은 class 키워드를 사용하는 C 스타일 언어입니다. 아래는 Lox 코드의 모습입니다.

class Pixel {
   init(red, blue, green, alpha) {
      this.red = red;
      this.blue = blue;
      this.green = green;
      this.alpha = alpha;
   }

   incrRed() {
      if (this.red < 255) {
         this.red = this.red + 1;
      }
   }

   incrBlue() {
      if (this.blue < 255) {
         this.blue = this.blue + 1;
      }
   }

   incrGreen() {
    if (this.green < 255) {
     this.green = this.green + 1;
    }
  }
}

fun incrNTimes(pixel, n, color) {                         // probably the worst possible way to modify color values
    for (var i = 0; i < n; i++) {                         // it just gets worse
        if (color == "red") pixel.red = pixel.red + 1;
        if (color == "green") pixel.green = pixel.green + 1;
        if (color == "blue") pixel.blue = pixel.blue + 1;
    }
}

var pixel = Pixel(25, 50, 75);
incrNTimes(pixel, 75, "red");
incrNTimes(pixel, 50, "green");
incrNTimes(pixel, 25, "blue");

print pixel;

 

문법

언어 구현을 시작하기 전에 언어 구문에 대한 공식적인 정의를 갖는 것이 중요합니다. 이러한 구문은 문법에서 정확하고 간결하게 표현 될 수 있습니다. 언어 문법은 언어 구문의 컨텍스트에서 유효한 언어의 알파벳에서 문자열을 형성하는 방법을 설명합니다. 문법은 문자열의 의미나 주어진 맥락에서 문자열로 무엇을 할 수 있는지 설명하지 않으므로 종종 문맥 없는 문법이라고 합니다. 다음은 Lox's Grammar 전체입니다(실제로 작은 언어입니다).

program        → declaration* EOF ;

declaration    →  funDecl | varDecl | statement | classDecl ;

varDecl        → "var" IDENTIFIER ( "=" expression )? ";" ;

statement      → exprStmt
                 | printStmt
                 | block
                 | ifStmt 
                 | whileStmt
                 | returnStmt  ;

block          → "{" declaration* "}" ;

ifStmt         → "if" "(" expression ")" statement
                     ( "else" statement )?

whileStmt      → "while" "(" expression ")" stmt ; 

funDecl        →  "fun" function ;
function       →  IDENTIFIER "(" parameters? ")" block ;
parameters     →  IDENTIFIER ( ',' IDENTIFIER )* ;

returnStmt     → "return" expression? ";" ;

exprStmt       → expression ";" ;
printStmt      → "print" expression ";" ;
expression     →  assignment ;
assignment     →  IDENTIFIER "=" assignment | logic_or ;
logic_or       →  logic_and ( "or" logic_and )* ;
logic_and      →  equality ( "and" equality )* ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" ) unary )* ;
unary          → ( "!" | "-" ) unary | call ;
call           → primary ( "(" arguments? ")" )* ;
arguments      → expression ( "," expression )* ;
primary        → "true" | "false" | "nil"
                 | NUMBER | STRING
                 | "(" expression ")"
                 | IDENTIFIER ;

Lox 프로그램은 문법 규칙을 준수해야하며 문법에서 벗어난 곳에서는 구문 오류가보고됩니다. Lox 프로그램은 일련의 "선언" 뒤에 EOF(End Of File) 문자가 오는 것으로 처리됩니다. 모든 선언은 varDecl, funDecl, classDecl 또는 statement 형식일 수 있습니다. 같은 방식으로 사용자 프로그램의 각 부분은 기본에 도달할 때까지 더 작고 간단한 표현으로 나뉩니다. 문법에서 이러한 규칙은 터미널이라고도 합니다. 위에서 언급한 각 규칙을 프로덕션이라고 합니다. 이러한 문법 규칙이 작성되는 방식도 언어의 우선 순위와 유사합니다.

 

언어 구현

스캐너

통역사의 첫 번째 단계는 스캔 또는 어휘 분석입니다. 스캐너는 사용자 코드를 입력으로 사용하고 일련의 문자를 토큰으로 연결하려고 합니다. 토큰은 소스 코드의 기본 구성 요소입니다. 토큰은 var, fun 및 class와 같은 키워드 형식일 수 있습니다. 변수 이름, 숫자, 문자열, 부울 또는 '{', '(', '.'와 같은 단일 문자일 수 있습니다. 이러한 토큰을 식별하는 동안 스캐너는 나중에 사용자 코드에서 구문 오류를 식별하는 데 도움이 될 수 있는 이러한 각 토큰의 줄 번호와 시작점도 추적합니다.

AST(Abstract Syntax Tree) 표현

AST(Abstract Syntax Tree)는 텍스트의 구문 구조를 트리로 표현한 것입니다. 언어의 재귀적 특성을 감안할 때 명령문, 표현식, 연산자가 모두 임의의 깊이로 서로 중첩될 수 있는 경우 트리는 문법을 나타내는 가장 간단한 방법입니다. 이름에서 알 수 있듯이 AST는 모든 세부 사항(추상)을 캡슐화하는 것이 아니라 구조 정보만 캡슐화합니다. 방정식을 고려하십시오

x = a * (b + c) / 2

AST에서 이것은 다음과 같이 표현됩니다.

추상 구문 트리 표현

구문 트리를 구현하는 동안 방문자 패턴이라는 흥미로운 디자인 패턴을 발견했습니다. 방문자 패턴은 트리 표현의 근본적인 문제에서 발생합니다. 인터프리터는 발생하는 각 유형의 표현식을 처리하기 위해 다른 코드 청크를 선택해야 합니다. 트리를 표현하는 동안 각 유형의 표현식은 자체 클래스를 가지므로 인터프리터가 특정 클래스의 트리 노드를 수신할 때 무엇을 해야 하는지 알 수 있는 논리적인 방법은 무엇을 해야 하는지 알기 전에 표현식의 유형을 확인할 수 있는 긴 유형 테스트 목록을 갖는 것입니다. 인터프리터 패턴(Interpreter Pattern)이라는 디자인 패턴을 사용하여 이 문제를 해결할 수 있지만 확장성이 떨어집니다.

파서

Java 인터프리터는 구문 분석기를 빌드하는 가장 간단한 방법인 재귀 하강 구문 분석기를 구현합니다. 단순함에도 불구하고 재귀 하강 파서는 빠르고 강력하며 오류 처리를 지원할 수 있습니다. GCC, V8 및 기타 여러 프로덕션 언어 구현은 재귀 하강을 사용합니다. 문법의 규칙을 코드로 문자 그대로 번역한 것으로, 각 규칙이 함수가 됩니다.

파서는 두 가지 작업을 가지고 있습니다 - 유효한 토큰 시퀀스가 주어지면 구문 트리를 생성하고, 유효하지 않은 토큰 시퀀스가 주어지면 오류를 감지하고 사용자에게 알립니다. 파서의 경우 잘못된 코드도 유효한 입력이므로 강력하고 던져진 모든 것을 처리할 수 있는지 확인하는 것이 중요합니다. 파서는 빨라야 합니다. 최신 IDE에서 코드는 거의 새 문자가 입력될 때마다 실시간으로 재구문 분석됩니다. 또한 파서는 오류가 발생한 후에도 구문 분석을 계속해야 합니다. 한 번에 하나의 오류를보고하는 것은 사용자가 모든 단일 오류를 수정 한 후 다시 컴파일해야하므로 나쁜 디자인입니다. Java 구문 분석기가 구현하는 오류 복구의 종류를 패닉 모드 오류 복구라고 합니다. 여기서 파서는 오류가 발생할 때마다 패닉 모드라는 상태로 전환되며, 여기서 전달되는 현재 토큰 시퀀스에 문제가 있음을 알 수 있습니다. 구문 분석을 다시 시작하기 전에 파서는 동기화라는 프로세스를 거쳐야 하며, 여기서 토큰이 다시 이해되기 시작하는 다음 지점을 찾으려고 합니다.

코드가 파서에서 나올 때쯤이면 완전히 일련의 구문 트리로 표현됩니다. 각 문은 트리에 자체 노드를 가지며 표현식으로 구성됩니다.

해결 프로그램

해석기는 인터프리터가 사용자 코드 평가를 시작하기 전에 AST의 두 번째 패스를 수행하는 Java 인터프리터의 구성 요소입니다. 확인자의 역할은 각 변수가 속한 범위를 올바르게 식별하는 것입니다. 범위 지정이 처리되는 방식은 각 코드 블록에 고유한 새 범위가 있다는 것입니다. 최상위 수준에는 전역 범위가 있습니다. 새로 생성된 모든 범위에는 외부 범위에 대한 참조가 있습니다. 변수, 함수 또는 클래스를 해결해야 할 때마다 인터프리터는 현재 범위를 보고 참조를 찾을 수 있습니다. 참조가 현재 범위에 없으면 바깥쪽 범위를 찾을 수 있습니다. 이 조회는 전역 범위까지 계속되며, 참조를 찾을 수 없는 경우 오류를 보고할 수 있습니다.

통역사

인터프리터는 컴퓨터가 사용자가 소스 코드가 원하는 작업을 수행하도록 하는 역할을 합니다. Java 구현은 트리 워크 인터프리터로 구성됩니다. 인터프리터는 사용자의 코드를 가져와 기계어로 직접 컴파일하거나, 다른 고급 언어로 번역하거나, 바이트코드 형식으로 변환하여 가상 머신에서 실행할 수 있습니다. 나무 산책 통역사는 통역사를 구현하는 가장 간단하고 직접적인 접근 방식입니다. 말 그대로 구문 트리의 각 노드를 살펴보고 평가합니다. 구문 트리의 나뭇잎은 기본 표현식입니다. number, string, true, false 및 nil 형식입니다. Lox의 숫자는 기본적으로 Java의 Double 데이터 유형으로 표시되며 문자열은 Java 문자열에 직접 매핑됩니다. 참 값과 거짓 값의 경우도 마찬가지입니다. Lox는 키워드 nil을 사용하여 Java에서 null 값을 나타냅니다. Lox는 동적으로 입력되는 언어이기 때문에 런타임까지 특정 요소가 어떤 종류의 값을 나타내는지 알 수 있는 방법이 없습니다. 구현은 또한 이를 반영하고 Java의 instanceof 메소드를 사용하여 런타임에 각 Lox 객체의 유형을 결정합니다.