[오토마타] 15. Parsing

이번 글에서는 CFL라는 새로운 종류의 언어에 대해 어떤 문장이 이 CFL에 속하는지 판별하는 방법을 알아보자.

먼저 결론을 말하면, CFL에 대해 membership을 판단할 때는 parsing을 통해 판단할 수 있다.

 

Parsing

파싱은 L(G)에 속하는 문장 w를 유도하는 production 의 나열을 찾는 것을 말한다.

 

 

 

위와 같은 문법이 주어졌을 때, aabb 와 abb가 이 문법으로 만들어지는 언어에 포함되는지 확인해보자. (membership problem)

CFL에서 멤버쉽을 따질 때는 파싱 알고리즘으로 주어진 문장이 L에 포함되는지 확인할 수 있다.

파싱을 했더니 w를 유도하는 production 시퀀스가 존재했다면 멤버인 것이고, 아니라면 멤버가 아닌 것이다.

 

1. aabb

aabb는 다음과 같이 유도할 수 있다. S => aSb => aaSbb => aabb

따라서 aabb 는 L(G)에 속하는 문장이다.

 

2. abb

abb는 L(G)에 속하는 문장이 아니다.

주어진 production 을 보면 a를 하나 추가할 때 반드시 b도 동일하게 1개 추가되므로, a와 b의 개수가 다를 수 없기 때문이다.

 

 

지금은 직관에 의존해서, 혹은 운이 좋게, 파싱을 통해 membership을 판단했으나,

컴퓨터에게 대신 파싱을 통해 멤버쉽을 판단하도록 시킨다면, 그때는 좀 더 체계적인 알고리즘이 필요하다.

그 알고리즘으로 간단하게 생각할 수 있는 방법은 '일단 가능한 경우의 수를 다 해보는 것'이다.

이를 가리켜 exhaustive search parsing 이라고도 한다. (top-down parsing)

 

이때 변수가 여러개 있다면 이전 글에서도 정리하였듯, 어떤 변수를 먼저 바꾸는지는 중요하지 않다.

따라서 leftmost든 rightmost든 일관되게 하나의 변수를 선택해서 교체한다.

 

예를 들어, 위 예시에서는 1번째 라운드에서 다음과 같이 4가지 경우를 시도할 수 있다.

 

 

시작 변수가 S 인데, S로부터 갈 수 있는 프로덕션이 4가지 있기 때문이다.

이제 이 4가지 중에서 절대 aabb 를 유도할 수 없는 것을 지우면, 위 그림과 같이 3, 4번 선택지를 지울 수 있다.

 

다음으로 2번째 라운드에서 leftmost derivation 방법으로 한번 더 유도한다고 하면 아래와 같은 경우의 수가 존재한다.

 

 

이제 여기에서 다음으로 round 3이 되면 또 leftmost derivation으로 가능한 경우의 수를 다 해볼 것이다.

 

 

 

그 경우의 수가 매우 많지만, 위와 같이 aabb가 유도되는 경우에 접근하면 답을 찾을 수 있고, 이로부터 aabb가 L(G)의 문장임을 판별할 수 있다.

 

사실 위 예시와 같이 라운드를 거듭할 수록 sentential form 의 길이가 계속 증가한다면 언젠가는 답을 찾을 수 있다.

우리가 찾고자 하는 문장의 길이는 유한하므로, 그 유한한 길이를 넘어가는 sentential form 에서 부터는 더 이상 고려할 필요가 없기 때문이다.

 

이 방법은 현재 단계에서 적용할 수 있는 모든 production의 경우의 수를 다 시도해보므로, 시간이 오래 걸린다. (지수 시간 소요)

그래도 시간이 오래 걸려도 답을 찾아낼 수만 있다면 다행이겠지만, 이 방법은 또 다른 문제가 있다.

바로 아무리 시간을 들여도 파싱이 아예 끝나지 않을 수도 있다는 것이다.

 

 

 

예를 들어 이렇게 1개 변수에서 1개 변수를 produce하는 프로덕션이나, λ로 끝나는 프로덕션이 있다면 파싱이 무한히 끝나지 않을 수 있다.

전자의 경우 sentential form 의 길이가 그대로 유지되므로 특정 길이가 넘어가면 파싱을 종료하는 방식을 사용할 수 없고,

후자의 경우에는 λ로 끝나면 오히려 길이가 짧아지므로 길이가 늘어났다가 줄어들면 계속 같은 길이를 유지할 수 있기 때문이다.

따라서 파싱을 통해 확실하게 멤버쉽을 판별하려면 이런 프로덕션을 제거할 필요가 있다.

(이와 관련해서는 다음 글에서 더 자세히 정리한다.)

 

예를 들어 5.7 예시에서 S→SS | λ 만 생각해보면 S→S와 같은 유도가 나올 수 있으므로, 무한히 반복해서 파싱을 진행할 위험이 있다.

그래서 이 문제를 해결하기 위해, 위에서 말한 2가지 production을 제거하여 아래와 같이 문법을 바꿀 수 있다.

 

 

 

이 5.8 예제의 문법은 5.7 예제의 문법과 비교했을 때 생성하는 언어가 λ를 제외하고는 모두 동일하다.

그리고 이 문법에서는 무한히 파싱할 위험이 없으므로, λ가 아닌 문장에 대해서는 확실하게 membership을 판단할 수 있다.

매 라운드마다 production을 적용하면 sentential form의 길이가 반드시 1 이상 증가하기 때문이다.

따라서 길이가 w인 문자열에 대해 membership 판별을 시도했을 때, 판별 결과는 반드시 w 라운드 이내에 끝난다.

 

이를 정리하면 다음과 같다.

 

G = (V, T, S, P) 가 CFG이며, A→B 또는 A→λ 형태의 production을 가지지 않는다면,
exhaustive searching parsing 방법으로 파싱했을 때 언젠가는 반드시 종료된다.

 

 

그렇다면 최악의 경우, 몇 번의 라운드를 거쳐야 파싱이 종료될까?

최악의 어떤 문자열의 길이가 w 라면, 최악의 경우에는 2w 만큼의 라운드를 거쳐야 파싱이 종료될 수 있다.

왜냐하면 각 라운드에서 변수의 개수가 늘어나거나, 변수가 terminal 로 바뀌거나 둘 중 하나의 과정이 발생할 수 있기 때문이다.

 

극단적인 예시를 들면, 길이가 w 인 문자열을 유도하기 위해, 변수가 1개씩 증가하는 produce를 최대 w번 적용할 수 있고,

길이가 w인 sentential form에 대해, 각각의 변수 하나를 터미널 심볼 하나로 바꾸는 과정을 최대 w번 적용할 수 있으므로

최대 2w 번의 라운드가 필요하다.

 

사실 라운드 횟수만 놓고보면 linear 하므로 그래도 괜찮아보인다.

그런데 각 라운드에서 선택가능한 프로덕션의 경우의 수를 고려하면, 최악의 경우, 매 라운드마다 모든 프로덕션을 다 고려해야 할 수도 있다. 즉, 매 라운드마다 프로덕션 개수만큼의 setential form 이 만들어지는 것이다.

 

만약 프로덕션의 개수가 p 라고 한다면, 최악의 경우 문장임을 판별하는데 고려해야 할 총 sentential form의 개수는

1라운드에서는 p개, 2라운드에서는 p² 개, ...., 2w 라운드에서는  p²ʷ 개를 고려하므로, 

 

p + p² + ... +  p²ʷ ≦ p²ʷ⁺¹ 

 

따라서 O(p²ʷ⁺¹) 만큼의 sentential form을 고려해야 한다.

 

따라서 exhaustive searching parsing 알고리즘은, 설사 반드시 파싱이 가능하도록 문법을 개선하였다고 하더라도,

(프로덕션의 개수도 중요하지만) 판별하려는 문장의 길이에 따라 exponential 하게 시간이 증가하므로 효율적인 알고리즘은 아니다.

실제로는 CYK 라는 알고리즘을 사용하며, 이 알고리즘은 문장 길이가 w 일 때 w³ 만큼의 라운드를 통해 문장인지 판별할 수 있다.

이전의 방법보다는 매우 효율적이지만, 여전히 세제곱에 비례하므로, 그렇게까지 효율적이지는 않다.

 

 

Simple Grammar

이전에 알아본 방법은 파싱에 시간이 너무 오래걸리는 단점이 있었다.

제일 좋은 것은 문장의 길에 비례한 리니어 타임에 파싱을 완료하는 것일텐데, 과연 그 방법은 없을까?

 

이를 위해 CFG에 제약을 더 걸어서 더 단순하게 만든 Simple grammar 가 등장하였다.

Simple Grammar(또는 s-grammar)의 정의는 다음과 같다.

 

 

모든 프로덕션이 A→aX 형태이고 (a는 터미널, X는 0개 이상의 변수), (A, a) 조합이 프로덕션에서 유일한 문법

 

 

s-grammar는 모든 production의 화살표 왼쪽에 1개 변수만 존재하므로 CFG이다.

 

 

 

예시를 보면서 위 문법이 s-grammar 인지 판별해보자.

 

첫 번째 문법은 S 라는 화살표 왼쪽의 한 개 변수에 대해 오른쪽에는 터미널-변수나열 형태이고, (S, 터미널) 조합이 한 번씩만 등장하므로 simple grammar 이다.

 

두 번째 문법은 형태는 s-grammar를 만족하나, (S, a) 조합이 두 번 등장하므로 s-grammar 가 아니다.

 

 

실제로 문자열을 넣어보면서 s-grammar에서의 파싱 과정을 살펴보자.

만약 abc 라는 문자열에 대해 이 문자열이 주어진 문법으로 만들어지는 언어에 속하는지 판단한다면,

첫 번째 문법을 사용하는 경우, a를 읽었을 때 어떤 production을 사용할 지 유일하게 결정할 수 있다.

반면 두 번째 문법을 사용하는 경우, a를 읽었을 때 어떤 production을 사용할 지 결정할 수 없으므로 선택지가 발생한다.

 

따라서 s-grammar를 사용하면 모든 문장을 linear time에 파싱할 수 있다.

매번 하나의 symbol을 읽을 때마다 그때그때 유일한 production이 결정되기 때문이다.

(따라서 길이가 w라면 총 w의 라운드를 거쳐 파싱할 수 있다.)

 

 

---

Ambiguity

CFG는 반드시 모호하거나 모호하지않거나 둘 중 하나의 속성을 갖는다.

어떤 CFG가 모호하다는 뜻은, 해당 문법으로 만들어지는 언어의 문장 중에 단, 하나라도 2개 이상의 derivation tree를 가질 수 있으면 모호하고, 모든 문장이 유일한 derivation tree를 가지면 모호하지 않다.

 

 

예시를 보면 이해가 빠르다.

주어진 문법에 대해, aabb 를 유도해보면 두 가지 방법으로 유도된다.

이를 각각 derivation tree로 그려보면 아래와 같이 그려진다.

 

 

특히 T2의 루트에서 왼쪽 서브트리는 T1과 동일함을 알 수 있다.

따라서 T1 과 T2는 다르고, 서로 다른 derivation tree 가 만들어졌으므로 이 문법은 모호하다.

 

이번엔 실제 프로그래밍 언어에서 자주 사용하는 if-else 문법 예제를 살펴보자.

 

 

이 문법은 모호할까?

주어진 문장으로 2개 이상의 derivation tree가 그려지는지 확인해보자.

 

 

이렇게 서로 다른 트리가 그려질 수 있다.

따라서 이 문법 역시 모호하다.

 

결국 어떤 문법이 모호하다는 뜻은, 주어진 문자열이 분명 그 문법으로부터 유도가 되어 문장이기는 하나, 그 유도 과정이 일관되지 않아 누구는 이렇게 유도하고 누구는 저렇게 유도할 수 있어서 모호하다는 뜻이다.

 

위 예시에서는 w 에 들어있는 else 라는 것이, 어떤 것에 대한 else 인지 모호하다고도 말할 수 있다.

자신과 가까이 있는 if 에 대한 else 인지, 그보다 왼쪽에 있는 if 에 대한 else 인지 해석하기에 따라 달라지기 때문이다.

따라서 프로그래밍 언어에서는 이런 모호함이 발생하지 않도록 꼼꼼하게 규칙을 만들어야 한다.

 

그럼 위 문법이 모호하지 않도록 기존 문법을 개선해보자.

 

 

기존 문법이 모호했던 이유는 else 가 어떤 if에 걸리는지 모호했기 때문에 발생한 문제였다.

if (if) else 인지, if (if else) 인지 알 수 없었던 것이다.

 

그래서 위 문법에서는 else 가 반드시 제일 가까운 if 에만 걸리도록 명확하게 문법을 작성하였다.

먼저 S 는 if 문만 만들어 내고, A 는 if-else 문만 만들어내도록 하였다.

그리고 if-else 에서 if 뒤에는 if-else 문만 들어갈 수 있도록 제약을 걸었다.

그러면 if else / if (if else) else / .. 와 같은 형식으로만 파싱이 가능하므로 모호하지 않아진다. 

 

---

 

또 다른 예시를 보면, 이번에는 a + b * c 라는 문장을 넣었을 때, 주어진 문법이 모호한지 아닌지 판단해보자.

이 문법은 컴퓨터 입장에서 모호해서는 안된다.

예를 들어 2 + 3 * 4 를 계산할 때 경우에 따라 해석하는 게 다르다면 서로 다른 연산 결과가 나올 수 있기 때문이다.

 

 

이 production을 가진 문법을 제대로 정의해보면 위와 같이 작성할 수 있다.

이때 프로그래밍 언어의 관점에서 보면 E는 사실 expression, I = identifier(식별자) 라고 유추할 수도 있다.

 

여기서 이 문법을 보면 사실 직관적으로 이 문법은 모호하다는 것을 느낄 수 있다.

왜냐하면 E로부터 유도 가능한 수식에 대해 E + E 와 E * E 가 아무거나 선택해서 등장할 수 있기 때문이다.

이 둘 사이에 우선순위가 명시되어 있지 않으면 서로 다른 연산 결과가 나오므로 모호할 것이다.

 

한번 derivation tree 를 통해 이를 확인해보자.

 

 

먼저 주어진 문법으로부터 a + b * c 를 유도하는 첫 번째 방법은 위와 같다.

여기에서는 곱셈을 먼저하고 덧셈을 한 것과 같은 방법으로 파싱했다고 볼 수 있다.

(E + E 라는 커다란 결과에 대해서 뒤의 E는 곱셈의 결과이므로)

 

 

반면 트리를 위와 같이 그린다면 이번엔 E 를 E * E 로 먼저 바꾸고나서 덧셈을 만들었으므로,

연산자 우선순위 관점에서 덧셈을 먼저하고 곱셈을 한 것과 같다.

 

결론적으로는 서로 다른 두 개의 derivation tree를 만들었으므로 이 문법은 모호하다는 것을 알 수 있다.

 

실제 수학에서의 연산자 우선순위를 고려하여 문법을 생성한 것은 아래의 5.12 예제와 같다.

 

이 예제에서는 E를 곱셈의 결과인 T 단독으로 produce 하거나, E와 T의 덧셈을 produce 하도록 하고 있다.

따라서 곱셈을 먼저 처리하고 그 다음에 덧셈을 진행하므로 연산자 우선순위를 명시하였다.

 

 

이 문법에 맞춰 같은 문장에 대해 derivation tree 를 그리면 위와 같으며, 위 트리 외에는 derivation tree가 존재하지 않는다.

 

---

언어에서의 ambiguity

이제 이 '모호함'과 관련된 내용을 문법이 아니라 '언어'에 적용해보자.

그러면 모든 CFL에 대해서 다음 정리가 성립한다.

 

모호하지 않은 문법이 존재하는 CFL은 unambiguous 하고,
모든 문법이 ambiguous 한 CFL은 inherently ambiguous 하다.

 

 

즉, CFL은 모호하지 않거나 / 태생적으로 모호하거나 둘 중 하나이다.

언어에 대해서 조금 다르게 표현이 되는 이유는, 하나의 언어를 표현하는 문법이 여러가지가 있을 수 있기 때문이다.

 

그래서 이 언어를 표현하는 여러 문법 중에 하나라도 모호하지 않은 문법이 있다면, 이 언어는 모호하지 않다고 말할 수 있게 되고,

그런 문법이 없다면 = 모든 문법이 모호하다면 이 언어는 태생적으로 모호하다고 할 수 있다.

 

 

예를 들어 위와 같은 언어를 보자.

먼저 주어진 언어들이 CFL인지 확인하기 위해, 세 언어를 CFG로 표현할 수 있는지 생각해보자.

 

 

그러면 이렇게 L1, L2, L 에 대해서 모두 CFG를 만들 수 있기 때문에 세 언어는 모두 CFL이다.

L1의 문법을 보면, 이 언어는 a, b의 개수가 같고, c의 개수가 독립적이므로, a와 b의 개수가 같은 결과를 갖도록 하는 변수 A를 두고, A 뒤에 원하는 만큼 c를 붙일 수 있도록 하였다.

 

L2에서는 거꾸로 b와 c의 개수가 같은 변수를 B로 두고, 그 앞에 a를 원하는 만큼 붙일 수 있게 두었다.

 

L은 이 둘의 합집합이므로 L1, L2 중 하나를 선택하도록 S1 / S2 변수를 두고, 하나가 선택된 이후에는 그 경우에 대해 L1 또는 L2의 문법을 그대로 적용하도록 하였다.

 

그렇다면 L이 inherently ambiguous 하다는 것을 증명할 수 있을까?

수업에서는 아이디어만 간단하게 말씀해주셨는데, 그 아이디어는 다음과 같다.

 

L1 과 L2의 교집합을 생각해보면 그 교집합 언어는 a, b, c의 개수가 모두 같은 언어이다.

이때 이 교집합에 속하는 언어는 L의 문법을 볼 때 S1으로부터 유도될 수도, S2로부터 유도될 수도 있으므로 반드시 모호하다.

(교집합 언어에 대해서는 모호하지 않은 문법이 존재할 수 없다.) 따라서 이 언어는 태생적으로 모호하다.

 

사실 이 문법 말고도 다른 문법이 있을 수 있기에 엄밀한 증명은 아니긴 하지만, 결론을 말하면 이 언어는 태생적으로 모호한 언어이다.

 

---

BNF

실제로 프로그래밍 언어에서는 BNF 라는 유명한 폼을 사용하여 프로그래밍 언어의 문법을 기술한다.

 

 

그 예시는 위와 같으며, < > 로 묶은 것이 변수이고, ::= 가 화살표에 해당한다.

| 는 위에서 본 문법에서 or 과 같은 의미를 가진다. 이외에 < > 로 감싸지지 않은 부분은 터미널로서 심볼에 해당한다.

 

그리고 BNF의 형식을 보면 결국 프로그래밍 언어의 문법을 BNF로 표현하면 CFG 인 것 과 같다.

화살표 왼쪽에 변수가 1개만 있기 때문이다.

 

특히 while 문의 문법과 같은 경우를 보면 while 이라는 터미널 하나에 대해서는 이 production만 존재하도록 하는 simple grammar 형식을 띄는 것이 일반적이다. 그래야 컴파일러가 파싱하기 편하기 때문이다.

 

마지막으로 실제 컴파일러는 이렇게 syntax 형태를 확인하는 것 말고도, 의미론적으로 올바른지 symantics 도 검증해야 한다.

예를 들어 char c; c = 3.2; 와 같이 작성한 경우에 syntax는 올바를 수 있어도 char 형 변수에 실수를 저장하고 있으므로 의미론적으로는 올바르지 않다.

 

하지만 CFG로는 이런 의미론적 정의까지 표현할 수 있다.