💻 컴퓨터 과학

Disambiguating Context-Free Grammars by Selecting the Minimum-Cost Parse Tree

이 논문은 임의의 문맥 자유 문법을 모호성을 해소하기 위해 파스 트리 선택을 최소 비용 최적화 문제로 취급하며, 원래의 언어를 보존하면서 패널티가 부여된 모호성 패턴을 기반으로 단일 최적 트리를 찾기 위해 동적 계획법을 사용하는 방법을 제안한다.

원저자: Mina Hematikarimkhani

게시일 2026-11-05

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mina Hematikarimkhani

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

언어는 단순한 부분들로부터 복잡한 아이디어를 구축할 수 있게 해주는 규칙의 체계입니다. 컴퓨터의 세계에서 이러한 규칙들은 문법(grammars)이라 불리며, 기계가 코드의 문자열이나 문장을 어떻게 이해해야 하는지 알려줍니다. 이상적으로, 일련의 규칙은 주어진 입력에 대해 오직 하나의 가능한 의미만을 도출해야 합니다. 그러나 프로그래밍 언어를 설명하는 데 사용되는 많은 문법은 모호하며, 이는 하나의 텍스트 문자열이 여러 가지 상충하는 방식으로 해석될 수 있음을 의미합니다. 전형적인 예로, 더하기와 곱하기와 같은 두 가지 연산이 포함된 문장이 있습니다. 명확한 지침이 없다면, 컴퓨터는 더하기를 먼저 하고 그다음에 곱하기를 해야 할지, 아니면 곱하기를 먼저 하고 그다음에 더하기를 해야 할지 알 수 없습니다. 마찬가지로, "if" 문이 사슬처럼 이어질 때, 컴퓨터는 어떤 조건에 "else" 명령이 속하는지 알지 못할 수 있습니다. 컴퓨터가 올바르게 작동하려면 반드시 단 하나의 해석을 선택해야 하지만, 규칙 자체는 종종 명확한 승자를 제시하지 못합니다.

수십 년 동안 이 혼란을 처리하는 표준적인 방법은 규칙을 직접 다시 쓰거나, 컴퓨터가 막혔을 때 어느 경로를 택할지 알려주는 특별한 선언을 추가함으로써 규칙을 덜 모호하게 강제하는 것이었습니다. 이러한 방법들은 특정 유형의 문제에는 잘 작동하지만, 인간의 개입을 필요로 하며 때로는 언어의 원래 구조를 깨뜨릴 수 있습니다. 미나 헤마티카림카니(Mina Hematikarimkhani)가 제안한 새로운 접근 방식은 이 문제를 규칙을 재작성하여 해결해야 할 퍼즐이 아니라, 최적화 과제로 취급합니다. 이 방법은 잘못된 답을 삭제하려고 노력하는 대신, 컴퓨터가 모든 가능한 해석을 평가하고 특정 기준에 따라 가장 "저렴한(cheapest)" 것을 선택하도록 요청합니다.

핵심 아이디어는 컴퓨터가 텍스트를 이해하기 위해 구축하는 모든 가능한 트리 형태의 구조에 비용을 할당하는 것입니다. 이 시스템에서 트리는 문장을 파싱하는 하나의 방식을 나타냅니다. 비용은 금전적 가치가 아니라 세 가지 요인에 기반한 점수입니다. 첫째, 시스템은 트리가 사용자의 선호 패턴(예: 어떤 연산이 먼저 일어나야 하는지에 대한 규칙)을 얼마나 위반하는지 계산합니다. 둘째, 트리의 노드 수를 계산하는데, 이는 컴퓨터가 무한 루프에 빠지는 것을 방지하는 데 도움을 줍니다. 마지막으로, 만약 두 트리의 점수가 같다면, 컴퓨터가 항상 정확히 동일한 결과를 선택할 수 있도록 고유 식별자가 동점 상황을 해결합니다. 그러면 컴퓨터는 총점이 가장 낮은 트리를 유지합니다. 이 시스템은 잘못된 선택을 아예 금지하기보다 벌점을 부여하는 방식이기 때문에, 설령 그 해석이 일부 규칙 위반을 포함하더라도, 언어 내의 모든 유효한 문장이 정확히 하나의 해석을 갖도록 보장합니다.

이 최적의 트리를 찾기 위해 연구진은 복잡한 문제를 더 작고 중복되는 조각들로 나누어 해결하는 방법인 동적 계획법(dynamic programming)을 사용합니다. 컴퓨터가 문장을 보면서 그 문장의 모든 작은 덩어리들을 이해하는 최선의 방법을 찾아낸 다음, 그 덩어리들을 결합하여 전체를 이해한다고 상상해 보십시오. 연산 순서를 결정하는 것과 같은 단순한 경우, 컴퓨터는 인접한 이웃들만 살펴보면 됩니다. 그러나 "else" 절이 근처의 "if"에 속하는지 혹은 멀리 있는 것에 속하는지를 결정해야 하는 "dangling else" 문제와 같이 더 복잡한 상황의 경우, 컴퓨터는 구조를 더 깊이 들여다봐야 합니다. 이를 처리하기 위해 연구진은 '프로필(profile)'이라는 개념을 도입했습니다. 컴퓨터가 트리의 작은 조각을 구축할 때, 부모 구조에게 그 아래에 무엇이 있는지(예: 해당 브랜치가 특정 유형의 규칙으로 끝나는지 여부)를 알려주는 짧은 요약, 즉 프로필을 함께 생성합니다. 이를 통해 컴퓨터는 매번 전체 트리를 처음부터 다시 구축할 필요 없이, 문장의 먼 부분에 대해서도 정보에 입각한 결정을 내릴 수 있습니다.

이 방법은 빈 단계(empty steps)나 다른 시스템을 혼란스럽게 할 수 있는 순환 참조를 포함하는 규칙 세트에도 적용 가능합니다. 테스트에서 연구진은 혼합 연산자가 포함된 수학적 표현식과 중첩된 조건문을 포함하여 다양한 예시에 이 기술을 적용했습니다. 모든 경우에서 시스템은 단 하나의 가장 적절한 트리를 성공적으로 식별해 냈습니다. 예를 들어, 덧셈과 곱셈이 모두 포함된 문자열이 주어졌을 때, 시스템은 표준 수학적 우선순위를 준수하는 트리를 선택하고, 이 규칙을 위반하는 트리에 더 높은 비용을 할당했습니다. 중첩된 "if" 문을 마주했을 때, 시스템은 "else"를 가장 가까운 "if"에 연결하여 프로그래밍의 표준 관례를 따랐습니다. 또한 시스템은 특정 규칙이 제공되지 않은 경우에도 구조 자체에 기반한 일관되고 결정론적인 선택을 기본값으로 하여 처리했습니다.

이 방법은 강력하지만, 저자는 그 한계점에 대해서도 명확히 밝히고 있습니다. 알고리즘을 실행하는 데 걸리는 시간은 입력값이 커짐에 따라 크게 증가하므로, 초당 수백만 줄의 코드를 처리하는 현대의 고속 프로덕션 컴파일러의 요구 사항을 충족하기에는 너무 느립니다. 대신 연구진은 이 접근 방식이 임의의 사용자 정의 문법을 다뤄야 하는 도구들, 예를 들어 언어 에디터, 정적 분석 도구, 또는 원시적인 속도보다 재현성과 복잡하고 지저질한 규칙의 처리가 더 중요한 교육용 소프트웨어에 가장 적합하다고 제안합니다. 결과의 품질은 전적으로 사용자가 제공하는 패턴에 달려 있습니다. 만약 규칙이 불완전하거나 모순된다면, 시스템은 여전히 결과를 반환하겠지만 그것이 인간이 의도한 결과와는 다를 수 있습니다. 이 방법은 문법이 애초에 모호한지 여부를 판별하는 근본적인 수학적 문제를 해결하는 것이 아니라, 일단 모호함에 직면했을 때 이를 탐색하는 신뢰할 수 있는 방법을 제공합니다.

이 연구는 우리가 언어 처리를 생각하는 방식의 변화를 나타냅냅니다. 컴퓨터가 문장을 접하기 전에 언어의 규칙을 완벽하게 만들도록 강요하는 대신, 컴퓨터가 모든 가능성을 탐색하고 명확하고 측정 가능한 기준에 따라 최선의 것을 선택하도록 허용합니다. 이는 모호함이 많은 자연어와 인공 언어의 특징임을 인정하고, 원래의 구조를 잃지 않으면서 이를 관리할 수 있는 방법을 제시합니다. 이 문제를 최소 비용을 찾는 탐색으로 취급함으로써, 연구진은 유연하고 견고하며, 복잡한 문법의 무질서한 현실을 다룰 수 있는 도구를 만들어 모든 유효한 문장에 대해 항상 하나의 명확하고 재현 가능한 답이 존재하도록 했습니다.

기술 요약: 최소 비용 파스 트리 선택을 통한 문맥 자유 문법의 모호성 해소

문제 정의
프로그래밍 언어를 기술하는 데 사용되는 문맥 자유 문법(CFG)은 종종 모호하여, 하나의 입력 문자열이 여러 개의 파스 트리(parse tree)를 생성할 수 있습니다. 인터프리터와 컴파일러는 단일하고 특정한 해석을 필요로 하지만, 기존의 모호성 해소 기술들은 특정 제약 조건이나 파이프라인 단계에 의존하는 경우가 많습니다. 우선순위 선언(예: Yacc/Bison의 precedence declarations)은 적용 후에도 문법이 충돌이 없는 상태가 되어야만 충돌을 해결할 수 있으며, 문법 재작성은 수동 개입을 요구하고 트리 구조를 변경합니다. 또한, 파싱 후의 트리 필터(post-parsing tree filters)는 만약 남은 트리들을 모두 삭제하게 될 경우 유효한 문자열까지 거부할 위험이 있습니다. 나아가, 파싱 표현 문법(PEG)은 구조 중 하나를 선택하는 것이 아니라 순서가 있는 선택(ordered choice)을 통해 언어의 정의 자체를 변경함으로써 모호성을 해결합니다.

방법론
저자는 모호성 해소를 필터링이나 재작성 작업이 아닌 최적화 문제로 다룰 것을 제안합니다. 핵심 접근 방식은 모든 가능한 파스 트리에 비용을 할당하고 최소 비용 트리를 선택하는 것입니다.

비용 모델 (Cost Model):
파스 트리 $t$ 의 비용은 렉시코그래픽(lexicographic) 삼중항 $c(t) = (v(t), |t|, \kappa(t))$ 로 정의됩니다:

위반 횟수 ( $v(t)$ ): 만족된 "금지된 패턴"의 수입니다. 이 패턴들은 트리플 $(p, k, c)$ 로 구성되며, 규칙 $p$ 를 사용하는 노드에서 $k$ 번째 자식은 규칙 $c$ 를 사용해서는 안 된다는 것을 명시합니다. 이 구성 요소는 "소프트(soft)"한 것으로, 위반 사항에 페널티를 부여하지만 트리를 엄격히 금지하지는 않으므로, 언어 내의 문자열에 대해 항상 솔루션이 존재함을 보장합니다.
트리 크기 ( $|t|$ ): 비단말(non-terminal) 노드의 수입니다. 이 구성 요소는 사이클(예: $A \to A$ )을 처리하며, 임의로 긴 유닛 유도(unit derivation) 체인을 가진 트리에 페널티를 부여함으로써 종료를 보장합니다.
정준 키 (Canonical Key, $\kappa(t)$ ): 동점 상황을 해결하기 위해 사용되는 결정론적인 규칙 인덱스와 분할 지점(split points)의 시퀀스로, 출력이 유일함을 보장합니다.

알고리즘:
최소 비용 트리의 선택은 입력 스팬(span)에 대한 동적 계획법(dynamic programming)을 사용하여 수행되며, 이는 CYK 알고리즘과 유사합니다.

단순 패턴: 직계 자식만을 포함하는 패턴의 경우, 알고리즘은 루트 규칙 $r$ 을 가진 스팬 $[i, j)$ 위의 비단말 $A$ 에 대한 최적의 트리 $B[A, i, j, r]$ 을 유지합니다.
비국소적 패턴을 위한 프로파일 (Profiles for Non-Local Patterns): 부모가 서브트리에 대해 알아야 하는 정보(예: else가 가장 가까운 if에 붙어야 하는 "dangling else" 문제와 같이 자식, 형제, 손자 또는 우측 스파인(right spine)의 규칙을 고려해야 하는 경우)를 처리하기 위해, 저자는 프로파일을 도입합니다. 프로파일 $\sigma(t)$ 는 루트 규칙, 특정 손자들의 규칙, 그리고 서브트리의 우측 스파인에 있는 감시 대상 규칙의 부분 집합과 같은 정보를 캡슐화합니다. 동적 계획법 테이블은 $B[A, i, j, \sigma]$ 로 확장되어 각 프로파일에 대한 최적의 트리를 저장합니다.
사이클 및 $\epsilon$ -규칙 처리: 알고리즘은 스팬의 길이를 증가시키며 처리합니다. 스팬 내에서는 고정점(fixed point)에 도달할 때까지 반복 수행되며(Bellman-Ford와 유사), 사이클이나 빈 규칙(empty rules)이 존재하는 경우에도 종료를 보장하기 위해 트리 크기 구성 요정에 의존합니다.

주요 기여

렉시코그래픽 비용 정의: 유일한 최소값이 존재함을 보장하고, 사이클을 자연스럽게 처리하며, 결정론을 보장하는 비용 함수를 정의했습니다.
일반화된 동적 계획법: $\epsilon$ -규칙이나 사이클이 포함된 모든 CFG에 대해 작동하는 CYK 스타일의 알고리즘을 제시하며, 문법이 특정 정규형(normal form)에 있을 필요가 없습니다.
프로파일 메커니즘: 프로파일의 도입은 비국소적 모호성 해소 패턴(형제, 손자, 우측 스파인에 대한 조건 등)을 지원하도록 동적 계획법 접근 방식을 확장합니다.
구현 및 검증: 저자는 구현을 제공하고 연산자 우선순위, 결합 법칙, 중첩된 if-else 구조를 포함한 표준 예제들에 대해 알고리즘의 정확성을 입증했습니다.

결과
구현체는 $O(n^4 \cdot C)$ 시간 복잡도로 실행되며, 여기서 $n$ 은 입력 길이이고 $C$ 는 문법 및 패턴 집합에 의존하는 상수입니다.

정확성: 테스트된 모든 사례(연산자 우선순위, 결합 법칙, dangling else, 순환 문법)에서 알고리즘은 유효한 입력 문자열당 정확히 하나의 파스 트리를 성공적으로 반환했습니다.
동작: 알고리즘은 패턴 위반이 없는 트리를 우선적으로 선택합니다. 위반을 피할 수 없는 경우, 트리 크기와 정준 키로 순차적으로 넘어가 재현 가능한 결과를 보장합니다.
비교: 트리 필터와 달리, 이 방법은 유효한 문자열을 절대 거부하지 않습니다. LR 생성기와 달리, 모호성 해소 후 문법이 LALR(1) 호환성을 갖출 필요가 없습니다.

의의 및 한계
저자는 이 방법을 생산용 컴파일러를 위한 선형 시간 LR 파서의 대체재가 아니라, 임의의 사용자 제공 문법을 처리하면서 재현 가능한 답을 제공해야 하는 범용 도구(예: 언어 워크벤치, 에디터, 정적 분석 프런트엔드)를 위한 견고한 솔루션으로 위치시킵니다.

논문은 다음과 같은 몇 가지 한계를 명시적으로 인정합니다:

패턴 의존성: 결과의 "정확성"은 전적으로 제공된 패턴의 품질에 달려 있습니다. 불완전하거나 모순된 패턴은 정준 키에 기반한 임의의 선택을 초래할 수 있습니다.
패턴의 범위: 현재 패턴 언어는 하향식 문맥(자식, 형제, 손자, 우측 스파인)으로 제한되어 있으며, 좌측 스파인이나 임의의 깊이를 검사할 수 없습니다.
성능: $O(n^4)$ 의 복잡도는 대규모 입력을 다루기에 선형 시간 파서에 비해 부적합합니다.
모호성 결정 불가능성: 이 방법은 문법이 모호한지 여부를 결정하려고 시도하지 않습니다(이는 결정 불가능한 문제입니다). 단지 특정 입력 문자열에 대한 모호성을 해소할 뿐입니다.

결론적으로, 본 논문은 모의성을 해소하기 위해 원래의 언어 정의를 보존하면서 비용 최소화를 통해 유일한 파스 트리를 보장하는 일관되고 선언적인 프레임워크를 제공합니다.

유사한 논문