[컴파일러 만들기] 2. Parser 만들기

머윤 2025. 3. 18. 22:47

2025. 3. 18. 22:47

[컴파일러 만들기] 1. Scanner 만들기

Scanner 만들기한글로 된 언어를 만들거라, Korlang 이라고 이름을 지었다.https://github.com/Yoon6/korlang GitHub - Yoon6/korlang: korlang compiler.korlang compiler. Contribute to Yoon6/korlang development by creating an account on GitH

yoonda.tistory.com

Parser 만들기

Parser란?

Parser에서는 syntax analysis를 수행한다.
작성한 소스 코드의 구조를 분석하는 과정이다.
- 문법에 맞는지 검사하고,Parser Tree를 만든다.
- 에러 처리를 한다.
- symbol 테이블을 만든다.

https://www.geeksforgeeks.org/introduction-to-syntax-analysis-in-compiler-design/

Introduction to Syntax Analysis in Compiler Design - GeeksforGeeks

Syntax analysis, or parsing, is a crucial step in compiler design that verifies the grammatical structure of source code by interpreting tokens produced during lexical analysis and constructing a parse tree or abstract syntax tree while detecting syntax er

www.geeksforgeeks.org

CFG, LL Parser, LR Parser 등의 개념은 잘 모르겠다.
- 더 공부해서 추가 포스팅 올리기

문과 식

문 -> Statement
식 -> Expression

Expression

평가가 가능해서 하나의 값으로 표현되는 '식'을 말한다.

// 계산식
1 + 2 * 3 
a + b 

// 배열 연산자
arr[1]

// 함수 콜
getValue()

이런 애들을 Expression이라고 한다.

Statement

실행가능한 코드 조각을 말한다.
- Expression도 Statement라고 볼 수 있다.

복합문과 단일문으로 구분되며, for/if 처럼 다른 문을 포함할 수 있는 문을 복합문, return/continue 처럼 다른 문을 포함할 수 없는 문을 단일문이라고 한다.

1. Parser Tree 의 Node 만들기

가장 먼저 root 노드를 만들어주자.

Node.h

#ifndef KORLANG_NODE_H
#define KORLANG_NODE_H

#include "Kind.h"

struct Statement {};
struct Expression {};

typedef struct Function: Statement {
    wstring name;
    vector<wstring> parameters;
    vector<Statement> blocks;
} Function;

struct Program {
    vector<Function*> functions;
};

#endif //KORLANG_NODE_H

책의 사양대로 따라했기 때문에, Program(Root Node)에서는 함수의 정의만 포함하고 있다.
- 함수 호출은 Expression(식)이고, 함수 정의는 Statement(문)이다.

struct Return : Statement {
    Expression* expression;
};

반환문은 반환식을 포함한다.

struct Variable : Statement {
    wstring name;
    Expression *expression;
};

변수의 선언식이다.
변수의 이름과 초기화식을 포함한다.

struct For : Statement {
    Variable *variable;
    Expression *condition;
    Expression *expression;
    vector<Statement *> blocks;
};

변수 선언, 조건식, 증감식, 실행문 리스트를 포함한다.

이런 방식으로 언어에서 사용하는 Statement, Expression들을 추가해준다.

#ifndef KORLANG_NODE_H
#define KORLANG_NODE_H

#include "Kind.h"

struct Statement {};
struct Expression {};

typedef struct Function : Statement {
    wstring name;
    vector<wstring> parameters;
    vector<Statement> blocks;
} Function;

struct Program {
    vector<Function*> functions;
};

struct Return : Statement {
    Expression* expression;
};

struct Variable : Statement {
    wstring name;
    Expression* expression;
};

struct For : Statement {
    Variable* variable;
    Expression* condition;
    Expression* expression;
    vector<Statement*> blocks;
};

struct Break : Statement {};
struct Continue : Statement {};

struct If : Statement {
    vector<Expression*> conditions;
    vector<Statement*> blocks;
    vector<Statement*> elseBlock;
};

struct Print : Statement {
    vector<Expression*> arguments;
};

struct ExpressionStatement : Statement {
    Expression* expression;
};

struct Or : Expression {
    Expression* lhs;
    Expression* rhs;
};

struct And : Expression {
    Expression* lhs;
    Expression* rhs;
};

struct Relational : Expression {
    Kind kind;
    Expression* lhs;
    Expression* rhs;
};

struct Arithmetic : Expression {
    Kind kind;
    Expression* lhs;
    Expression* rhs;
};

struct Unary : Expression {
    Kind kind;
    Expression* sub;
};

struct Call : Expression {
    Expression* sub;
    vector<Expression*> arguments;
};

// 배열, map 원소의 참조
// arr[0]
struct GetElement : Expression {
    Expression* sub;
    Expression* index;
};

// arr[0] = 3; 
// 할당은 statement 아닌가?
struct SetElement : Expression {
    Expression* sub;
    Expression* index;
    Expression* value;
};

// 변수 참조
struct GetVariable : Expression {
    wstring name;
};

// 변수 수정
struct SetVariable : Expression {
    wstring name;
    Expression* value;
};

struct NullLiteral : Expression {};
struct BooleanLiteral : Expression {
    bool value = false;
};
struct NumberLiteral : Expression {
    double value = 0.0;
};
struct StringLiteral : Expression {
    wstring value;
};
struct ArrayLiteral : Expression {
    vector<Expression*> values;
};
struct MapLiteral : Expression {
    map<wstring, Expression*> values;
};
#endif //KORLANG_NODE_H

2. Parse 함수 만들기

main.cpp

vector<Token> scan(string sourceCode);
Program* parse(vector<Token> tokenList);
auto printTokenList(vector<Token>) -> void;
auto printSyntaxTree(Program*) -> void;

int main() {
    string sourceCode = R"(
        함수 시작() {
            출력("안녕");
            출력("\n");
            출력(1 + 2 * 3);
            출력("\n");
        }
    )";

    vector<Token> tokenList = scan(sourceCode);
	Program* syntaxTree = parse(tokenList);

    printSyntaxTree(syntaxTree);
    //printTokenList(tokenList);

    return 0;
}

main 함수에서 parsing을 하고, 트리를 출력해준다.

Parser.cpp

#include <vector>

#include "Node.h"
#include "Token.h"

static vector<Token>::iterator currentToken;

Program* parse(vector<Token> tokenList) {
	auto result = new Program();

	currentToken = tokenList.begin();

	while (currentToken->kind != Kind::EndOfLine)
	{
		switch (currentToken->kind)
		{
		case Kind::Function:
			result->functions.push_back(parseFunction());
			break;
		default:
			cout << *currentToken << " 잘못된 구문입니다.";
			exit(1);
		}
	}


	return result;
}

현재 스펙 상, 프로그램에 포함될 수 있는 것은 함수 밖에 없다.
그래서 parse 함수는 이걸로 끝이다.

bool skipCurrentIf(Kind kind)
{
	if (currentToken->kind != kind)
	{
		return false;
	}

	currentToken++;
	return true;
}

void skipCurrent(Kind kind)
{
	std::wstring_convert<std::codecvt_utf8_utf16<wchar_t>> converter;
	if (currentToken->kind != kind)
	{
		cout << converter.to_bytes(toString(kind)) << " 토큰이 필요합니다.";
		exit(1);
	}
	currentToken++;
}

vector<Statement*> parseBlock()
{

}

Function* parseFunction()
{
	auto result = new Function();
	skipCurrent(Kind::Function);

	// function name
	result->name = currentToken->string;
	skipCurrent(Kind::Identifier);

	// (
	skipCurrent(Kind::LeftParen);

	// parameters
	if (currentToken->kind != Kind::RightParen)
	{
		do
		{
			result->parameters.push_back(currentToken->string);
			skipCurrent(Kind::Identifier);
		}
		while (skipCurrentIf(Kind::Comma));
	}

	// )
	skipCurrent(Kind::RightParen);
	// {
	skipCurrent(Kind::LeftBrace);
	// body
	result->blocks = parseBlock();
	// }
	skipCurrent(Kind::RightBrace);

	return result;
}

parseFunction() 함수를 작성해주었다.

vector<Statement*> parseBlock()
{
	vector<Statement*> result;

	while (currentToken->kind != Kind::RightBrace)
	{
		switch (currentToken->kind)
		{
		case Kind::Variable:
			result.push_back(parseVariable());
			break;
		case Kind::For:
			result.push_back(parseFor());
			break;
		case Kind::If:
			result.push_back(parseIf());
			break;
		case Kind::Print:
			result.push_back(parsePrint());
			break;
		case Kind::Return:
			result.push_back(parseReturn());
			break;
		case Kind::Break:
			result.push_back(parseBreak());
			break;
		case Kind::Continue:
			result.push_back(parseContinue());
			break;
		case Kind::EndOfLine:
		case Kind::Unknown:
			cout << *currentToken << " 잘못된 구문입니다.";
			exit(1);
		}
	}

	return result;
}

parseBlock()을 만들어준다.
korlang 사양으로는 함수만 프로그램에 포함 가능하고, 모든 동작이 함수 안에서 일어나므로, parseBlock()만 이해하면 된다.
Block 안에 있는 노드들은 모드 Statement(문) 이다.

나머지 statement parse 함수들도 작성해주자.

Variable* parseVariable()
{
	auto result = new Variable();
	// `변수` 키워드를 건너뛴다.
	skipCurrent(Kind::Variable);

	result->name = currentToken->string;
	// skip variable name
	skipCurrent(Kind::Identifier);

	// skip =
	skipCurrent(Kind::Assignment);

	result->expression = parseExpression();

	// skip ;
	skipCurrent(Kind::Semicolon);

	return result;
}

For* parseFor()
{
	auto result = new For();

	// skip '반복'
	skipCurrent(Kind::For);

	result->variable = new Variable();
	result->variable->name = currentToken->string;

	// skip variable name
	skipCurrent(Kind::Identifier);
	// skip =
	skipCurrent(Kind::Assignment);
	result->variable->expression = parseExpression();

	if (result->variable->expression == nullptr)
	{
		cout << "for문에 초기화 식이 없습니다.";
		exit(1);
	}

	// skip ;
	skipCurrent(Kind::Semicolon);
	result->condition = parseExpression();
	if (result->condition == nullptr)
	{
		cout << "for문에 조건식이 없습니다.";
		exit(1);
	}

	// skip ;
	skipCurrent(Kind::Semicolon);
	result->expression = parseExpression();
	if (result->expression == nullptr)
	{
		cout << "for문에 증감식이 없습니다.";
		exit(1);
	}

	// skip {
	skipCurrent(Kind::LeftBrace);
	result->blocks = parseBlock();
	// skip }
	skipCurrent(Kind::RightBrace);

	return result;
}

If* parseIf()
{
	auto result = new If();
	
	// skip '만약'
	skipCurrent(Kind::If);
	do
	{
		auto condition = parseExpression();
		if (condition == nullptr)
		{
			cout << "if문에 조건식이 없습니다.";
			exit(1);
		}
		result->conditions.push_back(condition);
		// skip {
		skipCurrent(Kind::LeftBrace);
		result->blocks.push_back(parseBlock());
		// skip }
		skipCurrent(Kind::RightBrace);
	}
	while (skipCurrentIf(Kind::Elif));

	if (skipCurrentIf(Kind::Else))
	{
		// skip {
		skipCurrent(Kind::LeftBrace);
		result->elseBlock = parseBlock();
		// skip }
		skipCurrent(Kind::RightBrace);
	}

	return result;
}

Print* parsePrint()
{
	auto result = new Print();
	// skip '출력'
	skipCurrent(Kind::Print);
	// skip (
	skipCurrent(Kind::LeftParen);

	// 하나의 식만 출력 가능
	result->arguments.push_back(parseExpression());

	// skip )
	skipCurrent(Kind::RightParen);
	// skip ;
	skipCurrent(Kind::Semicolon);


	return result;
}

Return* parseReturn()
{
	auto result = new Return();

	// skip '반환'
	skipCurrent(Kind::Return);

	result->expression = parseExpression();
	if (result->expression == nullptr)
	{
		cout << "반환문에 반환값이 없습니다.";
		exit(1);
	}

	// skip ;
	skipCurrent(Kind::Semicolon);

	return result;
}

Break* parseBreak()
{
	auto result = new Break();
	// skip '끊기'
	skipCurrent(Kind::Break);
	// skip ;
	skipCurrent(Kind::Semicolon);

	return result;
}

Continue* parseContinue()
{
	auto result = new Continue();
	// skip '계속하기'
	skipCurrent(Kind::Continue);
	// skip ;
	skipCurrent(Kind::Semicolon);

	return result;
}

ExpressionStatement* parseExpressionStatement()
{
	auto result = new ExpressionStatement();
	result->expression = parseExpression();
	skipCurrent(Kind::Semicolon);
	return result;
}

이렇게 모든 Statement의 parse 함수를 작어하였다.
이제 expression을 파싱해보자.

Expression

Expression 안에는
- 연산자
  - 피연산자
  - 연산자
    - 단항 연산자
    - 이항 연산자
- 피연산자

가 있다.

연산자에는 우선순위가 있는데 다음과 같다.

우선순위가 높은 연산자가 가장 먼저 연산된다.

* 높다 -> 1위가 가장 높음. 6위가 가장 낮음.

우선순위	연산자	종류	결합 방향
1	후위 () [] 연산자	단항연산자	왼쪽
2	전위 + - 연산자	단항연산자	오른쪽
3	산술 * / % 연산자	이항연산자	왼쪽
4	산술 + - 연산자	이항연산자	왼쪽
5	관계 연산자	이항연산자	왼쪽
6	논리 AND 연산자	이항연산자	왼쪽
7	논리 OR 연산자	이항연산자	왼쪽
8	대입 연산자	이항연산자	오른쪽

구문트리를 만들 때는, 말단의 노드부터 차례대로 연산하기 때문에(bottom-up) 우선순위가 낮은 연산자부터 계산해야한다.

Expression* parseAssignment()
{
	// = 대입 연산자
	// 1. 왼쪽 피연산자부터 파싱
	auto result = parseOr();

	if (currentToken->kind != Kind::Assignment)
	{
		return result;
	}

	// skip =
	skipCurrent(Kind::Assignment);

	// GetVariable -> 참조 변수 타입
	GetVariable* variable = dynamic_cast<GetVariable*>(result);
	if (variable != nullptr)
	{
		SetVariable* result = new SetVariable();
		result->name = variable->name;
		result->value = parseAssignment();
		return result;
	}

	// GetElement -> 배열, map 원소 참조 타입
	GetElement* element = dynamic_cast<GetElement*>(result);
	if (element != nullptr)
	{
		SetElement* result = new SetElement();
		result->sub = element->sub;
		result->index = element->index;
		result->value = parseAssignment();
		return result;
	}

	cout << "대입 연산자의 왼쪽 피연산자가 변수나 배열, map 원소 참조가 아닙니다.";
	exit(1);
}

Expression* parseExpression()
{
	return parseAssignment();
}

parseExpression()에서는 순위가 가장 낮은 대입연산자 parseAssignment 처리 부터 해준다.
parseAssignment에서는 그 다음으로 순위가 낮은 OR연산자 parseOr을 수행한다.
왼쪽 피연산자를 알아내고, GetVariable(변수), GetElement(배열, 맵)인지 확인한다.
- 그리고 재귀적으로 parseAssignment를 호출한다.
  - 재귀적으로 호출하는 이유 -> 대입 연산자는 우측 결합 연산자이기 때문.
    - a = arr[1] = b = 3;
      - 이런 식이 있을 때, b = 3이 가장 먼저 연산되고, arr[1] = b, a = arr[1] 순서대로 연산되기 때문이다.

Expression* parseOr()
{
	auto result = parseAnd();

	while (skipCurrentIf(Kind::LogicalOr))
	{
		auto temp = new Or();
		temp->lhs = result;
		temp->rhs = parseAnd();
		result = temp; // { { parseAnd() || parseAnd() } || parseAnd() } || parseAnd() ...
	}

	return result;
}

parseOr()는 이렇게 만든다.
OR연산자가 나올 때 까지 누적해서 Or expression을 만든다.
parseAssignment()와 달리 반복문으로 하는 이유
- OR연산은 왼쪽 결합 연산자이기 때문이다.
  - a 또는 b 또는 c
  - 라는 식이 있을 때, a 또는 b부터 계산이 되어야한다.

이렇게 나머지 Expression parsing 함수도 작성해보자.

Expression* parseElement(Expression* sub)
{
	auto result = new GetElement();
	result->sub = sub;

	// skip [
	skipCurrent(Kind::LeftBraket);

	// index 계산
	result->index = parseExpression();

	// skip ]
	skipCurrent(Kind::RightBraket);

	return result;
}

Expression* parseCall(Expression* sub)
{
	auto result = new Call();
	result->sub = sub;

	// skip (
	skipCurrent(Kind::LeftParen);

	// 파라미터 추가
	if (currentToken->kind != Kind::RightParen)
	{
		do
		{
			result->parameters.push_back(parseExpression());
		} while (skipCurrentIf(Kind::Comma));
	}
	// skip )
	skipCurrent(Kind::RightParen);
	return result;
}

Expression* parsePostfix(Expression* sub)
{
	while (true)
	{
		switch (currentToken->kind)
		{
		case Kind::LeftParen:
			sub = parseCall(sub);
			break;
		case Kind::LeftBraket:
			sub = parseElement(sub);
			break;
		default:
			return sub;
		}
	}
}


Expression* parseNullLiteral()
{
	skipCurrent(Kind::NullLiteral);
	auto result = new NullLiteral();
	return result;
}

Expression* parseBooleanLiteral()
{
	auto result = new BooleanLiteral();
	result->value = currentToken->kind == Kind::TrueLiteral;
	skipCurrent(currentToken->kind);
	return result;
}

Expression* parseNumberLiteral() 
{
	auto result = new NumberLiteral();
	result->value = stod(currentToken->string);
	skipCurrent(Kind::NumberLiteral);
	return result;
}

Expression* parseStringLiteral()
{
	auto result = new StringLiteral();
	result->value = currentToken->string;
	skipCurrent(Kind::StringLiteral);
	return result;
}

Expression* parseListLiteral()
{
	auto result = new ArrayLiteral();
	// skip [
	skipCurrent(Kind::LeftBraket);

	if (currentToken->kind != Kind::RightBraket)
	{
		do
		{
			result->values.push_back(parseExpression());
		} while (skipCurrentIf(Kind::Comma));
	}

	// skip ]
	skipCurrent(Kind::RightBraket);
	return result;
}

Expression* parseMapLiteral()
{
	auto result = new MapLiteral();
	// skip {
	skipCurrent(Kind::LeftBrace);

	if (currentToken->kind != Kind::RightBrace)
	{
		do
		{
			wstring name = currentToken->string;
			skipCurrent(Kind::StringLiteral);
			skipCurrent(Kind::Colon);

			auto value = parseExpression();
			result->values[name] = value;
		} while (skipCurrentIf(Kind::Comma));
	}

	// skip }
	skipCurrent(Kind::RightBrace);
	return result;
}

Expression* parseIdentifier() 
{
	auto result = new GetVariable();
	result->name = currentToken->string;
	skipCurrent(Kind::Identifier);
	return result;
}

Expression* parseInnerExpression()
{
	skipCurrent(Kind::LeftParen);
	auto result = parseExpression();
	skipCurrent(Kind::RightParen);
	return result;
}


Expression* parseOperand()
{
	Expression* result = nullptr;
	switch (currentToken->kind)
	{
	case Kind::NullLiteral:   result = parseNullLiteral();      break;
	case Kind::TrueLiteral:
	case Kind::FalseLiteral:  result = parseBooleanLiteral();   break;
	case Kind::NumberLiteral: result = parseNumberLiteral();    break;
	case Kind::StringLiteral: result = parseStringLiteral();    break;
	case Kind::LeftBraket:    result = parseListLiteral();      break;
	case Kind::LeftBrace:     result = parseMapLiteral();       break;
	case Kind::Identifier:    result = parseIdentifier();       break;
	case Kind::LeftParen:     result = parseInnerExpression();  break;
	default:                  cout << "잘못된 식입니다.";       exit(1);
	}

	return parsePostfix(result);
}

Expression* parseUnary()
{
	set<Kind> operators = {
		Kind::Add,
		Kind::Subtract,
	};
	while (operators.count(currentToken->kind))
	{
		auto temp = new Unary();
		temp->kind = currentToken->kind;
		skipCurrent(currentToken->kind);
		temp->sub = parseUnary();
		return temp;
	}

	return parseOperand();
}

Expression* parseArithmetic2()
{
	set<Kind> operators = {
	Kind::Multiply,
	Kind::Divide,
	Kind::Modulo,
	};
	auto result = parseUnary();

	while (operators.count(currentToken->kind))
	{
		auto temp = new Arithmetic();
		temp->kind = currentToken->kind;
		skipCurrent(currentToken->kind);
		temp->lhs = result;
		temp->rhs = parseUnary();
		result = temp;
	}

	return result;
}

Expression* parseArithmetic1()
{
	set<Kind> operators = {
		Kind::Add,
		Kind::Subtract,
	};
	auto result = parseArithmetic2();

	while (operators.count(currentToken->kind))
	{
		auto temp = new Arithmetic();
		temp->kind = currentToken->kind;
		skipCurrent(currentToken->kind);
		temp->lhs = result;
		temp->rhs = parseArithmetic2();
		result = temp;
	}

	return result;
}

Expression* parseRelational() // <, >, == ...
{
	set<Kind> operators = {
		Kind::Equal,
		Kind::NotEqual,
		Kind::LessThan,
		Kind::GreaterThan,
		Kind::LessOrEqual,
		Kind::GreaterOrEqual,
	};
	auto result = parseArithmetic1();

	while (operators.count(currentToken->kind))
	{
		auto temp = new Relational();
		temp->kind = currentToken->kind;
		skipCurrent(currentToken->kind);
		temp->lhs = result;
		temp->rhs = parseArithmetic1();
		result = temp;
	}

	return result;
}

Expression* parseAnd()
{
	auto result = parseRelational();

	while (skipCurrentIf(Kind::LogicalAnd)) 
	{
		auto temp = new And();
		temp->lhs = result;
		temp->rhs = parseRelational();
		result = temp; // { { parseEquality() && parseEquality() } && parseEquality() } && parseEquality() ...
	}

	return result;

}

Print 함수를 만들어서 출력하면 아래와 같이 나온다.

소스코드

함수 시작() {
    출력("안녕");
    출력("\n");
    출력(1 + 2 * 3);
    출력("\n");
}

결과

FUNCTION 시작:
  BLOCK:
    PRINT:
      "안녕"
    PRINT:
      "\n"
    PRINT:
      +:
        LHS:
          1
        RHS:
          *:
            LHS:
              2
            RHS:
              3
    PRINT:
      "\n"

참고 자료

https://shoark7.github.io/programming/knowledge/expression-vs-statement

728x90

저작자표시 비영리

'CS > 컴파일러' 카테고리의 다른 글

[컴파일러 만들기] 4. 가상머신 만들기 (1)	2025.04.08
[컴파일러 만들기] 3. Generator 만들기 (0)	2025.03.26
[컴파일러 만들기] 1. Scanner 만들기 (0)	2025.03.16
[컴파일러 만들기] C++로 컴파일러 만들어보기 (0)	2025.03.11

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Valuable