Robotics

[펌]
저번에 PGLight언어 문법를 BNF스타일로 정리했습니다. 이제 파싱하는 코드를 짤 차례인데요, 실은 저번에 제대로 정리하지 않고 넘어간게 있었습니다.
원래 BNF로 문법을 정리할때 말단 노드들이 어떻게 정의되는지도 명확히 해놔야 파싱 코드 작성할 때 용이합니다만, 그런거 없다! 하고 넘어왔었죠.


저번 BNF 표기법에서 어물쩍 넘어간
<identifier>와 <simple_literal>이 어떤 놈인지를 명확하게 하고 갑시다.
<identifier>는 말그대로 식별자가 될만한 놈들인데, 대게의 언어에서는 특수기호가 아닌 문자열로 구성됩니다. 정규표현식으로 쓰자면 [A-Za-z][A-Za-z0-9]* 요런식으로 되겠습니다. 근데 PGLight는 소스에서부터 유니코드를 지원하기로 했기때문에, 식별자에도 특수문자를 제외한 모든 유니코드문자를 허용하기로 했는데... 음 정규표현식으로 쓰기엔 귀찮으니 생략하도록 할게요ㅋ
<simple_literal>은 문장 내에서 쓰이는 단순한 상수값들입니다. 정수인경우에는 0 | [1-9][0-9]* 가 될것이고, 문자열일 경우는 "" 따옴표로 둘러쌓인 덩어리, boolean 값일 경우는 true | false가 될겁니다. 이중 파싱하기 까다로운건 문자열인데요, 따옴표 내에 \로 이스케이프 된 경우까지 따져야하기 때문이죠. 그래서 정규표현식으로 쓰기에는 조금 까다로운 면이 있으니 생략할게요.

자, 첫번째 단계는 줄줄이 이어져있는 소스 코드를 최소 의미 단위인 토큰(token)으로 쪼개는 것입니다. 이를 Tokenize라고 합니다. 일단 언어에 어떤 토큰들이 있나를 정의할 필요가 있습니다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

enum class TokenType {     none, // 아무것도 아님     eof, // 문자열의 끝     error, // 알수없는 토큰(에러 처리)     string, // 따옴표로 둘러싸인 문자열     integer, // 정수     real, // 실수     identifier, // 식별자     question, // ?     plus, //       minus, // -     asterisk, // *     divide, // /     percent, // %     hat, // ^     dot, // .     assign, // =     equal, // ==     greater, // >     greaterequal, // >=     less, // <     lessequal, // <=     notequal, // !=     colon, // :     semicolon, // ;     comma, // ,     lbracket, // {     rbracket, // }     lparen, // (     rparen, // )     lsbracket, // [     rsbracket, // ]     bar, // |     _and, // and     _or, // or     _not, // not     _function, // function     _var, // var     _as, // as     _if, // if     _else, // else     _for, // for     _do, // do     _while, // while     _return, // return     _true, // true     _false, // false     _null, // null     _continue, // continue     _break, // break     _done, // done     _in, // in     _yield, // yield     _this, // this     comment1, // 한줄 주석     comment2, // 블럭 주석 };

딱 보면 뭐하는 토큰인지 알기 쉽게 나름대로 이름을 지었습니다. 토큰 타입을 알려주는 enum 뿐만 아니라 각각의 토큰을 담는 토큰 구조체가 필요하겠죠. 보통 토큰을 담을때는 토큰의 종류와 문자열, 이 두 가지만 담으면 충분하다고 생각할 수 있는데, 요러면 나중에 에러 코드 뿜어내는 부분을 작성할때 힘든 부분이 많습니다. 그래서 토큰이 위치한 줄번호까지도 함께 토큰 구조체에 담아두고, 나중에 구문 오류가 발생했을때 줄번호를 표시할수 있게 해줍니다.

?

1 2 3 4 5 6 7 8

struct Token {     string str;     TokenType type;     int line;     Token(string s = string(), TokenType t = TokenType::none, int _line = 0) : str(s), type(t), line(_line) {} // 문자열은 모두 utf8로 처리합니다. };

123 4*2

는 123, , 4, *, 2

abc      de

는 abc, , de


로 분리되어야합니다.
띄어쓰기는 싹다 무시하고, * 와 같은 연산자 앞에서는 무조건 토큰을 끊어줘야하지요. 자 먼저 무조건 토큰을 끊어줘야하는 문자들을 구분해내볼까요

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

// 토큰이 무조건 잘려야하는 문자면 true를 반환하는 함수 bool IsCutCharacter(wchar_t c) {     switch(c)     {     case L' ':     case L'\t':     case L'\r':     case L'\n':     case L'<':     case L'>':     case L'[':     case L']':     case L'=':     case L'!':     case L'+':     case L'-':     case L'*':     case L'/':     case L'%':     case L'^':     case L'?':     case L'.':     case L':':     case L';':     case L',':     case L'{':     case L'}':     case L'(':     case L')':     case L'|':         return true;     }     return false; }

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

// 16진수 문자인지 확인하는 함수 bool ishex(char c) {     if('0' <= c && c <= '9') return true;     if('A' <= c && c <= 'F') return true;     if('a' <= c && c <= 'f') return true;     return false; }   //16진수 문자를 정수로 변환하는 함수 int hexToInt(char c) {     if('0' <= c && c <= '9') return c - '0';     if('A' <= c && c <= 'F') return c - 'A' + 10;     if('a' <= c && c <= 'f') return c - 'a' + 10;     return -1; }

이스케이프에서 사용되는 \xAA 같은 표현을 해석할때 위 두 함수는 매우 유용합니다.
다음은 문자열에서 \로 시작하는 이스케이프 문자열을 해석해주는 함수입니다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

/* \로 Escape되어있는 문자열을 원래값으로 해석하여 반환한다 it에서 시작해서 end에서 끝나는 문자열. Escape이 끝나는 지점으로 it로 옮기고, 실패했을 경우 error를 true로 설정한다*/ wchar_t DecodeEscape(string::const_iterator& it, string::const_iterator end, bool& error) { //시작이 끝과 같거나, it가 \를 가리키지 않으면 실패합니다.     if(it == end || *it != '\\')     {         error = true;         return 0;     }       it;     error = false;     switch(*it)     {     case '\\':           it;         return '\\';     case 't':           it;         return '\t';     case 'n':           it;         return '\n';     case 'r':           it;         return '\r';     case '\'':           it;         return '\'';     case '"':           it;         return '\"';     case '0':           it;         return '\0';     case 'x':         {             ++it;             int h = 0;             for(int i = 0; i < 2; ++i)             {                 if(!ishex(*it))                 {                     error = true;                     return 0;                 }                 h = h * 16 + hexToInt(*it);                 ++it;             }             return h;         }     } //나머지는 처리할수 없다고 해버려요. 물론 이스케이프 문자가 몇 종류 더 있지만 자주 안쓰이므로 쿨하게 버렸습니다     error = true;     return '\\'; }

이제 진짜로 tokenizer를 짜봅시다. 좀 길고 코드가 더러운데 그냥 봐주세요 ㅠㅠ (너무 지저분해서 다시 건드리기조차 무섭네요)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337

//문자열을 입력받아서 Token의 vector로 반환해줍니다. vector<Token> Tokenize(const string& str) {     vector<Token> ret;       auto it = str.begin();     auto marker = str.begin();   /* 토큰화하고 있는 작업의 단계입니다. 무슨 타입의 토큰을 작업하는지를 담고 있어요. 처음에는 TokenType::none 스테이지에서 시작합니다.*/     TokenType stage = TokenType::none; // 줄번호입니다.     int line = 1; // 임시 문자열을 저장하는 놈     string s;   // it가 끝에 다다를때까지 반복해요.     for(;it != str.end();++it)     {         switch(stage)         { // none스테이지일 경우입니다.         case TokenType::none:             switch(*it)             { // 줄바꿈 문자열일 경우는 line을 늘려주고 패스             case '\n':                   line; // 나머지는 쿨하게 씹어요. 다 공백들이니깐             case ' ':             case '\t':             case '\r':                 break; // 따옴표인 경우는 스테이지를 string으로 설정하고 s를 비워둬요.             case '\"':                 stage = TokenType::string;                 s.clear();                 break; // 숫자인 경우는 스테이지를 integer로 설정하고 marker를 현재 지점에 찍어놓습니다.             case '0':             case '1':             case '2':             case '3':             case '4':             case '5':             case '6':             case '7':             case '8':             case '9':                 stage = TokenType::integer;                 marker = it;                 break; // < 인겨우는 < 인지 <=인지 알아보기 위해 다음 문자를 쓱 살펴봐요             case '<':                 if(it   1 != str.end() && it[1] == '=')                 {                     ret.push_back(Token("<=", TokenType::lessequal, line));                       it;                 }                 else                 {                     ret.push_back(Token("<", TokenType::less, line));                 }                 break; // >도 마찬가지입니다.             case '>':                 if(it   1 != str.end() && it[1] == '=')                 {                     ret.push_back(Token(">=", TokenType::greaterequal, line));                       it;                 }                 else                 {                     ret.push_back(Token(">", TokenType::greater, line));                 }                                   break;             case '[':                 ret.push_back(Token("[", TokenType::lsbracket, line));                 break;             case ']':                 ret.push_back(Token("]", TokenType::rsbracket, line));                 break; // !인 경우는 != 일때만 쓰여요.             case '!':                 if(it   1 != str.end() && it[1] == '=')                 {                     ret.push_back(Token("!=", TokenType::notequal, line));                       it;                 } // 뒷 문자가 =가 아니면 무조건 에러입니다.                 else                 {                     ret.push_back(Token("!", TokenType::error, line));                 }                 break; // =이면 ==이거나 =이거나 둘중 하나입니다.             case '=':                 if(it   1 != str.end() && it[1] == '=')                 {                     ret.push_back(Token("==", TokenType::equal, line));                       it;                 }                 else                 {                     ret.push_back(Token("=", TokenType::assign, line));                 }                 break;             case '+':                 ret.push_back(Token(string(it, it + 1), TokenType::plus, line));                 break;             case '-':                 ret.push_back(Token(string(it, it + 1), TokenType::minus, line));                 break;             case '*':                 ret.push_back(Token(string(it, it + 1), TokenType::asterisk, line));                 break; // / 일겨우는 // 나, /* 아니면 그냥 / 입니다.             case '/':                 if(it + 1 != str.end() && it[1] == '/')                 { // 한줄 주석인 경우는 스테이지를 comment1로                     stage = TokenType::comment1;                       it;                 }                 else if(it + 1 != str.end() && it[1] == '*')                 { // 블록 주석인 경우는 스테이지를 comment2로                     stage = TokenType::comment2;                       it;                 }                 else                 { // 나머지는 일반 나눗셈                     ret.push_back(Token(string(it, it + 1), TokenType::divide, line));                 }                 break;             case '%':                 ret.push_back(Token(string(it, it + 1), TokenType::percent, line));                 break;             case '^':                 ret.push_back(Token(string(it, it + 1), TokenType::hat, line));                 break;             case '?':                 ret.push_back(Token(string(it, it + 1), TokenType::question, line));                 break;             case '.':                 ret.push_back(Token(string(it, it + 1), TokenType::dot, line));                 break;             case ':':                 ret.push_back(Token(string(it, it + 1), TokenType::colon, line));                 break;             case ';':                 ret.push_back(Token(string(it, it + 1), TokenType::semicolon, line));                 break;             case ',':                 ret.push_back(Token(string(it, it + 1), TokenType::comma, line));                 break;             case '{':                 ret.push_back(Token(string(it, it + 1), TokenType::lbracket, line));                 break;             case '}':                 ret.push_back(Token(string(it, it + 1), TokenType::rbracket, line));                 break;             case '(':                 ret.push_back(Token(string(it, it + 1), TokenType::lparen, line));                 break;             case ')':                 ret.push_back(Token(string(it, it + 1), TokenType::rparen, line));                 break;             case '|':                 ret.push_back(Token(string(it, it + 1), TokenType::bar, line));                 break; // 나머지인 경우는 다 식별자로 취급합니다. marker를 시작지점에 찍어놓습니다             default:                 stage = TokenType::identifier;                 marker = it;                 break;             }             break; // 스테이지가 string일 경우 ("로 시작하는 경우죠)         case TokenType::string:             for(;*it != '\"'; ++it)             { // 닫는 따옴표가 안 나왔는데, 끝에 도달하거나 줄바꿈을 당했으면 어딘가 잘못된거죠                 if(it == str.end() || *it == '\n' || *it == '\r')                 {                     stage = TokenType::none;                     ret.push_back(Token(s, TokenType::error, line));                     break;                 } // 이스케이프 문자입니다. 앞에서 선언한 DecodeEscape함수를 호출해요                 else if(*it == '\\')                 {                     bool err;                     s.push_back(DecodeEscape(it, str.end(), err));                     if(err)                     {                         stage = TokenType::none;                         ret.push_back(Token(s, TokenType::error, line));                         break;                     }                     --it;                 } // 나머지인 경우는 그냥 s에 차곡차곡 쌓아넣습니다.                 else                 {                     s.push_back(*it);                 }             } // 성공적으로 닫는 따옴표를 마치고 나왔습니다. // 스테이지를 다시 기본으로 돌리고, 현재 문자열을 토큰으로 넣습니다             stage = TokenType::none;             ret.push_back(Token(s, TokenType::string, line));             break; // 스테이지가 integer인 경우 (숫자로 시작한 경우죠)         case TokenType::integer: // 마침표를 만나면 이건 실수인겁니다. 스테이지 전향             if(*it == '.')             {                 stage = TokenType::real;             } // 토큰을 자르는 문자를 만났으면 여기까지만 숫자인걸로 봐야합니다 // 스테이지를 기본으로 돌리고, 이 문자 전까지를 토큰에 넣어요             else if(IsCutCharacter(*it))             {                 stage = TokenType::none;                 ret.push_back(Token(string(marker, it--), TokenType::integer, line));             } // 숫자가 아닌 놈이 뒤에 붙어있으면 에러입니다.             else if(!isdigit(*it))             {                 stage = TokenType::none;                 ret.push_back(Token(string(marker, it), TokenType::error, line));                 --it;             }             break; // 스테이지가 실수인 경우 (숫자로 시작해서 .을 만난 경우죠)         case TokenType::real:             if(IsCutCharacter(*it))             {                 stage = TokenType::none;                 ret.push_back(Token(string(marker, it--), TokenType::real, line));             }             else if(!isdigit(*it))             {                 stage = TokenType::none;                 ret.push_back(Token(string(marker, it), TokenType::error, line));                 --it;             }             break; // 스테이지가 식별자인 경우 (특수 문자가 아닌 기타 일반적인 문자로 시작한경우)         case TokenType::identifier: // 토큰을 자르는 문자를 만났으면, 여기까지 문자열을 뚝 잘라서 키워드와 비교해봅니다             if(IsCutCharacter(*it))             {                 stage = TokenType::none;                 string s(marker, it--);                 if(s == "and")                     ret.push_back(Token(s, TokenType::_and, line));                 else if(s == "or")                     ret.push_back(Token(s, TokenType::_or, line));                 else if(s == "not")                     ret.push_back(Token(s, TokenType::_not, line));                 else if(s == "function")                     ret.push_back(Token(s, TokenType::_function, line));                 else if(s == "var")                     ret.push_back(Token(s, TokenType::_var, line));                 else if(s == "as")                     ret.push_back(Token(s, TokenType::_as, line));                 else if(s == "if")                     ret.push_back(Token(s, TokenType::_if, line));                 else if(s == "else")                     ret.push_back(Token(s, TokenType::_else, line));                 else if(s == "for")                     ret.push_back(Token(s, TokenType::_for, line));                 else if(s == "while")                     ret.push_back(Token(s, TokenType::_while, line));                 else if(s == "do")                     ret.push_back(Token(s, TokenType::_do, line));                 else if(s == "true")                     ret.push_back(Token(s, TokenType::_true, line));                 else if(s == "false")                     ret.push_back(Token(s, TokenType::_false, line));                 else if(s == "null")                     ret.push_back(Token(s, TokenType::_null, line));                 else if(s == "return")                     ret.push_back(Token(s, TokenType::_return, line));                 else if(s == "break")                     ret.push_back(Token(s, TokenType::_break, line));                 else if(s == "continue")                     ret.push_back(Token(s, TokenType::_continue, line));                 else if(s == "done")                     ret.push_back(Token(s, TokenType::_done, line));                 else if(s == "in")                     ret.push_back(Token(s, TokenType::_in, line));                 else if(s == "yield")                     ret.push_back(Token(s, TokenType::_yield, line));                 else if(s == "this")                     ret.push_back(Token(s, TokenType::_this, line)); // 아무 키워드에 해당안되면 그냥 일반 식별자인거에요                 else                     ret.push_back(Token(s, TokenType::identifier, line));             }             break; // 스테이지가 한 줄 주석인 경우         case TokenType::comment1: // 줄바꿈을 만날때까지 싹다 무시합니다             if(*it == '\n')             {                 ++line;                 stage = TokenType::none;             }             break; // 스테이지가 블록 주석인 경우         case TokenType::comment2:             switch(*it)             { // 줄바꿈을 만나면 line 증가시키는거 까먹으면 안되구요             case '\n':                 ++line;                 break; // * 뒤에 /가 오는 경우에 블록 주석이 끝납니다             case '*':                 if(it   1 != str.end() && it[1] == '/')                 {                     ++it;                     stage = TokenType::none;                 }                 break;             }             break;         }     } // 다 돌고 난 뒤에 제일 마지막에 eof를 넣어줘요.     ret.push_back(Token("", TokenType::eof, line));     return ret; }

므앙


쫌 길죠. 근데 어려운건 하나도 없는 코드입니다. (파싱 작업이라는게 실제로 어려운 부분은 하나도 없습니다. 다만 귀찮은 부분이 너무 많을뿐)


토크나이징 끝냈으면, 이제 진짜 파싱을 시작할 수 있어요. 파싱을 시작하기 전에 AST(Abstract Syntax Tree, 추상구문트리)를 설계할 필요가 있습니다. 우리가 파싱을 통해서 얻고자 하는게 바로 이 구문트리니까요.
PGLight의 문장 구조는 크게 표현식(expression)과 구문(statement)로 나눌 수 있어요.
표현식은 이런 놈들

1 2, 3*4*foo("sent")

이구요,


구문은

if(test())
{

foo(bar);

}


var a = 123*4;

요런 놈들입니다. 그래도 모르겠다면, 표현식은 연산자로 연결되어서 값을 평가할 수 있는 코드 일부분, 구문은 표현식을 포함하는 문장으로, 실제로 코드를 구성하는 단위라고 생각하시면 됩니다.
먼저 표현식을 나타내는 트리 구조체를 짜봅시다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272

//온갖 구문트리들의 조상님 struct PGL_tree {     virtual void ResolveIdentifier(ResolveData* rd) {}     virtual void GenerateCode(GenerateData* gd) {}     virtual string GetType() const {return "";} // 이 함수들은 추후에 코드를 생성할때 쓰는 놈들이에요. // 지금은 신경쓰지 않아도 됩니다. };   // 모든 표현식트리의 아버지 struct PGL_expr : public PGL_tree {     virtual ~PGL_expr() {} };   /* 좌측값으로 쓰일수 있는 표현식 참고로 좌측값으로 쓰일수 있는 놈들은 우측값으로도 쓰일수 있어요*/ struct PGL_lexpr : public PGL_expr {     virtual void GenerateLCode(GenerateData* gd) {}     virtual ~PGL_lexpr() {} };   // 상수값을 표현합니다. struct PGL_literal : public PGL_expr {     shared_ptr<PGLCompoundData> l; // 값을 담는 구조체 PGLCompoundData입니다.     PGL_literal(shared_ptr<PGLCompoundData> _l) : l(_l) {}     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd); };   // 식별자(대게는 변수죠)를 표현합니다. // 식별자는 (대게) 좌측값이 될수 있어요 struct PGL_identifier : public PGL_lexpr {     string id;     shared_ptr<PGLID> pid;     PGL_identifier(string _id) : id(_id), pid(nullptr) {}     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd);     void GenerateLCode(GenerateData* gd); };   // this. 멤버함수에서 사용됩니다. // 역시 좌측값이 될수 있습니다 struct PGL_this : public PGL_lexpr {     PGL_this() {}     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd);     void GenerateLCode(GenerateData* gd); };   // not 연산자. 피연사자를 하나 받습니다 struct PGL_not_expr : public PGL_expr {     shared_ptr<PGL_expr> r;     PGL_not_expr(shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : r(_r) {}     void ResolveIdentifier(ResolveData* rd) {r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // and 연산자. 피연산자를 두 개 받아요 struct PGL_and_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_and_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // or 연산자. 피연산자를 두 개 받아요 struct PGL_or_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_or_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // == 연산자. 피연산자 2개 struct PGL_equal_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_equal_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // != 연산자. 피연산자 2개 struct PGL_notequal_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_notequal_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // > 연산자. 피연산자 2개 struct PGL_greater_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_greater_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // >= 연산자. 피연산자 2개 struct PGL_greaterequal_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_greaterequal_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // < 연산자. 피연산자 2개 struct PGL_less_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_less_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // <= 연산자. 피연산자 2개 struct PGL_lessequal_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_lessequal_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // + 연산자. 피연산자 2개 struct PGL_add_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_add_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // - 연산자. 피연산자 2개 struct PGL_sub_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_sub_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // * 연산자. 피연산자 2개 struct PGL_mul_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_mul_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // / 연산자. 피연산자 2개 struct PGL_div_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_div_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // % 연산자. 피연산자 2개 struct PGL_mod_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_mod_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // ^ 연산자. 피연산자 2개 struct PGL_pow_expr : public PGL_expr {     shared_ptr<PGL_expr> l, r;     PGL_pow_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // - 연산자. 피연산자 1개 struct PGL_sign_expr : public PGL_expr {     shared_ptr<PGL_expr> r;     PGL_sign_expr(shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : r(_r) {}     void ResolveIdentifier(ResolveData* rd) {r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // . 연산자. 좌측에는 어떤 표현식도 올수 있지만, // 우측에는 문자열만 올수 있어요 struct PGL_dot_expr : public PGL_lexpr {     shared_ptr<PGL_expr> l;     string r;     shared_ptr<PGLID> pid;     PGL_dot_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         string _r = string()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd);     void GenerateLCode(GenerateData* gd);     virtual string GetType() const {return "dot_expr";} };   // [] 배열/사전 참조 연산자. 좌측, 우측 둘 다 어떤 표현식도 올수 있습니다 struct PGL_ref_expr : public PGL_lexpr {     shared_ptr<PGL_expr> l, r;     PGL_ref_expr(shared_ptr<PGL_expr> _l = shared_ptr<PGL_expr>(),         shared_ptr<PGL_expr> _r = shared_ptr<PGL_expr>()) : l(_l), r(_r) {}     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd);     void GenerateLCode(GenerateData* gd); };   // 함수 호출 표현식. 함수주소값과 인자 목록이 들어갑니다 struct PGL_functioncall_expr : public PGL_expr {     shared_ptr<PGL_expr> l;     vector<shared_ptr<PGL_expr>> params;     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); for(auto&r : params)r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // 배열 표현식. 배열의 요소들이 들어갑니다 struct PGL_array_expr : public PGL_expr {     vector<shared_ptr<PGL_expr>> elem;     void ResolveIdentifier(ResolveData* rd) {for(auto&r : elem)r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // 키와 값을 담는 구조체. 혼자 PGL_expr의 자손이 아닙니다 스파이에요. struct PGL_key_val {     shared_ptr<PGL_expr> key;     shared_ptr<PGL_expr> val;     void ResolveIdentifier(ResolveData* rd) {key->ResolveIdentifier(rd); val->ResolveIdentifier(rd);} };   // 사전 표현식. 키와 값을 담는 구조체 배열이 들어갑니다 struct PGL_dict_expr : public PGL_expr {     vector<PGL_key_val> elem;     void ResolveIdentifier(ResolveData* rd) {for(auto&r : elem)r.ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };

그 다음은 구문들을 나타내는 트리 구조체!

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

// 구문트리의 아버지 struct PGL_sentence : public PGL_tree {     virtual ~PGL_sentence() {}     virtual void CollectID(ResolveData* rd) {}     virtual void EraseIdentifier(ResolveData* rd) {}     virtual int CountPopStack() const {return 0;} };   // 단순 구문 트리를 위한건데 아직 아무 내용도 없네요ㅋ struct PGL_simple_sentence : public PGL_sentence {   };   // 대입문. struct PGL_assign : public PGL_simple_sentence {     shared_ptr<PGL_lexpr> l;     shared_ptr<PGL_expr> r;     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd); r->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // 함수 호출문 struct PGL_call : public PGL_simple_sentence {     shared_ptr<PGL_expr> l;     void ResolveIdentifier(ResolveData* rd) {l->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // 코드 전체를 담는 놈 struct PGL_whole {     vector<shared_ptr<PGL_sentence>> sents;     void CollectID(ResolveData* rd) {for(auto& r : sents)r->CollectID(rd);}     void ResolveIdentifier(ResolveData* rd) {for(auto& r : sents)r->ResolveIdentifier(rd);for(auto& r : sents)r->EraseIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // 코드 블럭을 담는 놈 struct PGL_block : public PGL_whole {     void GenerateCode(GenerateData* gd);     int CountPopStack() const {return accumulate(sents.begin(), sents.end(), 0, [](int a, const shared_ptr<PGL_sentence>& b){return a   b->CountPopStack();});} };   // if문을 담는놈. // else if 같은 경우는 else문 속의 if문으로 볼 수 있습니다 struct PGL_if : public PGL_sentence {     shared_ptr<PGL_expr> cond;     PGL_block trueSents, falseSents;     void ResolveIdentifier(ResolveData* rd) {cond->ResolveIdentifier(rd); trueSents.ResolveIdentifier(rd); falseSents.ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // while문 담는놈 struct PGL_while : public PGL_sentence, public PGL_loopUnit {     shared_ptr<PGL_expr> cond;     PGL_block sents;     PGL_block doneS;     PGL_block elseS;     void ResolveIdentifier(ResolveData* rd) {cond->ResolveIdentifier(rd); sents.ResolveIdentifier(rd); doneS.ResolveIdentifier(rd); elseS.ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // return 문 struct PGL_return : public PGL_sentence {     shared_ptr<PGL_expr> ret;     void ResolveIdentifier(ResolveData* rd) {ret->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // yield 문 struct PGL_yield : public PGL_sentence {     shared_ptr<PGL_expr> ret;     void ResolveIdentifier(ResolveData* rd) {ret->ResolveIdentifier(rd);}     void GenerateCode(GenerateData* gd); };   // break문 struct PGL_break : public PGL_sentence {     string label;     void GenerateCode(GenerateData* gd); };   // continue문 struct PGL_continue : public PGL_sentence {     string label;     void GenerateCode(GenerateData* gd); };   // 변수 선언문 struct PGL_decl_var : public PGL_sentence {     string name, type;     shared_ptr<PGL_expr> init;     shared_ptr<PGLID> pid;     void CollectID(ResolveData* rd);     void ResolveIdentifier(ResolveData* rd);     void EraseIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd);     int CountPopStack() const {return 1;} };   // for문 struct PGL_for : public PGL_sentence, public PGL_loopUnit {     shared_ptr<PGL_decl_var> var;     shared_ptr<PGL_expr> cond;     shared_ptr<PGL_simple_sentence> loop;     PGL_block sents;     PGL_block doneS;     PGL_block elseS;     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd); };   // 범위기반 for문 struct PGL_for_in : public PGL_sentence, public PGL_loopUnit {     string varKey, varVal;     shared_ptr<PGLID> pidCont;     shared_ptr<PGLID>pidIt;     shared_ptr<PGLID> pidKey;     shared_ptr<PGLID> pidVal;     shared_ptr<PGL_expr> container;     PGL_block sents;     PGL_block doneS;     PGL_block elseS;     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd); };   // 스파이다. 인수목록을 담는 구조체입니다 struct PGL_param {     shared_ptr<PGLID> pid;     string name, type; };   // 함수 선언문, 변수를 캡쳐할 수 있는 단위(closureUnit) struct PGL_decl_function : public PGL_sentence, public PGL_closeUnit {     string name, type;     vector<PGL_param> params;     PGL_block sents;     shared_ptr<PGLID> pid;     shared_ptr<PGLFunctionData> faddr;     void CollectID(ResolveData* rd);     void ResolveIdentifier(ResolveData* rd);     void EraseIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd);     void Link(int pos);     string GetName() const {return name;} };   // 익명함수 표현식. (얘는 표현식이에요. 구문 아닙니다), 변수를 캡쳐할수 있는 단위에요. struct PGL_function_expr : public PGL_expr, public PGL_closeUnit {     string type;     vector<PGL_param> params;     PGL_block sents;     shared_ptr<PGLID> pid;     shared_ptr<PGLFunctionData> faddr;     void ResolveIdentifier(ResolveData* rd);     void GenerateCode(GenerateData* gd);     void Link(int pos); };

PGLID, PGLFunctionData 같은 놈들이 등장해서 코드가 번잡해졌지만 저런거 싹다 무시하고, 전체적인 구조만 보면돼요. 이제 우리가 할 일은 토큰목록을 파싱하여 이 구조에 맞춰서 내용물들을 채워주면 되는거죠. 으앙 코드가 너무 길어져서 터질거 같네요. 본격 파싱은 다음으로 넘겨야겠습니다.


출처: https://bab2min.tistory.com/327?category=115013 [나의 큰 O는 logx야..]