Parser from scratch (2) - Recursive Descent Parser

이전 포스트에서 E -> T { (+|-) T }, T -> num | (E) 라는 문법의 파서를 만들어보았습니다.

여기서는 문법을 좀더 확장하고 수식 계산 과정을 보여줄 수 있는 파서를 만들어보도록 하겠습니다. (완성된 코드와 실행결과는 하단에 링크되어 있습니다.)

	/*
	 * E -> T { (+|-) T }
	 * T -> F { (*|/) F }
	 * F -> num
	 *    | ( E )
	 */

이전 포스트에서 +와 - 연산만 지원하는 문법에서 *와 /를 지원하는 문법으로 확장한 것입니다. 우선순위를 고려하기 위해 새로운 넌터미널을 도입하여 괄호()로 둘러싼 부분이 가장 우선순위가 높고 *|/가 그 다음 순위고 +|-가 가장 우선순위가 낮아서 마지막으로 처리되도록 문법을 만든 것입니다.

이렇게 되면 T() 메소드가 추가되어서 T 부분을 처리할 수 있어야 합니다. 이를 위해서는 E에서 T()를 호출하던 것과 똑같이 F()를 호출한 후 연산자 * 또는 /를 읽고 다시 F()를 호출하게 된다. 또한 다음 토큰이 또 * 또는 /일 동안 이것을 반복하여 *나 / 연산이 연속되는 경우를 처리하게 된다.

	int T()  {
		int rval;
		int value = 0;
		value = F();
		while (true) {
			if (!token.is(Token.MUL) && !token.is(Token.DIV))
				break;
			Token prevOp = token;
			token = nextToken();
			rval = F();
			if (prevOp.is(Token.MUL)) {
				System.out.printf("%d * %d = %d\n", value, rval, value*rval);
				value *= rval;
			} else if (prevOp.is(Token.DIV)) {
				System.out.printf("%d / %d = %d\n", value, rval, value/rval);
				value /= rval;
			}
		}
		if (!grammar.Follow("T", token))
			throw new RuntimeException("After T : wrong token " + token);
		return value;
	}

이 단계에서는 앞의 Token 클래스는 그대로 사용할 수 있습니다. 이전 단계에서 T() 메소드는 이제 F()가 되어야 되겠지요? 이런 식으로 새로운 연산자를 추가하는 것은 기존 구조를 바꾸지 않고 새로운 넌터미널과 그에 대응하는 메소드를 추가하면 됩니다.

다음으로 이러한 지정문을 가지는 언어의 문법으로 확장을 해 보겠습니다. 다음 문법은 세미콜론으로 연결된 여러 개의 지정문을 가지는 프로그램을 나타냅니다. 지정문은 = 왼쪽에 이름(id)가 나오고 오른쪽에는 수식이 나오는 형태입니다.

S -> St { ; St }
St -> id = E
E -> T { (+|-) T }
T -> F { (*|/) F }
F -> num | id | ( E )

이 문법은 이제 좀더 프로그래밍 언어의 모양을 갖추었고 넌터미널(N) 심볼과 터미널(T) 심볼도 꽤 많아졌습니다.

N = {S, E, T, F}
T = {id, =, num, +, -, *, /, (, ), ;, $}

Token 클래스가 터미널 심볼들을 모두 인식할 수 있게 확장되어야 되겠지요? 그리고 Token 클래스에 몇 개의 헬퍼 메소드를 추가했습니다. 토큰이 가진 심볼이 무엇인지 확인할 수 있는 is(Token번호) 메소드와 숫자인 경우 int 값으로 변환해 주는 getInt() 메소드를 추가했습니다.

또한 체계적인 문법의 처리를 위해 Grammar 클래스를 추가해서 문법을 출력하고 오류검사하는 기능도 구현해 보겠습니다. 문법은 허용되는 모든 문자열을 나타내므로 허용되지 않는 문자열의 경우 나타날 수 없는 심볼이 처음 나온 위치를 알 수 있습니다. 이것이 컴파일러가 보여주는 문법 오류에 해당합니다. 보통 잘못된 첫번째 심볼과 코드상의 위치를 보여주고 그 자리에 나와야 할 또는 나올 수 있는 심볼들을 보여줍니다. 이것을 가능하게 하는 것이 문법에서 넌터미널 심볼의 Follow라는 개념입니다. 즉 각 넌터미널 심볼에 대해서 뒤에 나올 수 있는 심볼이 무엇인지를 미리 계산해 두는 것입니다. 이것은 문법을 분석하여 얻을 수 있습니다.

boolean followTable[][] = {
	// id   =      n      +      -      *      /      (      )      ;      $
	{false, false, false, false, false, false, false, false, false, false, true},// S
	{false, false, false, false, false, false, false, false, false, true, true}, // St
	{false, false, false, false, false, false, false, false, true, true, true},  // E
	{false, false, false, true, true, false, false, false, true, true, true},    // T
	{false, false, false, true, true, true, true, false, true, true, true}       // F
};

위의 표는 각 넌터미널 심볼의 Follow를 모아둔 표입니다. 각 넌터미널에 대해 다음에 나타날 수 있는 터미널 심볼을 True로 표시해 둔 표입니다. 이것을 이용하면 각 넌터미널의 유도가 끝난 후 다음 심볼이 문법에 맞는 것이 나왔는지 검사할 수 있습니다. 다음 메소드는 Grammar 클래스에서 이런 일을 담당하는 메소드입니다. 넌터미널 심볼의 스트링을 받아 그것의 번호에 대응하는 Follow 테이블의 행에서 다음 토큰이 나올 수 있는지 검사하는 것입니다.

	void checkFollow(String nt, Token tok) {
		if (!followTable[ntMap.get(nt)][tok.tokNum])
			throw new RuntimeException("\nFollow("+nt+") not contains "+tok);
	}

그럼 이제 입력을 받아 위의 문법에 대해 파싱을 수행할 파서를 만들 준비가 되었습니다. 다음은 파서의 실행 화면을 보여줍니다. 여러 개의 문장을 입력으로 주면 계산 결과를 보여주고 마지막으로 $(EOF)가 들어오면 심볼들에 대해 지정된 값의 이미지(메모리 상태)를 보여줍니다.

두번째와 세번째 화면은 오류 처리 예를 보여줍니다. 두 번째 화면에서는 지정문이 아니라 수식이 바로 나온 경우 id가 나와야 한다는 오류 메시지를 보여줍니다. 또한 세 번째 화면에서는 세미콜론이 나와야 하는데 b가 나왔다는 메시지를 보여줍니다. (여기서 Follow를 모두 찍어주면 나올 수 있는 심볼이 무엇인지 보여줄 수 있겠지요?)

문법을 처리하는 메소드들을 좀더 살펴보겠습니다.

	HashMap<String, Integer> symbTab = new HashMap<>();
	void S() {
		St();
		while (true) {		
			if (!token.is(Token.SEMI))
				break;
			token = nextToken();
			St();
		}
		grammar.checkFollow("S", token);
	}
	void St() {
		String id = token.tok; // id
		token = nextToken();  // =
		token = nextToken();
		int rval = E();
		grammar.checkFollow("St", token);
		symbTab.put(id,  rval);
		System.out.printf("[저장] %s <- %d\n", id, rval);
	}

 위 코드의 첫줄은 심볼테이블을 나타낼 해시맵입니다. 아이디와 그 아이디에 저장된 값을 가집니다. 여기서 우리는 정수값만 다루므로 값은 항상 Integer 타입일 것입니다. 문장을 처리할 때 St()에서 지정문에 대한 처리가 끝나고 우변의 수식의 계산 결과를 rval에 받으면 그것을 심볼테이블에 넣습니다. symTab.put(id, rval);

여기서 checkFollow는 다음 토큰이 이 넌터미널 St의 Follow에 속하는가를 검사하는 것입니다. 여기서 오류가 발견되면 적절한 에러 메시지와 함께 RuntimeException을 일으켜 프로그램을 종료합니다. 마찬가지로 id = E; 부분에서 적합하지 않은 토큰이 나타난 경우에 대한 오류처리는 다음과 같이 추가로 해 주어야 합니다.

	void St() {
		if (!token.is(Token.ID)) {
			throw new RuntimeException("\nid is expected, but next is "+token);
		}		
		token = nextToken();  // =
		if (!token.is(Token.EQ)) {
			throw new RuntimeException("\n= is expected, but next is "+token);
		}
		token = nextToken();
		int rval = E();

이상의 과정을 완성한 코드는 다음과 같습니다. 이 프로그램을 이용하여 if else나 for 루프 등 프로그래밍 언어의 다양한 기능을 확장해 보면 좋은 연습이 될 것입니다.

step2.txt

0.01MB

step2.output.txt

0.00MB