특집기사:Xtext로 수식 파싱하기

위클립스
이동: 둘러보기, 찾기
Article.png 특집기사 정보
원문 보기
저자 Sven Efftinge
역자 이지율

이 문서는 Xtext를 이용하여 좌항 재귀(Left-Recursion)문제를 해결하는 방법을 설명하고, 원하는 AST를 구성하도록 Xtext 문법을 정의 하는 방법을 설명한다.

목차

[편집] 개요

단순한 구조적 언어를 Xtext로 파싱하는 것은 생각을 깊게 할 필요도 없을 정도로 간단하다. 하지만 재귀된 표현식을 파싱하는 것은 종종 좀 골치아파진다. 왜냐하면 Xtext가 좌항 재귀(Left recursive) 파서 룰을 허용하지 않기 때문이다. Xtext가 사용하는 파서(ANTLR에 의해 생성된)는 탑-다운 접근법을 사용하며, 이로 인해 좌항 재귀 문법을 이용할 경우 무한 재귀에 빠질 수 있게 된다.

다음과 같은 단순한 수식을 파싱한다고 가정하자:

2 + 20 * 2

[편집] 좌항 재귀(Left-Recursion)

여러분이 EBNF를 좀 알고 좌항 재귀 상황을 피할 생각이 없다면, 아마 다음과 같은 문법을 정의할 것이다:

Expression:
  Expression '+' Expression |
  Expression '*' Expression |
  INT;

파서가 문법을 탑-다운, 그리고 왼쪽에서 오른쪽으로 분석해 나가기 때문에 이 문법정의는 좌항 재귀에 빠지게 된다. 따라서, Expression 파서 룰은 어떤 문자도 소비하지 않은 채 계속해서 Expression 파서 룰을 무한 반복하게 된다. 이런 종류의 문제를 처리할 때, 바텀-업 파서를 이용할 수 있지만 여전히 연산자의 우선순위 문제도 해결해야 한다. 예제를 기준으로 하자면 곱셉이 덧셈보다 우선해야 할 것이다.

Xtext에서 명시적인 우선순위를 지정하려면 공통 좌항을 인수분해(left-factoring)[1]해야한다. 현재 우리가 해결할 문제에서 Left-Factoring[1]이란 아래에 소개될 정확한 테크닉을 이용하여 좌항 재귀를 제거하는 것을 말한다.

아래는 좌항이 인수분해된 문법이다(아직 Xtext에서 돌아가는 문법은 아니다):

Addition :
  Multiplication ('+' Multiplication)*;
 
Multiplication:
  NumberLiteral ('*' NumberLiteral)*;
 
NumberLiteral:
  INT;

앞서의 문법과 주요한 차이점은 하나의 파서룰 대신에 세개의 파서룰을 정의한것이다. 좀 더 주의깊게 살펴보면 명시적인 위임 패턴이 참여하고 있음을 알 수 있다. Addition룰은 자기 자신을 호출 하지 않고 대신 Multiplication을 호출한다. 연산자의 우선순위는 위임의 순서에 의해 정의된다. 예제에서는 나중에 선언된 룰이 더 높은 우선 순위를 갖게 된다.

또 우리는 사용자가 괄호를 이용하여 명시적으로 우선순위를 변경하는 것을 허용해야 할 것이다. 예: (2 + 20) * 2.

이제 그것을 지원해 보자(아직 이 문법은 Xtext에서 돌아가지 않는다)

Addition :
  Multiplication ('+' Multiplication)*;
 
Multiplication:
  Primary ('*' Primary)*;
 
Primary :
  NumberLiteral |
  '(' Addition ')';
 
NumberLiteral:
  INT;

다시 한 번 정리하면: 만약 왼쪽에서 재귀가 일어나는 구도가 발생하면, 연산자의 우선순위에 따라 이를 위임하는 체인으로 변경해야 한다. 다음 우선순위를 가진 연산자를 분석하는 룰로 위임하는 패턴은 어떤 룰에서건 항상 동일하게 적용된다.

[편집] AST의 구축

이제 우리는 좌항 재귀(Left-Recursion)를 피하는 방법을 알게 됐다. 이제 파서가 뭘 만들어내야 할지를 고민해 보자. Xtext에서 파서 룰들은 어떤 값을 항상 리턴한다. 이 값은 AST 노드들이다(예: EObject 인스턴스) datatype rule이나 terminal rule은 String이나 EMF에 EDatatype으로 정의된 값들을 리턴한다.

Xtext는 특정 룰이 파서룰인지 터미널 룰인지, 데이터 타입 룰인지를 자동으로 추론할 수 있다. 위의 예제들은 데이터 타입룰들로만 구성되었고 파서는 String을 리턴할 것이다.

좀 더 쓸만한 결과, 즉 의미를 지니는 AST를 얻기 위해서는 할당문(Assignment)과 액션을 추가해야 한다. 하지만 그 전에 리턴 타입에 대해 먼저 논의할 필요가 있다.

[편집] 리턴 타입

룰의 리턴 타입은 'returns' 키워드를 이용하여 명시적으로 지정될 수 있지만, 지정하지 않으면 룰의 이름이 타입 이름으로 추론된다. 따라서:

NumberLiteral : ...;

위의 문법은 아래와 동일하다:

NumberLiteral returns NumberLiteral : ...;

하지만 우리가 정의한 문법과 같은 경우, 각 구문이 재귀적 구조이므로 모든 룰들이 동일한 타입을 리턴해야 한다. 따라서 문법을 좀더 쓸만하게 하기 위해 우리는 공통 리턴 타입을 명시적으로 추가해야 한다 (이 문법은 여전히 뭔가 빠져있다):

Addition returns Expression:
  Multiplication ('+' Multiplication)*;
 
Multiplication returns Expression:
  Primary ('*' Primary)*;
 
Primary returns Expression:
  NumberLiteral |
  '(' Addition ')';
 
NumberLiteral:
  INT;

Xtext의 AST 타입 추론 매커니즘은 두가지 유형으로 추론할 것이다: ExpressionNumberLiteral.

이제 우리는 할당문과 액션을 추가하여 우리가 필요로 하는 중요한 정보를 AST 노드에 저장해야 하고, 두 연산자에 적합한 서브 타입을 만들어야 한다.

자 드디어 정상 작동하는 Xtext 문법이다:

  1. Addition returns Expression:
  2.   Multiplication ({Addition.left=current} '+' right=Multiplication)*;
  3.  
  4. Multiplication returns Expression:
  5.   Primary ({Multiplication.left=current} '*' right=Primary)*;
  6.  
  7. Primary returns Expression:
  8.   NumberLiteral |
  9.   '(' Addition ')';
  10.  
  11. NumberLiteral:
  12.   value=INT;

[편집] 파싱 과정

자 이제 파서가 이 문법을 어떻게 따라가는지 추적해 보자.

(1 + 20) * 2
나는 이 텍스트를 읽는 것 만으로, 이해하는 것이 꽤 어렵다고 확신한다. 그래서 뭐가 어떻게 돌아가는지를 시각적으로 보여주는 비디오 하나를 준비했고 다음 절에서 볼 수 있다.

1파서는 항상 첫번 째 룰인 Addition에서 시작한다. 2그중 첫번째 요소는 Multiplication룰을 호출하는 것이고 이는 다시 5Primary룰을 호출한다. Primary룰은 이제 문제를 해결할 두가지 방법을 가지고 있다. 8첫번째 방법은 INT값을 value라는 변수에 담는 NumberLiteral룰을 호출 하는 것이다.

하지만 첫번째 토큰이 '('이기 때문에 9파서는 두번째 방법(Alternative)인 '(' Addition ')'를 선택할 것이다. '('는 할당되지 않았으므로 소모(consume)된다. 그리고 Addition 룰이 호출 된다. 이제 '1' 토큰이 Addtion룰로 전달 될 것이고 2이 룰은 다시 Multiplication룰을 호출하고 이는 다시 5Primary룰을 호출하게 된다. 이 시점에서 파서는 8 첫번째 대안(Alternative)인 NumberLiteral를 선택한다. 그리고 value 변수에 INT값을 할당할 것이다.

파서가 할당문을 만나면, 파서는 현재 룰에 대한 AST 노드가 이미 만들어져있는지 확인한다. 만약 없다면 리턴 타입에 근거하여(여기서는 NumberLiteral) 새로 만든다. Xtext 소스 생성기는 NumberLiteral라는 EClass를 만들어 준다. 파서는 이를 이용하여 AST 노드 인스턴스를 만들고 value 값을 할당한다.

이를 자바로 나타내면 다음과 같다:

// value=INT
if (current == null)
 current = new NumberLiteral();
current.setValue(ruleINT());
...

이제 NumberLiteral 룰이 종료되어 8이를 호출한 Primary룰 에게 EObject가 리턴되었다. 이 값은 변경되지 않고 차례로 Primary룰의 호출자에게 다시 리턴된다. 5Mulitiplcation룰 내부에서 Primary룰이 호출되었고, 이는 성공적으로 파싱되어 NumberLiteral 인스턴스가 리턴되었다.

5Mulitiplcation룰 의 다음 파트인 ({Addition.left=current} '+' right=Multiplication)*는 그룹이라고 불린다(괄호로 싸인 부분). 괄호 뒤의 '*' 아스테리크 마크는 이 부분이 0회 또는 여러번 소비(Consume)될 수 있음을 뜻한다. 이 파트의 첫번째로 소비될 토큰은 '*'이다, 따라서 이 그룹은 소비될 수 없고, 룰은 할당되지 않은 값인 NumberLiteral을 리턴한다.

2Addition 룰에서 비슷한 그룹이 등장하지만 이번엔 소비할 다음 토큰이 '+'로 일치한다. 이 그룹의 첫 부분인 {Addition.left=current}는 액션이라고 부르며 '{', '}'로 싸여 있다. Xtext는 매우 선언적이며 양방향적이다. 따라서 다른 파서 생성기들 처럼 액션안에 임의 표현이 등장하는 것은 좋은 생각이 아니다. 대신 Xtext는 딱 두가지의 액션만을 지원한다. 예제의 경우 Addition 클래스의 인스턴스를 하나 만들어, 리턴된 값을 인스턴스의 left 피쳐에 할당한다. 자바로 나타내면 다음과 같다:

// Multiplication rule call
current = ruleMultiplication();
// {Addition.left=current}
Addition temp = new Addition();
temp.setLeft(current);
current = temp;
...

2결과적으로 룰은 left 속성 값이 NumberLiteral로 지정된 Addition인스턴스를 리턴한다. 이제 파서는 '+' 연산자를 소비한다. 타입이 명시적으로 역할을 설명하므로, 이 토큰은 저장하지 않고 버린다. 할당문('right=Multiplication'Multiplication 룰을 호출하고 결과 값(value = 20인 NumberLiteral)을 right 속성으로 지정한다.

만약 소모할 '+'가 더 있다면 그룹은 몇차례 더 반복되며 현재의 리턴값을 left로 갖는 Addition 인스턴스를 만들 것이다. 그러나 다음 토큰은 ')' 이므로 룰은 종료되어 Addition 인스턴스를 9호출자(Primary 룰의 두번째 대안)로 리턴한다. 이제 ')'는 일치하고 소모되어 스택이 한 단계 감소한다.

5이제 우리는 Multiplication룰로 돌아왔으며 '*' 토큰을 처리할 차례다. 파서는 그룹과 액션을 적용할 것이다. 마지막으로 Primary 룰을 호출하고, 또 다른 NumberLiteral 인스턴스(value = 2)를 만들어 Multiplication 룰의 right 속성으로 지정할 것이다. 그리고 Addtion에게 Multiplication을 리턴하게 된다. 이는 호출자를 따라 차례로 리턴되고, 이제 더 파싱할 것이 남지 않게 된다.

결과 AST는 다음과 같다:

Xtext-expression-ast-example.png

다음 비디오는 방금 여러분이 읽은 내용을 설명한다. 문법이 약간 다르지만, 별로 문제가 되지 않는다고 확신한다. ;-).

[편집] 연합성(Associativity)

아직 언급해야할 주제가 남아있는데, 바로 연합성에 관한 이야기이다. 연합성에는 좌측 연합성(Left associativity), 우측 연합성(Right associativity) 그리고 무연합성(No associativity)이 있다. 예제에서 우리는 좌측 연합성을 보았다. 연합성은 파서가 동일한 우선순위를 가진 접속 연산자를 만났을 때 어떻게 AST를 만드는지 정의한다. 다음 예제는 위키피디아에서 가져왔다:

a ~ b ~ c 라는 표현식을 가정하자. 만약 연산자 ~가 좌측 연합성을 가졌다면 (a ~ b) ~ c 형태로 인터프리트 되며 좌측 부터 오른쪽으로 평가된다. 만약 연산자가 우측 연합성을 가졌다면 표현식은 a ~ (b ~ c) 형태로 인터프리트 되고 우측부터 평가된다. 연산자가 비 연합성인경우, 이 표현식은 문법 에러를 일으키거나 다른 특별한 의미로 해석되어야 한다.

우리는 이미 좌측 연합성의 주요 형태를 알고 있다:

Addition returns Expression:
  Multiplication ({Addition.left=current} '+' right=Multiplication)*;

우측 연합성(Right associativity)는 다음 패턴을 통해 구현한다(수량 연산자로 '?'가 사용된 것과 룰 자기 자신을 마지막에 다시 호출하는 것을 주목하라):

Addition returns Expression:
  Multiplication ({Addition.left=current} '+' right=Addition)?;

만약 같은 줄에서 여러번 동일한 표현식을 사용하는 것을 허용하지 않고 싶다면(무연관성) 이렇게 한다:

Addition returns Expression:
  Multiplication ({Addition.left=current} '+' right=Multiplication)?;

가끔은 파서 레벨에서는 연합성을 제공하지만, 나중에 벨리데이션 단계에 이를 금지하는 것이 좋을 때가 있다. 왜냐면 더 좋은 에러메시지를 보여줄 수 있기 때문이다. 또한 전체 파싱이 도중에 중단되는 것을 방지할 수도 있으므로, 여러분의 도구는 더 관대해질 수 있다.

[편집] 참조

  1. 1.0 1.1 Left-Factoring: 같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재할 경우, 공통된 prefix를 인수분해하는 것을 left-factoring이라고 한다.[1]

이 기사에 대한 의견은 토론 페이지를 통해 나눌 수 있습니다.

개인 도구
이름공간
변수
행위
포탈
탐색
도움
도구모음