컴파일러 만들기를 읽고
-
책을 읽으며 중요하다고 생각되는 내용들을 정리하였다.
-
책이 C++ 코드로 되어있는데, 이를 자바로 변환하였다.
정리한 Chapter
- 1장 시작하며
- 2장 어휘 분석
- 3장 구문 분석
- 4장 인터프리터
- 5장 코드 생성
- 6장 가상 머신
시작하며
컴파일러
-
컴파일러는 코드를 입력받아 코드를 출력하는 프로그램
-
input으로 입력받는 코드 = 소스코드
-
output으로 출력하는 코드 = 목적 코드
-
즉, 소스 코드를 목적 코드로 번역하는 과정을 컴파일이라 한다.
컴파일은 세 단계로 나뉜다.
인터프리터의 경우, 소스 코드를 바로 실행한다.
인터프리터 역시, 다음과 같이 세 단계로 구성되어 있다.
어휘 분석
-
어휘 분석은 컴파일 과정의 첫 번째 단계
-
프로그래밍 언어로 작성한 소스 코드의 문자열을 분석한다.
- 소스코드 문자열은 어휘들의 나열이다.
-
소스 코드 문자열은 키워드, 식별자, 연산자, 구분자, 숫자 리터럴, 문자열 리터럴로 구성된다.
-
키워드는
for,iffunction과 같이 프로그래밍 언어에서 특별하게 취급하는 어휘 -
식별자는 변수나 함수의 이름처럼 사용자가 정의하는 어휘
-
구분자는 괄호나 세미콜론과 같이 어휘들을 구분 짓기 위한 기호
-
-
어휘는 종류에 따라 서로 다른 문자로 시작한다.
package scanner;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import static java.util.function.Function.identity;
public enum Kind {
UnKnown("#unknown"), EndOfToken("#EndOfToken"),
NullLiteral("null"),
TrueLiteral("true"), FalseLiteral("false"),
NumberLiteral("#Number"), StringLiteral("#String"),
Identifier("#identifier"),
Function("function"), Return("return"),
Variable("var"),
For("for"), Break("break"), Continue("continue"),
If("if"), Elif("elif"), Else("else"),
Print("print"), PrintLine("printLine"),
LogicalAnd("and"), LogicalOr("or"),
Assignment("="),
Add("+"), Subtract("-"),
Multiply("*"), Divide("/"), Modulo("%"),
Equal("=="), NotEqual("!="),
LessThan("<"), GreaterThan(">"),
LessOrEqual("<="), GreaterOrEqual(">="),
Comma(","), Colon(":"), Semicolon(";"),
LeftParen("("), RightParen(")"),
LeftBrace("{"), RightBrace("}"),
LeftBracket("["), RightBracket("]"),
;
private final String string;
Kind(String string) {
this.string = string;
}
public String getString() {
return string;
}
private static final Map<String, Kind> stringToKind = Collections.unmodifiableMap(
Stream.of(values())
.collect(Collectors.toMap(Kind::getString, identity()))
);
public static Kind toKind(String string) {
if (stringToKind.containsKey(string)) {
return stringToKind.get(string);
}
return Kind.UnKnown;
}
}
// 소스 코드에서 사용되는 어휘들을 정의
- 소스 코드에서 사용되는 어휘들을 정의한다.
stringToKind맵은 토큰으로 이루어져 있다.
- 토큰 = 어휘의 문자열 + 종류
toKind(String string)
- 문자열을 입력받아 어휘의 종류로 반환한다.
package parser;
public class Token {
Kind kind = Kind.UnKnown;
String string;
public Token(Kind kind) {
this.kind = kind;
}
public Token(Kind kind, String string) {
this.kind = kind;
this.string = string;
}
@Override
public String toString() {
return "Token{" +
"kind=" + kind +
", string='" + string + '\'' +
'}';
}
}
Token클래스
- 토큰을 정의한다.
- 어휘의 종류와 문자열로 이루어져 있다.
package scanner;
public enum CharType {
Unknown, // 사용할 수 없는 문자
WhiteSpace, // 공백, 탭, 개행
NumberLiteral, // 숫자 리터럴
StringLiteral, // 문자열 리터럴
IdentifierAndKeyword, // 식별자, 키워드
OperatorAndPunctuator, // 연산자, 구분자
}
CharType클래스
- 문자 타입을 크게 6가지로 나눈다.
package scanner;
import parser.Kind;
import parser.Token;
import java.util.ArrayList;
import java.util.List;
public class Scanner {
private static int index;
public List<Token> scan(String sourceCode) { // 주어진 소스코드의 어휘 분석
List<Token> result = new ArrayList<>();
sourceCode += '\0';
index = 0;
while (sourceCode.charAt(index) != '\0') {
char ch = sourceCode.charAt(index);
switch (getCharType(ch)) {
case WhiteSpace -> index += 1;
case NumberLiteral -> result.add(scanNumberLiteral(sourceCode));
case StringLiteral -> result.add(scanStringLiteral(sourceCode));
case IdentifierAndKeyword -> result.add(scanIdentifierAndKeyword(sourceCode));
case OperatorAndPunctuator -> result.add(scanOperatorAndPunctuator(sourceCode));
default -> throw new RuntimeException(ch + " 사용할 수 없는 문자입니다.");
}
}
result.add(new Token(Kind.EndOfToken));
return result;
}
private CharType getCharType(char ch) { // 문자열의 시작부분을 읽고, 종류를 판별하여 반환
if (' ' == ch || '\t' == ch || '\r' == ch || '\n' == ch) {
return CharType.WhiteSpace;
}
if ('0' <= ch && ch <= '9') {
return CharType.NumberLiteral;
}
if (ch == '\'') {
return CharType.StringLiteral;
}
if ('a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z') {
return CharType.IdentifierAndKeyword;
}
if (33 <= ch && ch <= 47 && ch != '\'' ||
58 <= ch && ch <= 64 ||
91 <= ch && ch <= 96 ||
123 <= ch && ch <= 126) {
return CharType.OperatorAndPunctuator;
}
return CharType.Unknown;
}
private Token scanNumberLiteral(String sourceCode) { // 숫자 리터럴을 분석하여 토큰으로 반환
String string = "";
while (isCharType(sourceCode.charAt(index), CharType.NumberLiteral)) {
string += sourceCode.charAt(index);
index += 1;
}
if (sourceCode.charAt(index) == '.') {
string += sourceCode.charAt(index);
index += 1;
while (isCharType(sourceCode.charAt(index), CharType.NumberLiteral)) {
string += sourceCode.charAt(index);
index += 1;
}
}
return new Token(Kind.NumberLiteral, string);
}
private Token scanStringLiteral(String sourceCode) { // 문자 리터럴을 분석하여 토큰으로 반환
String string = "";
index += 1;
while (isCharType(sourceCode.charAt(index), CharType.StringLiteral)) {
string += sourceCode.charAt(index);
index += 1;
}
if (sourceCode.charAt(index) != '\'') {
throw new RuntimeException("문자열의 종료 문자가 없습니다.");
}
index += 1;
return new Token(Kind.StringLiteral, string);
}
private Token scanIdentifierAndKeyword(String sourceCode) { // 식별자와 키워드를 분석하여 토큰으로 반환
String string = "";
while (isCharType(sourceCode.charAt(index), CharType.IdentifierAndKeyword)) {
string += sourceCode.charAt(index);
index += 1;
}
Kind kind = Kind.toKind(string);
if (kind == Kind.UnKnown) {
kind = Kind.Identifier;
}
return new Token(kind, string);
}
private Token scanOperatorAndPunctuator(String sourceCode) { // 연산자와 구분자를 분석하여 토큰으로 반환
StringBuilder sb = new StringBuilder();
while (isCharType(sourceCode.charAt(index), CharType.OperatorAndPunctuator)) {
sb.append(sourceCode.charAt(index));
index += 1;
}
while ((sb.length() > 0) && Kind.toKind(sb.toString()) == Kind.UnKnown) {
sb.deleteCharAt(sb.length() - 1);
index -= 1;
}
if (sb.isEmpty()) {
throw new RuntimeException(sourceCode.charAt(index) + " 사용할 수 없는 문자입니다.");
}
String string = sb.toString();
return new Token(Kind.toKind(string), string);
}
private boolean isCharType(char ch, CharType type) { // 문자열이 어디까지 연속되는지 판단
switch (type) {
case NumberLiteral -> {
return '0' <= ch && ch <= '9';
}
case StringLiteral -> {
return 32 <= ch && ch <= 126 && ch != '\'';
}
case IdentifierAndKeyword -> {
return '0' <= ch && ch <= '9' ||
'a' <= ch && ch <= 'z' ||
'A' <= ch && ch <= 'Z';
}
case OperatorAndPunctuator -> {
return 33 <= ch && ch <= 47 ||
58 <= ch && ch <= 64 ||
91 <= ch && ch <= 96 ||
123 <= ch && ch <= 126;
}
default -> {
return false;
}
}
}
}
Scanner클래스
- 주어진 소스코드의 어휘를 분석하여 토큰 리스트를 반환한다.
- 동작 원리
- 첫 문자를 확인하여 어휘의 타입을 결정하고 (
getCharType(ch))- 연속된 문자들이 해당 어휘의 타입에 속하는 지 연속해서 검증하고 (
isCharType(char ch, CharType type)- 연속된 문자들을 하나의 토큰으로 만들어서 반환한다. (
scanNumberLiteral,scanStringLiteral, ...)
private Token scanIdentifierAndKeyword(String sourceCode) { // 식별자와 키워드를 분석하여 토큰으로 반환
String string = "";
while (isCharType(sourceCode.charAt(index), CharType.IdentifierAndKeyword)) {
string += sourceCode.charAt(index);
index += 1;
}
Kind kind = Kind.toKind(string);
if (kind == Kind.UnKnown) {
kind = Kind.Identifier;
}
return new Token(kind, string);
}
scanIdentifierAndKeyword(String sourceCode)메서드
- 식별자와 키워드를 분석하여 토큰으로 반환하는 메서드
Kind kind = Kind.toKind(string);를 통해서 가져온 어휘의 종류가 이미 존재하는 종류라면, 시스템에서 정한키워드- 만약 존재하지 않는 종류라면, 사용자가 정한
식별자이다.
private Token scanOperatorAndPunctuator(String sourceCode) { // 연산자와 구분자를 분석하여 토큰으로 반환
StringBuilder sb = new StringBuilder();
while (isCharType(sourceCode.charAt(index), CharType.OperatorAndPunctuator)) {
sb.append(sourceCode.charAt(index));
index += 1;
}
while ((sb.length() > 0) && Kind.toKind(sb.toString()) == Kind.UnKnown) {
sb.deleteCharAt(sb.length() - 1);
index -= 1;
}
if (sb.isEmpty()) {
throw new RuntimeException(sourceCode.charAt(index) + " 사용할 수 없는 문자입니다.");
}
String string = sb.toString();
return new Token(Kind.toKind(string), string);
}
scanOperatorAndPunctuator(String sourceCode)메서드
- 연산자와 구분자를 분석하여 토큰으로 반환한다.
- 연산자나 구분자로 구분되는 문자면 모두
StringBuilder sb에 넣는다.- 이렇게 모인 문자열이 말이 안되는 문자열이면 뒷 문자부터 제거한다.
- 말이 되는 문자열이 될 때, 이를 토큰으로 만들어 반환한다.
소스 코드: https://github.com/ghkdgus29/crafting-compiler/tree/lexical-analysis
구문 분석
-
소스 코드의 구조를 분석하는 과정
- 분석 후, 소스 코드의 구조도를 구문 트리로 표현한다.
-
소스 코드의 구조는 문과 식으로 구성된다.
-
문은 복합문과 단일문으로 구분된다.
-
복합문:
for문과 같이 다른 문을 포함할 수 있는 문 -
단일문:
return과 같이 다른 문을 포함할 수 없는 문
-
-
문은 식을 포함하고, 식은 식을 포함한다.
- 곱셈식
1+2*3는1+2덧셈식과3으로 이루어져 있다.
- 곱셈식
-
노드 정의
- 구문 트리의 구성요소인 노드를 정의한다.
public interface Statement {
void print(int depth);
}
// 문
public interface Expression {
void print(int depth);
}
// 식
print(int depth)는 구문트리를 출력해보기 위한 함수이다.
Expression을 구현한 문은Break,Continue,ExpressionsStatement,For,Function,If,Print,Return,Variable이 있다.ExpressionsStatement를 제외한 나머지 코드는 깃허브로 대체
public class ExpressionStatement implements Statement{
private Expression expression;
public void setExpression(Expression expression) {
this.expression = expression;
}
@Override
public void print(int depth) {
indent(depth);
System.out.println("EXPRESSION:");
expression.print(depth + 1);
}
}
ExpressionStatement구현체
- 식을 임의로 소비시키기 위해 식을 감싸는 문 노드
- 식은 항상 결과값을 남긴다. ➔ 식의 결과값은 문의 목적에 따라 소비된다.
return 1 + 2;에 속한1 + 2식은 결과값3을 반환하고 소비된다.
- 그러나 어떠한 문에도 포함되지 않고, 사용되지 않는 식이 존재할 수 있다.
- ex) 반환값이 있는 함수를 호출했지만, 반환값은 사용하지 않는 경우
- 이 경우 소비되지 않는 결과값을 임의로 소비시키기 위해 식을 감싸는 문 노드를 정의한다.
Parser 클래스
- 앞서 어휘 분석의 결과물인 토큰 리스트를 입력으로 받아, 구문 분석을 수행하는 클래스
public class Parser {
private static int index;
public Program parse(List<Token> tokens) {
Program result = new Program();
index = 0;
while (tokens.get(index).getKind() != Kind.EndOfToken) {
switch (tokens.get(index).getKind()) {
case Function -> {
result.add(parseFunction(tokens));
}
default -> {
throw new RuntimeException(tokens.get(index) + " 잘못된 구문입니다.");
}
}
}
return result;
}
// ...
}
parse(List<Token> tokens)
- 토큰 리스트들을 토대로 함수들을 분석
- 함수들의 집합인
Program반환
private void skipCurrent(List<Token> tokens, Kind kind) {
if (tokens.get(index).getKind() != kind) {
throw new RuntimeException(kind + " 토큰이 필요합니다.");
}
index += 1;
}
skipCurrent(List<Token> tokens, Kind kind)
- 현재 인덱스의 어휘 검증 후, 인덱스를 1 증가
private boolean skipCurrentIf(List<Token> tokens, Kind kind) {
if (tokens.get(index).getKind() != kind) {
return false;
}
index += 1;
return true;
}
skipCurrentIf(List<Token> tokens, Kind kind)
- 현재 인덱스의 어휘가 입력받은
kind와 같다면
- 인덱스 1 증가
true반환kind와 다르다면
false반환
private Function parseFunction(List<Token> tokens) {
Function result = new Function();
skipCurrent(tokens, Kind.Function);
result.setName(tokens.get(index).getString()); // 식별자 세팅
skipCurrent(tokens, Kind.Identifier);
skipCurrent(tokens, Kind.LeftParen);
if (tokens.get(index).getKind() != Kind.RightParen) {
do {
result.add(tokens.get(index).getString()); // 파라미터 세팅
skipCurrent(tokens, Kind.Identifier);
} while (skipCurrentIf(tokens, Kind.Comma));
}
skipCurrent(tokens, Kind.RightParen);
skipCurrent(tokens, Kind.LeftBrace);
result.setBlock(parseBlock(tokens)); // 함수의 블록 세팅
skipCurrent(tokens, Kind.RightBrace);
return result;
}
parseFunction(List<Token> tokens)
- 함수 분석 메서드
private List<Statement> parseBlock(List<Token> tokens) {
List<Statement> result = new ArrayList<>();
while (tokens.get(index).getKind() != Kind.RightBrace) {
switch (tokens.get(index).getKind()) {
default -> result.add(parseExpressionStatement(tokens));
case Variable -> result.add(parseVariable(tokens));
case For -> result.add(parseFor(tokens));
case If -> result.add(parseIf(tokens));
case Print, PrintLine -> result.add(parsePrint(tokens));
case Return -> result.add(parseReturn(tokens));
case Break -> result.add(parseBreak(tokens));
case Continue -> result.add(parseContinue(tokens));
case EndOfToken -> throw new RuntimeException(tokens.get(index) + " 잘못된 구문입니다.");
}
}
return result;
}
parseBlock(List<Token> tokens)
- 함수 블록 내의 식이나 문을 분석하는 메서드
parseXXX메서드를 통해 구문 분석을 수행
- 자세한 문 분석 코드는 깃허브 참고
private Expression parseExpression(List<Token> tokens) {
return parseAssignment(tokens);
}
parseExpression(List<Token> tokens)
- 식을 분석하는 코드
- 식은 연산자 우선 순위가 있다.
-
가장 우선순위가 낮은 연산자가 우선 분석되어야 한다.
- 가장 우선순위가 낮은 연산자를 분석하는 함수가 우선 호출된다.
-
가장 우선순위가 낮은 연산자가 구문트리의 상위에 위치해야 한다.
+연산 ➔*연산 ➔숫자 리터럴순으로 함수가 호출되어야 한다.
private Expression parseAssignment(List<Token> tokens) {
Expression result = parseOr(tokens); // 왼쪽 피연산자 식 먼저 분석
if (tokens.get(index).getKind() != Kind.Assignment) { // 만약 현재 식이 대입 연산자 식이 아닌 경우, 결과 그냥 반환
return result;
}
skipCurrent(tokens, Kind.Assignment);
if (result instanceof GetVariable getVariable) { // 일반 변수에 대입하는 경우
SetVariable setVariable = new SetVariable();
setVariable.setName(getVariable.getName());
setVariable.setValue(parseAssignment(tokens));
return setVariable;
}
if (result instanceof GetElement getElement) { // 특정 배열이나 맵의 원소에 대입하는 경우
SetElement setElement = new SetElement();
setElement.setSub(getElement.getSub());
setElement.setIndex(getElement.getIndex());
setElement.setValue(parseAssignment(tokens));
return setElement;
}
throw new RuntimeException("잘못된 대입 연산 식입니다.");
}
parseAssignment(List<Token> tokens)
- 대입 연산식을 분석한다.
- 대입 연산의 경우 우측 결합 연산자이다.
- 오른쪽 식을 먼저 계산 후, 왼쪽 식을 계산한다.
- 따라서 재귀함수 호출을 통해 구문트리가 오른쪽으로 자라도록 만들어준다.
private Expression parseOr(List<Token> tokens) {
Expression result = parseAnd(tokens);
while (skipCurrentIf(tokens, Kind.LogicalOr)) {
Or temp = new Or();
temp.setLhs(result);
temp.setRhs(parseAnd(tokens));
result = temp;
}
return result;
}
parseOr(List<Token> tokens)
or연산식을 분석한다.or연산의 경우 좌측 결합 연산자이다.
- 왼쪽 식을 먼저 계산 후, 오른쪽 식을 계산한다.
- 따라서 반복문을 통한 함수 호출을 통해 구문트리가 왼쪽으로 자라도록 만들어준다.
소스 코드: https://github.com/ghkdgus29/crafting-compiler/tree/syntax-analysis
인터프리터
-
소스 코드를 실행하는 프로그램
- 구문 트리를 순회하며 노드를 실행한다.
Datatype 클래스
-
동적으로 넘어오는 데이터 타입들을 정적으로 사용하기 위해 변환하는 클래스
- 책에서 만드는 언어는 동적 타입인데 반해, 자바는 정적 타입이기 때문에 필요하다.
-
두 가지 역할을 수행한다.
-
파라미터로 넘어오는 데이터 타입이 무슨 타입인지 검증:
isXXX(Object value) -
파라미터로 넘어오는 데이터 타입을 원하는 타입으로 변환:
toXXX(Object value)
-
public class Datatype {
public static Boolean isNull(Object value) {
return value == null;
}
public static Boolean isTrue(Object value) {
return isBoolean(value) && toBoolean(value);
}
public static Boolean isFalse(Object value) {
return isBoolean(value) && (toBoolean(value) == false);
}
public static Boolean isBoolean(Object value) {
return value instanceof Boolean;
}
public static Boolean toBoolean(Object value) {
return (Boolean) value;
}
public static Boolean isNumber(Object value) {
return value instanceof Double;
}
public static Double toNumber(Object value) {
return (Double) value;
}
public static Boolean isString(Object value) {
return value instanceof String;
}
public static String toString(Object value) {
return (String) value;
}
public static Boolean isArray(Object value) {
return value instanceof List;
}
public static List toArray(Object value) {
return (List) value;
}
// ...
}노드에 interpret() 메서드 추가
public interface Statement {
void print(int depth);
void interpret(); // 4장 인터프리터에서 사용하기 위한 메서드
}문의 경우, 실행 후 반환값이 없다.
public interface Expression {
void print(int depth);
Object interpret(); // 4장 인터프리터에서 사용하기 위한 메서드
}식의 경우, 실행 후 반환값이 있다.
Interpreter 클래스
-
엔트리 포인트 함수인
main()함수부터 실행한다. -
전역 변수, 지역 변수, 함수 테이블을 관리한다.
-
구문트리(
Program) 를 입력으로 받아 트리 내의 함수 노드들을 함수 테이블에 등록한다.
public class Interpreter {
private static final String ENTRY_POINT = "main";
public static Map<String, Object> global = new HashMap<>();
public static List<List<Map<String, Object>>> local = new ArrayList<>();
public static Map<String, Function> functionTable = new HashMap<>();
public void interpret(Program program) {
functionTable.clear();
global.clear();
local.clear();
for (Function node : program.getFunctions()) {
functionTable.put(node.getName(), node);
}
if (!functionTable.containsKey(ENTRY_POINT)) { // 만약 main 함수가 없으면 바로 종료
return;
}
local.add(new ArrayList<>()); // 함수 블록 (스택 프레임) 은 뒤로 차곡차곡 쌓인다.
local.get(local.size() - 1).add(0, new HashMap<>()); // for, if 와 같은 문 블록들은 함수 블록 내에서 맨 앞으로 쌓인다.
try {
functionTable.get(ENTRY_POINT).interpret(); // main 함수부터 시작
} catch (ReturnException | BreakException | ContinueException e) {}
local.remove(local.size() - 1);
}
}
local.add(new ArrayList<>())
- 함수 블록 (스택 프레임) 은 뒤로 차곡차곡 쌓인다.
local.get(local.size() - 1).add(0, new HashMap<>());
- 함수 블록 내의 문 블록 (
if,for) 들은 함수 블록 내에서 맨 앞으로 쌓인다.- 이후 지역 변수를 찾을 때 가장 겹겹이 쌓인 문 블록부터 순회를 시작한다.
- 맨 앞에서 부터 순회를 시작하면, 겹겹이 쌓인 문 블록부터 순회를 시작하는 것과 같다.
print 실행
Function문에interpret()구현
public class Function implements Statement {
private String name;
private List<String> parameters = new ArrayList<>();
private List<Statement> block;
// ...
@Override
public void interpret() {
for (Statement node : block) {
node.interpret();
}
}
}블록내의 모든 문들을 실행한다.
Print문에interpret()구현
public class Print implements Statement{
private boolean lineFeed = false;
private List<Expression> arguments = new ArrayList<>();
// ...
@Override
public void interpret() {
for (Expression node : arguments) {
Object value = node.interpret();
System.out.print(value);
}
if (lineFeed) {
System.out.println(); // 개행이 있는 경우
}
}
}식 인자들을 차례로 실행한 뒤, 결과값들을 차례로 출력한다.
StringLiteral식에interpret()구현
public class StringLiteral implements Expression {
private String value;
// ...
@Override
public Object interpret() {
return value;
}
}그냥 문자열 값을 반환한다.
- 실행결과
@DisplayName("문자열을 출력한다.")
@Test
void printString() {
// given
String sourceCode = """
function main(arg1, arg2) {
printLine 'Hello, World!';
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}Hello, World!
산술 논리 연산 실행
Arithmetic식에interpret()구현
public class Arithmetic implements Expression {
private Kind kind;
private Expression lhs;
private Expression rhs;
// ...
@Override
public Object interpret() {
Object lValue = lhs.interpret();
Object rValue = rhs.interpret();
if (kind == Kind.Add && isNumber(lValue) && isNumber(rValue)) {
return toNumber(lValue) + toNumber(rValue);
}
if (kind == Kind.Add && isString(lValue) && isString(rValue)) {
return Datatype.toString(lValue) + Datatype.toString(rValue);
}
if (kind == Kind.Subtract && isNumber(lValue) && isNumber(rValue)) {
return toNumber(lValue) - toNumber(rValue);
}
if (kind == Kind.Multiply && isNumber(lValue) && isNumber(rValue)) {
return toNumber(lValue) * toNumber(rValue);
}
if (kind == Kind.Divide && isNumber(lValue) && isNumber(rValue)) {
return toNumber(rValue) == 0 ? "INF" : toNumber(lValue) / toNumber(rValue);
}
if (kind == Kind.Modulo && isNumber(lValue) && isNumber(rValue)) {
return toNumber(rValue) == 0 ? "NaN" : toNumber(lValue) % toNumber(rValue);
}
throw new RuntimeException(lValue + " " + kind.getString() + " " + rValue + ": 잘못된 계산 식입니다.");
}
}연산자 (
kind) 에 해당하는 연산을 분기를 나눠 수행한 뒤, 결과값을 반환한다.
- 산술 연산 실행 결과
@DisplayName("산술연산을 수행한다.")
@Test
void calculateArithmetic() {
// given
String sourceCode = """
function main(arg1, arg2) {
printLine 1 * 2 + 3 * 4;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}14.0
Or식에interpret()구현
public class Or implements Expression {
private Expression lhs;
private Expression rhs;
// ...
@Override
public Object interpret() {
return isTrue(lhs.interpret()) ? true : rhs.interpret();
}
}왼쪽 식의 결과물이 참이면 오른쪽 식은 더 이상 실행하지 않는다.
And식에interpret()구현
public class And implements Expression {
private Expression lhs;
private Expression rhs;
// ...
@Override
public Object interpret() {
return isFalse(lhs.interpret()) ? false : rhs.interpret();
}
}왼쪽 식의 결과물이 거짓이면, 오른쪽 식은 더 이상 실행하지 않는다.
- 논리 연산 실행 결과
@DisplayName("논리연산을 수행한다.")
@Test
void calculateLogical() {
// given
String sourceCode = """
function main(arg1, arg2) {
printLine true or 'Hello, world!';
printLine false or 'Hello, world!';
printLine true and 'Hello, world!';
printLine false and 'Hello, world!';
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}true Hello, world! Hello, world! false
변수의 선언과 참조
Variable문에interpret()구현
public class Variable implements Statement{
private String name;
private Expression expression;
// ...
@Override
public void interpret() {
local.get(local.size() - 1).get(0).put(name, expression.interpret());
}
}함수 프레임의 맨 앞에 변수 맵을 삽입
GetVariable식에interpret()구현
public class GetVariable implements Expression {
private String name;
// ...
@Override
public Object interpret() {
for (Map<String, Object> variables : local.get(local.size() - 1)) { // 지역 변수에 이름이 존재한다면
if (variables.containsKey(name)) {
return variables.get(name);
}
}
if (global.containsKey(name)) { // 전역 변수에 이름이 존재한다면
return global.get(name);
}
if (functionTable.containsKey(name)) { // 함수 테이블에 이름이 존재한다면
return functionTable.get(name);
}
if (builtinFunctionTable.containsKey(name)) { // 내장 함수에 이름이 존재한다면
return builtinFunctionTable.get(name);
}
return null;
}
}
지역변수➔전역변수➔사용자 정의 함수➔내장 함수순으로 변수/참조명 탐색- 변수와 함수의 이름 공간을 구분하지 않는다.
- 일반적인 프로그래밍 언어는 변수와 함수의 이름 공간을 구분한다.
for (Map<String, Object> variables : local.get(local.size() - 1))
- 현재 함수 프레임의 겹겹이 쌓인 블록부터 지역변수를 탐색한다.
- 즉, 앞에서 부터 탐색한다.
SetVariable식에interpret()구현
public class SetVariable implements Expression {
private String name;
private Expression value;
// ...
@Override
public Object interpret() {
for (Map<String, Object> variables : local.get(local.size() - 1)) { // 지역 변수 테이블에 변수명이 존재한다면
if (variables.containsKey(name)) {
variables.put(name, value.interpret());
return value.interpret();
}
}
return global.put(name, value.interpret()); // 지역 변수 테이블에 변수명이 존재하지 않는다면, 전역 변수로 설정
}
var a = 15➔Variable문,var키워드 사용,a선언b = 15➔SetVariable식,var키워드 x
- 만약 한번도
b를 선언하지 않았다면b는 전역 변수
- 변수 선언 및 참조 실행 결과
@DisplayName("변수의 선언과 참조, 대입을 수행한다.")
@Test
void manageVariable() {
// given
String sourceCode = """
function main(arg1, arg2) {
global = 4;
var local = 13;
printLine 'global: ', global;
printLine 'local: ', local;
global = local = 7;
printLine 'global: ', global;
printLine 'local: ', local;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}global: 4.0 local: 13.0 global: 7.0 local: 7.0
for문 실행
For문에interpret()구현
public class For implements Statement {
private Variable variable;
private Expression condition;
private Expression expression;
private List<Statement> block;
// ...
@Override
public void interpret() {
local.get(local.size() - 1).add(0, new HashMap<>()); // 함수 프레임 내에 For문 지역 변수 블록 추가
variable.interpret();
while (true) {
Object result = condition.interpret();
if (!isTrue(result)) { // 탈출 조건
break;
}
try {
for (Statement node : block) { // 반복문 내의 블록 실행
node.interpret();
}
} catch (ContinueException ce) { // Continue 문을 만난 경우
} catch (BreakException be) { // Break 문을 만난 경우
break;
}
expression.interpret(); // 증감식 실행
}
local.get(local.size() - 1).remove(0); // For 문 지역 변수 블록 제거
}
}Continue,Break문에interpret()구현
public class Continue implements Statement {
// ...
@Override
public void interpret() {
throw new ContinueException();
}
}
public class Break implements Statement {
// ...
@Override
public void interpret() {
throw new BreakException();
}
}예외를 발생시킨다.
- 실행 결과
@DisplayName("반복문을 실행한다.")
@Test
void executeFor() {
// given
String sourceCode = """
function main(arg1, arg2) {
for i=0, i<3, i=i+1 {
printLine 'i: ', i;
}
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}i: 0.0 i: 1.0 i: 2.0
If 문 실행
If문에interpret()구현
public class If implements Statement {
private List<Expression> conditions = new ArrayList<>();
private List<List<Statement>> blocks = new ArrayList<>();
private List<Statement> elseBlock = new ArrayList<>();
// ...
@Override
public void interpret() {
for (int i = 0; i < conditions.size(); i++) {
Object result = conditions.get(i).interpret();
if (!isTrue(result)) { // 현재 조건문이 참이 아닌 경우, skip
continue;
}
local.get(local.size() - 1).add(0, new HashMap<>());
for (Statement node : blocks.get(i)) { // 조건문 블록 안의 문들 실행
node.interpret();
}
local.get(local.size() - 1).remove(0);
return;
}
if (elseBlock.isEmpty()) {
return;
}
local.get(local.size() - 1).add(0, new HashMap<>()); // else 조건에 걸리는 경우
for (Statement node : elseBlock) { // else 블록 안의 문들 실행
node.interpret();
}
local.get(local.size() - 1).remove(0);
}
}- 실행 결과
@DisplayName("조건문을 실행한다.")
@Test
void executeConditionStatement() {
// given
String sourceCode = """
function main(arg1, arg2) {
for i=0, i<6, i=i+1 {
if i == 1 {
printLine 'one';
} elif i == 2 {
printLine 'two';
} elif i == 3 {
printLine 'three';
} else {
printLine i;
}
}
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}0.0 one two three 4.0 5.0
함수 호출 실행
Call식에interpret()구현
public class Call implements Expression {
private Expression sub;
private List<Expression> arguments = new ArrayList<>();
// ...
@Override
public Object interpret() {
Object value = sub.interpret();
if (isBuiltinFunction(value)) { // 함수가 내장함수인지 체크
List<Object> parameters = new ArrayList<>();
for (int i = 0; i < arguments.size(); i++) {
parameters.add(arguments.get(i).interpret()); // 파라미터 세팅
}
return toBuiltinFunction(value).apply(parameters); // 내장함수 Map 에서 내장함수를 찾아, 파라미터를 넘겨주고 실행
}
if (!isFunction(value)) { // 존재하는 사용자 정의 함수가 아닌 경우
return null;
}
Map<String, Object> parameters = new HashMap<>();
for (int i = 0; i < arguments.size(); i++) {
String name = toFunction(value).getParameterOf(i); // 함수 노드로 만들고, 함수 노드의 파라미터명을 가져온다.
parameters.put(name, arguments.get(i).interpret()); // 파라미터 명과 식을 매핑하여 파라미터 세팅
}
local.add(new ArrayList<>()); // 함수 프레임을 생성
local.get(local.size() - 1).add(0, parameters); // 함수 프레임의 맨 앞에 파라미터(매개변수) Map 추가
try {
toFunction(value).interpret(); // 함수 실행
} catch (ReturnException re) {
local.remove(local.size() - 1); // 호출함수 프레임 제거
return re.getResult(); // 호출한 함수의 반환값
}
local.remove(local.size() - 1); // 호출함수 프레임 제거
return null;
}
}- 반환값, 매개변수가 없는 함수 호출 실행 결과
@DisplayName("반환값, 매개변수가 없는 함수 호출")
@Test
void call() {
// given
String sourceCode = """
function main() {
sayHo();
}
function sayHo() {
printLine 'Ho!';
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}Ho!
- 매개변수가 있는 함수 호출 실행 결과
@DisplayName("매개변수가 있는 함수 호출")
@Test
void callWithParameters() {
// given
String sourceCode = """
function main() {
add(1, 3);
}
function add(a, b) {
printLine a + b;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}4.0
- 매개변수와 반환값이 있는 함수 호출 실행 결과
@DisplayName("매개변수와 반환값이 있는 함수 호출")
@Test
void callWithParametersAndReturn() {
// given
String sourceCode = """
function main() {
var ans = add(3, 4);
printLine ans;
}
function add(a, b) {
return a * a + b * b;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}25.0
내장 함수 실행하기
builtinFunctionTable에 내장 함수들 정의하기
public class BuiltInFunctionTable {
public static Map<String, Function<List<Object>, Object>> builtinFunctionTable = initialize();
private static Map<String, Function<List<Object>, Object>> initialize() {
Map<String, Function<List<Object>, Object>> result = new HashMap<>();
result.put("length", params -> {
if (params.size() == 1 && isArray(params.get(0))) {
return toArray(params.get(0)).size();
}
if (params.size() == 1 && isMap(params.get(0))) {
return toMap(params.get(0)).size();
}
return 0.0;
});
result.put("push", params -> {
if (params.size() == 2 && isArray(params.get(0))) {
toArray(params.get(0)).add(params.get(1));
return params.get(0);
}
return null;
});
result.put("pop", params -> {
if (params.size() == 1 && isArray(params.get(0)) && toArray(params.get(0)).size() != 0) {
Object pop = toArray(params.get(0)).get(toArray(params.get(0)).size() - 1);
toArray(params.get(0)).remove(toArray(params.get(0)).size() - 1);
return pop;
}
return null;
});
result.put("erase", params -> {
if (params.size() == 2 && isMap(params.get(0)) && isString(params.get(1)) && toMap(params.get(0)).containsKey(Datatype.toString(params.get(1)))) {
Object erase = toMap(params.get(0)).get(Datatype.toString(params.get(1)));
toMap(params.get(0)).remove(Datatype.toString(params.get(1)));
return erase;
}
return null;
});
result.put("sqrt", params -> Math.sqrt(toNumber(params.get(0))));
return result;
}
}- 내장 함수 실행하기
@DisplayName("내장 함수 호출")
@Test
void callBuiltinFunction() {
// given
String sourceCode = """
function main() {
printLine sqrt(25);
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}5.0
배열, 맵 원소 참조 및 변경
ArrayLiteral식에interpret()구현
public class ArrayLiteral implements Expression {
private List<Expression> values = new ArrayList<>();
// ...
@Override
public Object interpret() {
ArrayList<Object> result = new ArrayList<>();
for (Expression node : values) {
result.add(node.interpret());
}
return result;
}
}MapLiteral식에interpret()구현
public class MapLiteral implements Expression {
private Map<String, Expression> values = new HashMap<>();
// ...
@Override
public Object interpret() {
HashMap<String, Object> result = new HashMap<>();
for (String key : values.keySet()) {
result.put(key, values.get(key).interpret());
}
return result;
}
}- 배열 리터럴, 맵 리터럴 출력 결과
@DisplayName("배열과 맵 리터럴 출력")
@Test
void printListAndMapLiteral() {
// given
String sourceCode = """
function main() {
var list = [1, 2, 3];
var map = {'a':1, 'b':2, 'c':3};
printLine list;
printLine map;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}[1.0, 2.0, 3.0] {a=1.0, b=2.0, c=3.0}
GetElement식에interpret()구현
public class GetElement implements Expression {
private Expression sub;
private Expression index;
// ...
@Override
public Object interpret() {
Object object = sub.interpret();
Object index = this.index.interpret();
if (isArray(object) && isNumber(index)) {
return getValueOfArray(object, index);
}
if (isMap(object) && isString(index)) {
return getValueOfMap(object, index);
}
return null;
}
}
getValueOfArray,getValueOfMap은Datatype클래스에 정의되어 있다.
- 주어진 인덱스에 해당하는 요소를 반환한다.
- 원소값 참조 실행결과
@DisplayName("배열과 맵의 원소값 참조")
@Test
void getElement() {
// given
String sourceCode = """
function main() {
var list = [1, 2, 3];
var map = {'a':1, 'b':2, 'c':3};
printLine list[2];
printLine map['a'];
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}3.0 1.0
SetElement식에interpret()구현
public class SetElement implements Expression {
private Expression sub;
private Expression index;
private Expression value;
// ...
@Override
public Object interpret() {
Object object = sub.interpret();
Object index = this.index.interpret();
Object value = this.value.interpret();
if (isArray(object) && isNumber(index)) {
return setValueOfArray(object, index, value);
}
if (isMap(object) && isString(index)) {
return setValueOfMap(object, index, value);
}
return null;
}
}
setValueOfArray,setValueOfMap은Datatype클래스에 정의되어 있다.
- 주어진 인덱스에 해당하는 요소를
value로 변경한다.
- 원소값 변경 실행결과
@DisplayName("배열과 맵의 원소값 변경")
@Test
void modifyElement() {
// given
String sourceCode = """
function main() {
var list = [1, 2, 3];
var map = {'a':1, 'b':2, 'c':3};
list[2] = 10;
map['a'] = 'abc';
printLine list[2];
printLine map['a'];
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when // then
interpreter.interpret(syntaxTree);
}10.0 abc
소스 코드: https://github.com/ghkdgus29/crafting-compiler/tree/interpreter
코드 생성
-
목적 코드를 생성하는 과정
-
소스 코드: 사람이 읽을수 있는 문자열 형태의 코드
-
목적 코드: 기계가 읽을 수 있는 바이너리 형태의 코드
-
-
인터프리터처럼 비선형 구조 (구문 트리) 를 순회하며 소스 코드를 실행하는 것은 느리다.
-
비선형 구조의 구문 트리를 선형 구조로 표현한다면 실행 속도를 높일 수 있다.
- 즉, 코드 생성은 비선형 구조의 구문 트리를 선형 구조로 표현하는 것
-
이 책에서는, 자바의 바이트코드처럼, 가상 머신을 대상으로 하는 목적 코드를 만든다.
- 기계에 종속적이지 않고, 독립적으로 동작한다.
Instruction Enum
- 목적코드에서 사용할 명령어들을 정의한다.
public enum Instruction {
Exit,
Call, Alloca, Return,
Jump, ConditionJump,
Print, PrintLine,
LogicalOr, LogicalAnd,
Add, Subtract,
Multiply, Divide, Modulo,
Equal, NotEqual,
LessThan, GreaterThan,
LessOrEqual, GreaterOrEqual,
Absolute, ReverseSign,
GetElement, SetElement,
GetGlobal, SetGlobal,
GetLocal, SetLocal,
PushNull, PushBoolean,
PushNumber, PushString,
PushArray, PushMap,
PopOperand,
}Code 클래스
- 명령어와 명령어가 필요로하는 연산자를 정의한다.
public class Code {
Instruction instruction;
Object operand;
public Code(Instruction instruction) {
this.instruction = instruction;
}
public Code(Instruction instruction, Object operand) {
this.instruction = instruction;
this.operand = operand;
}
public void setOperand(Object operand) {
this.operand = operand;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("%-15s", instruction));
if (operand instanceof Integer) {
sb.append("[" + operand + "]");
} else if (operand instanceof Boolean) {
sb.append(operand);
} else if (operand instanceof Double) {
sb.append(operand);
} else if (operand instanceof String) {
sb.append("\"" + operand + "\"");
}
return sb.toString();
}
}
toString()은 목적 코드를 출력해보기 위함이다.
Generator 클래스
-
구문 트리 (
Program)를 입력으로 받아 명령어 리스트 (List<Code>) 와 함수 테이블 (Map<String, Integer>) 을 튜플로 묶어 반환한다.- 목적 코드 = 명령어 리스트 + 함수 테이블
-
엔트리 포인트 함수인
main()함수부터 호출한다.
public class Generator {
public static List<Code> codeList = new ArrayList<>(); // 명령어 리스트
public static Map<String, Integer> functionTable = new HashMap<>(); // 함수 테이블
public static int localSize; // 지역 변수 크기
public static List<List<Integer>> continueStack = new ArrayList<>(); // Continue 명령어 실행 위치를 기록
public static List<List<Integer>> breakStack = new ArrayList<>(); // Break 명령어 실행 위치를 기록
private static List<Map<String, Integer>> symbolStack = new ArrayList<>(); // 함수 프레임 내의 위치한 모든 블록들의 지역 변수 위치(인덱스)를 나타낸다.
private static List<Integer> offsetStack = new ArrayList<>(); // 함수 프레임 내의 위치한 각각의 블록들에서 지역 변수를 저장할 수 있는 위치(블록내의 지역 변수의 개수)를 나타낸다.
public Pair<List<Code>, Map<String, Integer>> generate(Program program) {
codeList.clear();
functionTable.clear();
writeCode(Instruction.GetGlobal, "main");
writeCode(Instruction.Call, 0);
writeCode(Instruction.Exit);
for (Statement node : program.getFunctions()) { // Program 의 모든 함수들을 실행
node.generate();
}
return new Pair<>(codeList, functionTable);
}
public static int writeCode(Instruction instruction) { // 명령어 목록에 명령어를 생성하여 넣고, 해당 명령어의 위치 반환
codeList.add(new Code(instruction));
return codeList.size() - 1;
}
public static int writeCode(Instruction instruction, Object operand) { // 명령어 목록에 명령어와 연산자를 생성하여 넣고, 해당 명령어의 위치 반환
codeList.add(new Code(instruction, operand));
return codeList.size() - 1;
}
public static void patchAddress(int codeIndex) { // codeIndex에 위치한 명령어를 찾아서 해당 명령어의 연산자를, 명령어 목록 개수 + 1 위치를 가리키도록 설정
codeList.get(codeIndex).setOperand(codeList.size());
}
public static int getLocal(String name) { // symbolStack을 사용해 지역변수의 위치 반환
for (Map<String, Integer> symbolTable : symbolStack) {
if (symbolTable.containsKey(name)) {
return symbolTable.get(name);
}
}
return Integer.MAX_VALUE; // symbolStack에 존재하지 않는 경우, 전역변수이다.
}
public static void setLocal(String name) { // 지역 변수 설정
symbolStack.get(0).put(name, offsetStack.get(offsetStack.size() - 1)); // symbolStack 에 지역 변수 이름과 지역 변수 위치 (offsetStack 마지막 값) 를 설정
offsetStack.set(offsetStack.size() - 1, offsetStack.get(offsetStack.size() - 1) + 1); // offsetStack 의 현재 블록의 지역 변수 개수를 1 증가 시킨다.
localSize = Math.max(localSize, offsetStack.get(offsetStack.size() - 1)); // localSize 를 큰 값으로 갱신한다.
}
public static void initBlock() { // 블록 초기화, 지역 변수 개수와 offsetStack 을 초기화하고
localSize = 0; // symbolStack 에 현재 블록의 지역 변수 공간 추가
offsetStack.add(0);
symbolStack.add(0, new HashMap<>());
}
public static void pushBlock() { // 블록 추가, 상위 블록의 offsetStack 값을 가져와 새로운 요소로 추가한다.
symbolStack.add(0, new HashMap<>());
offsetStack.add(offsetStack.get(offsetStack.size() - 1));
}
public static void popBlock() { // 블록 제거, 현재 블록의 offsetStack 요소를 제거한다.
offsetStack.remove(offsetStack.size() - 1);
symbolStack.remove(0);
}
public static void patchOperand(int codeIndex, int operand) { // codeIndex에 위치한 명령어를 찾아서 해당 명령어의 연산자를, operand 로 설정
codeList.get(codeIndex).setOperand(operand);
}
}print문 목적 코드 생성
Function문에generate()구현
public class Function implements Statement {
private String name;
private List<String> parameters = new ArrayList<>();
private List<Statement> block;
// ...
@Override
public void generate() {
functionTable.put(name, codeList.size()); // 함수 테이블에 함수의 이름과 명령어가 시작하는 위치 저장
int temp = writeCode(Instruction.Alloca); // 지역 변수 저장을 위한 공간 할당 명령어 생성, 아직 몇 개의 변수 공간이 필요한지는 모른다.
initBlock(); // 함수 블록 초기화
for (String name : parameters) {
setLocal(name); // 파라미터들을 지역 변수로 설정
}
for (Statement node : block) {
node.generate(); // 함수 내의 문들 실행
}
popBlock(); // 함수 블록 제거
patchOperand(temp, localSize); // 공간 할당 명령어에 필요한 변수 공간 설정
writeCode(Instruction.Return); // 반환 명령어 생성
}
}Print문에generate()구현
public class Print implements Statement{
private boolean lineFeed = false;
private List<Expression> arguments = new ArrayList<>();
// ...
@Override
public void generate() {
for (int i = arguments.size()-1; i >= 0; i--) {
arguments.get(i).generate(); // 피연산자 스택에 인자의 마지막 값부터 넣는다.
}
writeCode(Instruction.Print, arguments.size()); // 출력 명령어 + 인자 개수
if (lineFeed) {
writeCode(Instruction.PrintLine);
}
}
}StringLiteral식에generate()구현
public class StringLiteral implements Expression {
private String value;
// ...
@Override
public void generate() {
writeCode(Instruction.PushString, value); // 피연산자 스택에 문자열 push
}
}- 실행 결과
@DisplayName("문자열을 출력하는 목적 코드 생성")
@Test
void printString() {
// given
String sourceCode = """
function main() {
print 'Hello, World!';
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
4: 피연산자 스택에 push5: 피연산자 스택에서 pop
산술 연산자 목적 코드 생성
Arithmetic식에generate()구현
public class Arithmetic implements Expression {
private Kind kind;
private Expression lhs;
private Expression rhs;
// ...
@Override
public void generate() {
Map<Kind, Instruction> instructions = Map.of(
Kind.Add, Instruction.Add,
Kind.Subtract, Instruction.Subtract,
Kind.Multiply, Instruction.Multiply,
Kind.Divide, Instruction.Divide,
Kind.Modulo, Instruction.Modulo
);
lhs.generate();
rhs.generate();
writeCode(instructions.get(kind));
}
}- 실행 결과
@DisplayName("산술 연산자 목적 코드 생성")
@Test
void arithmetic() {
// given
String sourceCode = """
function main() {
print 1 * 2 + 3 * 4;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
연산자 명령어: 피연산자 스택에서pop2번 ➔ 계산 ➔ 피연산자 스택에pushPrint [개수] 명령어: 피연산자 스택에서[개수]만큼pop수행하여 출력
식을 임의로 소비하는 문의 목적 코드 생성
ExpressionStatement문에generate()구현
public class ExpressionStatement implements Statement{
private Expression expression;
// ...
@Override
public void generate() {
expression.generate();
writeCode(Instruction.PopOperand); // 피연산자 스택에 남아있는 연산결과물을 제거
}
}- 실행 결과
@DisplayName("식을 임의로 소비하는 문의 목적 코드 생성")
@Test
void expressionStatement() {
// given
String sourceCode = """
function main() {
1 + 2;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
PopOperand: 피연산자 스택에서pop한번
- 이를 통해 소비되지 않은 연산 결과물을 제거
논리 연산자 목적 코드 생성
Or식에generate()구현
public class Or implements Expression {
private Expression lhs;
private Expression rhs;
// ...
@Override
public void generate() {
lhs.generate();
int logicalOr = writeCode(Instruction.LogicalOr); // lhs 연산이 끝난 후, LogicalOr 명령어를 생성하여 명령어 목록에 저장
rhs.generate();
patchAddress(logicalOr); // 만약 lhs 연산이 참인 경우, rhs 연산을 skip 하는 위치로 LogicalOr 명령어의 점프주소를 설정
}
}And식에generate()구현
public class And implements Expression {
private Expression lhs;
private Expression rhs;
// ...
@Override
public void generate() {
lhs.generate();
int logicalAnd = writeCode(Instruction.LogicalAnd); // lhs 연산이 끝난 후, LogicalAnd 명령어를 생성하여 명령어 목록에 저장
rhs.generate();
patchAddress(logicalAnd); // 만약 lhs 연산이 거짓인 경우, rhs 연산을 skip 하는 위치로 LogicalAnd 명령어의 점프주소를 설정
}
}- 실행 결과
@DisplayName("논리 연산 목적 코드 생성")
@Test
void logical() {
// given
String sourceCode = """
function main() {
print false or 1 + 2;
print true and 1 + 2;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
LogicalOr
- 피연산자 스택의 값이
true이면 Jump (RHS 연산을 skip 하는 위치로)- 피연산자 스택의 값이
false이면 스택의 값을 제거하고 RHS 연산 수행
LogicalAnd
- 피연산자 스택의 값이
true이면 스택의 값을 제거하고 RHS 연산 수행- 피연산자 스택의 값이
false이면 Jump (RHS 연산을 skip 하는 위치로)
변수 선언 목적 코드 생성
Function문에generate()구현
public class Function implements Statement {
private String name;
private List<String> parameters = new ArrayList<>();
private List<Statement> block;
// ...
@Override
public void generate() {
functionTable.put(name, codeList.size()); // 함수 테이블에 함수의 이름과 명령어가 시작하는 위치 저장
int temp = writeCode(Instruction.Alloca); // 함수내의 지역 변수 저장을 위한 공간 할당 명령어 생성, 아직 몇 개의 변수 공간이 필요한지는 모른다.
initBlock(); // 함수 블록 초기화
for (String name : parameters) {
setLocal(name); // 파라미터들을 지역 변수로 설정
}
for (Statement node : block) {
node.generate(); // 함수 내의 문들 실행
}
popBlock(); // 함수 블록 제거
patchOperand(temp, localSize); // 함수내의 지역 변수 저장을 위한 공간 크기 설정, 이제는 몇 개의 변수 공간이 필요한지 안다.
writeCode(Instruction.Return); // 반환 명령어 생성
}
}Variable문에generate()구현
public class Variable implements Statement{
private String name;
private Expression expression;
// ...
@Override
public void generate() {
setLocal(name); // 지역 변수로 설정
expression.generate();
writeCode(Instruction.SetLocal, getLocal(name)); // 함수의 변수 공간에서 해당 지역 변수의 인덱스 위치 설정
writeCode(Instruction.PopOperand); // 대입을 위해 사용한 피연산자 스택의 피연산자 제거
}
}- 실행 결과
@DisplayName("변수 선언 목적 코드 생성")
@Test
void defineVariable() {
// given
String sourceCode = """
function main() {
var a = 'first';
var b = 'second';
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
Alloca [2]
- 함수 내의 변수 공간의 크기를 2로 할당
SetLocal [n]
- 피연산자 스택값을 함수 내의 변수 공간의 n 번째 위치에 저장
변수 참조 목적 코드 생성
GetVariable식에generate()구현
public class GetVariable implements Expression {
private String name;
// ...
@Override
public void generate() {
if (getLocal(name) == Integer.MAX_VALUE) { // 전역 볌수 참조
writeCode(Instruction.GetGlobal, name);
} else {
writeCode(Instruction.GetLocal, getLocal(name)); // 지역 변수 참조
}
}
}SetVariable식에generate()구현
public class SetVariable implements Expression {
private String name;
private Expression value;
// ...
@Override
public void generate() {
value.generate();
if (getLocal(name) == Integer.MAX_VALUE) { // 전역 변수 수정
writeCode(Instruction.SetGlobal, name);
} else {
writeCode(Instruction.SetLocal, getLocal(name)); // 지역 변수 수정
}
}
}- 실행 결과
@DisplayName("변수 참조 목적 코드 생성")
@Test
void getVariable() {
// given
String sourceCode = """
function main() {
var local = 'first';
local = 'second';
print local;
global = 'first';
global = 'second';
print global;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
GetLocal [n]
- 함수 내의 변수 공간의 n 번째 인덱스에 위치한 변수를 가져와 피연산자 스택에
pushSetGlobal "변수명"
- 피연산자 스택 값을
변수명전역 변수에 대입한다.GetGlobal "변수명"
변수명전역 변수 값을 피연산자 스택에push
for 문 목적 코드 생성
For문에generate()구현
public class For implements Statement {
private Variable variable;
private Expression condition;
private Expression expression;
private List<Statement> block;
// ...
@Override
breakStack.add(new ArrayList<>()); // break 를 의미하는 jump 명령어들을 저장할 스택
continueStack.add(new ArrayList<>()); // continue 를 의미하는 jump 명령어들을 저장할 스택
pushBlock(); // 현재 함수 프레임에 블록 추가
variable.generate(); // 초기화식 목적 코드 생성
int jumpAddress = codeList.size(); // for 문을 반복 시 다시 되돌아올 주소 -> 조건식 시작 위치
condition.generate(); // 조건식 목적 코드 생성
int conditionJump = writeCode(Instruction.ConditionJump); // 조건식을 만족하지 않을 경우, for문 반복 탈출을 위한 conditionJump 명령어 작성
for (Statement node : block) {
node.generate(); // for문 본문 블록 목적 코드 생성
}
int continueAddress = codeList.size(); // for문 본문 블록이 끝난 주소 -> continue 명령어가 jump 할 위치
expression.generate(); // 증감식 목적 코드 생성
writeCode(Instruction.PopOperand); // 증감식의 결과물을 피연산자 스택에서 제거
writeCode(Instruction.Jump, jumpAddress); // for 문 반복을 위해 다시 되돌아갈 주소로 jump
patchAddress(conditionJump); // for 문 반복 종료 시, 탈출할 위치 주소를 conditionJump 명령어에 설정
popBlock(); // 블록 제거
for (Integer jump : continueStack.get(continueStack.size() - 1)) { // 모든 continue 명령어의 jump 할 위치를 continueAddress (for 문 본문 블록이 끝난 주소) 로 설정
patchOperand(jump, continueAddress);
}
continueStack.remove(continueStack.size() - 1); // for 문이 끝났으니 continue 스택 제거
for (Integer jump : breakStack.get(breakStack.size() - 1)) { // 모든 break 명령어의 jump 할 위치를 for 문 반복 종료 후 탈출할 위치 주소로 설정
patchAddress(jump);
}
breakStack.remove(breakStack.size() - 1); // for 문이 끝났으니 break 스택 제거
}
}Continue문에generate()구현
public class Continue implements Statement {
// ...
@Override
public void generate() {
if (continueStack.isEmpty()) {
return;
}
int jumpCode = writeCode(Instruction.Jump);
continueStack.get(continueStack.size() - 1).add(jumpCode); // 현재 반복문의 continueStack 에 현재 jump 명령어 추가
}
}Break문에generate()구현
public class Break implements Statement {
// ...
@Override
public void generate() {
if (breakStack.isEmpty()) {
return;
}
int jumpCode = writeCode(Instruction.Jump);
breakStack.get(breakStack.size() - 1).add(jumpCode); // 현재 반복문의 breakStack 에 현재 jump 명령어 추가
}
}- 단순 반복문 실행 결과
@DisplayName("단순 반복문 목적 코드 생성")
@Test
void executeFor() {
// given
String sourceCode = """
function main() {
for i=0, i<3, i=i+1 {
print i;
}
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
LessThan
피연산자 스택[-2] < 피연산자 스택[-1]을 만족하지 않는다면ConditionJump [n]을 수행ConditionJump [n]
n으로 Jump
Continue가 있는 반복문 실행 결과
@DisplayName("Continue 반복문 목적 코드 생성")
@Test
void continueFor() {
// given
String sourceCode = """
function main() {
for i=0, i<3, i=i+1 {
continue;
print i;
}
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
continue;실행 시, 해당 지점에서 증감식 시작 부분까지 Jump
Break가 있는 반복문 실행 결과
@DisplayName("Break 반복문 목적 코드 생성")
@Test
void breakFor() {
// given
String sourceCode = """
function main() {
for i=0, i<3, i=i+1 {
break;
print i;
}
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
break;실행 시, 해당 지점에서 반복문 탈출 지점까지 Jump
If 문 목적 코드 생성
If문에generate()구현
public class If implements Statement {
private List<Expression> conditions = new ArrayList<>();
private List<List<Statement>> blocks = new ArrayList<>();
private List<Statement> elseBlock = new ArrayList<>();
// ...
@Override
public void generate() {
List<Integer> jumpList = new ArrayList<>(); // 하나의 조건문 블록 수행 시, 남은 여러개의 조건문들을 건너뛰고 종료해야 한다.
// 이때 필요한 각각의 조건문 블록이 끝난 뒤 사용되는 jump 명령어들을 저장하는 리스트
for (int i = 0; i < conditions.size(); i++) {
conditions.get(i).generate(); // 조건식 목적 코드 생성
int conditionJump = writeCode(Instruction.ConditionJump); // 조건식이 거짓인 경우 다음 조건문으로 ConditionJump
pushBlock(); // 함수 프레임 내에 블록 추가
for (Statement node : blocks.get(i)) {
node.generate(); // 조건문의 본문 목적 코드 생성
}
popBlock(); // 블록 제거
jumpList.add(writeCode(Instruction.Jump)); // 현재 조건문의 종료 지점에 남은 조건문들을 건너뛰기 위한 Jump 명령어 생성
patchAddress(conditionJump); // 현재 조건문의 종료 지점 바로 다음을 CoditionJump 명령어에 Jump 할 주소로 설정
}
if (!elseBlock.isEmpty()) { // elseBlock 목적 코드 생성
pushBlock(); // 함수 프레임 내에 블록 추가
for (Statement node : elseBlock) {
node.generate(); // elseBlock 본문 목적 코드 생성
}
popBlock(); // 블록 제거
}
for (Integer jump : jumpList) { // 남은 조건문들을 건너뛰기 위한 Jump 명령어들의 Jump 할 주소를 마지막 주소 바로 다음 주소로 설정
patchAddress(jump);
}
}
}- 실행 결과
@DisplayName("if 문 목적 코드 생성")
@Test
void executeIf() {
// given
String sourceCode = """
function main() {
if true {
print 'if';
} elif true {
print 'elif';
} else {
print 'else';
}
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
함수 호출 목적 코드 생성
Call식에generate()구현
public class Call implements Expression {
private Expression sub;
private List<Expression> arguments = new ArrayList<>();
// ...
@Override
public void generate() {
for (int i = arguments.size() - 1; i >= 0; i--) {
arguments.get(i).generate(); // 피연산자 스택에 넣으므로, 역순으로 인자들의 목적 코드 생성
}
sub.generate(); // 함수명 목적 코드를 생성하여 호출한 함수의 주소를 얻어온다.
writeCode(Instruction.Call, arguments.size()); // 피연산자 스택[-1] 값 (호출한 함수 주소)으로 Jump 한다. + 피연산자 스택에서 인자 개수만큼 파라미터로 가져간다.
}
}Return문에generate()구현
public class Return implements Statement {
private Expression expression;
// ...
@Override
public void generate() {
expression.generate();
writeCode(Instruction.Return); // 피연산자 스택에 있는 연산결과값을 반환
}
}- 실행 결과
@DisplayName("함수 호출 목적 코드 생성")
@Test
void callFunc() {
// given
String sourceCode = """
function main() {
print add(3, 4);
}
function add(a, b) {
return a + b;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
Call [n]
- 피연산자 스택[-1] 값이 Jump 할 명령어 주소 (호출한 함수 주소)
- 피연산자 스택[-2] 부터 n개는 파라미터로 넘어간다.
- 해당 값들이 피연산자 스택에서
pop된다.Return
Call명령어 바로 다음 명령어 주소를 가리킨다.- 반환값이 있는 함수의 경우
Return이 두개다.
- 앞의 것이
Return문에서 만드는Return명령어이고, 뒤의 것이Function문에서 만드는Return명령어이다.
배열, 맵 리터럴 목적 코드 생성
ArrayLiteral식에generate()구현
public class ArrayLiteral implements Expression {
private List<Expression> values = new ArrayList<>();
// ...
@Override
public void generate() {
for (int i = values.size() - 1; i >= 0; i--) {
values.get(i).generate(); // 뒤에서 부터 목적 코드 생성
}
writeCode(Instruction.PushArray, values.size()); // 피연산자 스택에서 [n]개를 꺼내 배열로 만들고, 피연산자 스택에 다시 넣는다.
}
}- 실행 결과
@DisplayName("배열과 맵 목적 코드 생성")
@Test
void arrayAndMapLiteral() {
// given
String sourceCode = """
function main() {
[1, 2, 'element'];
{'a' : 'a_val', 'b' : 1};
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
PushArray [n]
- 피연산자 스택에서 n 개를 꺼내어 배열로 만들어 다시
pushPushMap [n]
- 피연산자 스택에서 n 개 쌍을 꺼내어 맵으로 만들어 다시
push
원소값 참조 및 수정 목적 코드 생성
GetElement식에generate()구현
public class GetElement implements Expression {
private Expression sub;
private Expression index;
// ...
@Override
public void generate() {
sub.generate(); // 배열, 맵의 정보를 알아내기 위한 피연산자 목적 코드 생성
index.generate(); // 인덱스 목적 코드 생성
writeCode(Instruction.GetElement); // 피연산자 스택[-2] (배열, 맵)의 피연산자 스택[-1] (인덱스) 번째 값을 가져와 다시 피연산자 스택에 push
}
}- 원소 참조 실행 결과
public class GetElement implements Expression {
private Expression sub;
private Expression index;
// ...
@Override
public void generate() {
sub.generate(); // 배열, 맵의 정보를 알아내기 위한 피연산자 목적 코드 생성
index.generate(); // 인덱스 목적 코드 생성
writeCode(Instruction.GetElement); // 피연산자 스택[-2] (배열, 맵)의 피연산자 스택[-1] (인덱스) 번째 값을 가져와 다시 피연산자 스택에 push
}
}
GetElement
피연산자 스택[-2] (배열, 맵)의피연산자 스택[-1] (인덱스)값을 가져와 다시 피연산자 스택에push
SetElement식에generate()구현
public class SetElement implements Expression {
private Expression sub;
private Expression index;
private Expression value;
// ...
@Override
public void generate() {
value.generate(); // 대입할 값 목적 코드 생성
sub.generate();
index.generate();
writeCode(Instruction.SetElement); // 피연산자 스택[-2] (배열, 맵) 의 피연산자 스택[-1] (인덱스) 번째 값을 피연산자 스택[-3] 으로 수정
}
}- 원소 변경 실행 결과
@DisplayName("배열 원소 변경 코드 생성")
@Test
void arraySetElement() {
// given
String sourceCode = """
function main() {
var a = [1, 2, 'element'];
a[2] = 3;
}
""";
List<Token> tokenList = scanner.scan(sourceCode);
Program syntaxTree = parser.parse(tokenList);
// when
Pair<List<Code>, Map<String, Integer>> objectCode = generator.generate(syntaxTree);
// then
printObjectCode(objectCode);
}
SetElement
피연산자 스택[-2] (배열, 맵)의피연산자 스택[-1] (인덱스)번째 값을피연산자 스택[-3]으로 수정
소스 코드: https://github.com/ghkdgus29/crafting-compiler/tree/make-object-code
가상머신
-
앞서 만든 선형 구조인 목적 코드를 순차적으로 하나씩 읽고 실행한다.
-
스택 프레임을 제공한다.
-
피연산자 스택
-
매개변수, 지역변수 저장 공간
-
다음에 실행할 명령어의 위치를 가리키는 명령어 포인터 가 필요하다.
-
-
콜 스택 (호출 스택)을 제공한다.
- 스택 프레임들의 리스트이다.
StackFrame 클래스
-
함수 하나의 스택 프레임을 나타낸다.
-
함수내의 변수 공간 (
variables) -
피연산자 스택 (
operandStack) -
명령어 포인터 (
instructionPointer) 로 이루어져 있다.
-
public class StackFrame {
List<Object> variables = new ArrayList<>(); // 함수내의 변수 공간
Stack<Object> operandStack = new Stack<>(); // 피연산자 스택
int instructionPointer = 0; // 명령어 포인터
public Object getVariableAt(int index) { // 변수 공간의 n 번째 인덱스의 변수를 가져온다.
return variables.get(index);
}
public void changeValueAt(int index, Object value) { // 변수 공간의 n 번째 인덱스의 변수를 바꾼다.
if (variables.size() > index) {
variables.set(index, value);
} else {
variables.add(value);
}
}
public void addVariable(Object variable) { // 변수 공간에 변수를 추가한다.
variables.add(variable);
}
public List<Object> getVariables() {
return variables;
}
public void addOperand(Object value) { // 피연산자 스택에 피연산자를 push
operandStack.push(value);
}
public Object popOperand() { // 피연산자 스택에 피연산자를 pop
return operandStack.pop();
}
public Object peekOperand() { // 피연산자 스택에 top 값을 peek
return operandStack.peek();
}
public boolean isOperandStackEmpty() {
return operandStack.isEmpty();
}
public Stack<Object> getOperandStack() {
return operandStack;
}
public int getInstructionPointer() {
return instructionPointer;
}
public void setInstructionPointer(int instructionPointer) { // 명령어 포인터 값을 변경한다. (Jump, ConditionJump)
this.instructionPointer = instructionPointer;
}
public void increaseInstructionPointer() { // 명령어 포인터 값을 1 증가한다. (일반적인 명령어 진행 흐름)
instructionPointer += 1;
}
}Machine 클래스
-
가상 머신으로 동작하는 클래스
-
스택 프레임들을 보관하는 콜 스택, 전역 변수, 가비지 콜렉션을 위한 해쉬맵을 관리한다.
- 가비지 콜렉션 방식은 마크 앤 스윕으로, 배열과 맵이 가비지 콜렉션의 대상이 된다.
-
각 명령어의 실제 동작을 구현한다.
public class Machine {
private static Stack<StackFrame> callStack = new Stack<>(); // 스택 프레임들을 보관하는 호출 스택
private static Map<String, Object> global = new HashMap<>(); // 전역 변수 관리
private static Map<Object, Boolean> objects = new HashMap<>(); // 가비지 콜렉션을 위한 해쉬맵, true -> mark, false -> unmark
public void execute(Pair<List<Code>, Map<String, Integer>> objectCode) { // 가상 머신이 목적 코드를 읽으면서 프로그램을 실행한다.
callStack.push(new StackFrame());
List<Code> codeList = objectCode.getKey();
Map<String, Integer> functionTable = objectCode.getValue();
while (true) {
int instructionPointer = callStack.peek().getInstructionPointer();
Code code = codeList.get(instructionPointer);
switch (code.getInstruction()) {
case Exit -> { // 프로그램 종료
callStack.pop();
return;
}
case GetGlobal -> { // 전역 변수 참조
String name = (String) code.getOperand();
if (functionTable.containsKey(name)) {
pushOperand(functionTable.get(name)); // 함수 이름인 경우, 함수 시작 주소를 피연산자에 push
} else if (builtinFunctionTable.containsKey(name)) {
pushOperand(name); // 내장 함수 이름인 경우, 내장 함수 이름을 피연산자에 push
} else if (global.containsKey(name)) {
pushOperand(global.get(name)); // 전역 변수인 경우, 전역 변수값을 피연산자에 push
} else {
throw new RuntimeException("존재하지 않는 전역변수 참조입니다.");
}
}
case SetGlobal -> { // 전역 변수 설정
String name = Datatype.toString(code.getOperand());
global.put(name, peekOperand()); // 피연산자 스택에서 peek, 전역 변수 선언식을 감싸는 ExpressionStatement 문이 피연산자 스택에서 1개 pop 하기 때문에
}
case Call -> { // 함수 호출
Object operand = popOperand(); // 피연산자 스택에서 함수 시작 주소 pop
if (isSize(operand)) { // 주소인 경우 -> 사용자 정의 함수
StackFrame stackFrame = new StackFrame();
stackFrame.setInstructionPointer(toSize(operand)); // 호출 함수 스택 프레임 생성 후, 명령어 포인터를 함수 시작 주소로 설정
for (int i = 0; i < toSize(code.getOperand()); i++) {
stackFrame.addVariable(popOperand()); // 파라미터를 호출 함수 변수 공간에 넣는다.
}
callStack.push(stackFrame); // 호출 스택에 호출 함수 스택 프레임을 push
continue; // 위에서 명령어 주소를 설정하였기 때문에, 밑에서 명령어 포인터가 1 증가하지 않도록 설정
}
if (isBuiltinFunction(operand)) { // 이름인 경우 -> 내장 함수
List<Object> arguments = new ArrayList<>();
for (int i = 0; i < toSize(code.getOperand()); i++) {
arguments.add(popOperand()); // 파라미터 리스트를 만든다.
}
pushOperand(toBuiltinFunction(operand).apply(arguments)); // 내장 함수를 실행한 후, 결과값을 피연산자 스택에 push
break; // case 문 탈출
}
pushOperand(null); // 잘못된 함수 호출의 경우 null 을 피연산자 스택에 push
}
case Alloca -> {
// 현재 스택 프레임이 필요로 하는 함수 내의 지역 변수 공간의 크기는 현재 실행하는 명령어가 갖고 있다.
// Alloca 명령어는 함수 내의 지역 변수 공간의 크기를 보장해준다.
// 자바의 List 는 동적으로 크기를 증가시키므로, 지역 변수 공간의 크기를 보장해주는 로직은 특별히 필요없다.
}
case Print -> { // 출력
for (int i = 0; i < toSize(code.getOperand()); i++) {
Object value = popOperand(); // 피연산자 스택에서 꺼내서 출력
System.out.print(value);
}
}
case PrintLine -> System.out.println(); // 줄바꿈 출력 명령어
case Return -> { // 함수 결과값 반환
Object result = null; // 반환값이 없는 경우 null
if (!callStack.peek().isOperandStackEmpty()) { // 반환값이 있는 경우
result = popOperand();
}
callStack.pop(); // 현재 호출된 함수가 종료되었으므로, 현재 스택프레임 제거
pushOperand(result); // 피호출 스택프레임의 피연산자 스택에 result 추가
// 반환값이 없더라도 null을 피연산자 스택에 넣어야 한다.
// 호출함수를 감싸는 ExpressionStatement, Variable 문이 피연산자 스택에서 1개를 pop 하기 때문이다.
collectGarbage();
}
case Add -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) + toNumber(rValue));
} else if (isString(lValue) && isString(rValue)) {
pushOperand(Datatype.toString(lValue) + Datatype.toString(rValue));
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case Subtract -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) - toNumber(rValue));
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case Multiply -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) * toNumber(rValue));
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case Divide -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue) && toNumber(rValue) == 0) {
pushOperand("INF");
} else if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) / toNumber(rValue));
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case Modulo -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue) && toNumber(rValue) == 0) {
pushOperand("NaN");
} else if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) % toNumber(rValue));
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case Absolute -> {
Object value = popOperand();
if (isNumber(value)) {
pushOperand(Math.abs(toNumber(value)));
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case ReverseSign -> {
Object value = popOperand();
if (isNumber(value)) {
pushOperand(toNumber(value) * -1);
} else {
throw new RuntimeException("잘못된 연산입니다.");
}
}
case LogicalOr -> { // or 연산
Object value = popOperand();
if (isTrue(value)) {
pushOperand(value); // 앞에서 검사를 위해 뺀 value 값을 다시 push 하여 참/거짓 여부를 결정하는 키로 사용
callStack.peek().setInstructionPointer(toSize(code.getOperand())); // 만약 왼쪽 항목이 참인 경우, 오른쪽 항목을 검사하지 않고 JUMP
continue; // 위에서 명령어 주소를 설정하였기 때문에, 밑에서 명령어 포인터가 1 증가하지 않도록 설정
}
// 만약 lValue 가 참이 아닌 경우, rValue 값이 피연산자 스택에 남아 참/거짓 여부를 결정하는 키가 된다.
}
case LogicalAnd -> { // and 연산
Object value = popOperand();
if (isFalse(value)) {
pushOperand(value); // 앞에서 검사를 위해 뺀 value 값을 다시 push 하여 참/거짓 여부를 결정하는 키로 사용
callStack.peek().setInstructionPointer(toSize(code.getOperand())); // 만약 왼쪽 항목이 거짓인 경우, 오른쪽 항목을 검사하지 않고 JUMP
continue; // 위에서 명령어 주소를 설정하였기 때문에, 밑에서 명령어 포인터가 1 증가하지 않도록 설정
}
// 만약 lValue 가 거짓이 아닌 경우, rValue 값이 피연산자 스택에 남아 참/거짓 여부를 결정하는 키가 된다.
}
case Equal -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNull(lValue) && isNull(rValue)) {
pushOperand(true);
} else if (isBoolean(lValue) && isBoolean(rValue)) {
pushOperand(toBoolean(lValue) == toBoolean(rValue));
} else if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue).equals(toNumber(rValue)));
} else if (isString(lValue) && isString(rValue)) {
pushOperand(Datatype.toString(lValue).equals(Datatype.toString(rValue)));
} else {
throw new RuntimeException("잘못된 비교입니다.");
}
}
case NotEqual -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNull(lValue) && isNull(rValue)) {
pushOperand(false);
} else if (isNull(lValue) || isNull(rValue)) {
pushOperand(true);
} else if (isBoolean(lValue) && isBoolean(rValue)) {
pushOperand(toBoolean(lValue) != toBoolean(rValue));
} else if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(!toNumber(lValue).equals(toNumber(rValue)));
} else if (isString(lValue) && isString(rValue)) {
pushOperand(!Datatype.toString(lValue).equals(Datatype.toString(rValue)));
} else {
throw new RuntimeException("잘못된 비교입니다.");
}
}
case LessThan -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) < (toNumber(rValue)));
} else {
throw new RuntimeException("잘못된 비교입니다.");
}
}
case GreaterThan -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) > (toNumber(rValue)));
} else {
throw new RuntimeException("잘못된 비교입니다.");
}
}
case LessOrEqual -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) <= (toNumber(rValue)));
} else {
throw new RuntimeException("잘못된 비교입니다.");
}
}
case GreaterOrEqual -> {
Object rValue = popOperand();
Object lValue = popOperand();
if (isNumber(lValue) && isNumber(rValue)) {
pushOperand(toNumber(lValue) >= (toNumber(rValue)));
} else {
throw new RuntimeException("잘못된 비교입니다.");
}
}
case GetLocal -> { // 지역 변수 참조
int index = toSize(code.getOperand());
pushOperand(callStack.peek().getVariableAt(index)); // 명령어에 입력된 index 를 사용해, 함수 내의 변수 공간의 index 번째 변수값을 피연산자 스택에 push
}
case SetLocal -> { // 지역 변수 변경
int index = toSize(code.getOperand());
callStack.peek().changeValueAt(index, peekOperand()); // 명령어에 입력된 index 를 사용해, 함수 내의 변수 공간의 index 번째 변수값을 피연산자 스택에 peek 값으로 변경
// SetLocal 식을 포함하는 ExpressionStatement 문이 피연산자 스택에서 1개를 pop 한다.
}
case Jump -> { // 점프 명령
callStack.peek().setInstructionPointer(toSize(code.getOperand())); // 점프 명령어에 입력된 주소로 명령어 포인터 값을 바꾼다.
continue; // 위에서 명령어 주소를 설정하였기 때문에, 밑에서 명령어 포인터가 1 증가하지 않도록 설정
}
case ConditionJump -> { // 조건을 만족하지 않는 경우 Jump 한다.
Object condition = popOperand();
if (isTrue(condition)) { // 조건을 만족하면 case 문 탈출
break;
}
callStack.peek().setInstructionPointer(toSize(code.getOperand())); // 컨디션점프 명령어에 입력된 주소로 명령어 포인터 값을 바꾼다.
continue; // 위에서 명령어 주소를 설정하였기 때문에, 밑에서 명령어 포인터가 1 증가하지 않도록 설정
}
case PushNull -> pushOperand(null);
case PushBoolean -> pushOperand(code.getOperand());
case PushNumber -> pushOperand(code.getOperand());
case PushString -> pushOperand(code.getOperand());
case PushArray -> {
List<Object> result = new ArrayList<>();
for (int i = 0; i < toSize(code.getOperand()); i++) {
result.add(popOperand());
}
pushOperand(result); // 피연산자 스택에 push 되는 것은 실제 배열이 아니고, 참조이다.
objects.put(result, false); // 실제로는 힙 공간에 생성 -> 가비지 콜렉션의 대상이 된다.
}
case PushMap -> {
Map<String, Object> result = new HashMap<>();
for (int i = 0; i < toSize(code.getOperand()); i++) {
Object value = popOperand();
String key = Datatype.toString(popOperand());
result.put(key, value);
}
pushOperand(result); // 피연산자 스택에 push 되는 것은 실제 맵이 아니고, 참조이다.
objects.put(result, false); // 실제로는 힙 공간에 생성 -> 가비지 콜렉션의 대상이 된다.
}
case GetElement -> {
Object index = popOperand();
Object sub = popOperand();
if (isArray(sub) && isNumber(index)) {
pushOperand(getValueOfArray(sub, index));
} else if (isMap(sub) && isString(index)) {
pushOperand(getValueOfMap(sub, index));
} else {
throw new RuntimeException("잘못된 인덱스 접근입니다.");
}
}
case SetElement -> { // 배열, 맵의 요소 변경
Object index = popOperand();
Object sub = popOperand(); // sub는 힙 공간에 있는 배열/맵의 참조이다.
// 따라서 sub 내의 요소를 변경하면 힙 공간에 있는 참조된 배열/맵 요소들이 변경된다.
if (isArray(sub) && isNumber(index)) {
setValueOfArray(sub, index, peekOperand());
} else if (isMap(sub) && isString(index)) {
setValueOfMap(sub, index, peekOperand()); // peekOperand() = 바꾸려는 값, SetElement를 감싸는 ExpressionStatement 문이 피연산자 스택에서 1개 pop 한다.
} else {
throw new RuntimeException("잘못된 인덱스 접근입니다.");
}
}
case PopOperand -> popOperand();
}
callStack.peek().increaseInstructionPointer(); // 명령어 포인터 1 증가
}
}
private void pushOperand(Object value) { // 현재 실행하는 스택 프레임의 피연산자 스택에 value push
callStack.peek().addOperand(value);
}
private Object popOperand() { // 현재 실행하는 스택 프레임의 피연산자 스택에서 pop
return callStack.peek().popOperand();
}
private Object peekOperand() { // 현재 실행하는 스택 프레임의 피연산자 스택에서 peek
return callStack.peek().peekOperand();
}
private void collectGarbage() { // mark and sweep 방식 가비지 콜렉션
for (StackFrame stackFrame : callStack) { // 호출 스택을 다 돌면서 마킹
for (Object value : stackFrame.getOperandStack()) {
markObject(value);
}
for (Object value : stackFrame.getVariables()) {
markObject(value);
}
}
for (Object value : global.values()) { // 전역 변수가 참조하는 공간들도 마킹
markObject(value);
}
sweepObject(); // 스윕
}
private void markObject(Object value) { // 힙 공간에 생성되는 배열, 맵을 재귀적으로 마킹
if (isArray(value)) {
if (!objects.get(value)) {
objects.put(value, true);
for (Object element : toArray(value)) {
markObject(element);
}
}
}
else if (isMap(value)) {
if (!objects.get(value)) {
objects.put(value, true);
for (Object element : toMap(value).values()) {
markObject(element);
}
}
}
}
private void sweepObject() { // 마킹되지 않은 객체들을 힙 공간에서 제거
List<Object> remove = new ArrayList<>();
objects.forEach((ref, mark) -> {
if (mark) {
objects.replace(ref, false);
} else {
remove.add(ref);
}
});
remove.forEach(ref -> {
objects.remove(ref);
});
}
}소스 코드: https://github.com/ghkdgus29/crafting-compiler/tree/virtual-machine
출처
컴파일러 만들기 (유종원 님)
좋은 글 잘 읽었습니다. 자바 버전은 함 실행해봐야겠어요 ㅋ