Parsing domain-specific languages with JavaCC

Posted 2009.03.04 21:15 by shinji

 

원문: http://www.guydavis.ca/log/view.jsp?id=1085

 

JavaCC 로 도메인 특정적인 언어 파싱하기

 

개요

 

나는 최근에 자바로 도메인 특정적인(domain-specific) 언어를 해석하고 값을 구할 필요가 있었다. 나는 내가 파서를 직접만드는 것은 나에게 시간 낭비라는 것을 알만큼 충분히 코딩을 경험해왔다. 간단히 구글에 검색한 결과 JavaCC라는 괜잖은 것을 발견했다. JavaCC 는 밑바닥에서 코딩하게 될 때 부닥칠 많은 에러들이 없게 문자열을 파싱하는 클래스를 생성하는 모든 힘든 일을 처리하는 자바 코드 생성기이다. 여러분이 할 모든 것은 그저 여러분이 파싱하려고하는 허용된 구문을 설명하는 문법 파일만 제공하면 된다. 이 튜토리얼은 JavaCC로 간단한 참/거짓 언어(boolean language)를 어떻게 파싱하는지 설명한다.

 

참/거짓 언어 (Boolean Language)

 

JavaCC의 사용을 설명하기 위해서 참/거짓의 구문만으로 구성된 간단한 언어의 구문을 정의해보자. 그 언어는 임의의 괄호로 중첩된 구문을 허용한다. 여기에 유효한 표현의 예들이 있다 (라인당 하나씩).

TRUE
FALSE
TRUE AND FALSE
FALSE OR TRUE
FALSE XOR FALSE
TRUE AND (FALSE OR TRUE)
TRUE AND (FALSE OR (TRUE XOR TRUE))

충분히 간단한 언어지 않은가? 한가지 까다로운 부분은 구문들을 평가할때 우선순위의 자격을 가질 순서를 결정하는 괄호를 사용하는 부분이다.

문법 정의하기

이제 우리의 새로운 참/거짓 언어에서 유효한 구문을 해석할 JavaCC 문법을 정의해보자. 먼저, grammer.jj 은 생성자와 몇몇 메쏘드들을 가지는 BooleanLogicParser 클래스를 선언한다. 이 자바 코드는 JavaCC가 코드를 생성하는 동안에 바로 넘겨질 것이다.

public class BooleanLogicParser {

private Expression rootExpr;

public BooleanLogicParser(String s) {
this((Reader)(new StringReader(s)));
}

public boolean evaluate() {
return this.rootExpr.eval();
}
}

다음은 문법에서 허용되는 키워드를 나타내는 토큰들을 정의한다. 참/거짓 언어에서는 우리는 TRUE, FALSE, AND, OR, 와 XOR 를 보게된다.

<DEFAULT> TOKEN:
{
<AND: "AND">
| <OR: "OR">
| <XOR: "XOR">
| <LPAREN: "(" >
| <RPAREN: ")" >
| <TRUE: "TRUE">
| <FALSE: "FALSE">
}

다음으로 우리는 파서가 수락할 허용된 포맷들을 선언한다. 자바 메쏘드와 비슷하게 JavaCC는 자바 코드 조각(중괄호로 감싸진)과 토큰들과 일치를 위한 정규 표현들로 구성되는 "프로덕션"을 선언한다.

먼저 우리는 최상위 계층의 parser() 프로덕션을 선언한다. 전체 명령문 문자열은 이 parse 프로덕션과 일치해야 한다. 우리의 경우에는 그것은 유효한 '파일끝' 이 따라오는 참/거짓 표현식이어야 한다.

void parse() : {} 
{
this.rootExpr = parseExpr(null) <EOF>
}

parseExr 프로덕션은 참/거짓 표현에 대한 재귀적인 일치됨이다. 괄호들의 처번째 집합에서 초기의 셋업 자바코드들 뒤에 매칭이 시작된다. (X|Y|Z) 는 정규 표현식에서 사용되는 것과 같은 형태의 선택자이다. 그래서 첫째로, 우리는 TRUE, FALSE 또는 괄호로 둘러싸이는 하위 표현을 둘 수 있다. 그 다음 선택적인 AND, OR, XOR 중 한가지의 참/거짓 연산자들 중 하나를 가진다. 마지막으로 오른쪽편에 다시 TRUE, FALSE 또는 괄호로 둘러싸이는 하위 표현을 둘 수 있다.

Expression parseExpr(Expression parent) : 
{
Expression expr = new Expression();
if (parent != null) {
parent.add(expr);
}
}
{
(
<TRUE> { expr.add(true); }
| <FALSE> { expr.add(false); }
| <LPAREN> parseExpr(expr) <RPAREN>
)
(
(
<AND> { expr.add(BooleanOperator.AND); }
| <OR> { expr.add(BooleanOperator.OR); }
| <XOR> { expr.add(BooleanOperator.XOR); }
)
(
<TRUE> { expr.add(true); }
| <FALSE> { expr.add(false); }
| <LPAREN> parseExpr(expr) <RPAREN>
)
)*
{ return expr; }
}

중괄호를 사용함으로써, 일치되는 특별한 토큰 오른쪽 다음에 오는 간단한 자바코드로 잠깐 들어갈 수 있다는 것이다. 이것은 우리가 나중에 평가하게 될 파스의 트리를 구성하도록 한다.

표현식 객체 구성하기

파서가 토큰들이 나오는 순서대로 TRUE, FALSE, 참/거짓 연산자 도는 하위 표현들을 추가하여 Expression 객체를 구성하게 된다.

public class Expression {
List pieces;

public Expression() {
this.pieces = new ArrayList();
}

public void add(Expression expr) {
this.pieces.add(expr);
}

public void add(BooleanOperator opr) {
this.pieces.add(opr);
}

public void add(Boolean bool) {
this.pieces.add(bool);
}
}

또한 연산자들을 상수로써 가지는 BooleanOperator 열거형을 정의한다.

public enum BooleanOperator {
AND, OR, XOR
}

파싱이 실행된 후에, 그 Expression 객체는 그 자신들의 조각(pieces)들의 리스트로 표현 컴포넌트들을 포함하게 될 것이다. 각각의 조각들은 아래 중 하나이다.

  1. TRUE 또는 FALSE 로 해석되어진 참/거짓
  2. AND, OR, XOR 로 해석되어진 BooleanOperator
  3. 괄호 안에서 발견된 하위표현으로 해석되어진 Expression 객체

표현식 평가하기

Expression 객체가 한 번 구성되면, 그것이 참인지 거짓인지 이제 계산되어 질 수 있다. 여기에 그것을 하는 자바코드가 있다.

  public boolean eval() {
boolean result = eval(this.pieces.get(0));
for (int i = 1; i < this.pieces.size(); i+=2) {
BooleanOperator opr = (BooleanOperator) this.pieces.get(i);
boolean evalResult = eval(this.pieces.get(i+1));
if (opr == BooleanOperator.AND) {
result &= evalResult;
}
else if (opr == BooleanOperator.OR) {
result |= evalResult;
}
else if (opr == BooleanOperator.XOR) {
result ^= evalResult;
}
}
return result;
}

private boolean eval(Object piece) {
if (piece instanceof Expression) {
return ((Expression) piece).eval();
} else if (piece instanceof Boolean) {
return ((Boolean) piece).booleanValue();
}
throw new RuntimeException("Invalid expression piece found: " + piece);
}

연습으로써, 이미 결과를 알게될 때에는 불필요한 계산을 피하기 위한 생략을 하기 위해서 eval 을 수정한다. (As an exercise, modify the eval to short-circuit to avoid unnecessary computation when the result is already known.) 예를 들면 true or X; 가 있다면 X 를 계산하는 것은 중요하지 않다.

Ant 로 빌드하기

이 튜토리얼의 예제를 실행하기 위해서는 JavaCC 코드 생성기를 구동하고 여러분 자신의 코드를 생성된 코드와 같이 컴파일하기 위해 Ant 가 필요할 것이다. 여기에 작동하는 Ant build.xml 파일이 있다.

  <target name="codegen"
depends="init"
description="Runs JavaCC code generation.">
<delete>
<fileset dir="src/ca/guydavis/javacc/codegen">
<include name="*.java" />
</fileset>
</delete>
<javacc target="src/ca/guydavis/javacc/codegen/grammar.jj"
javacchome="javacc-4.2"
debugparser="true" />
<replace token="public class"
value='@SuppressWarnings("all") public class'
dir="src/ca/guydavis/javacc/codegen/"
includes="*.java" />
</target>

경고 옵션을 켜놓은 이클립스를 사용하는 사람들을 위한 유용한 트릭은 Ant 의 replace 태스크를 사용하여 모든 생성될 자바 클래스들에 @SuppressWarnings("all") 을 추가하는 것이다. JavaCC의 코드가 여러분의 프로젝트의 표준을 따르지 않을 수 있기 때문에, 이것은 여러분들의 코드 기반에서 이클립스가 문제점을 보여줄때 그것을 무시하게 만든다.

JUnit으로 테스트 하기

JavaCC의 개발자들이 파서를 만드는 것에서 우리가 하는 것 보다 훨씬 낫다고 할지라도 그것은 우리가 그들이 생성한 코드를 테스트 할 수 없다는 것을 의미하지는 않는다. 여기에 성공적으로 파싱되고 잘못된 구문에서는 에러를 내는 우리의 테스트 경우를 확실하게 해주는 JUnit 예제 클래스들이 있다.

  private boolean parseValid(String stmt) {
BooleanLogicParser parser = new BooleanLogicParser(stmt);
try {
parser.parse();

} catch (Throwable t) {
fail("Unable to parse because: " + t.getLocalizedMessage());
}
return parser.evaluate();
}

@Test
public void parseTrue() {
assertTrue(parseValid("TRUE"));
}

@Test
public void parseFalseAndTrue() {
assertFalse(parseValid("FALSE AND TRUE"));
}

@Test
public void parseMultipleNesting() {
assertFalse(parseValid("TRUE AND (FALSE OR (TRUE XOR TRUE))"));
}

@Test(expected = TokenMgrError.class)
public void parseWrongKeywords() throws ParseException {
BooleanLogicParser parser = new BooleanLogicParser("TRUISH AND MAYBE");
parser.parse();
fail("Parsing succeeded for a malformed statement.");
}

요약

이 간단한 예제가 도메인 특정적인 언어들에 대한 파서를 빠르게 구성하기 위해 JavaCC를 사용이 강력함을 보여줬기를 바란다. 루비가 아마도 도메인 특정적인 언어(DSL)에 대해 더 나은 또 하나의 선택일지도 모르지만 만약 여러분이 자바에 빠져 있다면 JavaCC 는 필수적인 라이브러리이다.

Resources

  • Full Eclipse project with Ant build for all the code described above in a zip file.
  • JavaCC project at Java.net
  • IBM Developerworks tutorial on JavaCC

This article was written in springnote.

« PREV : 1 : ··· : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : ··· : 158 : NEXT »