![닫기 [x]](http://dw1.s81c.com/i/c.gif){kind=small}
실례지만 우리 영웅이 위기에 빠졌다는 것을 상기하라. 우리 영웅은 DSL(이 경우는 우스울 정도로 단순한 계산기 언어지만)을 만들기 위해 다음과 같이 그 언어에 적용할 수 있는 다양한 선택 사항을 담은 트리 구조를 만들었다.
- 이항 연산자(binary operator)인 더하기/빼기/곱하기/나누기
- 단항 연산자(unary operator)인 부정(negation) 연산자
- 수치 값
이 구조 이면에 있는 실행 엔진은 이 연산을 어떻게 실행하는지 알았고 심지어 결과를 내는 데 필요한 계산을 줄이기 위해 설계된 명시적인 최적화 단계도 가지고 있었다.
지난 번 작성한 마지막 코드는 다음과 같았다.
Listing 1. 계산기 DSL: AST와 해석기
package com.tedneward.calcdsl
{
private[calcdsl] abstract class Expr
private[calcdsl] case class Variable(name : String) extends Expr
private[calcdsl] case class Number(value : Double) extends Expr
private[calcdsl] case class UnaryOp(operator : String, arg : Expr) extends Expr
private[calcdsl] case class BinaryOp(operator : String, left : Expr, right : Expr)
extends Expr
object Calc
{
/**
* (수학 용어로 말하면) 수식을 단순화하기 위한 함수
*/
def simplify(e : Expr) : Expr =
{
e match {
// 부정 두 번은 원래 값
case UnaryOp("-", UnaryOp("-", x)) => simplify(x)
// + 하나는 원래 값
case UnaryOp("+", x) => simplify(x)
// x에 1을 곱하면 원래 값
case BinaryOp("*", x, Number(1)) => simplify(x)
// 1에 x를 곱하면 원래 값
case BinaryOp("*", Number(1), x) => simplify(x)
// x에 0을 곱하면 0
case BinaryOp("*", x, Number(0)) => Number(0)
// 0에 x를 곱하면 0
case BinaryOp("*", Number(0), x) => Number(0)
// x를 1로 나누면 원래 값
case BinaryOp("/", x, Number(1)) => simplify(x)
// x를 x로 나누면 1
case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)
// 0에 x를 더하면 원래 값
case BinaryOp("+", x, Number(0)) => simplify(x)
// x에 0을 더하면 원래 값
case BinaryOp("+", Number(0), x) => simplify(x)
// 다른 경우는 (아직) 단순화 못함
case _ => e
}
}
def evaluate(e : Expr) : Double =
{
simplify(e) match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}
}
}
|
지난 글을 읽은 사람이라면 Listing 1처럼 단순히 트리 최상단에서만 최적화를 하는 대신 트리 더 깊숙이 최적화를 수행하도록 향상시켜 보라는 숙제가 있었음을 기억할 것이다. 독자인 Lex Spoon이 필자가 아는 한 가장 간단한 최적화 방법을 발견했다. 즉, Listing 2처럼 트리의 에지(각 수식 내 피연산자들)를 먼저 단순화하고, 단순화된 결과를 가지고, 최상위 수식을 최적화한다(역주: 트리 구조는 노드(node, 정점)와 그 사이를 잇는 선인 에지(edge, 간선)로 이뤄진다).
Listing 2. 단순하게, 단순하게, … 단순화됐음
/*
* Lex가 작성한 버전:
*/
def simplify(e: Expr): Expr = {
// 먼저 부분식(subexpression)을 단순화한다.
val simpSubs = e match {
// 좌, 우측 각각에 대해 단순화를 요청한다.
case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))
// 피연산자를 단순화하도록 요청한다.
case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
// 다른 경우는 복잡할 것이 없다(단순화할 피연산자가 없음).
case _ => e
}
// 이제 구성 요소는 다 단순화됐다고 가정하고 최상위에서 단순화한다.
def simplifyTop(x: Expr) = x match {
// 부정 두 번은 원래 값
case UnaryOp("-", UnaryOp("-", x)) => x
// + 하나는 원래 값
case UnaryOp("+", x) => x
// x에 1을 곱하면 원래 값
case BinaryOp("*", x, Number(1)) => x
// 1에 x를 곱하면 원래 값
case BinaryOp("*", Number(1), x) => x
// x에 0을 곱하면 0
case BinaryOp("*", x, Number(0)) => Number(0)
// 0에 x를 곱하면 0
case BinaryOp("*", Number(0), x) => Number(0)
// x를 1로 나누면 원래 값
case BinaryOp("/", x, Number(1)) => x
// x를 x로 나누면 1
case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)
// 0에 x를 더하면 원래 값
case BinaryOp("+", x, Number(0)) => x
// x에 0을 더하면 원래 값
case BinaryOp("+", Number(0), x) => x
// 다른 경우는 (아직) 단순화 못함
case e => e
}
simplifyTop(simpSubs)
}
|
Lex 고마워요.
이제 DSL의 남은 반쪽 구현을 시작해 보자. 어떤 종류의 텍스트 입력을 받아서 AST로 바꾸는 코드가 필요하다. 이런 과정을 더 전문적으로 파싱(구문 분석)이라고 한다. (더 정확하게는 토큰화(tokenizing), 어휘 분석(lexing), 구문 분석(parsing)으로 나뉜다.)
전통적으로 파서를 만드는 데는 두 가지 접근법이 있다.
- 수작업으로 파서를 작성
- 도구로 파서를 생성
수작업으로 입력 스트림에서 직접 한 글자씩 끄집어 내서 살펴본 뒤 해당 문자뿐 아니라 그 전에 읽었던 문자들에 (그리고 때론 해당 문자 뒤에 오는 문자들에) 기반을 두고 어떤 동작을 수행하는 식으로 파서를 만들 수 있다. 언어가 작다면 수작업으로 파서를 작성하는 것이 더 빠르고 쉬울 수 있겠지만 언어가 커지면 파서를 작성하기가 어려워지는 것이 보통이다.
수작업으로 만든 파서에 대한 대안은 도구가 파서를 생성하도록 하는 것이다. 전통적으로 이 분야에는 애칭으로 lex("lexer"를 생성하니까)와 yacc("Yet Another Compiler Compiler")라고는 도구가 주로 사용되어 왔다. 파서를 작성하려는 프로그래머는 수작업으로 파서를 작성하는 대신, 파서의 전단부(front end)를 생성할 "lex"에 넘겨줄 다른 소스 파일을 작성한다. 이 생성된 코드는 언어의 기본 문법 규칙을 정의하는 "문법(grammar)" 파일과 결합되고, 파서를 생성하기 위해 yacc에 넘겨진다(문법 파일에서는 토큰이 키워드이고, 코드 블록 등을 명시할 수 있다).
여기까지는 기본적인 컴퓨터공학 입문 교과서다. 그래서 여기서 유한 상태 기계(finite state machine)나 LALR/LR 파서에 대해 상세히 살펴보기보다는, 상세 내용에 관심이 있는 사람들이라면 이 주제에 대한 책이나 글(혹은 둘 다!)을 찾아볼 거라고 가정하고 넘어가겠다.
그 사이에 스칼라로 파서를 만드는 세 번째 방법인 "파서 콤비네이터"를 살펴 보자. 파서 콤비네이터는 전적으로 함수 언어적인 측면에서 설계된 것이다. 파서 콤비네이터는 특정 언어의 다양한 구성 요소를 코드 생성이 필요 없으면서도 덤으로 언어 명세처럼 보이는, 파싱을 위한 해법을 제공할 수 있는 덩어리들로 "결합(combine)"할 수 있게 해 준다.
파서 콤비네이터에 숨어 있는 핵심을 이해하려면 어떤 언어가 어떤 모양인지를 명시하는 방법인 배커스-나우어 형식(Backus-Naur Form, 약자로 BNF)에 대한 개괄적인 지식이 도움이 된다. 예를 들어 우리 계산기 언어는 BNF 문법으로 표현하면 Listing 3과 같다.
Listing 3. 언어를 기술하기
input ::= ws expr ws eoi;
expr ::= ws powterm [{ws '^' ws powterm}];
powterm ::= ws factor [{ws ('*'|'/') ws factor}];
factor ::= ws term [{ws ('+'|'-') ws term}];
term ::= '(' ws expr ws ')' | '-' ws expr | number;
number ::= {dgt} ['.' {dgt}] [('e'|'E') ['-'] {dgt}];
dgt ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';
ws ::= [{' '|'\t'|'\n'|'\r'}];
|
여기서 각 문장의 왼쪽에 있는 요소 각각은 가능한 입력 집합의 이름이고 오른쪽에 있는 요소는 항(term)이라고도 하는데 선택이나 필수로 조합된 일련의 식이나 글자들이다. (앞선 경우와 같이 BNF 문법에 대한 완전한 세부 내용은 참고자료의 Aho/Sethi/Ullman 책 등의 문헌에 더 잘 설명되어 있다.)
언어를 BNF 형식으로 표현해서 좋은 점은 BNF에서 스칼라의 파서 콤비네이터를 쉽게 만들 수 있다는 점이다. Listing 3의 BNF를 단순화하면 Listing 4와 같다.
Listing 4. (다시) 단순화하고 단순화하자.
expr ::= term {'+' term | '-' term}
term ::= factor {'*' factor | '/' factor}
factor ::= floatingPointNumber | '(' expr ')'
|
여기서 {}는 그 내부 내용이 0 혹은 여러 번 반복할 수 있음을 나타내고, 수직 막대(혹은 "파이프" |)는 either/or 관계를 나타낸다. 따라서 Listing 4를 보면 factor는 floatingPointNumber(정의하는 부분은 이유가 있어서 나타내지 않았다)이거나 왼쪽 괄호, expr, 오른쪽 괄호를 순서대로 조합한 것이다.
이제 이를 스칼라 파서로 바꾸는 일은 Listing 5에서 보듯이 어처구니 없이 간단하다.
Listing 5. BNF를 parsec으로 바꾸기
package com.tedneward.calcdsl
{
object Calc
{
// ...
import scala.util.parsing.combinator._
object ArithParser extends JavaTokenParsers
{
def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
def factor : Parser[Any] = floatingPointNumber | "("~expr~")"
def parse(text : String) =
{
parseAll(expr, text)
}
}
def parse(text : String) =
{
val results = ArithParser.parse(text)
System.out.println("parsed " + text + " as " + results + " which is a type "
+ results.getClass())
}
// ...
}
}
|
근본적으로 BNF가 대신 몇몇 파서 콤비네이터의 문법적 요소로 대체되었다. 즉, 공백은 ~ 메서드(순서대로 나타난다는 것을 의미)로, 반복은 rep 메서드로 대체되었고, 선택은 똑같이 | 메서드를 사용한다. 나타내는 문자열은 그대로 표준 문자열이다.
이 접근법의 장점 중 일부는 두 부분으로 나눠 볼 수 있다. 먼저 파서가 스칼라에서 제공하는 JavaTokenParsers라는 베이스 클래스(이 클래스는 다시 다른 클래스에서 상속 받는다. 그런 슈퍼클래스는 자바 문법과 밀접하게 관련 없는 언어를 원할 때 사용할 수 있다)를 확장한다는 점이고, 두 번째는 부동 소수점 수를 파싱하는 세부 사항을 처리하기 위해 floatingPointNumber라는 미리 알려진 콤비네이터를 사용한다는 점이다.
이 특정 문법(중위(infix) 연산자 계산기)은 어떤 방법을 쓰든지 파서를 만들기가 어렵지 않지만(이런 이유로 이 예제가 그 많은 데모나 글에서 사용되는 것이다), BNF 문법과 파서를 구성하는 코드 사이의 관계가 밀접하면 파서를 더 쉽게 빠르게 만들 수 있기 때문에 파서를 수작업으로 구현하는 것도 어렵지 않다.
이 모든 것이 어떻게 동작하는지를 이해하려면 잠시 파서 콤비네이터의 구현에 대해 알아 봐야 한다. 본질적으로 각 "파서"는 어떤 입력을 받아서 결과로 "파서"를 토해내는 함수나 케이스 클래스다. 예를 들어 파서 콤비네이터는 가장 밑바닥에서는 어떤 입력을 읽는 요소(Reader 객체)를 입력으로 받아서 더 고수준 의미를 제공할 수 있는 뭔가(Parser 객체)를 결과로 만들어내는 간단한 파서들 위에 구축되어 있다.
Listing 6. 기본적인 파서
type Elem type Input = Reader[Elem] type Parser[T] = Input => ParseResult[T] sealed abstract class ParseResult[+T] case class Success[T](result: T, in: Input) extends ParseResult[T] case class Failure(msg: String, in: Input) extends ParseResult[Nothing] |
다시 말해 Elem은 음… 파싱할 수 있는 모든 것을 나타내는 추상 타입으로, 통상 텍스트 문자열이나 스트림이다. 다음으로 Input 객체는 Elem 타입을 감싼 scala.util.parsing.input.Reader다. ([]는 Reader가 제네릭 타입이라는 것을 나타낸다. 만약 자바나 C++ 스타일 문법을 선호하는 편이면 []를 <>로 생각하면 이해가 쉬울 것이다.) 마지막으로 T 타입의 Parser는 Input을 하나 받아서 (본질적으로) Success이거나 Failure 객체 중 하나인 ParseResult 객체를 하나 만들어 내는 타입이다.
파서 콤비네이터 라이브러리에 여기서 보인 것 외 뭔가 더 있다는 건 분명하다. ~와 rep 함수까지 가는 데만 해도 만만치 않다. 하지만 지금까지 설명한 내용으로 파서 콤비네이터가 어떻게 동작하는지 기본적인 개념을 얻을 수 있었을 것이다. 파서들은 "결합"하면서 파싱 개념에 대한 더욱 높은 수준의 추상화를 제공한다. 그래서 "파서 콤비네이터"라는 이름이 붙었다. 요소들이 결합되어 파싱 기능을 제공한다.
아직 설명할 것이 남았다. 이렇게 만들어진 파서를 간단히 테스트해 보면 파서에서 돌려주는 객체가 나머지 계산기 시스템에서 필요한 것과 맞지 않는다는 것을 알 수 있다.
Listing 7. 첫 시험은 실패???
package com.tedneward.calcdsl.test
{
class CalcTest
{
import org.junit._, Assert._
// ...
@Test def parseNumber =
{
assertEquals(Number(5), Calc.parse("5"))
assertEquals(Number(5), Calc.parse("5.0"))
}
}
}
|
실행하면 파서의 parseAll 메서드가 우리가 정의한 케이스 클래스인 Number(이는 어느 정도는 납득할 만한데 파서에서 우리 케이스 클래스와 파서의 생성 규칙(production rule) 사이의 관계를 명시하지 않았기 때문이다)를 돌려주지 않아 테스트가 실패한다. 그렇다고 parseAll은 텍스트 토큰이나 int 집합을 돌려주지도 않는다.
대신 파서는 Parsers.Success 인스턴스(이 안에 우리가 찾는 결과가 있다)나 Parsers.NoSuccess, Parsers.Failure, Parsers.Error 인스턴스 중 하나인(이는 모두 같은 의미다. 즉, 어떤 이유로 파싱이 되지 않았다는 뜻이다) Parsers.ParseResult를 돌려준다.
파싱이 성공했다고 가정하고 실제 결과를 얻기 위해서는 ParseResult의 get 메서드를 사용해야 한다. 이는 테스트가 성공하기 위해서는 Calc.parse 메서드를 살짝 고쳐서 Listing 8에 보인 것처럼 해야 한다는 뜻이다.
Listing 8. BNF에서 parsec로
package com.tedneward.calcdsl
{
object Calc
{
// ...
import scala.util.parsing.combinator._
object ArithParser extends JavaTokenParsers
{
def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
def factor : Parser[Any] = floatingPointNumber | "("~expr~")"
def parse(text : String) =
{
parseAll(expr, text)
}
}
def parse(text : String) =
{
val results = ArithParser.parse(text)
System.out.println("parsed " + text + " as " + results + " which is a type "
+ results.getClass())
results.get
}
// ...
}
}
|
이제 테스트가 성공하지 않았나?
미안하지만 실패다. 테스트를 돌려보면 파서가 내놓은 결과는 아직 이전에 만든 AST 타입(Expr과 딸린 서브클래스들)이 아니고, 대신 리스트와 문자열 같은 것으로 구성된 형태다. 여기서 방향을 전환해서 이 결과를 파싱해 Expr 인스턴스들을 만들어 그걸 해석할 수도 있다고 생각하기는 하지만, 분명 다른 방법이 있을 것이다.
실제로 그런 방법이 있기는 한데, 이 방법이 어떻게 동작하는지를 이해하려면 파서 콤비네이터가 어떻게 비"표준" 요소(즉, 문자열과 리스트 말고 다른 것)를 만들어내는지를 개략적으로 알아야 한다. 적합한 용어를 써서 다시 표현하자면 파서가 어떻게 맞춤 요소(custom element)… 여기서는 AST 객체들을 만들어낼 수 있는지를 알아야 한다. 여기에 대한 내용은 다음 번 주제다.
다음 글에서는 파서 콤비네이터 구현의 기본을 살펴보고 텍스트를 계산하는데 쓰는(나중에는 컴파일하는 데 쓰는) AST로 어떻게 파싱할 수 있는지를 살펴보겠다.
자, 분명히 아직 완전히 마친 건 아니다(아직 파싱에 대해서도 마무리해야 한다). 하지만 기본적인 파서 동작이 완료되었고 이제 파서가 생성한 요소가 AST 요소를 생성하도록 확장하기만 하면 된다.
먼저 앞서 나가고 싶은 사람은 스칼라 문서나 Programming in Scala의 파서 콤비네이터에 대한 장에서 설명하고 있는 ^^ 메서드를 살펴 보기 바란다. 주의해야 할 것은 이 계산기 언어가 참고자료에 나오는 예제에 비해 약간 미묘하다는 것이다.
물론 문자열과 리스트 같은 것만 다루고 AST 부분을 무시할 수도 있다. 파서가 돌려주는 문자열과 리스트를 분리해 내 다시 파싱해서 AST 요소를 만들어내는 식으로 말이다. 하지만 파서 콤비네이터 라이브러리가 해법을 준비해 놓은 마당에 왜 그래야 하는가?
교육
- "바쁜 자바 프로그래머를 위한 스칼라 입문: 객체 지향론자를 위한 함수 프로그래밍"(Ted Neward, 한국 developerWorks, 2008년 4월): 이 연재의 첫 편으로 스칼라 전반에 대해 소개하고 여러 요소 중 스칼라의 동시성(concurrency)에 대한 함수적인 접근에 대해 설명한다. 이 연재의 다른 글은 다음과 같다.
- "클래스 동작"(2008년 4월): 스칼라의 클래스 문법과 의미에 대해 상세히 다룬다.
- "루프 때문에 당황하지 말자!"(2008년 5월): 스칼라의 제어 구문에 대해 상세히 알아본다.
- "특성과 동작"(2008년 6월): 스칼라 판 자바 인터페이스를 다룬다.
- "구현 상속"(2008년 9월): 스칼라에서의 다형성(polymorphism)에 대해 다룬다.
- "컬렉션 타입"(2008년 9월): 튜플, 배열, 리스트에 대해 다룬다.
- "패키지와 접근 제한 지시어"(2008년 10월): 스칼라의 패키지와 접근 제한 지시어(access modifier),
apply기능에 대해 다룬다. - "계산기 만들기 1부"(2008년 10월): 이 글에서 다루는 예제를 만드는 첫 편이다.
- "자바를 이용한 함수 프로그래밍"(Abhijit Belapurkar, 한국 developerWorks, 2007년 4월): 자바 개발자 관점에서 함수 프로그래밍의 이점과 용례에 대해 배운다.
- "Scala by Example"(Martin Odersky, 2007년 12월): 짧은 코드 중심의 스칼라 입문서(PDF 형식).
- Programming in Scala(Martin Odersky, Lex Spoon, Bill Venners; Artima, 2007년 12월): 최초의 책 한 권 분량의 스칼라 입문서
- developerWorks 자바 기술 존: 자바 프로그래밍의 모든 측면에 대한 수백 개의 기사가 제공된다.
제품 및 기술 얻기
토론
- developerWorks 블로그: developerWorks 커뮤니티에 참여해 보자.
태그
태그를 더 많이 보거나 적게 보기 위해 슬라이더 막대를 사용하십시오.
인기 태그는 특정 컨텐츠 존(예를 들어, 자바, 리눅스, WebSphere)의 최고 인기 태그를 보여줍니다.
내 태그는 특정 컨텐츠 존(예를 들어, 자바, 리눅스, WebSphere)의 귀하의 태그를 보여줍니다.
인기 기사 태그 |
내 기사 태그태그 목록으로 건너뛰기
인기 기사 태그 |
내 기사 태그