[컴파일러 만들기] 2장 - 어휘 분석

2.0 어휘 분석

  - 어휘 분석: 프로그래밍 언어로 작성한 소스 코드 문자열의 어휘를 분석하는 과정

  - 소스 코드 문자열: 키워드, 식별자, 연산자, 구분자, 숫자 리터럴, 문자열 리터럴

2.1 어휘와 토큰

  - 가장 먼저 해야 할 일 => 소스 코드에 사용되는 어휘 정의

    - 어휘의 종류를 열거형으로 나열 (열거형의 멤버 => 문자열 대신할 상수)

  - 소스 코드 문자열에 포함된 어휘 문자열들을 열거형의 멤버들과 연관시키기 위해 연관 데이터도 작성

  - 토큰: 어휘의 종류와 문자열을 묶은 것

    - ex. 키워드 for 토큰 => 문자열: 'for', 종류: Kind::For

  - 토큰 구조체 작성 (쌍이 되는 어휘의 종류와 문자열을 묶어 다루기 위함)

  - 어휘 분석의 결과는 토큰 구조체의 리스트

 

// Kind.h

// 어휘의 종류를 열거형으로 나열
enum class Kind {
  Unknown, EndOfToken,
  NullLiteral,
  TrueLiteral, FalseLiteral,
  NumberLiteral, StringLiteral,
  Identifier,

  Function, Return,
  Variable,
  For, Break, Continue,
  If, Elif, Else,
  Print, PrintLine,

  LogicalAnd, LogicalOr,
  Assignment,
  Add, Subtract,
  Multiply, Divide, Modulo,
  Equal, NotEqual,
  LessThan, GreaterThan,
  LessOrEqual, GreaterOrEqual,

  Comma, Colon, Semicolon,
  LeftParen, RightParen,
  LeftBrace, RightBrace,
  LeftBraket, RightBraket,
};

auto toKind(string) -> Kind;

---

// Kind.cpp

// 어휘 문자열들을 열거형의 멤버들과 연관시킬 연관 데이터
static map<string, Kind> stringToKind = {
  {"#unknown",    Kind::Unknown},
  {"#EndOfToken", Kind::EndOfToken},

  {"null",        Kind::NullLiteral},
  {"true",        Kind::TrueLiteral},
  {"false",       Kind::FalseLiteral},
  {"#Number",     Kind::NumberLiteral},
  {"#String",     Kind::StringLiteral},
  {"#identifier", Kind::Identifier},
  {"function",    Kind::Function},
  {"return",      Kind::Return},
  {"var",         Kind::Variable},
  {"for",         Kind::For},
  {"break",       Kind::Break},
  {"continue",    Kind::Continue},
  {"if",          Kind::If},
  {"elif",        Kind::Elif},
  {"else",        Kind::Else},
  {"print",       Kind::Print},
  {"printLine",   Kind::PrintLine},
  
  {"and",         Kind::LogicalAnd},
  {"or",          Kind::LogicalOr},

  {"=",           Kind::Assignment},
  
  {"+",           Kind::Add},
  {"-",           Kind::Subtract},
  {"*",           Kind::Multiply},
  {"/",           Kind::Divide},
  {"%",           Kind::Modulo},

  {"==",          Kind::Equal},
  {"!=",          Kind::NotEqual},
  {"<",           Kind::LessThan},
  {">",           Kind::GreaterThan},
  {"<=",          Kind::LessOrEqual},
  {">=",          Kind::GreaterOrEqual},

  {",",           Kind::Comma},
  {":",           Kind::Colon},
  {";",           Kind::Semicolon},
  {"(",           Kind::LeftParen},
  {")",           Kind::RightParen},
  {"{",           Kind::LeftBrace},
  {"}",           Kind::RightBrace},
  {"[",           Kind::LeftBraket},
  {"]",           Kind::RightBraket},
};

// 매개변수로 받은 문자열이 키워드 문자열들 중 하나가 아니면 Kind::Unknown 반환
auto toKind(string string) -> Kind {
  if (stringToKind.count(string))
    return stringToKind.at(string);
  return Kind::Unknown;
}

---

// Token.h

// 토큰 구조체
struct Token {
  Kind kind = Kind::Unknown; // 어휘 종류
  string string; // 어휘 문자열
};

2.2 어휘 분석기

  - 어휘 분석: 소스 코드 문자열에 포함된 어휘 분석

  - 토큰: 분석된 어휘의 문자열과 종류의 쌍

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

  - 소스 코드 문자열

  - 어휘의 시작 문자

  - 숫자 리터럴의 시작 문자

  - 문자열 리터럴의 시작 문자

  - 식별자와 키워드의 시작 문자

  - 연산자와 구분자의 시작 문자

  - 숫자 리터럴 어휘

  - 문자열 리터럴 어휘

  - 식별자와 키워드 어휘

  - 연산자와 구분자 어휘

 

// Main.cpp

// 어휘 분석 함수
auto scan(string) -> vector<Token>;

auto main() -> void {
  string sourceCode = R""""(
    function main() {
      printLine 'Hello, World!';
      printLine 1 + 2 * 3;
    }
  )"""";
  auto tokenList = scan(sourceCode);
  // printTokenist() 함수: 토큰 리스트의 내용을 콘솔에 출력 가능
  printTokenList(tokenList);
}

---

// Scanner.cpp

static string::iterator current;

auto scan(string sourceCode) -> vector<Token> {
  // 소스 코드 문자열을 처음부터 끝까지 문자 단위로 순회하며 토큰 리스트에 토큰 추가
  vector<Token> result;
  // 소스 코드 문자열 끝에 널 문자 추가
  sourceCode += '\0';
  // current; 현재 문자 가리키는 전역 변수
  current = sourceCode.begin();
  while (*current != '\0') {
    // getCharType() 함수; 현재 문자의 종류 반환 (CharType 열거형 멤버 중 하나)
    // 현재 문자가 어떤 어휘의 시작 문자인지 판단하기 위해 getCharType() 호출
    switch (getCharType(*current)) {
      // WhiteSpace인 경우 현재 문자 무시
      case CharType::WhiteSpace:
        current += 1;
        break;
      // 숫자 리터럴 문자열 분석해서 토큰 리스트에 추가
      case CharType::NumberLiteral:
        result.push_back(scanNumberLiteral());
        break;
      case CharType::StringLiteral:
        result.push_back(scanStringLiteral());
        break;
      case CharType::IdentifierAndKeyword:
        result.push_back(scanIdentifierAndKeyword());
        break;
      case CharType::OperatorAndPunctuator:
        result.push_back(scanOperatorAndPunctuator());
        break;
      default:
        cout << *current << " 사용할 수 없는 문자입니다.";
        exit(1);
    }
  }
  // 토큰 리스트에 EndOfToken 토큰 추가
  result.push_back({Kind::EndOfToken});
  return result;
}

enum class CharType {
  Unknown,                // 사용할 수 없는 문자
  WhiteSpace,             // 공백, 탭, 개행
  NumberLiteral,          // 숫자 리터럴
  StringLiteral,          // 문자열 리터럴
  IdentifierAndKeyword    // 식별자, 키워드
  OperatorAndPunctuator,  // 연산자, 구분자
};

auto getCharType(char c) -> CharType {
  // 공백, 탭, 캐리지 리턴, 개행은 토큰 생성 필요 X
  if (' ' == c || '\t' == c || '\r' == c || '\n' == c)
    return CharType::WhiteSpace;
  // 숫자 리터럴의 시작 문자는 숫자
  if ('0' <= c && c <= '9')
    return CharType::NumberLiteral;
  // 문자열 리터럴의 시작 문자는 따옴표
  if (c == '\'')
    return CharType::StringLiteral;
  if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z')
    return CharType::IdentifierAndKeyword;
  // 따옴표는 문자열 리터럴 시작 문자이므로 제외
  if (33 <= c && c <= 47 && c != '\'' ||
      58 <= c && c <= 64 ||
      91 <= c && c <= 126)
    return CharType::OperatorAndPunctuator;
  return CharType::Unknown;
}

// 어휘 문자열 분석 함수에서 현재 문자가 어떤 어휘에 포함되는 문자인지 판단하기 위해 호출
auto isCharType(char c, CharType type) -> bool {
  switch (type) {
    case CharType::NumberLiteral:
      return '0' <= c && c <= '9';
    case CharType::StringLiteral:
      return 32 <= c && c <= 126 && c != '\'';
    case CharType::IdentifierAndKeyword:
      return '0' <= c && c <= '9' ||
             'a' <= c && c <= 'z' ||
             'A' <= c && c <= 'Z';
    case CharType::OperatorAndPunctuator:
      return 33 <= c && c <= 47 ||
             58 <= c && c <= 64 ||
             91 <= c && c <= 96 ||
             123 <= c && c <= 126;
    default:
      return false;
  }
}

// 숫자 리터럴의 문자열 분석하여 토큰 생성하는 함수
// 현재 문자(숫자)부터 연속된 숫자 문자들 추출
auto scanNumberLiteral() -> Token {
  string string;
  if (*current == '.') {
    string += *current++;
    while (isCharType(*current, CharType::NumberLiteral))
      string += *current++;
  }
  return Token{Kind::NumberLiteral, string};
}

// 문자열 리터럴의 문자열 분석하여 토큰 생성하는 함수
// 함수 호출되면 현재 문자는 따옴표이므로
// 현재 문자는 건너뛰고 그 다움 문자부터 따옴표 나오기 전까지의 문자들 추출하여 토큰 생성
auto scanStringLiteral() -> Token {
  string string;
  current++;
  while (isCharType(*current, CharType::StringLiteral))
    string += *current++;
  // 문자열 리터럴 마지막 문자는 따옴표
  // while 문 종료된 시점에 현재 문자 따옴표인지 확인 후 현재 문자 건너뛰기
  if (*current != '\'') {
    cout << "문자열의 종료 문자가 없습니다.";
    exit(1);
  }
  current++;
  return Token{Kind::StringLiteral, string};
}

// 현재 문자는 알파벳
// 현재 문자부터 연속된 알파벳이나 순자 문자들 추출하여 토큰 생성
auto scanIdentifierAndKeyword() -> Token {
  string string;
  while (isCharType(*current, CharType::IdentifierAndKeyword))
    string += *current++;
    // 키워드 중 하나가 아니라면 식별자로 간주
  auto kind = toKind(string);
  if (kind == Kind::Unknown)
    kind = Kind::Identifier;
  return Token{kind, string};
}

// 현재 문자는 특수문자이므로 현재 문자부터 연속된 특수문자들 추출하여 토큰 생성
auto scanOperatorAndPunctuator() -> Token {
  stirng string;
  while (isCharType(*current, CharType::OperatorAndPunctuator))
    stirng += *current++;
  // 추출된 문자열이 미리 정의된 연산자나 구분자 중 하나이거나
  // 추출된 문자열의 길이가 0이 아닐 때까지 문자열을 뒤에서부터 하나씩 줄여가며 판단
  // 가장 짧은 특수 문자열부터 매칭 되는 것이 있으면 주석 기호로 인식 (그 외는 나눗셈 연산자)
  while (string.empty() == false && toKind(string) == Kind::Unknown) {
    string.pop_back();
    current--;
  }
  if (string.empty()) {
    cout << *current << " 사용할 수 없는 문자입니다.";
    exit(1);
  }
  return Token{toKind(string), string};
}

2.3 마치며

  - 어휘 분석은 컴파일 과정의 첫번째 단계

  - 어휘 분석: 소스 코드의 문자열 분석

  - 소스 코드 문자열은 어휘들의 나열

  - 어휘에는 식별자, 키워드, 연산자, 구분자, 숫자 리터럴, 문자열 리터럴이 있음

  - 어휘는 종류에 따라 서로 다른 문자로 시작

  - 식별자는 알파벳으로 시작하고 알파벳이나 숫자가 연속되는 어휘임

  - 키워드는 식별자와 동일하지만 프로그래밍 언어에서 특별하게 취급하는 어휘임

  - 연산자와 구분자는 따옴표를 제외한 특수문자로 시작하고 특수문자가 연속되는 어휘임

  - 연산자와 구분자는 키워드와 마찬가지로 프로그래밍 언어에서 특별하게 취급되는 어휘임

  - 숫자 리터럴은 숫자로 시작하며 숫자가 연속되는 어휘임

  - 문자열 리터럴은 따옴표로 시작하며 따옴표로 끝나는 어휘임

  - 토큰은 어휘의 문자열과 종류의 묶음

  - 어휘 분석기는 소스 코드의 문자열을 분석하는 어휘 분석 프로그램

  - 어휘 분석기의 입력은 소스 코드 문자열, 출력은 토큰 리스트

 

---

[Source Code] 어휘와 토큰 (Kind.h)

[Source Code] 어휘와 토큰 (Kind.cpp)

[Source Code] 어휘와 토큰 (Token.h)

 

[Source Code] 어휘 분석기 (Main.cpp)

[Source Code] 어휘 분석기 (Scanner.cpp)