파스 트리 (2) - 모호성과 모호성 제거

1. 좌우선(leftmost) 유도와 우우선(rightmost) 유도

• 문법을 잘못 만들면 상황에 따라 다른 모호한 파스트리가 만들어 질 수 있다.
• 좌우선(leftmost) 유도 : 왼쪽 non terminal부터 유도한다.
• 우우선(rightmost) 유도 : 오른쪽 non terminal부터 유도한다.
• 아래와 같은 문법으로 파스트리를 만들면 항상 같은 파스트리가 만들어진다. (모호성이 없다)

// 좌우선(Leftmost) 유도
<number> → <number><digit>
         → <number><digit><digit>
         → <digit><digit><digit>
         → 1<digit><digit>
         → 12<digit>
         → 123

// 우우선(Rightmost) 유도
<number> → <number><digit>
         → <number>3
         → <number><digit>3
         → <number>23
         → <digit>23
         → 123

 

[그림] 모호하지 않은 파스트리

 

2. 모호성제거 (1) - 연산자의 종류에 따른 우선순위

1) 모호한 파스트리의 생성 이유

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> ＋ <expr>
           | <expr> －<expr>
           | <expr> * <expr>
           | <number>
           
<number> → <number><digit>
               | <digit>

<digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

• 눈치챘을 수도 있지만 이 모호성은 대부분 "연산자의 종류에 따른 우선순위"에서 기인된다.
• <expr> + <expr>과 <expr> * <expr>의 우선순위가 같다고 해놓아서 다른 결과가 나오는 것이다
• 우리가 사칙연산을 할 때는 *가 빠르다고 생각하고 연산하지만, +가 빠르다고 생각하면 다른 결과가 나온다
• 다음은 A = 3 + 5 * 2의 좌우선, 우우선 파스트리이다. 두 파스트리가 다르기 때문에 연산 결과도 다르다.

 

[그림] 좌우선유도와 우우선유도가 다른 파스트리

• 위 그림을 보면, 처음에 assign하고나서 id = expr까지는 동일하게 진행된다.
• 그리고 나서 여기에 expr을 더할 것인지, 곱할 것인지 선택하게 되는데 여기에서 문제가 발생한다.
• 결론부터 말하자면 여기에서 더하기를 선택해야한다. 왜냐하면, 우리가 파스트리로 연산을 진행할때는
• 거꾸로부터 타고 올라가기 때문이다. 즉, 곱하기가 늦게 선택되어야 곱하기를 먼저 연산하게 된다.
• 결국 좌우선은 5 * 2를 먼저 하고 3에 더하지만(정답), 우우선은 3 + 5를 하고 거기에 2를 곱한다(오답)

 

2) 왜 거꾸로 타고 올라가서 연산할까?

private int precedence(char c) {
	if (c == '*' || c == '/') return 2;
	else if (c == '+' || c == '-') return 1;
	else return 0;
}

public String transform(String inFix) {
	char[] f = inFix.toCharArray();
	ListStack stack = new ListStack();
	String postFix = "";

	for (char c : f) {
		if (c == '(')
			stack.push(c);
            
		else if (c == ')') {
			while (!stack.isEmpty() && stack.peek() != '(')
				postFix += (char) stack.pop();     
                
			stack.pop();
            
		} else if (c == '+' || c == '-' || c == '*' || c == '/') {
			while (!stack.isEmpty() && precedence((char) stack.peek()) >= precedence(c))
				postFix += (char) stack.pop();
                
			stack.push(c);
            
		} else if (c >= '0' && c <= '9')
			postFix += c;
		}

	while (!stack.isEmpty())
		postFix += (char) stack.pop();
        
	return postFix;
}

• 왜 거꾸로 타고 올라가야하냐면,,, 사실 이거 알고리즘(후위표기법)때 했던 것과 동일한 원리이다
• 파스트리는 트리구조를 이용했지만, 스택을 써서 파스트리와 똑같이 구현해놓은 것이 위 알고리즘이다.
• 사칙연산을 할때는 먼저 Stack에 연산자들을 push하고 규칙에 따라 pop하면 후위표기법으로 변한다.
• 그러나, 곱하기를 가장 먼저 연산하려면 스택에 가장 마지막에 넣어야하는데 (후입선출이므로),
• 곱하기가 먼저 들어가면 스택 구조상 가장 늦게 나오게 되고, 그럼 더하기 먼저 연산 되는 것이다.

 

3) 해결방법 

• 자, 그럼 해결방법은 무엇일까? 생각보다 엄청 간단하다. 그냥 더 높은 순위의 연산자(곱하기)가
• 무조건 더 나중에 스택에 들어가게만 만들어주면 끝이다. 그렇게 하면, 곱하기가 먼저 Pop된다.
• BNF로 보자. 결과는 <expr>과 * 연산 사이에 하나의 비단말 기호 <term>을 넣어주는 것이다.
• term은 expr과 절대 더할 수 없다. 때문에, term으로 바꾸기 전에 더하기를 스택에 넣어야만 계산할 수 있다
• 즉 더하기 먼저 스택에 넣고 더해지는 하나의 대상을 term을 선택하여 곱하기를 스택에 넣어야만 한다.

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> + <expr>
       | <expr> - <expr>
       | <term>

<term> → <term> * <term>
       | <number>

<number> → <number><digit>
        ｜ <digit>

<digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

[그림] 강제로 +를 선택하게 만들어서 모호성 해결

• 이 파스트리의 경우, 가장 아래쪽에 위치한 연산인 곱하기가 스택에서 나와서 먼저 계산되고,
• 그리고나서 더하기가 나와서 더해지고 연산을 종료한다. 그런데 만약 assign에서 나뉘어 지고,
• expr에서 덧셈보다 먼저 곱하기 먼저 스택에 넣기 위해 비단말 기호를 term으로 바뀌 버리는 순간,
• 그 이후로는 다시는 expr으로 돌아올 수 없게 되고, 더하기 연산을 절대 할 수 없게 된다.

 

3. 모호성 제거 (2) - 피연산자(Operand) 순서에 의한 우선순위

1) 모호한 파스트리 생성 이유

[그림] 피연산자의 순서에 따른 모호성

• 자, 다 끝난 것 같지만 "B = 3 - 5 - 2"를 예제를 보면 또 다시 모호성이 발생한다.
• 두 뺄셈 연산의 우선순위가 동일해서, 둘중 무엇을 먼저 연산해야 하는지 모르기 때문이다.
• 즉, 무슨 말이냐면 3 - 5를 먼저 연산할지, 5 - 2를 먼저 연산할지 몰라서 모호성이 생긴다.
• 일반적으로 우리는 앞 연산자를 먼저 계산하는데, 지금의 문법은 그런 Rule이 없기 때문이다.
• 때문에 뒤쪽 뺄셈 연산이 스택에 먼저 들어가게 해주면 된다. (제일 늦게 Pop되서 늦게 연산된다)

 

2) 해결방법

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> + <term>
       | <expr> - <term>
       | <term>

<term> → <term> * <term>
       | <number>

<number> → <number><digit>
        ｜ <digit>

<digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

• 이렇게 변경하면 동일한 연산자에서 피연산자의 순서에 따라 달라지는 우선순위 문제를 해결할 수 있다.
• expr과 expr은 뺄 수 없게 만든다. 하나의 expr을 expr과 term 사이의 뺄셈이던 덧셈연산으로 바꿀 때
• 앞쪽만 expr으로 살고 뒤쪽은 term으로 죽는다. 그래서 앞쪽에서만 반드시 뺄셈을 전개해야만 하게되고,
• 그러면 앞쪽 피연산자들 사이에서 먼저 뺄셈 연산이 먼저 수행될 수 밖에 없다. (그림을 보면 이해간다)

 

[그림] 강제로 뒤쪽 피연산자로 연산 못하게 만들어서 모호성 해결

 

4. 모호성 제거 결론

• 연산자 높은 우선순위의 연산자가 더 나중에 선택(스택에 push)되게 하기 위해서 높은 우선순위의
• 연산자인 곱셈은 BNF 상에서 아예 따로 떼서 분리해버리고, 다시 덧셈연산을 못하게끔 만들어서
• 무조건 덧셈을 찍고(스택에 Push) 그리고 나서 곱셈을 선택(스택에 Push)할 수 밖에 없게 만든다거나,
• 아니면 피연산자 순서에 의한 모호성을 막기 위해 한쪽에서는 연산이 전개되게 못하게 막아버리는 등
• 몇몇 노벨한 아이디어를 적용하여 모호성을 훌륭하게 제거할 수 있다. 모호성이 제거된 파스트리는
• 구문분석단계를 넘어가서 의미분석후에, 중간코드를 생성하게 되고, 목적프로그램이 생성된다.