간단한 스택 기반 프로그래밍 언어 구현 방법

Question

스택 기반 프로그래밍 언어를 구현하여 컴퓨터 프로그래밍 지식을 확장하는 데 관심이 있습니다. "pushint 1"과 같은 함수를 사용하여 스택의 맨 위에 값 1을 가진 정수를 전달하고 "L01: jump L01:"과 같은 레이블을 통해 흐름 제어를 수행 할 계획이므로 어디서부터 시작할지 조언을 구합니다.

지금까지 나는 (IDEOne에 연결하려고했지만) 내 언어가 작동하도록하려는 C# 구현을 만들었지 만 매우 복잡하고 최적화가 필요합니다. 입력을 XML로 변환 한 다음 구문 분석합니다. 내 목표는 더 낮은 수준의 언어 (아마도 C/C++)로 가고 있지만 내 문제는 다양한 데이터 유형을 보유 할 수 있고 고정 크기가 아닌 스택을 구현하는 것입니다.

결국 배열 및 함수도 구현하고 싶습니다. 또한, 나는 더 나은 Lexer를 가질 필요가 있다고 생각하며, 파싱 트리가 그러한 단순한 언어에 좋은 아이디어인지 궁금해합니다.

아무런 조언이나 비판을 환영하며, 아직 프로그래밍에 익숙하지 않은 것으로 간주하십시오. (최근 AP CompSci I을 완료했습니다.) 또한 오픈 소스 스택 기반 언어에 대한 링크도 환영합니다. 여기

내가 컴파일/시도하고 해석하고자하는 기본 프로그램입니다 (여기서 [this is a comment]) :

[Hello World!] 
pushchar '\n' 
pushstring "Hello World!" 
print 
[Count to 5 and then count down!] 
pushint  1 
setlocal 0 
L01: 
pushchar '\n' 
getlocal 0 
print   [print x + '\n'] 
getlocal 0 
increment 
setlocal 0 [x = x + 1] 
pushint  5 
getlocal 0 
lessthan  [x < 5] 
iftrue  L01 
L02: 
pushchar '\n' 
getlocal 0 
print   [print x + '\n'] 
getlocal 0 
decrement 
setlocal 0 [x = x - 1] 
pushint  0 
getlocal 0 
greaterthan  [x > 0] 
iftrue  L02 

는 예상 출력은 다음과 같습니다

Hello World! 
1 
2 
3 
4 
5 
4 
3 
2 
1 

Answer 1

스택 기반 언어 등 Factor의 구문은 다음과 같습니다.

2 3 + 5 - print 

이것은 equ 다음 C 스타일 코드와 동일합니다.

print(2 + 3 - 5); 

스택 기반 언어를 사용할 때의 장점은 구현하기 쉽다는 것입니다. 또한 언어가 reverse polish notation을 사용하는 경우 대부분의 스택 기반 언어에서와 마찬가지로 사용자 언어의 front end에 필요한 것은 렉서입니다. 토큰 스트림을 디코딩하는 유일한 방법이 있기 때문에 토큰을 구문 트리로 구문 분석 할 필요가 없습니다.

생성하려는 것은 스택 기반 프로그래밍 언어가 아니고 스택 기반 virtual machine입니다. 응용 프로그램 가상 컴퓨터는 stack based 또는 register based 일 수 있습니다. 예를 들어, Java Virtual Machine은 스택 기반입니다. Java bytecode (가상 컴퓨터 용 바이트 코드)을 실행합니다. 그러나이 바이트 코드로 컴파일되는 프로그래밍 언어 (예 : Java, Erlang, Groovy 등)는 스택 기반이 아닙니다.

만들려는 것은 스택 기반의 가상 머신의 어셈블리 수준 언어와 같습니다. 스택 기반 가상 컴퓨터는 레지스터 기반 가상 컴퓨터를 쉽게 구현할 수 있습니다. 다시 말하지만, 필요한 것은 모두 flex과 같은 렉서 (lexer)입니다. 여기 lexer라는 라이브러리를 사용하여 자바 스크립트의 작은 예입니다

var program = "[print(2 + 3)]"; 
 
program += "\n push 2"; 
 
program += "\n push 3"; 
 
program += "\n add"; 
 
program += "\n print"; 
 

 
lexer.setInput(program); 
 

 
var token; 
 
var stack = []; 
 
var push = false; 
 

 
while (token = lexer.lex()) { 
 
    switch (token) { 
 
    case "NUMBER": 
 
     if (push) stack.push(lexer.yytext); 
 
     else alert("Unexpected number."); 
 
     break; 
 
    case "ADD": 
 
     if (push) alert("Expected number."); 
 
     else stack.push(stack.pop() + stack.pop()); 
 
     break; 
 
    case "PRINT": 
 
     if (push) alert("Expected number."); 
 
     else alert(stack.pop()); 
 
     break; 
 
    } 
 

 
    push = token === "PUSH"; 
 
}

<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script> 
 
<script> 
 
var lexer = new Lexer; 
 

 
lexer.addRule(/\s+/, function() { 
 
    // matched whitespace - discard it 
 
}); 
 

 
lexer.addRule(/\[.*\]/, function() { 
 
    // matched a comment - discard it 
 
}); 
 

 
lexer.addRule(/\d+/, function (lexeme) { 
 
    this.yytext = parseInt(lexeme); 
 
    return "NUMBER"; 
 
}); 
 

 
lexer.addRule(/push/, function() { 
 
    return "PUSH"; 
 
}); 
 

 
lexer.addRule(/add/, function() { 
 
    return "ADD"; 
 
}); 
 

 
lexer.addRule(/print/, function() { 
 
    return "PRINT"; 
 
}); 
 
</script>

정말 간단합니다. 프로그램을 바이올린하고 필요에 맞게 수정할 수 있습니다.행운을 빌어 요.

Answer 2

나는 "MetaII"에 관한 논문을 실제로 계몽 할 것이라고 생각합니다. 10 개의 짧지만 마음이 굽은 페이지에서 푸시 다운 스택 컴파일러 시스템과 컴파일러를 정의하는 방법을 보여줍니다. 이 대답을 참조하십시오 : https://stackoverflow.com/a/1005680/120163 이것을 이해하면 푸시 다운 스택 해석기 작성이 쉽습니다.