Summary
최근 학교 수업에서 컴파일러를 공부해볼 수 있는 기회가 생겼습니다. 본래 프로젝트 주제는 어셈블러와 MCU Emulator를 구현하고 어셈블러를 통해 컴파일된 목적코드를 MCU Emulator로 실행하는 것이었으나, 욕심이 생겨 간단한 고급 언어를 컴파일할 수 있는 컴파일러를 구현해보았습니다. 구현하기까지 공부했던 모든 내용을 담기에는 어려움이 있겠으나 컴파일 절차가 구체적으로 어떠하고, 어떻게 구현될 수 있는지에 대해서는 대략적으로 공유할 수 있을 것 같아 글을 남깁니다.
Implementation
Preprocessor
public class Preprocessor {
public String preprocess(String sourceCode) {
sourceCode = removeComment(sourceCode);
sourceCode = removeEmptyLine(sourceCode);
return sourceCode;
}
private String removeComment(String sourceCode) {
StringBuilder buffer = new StringBuilder();
for (String line : sourceCode.split("\n"))
buffer.append(line.split("//")[0]).append("\n");
return buffer.toString();
}
private String removeEmptyLine(String sourceCode) {
StringBuilder buffer = new StringBuilder();
for (String line : sourceCode.split("\n"))
if (!line.equals(""))
buffer.append(line).append("\n");
return buffer.toString();
}
}
Java
복사
제가 구현한 전처리기는 주석과 비어있는 라인을 제거하는 작업만 수행 합니다. 하지만 C언어 컴파일러와 같이 더 복잡한 컴파일러의 전처리기는 매크로 상수 및 함수, 프로토타입을 처리하는 등 더 많은 작업을 수행할 수 있습니다.
Lexer
컴파일의 첫단계는 어휘 분석입니다. 그리고 어휘분석을 수행하는 모듈을 Lexical Analyzer(Lexer)라고 부릅니다. 소스코드도 결국 하나의 긴 문자열입니다. 우리는 이 문자열을 구분자(일반적으로는 Whitespace)로 구분한 뒤, 구분된 문자열들이 어떤 심볼에 속하는지 확인할 것입니다.
심볼의 정규 문법을 정규 표현식으로 나타내면 아래와 같습니다.
IF ^if$
ENDIF ^endif$
WHILE ^while$
ENDWHILE ^endwhile$
DATA_TYPE ^short|int|long$
RELATIONAL_OPERATOR ^!=|<|>$
ARITHMETIC_OPERATOR ^\\+|-|/|\\*$
EQUALS_SIGN ^=$
PRINT_FUNC ^print$
IDENTIFIER ^[^0-9][a-zA-Z0-9]*$
NUMBER ^[0-9]*$
Plain Text
복사
이어 소스 코드는 아래와 같습니다.
public class Lexer {
private final Queue<Token> symbolTable = new LinkedList<>();
public boolean analysis(String sourceCode) {
Scanner scanner = new Scanner(sourceCode);
while (scanner.hasNext()) {
String lexeme = scanner.next();
Symbol symbol = findSymbol(lexeme);
if (symbol == null) {
System.out.println("Unknown Token : " + lexeme);
System.out.printf("%-20s%-7s\n", "Lexical Analysis", "KO :(");
return false;
}
symbolTable.add(new Token(symbol, lexeme));
}
scanner.close();
return true;
}
private Symbol findSymbol(String value) {
for (Symbol symbol : Symbol.values())
if (Pattern.matches(symbol.getRegex(), value)) return (symbol);
return null;
}
public Token getToken() {
return symbolTable.isEmpty() ? null : symbolTable.poll();
}
}
Java
복사
Scanner 클래스는 Whitespace를 구분자로 하여 구분된 문자열을 next 함수가 호출될 때마다 순차적으로 반환합니다. 이렇게 구분자로 구분된 하나의 문자열을 어휘소(Lexeme)라고 부릅니다. while, if, else, {, }, int, main… 이런 문자열들이 모두 어휘소가 됩니다. 어휘소가 어떤 심볼에 속하는 확인하기 위해 findSymbol함수를 호출합니다. findSymbol 함수는 사전에 정의된 심볼의 정규 문법을 통해 어휘소가 어떤 심볼에 속하는지 확인한 후에 해당 심볼을 반환합니다. 만약 어휘소가 어떤 심볼에도 속하지 않는다면 예외 메시지를 출력하고 false를 반환합니다.
심볼과 어휘소를 기본키로 하는 개체를 토큰이라고 부릅니다. 어휘소가 속한 심볼을 찾았다면 두 값을 기본키로 하는 토큰 인스턴스를 생성하여 심볼 테이블에 추가합니다. 심볼 테이블에 모든 토큰이 추가되었다면 Lexer의 역할은 끝이 납니다. 이렇게 만들어진 심볼 테이블은 다음 단계인 구문 분석에서 사용될 것입니다.
기본키(Primary key)는 개체를 식별할 수 있는 값입니다. 42Seoul의 카뎃분들을 예를 들면 인트라 아이디가 기본키가 될 수 있습니다. 반대로 이름은 기본키가 될 수 없습니다. 동명이인이 있을 수 있으니까요.
Parser
어휘 분석을 통해 각 어휘소가 어떤 심볼에 속하는지 확인했습니다. 이제 할 일은 우리가 정의한 생성 규칙으로 문장을 만들어낼 수 있는지 확인하는 것입니다. 쉽게 말해 심볼들이 적절한 순서로 나열되어있는지 확인하겠다는 것입니다. 이 과정을 구문 분석이라고 부릅니다.
구문 분석은 철저하게 문맥 자유 문법의 Production Rule에 의해서 수행됩니다. 다음은 Production Rule을 바커스-나우르 폼으로 표현한 결과입니다.
<VALUE> ::= <IDENTIFIER> | <NUMBER>
<EXPRESSION> ::= <VALUE><ARITHMETIC_OPERATOR><VALUE>
<DECLARATION> ::= <DATA_TYPE><ASSIGNMENT>
<ASSIGNMENT> ::= <IDENTIFIER><EQUALS_SIGN><EXPRESSION>
<CONDITION> ::= <VALUE><RELATIONAL_OPERATOR><VALUE>
<ITERATION_BRANCH> ::= <STATEMENT><ITERATION_BRANCH> | <STATEMENT><ENDWHILE>
<SELECTION_BRANCH> ::= <STATEMENT><SELECTION_BRANCH> | <STATEMENT><ENDIF>
<ITERATION> ::= <WHILE><CONDITION><ITERATION_BRANCH>
<SELECTION> ::= <IF><CONDITION><SELECTION_BRANCH>
<PRINT> ::= <PRINT_FUNC><VALUE>
<STATEMENT> ::= <ASSIGNMENT> | <ITERATION> | <SELECTION> | <PRINT>
<PROGRAM> ::= <STATEMENT> | <STATEMENT><PROGRAM>
Plain Text
복사
저는 재귀 하향 파서로 구현했기 때문에 코드의 구현도 Production Rule에 근거합니다.
public boolean parse() {
nextToken();
return program();
}
private boolean program() {
root = new Token(Statement.PROGRAM);
while (token != null) {
Token token = statement();
if (token == null) {
System.out.println("Unexpected Symbol : " + token.value);
System.out.printf("%-20s%-7s\n", "Parsing", "KO :(");
return false;
}
root.addChild(token);
}
return true;
}
private Token statement() {
Token node = new Token();
if (accept(Symbol.DATA_TYPE, node)) {
node.statement = Statement.DECLARATION;
expect(Symbol.IDENTIFIER, node);
expect(Symbol.EQUALS_SIGN, node);
node.addChild(expression());
} else if (accept(Symbol.IDENTIFIER, node)) {
node.statement = Statement.ASSIGNMENT;
expect(Symbol.EQUALS_SIGN, node);
node.addChild(expression());
} else if (accept(Symbol.WHILE, node)) {
node.statement = Statement.ITERATION;
node.addChild(condition());
node.addChild(whileBlock());
} else if (accept(Symbol.IF, node)) {
node.statement = Statement.SELECTION;
node.addChild(condition());
node.addChild(ifBlock());
} else if (accept(Symbol.PRINT_FUNC, node)) {
node.statement = Statement.PRINT;
if (!accept(Symbol.IDENTIFIER, node)) expect(Symbol.NUMBER, node);
} else return null;
return node;
}
private Token expression() {
Token node = new Token(Statement.EXPRESSION);
if (!accept(Symbol.IDENTIFIER, node)) expect(Symbol.NUMBER, node);
if (accept(Symbol.ARITHMETIC_OPERATOR, node))
if (!accept(Symbol.IDENTIFIER, node)) expect(Symbol.NUMBER, node);
return node;
}
private Token condition() {
Token node = new Token(Statement.CONDITION);
if (!accept(Symbol.IDENTIFIER, node)) expect(Symbol.NUMBER, node);
expect(Symbol.RELATIONAL_OPERATOR, node);
if (!accept(Symbol.IDENTIFIER, node)) expect(Symbol.NUMBER, node);
return node;
}
private Token whileBlock() {
Token node = new Token(Statement.BRANCH);
while (!accept(Symbol.ENDWHILE, node)) node.addChild(statement());
return node;
}
private Token ifBlock() {
Token node = new Token(Statement.BRANCH);
while (!accept(Symbol.ENDIF, node)) node.addChild(statement());
return node;
}
private boolean accept(Symbol symbol, Token node) {
if (token.symbol == symbol) {
node.addChild(token);
nextToken();
return true;
}
return false;
}
private void expect(Symbol symbol, Token node) {
if (!accept(symbol, node)) {
System.out.println("Unexpected Symbol : " + token.value);
System.out.printf("%-20s%-7s\n", "Parsing", "KO :(");
System.exit(0);
}
}
private void nextToken() {
token = lexer.getToken();
}
Java
복사
위 코드를 통해 파스 트리를 생성하면 구문 분석 단계도 끝이 납니다.
구문 분석 다음 단계는 원래 의미 분석입니다. 구문 분석이 심볼들의 나열 순서를 확인하는 것이었다면 의미 분석은 문장들의 나열 순서를 확인하는 것입니다. 예를 들면 a라는 변수의 선언문이 a를 피연산자로 하는 산술연산식보다 앞에 있는지 확인하는 것입니다. 선언하지도 않은 변수를 연산에 사용할 수는 없으니까요.
원래 이 부분만 수행하는 모듈이 따로 있으나 문법 자체가 간단하기 때문에 선언문으로 선언된 변수만 사용할 수 있도록 하면 됩니다. 따라서 이 부분은 Code generator에서 수행하도록 구현했습니다.
Code generator
구문 분석 단계에서 만들었던 파스 트리를 순회하여 문장들을 기계 코드로 번역할 것입니다. 이 과정에서 우리가 이름을 붙여 선언했던 변수들은 모두 메모리 주소로 변환됩니다. 기계 코드에는 우리가 작성했던 소스 코드의 정보가 모두 사라지게 되는 것이죠.
코드 생성도 파스 트리를 생성했을 때처럼 재귀적으로 구현됩니다.
private List<String> instructions;
private List<Identifier> idTable;
// addressing mode
private final String IM = "00";
private final String DI = "01";
private final String IN = "11";
// opcode
private final String HLT = "0000";
private final String PRT = "0001";
private final String STO = "0010";
private final String LDA = "0011";
private final String ADD = "0100";
private final String SUB = "0101";
private final String MUL = "0110";
private final String DIV = "0111";
private final String JMP = "1000";
private final String JPZ = "1001";
private final String JPN = "1010";
private final String JPP = "1011";
private final String AND = "1100";
private final String OR = "1101";
private final String XOR = "1110";
public Generator() {
instructions = new LinkedList<>();
idTable = new LinkedList<>();
}
public void associate(Parser parser) {
this.parser = parser;
}
public boolean generate() {
Token root = parser.getParseTree();
for (Token child : root.children) {
List<String> block = statement(child, instructions.size());
if (block == null || checkNullContained(block))
return false;
instructions.addAll(block);
}
instructions.add(IM + HLT + toBinary(0));
return true;
}
private List<String> statement(Token node, int entryPoint) {
if (node.statement == Statement.DECLARATION) return declaration(node);
else if (node.statement == Statement.ASSIGNMENT) return assignment(node);
else if (node.statement == Statement.SELECTION) return selection(node, entryPoint);
else if (node.statement == Statement.ITERATION) return iteration(node, entryPoint);
else if (node.statement == Statement.PRINT) return print(node);
else if (node.symbol == Symbol.ENDWHILE || node.symbol == Symbol.ENDIF) return new LinkedList<>();
else {
System.out.println("Unknown Statement : " + node.statement);
System.out.printf("%-20s%-7s\n", "Code Generation", "KO :(");
return null;
}
}
private List<String> declaration(Token node) {
List<String> block = new LinkedList<>(expression(node.getChild(3)));
addIdentifier(node.getChild(0), node.getChild(1));
block.add(DI + STO + toBinary(node.getChild(1)));
return block;
}
private List<String> selection(Token node, int entryPoint) {
List<String> block = new LinkedList<>();
for (Token child : node.getChild(2).children)
block.addAll(statement(child, entryPoint + block.size() + 3));
int terminalPoint = entryPoint + block.size() + 4;
block.addAll(0, condition(node, terminalPoint));
return block;
}
private List<String> iteration(Token node, int entryPoint) {
List<String> block = new LinkedList<>();
for (Token child : node.getChild(2).children)
block.addAll(statement(child, entryPoint + block.size() + 3));
int terminalPoint = entryPoint + block.size() + 4;
block.add(IM + JMP + toBinary(entryPoint));
block.addAll(0, condition(node, terminalPoint));
return block;
}
private List<String> condition(Token node, int terminalPoint) {
List<String> block = new LinkedList<>();
Token leftOperand = node.getChild(1).getChild(0);
Token operator = node.getChild(1).getChild(1);
Token rightOperand = node.getChild(1).getChild(2);
if (leftOperand.symbol == Symbol.IDENTIFIER)
block.add(DI + LDA + toBinary(leftOperand));
else block.add(IM + LDA + toBinary(leftOperand));
if (rightOperand.symbol == Symbol.IDENTIFIER)
block.add(DI + SUB + toBinary(rightOperand));
else block.add(IM + SUB + toBinary(rightOperand));
if (operator.value.equals("!=")) operator.value = JPZ;
if (operator.value.equals(">")) operator.value = JPN;
if (operator.value.equals("<")) operator.value = JPP;
block.add(IM + operator.value + toBinary(terminalPoint));
return block;
}
private List<String> expression(Token node) {
List<String> block = new LinkedList<>();
if (node.children.size() == 1) {
if (node.getChild(0).symbol == Symbol.IDENTIFIER)
block.add(DI + LDA + toBinary(node.getChild(0)));
else block.add(IM + LDA + toBinary(node.getChild(0)));
return block;
}
Token leftOperand = node.getChild(0);
Token operator = node.getChild(1);
Token rightOperand = node.getChild(2);
if (leftOperand.symbol == Symbol.IDENTIFIER)
block.add(DI + LDA + toBinary(leftOperand));
else block.add(IM + LDA + toBinary(leftOperand));
if (node.children.size() > 1) {
if (operator.value.equals("+")) operator.value = ADD;
if (operator.value.equals("-")) operator.value = SUB;
if (operator.value.equals("*")) operator.value = MUL;
if (operator.value.equals("/")) operator.value = DIV;
if (operator.value.equals("&")) operator.value = AND;
if (operator.value.equals("|")) operator.value = OR;
if (operator.value.equals("^")) operator.value = XOR;
if (rightOperand.symbol == Symbol.IDENTIFIER)
block.add(DI + operator.value + toBinary(rightOperand));
else block.add(IM + operator.value + toBinary(rightOperand));
}
return block;
}
private List<String> assignment(Token node) {
List<String> block = new LinkedList<>(expression(node.getChild(2)));
block.add(DI + STO + toBinary(node.getChild(0)));
return block;
}
private List<String> print(Token node) {
List<String> block = new LinkedList<>();
if (node.getChild(1).symbol == Symbol.IDENTIFIER)
block.add(DI + PRT + toBinary(node.getChild(1)));
else block.add(IM + PRT + toBinary(node.getChild(1)));
return block;
}
private boolean checkNullContained(List<String> block) {
for (String line : block) {
if (line.contains("null"))
return true;
}
return false;
}
private void addIdentifier(Token type, Token id) {
Identifier identifier = new Identifier();
identifier.name = id.value;
identifier.type = type.value;
for (DataType dataType : DataType.values()) {
if (dataType.getName().equals(identifier.type)) {
identifier.size = dataType.getSize();
break;
}
}
if (idTable.isEmpty()) identifier.address = 0;
else {
Identifier lastId = idTable.get(idTable.size() - 1);
identifier.address = lastId.address + lastId.size;
}
idTable.add(identifier);
}
private String toBinary(Token token) {
Integer value = null;
if (token.symbol == Symbol.IDENTIFIER) {
for (Identifier id : idTable) {
if (id.name.equals(token.value)) {
value = id.address;
break;
}
}
} else value = Integer.parseInt(token.value);
if (value == null) {
System.out.println("Unknown Identifier : " + token.value);
System.out.printf("%-20s%-7s\n", "Code Generation", "KO :(");
return null;
}
return toBinary(value);
}
private String toBinary(int value) {
String operand = "";
operand += Integer.toBinaryString(value);
while (operand.length() < 26) operand = "0" + operand;
return operand;
}
Java
복사
Instruction set에 대한 설명은 생략하겠습니다. 기계어로 번역하는 과정 자체는 복잡하지 않지만 프로그램 카운터의 값을 변경하는 Jump 계열 명령어의 경우, 해당 Instruction Block의 진입지점과 종료 지점이 명시되어야 한다는 점만 유의하면 됩니다.
idTable은 Identifier를 저장하는 테이블입니다. 이곳에 저장되지 않은 Identifier를 통한 계산이 진행될 경우 Unknown Identifier 에러를 출력합니다.
Conclusion
사실 컴파일러의 구현보다 어려웠던 점은 프로그래밍 언어 설계였습니다. 왜 문맥 의존 문법과 무제약 문법으로는 프로그래밍 언어를 설계할 수 없는지, Instruction Set에 대한 내용도 포함하려고 했으나 글이 너무 길어지는 것 같아 생략하게 되었습니다. 추후에 기회가 되면 따로 글을 작성할 수 있도록 하겠습니다.
귀중한 시간 내어 긴 글 읽어주심에 감사드립니다.
모든 코드는 깃허브에 업로드 되어있습니다. 아래에 링크를 남겨드립니다.
(5월 1일 이후 Public으로 전환 예정입니다.)
