[계산이론] - (11) 파싱과 모호성(Parsing, Ambiguity)

 

 

 

파싱(Parsing)

주어진 문자열 w가 어떠한 문법 G로부터 생성되는 언어 L(G)에 속하는지의 여부를 알아야 하는 경우가 있습니다.

이를 판별하기 위한 알고리즘을 소속성(membership) 알고리즘이라 합니다.

파싱의 의미는 L(G)에 속하는 w가 유도되는데 사용된 일련의 생성규칙을 찾는 것 입니다.

 

 

 

단순한 파싱 방법으로는 체계적(systematically)으로 가능한 모든 유도들을 구성해 가면서, 그 중에 w와 일치하는 것이 있는지를 알아보는 것입니다.

 

구체적으로, 처음으로는 다음과 같은 형태의 시작 심벌을 좌변으로 갖는 모든 생성규칙들을 살펴봅니다.

$$S \to x$$

 

 

시작 심벌 S로부터 한 단계에 유도될 수 있는 모든 문장형태 w를 찾습니다.

 

만약 어느 x도 일치하지 않는다면, 이후 각x의 가장 왼쪽 변수에 적용될 수 있는 모든 생성규칙들을 적용합니다.

 

이렇게 생성된 새로운 문장형태들 중 일부는 w에 유도될 가능성이 있으며, 일부는 제외됩니다.

 

이런식으로 계속하여 w를 유도할 때까지 반복합니다.

 

이러한 방법은 w의 유도를 찾기 위해 시작 심벌 S로부터 모든 가능한 유도들을 생성하므로,
이를 철저한 탐색 파싱(exhaustive search parsing)이라 부릅니다.

해당 파싱방법은 유도트리를 루트에서부터 시작하여 아래로 내려오면서 구성하는 것으로 볼 수 있기 때문에 하향식 파싱(top-down parsing)의 한 형태입니다.

 

 

 

예시

너무 길어 이후 과정은 생략합니다

 

 

 

 

 

 

 

 

 

철저한 탐색 파싱의 문제점

모든 가능한 유도 과정들을 모두 고려하기 때문에, 우선 효율적이지 못합니다.

게다가 w가 L(G)에 속하지 않는다면, 해당 과정이 종료되지 않을 수도 있습니다.

 

이를 해결하기 위해, 문법이 가질 수 있는 생성규칙의 형태에 제한을 두면 철저한 탐색 파싱에서 발생하는 비종료(nontermination)문제를 해결할 수 있습니다.

 

생성규칙의 제한은 다음 두 생성규칙을 허용하지 않는 것입니다.

람다 생성규칙과, 단위 생성규칙(우변에 변수 하나만이 존재)을 제거합니다.
$$A \to \lambda$$
$$A \to B$$

 

 

 

 

위 생성규칙을을 제거함으로써 문자열 w에 대한 파싱은 각 유도 단계마다 문장 형태의 심볼의 수가 최소한 하나 이상 증가하므로 항상 |w| 단계 이내에 종료됩니다.

w의 길이 혹은 w를 구성하는 단말 심벌들의 개수는 | w |를 초과할 수 없으며, 따라서 유도 과정의 총 단계 수는 2| w |를 초과할 수 없습니다.

 

 

 

그러나 이 방법은 문장 형태의 수가 지나치게 많아질 수 있다는 단점이 있습니다.

첫 단계 후에는 최대 |P|개의 문장 형태가 나올 수 있으며, 두번째 단계에는 |P|의 제곱, 3번째 단계에는 |P|의 3제곱, ....

즉 지수 형태로 증가하므로, 이는 매우 많은 비용이 소모될 수 있습니다.

 

 

 

 

최종적으로 원하는 것은 문자열의 길이에 비례하는 시간이 걸리는, 즉 선형 시간(Linear time)을 갖는 파싱 알고리즘입니다.

그러나 일반적인 경우 이러한 알고리즘은 아직 밝혀지지 않았습니다만

특정한 경우, 선형 시간 알고리즘을 적용할 수 있습니다.

 

 

 

 

 

 

 

단순 문법(Simple Grammer) (s-문법)

문맥-자유 문법 G = (V, T, S, P)의 모든 생성규칙들이 다음과 같은 형태이면 단순 문법(simple grammer) 혹은 s-문법(s-grammer)이라 불립니다.
$$A \to ax$$
여기서 A ∈ V, a ∈ T, x ∈ V* 이며, 임의의 쌍 (A, a)는 P에서 많아야 한 번 나타납니다.

terminal symbol이 문법의 우변에 맨 앞에 단 하나 등장하여야 하며, 이후 등장하는 Nonterminal Symbol의 수에는 제약이 없습니다.

 

 

예시

아래는 s-문법입니다.

$$S \to aS \; | \; bSS \; | \; c$$

 

 

아래는 s-문법이 아닙니다.

$$S \to aS \; | bSS \; |\; aSS \; | \; c$$

$$S \to Sa$$

 

 

 

 

 

 

 

 

 

단순 문법(S-문법)의 파싱

G가 s-문법이면, L(G)에 속한 모든 문자열 w가 | w |에 비례하는 노력(선형 시간)으로 파싱될 수 있습니다
s-문법은 좌변의 변수에 대하여, 우변은 중복되지 않는 terminal symbol 1개로 시작하므로 파싱의 각 단계마다 하나의 terminal symbol을 생성합니다.
즉 전체 과정이 | w | 단계 내에 완료됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

모호성(Ambiguity)

w ∈ L(G)인 한 문자열에 대하여 여러 개의 다른 유도 트리들이 존재할 가능성이 있는 것을 모호성이라 합니다.

문맥-자유 문법 G에서 두 개 이상의 서로 다른 유도 트리를 갖는 문자열 w가 존재하면, 문법 G는 모호하다고 합니다.

즉 모호성은 어떤 문자열 w에 대하여 두 개 이상의 좌측 우선 혹은 우측 우선 유도가 존재하는 것을 의미합니다.

 

모호성은 자연언어의 일반적인 특징입니다.

자연언어에서는 모호성이 허용되며 여러가지 방식으로 처리될 수 있지만, 프로그래밍 언어에서는 각 문장이 정확히 하나의 의미로 해석되어야 하기에 가능한 모호성을 제거해야 합니다.

 

이를 위해 주어진 문법을 동치이면서 모호하지 않은 다른 문법으로 다시 구성하여 모호성을 제거할 수 있습니다.

 

 

 

 

 

 

예를 들어 다음 문법을 통해 a + a*a를 만들어 보겠습니다.

$$ E \to E \;+ \;E\; |\; E \;* \;E\; |\; a$$

$$E \Rightarrow E + E \Rightarrow a+ E \Rightarrow  a + E * E \Rightarrow  a + a * E \Rightarrow  a + a * a$$
$$E \Rightarrow E * E \Rightarrow E + E * E \Rightarrow  a + E * E \Rightarrow  a + a * E \Rightarrow  a + a * a$$

 

다음과 같이 두개의 좌측 우선 유도가 존재하므로 이는 모호한 문법입니다.

해당 문법을 다음과 같이 변환하여 모호하지 않도록 바꾸어 보겠습니다.

$$E \to \;E \;+\; T \;| \;T$$
$$T \to \;T \;*\; F \;| \;F$$
$$F \to \;(E)\; | \;a$$

 

 

 

 

 

 

 

 

 

 

고유적으로 모호함(Inherently Ambiguous)

앞에서 보았던 모호한 문법들은 동치이면서 모호하지 않은 문법으로 재구성할 수 있었습니다.

그러나 어떤 언어는 언어 자체가 갖는 모호성 떄문에 모호하지 않은 문법의 구성이 불가능할 수 있습니다.

문맥 자유 언어 L이 모호하지 않은 문법을 가지면 L을 모호하지 않다고 합니다.
L을 생성하는 모든 문법들에 대해서 각 문법이 모호하면 L은 고유적으로 모호하다고 합니다.