ENE414 프로그래밍언어론강의노트 1 1 문법, 핵심구문나무, 인터프리터 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2012년 1학기 (version 0.35) 1 c David A. Schmidt, 도경구 (2012). 본문서는 Kansas State Univers

Transcription

1 ENE414 프로그래밍언어론강의노트 1 1 문법, 핵심구문나무, 인터프리터 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2012년 1학기 (version 0.35) 1 c David A. Schmidt, 도경구 (2012). 본문서는 Kansas State University의 David A. Schmidt 교수의강의노트 Introduction to Programming-Language Paradigms* 를한양대학교 ERICA캠퍼스컴퓨터공학과학부 3학년프로그래밍언어론강의용으로번역하여개작하였습니다. 수업이외의용도로원저자및번역개작자의허락없이무단복제하여배포할수없습니다. (*

2 내가쓴글을다른사람은어떻게이해할까? 서로약속된공용어로문법에맞게글을쓰면, 다른사람은내가사용한단어와문장의뜻 ( 의미 ) 을이해할수있을것이다. 컴퓨터와소통하기위해서프로그래밍언어로프로그램을짤때도같은원리가적용된다. 컴퓨터도프로그래머도사용하는프로그래밍언어의구문과의미를알고있어야한다. 구문syntax: 단어와문장의철자법과문법 생김새 의미semantics: 단어와문장의뜻 실행결과 표현 구문은문법grammar으로표현한다. 일반적으로 BNF(Backus-Naur Form) 를가장널리쓴다. 경우에따라서구문다이어그램syntax diagram과같이그림으로표현하기도하지만원칙적으로표기방식은같다. 의미는표현방식이다양하다. 수학함수로의미를표현하는함수의미표기법denotational semantics, 실행성질을논리식으로표현하는공리의미표기법axiomatic semantics, 실행과정을규칙으로표현하는실행의미표기법operational semantics이있다. 이중에서실행의미표기법은실제프로그래밍언어를사용하여프로그램으로표현가능하며, 이를인터프리터 ( 해석기 )interpreter라고한다. 이해 프로그램의구문구조를이해하는프로그램은파서parser이다. 파서는문자열로작성된프로그램을핵심구문트리로만들어준다. 프로그램의의미를이해하는프로그램은인터프리터이다. 인터프리터는핵심구문트리의의미를이해하고실행하여결과를내준다. 이장에서는파서와인터프리터프로그램으로언어의구문과의미를상세하게이해하는기술에대해서공부하려고한다. 1. 문법 BNF 1950년대에노암촘스키Noam Chomsky 교수는나무tree 형식으로문장의구문을표현할수있음을알아챘다. 그리고구문에맞는문장을만드는규칙을귀납방정식inductive equations으로정의할수있다는사실을발견하고, 그정의를문법grammar이라고하였다. 이후에존박커스John Backus 와피터나우어Peter Naur는똑같은개념을따로발견했고실제로프로그래밍언어의구문을정의하는데사용할수있도록발전시켰다. 그래서 BNFBackus-Naur Form라고하기도한다. 문법은방정식 ( 규칙 ) 의집합으로방정식끼리서로참조하면서얽혀있는연립방정식으로볼수있으며, 단어로나열된문장의집합을정의한다. 사례탐구를통해서문법을어떻게정의하는지알아보자. 1

3 1.1 사례탐구 : 산술식수numeral와덧셈뺄셈연산자로구성된산술식arithmetic expression을작성하는구문을상세하게정의해보자. 먼저구문도메인syntax domain을다음과같이정의한다. E, E1, E2 : Expression O : Operator N : Numeral Expression, Operator, Numeral은각각구문도메인으로, Expression은정의하는모든산술식의집합이고, Operator는덧셈, 뺄셈연산자기호의집합이고, Numeral은숫자열의집합으로보면된다. 왼쪽에있는 E, E1, E2, O, N 구문도메인에속한산술식, 연산자기호, 숫자열을가리키는이름으로문법변수nonterminal라고한다. 구문도메인정의를사용하여산술식의구문을정의하는문법을다음과같이방정식으로표현할수있다. (1) E ::= N ( E1 O E2 ) (2) O ::= + - (3) N ::= 숫자열문법변수가아닌나머지단어또는기호는문법상수terminal라고한다. 위의문법에서문법변수와문법상수를모두찾아보자. 식 (1) 은산술식 (E) 을어떻게구성하는지정의한다. 산술식은임의의숫자열하나 (N) 로구성하거나, 아니면여는괄호기호 ((), 산술식 (E1), 연산자기호 (O), 산술식 (E2), 닫는괄호기호 ()) 순으로나열하여구성할수있다. ( 여기서 는 또는 을의미한다.) 숫자열 N은위에서말로정의했지만, 다음과같이상세하게문법으로정의할수도있다. D : Digit N ::= D D N D ::= 하지만 N과같이수 ( 또는단어 ) 의철자법은말로만정의해도의도를분명히전달할수있어서앞에서와같이대부분말로정의한다. 산술식 Expression의문법규칙을정의했으므로이제특정산술식이문법에맞는지검증할수있다. (4 - (3 + 2)) 검증절차는다음과같이말로기술할수있다. 1. 4와 3과 2는모두 N이다. 2. N은모두 E 산술식이므로 3과 2는 E 산술식이고, + 는 OPERATOR 기호이다. 따라서 (3 + 2) 는 E 산술식이다. 2

4 3. 4와 (3+2) 는모두 E 산술식이고, -는 O 기호이다. 따라서 (4 - (3 + 2)) 는 E 산술식이다. 말대신위에서정의한문법규칙을이용하여전개하면훨씬더상세하게검증할수있는데이를 유도derivation라고한다. (4 - (3 + 2)) 는다음과같이유도한다. E => ( E O E ) => ( N O E ) => ( 4 O E ) => ( 4 + E ) => ( 4 + ( E O E )) => ( 4 + ( N O E )) => ( 4 + ( 3 O E )) => ( 4 + ( 3 - E )) => ( 4 + ( 3 - N )) => ( 4 + ( 3-2 )) 유도는아래와같이유도나무derivation tree로그릴수도있다. 수와기호를나열하여 Expression 산술식을만드는필요충분조건은문법규칙을가지고수와기호로구성된유도나무를만들수있느냐이다. 지금까지본바와같이문법규칙으로언어의구문을상세하게정의할수있다. 프로그램을읽고의미를이해하는 (= 실행하는 ) 컴파일러와인터프리터프로그램을만들기전에문법규칙을먼저이해해야한다. 연습문제 1. 산술식 ((4-3) + 2) 를유도해보고, 유도나무를그려보자 는문법에맞는 Expression 문구가왜아닐까? 3

5 1.2 사례탐구 : 미니명령언어프로그래밍언어전체의구조를문법으로정의할수있다. 간단한미니명령언어의문법규칙을정의해보자. 먼저구문도메인을정의하자. P : Program CL : CommandList C : Command V : Var E : Expression N : Numeral O : Operator 여기서 Program은미니명령어프로그램의집합이고, Command는명령문의집합, CommandList 는 1개이상나열된명령문의집합이고, Var는 "print", "while", "end" 를제외한문자열의집합이다. P ::= CL CL ::= C C ; CL C ::= V = E print V while E : CL end E ::= N V ( E1 O E2 ) O ::= + - 문법규칙에의하면명령문 (C) 은지정문assignment 또는프린트문또는 while 루프로구성하고, 프로그램 (P) 은그러한명령문을하나이상나열하여구성한다. while 루프의몸체내부에도명령문을나열할수있다. 문법규칙은구문에대해서만정의하고그문구의뜻이무엇인지설명해주지않으므로, while x : x = (x - 1) end와같은프로그램이어떻게작동하는지문법규칙만봐서는알길이없다. 이는의미semantics 이슈이며곧뒤에서공부하게된다. 연습문제 1. 다음프로그램Program의유도나무를그려보자. x = (2 + x) x = 3; print x x = 3 ; while x : x = (x - 1) end ; print x 4

6 2. 핵심구문나무 유도나무는문장의복잡한내부구조를모두보여준다. 하지만유도나무의내부구조는좀지나치게복잡하여의미를파악하는데 ( 실제로프로그램을실행하는데 ) 필요없는부분은제거하고필요한실제모양만유지하도록간단하게만들필요가있다. 이렇게간단한형태로바꾼나무를핵심구문나무abstract-syntax tree 라고하고, 유도나무는상세구문나무concrete-syntax tree 라고한다. (4 - (3 + 2)) 을유도하면서만든핵심구문나무는다음과같다. 앞에서본유도나무와비교하면훨씬단출하지만, 실제로계산에필요한기본구조는동일하다. 문법과나무를다루는프로그램을만들려면 Python, Scheme, ML, OCaml과같이중첩리스트nested list를허용해주는자료구조를제공하는언어를쓰면좋다. 왜냐하면핵심구문나무는중첩리스트로쉽게표현되기때문이다. 위의핵심구문나무를 Python 리스트로표현하면다음과같다. ["-", "4", ["+", "3", "2"]] ((2+1) - (3-4)) 를핵심구문나무로표현하면, ["-", ["+", "2", "1"], ["-", "3", "4"]] 프로그램 x = 3; while x : x = (x -1) end; print x를핵심구문나무로표현하면, [["=", "x", "3"], ["while", "x", [["=", "x", ["-", "x", "1"]]]], ["print", "x"] ] 원하면전체를아래와같이한줄로늘어놓아도상관은없지만위와같이줄을띄우고약간의들여쓰기를하여맞추어나열하면보기가좋다. [["=", "x", "3"], ["while", "x", [["=", "x", ["-", "x", "1"]]]], ["print", "x"]] COMMANDLIST는명령문핵심구문나무의리스트로표현했다. 리스트로핵심구문나무를표현하면프로그램하기용이하므로앞으로쭉사용하도록하겠다. 연습문제 1. 앞의연습문제에서그린유도나무를모두핵심구문나무로바꾸시오. 5

7 핵심구문나무의 의미 3. 인터프리터(실행기)가 프로그램을 실행하기 위해서, 해당 프로그램 파일을 파싱하여 핵심구 문나무를 먼저 만들고, 핵심구문나무의 의미를 계산(실행)한다. (컴파일러가 프로그램을 번역 하기 위해서, 해당 프로그램 파일을 파싱하여 핵심구문나무를 먼저 만들고, 핵심구문나무를 다른 언어로 번역한다.) 핵심구문나무를 정의하는 BNF 규칙은 재귀적으로 정의하므로, 의미를 계산하는 함수도 재귀적으로 나무를 훑어서 의미를 계산한다. 자세히 예를 통해서 살펴보자. 3.1 산술식의 의미 산술식의 핵심구문나무는 두 가지 종류가 있으며, BNF 규칙으로 다음과 같이 정의할 수 있다. TREE ::= OP ::= NUMERAL + [ OP, TREE, TREE ] - 여기서 NUMERAL은 수를 나타내는 숫자열string of digits이다. 즉, 핵심구문나무는 하나의 수이거나 연산자기호와 2개의 하부나무subtree로 구성된 리스트 이다. 핵심구문나무를 훑으면서 의미를 계산하려면, 문법규칙의 귀납구조에 맞게 재귀호출을 하는 함수를 구현하면 된다. 산술식 핵심구문나무의 의미는 정수integer이다. 예를 들어, ["-", ["+", "2", "1"], ["-", "3", "4"]]를 계산하면 결과는 정수 4가 된다. 핵심구문나무를 훑어가면서 결과를 계산하는 함수 eval을 작성해보자. eval은 핵심구문나무의 의미semantics를 정의하는 함수이다. 즉, eval 함수는 산술식 언어의 인터프리터interpreter(해석기)인 셈이다. Python으로 작성한 완성된 인터프리터는 다음과 같다. # file: "eval.py" def eval(t) : pre: t == TREE, where TREE ::= NUMERAL [ OP, TREE, TREE ] OP ::= "+" "-" NUMERAL ::= 숫자열 post: ans == t의 의미(계산결과) returns: ans # case1: TREE == NUMERAL if isinstance(t, str) : if t.isdigit() : ans = int(t) raise Exception # t가 문자열인가? # t가 숫자로만 된 문자열인가? # 문자열을 해당 정수로 변환(cast) # t가 정수가 아님 # 프로그램 멈춤 6

8 # case2: TREE == [ OP, TREE, TREE ] op = t[0] t1 = t[1] t2 = t[2] # 왼쪽 하위나무의 답을 구함: ans1 = eval(t1) # 오른쪽 하위나무의 답을 구함: ans2 = eval(t2) if op == "+" : ans = ans1 + ans2 elif op == "-" : ans = ans1 - ans2 # 연산자가 + 또는 - 가 아님 print("eval error:", t, "is illegal") raise Exception # 프로그램 멈춤 return ans 함수의 재귀호출은 핵심구문나무를 정의한 문법규칙의 귀납구조와 정확하게 일치한다. 재 귀호출은 하부나무의 의미를 계산한 후, 이를 묶어서 전체 나무의 의미를 계산하는 방식으로 작동한다. 연습문제 위의 eval 함수를 eval.py라는 이름의 파일에 복사하고, Python 실행기를 띄워보자. 다음과 같은 예제를 만들어서 함수 호출을 해보자. eval( ["-", ["+", "2", "1"], ["-", "3", "4"]]) 위 함수 호출의 실행 과정을 추적해보자. eval 함수를 재귀 호출하면, eval 함수 호출 자리에 eval 함수 몸체를 복제하여 실행과정을 추적한다. 이를 복제규칙 의미계산copy-rule semantics 라고 하는데, 실제로 실행기가 실행할때는 함수를 호출할 때마다 필요한 정보를 보관하는 활 성레코드activation record를 만든다. 복제규칙 의미계산으로 실행 과정을 추적해보면 실행기가 실행할 때 어떠한 방식으로 활성레코드 스택을 확장하고 축소하는지 알 수 있다. eval( ["-", ["+", "2", "1"], ["-", "3", "4"]] ) => op = "-" t1 = ["+", "2", "1"] t2 = ["-", "3", "4"] ans1 = eval(t1) => op = "+" 7

9 t1 = "2" t2 = "1" ans1 = eval(t1) => ans = 2 => ans = 1 => ans = 3 => ans = 4 = 2 ans2 = eval(t2) = 1 ans = 2+1 = 3 = 3 ans2 = eval(t2) => op = "-" t1 = "3" t2 = "4" ans1 = eval(t1) = 3 ans2 = eval(t2) = 4 ans = 3-4 = -1 = -1 ans = 3 - (-1) = 4 = 4 실행과정 추적에서 =>는 핵심구문나무의 하부나무를 대상으로 eval 함수를 새로이 재귀호 출함을 나타낸다. 새롭게 재귀호출하면 지역변수의 고유 이름영역이 생기고 자신의 영역에서 답을 계산하는데 사용된다. 궁극적으로 돌아온 답은 모아져서 최종 계산을 하는데 사용된다. 재귀호출 패턴은 핵심구문나무의 구조 패턴과 정확하게 일치한다. 3.2 번역하기 컴파일러compiler(번역기translator)는 프로그램 파일을 파싱하여 핵심구문나무로 변환하 고, 이어서 (기계어와 같은) 다른 언어의 프로그램으로 변환하는 프로그램이다. 예를 들면, C 컴파일러는 C 프로그램을 어셈블리어(기계어)로 번역하고, 자바Java 컴파일러는 자바 프로그 램을 자바가상머신Java Virtual Machine에서 실행되는 자바바이트코드Java Bytecode로 번역한다. 이 절에서는 핵심구문나무를 연산자후위표기법postfix을 사용하는 바이트코드bytecode로 컴 파일해보자. 이는 실제로 자바 컴파일러가 바이트코드로 번역하는 방식과 원칙적으로 같다. # file: postfix.py def postfix(t) : pre: t == TREE, where TREE ::= NUM [ OP, TREE, TREE ] post: ans == t안에 있는 연산자기호들을 연산자후위표기법으로 나열 returns: ans 8

10 # case1: TREE == NUMERAL if isinstance(t, str) : # t가 문자열인가? # t가 숫자로만 된 문자열인가? if t.isdigit() : ans = t #(*) # t에 숫자가 아닌 문자가 있음 raise Exception # case2: TREE == [ OP, TREE, TREE ] # t의 모양은 리스트 [op, t1, t2] op = t[0] t1 = t[1] t2 = t[2] # 왼쪽 하위나무의 문자열 생성: ans1 = postfix(t1) # 오른쪽 하위나무 문자열 생성: ans2 = postfix(t2) # 하위 나무에서 구한 답을 연결: if op == "+" : ans = ans1 + ans2 + "+" #(*) elif op == "-" : ans = ans1 + ans2 + "-" #(*) print("error:", t, "is illegal") raise Exception # 프로그램 멈춤 return ans 이 코드는 eval 함수의 코드와 거의 같다. 그러나 실제로 #(*)로 표시된 부분에서 답을 계 산하는 대신 후위표기법으로 문자열을 재생성하였다. 예를 들어, postfix(["+", ["-", "2", "1"], "4"])는 "21-4+"와 같은 후위표기법 문자열을 생성한다. 수행하는 연산자가 뒤에 붙어 있어서 어떤 연산을 할지 알려준다. 이 연산의 실행과정은 다음과 같이 추적할 수 있다. postfix(["+", ["-", "2", "1"], "4"]) => op = "+" t1 = ["-", "2", "1"] t2 = "4" ans1 = postfix(t1) => op = "-" t1 = "2" t2 = "1" 9

11 ans1 = postfix(t1) => ans = "2" = "2" ans2 = postfix(t2) => ans = "1" = "1" ans = "2" + "1" + "-" = "21-" = "21-" ans2 = postfix(t2) => ans = "4" = "4" ans = "21-" + "4" + "+" = "21-4+" 여기서도 각 =>는 핵심구문나무의 하부나무를 대상으로 postfix 함수를 새로이 재귀호출함을 나타낸다. 아직도 이해가 가지 않으면 print 명령을 다음과 같이 적재적소에 삽입하여 나무를 연산자후위표기법으로 변환하는 과정을 따라가보면 이해가 쉬워질 것이다. # file: postfixx.py def postfixx(level, t) : pre: t == TREE, where TREE ::= INT [ OP, TREE, TREE ] level == 후위연산자가 붙는 전체 나무에서 t의 깊이를 나타내는 정수 post: ans == t안에 있는 심벌들을 연산자후위표기법으로 나열 returns: ans print(level * " ", "Entering subtree t=", t) # case1: TREE == NUMERAL if isinstance(t, str) : # t가 문자열인가? if t.isdigit() : ans = t # t가 숫자로만 된 문자열인가? #(*) # t에 숫자가 아닌 문자가 있음 raise Exception # case2: TREE == [ OP, TREE, TREE ] # t의 모양은 리스트 [op, t1, t2] op = t[0] t1 = t[1] t2 = t[2] # 왼쪽 하위나무의 문자열 생성: ans1 = postfixx(level + 1, t1) # 오른쪽 하위나무의 문자열 생성: 10

12 ans2 = postfixx(level + 1, t2) # 하위나무에서구한답을연결 : ans = ans1 + ans2 + op print(level * " ", "Exiting subtree t=", t, " ans=", ans) print() return ans postfixx(0, ["+", "2", ["-", "3", "4"]]) 를 Python으로실행하보자. 어떤결과가프 린트되는가? Entering subtree t= [ +, 2, [ -, 3, 4 ]] Entering subtree t= 2 Exiting subtree t= 2 ans= 2 Entering subtree t= [ -, 3, 4 ] Entering subtree t= 3 Exiting subtree t= 3 ans= 3 Entering subtree t= 4 Exiting subtree t= 4 ans= 4 Exiting subtree t= [ -, 3, 4 ] ans= 34- Exiting subtree t= [ +, 2, [ -, 3, 4 ]] ans= 컴퓨터는잎사귀 leaf 의답을모아서전체나무의답을계산하는데, 나무를깊이우선순으로 왼쪽에서오른쪽으로훑어내려간다. 3.3 명령문의의미 : 소형인터프리터구조 앞절에서배운기술을가지고실제프로그래밍언어의의미를달아줄수있다. 여기서도앞에서 본미니명령언어를가지고공부해보자. PROGRAM ::= COMMANDLIST COMMANDLIST ::= COMMAND COMMAND ; COMMANDLIST COMMAND ::= VAR = EXPRESSION print VAR while EXPRESSION : COMMANDLIST end EXPRESSION ::= NUMERAL VAR ( EXPRESSION OPERATOR EXPRESSION ) OPERATOR ::=

13 여기서 NUMERAL은숫자열의집합이고, VAR는 print, while, end를제외한문자열의집합이다. 이프로그램을보자. x = 3 ; while x : x = x - 1 end ; print x 그러면이프로그램의핵심구문나무는다음과같다. [["=", "x", "3"], ["while", "x", [["=", "x", ["-", "x", "1"]]]], ["print", "x"] ] 핵심구문나무에는 COMMANDLIST, COMMAND, EXPRESSION 등 3가지다른레벨이있다. 프로그램은그자체가 COMMANDLIST이며, 핵심구문나무를정의하는문법은다음과같다. PTREE ::= CLIST CLIST ::= [ CTREE+ ] 여기서 + 는한번이상반복해서나타남을표시함 CTREE ::= ["=", VAR, ETREE] ["print", VAR] ["while", ETREE, CLIST] ETREE ::= NUMERAL VAR [OP, ETREE, ETREE] 여기서 OP는 "+" 아니면 "-" 여기서각비단말자마다하나씩인터프리터함수를만드는데, 각함수가그비단말자에해당하는프로그램의의미를나타낸다. Python과 Java 내부적으로내장되어있는인터프리터도같은원리로만든다. 인터프리터의구조는아래그림과같이그릴수있다. 여기서화살표는입력데이터의흐름과데이터구조의호출흐름이있음을나타낸다. Python 으로데이터구조와함수를작성하여미니명령언어의인터프리터를만들어보자. 12

14 변수와루프로구성된미니명령언어의인터프리터프로그램 There is one crucial data structure: ns = {} # ns는이름등록부 (namespace) 이다. 프로그램변수의이름과값을알고있다. # Python의해시테이블, 즉, 사전 (dictionary) 을사용한다. # 예를들어, ns = { x = 2, y = 0} 이면, # 변수 x는정수 2의이름이고, 변수 y는정수 0의이름이다. def interpretclist(p) : pre: p == CLIST로표현된프로그램, CLIST ::= [ CTREE+ ] post: ns == 프로그램 p를실행한후변경된이름등록부 for command in p : interpretctree(command) def interpretctree(c) : pre: c == CTREE로표현된명령문, CTREE ::= ["=", VAR, ETREE] ["print", VAR] ["while", ETREE, CLIST] post: ns == 명령문 c를실행한후변경된이름등록부 operator = c[0] if operator == "=" : # 할당문 ["=", VAR, ETREE] var = c[1] # 좌변을가져옴 exprval = interpretetree(c[2]) # 우변을계산함 ns[var] = exprval # 우변값을좌변변수에저장 elif operator == "print" : # 프린트문 ["print", VAR] var = c[1] if var in ns : # 변수이름이이름등록부에등록되어있는지확인 ans = ns[var] # 해당값을가져옴 print(ans) crash("variable name undefined") elif operator == "while" : # while문 expr = c[1] body = c[2] while (interpretetree(expr)!= 0) : 13

15 interpretclist(body) # 오류 crash("invalid command") def interpretetree(e) : pre: e == ETREE로표현된식, ETREE ::= NUMERAL VAR [OP, ETREE, ETREE] 여기서 OP는 "+" 아니면 "-" post: ans == 식 e를계산한결과값 returns: ans if isinstance(e, str) and e.isdigit() : # 숫자열인지확인 ans = int(e) elif isinstance(e, str) and len(e) > 0 and e[0].isalpha() : # 변수이름인지확인 if e in ns : # 변수이름이이름등록부에등록되어있는지확인 ans = ns[e] # 해당값을가져옴 crash("variable name undefined") # [op, e1, e2] op = e[0] ans1 = interpretetree(e[1]) ans2 = interpretetree(e[2]) if op == "+" : ans = ans1 + ans2 elif op == "-" : ans = ans1 - ans2 crash("illegal arithmetic operator") return ans def crash(message) : pre: message == 문자열 post: message을출력하고, 인터프리터를종료함 print(message + "! crash! core dump: ", ns) raise Exception # 인터프리터를종료함 14

16 def main(program) : pre: program == PTREE로 표현된 프로그램, PTREE ::= post: CLIST ns == 프로그램을 모두 실행한 후 변경된 이름등록부 global ns # ns는 전역변수 ns = {} interpretclist(program) print("final namespace =", ns) main 함수는 인터프리터의 시동을 건다. main([["=", "x", "3"], ["while", "x", [["=", "x", ["-", "x", "1"]], ["print", "x"]]], ]) 위 프로그램은 3을 x 에 할당하고 x의 값을 2에서 1로, 다시 0으로 감소시키고, 루프를 마치는 프로그램이다. 연습문제 위의 실행기 코드를 실행시켜보시오. 가상머신 컴퓨터 하드웨어는 특정 기계어밖에 이해하지 못한다. 실행기는 우리가 사용하는 언어로 작성 한 프로그램을 컴퓨터가 직접 이해하는 것처럼 보이게 하는 역할을 하므로, 실행기를 가상머 신virtual machine이라고 하기도 한다. 단순무식 미니명령언어 컴파일러 3.4 명령문으로 구성된 프로그램은 바로 실행할 수 있는 실행기(인터프리터)가 없거나 기타 다른 이유로 직접 실행가능한 다른 언어로 번역해야 할 경우가 많다. C 프로그램은 특정 컴퓨터 프로세서가 이해하는 코드로 번역하여 실행하고, Java의 경우 자바바이트코드Java bytecode로 번역하여 자바가상컴퓨터Java Virtual Machine로 실행한다. 컴파일러를 이해하기 위해서 미니명 령언어를 자바바이트코드와 유사한 바이트코드로 번역하는 컴파일러를 만들어보자. 후위 산술 식으로 번역하는 방식과 유사하게, 미니명령언어 실행기를 수정하여 다음과 같은 미니명령언어 프로그램을 x = 3 ; while x : x = x - 1 end ; 15

17 print x 다음과 같은 바이트코드로 번역하는 컴파일러를 만들어보자. LOADNUM 3 STORE x BEGINLOOP LOAD x IFZERO EXITLOOP LOAD x LOADNUM 1 SUBTRACT STORE x ENDLOOP PRINT x 바이트코드 명령과 실행의미는 아래와 같다. 바이트코드는 실행할 때 스택메모리를 사용한 다. LOADNUM n n을 스택에 밀어넣음 LOAD v 심볼테이블에서 v 변수 값을 스택에 밀어넣음 ADD 스택 꼭대기 두 값을 꺼내서 더한 값을 다시 스택에 밀어넣음 SUBTRACT 스택 꼭대기 두 값을 꺼내서 뺀 값을 다시 스택에 밀어넣음 STORE v 스택의 꼭대기 값을 꺼내서 심볼테이블의 v에 저장 PRINT v 스택의 꼭대기 값을 꺼내서 화면에 출력 IFZERO EXITLOOP 스택의 꼭대기 값을 꺼내보고 0이면 루프의 끝으로 빠져나감 BEGINLOOP 루프의 시작지점 ENDLOOP 루프의 끝지점 컴파일할 때, 실행하면서 지정할 변수 목록을 심볼테이블symboltable로 유지한다. 지정하는 변 수를 심볼테이블symboltable에 저장하여 기억해두고 지정한 변수만 사용하는지 컴파일하면서 점검한다. 변수와 루프로 구성된 미니명령언어의 컴파일러 프로그램. 프로그램을 바이트코드로 번역함: 16

18 symboltable = [] # 심벌테이블 : 실행시간에메모리에저장될변수이름목록. # 프로그램의 " 선언점검 " 에사용됨. def compileclist(p) : pre: p is CLIST로표현된프로그램, CLIST ::= [ CTREE+ ] post: ans == 프로그램 p를컴파일한바이트코드 returns: ans ans = "" for command in p : ans = ans + compilectree(command) return ans def compilectree(c) : pre: c == CTREE로표현된명령문, CTREE ::= ["=", VAR, ETREE] ["print", VAR] ["while", ETREE, CLIST] post: ans == 명령문 c를컴파일한바이트코드 returns: ans operator = c[0] if operator == "=" : # 할당문 ["=", VAR, ETREE] var = c[1] # 좌변을가져옴 exprcode = compileetree(c[2]) symboltable.append(var) # 심벌테이블목록에변수이름추가 ans = exprcode + "STORE " + var + "\n" elif operator == "print" : # 프린트문 ["print", VAR] var = c[1] if var in symboltable : # 변수이름이이름등록부에등록되어있는지확인 ans = "PRINT " + var + "\n" crash("variable name undefined") elif operator == "while" : # while문 expr = c[1] body = c[2] exprcode = compileetree(c[1]) 17

19 bodycode = compileclist(c[2]) ans = "BEGINLOOP \n" + exprcode \ + "IFZERO EXITLOOP \n" + bodycode + "ENDLOOP \n" # 오류 crash("invalid command") return ans def compileetree(e) : pre: e == ETREE로표현된식, ETREE ::= NUMERAL VAR [OP, ETREE, ETREE] 여기서 OP는 "+" 아니면 "-" post: ans == 식 e를컴파일한바이트코드 returns: ans if isinstance(e, str) and e.isdigit() : # 숫자열인지확인 ans = "LOADNUM " + e + "\n" elif isinstance(e, str) and len(e) > 0 and e[0].isalpha() : # 변수이름인지확인 if e in symboltable : # 변수이름이이름등록부에등록되어있는지확인 ans = "LOAD " + e + "\n" crash("variable name undefined") # [op, e1, e2] op = e[0] ans1 = compileetree(e[1]) ans2 = compileetree(e[2]) if op == "+" : ans = ans1 + ans2 + "ADD \n" elif op == "-" : ans = ans1 + ans2 + "SUBTRACT \n" crash("illegal arithmetic operator") return ans def crash(message) : pre: message == 문자열 post: message을출력하고, 컴파일러를종료함 18

20 print(message + "! crash!", symboltable) raise Exception # 컴파일러를 종료함 def main(program) : pre: program == PTREE로 표현된 프로그램, PTREE ::= CLIST post: 프로그램을 모두 컴파일한 바이트코드 global symboltable # symboltable은 전역변수 symboltable = [] code = compileclist(program) print(code) 컴파일러는 핵심구문나무를 훑으면서 바이트코드를 문자열로 생성한다. 사소할 수도 있지 만 인터프리터와 컴파일러의 중요한 기술적인 차이점을 비교해보자. 인터프리터는 지정문을 실행하면서 이름등록부namespace를 사용하여 데이터를 저장, 수정, 참조하지만, 컴파일러는 지 정문을 실행하지 않고 번역만 하므로 이름등록부는 필요없다. 대신 프로그램이 실행중에 어떤 변수를 만들고 사용할 것인지를 기록하는 새로운 구조인 심볼테이블symboltable이 필요하다. 심볼테이블은 실행시간 메모리 사용을 예견해주는 일종의 고스트 역할을 하여, 지정되지 않은 변수를 사용하는 오류를 찾는데 도움을 준다. 실행 중 발생할 프로그램 오류를 컴파일하 면서 미리 발견하는 것이다. (만약 미니명령언어를 타입정보와 함께 변수를 미리 선언하도록 만들었다면, 심벌테이블에 타입정보를 저장하여 컴파일하면서 타입검사도 할 수 있었을 것이 다.) 여기서 공부한 컴파일러에서 while루프에 해당하는 바이트코드는 실제 컴파일러가 현장에 서 만들어내는 바이트코드에 비해서 단순하다. 실제 컴파일러는 루프를 번역할때 jump 명령과 레이블label을 같이 생성한다. 예를 들면, 앞에서 컴파일한 다음 코드는 LOADNUM 3 STORE x BEGINLOOP LOAD x IFZERO EXITLOOP LOAD x LOADNUM 1 SUBTRACT STORE x ENDLOOP PRINT x 현장에서는 다음과 같이 컴파일한다. 19

21 LOADNUM 3 STORE x LABEL1: LOAD x JUMPZERO LABEL2 LOAD x LOADNUM 1 SUBTRACT STORE x JUMP LABEL1 LABEL2: PRINT x 우리는기본개념만보여주려고했으므로상대적으로복잡한레이블생성은생략하였음을양해바란다. 3.5 인터프리터를쓸까? 컴파일러를쓸까? 새로운언어를설계할때항상인터프리터interpreter를먼저만든다. 그래야그언어의의미를이해할수있기때문이다. 시간과공간적인성능이중요하다면, 인터프리터를컴파일러compiler 로변경한다. 컴파일러는파싱, 핵심구문나무생성과같은지루한작업과변수선언점검, 연산의타입호환성등과관련한일상적인점검을수행하고나서, 컴파일할코드로번역하는절차를진행한다. 컴파일한결과는소형이면서빠르게실행되는프로그램이될것이다. 인터프리터작성에사용되는언어를하드웨어가이해하지못한다면, 인터프리터를수정하여하드웨어가이해하는언어로된프로그램을만들어내는컴파일러를만들면된다. ( 혹시하드웨어가이해하는언어로인터프리터를만들수있을까? 그게더쉬울지도모른다.) 프로그램을펌웨어firmware 또는칩에구어넣을수있다면, 파싱, 핵심구문나무생성, 변수선언점검, 타입호환성검사등을한번만하고컴파일된코드를펌웨어나칩에구워넣을수있도록인터프리터를컴파일러로만드는편이훨씬좋을것이다. 프로그램의정확성이생명이라면, 인터프리터를사용하는편이낫다. 컴파일러보다인터프리터를분석하기도쉽고, 제대로작동하는지증명하기도쉽다. 언어를지속적으로변경하거나확장해야한다면, 인터프리터로프로그램을실행하는편이훨씬유리하다. 컴파일러를고치기는정말끔찍하게복잡하기때문이다. 4. 파싱하기 : 핵심구문나무만들기 핵심구문나무 abstract syntax tree 는재귀함수로처리하기정말쉽기때문에, 프로그램텍스트를 읽으면서동시에핵심구문나무를만들어나가도록프로그램을작성하는것이제일좋다. ( 유 20

22 도나무 자체는 실제로 만들 필요가 전혀 없다!) 이 작업을 파싱parsing이라고 한다. 컴파일러든 인터프리터든 컴파일이나 실행하기 전에 이 파싱 작업을 반드시 거쳐야 한다. 예를 들어, ((2+1) - (3-4) )와 같은 텍스트 한 줄을 읽고, ["-", ["+", "2", "1"], ["-", "3", "4"]]와 같은 핵심구문나무를 만들 수 있는 파싱 프로그램 parseexpr를 작성해 보자. 파싱은 다음과 같이 두 단계로 나누면 편리하다. 1. 어휘분석lexical analysis 또는 스캐닝scanning: 텍스트 문자열에서 의미가 있는 최소 단위 토 큰token인 연산자와 단어를 차례로 인식하여, 토큰열로 모은다. 빈칸은 무시한다. 2. 파싱: 토큰열에서 토큰을 하나씩 읽어서, 문법규칙에 따라 핵심구문나무를 만든다. 두 번째 단계는 어려워보이지만, 지금까지 공부한 기술을 그대로 적용하면 의외로 쉽게 해결할 수 있다. 문법 규칙 하나에 함수 하나씩을 작성한다. 각 문법규칙에 맞추어 토큰을 하나 씩 읽으면서 핵심구문나무를 만들어나간다. 이 기술을 재귀강하파싱recursive-descent parsing 이라고 한다. 어휘분석, 스캐닝: 토큰을 인식하여 모으기 4.1 먼저 텍스트 문자열의 문자를 하나씩 검사하여 인식한 토큰 리스트를 만드는 함수를 만들어 보자. def scan(text) : scan 함수는 텍스트 문자열에서 토큰을 차례로 찾아내어 토큰 리스트로 모은다. pre: text == 프로그램 텍스트 문자열 post: answer == text에서 찾아낸 토큰 리스트 (빈칸과 빈줄은 무시) OPERATORS = ("(", ")", "+", "-", ";", ":", "=") # 문자 한 개짜리 연산자만 처리 가능 SPACES = (" ", "\n") SEPARATORS = OPERATORS + SPACES nextword = "" # answer 리스트에 추가될 다음 토큰 answer = [] for letter in text: # 불변식(invariant): # answer + nextword + letter # === 빈칸과 빈줄을 제외하고 텍스트에서 지금까지 읽은 모든 단어와 심벌 21

23 # nextword가 완전히 모아져서 answer의 뒤에 추가할 수 있는지 확인: if letter in SEPARATORS and nextword!= "" : answer.append(nextword) nextword = "" if letter in OPERATORS : answer.append(letter) elif letter in SPACES : pass # 빈칸과 빈줄은 버림 # 단어 또는 수를 만듬 nextword = nextword + letter if nextword!= "" : answer.append(nextword) return answer 예를 들어, scan("((2+1) - (3-4) )")을 실행하면 다음과 같은 결과를 얻는다. [ (, (, 2, +, 1, ), -, (, 3, -, 4, ), ) ] 4.2 파싱: (산술)식의 핵심구문나무 만들기 토큰 리스트를 읽고 핵심구문나무를 만드는 함수를 문법규칙에 맞추어서 작성한다. 산술식Expression 의 문법규칙은 다음과 같다. E ::= N V ( E1 O E2 ) 여기서 E, E1, E2 : Expression N : Numeral 은 숫자열 V : Var 은 문자열 O : Operator 는 "+" 또는 "-" 각 문법규칙마다 핵심구문나무를 하나씩 다음과 같이 만들면 된다. N의 핵심구문나무 = N V의 핵심구문나무 = V ( E1 O E2 )의 핵심구문나무 = [O, T1, T2] 여기서 T1은 E1의 핵심구문나무이고, T2는 E2의 핵심구문나무 22

24 산술식의 토큰을 읽어서 핵심구문나무를 만드는 parseexpr 함수를 작성해보자. 앞에서 공 부한 eval 함수와 같이 문법규칙을 보면 무엇을 어떻게 해야하는지 보인다. 아래에서 정의한 전역변수global variable와 도우미 함수를 쓰면 단어를 하나씩 받아서 파싱하 기 편하다. # 변수 inputtext에 프리로 파싱할 텍스트가 저장되어 있다고 가정하자. # 토큰 리스트 생성 wordlist = scan(inputtext) nextword = "" # 다음 토큰 # 전역 불변식(global invariant): nextword + wordlist == 처리할 토큰 # 토큰 리스트의 끝을 표시하는토큰 EOF = "!" # 이 함수를 호출하면 다음에 읽을 토큰을 nextword에 저장: def : wordlist의 맨 앞에 있는 단어를 nextword에 저장 wordlist가 비어있으면 nextword에 EOF를 저장 global nextword, wordlist if wordlist == [] : nextword = EOF nextword = wordlist[0] wordlist = wordlist[1:] 산술식 핵심구문나무를 만드는 함수는 다음과 같다. def parseexpr() : nextword + wordlist의 단어를 가지고 E 핵심구문나무를 만든다, 여기서 E ::= N V ( E1 O E2 ) O 는 "+" 또는 "-" wordlist와 nextword로 구성된 전역불변식은 항상 참이다 if nextword.isdigit() : # N? ans = nextword elif isvar(nextword) : # V? ans = nextword 23

25 elif nextword == "(" : # ( E1 O E2 )? tree1 = parseexpr() op = nextword if op == "+" or op == "-" : tree2 = parseexpr() if nextword == ")" : ans = [op, tree1, tree2] error("missing )") error("missing operator") error("illegal symbol to start an expression") return ans def isvar(word) : word가 합법적인 변수이름인지 확인 KEYWORDS = ("print", "while", "end") ans = ( word.isalpha() and not(word in KEYWORDS) ) return ans def error(message) : 오류메시지를 프린트하고 파싱을 종료 print("parse error: " + message) print(nextword, wordlist) raise Exception parseexpr 함수는 문법규칙을 사용하여 다음에 처리할 입력 단어인 nextword에 대해서 어 떠한 유형의 핵심구문나무를 만들지 결정하기 위해서 적절한 확인 절차를 거친다. Expression 의 3가지 종류의 문법규칙에서 맨 앞에 있는 단어들이 서로 구별되게 만든건 우연의 일치는 아니다. 어떤 나무를 만들지 바로 결정할 수 있게 해주어야 별 문제없이 파싱을 한다. 다음의 전역 변수와 main 함수가 전체 파싱 작업을 총지휘한다. # 전역 불변식: nextword + wordlist == 처리할 토큰 24

26 nextword = "" # 다음 토큰 wordlist = [] # 토큰 리스트 EOF = "!" # 토큰 리스트의 끝을 표시하는 토큰 def main() : global wordlist # 입력 텍스트를 읽고, 단어 단위로 쪼개서, wordlist에 나열하여 붙인다. text = input("type an arithmetic expression: ") wordlist = scan(text) # 파싱을 한다. tree = parseexpr() print(tree) if nextword!= EOF : error("there are extra words") 4.3 파싱: 명령문의 핵심구문나무 만들기 앞에서 작성한 함수를 이용하여 미니명령언어의 파서를 만들 수 있다. 사용하는 기술도 대동소 이하다. def parsecommand() : nextword + wordlist의 토큰을 가지고 Command 핵심구문나무를 만든다, 여기서 C ::= V = E print V while E : CL end wordlist와 nextword로 된 전역 불변식은 항상 참이다. if nextword == "print" : # print 변수? if isvar(nextword) : ans = ["print", nextword] error("expected var") elif nextword == "while" : # while E : CL end? exprtree = parseexpr() if nextword == ":" : 25

27 error("missing :") cmdlisttree = parsecmdlist() if nextword == "end" : ans = ["while", exprtree, cmdlisttree] error("missing end") elif isvar(nextword) : # V = E? v = nextword if nextword == "=" : exprtree = parseexpr() ans = ["=", v, exprtree] error("missing =") # 오류 -- 없는명령 error("bad word to start a command") return ans 다음은 CommandList에나열된명령을모아서처리하는함수이다. def parsecmdlist() : nextword + wordlist의단어를가지고 CommandList 핵심구문나무를만든다, 여기서 CL ::= C C ; CL 즉, 하나이상의 C 가 ; 로분리되어있음 wordlist와 nextword로된전역불변식은항상참이다. anslist = [ parsecommand() ] # 첫명령파싱 while nextword == ";" : # 다른명령수집 anslist.append( parsecommand() ) return anslist 그리고다음의 main 함수가전체파싱작업을총지휘한다. def main() : 26

28 입력 미니명령언어 프로그램을 읽고 핵심구문나무를 만든다, 여기서 P ::= CL 전역 불변식이 참이 되게 wordlist와 nextword 초기화 global wordlist text = input("type the program: ") wordlist = scan(text) # assert: 전역불변식 만족 tree = parsecmdlist() # assert: tree == text 전체에 해당하는 핵심구문나무 print(tree) if nextword!= EOF : error("there are extra words") 지금까지 살펴본 방식으로 하는 파싱을 하향식 예측 파싱top-down predictive parsing 이라고 도 한다. 왜냐하면 나무의 맨꼭대기 뿌리에서부터 아래 잎새쪽으로 내려오면서 핵심구문나무를 구축하고, 입력 프로그램에서 토큰을 하나씩 보아도 구문구조를 정확히 예측할 수 있기 때문이 다. 이 기술로 파싱을 성공적으로 하기 위해서는 입력 프로그램의 정확한 장소에 항상 정확한 수의 키워드와 괄호가 있어야 한다. 파싱이론parsing theory은 문법규칙과 파서의 작성방법에 대한 학문이다. 5. 이 기술을 배워야 하는 이유 프로그래밍언어를 사용하려면 문법 규칙을 숙지하여 문법에 맞는 프로그램을 짤 수 있어야 한다. 게다가 짜는 프로그램의 의미와 프로그램이 무엇을 하려하는지도 알아야 한다. 대부분의 프로그래밍 언어는 딱딱한 말로 쓰여진 매뉴얼(참고서)을 제공한다. 운이 좋으면 예제도 곁들 여 설명해준다. 문서가 잘 작성되어 있는 경우에는 언어의 문구가 어떤 의미인지 바로 이해할 수 있지만, 때로는 이 장에서 보여준 것과 같은 정의용 인터프리터definitional interpreter를 들 여다 봐야하는 이해가 가는 경우도 있다. 살다보면 필요에 의해서 프로그래밍 언어를 자신이 직접 설계해야 하는 경우도 생긴다. 사실, 소프트웨어를 설계할 때마다 이런 요구에 맞닥뜨리 게 되는게 현실이다. 왜냐하면, 소프트웨어에 주어지는 입력은 어떤 일정한 순서로 구문구조를 지키며 주어지기 때문이다. 소프트웨어를 사용하는 사람은 그 소프트웨어와 의사소통(교류) 하기 위한 입력 언어에 대한 (문법)규칙을 알아야 한다. 경우에 따라서 그 문법규칙은 마우스를 드래그하고 클릭하는 정해진 일정 순서일 수도 있다. 일종의 수화언어인 셈이다. 하지만 프로그램에 어떤 문구를 말하고(입력하고) 싶으면, 단어와 문구와 문장으로 구성 된 입력 언어input language가 필요한다. 이러한 언어는 어떤 모습이어야 할까? 어떤 연산자, 데이터, 제어장치가 필요할까? 소프트웨어를 설계하는 경우에는 그 언어를 설계해야 하고, 그 27

29 언어를처리할파서와인터프리터를작성해야한다. 이것이바로이과목에서프로그래밍언어의구문과의미를기술하고이해하는방법을반드시배워야하는이유이다. 특정분야 ( 항공학, 통신학, 문서처리, 데이터베이스, 게임등 ) 에특화된문제를해결하기위하여설계된프로그래밍언어는그분야에딱맞는연산을할수있는기능이있어야하고, 그분야의계산유형에적합한데이터및제어구조를갖춰야한다. 특정분야에맞추어서설계된언어를도메인특화프로그래밍언어domain-specific programming language라고한다. 이강의의끝자락에서그러한언어를설계하는기본기술을배울것이다. 그러고보니, BNF 문법표기법도파서를작성하기위한특수목적프로그래밍언어의일종이다! Yacc, Bison, Antlr 등의파서자동생성프로그램은문법규칙정의를입력으로읽어서파서코드를자동으로생성해준다. 따라서현실적으로문법규칙작성을완료하면이미파서작성은완료된것으로보아도무방한것이다. 연습문제 1. 본격적인인터프리터작성을위한머리 + 몸풀기숙제 (a) 앞에서공부한미니명령언어인터프리터를돌려보자. 미니명령언어프로그램파일을읽어서파싱한후실행해야한다. 교재에나오는예제를돌려보자. 파서는 PLY로자동생성한파서를사용해야한다. (b) 미니명령언어다음과같이확장하여인터프리터를구현해보자. 산술식 (Expression에는 *( 곱셈 ), /( 정수나눗셈, 몫구하기 ), 단항 -( 부호바꿈 ) 를다음과같이추가한다. E ::=... ( E1 * E2 ) ( E1 / E2 ) - E 명령문Command에는다음과같이조건문과입력문을추가한다. C ::=... if E then CL1 else CL2 end input V 조건문의의미 : E의계산결과가 0이아니면 CL1을실행하고, 0이면 CL2를실행한다. 입력문의의미 : 실행창에서사용자입력을문자열로받아서정수로바꾸어변수 V에저장한다. (Python의 input() 명령으로구현하면됨 ) (c) 미니명령언어로 입력받은정수의계승 (factorial) 구하여화면에프린트하는프로그램 을짜서인터프리터로실행해보자. (d) 미니명령언어로 입력받은두정수의최대공약수 (gcd) 구하여화면에프린트하는프로그램 을짜서인터프리터로실행해보자. 2. 1번문제로갈증이해소되지않으면내친김에미니명령언어의컴파일러도확장해봅시다. 3. 2번문제로만든컴파일러가컴파일한바이트코드를실행할가상머신 ( 바이트코드인터프리터 ) 를만들어봅시다. 28

30 4. 파라미터없는프로시저를다음과같은구문으로추가해보자. C ::=... proc I : C call I 인터프리터에서는새로정의한프로시저의몸체를이름등록부에저장한다. ( 즉, proc I: C 의의미는 I = C 의의미와비슷하다.) 그러면 call I 의의미는무엇일까? 구현해보자. 29