사칙연산 계산기 문제를 통해 컴파일러, yacc, 역폴란드 표기법, 스택 머신의 기본 개념을 쉽고 유쾌하게 설명합니다.
안녕하세요. "엑셀 파일 읽고 계신가요?"로 잘 알려진(?) 알다그램 테크니컬 펠로우 호라이입니다. 잘 지내고 계신가요?
네? 그것보다 더 신경 쓰이는 게 있다고요? 아, 이 제목 말인가요.
"사칙연산 정도는 할 수 있거든! 무시하지 마!!"
라고 하면서 관자놀이 핏줄이 꿈틀거리는 독자분들의 기운이 생생하게 느껴집니다.
"안심하세요, 느끼고 있습니다!"
자자, 일단 진정하시고 이 문제를 생각해 보세요.
어떠신가요? 할 수 있을 것 같나요?
(물론 javascript의 eval 함수 같은 것을 쓰는 건 금지입니다. 직접 만드세요.)
이 문제를 풀 수 있는 당신, 훌륭합니다. 이제 이 글은 더 읽지 않으셔도 됩니다.
어떻게 해야 할지 전혀 모르겠어요, 흑흑... 하는 당신도 괜찮습니다.
"안심하세요. 문제가 어려운 겁니다!"
그럼, 이 문제가 왜 어려운지 함께 생각해 봅시다.
예를 들어
4 + (10 - 2 * 3) / (4 / (5 - 3))
를 계산한다고 해 봅시다.
보통 손으로 계산한다면 어떻게 하시나요?
대충 이런 느낌이 되지 않을까요.
그러니까...
그걸 그대로 컴퓨터에게 시키면 됩니다.
"아니 아니... 그렇게 말해도 어려운 거 아닌가요?"
쓸 수 있는 것은 재활용하는 스타일. SDGs입니다.
그래도 문제가 어렵다는 사실만이라도 알아주셨다면, 이 글을 쓴 보람이 있습니다. 여기까지 읽어주셔서 감사합니다.
(이 글은 꽤 길기 때문에 중간에 포기할 것 같다면, 스크롤해서 마지막에 부분만이라도 읽어주시면 기쁘겠습니다)
갑자기 이야기가 바뀌지만, 컴퓨터를 한국어로 뭐라고 하는지 아시나요?
정답은 "전자계산기"입니다.
그렇습니다. 컴퓨터는 원래 계산을 하기 위해 만들어졌기 때문에, 이런 문제를 풀기 위해 발전해 온 것입니다.
문자로 계산식을 입력하고, 그것을 실행하면 답이 나온다... 왠지 익숙하지 않나요??
맞습니다. 그것이 바로 프로그래밍 언어의 원형입니다. (대부분의 프로그래밍 언어에는 사칙연산이 있죠)
그런데 여러분은 컴파일러라는 말을 들어본 적이 있으신가요? 아니면 매일 사용하고 계신 분도 많겠죠.
그럼, 컴파일러를 직접 만들어 본 사람은 얼마나 될까요?
대학교 등에서 컴퓨터 사이언스(계산기과학이라고 번역하면 왠지 촌스럽죠)를 공부한 분들은 한 번쯤 해보셨을지도 모르겠습니다.
(해봤지만 전혀 기억이 안 난다는 분도 많을 것 같지만요...)
그리고 아까 그 문제, 컴파일러를 만들 수 있는 사람이라면 할 수 있습니다.
"그래서 컴파일러가 뭔데?"
라고 생각하실 텐데, 컴파일러를 대충 말하면,
"프로그램을 컴퓨터가 처리하기 쉬운 형태로 변환하는 프로그램"
이라고 할 수 있습니다.
"추상적인 말만 하지 마! 프로그램을 변환하는 프로그램이라고?! 무슨 소리인지 모르겠다고!"
괜찮습니다. 아직 당황하지 마세요.
오히려 당황할 일은 지금부터입니다. 왜냐하면 이제부터 컴파일러를 만들기 위한 컴파일러도 소개할 테니까요..
"뭐라고!?"
라는 표정이신가요? 지금 아주 좋은 표정이십니다!
아까의 사칙연산 식에서, 컴퓨터가 이해하기 어려워하는 이유는 왜일까요?
"어디서부터 계산을 시작해야 할지 모르기 때문"
아닐까요? 인간은
같은 규칙을 알고 있고, 그것을 바탕으로 계산하기 때문에 올바른 순서로 계산할 수 있는 것입니다.
아까 식의 일부인 10 - 2 * 3을 컴퓨터가 이해하기 쉬운 형태로 바꾸면 이런 느낌이 됩니다.
10 2 3 * -
"이게 뭐야?"
라고 생각하는 분도 있을 것이고,
"아, 알아! 역폴란드 표기법이잖아!"
라고 하시는 분도 있겠죠.
사실 이 형식은 컴퓨터에게는 엄청나게 읽기 쉬운 형식입니다.
실은 이 형식에는 계산 순서가 이미 내장되어 있기 때문에, 곱셈과 뺄셈 중 어느 쪽을 먼저 계산할지 따로 생각할 필요가 없습니다.
믿기지 않겠지만... 사실입니다...?
그럼 실제로 그것을 어떻게 계산하는지 설명해 보겠습니다.
아까 손으로 계산할 때, 중간 계산 결과를 메모해 두었다가 나중에 썼죠?
2와 3을 곱해서 6이니까, 그것을 10에서 빼고... 같은 식으로요.
컴퓨터가 계산할 때도 마찬가지로 계산 도중의 결과를 메모해 두는 구조가 필요합니다.
이럴 때는 스택을 쓰는 것이 일반적입니다. 유명한 자료구조라서 아는 분도 많을 겁니다.
"알지 알지. 스택 오버플로우 그런 거 그거잖아? 이해. 이해."
라는 분을 위해 설명하자면...
어떤 데이터가 메모되어 있는지는 신경 쓰지 않고, 위에 차곡차곡 데이터를 쌓아 올리는 느낌입니다. 데이터를 꺼낼 때도 맨 위에서만 꺼낼 수 있습니다. 서류 더미 같은 이미지죠.
이것이 스택이다! 완벽하게 이해했다!
스택만 준비해 두면, 그 다음은 엄청나게 간단한 규칙으로 계산할 수 있습니다.
식을 왼쪽부터 순서대로 하나씩 읽어 나가면서
이상입니다.
"진짜야...?"
진짜입니다. 이것만으로 어떤 복잡한 계산식도 순서를 신경 쓰지 않고 계산할 수 있습니다.
아까 예를 계산해 봅시다.
이것이 스택 머신이다! Virtual Machine = VM 이라고 부르기도 합니다
아까의 예라면, 이렇게만 하면 기계적으로 계산할 수 있습니다. 위 그림을 보면서 읽어 보세요.
10 이 왔다 → 숫자니까 쌓자
2 가 왔다 → 숫자니까 쌓자
3 이 왔다 → 숫자니까 쌓자
* 가 왔다 → 2개 꺼내서 계산하고 쌓자
- 가 왔다 → 2개 꺼내서 계산하고 쌓자
마지막에 남은 것이 답
정답인 4가 나왔네요!
이런 식으로 스택을 사용해 계산을 실행하는 프로그램을 스택 머신이라고 부릅니다. (이 정도 프로그램이라면 쉽게 쓸 수 있을 것 같죠?)
참고로 JVM이나 WebAssembly 같은 "가상 머신"의 상당수도 바로 이 방식으로 동작합니다.
(평소 여러분이 접하는 x86이나 ARM 같은 실제 CPU는 레지스터 방식이 주류지만, "명령을 하나씩 읽고 처리한다"는 뼈대는 같습니다)
드디어 여기까지 오셨군요...
원래 식을 다른 형식으로 변환한다, 즉... 컴파일러를 만드는 방법을 알고 싶다, 그런 말씀이시죠?
"아니... 그, 딱히... 난 그런 뜻은..."
아이 참, 부끄러워하지 마세요! 제대로 알려드릴게요!
확실히 아무것도 쓰지 않고 맨손으로 컴파일러를 만드는 건 어렵습니다. 하지만 세상에는 컴파일러를 만들기 위한 도구가 있습니다.
파서 제너레이터라든가 컴파일러 컴파일러라고 불리는 것들인데요. (컴파일러를 만들기 위한 컴파일러! 입니다)
Unix에서 아주 오래전부터 쓰여 온 유명한 도구로 yacc라는 것이 있습니다.
참고로 yacc는 Yet Another Compiler Compiler의 약자입니다. 유명한 C 언어 초기 처리계 등도 yacc를 사용해 만들어졌다고 합니다.
"도구를 쓰는 건 반칙이잖아! 완전 수작업으로 만들어야지!"
라고 하시는 과격한 분이 계시다면 죄송합니다. 미리 사과드리겠습니다. (분명 그런 분은 평소에도 프로그램을 어셈블리 언어로 손으로 쓴 다음 16진수로 직접 변환하고 계시겠죠)
yacc는 현재 그 후계인 bison이 널리 사용되고 있습니다. yacc 외에는 ANTLR라는 도구도 있습니다. 꼭 여러 가지 찾아보세요.
참고로 도구를 쓰지 않고 컴파일러를 만드는 방법도 있습니다. 재귀 하강 파서로 검색해 보면 행복해질지도 모릅니다
그런 의미에서(?) 오래 기다리셨습니다. 드디어 yacc의 차례입니다.
yacc에게 무엇을 시키냐면, 먼저 문법을 가르쳐 줍니다. "문법"이라고 하면 괜히 겁먹게 되지만, 요컨대 식이란 이런 것이다라는 정의를 쓰는 것뿐입니다.
이런 식입니다.
%left '+' '-' /* 덧셈·뺄셈은 나중 순서(우선순위 낮음) */
%left '*' '/' /* 곱셈·나눗셈이 우선(이쪽이 아래=강함) */
%%
expr : expr '+' expr /* 식이란 「식 ＋ 식」이다 */
| expr '-' expr /* 또는 「식 − 식」이다 */
| expr '*' expr /* 또는 「식 × 식」이다 */
| expr '/' expr /* 또는 「식 ÷ 식」이다 */
| '(' expr ')' /* 또는 「( 식 )」이다 */
| NUM /* 또는 그냥 숫자이다 */
;
"뭔가 갑자기 튀어나왔어. 무서워!"
그 마음은 이해하지만, expr가 잔뜩 나오는 부분을 한 번 바라봐 주세요.
"식이란, 식+식이기도 하고, 식×식이기도 하고, (식)이기도 하고, 그냥 숫자이기도 하다"
뭔가 선문답 같지만, 이것이 식의 정체입니다.
식 안에 식이 나오는 이 중첩 구조야말로 괄호와 우선순위를 표현할 수 있는 비결입니다.
다음으로 주목해야 할 것은 맨 위의 **%left**로 시작하는 두 줄입니다.
이건 "곱셈·나눗셈이 덧셈·뺄셈보다 우선순위가 높다"고 선언하는 것입니다.
(참고로 %left는 연산자가 좌결합한다는 뜻이지만 지금은 신경 쓰지 않아도 됩니다)
"에, 그게 다야?"
그게 다입니다. 아까 손계산할 때 곱셈을 먼저 해야 하잖아 하면서 끙끙 고민했던 그 순서가, 단 두 줄로 적혀 버렸습니다.
그리고 그 규칙에 따른 구문 해석을 yacc가 해 주는 것입니다.
(참고로 yacc는 실제로는 이것을 거꾸로 따라갑니다. 입력 식 10 - ( 2 * 3) 쪽에서부터 부품을 묶어 올려 expr에 도달합니다 = 보텀업입니다. 이 "아래에서 조립하는" 움직임이 나중에 중요해집니다.)
여기서 기쁜 소식입니다.
서두의 문제에 이런 것도 있었죠.
" 7 - 32 * 4 + 3 / ( 21 + 3 - ( 4 ) " → ERROR
괄호가 닫히지 않은 잘못된 식입니다. "괄호 짝을 검사하는 코드를 직접 써야 하나..."라고 생각하셨나요?
쓸 필요 없습니다.
아까의 문법을 잘 보세요. '(' expr ')' —— 여는 괄호에는 반드시 닫는 괄호가 한 세트라고만 정의해 두었습니다.
그러므로 닫는 괄호가 부족한 식은 문법적으로 이 세상에 존재할 수 없는 식이 되고, yacc가 생성한 파서는 "그런 식은 모른다"며 에러를 내 주는 것입니다.
(규칙을 적용해도 답에 도달할 수 없는 이미지입니다)
에러가 났을 때 yacc는 yyerror라는 함수를 호출해 주므로, 거기서 ERROR라고 출력하면 사양대로입니다.
"문법을 정의했을 뿐인데, 에러 검출까지 공짜로 따라온다"
yacc님 고맙습니다.
"이건 못 참지! (의문)"
문법을 정의했으니 파서(구문 해석기)는 완성됐습니다.
하지만 지금 상태로는 식으로서 올바른지 판정만 할 뿐입니다. 모처럼이니 계산도 시켜 봅시다.
yacc에서는 각 규칙 뒤에 { }로 "액션"(= 해 주었으면 하는 처리)을 쓸 수 있습니다.
expr : expr '+' expr { $$ = $1 + $3; } /* 결과 = 왼쪽 + 오른쪽 */
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '(' expr ')' { $$ = $2; } /* 괄호 안 내용이 그대로 결과 */
| NUM { $$ = $1; } /* 숫자는 그 값 자체 */
;
주문처럼 보이는 $$라든가 $1은 무엇이냐 하면,
$1``$3 … 그 규칙의 첫 번째·세 번째 부품의 값 (expr '+' expr라면 $1은 왼쪽 expr, $2는 +, $3는 오른쪽 expr)$$ … 이 규칙 자체의 계산 결과즉 expr '+' expr { $$ = $1 + $3; }는
"왼쪽 식과 오른쪽 식이 모두 준비되면, 더해서 그것을 자기 자신의 값으로 해"
라는 뜻입니다.
...네, 이걸로 계산기 완성입니다.
"뭐라고!? 이게 끝이라고!?"
이게 끝입니다.
당신이 준 식은 여러 식의 조합으로 이루어져 있는데, 그 식들의 값을 줄줄이 계산해 결과를 내 주는 느낌이 됩니다.
우선순위도 괄호도 yacc가 알아서 처리해 주기 때문에, "어디서부터 계산할지"를 우리는 1밀리도 신경 쓰지 않았습니다. 아까 그렇게 고민했던 계산 순서를 완전히 yacc에게 떠넘길 수 있는 것입니다.
서두의 문제를 푸는 것만이 목적이라면, 사실 여기서 완성입니다.
실제로 만들어서 실행해 보면 이런 느낌이 됩니다
자, 아까는 구문 해석하는 그 자리에서 계산을 해 버렸습니다. 그런데 여기서 조금만 심술궂게 가 보겠습니다.
계산 자체를 하는 대신, 역폴란드 표기법을 출력하게 해 봅시다.
맞습니다. 글 전반부에 나왔던 10 2 3 * - 그 녀석입니다.
여기서 yacc의 성질이 엄청나게 빛을 발합니다.
yacc는 식을 보텀업(부품에서 조립해 가는 순서)으로 해석합니다.
그리고 액션은 자식이 전부 갖춰진 뒤에 호출됩니다.
그렇다는 것은 아래처럼 액션을 쓰면...
expr : expr '+' expr { printf("+ "); } /* 자식(왼쪽 expr와 오른쪽 expr) 뒤에 + 를 print */
| expr '-' expr { printf("- "); } /* 마찬가지로 - 를 print */
| expr '*' expr { printf("* "); } /* 마찬가지로 * 를 print */
| expr '/' expr { printf("/ "); } /* 마찬가지로 / 를 print */
| '(' expr ')' /* 괄호는 아무것도 출력하지 않는다! */
| NUM { printf("%d ", $1); } /* 숫자는 그 자리에서 출력 */
;
이라는 식으로 printf가 실행되므로, 결과적으로 역폴란드 순서대로 나열됩니다.
그래서,
4 + (10 - 2 * 3) / (4 / (5 - 3))
를 먹이면...
4 10 2 3 * - 4 5 3 - / / +
가 나옵니다. 괄호가 말끔히 사라졌죠?
역폴란드에는 계산 순서가 이미 내장되어 있기 때문에, 괄호는 이제 더 이상 필요 없습니다.
믿기지 않겠지만... 사실입니다...?
이건 이미 훌륭한 컴파일러입니다.
"식"이라는 인간의 언어를, "역폴란드"라는 컴퓨터 친화적인 형식으로 변환하는 프로그램 — 바로 글의 처음에 말했던 정의 그대로입니다.
슬슬 숨이 차오르시나요? 괜찮습니다. 여기까지 왔다면 골인은 눈앞입니다. 방금 나온 역폴란드 식
4 10 2 3 * - 4 5 3 - / / +
을 아까 만든 스택 머신에 흘려 넣기만 하면 됩니다. 기억하시나요, 그 엄청나게 간단한 규칙.
기계적으로 돌리면... 정확히 6이 나옵니다.
(코드는 쉽게 쓸 수 있으므로 생략합니다)
그리고 당신이 한 일을 정리하면... 이런 느낌입니다
"소스 코드를 컴파일하고, VM에서 실행한다"
— 규모만 다를 뿐, 당신이 평소 사용하는 프로그래밍 언어 처리계와 완전히 같은 구조입니다.
사칙연산밖에 못 하는 장난감이지만, 본질은 진짜입니다.
축하합니다!
당신은 이제 사칙연산을 계산하는 프로그램을 컴파일러 + VM (스택 머신) 구성으로 작성할 수 있는 엔지니어입니다. 아빠, 이제 당당하게 가슴을 펼 수 있겠네요.
이처럼 yacc는 매우 강력한 도구입니다.
여기서 더 나아가 진짜 프로그래밍 언어를 만드는 것까지도 가능합니다.
yacc의 실전 사용법을 배우기 위해 추천할 만한 책을 소개하겠습니다.
아주 오래된 책이지만, 커니핸의 **“The UNIX Programming Environment”**라는 책이 있습니다. 일본어판 신판(현지 제목: UNIXプログラミング環境)도 있습니다. (그쪽이 더 싸지만, 코드 예제에 오탈자가 있어서 고생할 가능성이 큽니다)
이 책의 8장 "Program Development"가 바로 yacc를 사용해 간단한 계산기부터 시작해서 그것을 확장해 프로그래밍 언어를 만드는 연습으로 되어 있습니다.
저희 회사에서는 이 책을 들고 컴파일러 만드는 법을 즐겁게(?) 배우고 있습니다. (저는 전임자로부터 넘겨받아 강사를 맡고 있습니다)
"이 AI가 뭐든지 다 해주는 시대에, 왜 굳이 컴파일러 같은 걸 만들어야 하는데!"
라고 생각하는 분도 많을 겁니다.
하지만 컴파일러의 구조를 모른다는 것은, 프로그램이 컴퓨터에서 어떻게 실행되는지 모른다고 말하는 것과 같습니다.
그런 당신은 서두의 질문에 뭐라고 답하시겠습니까?
"아빠는 말이야, 프로그램이 어떻게 동작하는지 몰라. 기본적인 사칙연산조차도. 심지어 프로그램도 전부 AI한테 써 달라고 하고 있어. 무슨 일이 일어나는지 전혀 모르지. 대단하지?"
라고 답하실 건가요?
그뿐만이 아닙니다. 실제 업무에서도 식 같은 것을 평가해서 계산해야 하는 경우는 의외로 있습니다. 그럴 때 아예 방향조차 세울 수 없다면?
(네? 엑셀 함수를 프런트엔드에서 실행하고 싶다고요? 대체 누가 그런 변태 같은 생각을... 돌아가 주세요. 개인적으로는 좋아합니다만.)
그리고 구조를 이해하지 못하면 간단한 변경조차 할 수 없습니다. (예: + - 를 * / 보다 우선해서 계산하도록 규칙을 바꾸고 싶다고 하면 어떻게 할 건가요?)
내가 상상도 못 하는 일은 AI에게 부탁하는 것도 어렵다는 말이죠.
엔지니어의 가치의 본질이 다시 묻히기 시작한 요즘이지만, 강하게 살아남을 힘을 길러 갑시다!
제 학부 시절 지도교수이셨던 유아사 다이치 선생님의 저서를 소개해 두겠습니다. 제목은 그야말로 직구로 "コンパイラ". 실전보다는 이론 쪽에 가까운 책이지만, 이론을 깊이 이해하고 싶은 분께 추천합니다.
https://www.amazon.co.jp/情報系教科書シリーズ-コンパイラ-湯淺-太一/dp/4274216209
이야, 그때는 정말 하나도 모르겠더라고요. (지금도 안다고는 하지 않겠습니다, 식은땀)