[컴파일러 만들기] 3장 - 구문 분석

3.0 구문 분석

  - 구문 분석: 소스 코드의 구조를 분석하는 과정 (소스 코드 구조의 문과 식을 분석하는 것)

  - 소스 코드의 구조: 문과 식

    - 문: 복합문(다른 문 포함 가능 ex. for, if 문, ...)
           단일문(다른 문 포함 불가, ex. return, continue 문, ...)

    - 문은 식도 포함 가능 ex. if문의 조건식, return문의 반환식, ...

  - 문은 문과 식을 포함하고, 식은 식을 포함함

3.1 구문 트리와 노드

  - 구문 트리: 소스 코드의 구조를 분석해 문과 식의 포함관계를 트리로 표현한 것

                  (분석된 소스 코드의 구조를 표현하는 트리 자료구조)

  - 구문 분석 위해 가장 먼저 해야 할 것은 구문 트리를 구성할 노드 정의

    - 가장 먼저 정의할 노드 => 구문 트리의 루트 노드이자 소스 코드의 선언 영역을 표현하는 노드

  - 프로그램 노드; 함수 노드의 리스트 (멤버)

  - 모든 문 노드와 식 노드의 부모 노드

  - 함수의 정의; 함수 이름, 매개변수 이름 리스트, 실행할 문 리스트

  - return문; 반환식

  - 변수의 선언; 변수의 이름, 초기화식

  - for문; 변수의 선언, 조건식, 증감식, 실행할 문 리스트

  - break문과 continue문; 멤버 없음

  - if문; 조건식 리스트, 각 조건식의 결과가 참일 때 실행할 문 리스트의 리스트, 거짓일 때 실행할 문 리스트

  - print문과 printLine문; 개행 여부, 콘솔에 출력할 식 리스트

  - 식의 문; 식

    - 식은 항상 결과값을 남김

    - 문에 속한 식의 결과값은 문의 목적에 따라 소비됨

    - 소비되지 않는 식의 결과값을 임의로 소비시키기 위해 식을 감싸는 문 노드 필요

  - 논리 연산자 or, and; 왼쪽 식, 오른쪽 식

  - 관계 연산자와 산술 연산자; 연산자의 종류, 왼쪽 피연산자 식, 오른쪽 피연산자 식

    - 논리 연산자 or와 and 구분 이유 => 단락 평가 때문 (경우에 따라 왼쪽 식만 평가)

    - 관계 연산자, 산술 연산자는 항상 양쪽 식 모두 평가

  - 단항 연산자; 연산자의 종류, 하나의 피 연산자 식

  - 함수의 호출; 피연산자 식, 인자식 리스트

  - 배열과 맵의 원소 참조; 피연산자 식, 인덱스 식

  - 배열과 맵의 원소 수정; 피연산자 식, 인덱스 식, 초기화식

  - 변수의 참조; 변수의 이름

  - 변수의 수정; 변수의 이름, 초기화식

  - 널 리터럴, 불리언 리터럴, 숫자 리터럴, 스트링 리터럴

    - 멤버: 널 리터럴 노드는 멤버 없음, 불리언 리터럴 노드는 불리언 값,

             숫자 리터럴 노드는 실수 값, 스트링 리터럴 노드는 문자열 값

  - 배열 리터럴; 원소식 리스트

  - 맵 리터럴; 문자열과 원소식을 쌍으로 하는 맵

 

// Node.h

// 프로그램 노드
// 멤버: 함수 노드의 리스트
struct Program {
  vector<struct Function*> functions;
};

// 모든 문 노드와 식 노드의 부모 노드
struct Statement {};
struct Expression {};

// 함수의 정의
// 멤버: 함수 이름, 매개변수 이름 리스트, 실행할 문 리스트
struct Function: Statement {
  string name;
  vector<string> parameters;
  vector<Statement*> block;
};

// return문
// 멤버: 반환식
struct Return: Statement {
  Expression* expression;
};

// 변수의 선언
// 멤버: 변수의 이름, 초기화식
struct Variable: Statement {
  string name;
  Expression* expression;
};

// for문
// 멤버: 변수의 선언, 조건식, 증감식, 실행할 문 리스트
struct For: Statement {
  Variable* variable;
  Expression* condition;
  Expression* expression;
  vector<Statement*> block;
};

// break문과 continue문
// 멤버 없음
struct Break: Statement {};
struct Continue: Statement {};

// if문
// 멤버: 조건식 리스트, 각 조건식의 결과가 참일 때 실행할 문 리스트의 리스트, 거짓일 때 실행할 문 리스트
struct If: Statement {
  vector<Expression*> conditions;
  vector<vector<Statement*>> blocks;
  vector<Statement*> elseBlock;
};

// print문과 printLine문
// 멤버: 개행 여부, 콘솔에 출력할 식 리스트
struct Print: Statement {
  bool lineFeed = false;
  vector<Expression*> arguments;
};

// 식의 문
// 멤버: 식
struct ExpressionStatement: Statement {
  Expression* expression;
};

// 논리 연산자 or, and (이항 연산자)
// 멤버: 왼쪽 식, 오른쪽 식
struct Or: Expression {
  Expression* lhs; // left hand side
  Expression* rhs; // right hand side
};
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; // ex. add(1,2)
  vector<Expression*> arguments;
};

// 배열과 맵의 원소 참조
// 멤버: 피연산자 식, 인덱스 식
struct GetElement: Expression {
  Expression* sub; // ex. map['property']
  Expression* index; // ex. array[0]
};

// 배열과 맵의 원소 수정
// 멤버: 피연산자 식, 인덱스 식, 초기화 식
struct SetElement: Expression {
  Expression* sub; // ex. map['property'] = 3;
  Expression* index; // ex. array[0] = 3;
  Expression* value;
};

// 변수의 참조
// 멤버: 변수의 이름
struct GetVariable: Expression {
  string name;
};

// 변수의 수정
// 멤버: 변수의 이름, 초기화식
struct SetVariable: Expression {
  string name;
  Expression* value;
};

// 널 리터럴, 불리언 리터럴, 숫자 리터럴, 스트링 리터럴
// 멤버: 널 리터럴 노드는 없음, 불리언 리터럴 노드는 불리언 값
//      숫자 리터럴 노드는 실수 값, 스트링 리터럴 노드는 문자열 값
struct NullLiteral: Expression {};
struct BooleanLiteral: Expression {
  bool value = false;
};
struct NumberLiteral: Expression {
  double value = 0.0;
};
struct StringLiteral: Expression {
  string value;
};

// 배열 리터럴
// 멤버: 원소식 리스트
struct ArrayLiteral: Expression {
  vector<Expression*> values; // ex. [1, 2, 3]
};

// 맵 리터럴
// 멤버: 문자열과 원소식을 쌍으로 하는 맵
struct MapLiteral: Expression {
  map<string, Expression*> values; // ex. {'a': 1, 'b': 2}
};

3.2 구문 분석기

  - 구문 분석기: 소스 코드의 구문을 분석하는 프로그램, 토큰 리스트를 입력받아 구문 트리 출력

  - 선언 영역

  - 함수의 정의

  - 본문

  - 변수의 선언

  - 본문의 식

  - 식

    - 피연산자

    - 연산자; 단항 연산자, 이항 연산자

      - 이항 연산자에는 우선순위가 있음 (숫자 클수록 우선순위 높음)

      - 구문 트리는 자식 노드가 없는 잎 노드부터 차례로 계산하므로 우선 순위 낮은 연산자부터 분석 필요

      - 우선순위가 높은 연산자는 먼저 계산되어야 하므로 우선순위 높은 연산자일수록 잎에 가까운 위치에 자리

    - 식에서 가장 먼저 분석되어야 할 연산자는 우선순위가 가장 낮은 연산자

  - 대입 연산자

  - 논리 Or 연산자

 

// Main.cpp

// 구문 분석 함수
auto parse(vector<Token>) -> Program*;

auto main() -> void {
  string sourceCode = R""""(
    function main() {
      printLine 'Hello, World!';
      printLine 1 + 2 * 3;
    }
  )"""";
  auto tokenList = scan(sourceCode);
  auto syntaxTree = parse(tokenList);

  // parse() 함수 반환한 구문 트리의 내용을 콘솔에 출력
  printSyntaxTree(syntaxTree);
}

---

// Parser.cpp

static vector<Token>::iterator current;

// 토큰 리스트를 처음부터 끝까지 토큰 단위로 순회하며 구문 트리 구성
auto parse(vector<Token> tokens) -> Program* {
  auto result = new Program();
  // 전역 변수 current가 매개변수로 받은 토큰 리스트의 첫 번째 토큰 가리킴
  current = tokens.begin();
  // 순회 끝나면 구문 트리의 루트 노드 반환 (result)
  while (current -> kind != Kind::EndOfToken) {
    switch (current -> kind) {
      case Kind::Function: {
        // 함수 정의 분석하고 반환받은 함수 노드를 프로그램 노드에 추가
        result -> functions.push_back(parseFunction());
        break;
      }
      default:
        cout << *current << " 잘못된 구문입니다.";
        exit(1);
    }
  }
  return result;
}

auto parseFunction() -> Function* {
  auto result = new Function();
  // Function 토큰은 함수 정의 시작을 나타내는 토큰일 뿐이므로 무시
  // 함수 노드 생성 후 현재 토큰 버림
  skipCurrent(Kind::Function);
  // 현재 토큰의 문자열을 앞서 생성한 함수 노드에 설정 후 현재 토큰 건너뜀
  result -> name = current -> string;
  skipCurrent(Kind::Identifier);
  // 매개변수 목록에서 괄호나 콤마와 같은 구분자는 건너뛰면서
  // 매개변수들의 이름을 함수 노드의 매개변수 리스트에 추가
  skipCurrent(Kind::LeftParen);
  if (current -> kind != Kind::RightParen) {
    do {
      result -> parameters.push_back(current -> string);
      skipCurrent(Kind::Identifier);
    } while (skipCurrentIf(Kind::Comma));
  }
  skipCurrent(Kind::RightParen);
  // 함수 본문의 앞/뒤 괄호는 건너뜀
  skipCurrent(Kind::LeftBrace);
  // 함수 본문 리스트를 함수 노드에 저장
  result -> block = parseBlock();
  skipCurrent(Kind::RightBrace);
  return result;
}

auto skipCurrent(Kind kind) -> void {
  // 매개변수로 받은 토큰이 현재 토큰과 같지 않으면 프로그램 종료
  if (current -> kind != kind) {
    cout << toString(kind) + " 토큰이 필요합니다.";
    exit(1);
  }
  // 같으면 현재 토큰 건너뜀 (무시)
  current++;
}

auto parseBlock() -> vector<Statement*> {
  vector<Statement*> result;
  while (current -> kind != Kind::RightBrace) {
    switch (current -> kind) {
      case Kind::Variable:
        result.push_back(parseVariable());
        break;
      case Kind::EndOfToken:
        cout << *current << " 잘못된 구문입니다.";
        exit(1);
      // 현재 토큰이 특정 키워드가 아닐 때를 식의 시작으로 간주 (별도 키워드 없음)
      default:
        result.push_back(parseExpressionStatement());
        break;
    }
  }
  return result;
}

// 변수의 선언 분석하는 함수
auto parseVariable() -> Variable* {
  // var 키워드 무시 (변수 선언 노드 생성하고 현재 토큰 건너뜀)
  auto result = new Variable();
  skipCurrent(Kind::Variable);
  // var 키워드 다음에는 변수의 이름인 식별자 토큰
  // 현재 토큰의 문자열을 변수 선언 노드의 이름으로 설정하고 현재 토큰 건너뜀
  result -> name = current -> string;
  skipCurrent(Kind::Identifier);
  // 변수 초기화 강제
  skipCurrent(Kind::Assignment);
  // 변수 선언 노드의 초기화 식으로 설정
  result -> expression = parseExpression();
  // 단일문 => 끝 표시하는 문자 필요 (세미콜론 또는 개행)
  skipCurrent(Kind::Semicolon);
  return result;
}

// 식을 분석하고 반환받은 식 노드를 식의 문 노드로 감싸서 반환
auto parseExpressionStatement() -> ExpressionStatement* {
  auto result = new ExpressionStatement();
  result -> expression = parseExpression();
  skipCurrent(Kind::Semicolon);
  return result;
}

// 식 분석 함수; 우선순위 가장 낮은 대입 연산자부터 분석 시작
auto parseExpression() -> Expression* {
  return parseAssignment();
}

auto parseAssignment() -> Expression* {
  // or 연산자가 대입 연산자보다 우선순위 한 단계 더 높음
  auto result = parseOr();
  // 왼쪽 식 분석 끝나면 대입 연산자보다 우선순위 높은 연산자들의 분석은 모두 끝난 상태
  // 현재 토큰이 대입 연산자 아니면 식이 끝난 것으로 간주
  if (current -> kind != Kind::Assignment)
    return result;
  skipCurrent(Kind::Assignment);
  // 대입 연산자 왼쪽 식으로 참조 가능한 변수가 옴
  if (auto getVariable = dynamic_cast<GetVariable*>(result)) {
    auto result = new SetVariable();
    result -> name = getVariable -> name;
    // 재귀 호출 이유; 대입 연산자는 우측 결합 연산자임
    result -> value = parseAssignment();
    return result;
  }
  // 대입 연산자 왼쪽 식으로 배열이나 맵의 원소 참조도 있음
  if (auto getElement = dynamic_cast<GetElement*>(result)) {
    auto result = new SetElement();
    result -> sub = getElement -> sub; // 피연산자 식
    result -> index = getElement -> index; // 인덱스 식
    // 대입 연산자가 구문 트리에서 루트 노드임
    result -> value = parseAssignment();
    return result;
  }
  cout << "잘못된 대입 연산 식입니다.";
  exit(1);
}

auto parseOr() -> Expression* {
  // or 연산자 보다 and 연산자가 우선순위 한 단계 더 높음 (왼쪽 피연산자 식 분석 위함)
  auto result = parseAnd();
  // 연속된 or 연산자들 분석위함
  while (skipCurrentIf(Kind::LogicalOr)) {
    // or 연산자는 왼쪽 결합 연산자임 (재귀 호출 안함)
    // 왼쪽 식 먼저 평가 후 오른쪽 식 평가
    auto temp = new Or();
    temp -> lhs = result;
    temp -> rhs = parseAnd();
    result = temp;
  }
  return result;
}

3.3 마치며

  - 구문 분석은 컴파일 과정의 두번째 단계

  - 구문 분석은 소스 코드의 구조를 분석하는 것

  - 소스 코드의 구조를 표현하는 트리 => 구문 트리

  - 소스 코드의 구조는 문과 식으로 구성됨

  - 문은 문과 식을 포함하고, 식은 식을 포함함

  - 연산자에는 우선 순위가 있음

  - 연산자의 우선 순위가 높을수록 구문 트리의 잎에 가깝게 위치

  - 구문 트리는 자식이 없는 잎 노드부터 평가

  - 연산자에는 결합 방향이 있고, 결합 방향에는 왼쪽과 오른쪽이 있음

  - 결합 방향이 왼쪽인 연산자는 구문 트리를 왼쪽으로 키우고 왼쪽부터 계산

  - 결합 방향이 오른쪽인 연산자는 구문 트리를 오른쪽으로 키우고 오른쪽부터 계산

  - 구문 분석기는 소스 코드의 구조를 분석하는 구문 분석 프로그램

  - 구문 분석기의 입력은 토큰 리스트, 출력은 구문 트리

---

[Source Code] 구문 트리와 노드 (Node.h)

 

[Source Code] 구문 분석기 (Main.cpp)

[Source Code] 구문 분석기 (Parser.cpp)

 

 

p.s) parenthesis (소괄호), brace (중괄호), bracket (대괄호)