최근 학교 수업에서 컴파일러를 공부해볼 수 있는 기회가 생겼습니다. 본래 프로젝트 주제는 어셈블러와 MCU Emulator를 구현하고 어셈블러를 통해 컴파일된 목적코드를 MCU Emulator로 실행하는 것이었으나, 욕심이 생겨 간단한 고급 언어를 컴파일할 수 있는 컴파일러를 구현해보았습니다. 구현하기까지 공부했던 모든 내용을 담기에는 어려움이 있겠으나 컴파일 절차가 구체적으로 어떠하고, 어떻게 구현될 수 있는지에 대해서는 대략적으로 공유할 수 있을 것 같아 글을 남깁니다.
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();
}
}
제가 구현한 전처리기는 주석과 비어있는 라인을 제거하는 작업만 수행 합니다. 하지만 C언어 컴파일러와 같이 더 복잡한 컴파일러의 전처리기는 매크로 상수 및 함수, 프로토타입을 처리하는 등 더 많은 작업을 수행할 수 있습니다.
컴파일의 첫단계는 어휘 분석입니다. 그리고 어휘분석을 수행하는 모듈을 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]*$
이어 소스 코드는 아래와 같습니다.
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();
}
}
Scanner 클래스는 Whitespace를 구분자로 하여 구분된 문자열을 next 함수가 호출될 때마다 순차적으로 반환합니다. 이렇게 구분자로 구분된 하나의 문자열을 어휘소(Lexeme)라고 부릅니다. while, if, else, {, }, int, main… 이런 문자열들이 모두 어휘소가 됩니다. 어휘소가 어떤 심볼에 속하는 확인하기 위해 findSymbol함수를 호출합니다. findSymbol 함수는 사전에 정의된 심볼의 정규 문법을 통해 어휘소가 어떤 심볼에 속하는지 확인한 후에 해당 심볼을 반환합니다. 만약 어휘소가 어떤 심볼에도 속하지 않는다면 예외 메시지를 출력하고 false를 반환합니다.
심볼과 어휘소를 기본키로 하는 개체를 토큰이라고 부릅니다. 어휘소가 속한 심볼을 찾았다면 두 값을 기본키로 하는 토큰 인스턴스를 생성하여 심볼 테이블에 추가합니다. 심볼 테이블에 모든 토큰이 추가되었다면 Lexer의 역할은 끝이 납니다. 이렇게 만들어진 심볼 테이블은 다음 단계인 구문 분석에서 사용될 것입니다.
<aside> 💡 기본키(Primary key)는 개체를 식별할 수 있는 값입니다. 42Seoul의 카뎃분들을 예를 들면 인트라 아이디가 기본키가 될 수 있습니다. 반대로 이름은 기본키가 될 수 없습니다. 동명이인이 있을 수 있으니까요.
</aside>
어휘 분석을 통해 각 어휘소가 어떤 심볼에 속하는지 확인했습니다. 이제 할 일은 우리가 정의한 생성 규칙으로 문장을 만들어낼 수 있는지 확인하는 것입니다. 쉽게 말해 심볼들이 적절한 순서로 나열되어있는지 확인하겠다는 것입니다. 이 과정을 구문 분석이라고 부릅니다.
구문 분석은 철저하게 문맥 자유 문법의 Production Rule에 의해서 수행됩니다. 다음은 Production Rule을 바커스-나우르 폼으로 표현한 결과입니다.