본문으로 이동

구문 분석

위키백과, 우리 모두의 백과사전.
(파싱에서 넘어옴)
파싱은 여기로 연결됩니다. 오스트리아의 도시에 대해서는 파싱 (오스트리아) 문서를 참고하십시오.

구문 분석(構文分析, 문화어: 구문해석, 문장해석) 또는 파싱(parsing)은 자연어, 컴퓨터 언어, 자료 구조 등 형식 문법의 규칙에 따라 일련의 문자열을 구성 성분으로 분해하여 분석하는 과정이다. 파싱(parsing)이라는 용어는 '부분(품사)'을 의미하는 라틴어 'pars (orationis)'에서 유래했다.[1]

이 용어는 언어학과 컴퓨터 과학의 각 분야에서 다소 다른 의미로 사용된다. 전통적인 문장 구문 분석은 문장이나 단어의 정확한 의미를 이해하기 위한 방법으로 수행되며, 때때로 문장 다이어그램과 같은 도구의 도움을 받기도 한다. 이는 대개 주어와 서술어와 같은 문법적 구분의 중요성을 강조한다.

전산언어학 내에서 이 용어는 문장이나 기타 단어열을 구성 성분으로 분해하여 컴퓨터가 형식적으로 분석하는 것을 의미하며, 그 결과로 상호 간의 통사적 관계를 보여주는 파스 트리를 생성한다. 이 트리에는 의미 정보가 포함될 수도 있다. 일부 구문 분석 알고리즘은 통사적 중의성을 가진 문자열로부터 파스 포레스트(parse forest)나 파스 트리 목록을 생성한다.[2]

이 용어는 언어 이해를 설명할 때 심리언어학에서도 사용된다. 이 문맥에서 구문 분석은 인간이 문장이나 구(구어 또는 텍스트)를 "문법적 구성 요소, 품사 식별, 통사적 관계 등의 측면에서" 분석하는 방식을 의미한다.[1] 이 용어는 화자가 가든 패스 문장을 해석하는 데 어떤 언어적 단서가 도움이 되는지를 논의할 때 특히 흔히 사용된다.

컴퓨터 과학 내에서 이 용어는 컴퓨터 언어 분석에 사용되며, 컴파일러 및 인터프리터 작성을 원활하게 하기 위해 입력 코드를 구성 요소로 나누는 통사적 분석을 지칭한다. 또한 분할이나 분리를 묘사하는 데 사용되기도 한다.

데이터 분석에서 이 용어는 데이터에서 원하는 정보를 추출하는 과정을 의미하는 경우가 많으며, 예를 들어 XML 문서에서 시계열 신호를 생성하는 과정 등이 이에 해당한다.

인간의 언어

[편집]

전통적 방법

[편집]

가끔 조항 분석(clause analysis)으로도 알려진 전통적인 문법 연습으로서의 구문 분석은 텍스트를 구성하는 품사로 분해하고 각 부분의 형태, 기능, 통사적 관계를 설명하는 것을 포함한다.[3] 이는 상당 부분 해당 언어의 굴절과 곡용 연구를 통해 결정되며, 굴절이 심한 언어의 경우 매우 복잡할 수 있다. "man bites dog"와 같은 구를 분석하는 것은 단수 명사 "man"이 문장의 주어이고, 동사 "bites"는 "to bite" 동사의 현재시제 3인칭 단수형이며, 단수 명사 "dog"가 문장의 목적어임을 기록하는 과정을 포함한다. 문장의 요소 간 관계를 나타내기 위해 문장 다이어그램과 같은 기법이 사용되기도 한다.

구문 분석은 과거 영어권 전역에서 문법 교육의 중심이었으며, 문어의 사용과 이해에 기본이 되는 것으로 널리 간주되었다.

계산적 방법

[편집]

일부 기계 번역 및 자연어 처리 시스템에서는 인간 언어로 된 텍스트를 컴퓨터 프로그램이 분석한다.[4] 인간의 문장은 프로그램으로 분석하기가 쉽지 않은데, 이는 인간 언어 구조에 상당한 중의성이 존재하기 때문이다. 언어의 사용은 잠재적으로 무한한 범위의 가능성 내에서 의미(또는 의미)를 전달하는 것이지만, 그중 일부만이 특정 상황과 관련이 있다.[5] 따라서 "Man bites dog"와 "Dog bites man"이라는 발화는 한 가지 세부 사항에 대해서는 명확하지만, 다른 언어에서는 더 큰 문맥에 의존하여 구별해야 하는 "Man dog bites"와 같이 나타날 수도 있다. 비록 어떤 규칙이 따르고 있다는 것은 분명하지만, 비격식적인 행동을 기술하기 위한 형식적인 규칙을 마련하는 것은 어렵다.

자연어 데이터를 구문 분석하기 위해 연구자들은 먼저 사용할 문법에 합의해야 한다. 통사 선택은 언어학적 관심사와 계산적 관심사 모두에 영향을 받는다. 예를 들어 일부 구문 분석 시스템은 어휘기능문법을 사용하지만, 일반적으로 이러한 유형의 문법을 위한 구문 분석은 NP-완전인 것으로 알려져 있다. 핵중심구구조문법은 구문 분석 커뮤니티에서 인기 있는 또 다른 언어 형식주의이지만, 다른 연구 노력들은 Penn 트리뱅크에서 사용된 것과 같은 덜 복잡한 형식주의에 집중해 왔다. 얕은 구문 분석은 명사구와 같은 주요 구성 성분의 경계만을 찾는 것을 목표로 한다. 언어적 논쟁을 피하기 위한 또 다른 인기 있는 전략은 의존 문법 구문 분석이다.

대부분의 현대 구문 분석기는 부분적으로라도 통계적이다. 즉, 이미 주석이 달린(수동으로 분석된) 말뭉치 훈련 데이터에 의존한다. 이 접근 방식은 시스템이 특정 상황에서 다양한 구성이 발생하는 빈도에 대한 정보를 수집할 수 있게 한다. (기계 학습 참조.) 사용된 접근 방식으로는 단순한 PCFG(확률 문맥 자유 문법),[6] 최대 엔트로피,[7] 그리고 신경망 등이 있다.[8] 더 성공적인 시스템 대부분은 어휘 통계를 사용한다(즉, 관련된 단어의 정체성과 품사를 고려한다). 그러나 이러한 시스템은 과적합에 취약하며 효과를 보려면 일종의 평활화가 필요하다.

자연어를 위한 구문 분석 알고리즘은 프로그래밍 언어를 위해 수동으로 설계된 문법처럼 '좋은' 속성을 갖는 문법에 의존할 수 없다. 앞서 언급했듯이 일부 문법 형식주의는 계산적으로 분석하기가 매우 어렵다. 일반적으로 원하는 구조가 문맥 자유 언어가 아니더라도, 첫 번째 패스를 수행하기 위해 문법에 대한 일종의 문맥 자유 근사가 사용된다. 문맥 자유 문법을 사용하는 알고리즘은 종종 CYK 알고리즘의 변형에 의존하며, 시간을 절약하기 위해 가능성이 낮은 분석을 가지치기하는 휴리스틱을 사용하는 경우가 많다.(차트 파싱 참조.) 그러나 일부 시스템은 시프트-리듀스 알고리즘의 선형 시간 버전 등을 사용하여 정확도보다 속도를 우선시한다. 다소 최근의 발전으로는 구문 분석기가 수많은 분석을 제안하고 더 복잡한 시스템이 최선의 옵션을 선택하는 파스 리랭킹(parse reranking)이 있다. 자연어 이해 응용 프로그램에서 의미론적 구문 분석기는 텍스트를 의미 표현으로 변환한다.[9]

심리언어학

[편집]

심리언어학에서 구문 분석은 단순히 단어를 범주에 할당하는 것(존재론적 통찰의 형성)뿐만 아니라, 문장 내 각 단어로부터 도출된 추론에 따른 문법 규칙(흔히 함축으로 알려짐)에 따라 문장의 의미를 평가하는 것을 포함한다. 이는 일반적으로 단어가 들리거나 읽히는 과정에서 발생한다.

신경언어학은 일반적으로 구문 분석을 작업 기억의 기능으로 이해한다. 즉, 구문 분석은 한 문장의 여러 부분을 동시에 머릿속에 담아두고 필요에 따라 분석할 수 있게 하는 데 사용된다는 의미이다. 인간의 작업 기억에는 한계가 있기 때문에, 문장 구문 분석 기능에도 한계가 있다.[10] 이는 정신적인 문장 구문 분석에 잠재적인 문제를 야기하는 여러 가지 통사적으로 복잡한 문장 유형을 통해 입증된다.

구문 분석 능력을 시험하는 첫 번째이자 아마도 가장 잘 알려진 유형의 문장은 가든 패스 문장이다. 이 문장들은 가장 일반적인 해석이 문법적으로 잘못된 것처럼 보이도록 설계되었지만, 더 자세히 살펴보면 문법적으로는 건전하다. 가든 패스 문장은 둘 이상의 의미를 가진 구나 단어를 포함하고 있어 분석하기 어려운데, 종종 그들의 가장 전형적인 의미가 다른 품사인 경우가 많다.[11] 예를 들어, "the horse raced past the barn fell"이라는 문장에서 raced는 처음에 과거 시제 동사로 해석되지만, 이 문장에서는 형용사구의 일부로 기능한다.[12] 구문 분석은 품사를 식별하는 데 사용되므로, 이러한 문장들은 독자의 구문 분석 능력을 시험한다.

분석하기 어려운 또 다른 유형의 문장은 첨부 중의성(attachment ambiguity)으로, 문장의 다른 부분을 잠재적으로 수식할 수 있는 구를 포함하고 있어 통사적 관계를 식별하는 데 어려움을 준다(예: "The boy saw the lady with the telescope"에서 'with the telescope'라는 중의적 구는 'the boy saw'를 수식할 수도 있고 'the lady'를 수식할 수도 있다.) [11]

구문 분석 능력을 시험하는 세 번째 유형의 문장은 중심 삽입(center embedding)으로, 구가 유사하게 형성된 다른 구의 중심에 배치되는 경우이다(예: "The rat the cat the man hit chased ran into the trap".) 2개 또는 극단적인 경우 3개의 중심 삽입이 있는 문장은 정신적 구문 분석에 어려움을 주는데, 이는 다시 통사적 관계의 중의성 때문이다.[13]

신경언어학 내에는 뇌에서 구문 분석이 어떻게 일어나는지를 설명하려는 여러 이론이 있다. 그중 하나는 문장 처리에 대한 더 전통적인 생성 모델로, 뇌 안에는 문장 분석을 위해 설계된 별도의 모듈이 있으며, 이는 어휘 인식 및 검색에 선행되고 그 후 구문 분석의 단일 통사적 결과를 고려하는 통사적 처리가 뒤따른다는 이론이다. 만약 잠재적인 문제가 감지되면 다시 돌아와 해당 통사적 해석을 수정한다.[14] 반면, 더 현대적인 모델은 마음속에서 문장의 처리가 모듈화되어 있거나 엄격한 순서로 발생하는 것이 아니라고 이론화한다. 오히려 어휘 접근, 통사적 처리, 의미 결정이 뇌에서 병렬로 일어나기 때문에 여러 가지 통사적 가능성이 동시에 고려될 수 있다고 주장한다. 이러한 방식으로 이 과정들은 통합된다.[15]

구문 분석의 신경학에 대해 아직 알아야 할 것이 많지만, 연구들은 뇌의 여러 영역이 구문 분석에 역할을 할 수 있다는 증거를 보여주었다. 여기에는 좌측 전방 측두극, 좌측 하전두회, 좌측 상측두회, 좌측 상전두회, 우측 후대상피질, 좌측 각회 등이 포함된다. 완전히 증명된 것은 아니지만, 이러한 다른 구조들이 구문 분석의 구구조 분석(phrase-structure parsing)이나 의존 구조 분석(dependency-structure parsing)을 선호할 수 있다는 점이 제안되었으며, 이는 다른 유형의 구문 분석이 아직 이해되지 않은 방식으로 처리될 수 있음을 의미한다.[16]

담론분석

[편집]

담론분석은 언어 사용과 기호학적 사건을 분석하는 방법을 조사한다. 설득력 있는 언어는 수사학이라 불릴 수 있다.

컴퓨터 언어

[편집]

구문 분석기

[편집]

구문 분석기(parser)는 입력 데이터(일반적으로 텍스트)를 가져와 자료 구조를 구축하는 소프트웨어 구성 요소이다. 이는 종종 파스 트리, 추상 구문 트리 또는 기타 계층적 구조 형태이며, 올바른 문법을 검사하는 동시에 입력에 대한 구조적 표현을 제공한다. 구문 분석은 다른 단계에 선행하거나 후행할 수 있으며, 이들이 단일 단계로 결합될 수도 있다. 구문 분석기는 종종 별도의 낱말 분석기(lexical analyser)에 선행되는데, 이 분석기는 입력 문자열에서 토큰을 생성한다. 대안으로 스캐너리스 파싱(scannerless parsing)에서는 이들이 결합되기도 한다. 구문 분석기는 수동으로 프로그래밍되거나 컴파일러 컴파일러에 의해 자동 또는 반자동으로 생성될 수 있다. 구문 분석은 포맷된 출력을 생성하는 템플릿 엔진과 상호 보완적이다. 이들은 서로 다른 도메인에 적용될 수 있지만 scanf/printf 쌍이나 컴파일러의 입력(프론트 엔드 파싱) 및 출력(백 엔드 코드 생성) 단계처럼 함께 나타나는 경우가 많다.

구문 분석기의 입력은 일반적으로 특정 컴퓨터 언어의 텍스트이지만, 자연어나 덜 구조화된 텍스트 데이터일 수도 있으며, 이 경우 일반적으로 파스 트리가 구성되기보다는 텍스트의 특정 부분만 추출된다. 구문 분석기는 scanf와 같은 매우 간단한 함수부터 C++ 컴파일러의 프론트 엔드나 웹 브라우저의 HTML 구문 분석기와 같은 복잡한 프로그램까지 다양하다. 중요한 간단한 구문 분석 클래스는 정규 표현식을 사용하여 수행된다. 이 방식에서는 정규 표현식 그룹이 정규 언어를 정의하고, 정규 표현식 엔진이 해당 언어에 대한 구문 분석기를 자동으로 생성하여 패턴 매칭 및 텍스트 추출을 가능하게 한다. 다른 문맥에서는 정규 표현식이 구문 분석 이전의 낱말 분석 단계로 사용되며, 그 결과물을 구문 분석기가 사용한다.

구문 분석기의 사용은 입력에 따라 다르다. 데이터 언어의 경우, 구문 분석기는 HTML이나 XML 텍스트를 읽는 것과 같은 프로그램의 파일 읽기 기능으로 흔히 발견된다. 이러한 예들은 마크업 언어이다. 프로그래밍 언어의 경우, 구문 분석기는 컴퓨터 프로그래밍 언어의 소스 코드를 분석하여 내부 표현의 형태로 만드는 컴파일러 또는 인터프리터의 구성 요소이다. 구문 분석기는 컴파일러 프론트 엔드의 핵심 단계이다. 프로그래밍 언어는 빠르고 효율적인 구문 분석기를 작성할 수 있기 때문에 결정론적 문맥 자유 문법으로 정의되는 경향이 있다. 컴파일러의 경우, 구문 분석 자체는 한 번의 패스 또는 여러 번의 패스로 수행될 수 있다. 원 패스 컴파일러와 멀티 패스 컴파일러를 참조하라.

원 패스 컴파일러의 암묵적인 단점은 픽스업(fix-ups)을 추가함으로써 크게 극복될 수 있다. 여기서는 전진 패스 동안 코드 재배치를 위한 준비를 하고, 현재 프로그램 세그먼트가 완료된 것으로 인식되면 후방에서 픽스업을 적용한다. 그러한 픽스업 메커니즘이 유용할 수 있는 예로는 전방 GOTO 문이 있는데, GOTO의 대상은 프로그램 세그먼트가 완료될 때까지 알 수 없다. 이 경우 픽스업 적용은 GOTO의 대상이 인식될 때까지 지연된다. 반대로, 후방 GOTO는 위치를 이미 알 수 있으므로 픽스업이 필요하지 않다.

문맥 자유 문법은 언어의 모든 요구 사항을 표현할 수 있는 범위에 제한이 있다. 비격식적으로 그 이유는 그러한 언어의 기억력이 제한되어 있기 때문이다. 문법은 임의로 긴 입력에 걸쳐 구성 요소의 존재를 기억할 수 없는데, 이는 예를 들어 이름을 참조하기 전에 선언해야 하는 언어에서는 필수적이다. 그러나 이러한 제약을 표현할 수 있는 더 강력한 문법은 효율적으로 분석될 수 없다. 따라서 문맥 자유 문법에 대해 원하는 언어 구성의 상위 집합을 허용하는(즉, 일부 잘못된 구성도 허용하는) 완화된 구문 분석기를 만드는 것이 일반적인 전략이다. 나중에 원치 않는 구성은 의미 분석(컴파일러)(맥락 분석) 단계에서 필터링될 수 있다.

예를 들어, 파이썬에서 다음은 통사적으로 유효한 코드이다:

x: int = 1
print(x)

하지만 다음 코드는 문맥 자유 문법 관점에서는 통사적으로 유효하며 이전과 동일한 구조의 구문 트리를 생성하지만, 사용 전 변수를 초기화해야 한다는 의미 규칙을 위반한다:

x: int = 1
print(y)

처리 과정 개요

[편집]
전형적인 구문 분석기에서의 데이터 흐름
전형적인 구문 분석기에서의 데이터 흐름

다음 예는 두 수준의 문법(낱말 및 통사)을 가진 컴퓨터 언어를 분석하는 일반적인 경우를 보여준다.

첫 번째 단계는 토큰 생성 또는 낱말 분석이며, 이를 통해 입력 문자열은 정규 표현식 문법으로 정의된 의미 있는 기호로 분할된다. 예를 들어, 계산기 프로그램은 "12 * (3 + 4)^2"와 같은 입력을 보고 이를 12, *, (, 3, +, 4, ), ^, 2와 같은 토큰으로 분할하는데, 각 토큰은 산술 표현식의 맥락에서 의미 있는 기호이다. 낱말 분석기는 *, +, ^, (, ) 문자가 새로운 토큰의 시작을 알린다는 규칙을 포함하여 "12*"나 "(3"과 같이 의미 없는 토큰이 생성되지 않도록 한다.

다음 단계는 구문 분석 또는 통사 분석으로, 토큰이 허용 가능한 표현식을 형성하는지 확인하는 과정이다. 이는 일반적으로 표현식을 구성할 수 있는 요소와 그 요소가 나타나야 하는 순서를 재귀적으로 정의하는 문맥 자유 문법을 참조하여 수행된다. 그러나 프로그래밍 언어를 정의하는 모든 규칙을 문맥 자유 문법만으로 표현할 수는 없다(예: 타입 유효성, 식별자의 올바른 선언). 이러한 규칙은 속성 문법으로 형식화될 수 있다.

마지막 단계는 의미론적 구문 분석 또는 분석으로, 방금 검증된 표현식의 의미를 파악하고 적절한 조치를 취하는 것이다.[17] 계산기나 인터프리터의 경우, 조치는 표현식이나 프로그램을 평가하는 것이며, 컴파일러는 코드의 일부 형태를 생성한다. 속성 문법을 사용하여 이러한 동작을 정의할 수도 있다.

구문 분석기의 유형

[편집]

구문 분석기의 작업은 기본적으로 입력이 문법의 시작 기호로부터 파생될 수 있는지, 그리고 어떻게 파생될 수 있는지를 결정하는 것이다. 이는 크게 두 가지 방식으로 수행될 수 있다.

하향식 구문 분석
하향식 구문 분석은 주어진 형식 문법 규칙을 사용하여 하향식 확장을 수행하여 파스 트리를 검색함으로써 입력 스트림의 가장 왼쪽 파생을 찾으려는 시도로 볼 수 있다. 토큰은 왼쪽에서 오른쪽으로 소비된다. 중의성을 수용하기 위해 문법 규칙의 모든 대체 우변을 확장하는 포괄적 선택이 사용된다.[18] 이를 원시 수프(primordial soup) 접근 방식이라고 한다. 문장 다이어그램과 매우 유사하게, 원시 수프는 문장의 구성 성분을 분석한다.[19]
상향식 구문 분석
구문 분석기는 입력에서 시작하여 이를 시작 기호로 다시 쓰려고 시도할 수 있다. 직관적으로 구문 분석기는 가장 기본적인 요소를 찾은 다음 이를 포함하는 요소를 찾는 방식으로 진행한다. LR 파서는 상향식 구문 분석기의 예이다. 이 유형의 구문 분석기에 사용되는 또 다른 용어는 시프트-리듀스 구문 분석이다.

LL 파서와 재귀 하향 파서는 좌좌회귀 생산 규칙을 수용할 수 없는 하향식 구문 분석기의 예이다. 간단한 하향식 구문 분석 구현은 직접적 및 간접적 좌좌회귀를 수용할 수 없으며 중의적 문맥 자유 문법을 분석할 때 지수 시간 및 공간 복잡도가 필요할 수 있다고 여겨졌지만, Frost, Hafiz, Callaghan에 의해 중의성과 좌좌회귀를 다항 시간 내에 수용하고 잠재적으로 지수적인 수의 파스 트리를 다항식 크기로 표현할 수 있는 더 정교한 하향식 구문 분석 알고리즘이 만들어졌다.[20][21] 그들의 알고리즘은 주어진 문맥 자유 문법에 관하여 입력의 가장 왼쪽 파생과 가장 오른쪽 파생을 모두 생성할 수 있다.

구문 분석기와 관련하여 중요한 구별은 구문 분석기가 가장 왼쪽 파생을 생성하는지 아니면 가장 오른쪽 파생을 생성하는지이다(문맥 자유 문법 참조). LL 파서는 가장 왼쪽 파생을 생성하고 LR 파서는 가장 오른쪽 파생을 생성한다(일반적으로 역순이지만).[18]

일부 그래픽 구문 분석 알고리즘은 시각 프로그래밍 언어를 위해 설계되었다.[22][23] 시각 언어를 위한 구문 분석기는 때때로 그래프 문법에 기반한다.[24]

적응형 구문 분석 알고리즘은 "자기 확장형" 자연어 사용자 인터페이스를 구축하는 데 사용되었다.[25]

구현

[편집]

간단한 구문 분석기 구현은 전체 입력 파일을 읽고 중간 계산이나 변환을 수행한 다음 전체 출력 파일을 쓰는 방식(예: 인메모리 멀티 패스 컴파일러)이다.

대안적인 구문 분석기 구현 접근 방식:

  • 푸시 구문 분석기(push parsers)는 입력 스트림에서 관련 토큰을 감지하는 즉시 등록된 핸들러(콜백)를 호출한다. 푸시 구문 분석기는 입력 중 관련 없는 부분을 건너뛸 수 있다(예: Expat).
  • 풀 구문 분석기(pull parsers)는 입력 텍스트를 "당겨오는(pulling)" 방식으로, 일반적으로 컴파일러 프론트 엔드에서 사용된다.
  • 증분 구문 분석기(incremental parsers)(예: 증분 차트 파서)는 사용자가 파일 텍스트를 편집할 때 파일 전체를 다시 분석할 필요가 없다.
  • 능동형 대 수동형 구문 분석기[26][27]

구문 분석기 개발 소프트웨어

[편집]

잘 알려진 구문 분석기 개발 도구는 다음과 같다:

룩어헤드

[편집]
2 토큰 룩어헤드 없이는 분석할 수 없는 C 프로그램. 위: C 문법 발췌.[28] 아래: 구문 분석기가 "int v;main(){" 토큰을 소화하고 Stmt를 도출할 규칙을 선택하려는 상황이다. 첫 번째 룩어헤드 토큰 "v"만 봐서는 두 가지 Stmt 대안 중 무엇을 선택해야 할지 결정할 수 없으며, 후자는 두 번째 토큰을 엿봐야 한다.

룩어헤드는 구문 분석기가 어떤 규칙을 사용할지 결정하기 위해 사용할 수 있는 최대 들어오는 토큰 수를 설정한다. 룩어헤드는 LL 파서, LR 파서, LALR 파서와 특히 관련이 있으며, 알고리즘 이름 뒤에 괄호로 룩어헤드를 명시하는 경우가 많다(예: LALR(1)).

구문 분석기의 주 대상인 대부분의 프로그래밍 언어는 룩어헤드가 제한된(일반적으로 1개) 구문 분석기가 분석할 수 있도록 세심하게 정의되는데, 룩어헤드가 제한된 구문 분석기가 더 효율적인 경우가 많기 때문이다. 이러한 경향에 대한 중요한 변화는 1990년 테렌스 파(Terence Parr)가 그의 박사 학위 논문을 위해 효율적인 LL(k) 파서를 위한 구문 분석기 생성기인 ANTLR을 만들면서 시작되었는데, 여기서 k는 임의의 고정된 값이다.

LR 파서는 일반적으로 각 토큰을 본 후 몇 가지 작업만 수행한다. 시프트(나중에 줄이기 위해 이 토큰을 스택에 추가), 리듀스(스택에서 토큰을 꺼내 통사적 구성을 형성), 끝, 오류(적용 가능한 규칙 없음) 또는 충돌(시프트할지 리듀스할지 알 수 없음)이다.

룩어헤드에는 두 가지 장점이 있다.

  • 충돌 발생 시 구문 분석기가 올바른 동작을 취하도록 돕는다. 예를 들어, else 절이 있는 경우 if 문을 분석할 때 그렇다.
  • 중복 상태를 많이 제거하고 추가 스택의 부담을 덜어준다. 룩어헤드가 없는 C 언어 구문 분석기는 약 10,000개의 상태를 가질 것이다. 룩어헤드 구문 분석기는 약 300개의 상태를 갖는다.

예: 표현식 1 + 2 * 3 구문 분석

표현식 구문 분석 규칙(문법이라 함)의 집합은 다음과 같다,
Rule1:E → E + E표현식은 두 표현식의 합이다.
Rule2:E → E * E표현식은 두 표현식의 곱이다.
Rule3:E → number표현식은 단순한 숫자이다.
Rule4:+는 *보다 우선순위가 낮다.

대부분의 프로그래밍 언어(APL 및 Smalltalk와 같은 일부 제외)와 대수 공식은 덧셈보다 곱셈에 더 높은 우선순위를 부여하며, 이 경우 위의 예에 대한 올바른 해석은 1 + (2 * 3)이다. Rule4는 의미 규칙임에 유의하라. 이 규칙을 통사 구조에 포함하도록 문법을 다시 작성하는 것은 가능하다. 그러나 모든 규칙이 통사 구조로 변환될 수는 없다.

룩어헤드가 없는 간단한 구문 분석기 동작

초기 입력 = [1, +, 2, *, 3]

  1. Rule3을 예상하여 입력에서 "1"을 스택으로 시프트한다. 입력 = [+, 2, *, 3] 스택 = [1]
  2. Rule3을 기반으로 "1"을 표현식 "E"로 리듀스한다. 스택 = [E]
  3. Rule1을 예상하여 입력에서 "+"를 스택으로 시프트한다. 입력 = [2, *, 3] 스택 = [E, +]
  4. Rule3을 예상하여 입력에서 "2"를 스택으로 시프트한다. 입력 = [*, 3] 스택 = [E, +, 2]
  5. Rule3을 기반으로 스택 요소 "2"를 표현식 "E"로 리듀스한다. 스택 = [E, +, E]
  6. Rule1을 기반으로 스택 항목 [E, +, E]와 새 입력 "E"를 "E"로 리듀스한다. 스택 = [E]
  7. Rule2를 예상하여 입력에서 "*"를 스택으로 시프트한다. 입력 = [3] 스택 = [E, *]
  8. Rule3을 예상하여 입력에서 "3"을 스택으로 시프트한다. 입력 = [] (비어 있음) 스택 = [E, *, 3]
  9. Rule3을 기반으로 스택 요소 "3"을 표현식 "E"로 리듀스한다. 스택 = [E, *, E]
  10. Rule2를 기반으로 스택 항목 [E, *, E]와 새 입력 "E"를 "E"로 리듀스한다. 스택 = [E]

파스 트리와 그 결과 코드는 언어 의미론에 따라 올바르지 않다.

룩어헤드 없이 올바르게 분석하려면 세 가지 해결책이 있다:

  • 사용자가 표현식을 괄호로 묶어야 한다. 이는 종종 실행 가능한 해결책이 아니다.
  • 구문 분석기는 규칙을 위반하거나 완료되지 않을 때마다 백트래킹(backtrack)하고 재시도할 더 많은 논리를 가져야 한다. LL 파서에서 이와 유사한 방법을 따른다.
  • 대안으로, 구문 분석기나 문법은 리듀스를 지연시키고 어떤 규칙을 먼저 리듀스해야 할지 확실할 때만 리듀스할 추가 논리를 가져야 한다. 이 방법은 LR 파서에서 사용된다. 이 방법은 표현식을 올바르게 분석하지만 더 많은 상태와 증가된 스택 깊이가 필요하다.
룩어헤드 구문 분석기 동작
  1. Rule3을 예상하여 입력 1에서 스택으로 1을 시프트한다. 즉시 리듀스하지 않는다.
  2. Rule3을 기반으로 입력 +에서 스택 항목 1을 단순 표현식으로 리듀스한다. 룩어헤드는 +이므로 E + 경로에 있으므로 스택을 E로 리듀스할 수 있다.
  3. Rule1을 예상하여 입력 +에서 스택으로 +를 시프트한다.
  4. Rule3을 예상하여 입력 2에서 스택으로 2를 시프트한다.
  5. Rule3을 기반으로 입력 *에서 스택 항목 2를 표현식으로 리듀스한다. 룩어헤드 *는 그 앞에 E만 기대한다.
  6. 이제 스택에는 E + E가 있고 여전히 입력은 *이다. 이제 Rule2에 기반하여 시프트하거나 Rule1에 기반하여 리듀스할 두 가지 선택이 있다. Rule4에 기반하여 *가 +보다 우선순위가 높으므로 Rule2를 예상하여 *를 스택으로 시프트한다.
  7. Rule3을 예상하여 입력 3에서 스택으로 3을 시프트한다.
  8. Rule3을 기반으로 입력 끝을 본 후 스택 항목 3을 표현식으로 리듀스한다.
  9. Rule2에 기반하여 스택 항목 E * E를 E로 리듀스한다.
  10. Rule1에 기반하여 스택 항목 E + E를 E로 리듀스한다.

생성된 파스 트리는 정확하며 룩어헤드가 없는 구문 분석기보다 단순하다. 이것이 LALR 파서에서 따르는 전략이다.

구문 분석 알고리즘 목록

[편집]
이 문단은 다음의 발췌 내용입니다: 알고리즘 목록 § 구문 분석.[편집]

같이 보기

[편집]

각주

[편집]
  1. 1 2 “Parse”. dictionary.reference.com. 2010년 11월 27일에 확인함.
  2. ↑ Masaru Tomita (2012년 12월 6일). 《Generalized LR Parsing》. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  3. ↑ “Grammar and Composition”. 2016년 12월 1일에 원본 문서에서 보존된 문서. 2012년 11월 24일에 확인함.
  4. ↑ Christopher D.. Manning; Christopher D. Manning; Hinrich Schütze (1999). 《Foundations of Statistical Natural Language Processing》. MIT Press. ISBN 978-0-262-13360-9.
  5. ↑ Jurafsky, Daniel (1996). “A Probabilistic Model of Lexical and Syntactic Access and Disambiguation”. 《Cognitive Science》 20 (2): 137–194. CiteSeerX 10.1.1.150.5711. doi:10.1207/s15516709cog2002_1.
  6. ↑ Klein, Dan, and Christopher D. Manning. "Accurate unlexicalized parsing." Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 1. Association for Computational Linguistics, 2003.
  7. ↑ Charniak, Eugene. "A maximum-entropy-inspired parser 보관됨 2019-04-01 - 웨이백 머신." Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference. Association for Computational Linguistics, 2000.
  8. ↑ Chen, Danqi, and Christopher Manning. "A fast and accurate dependency parser using neural networks." Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 2014.
  9. ↑ Jia, Robin; Liang, Percy (2016년 6월 11일). “Data Recombination for Neural Semantic Parsing”. arXiv:1606.03622 [cs.CL].
  10. ↑ Sandra H. Vos, Thomas C. Gunter, Herbert Schriefers & Angela D. Friederici (2001) Syntactic parsing and working memory: The effects of syntactic complexity, reading span, and concurrent load, Language and Cognitive Processes, 16:1, 65-103, DOI: 10.1080/01690960042000085
  11. 1 2 Pritchett, B. L. (1988). Garden Path Phenomena and the Grammatical Basis of Language Processing. Language, 64(3), 539–576. https://doi.org/10.2307/414532
  12. ↑ Thomas G Bever (1970). 《The cognitive basis for linguistic structures》. OCLC 43300456.
  13. ↑ Karlsson, F. (2010). Working Memory Constraints on Multiple Center-Embedding. Proceedings of the Annual Meeting of the Cognitive Science Society, 32. Retrieved from https://escholarship.org/uc/item/4j00v1j2
  14. ↑ Ferreira, F., & Clifton, C. (1986). The independence of syntactic processing. Journal of Memory and Language, 25(3), 348–368. https://doi.org/10.1016/0749-596X(86)90006-9
  15. ↑ Atlas, J. D. (1997). On the modularity of sentence processing: semantical generality and the language of thought. Language and Conceptualization, 213–214.
  16. ↑ Lopopolo, Alessandro, van den Bosch, Antal, Petersson, Karl-Magnus, and Roel M. Willems; Distinguishing Syntactic Operations in the Brain: Dependency and Phrase-Structure Parsing. Neurobiology of Language 2021; 2 (1): 152–175. doi: https://doi.org/10.1162/nol_a_00029
  17. ↑ Berant, Jonathan, and Percy Liang. "Semantic parsing via paraphrasing." Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2014.
  18. 1 2 Aho, A.V., Sethi, R. and Ullman, J.D. (1986) " Compilers: principles, techniques, and tools." Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
  19. ↑ Sikkel, Klaas (1997). 《Parsing schemata : a framework for specification and analysis of parsing algorithms》. Berlin: Springer. ISBN 9783642605413. OCLC 606012644.
  20. ↑ Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars 보관됨 2018-08-22 - 웨이백 머신 ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.
  21. ↑ Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167 - 181, January 2008, San Francisco.
  22. ↑ Rekers, Jan, and Andy Schürr. "Defining and parsing visual languages with layered graph grammars." Journal of Visual Languages & Computing 8.1 (1997): 27-55.
  23. ↑ Rekers, Jan, and A. Schurr. "A graph grammar approach to graphical parsing." Visual Languages, Proceedings., 11th IEEE International Symposium on. IEEE, 1995.
  24. ↑ Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "A context-sensitive graph grammar formalism for the specification of visual languages." The Computer Journal 44.3 (2001): 186-200.
  25. ↑ Jill Fain Lehman (2012년 12월 6일). 《Adaptive Parsing: Self-Extending Natural Language Interfaces》. Springer Science & Business Media. ISBN 978-1-4615-3622-2.
  26. ↑ Patrick Blackburn and Kristina Striegnitz. "Natural Language Processing Techniques in Prolog".
  27. ↑ Song-Chun Zhu. "Classic Parsing Algorithms".
  28. ↑ taken from Brian W. Kernighan and Dennis M. Ritchie (Apr 1988). 《The C Programming Language》 2판. Prentice Hall Software Series. Englewood Cliffs/NJ: Prentice Hall. ISBN 0131103628. (Appendix A.13 "Grammar", p.193 ff)

외부 링크

[편집]
원본 주소 "https://ko.wikipedia.org/w/index.php?title=구문_분석&oldid=42535915"