LR 파서

컴퓨터 과학에서, LR 파서(LR parser)는 선형 시간에 결정론적 문맥 자유 언어를 분석하는 상향식 파서의 한 종류이다.^[1] LR 파서에는 SLR 파서, LALR 파서, 정규 LR(1) 파서, 최소 LR(1) 파서, 일반화된 LR 파서(GLR 파서) 등 여러 변형이 있다. LR 파서는 파싱할 언어의 구문을 정의하는 형식 문법으로부터 파서 생성기에 의해 생성될 수 있다. 이들은 컴퓨터 언어 처리에 널리 사용된다.

LR 파서(왼쪽에서 오른쪽으로, 역방향에서 가장 오른쪽 파생)는 입력을 왼쪽에서 오른쪽으로 되돌아가지 않고 읽으며(대부분의 파서에 해당), 역방향으로 가장 오른쪽 파생을 생성한다. 즉, 상향식 파싱을 수행하며 하향식 LL 파싱이나 애드혹 파싱을 수행하지 않는다. "LR" 이름 뒤에는 종종 "LR(1)" 또는 때로는 "LR(k)"와 같이 숫자 한정자가 붙는다. 퇴각검색이나 추측을 피하기 위해 LR 파서는 이전 심볼을 파싱하는 방법을 결정하기 전에 k개의 미리 보기 입력 심볼을 미리 볼 수 있다. 일반적으로 k는 1이며 언급되지 않는다. "LR" 이름 앞에는 종종 "SLR" 및 "LALR"와 같은 다른 한정자가 붙는다. 문법에 대한 "LR(k)" 표기법은 커누스가 "k 범위로 왼쪽에서 오른쪽으로 번역 가능"을 의미한다고 제안했다.^[1]

LR 파서는 결정론적이다. 즉, 추측이나 퇴각검색 없이 선형 시간 내에 단일의 올바른 파싱 결과를 생성한다. 이는 컴퓨터 언어에 이상적이지만, LR 파서는 더 유연하지만 필연적으로 느린 방법을 필요로 하는 인간 언어에는 적합하지 않다. 임의의 문맥 자유 언어를 파싱할 수 있는 일부 방법(예: 콕-영거-카사미, 얼리, GLR)은 최악의 경우 O(n³) 시간 성능을 보인다. 잘못 추측하면 퇴각검색을 하거나 여러 파싱 결과를 산출하는 다른 방법은 지수 시간을 소요할 수도 있다.^[2]

위의 L, R, k 속성은 우선순위 파서를 포함한 모든 시프트-리듀스 파서가 공유한다. 그러나 관례적으로 LR이라는 이름은 도널드 커누스가 발명한 파싱 방식을 의미하며, 초기에는 덜 강력했던 우선순위 방식(예: 연산자 우선순위 파서)은 제외한다.^[1] LR 파서는 우선순위 파서나 하향식 LL 파싱보다 더 넓은 범위의 언어와 문법을 처리할 수 있다.^[3] 이는 LR 파서가 발견한 내용을 확정하기 전에 어떤 문법 패턴의 전체 인스턴스를 볼 때까지 기다리기 때문이다. LL 파서는 그 패턴의 가장 왼쪽 입력 심볼만 보았을 때 훨씬 더 일찍 자신이 무엇을 보고 있는지 결정하거나 추측해야 한다.

개요

예제 A * 2 + 1에 대한 상향식 파스 트리

LR 파서는 입력 텍스트를 한 번에 한 방향으로 스캔하고 구문 분석한다. 파서는 파스 트리를 추측이나 백트래킹 없이 점진적으로, 상향식으로, 왼쪽에서 오른쪽으로 구축한다. 이 과정의 모든 지점에서 파서는 이미 구문 분석된 입력 텍스트의 서브트리 또는 구문 목록을 축적했다. 이 서브트리들은 파서가 아직 서브트리들을 결합할 구문 패턴의 오른쪽 끝에 도달하지 않았기 때문에 아직 함께 결합되지 않았다.

예제 파싱의 6단계에서는 "A * 2"만 불완전하게 파싱되었다. 파스 트리의 음영 처리된 왼쪽 아래 모서리만 존재한다. 7번 이상 번호가 매겨진 파스 트리 노드는 아직 존재하지 않는다. 노드 3, 4, 6은 각각 변수 A, 연산자 *, 숫자 2에 대한 고립된 서브트리의 루트이다. 이 세 개의 루트 노드는 파스 스택에 임시로 보관된다. 입력 스트림의 나머지 구문 분석되지 않은 부분은 "+ 1"이다.

시프트 및 리듀스 동작

다른 시프트-리듀스 파서와 마찬가지로 LR 파서는 시프트 단계와 리듀스 단계를 조합하여 작동한다.

시프트 단계는 입력 스트림에서 한 심볼씩 전진한다. 이 시프트된 심볼은 새로운 단일 노드 파스 트리가 된다.
리듀스 단계는 완료된 문법 규칙을 최근의 파스 트리 중 일부에 적용하여 새로운 루트 심볼을 가진 하나의 트리로 결합한다.

입력에 구문 오류가 없으면, 파서는 모든 입력이 사용되고 모든 파스 트리가 전체 유효 입력을 나타내는 단일 트리로 축소될 때까지 이러한 단계를 계속한다.

LR 파서는 언제 리듀스할지, 그리고 비슷한 끝을 가진 규칙들 중에서 어떻게 선택할지 결정하는 방식에서 다른 시프트-리듀스 파서와 다르다. 그러나 최종 결정과 시프트 또는 리듀스 단계의 순서는 동일하다.

LR 파서의 효율성은 결정론적이라는 점에서 비롯된다. 추측을 피하기 위해 LR 파서는 이전에 스캔한 심볼을 어떻게 처리할지 결정하기 전에 종종 다음 스캔된 심볼을 미리 본다(오른쪽으로). 어휘 스캐너는 파서보다 하나 이상의 심볼을 앞서 작업한다. 미리 보기 심볼은 파싱 결정에 대한 '오른쪽 컨텍스트'이다.^[4]

상향식 파스 스택

다른 시프트-리듀스 파서와 마찬가지로 LR 파서는 어떤 구성 요소의 모든 부분을 스캔하고 파싱할 때까지 느긋하게 기다린 다음, 결합된 구성 요소가 무엇인지 확정한다. 파서는 더 이상 기다리지 않고 즉시 조합에 대해 동작한다. 파스 트리 예제에서 구문 A는 미리 보기 *가 보이는 즉시 1-3단계에서 Value로, 그리고 Products로 축소되며, 파스 트리의 해당 부분을 나중에 구성하기 위해 기다리지 않는다. A를 처리하는 방법에 대한 결정은 파서와 스캐너가 이미 본 내용만을 기반으로 하며, 훨씬 나중에 오른쪽에 나타나는 내용은 고려하지 않는다.

축소는 가장 최근에 파싱된 것들을 미리 보기 심볼 바로 왼쪽에 재구성한다. 따라서 이미 파싱된 항목 목록은 스택처럼 작동한다. 이 파스 스택은 오른쪽으로 커진다. 스택의 베이스 또는 바닥은 왼쪽에 있으며 가장 왼쪽의 가장 오래된 파싱 조각을 보유한다. 모든 축소 단계는 가장 오른쪽의 가장 최신 파싱 조각에만 작동한다. (이 누적 파스 스택은 하향식 파서가 사용하는 예측적이고 왼쪽으로 성장하는 파스 스택과는 매우 다르다.)

예제 A * 2 + 1에 대한 상향식 파스 단계

단계	파스 스택	미파싱됨	시프트/리듀스
0	비어있음	A * 2 + 1	시프트
1	id	* 2 + 1	Value → id
2	Value	* 2 + 1	Products → Value
3	Products	* 2 + 1	시프트
4	Products *	2 + 1	시프트
5	Products * int	+ 1	Value → int
6	Products * Value	+ 1	Products → Products * Value
7	Products	+ 1	Sums → Products
8	Sums	+ 1	시프트
9	Sums +	1	시프트
10	Sums + int	eof	Value → int
11	Sums + Value	eof	Products → Value
12	Sums + Products	eof	Sums → Sums + Products
13	Sums	eof	수락

6단계에서는 여러 부분을 가진 문법 규칙을 적용한다.

Products → Products * Value

이것은 파싱된 구문 "... Products * Value"를 담고 있는 스택 상단과 일치한다. 축소 단계는 이 규칙의 오른쪽 부분인 "Products * Value"의 인스턴스를 규칙의 왼쪽 부분 심볼, 여기서는 더 큰 Products로 대체한다. 파서가 완전한 파스 트리를 구축하면 내부 Products, *, Value에 대한 세 개의 트리가 Products에 대한 새로운 트리 루트에 의해 결합된다. 그렇지 않으면 내부 Products와 Value의 의미론적 세부 정보가 이후 컴파일러 단계로 출력되거나, 새로운 Products 심볼에 결합되어 저장된다.^[5]

예제 A * 2 + 1에 대한 LR 파스 단계

LR 파서에서 시프트 및 리듀스 결정은 단순히 단일 최상위 스택 심볼뿐만 아니라 이전에 파싱된 모든 것의 전체 스택을 기반으로 할 수 있다. 만약 영리하지 못한 방식으로 이루어진다면, 이는 더 긴 입력에 대해 점점 더 느려지는 매우 느린 파서를 초래할 수 있다. LR 파서는 모든 관련 왼쪽 컨텍스트 정보를 LR(0) 파서 상태라는 단일 숫자로 요약하여 일정한 속도로 이를 수행한다. 각 문법 및 LR 분석 방법에 대해 고정된(유한한) 수의 이러한 상태가 있다. 이미 파싱된 심볼을 저장하는 것 외에도 파스 스택은 해당 지점까지 도달한 상태 번호를 기억한다.

모든 파싱 단계에서 전체 입력 텍스트는 이전에 파싱된 구문 스택, 현재 미리 보기 심볼, 그리고 나머지 스캔되지 않은 텍스트로 나뉜다. 파서의 다음 동작은 현재 LR(0) 상태 번호(스택의 가장 오른쪽)와 미리 보기 심볼에 의해 결정된다. 아래 단계에서 모든 검은색 세부 정보는 다른 비-LR 시프트-리듀스 파서와 정확히 동일하다. LR 파서 스택은 스택의 왼쪽에 있는 검은색 구문과 다음에 예상되는 구문 가능성을 요약하는 보라색 상태 정보를 추가한다. LR 파서 사용자는 일반적으로 상태 정보를 무시할 수 있다. 이 상태들은 나중에 설명한다.

단계	파스 스택 _상태 [심볼_상태]*	미리 보기	스캔되지 않음	파서 동작	문법 규칙	다음 상태
0	₀	id	* 2 + 1	시프트		9
1	₀ id₉	*	2 + 1	리듀스	Value → id	7
2	₀ Value₇	*	2 + 1	리듀스	Products → Value	4
3	₀ Products₄	*	2 + 1	시프트		5
4	₀ Products₄ *₅	int	+ 1	시프트		8
5	₀ Products₄ *₅ int₈	+	1	리듀스	Value → int	6
6	₀ Products₄ *₅ Value₆	+	1	리듀스	Products → Products * Value	4
7	₀ Products₄	+	1	리듀스	Sums → Products	1
8	₀ Sums₁	+	1	시프트		2
9	₀ Sums₁ +₂	int	eof	시프트		8
10	₀ Sums₁ +₂ int₈	eof		리듀스	Value → int	7
11	₀ Sums₁ +₂ Value₇	eof		리듀스	Products → Value	3
12	₀ Sums₁ +₂ Products₃	eof		리듀스	Sums → Sums + Products	1
13	₀ Sums₁	eof		수락

초기 0단계에서 입력 스트림 "A * 2 + 1"은 다음과 같이 나뉜다.

파스 스택의 빈 섹션,
id 심볼로 스캔된 미리 보기 텍스트 "A", 그리고
나머지 스캔되지 않은 텍스트 "* 2 + 1".

파스 스택은 초기 상태 0만 포함한 채 시작한다. 상태 0이 미리 보기 id를 보면, 해당 id를 스택에 시프트하고 다음 입력 심볼 *를 스캔하여 상태 9로 진행해야 함을 안다.

4단계에서 총 입력 스트림 "A * 2 + 1"은 현재 다음과 같이 나뉜다.

Products와 * 두 개의 스택된 구문이 있는 파싱된 섹션 "A *",
int 심볼로 스캔된 미리 보기 텍스트 "2", 그리고
나머지 스캔되지 않은 텍스트 " + 1".

스택된 구문에 해당하는 상태는 0, 4, 5이다. 스택의 현재 가장 오른쪽 상태는 상태 5이다. 상태 5가 미리 보기 int를 보면, 해당 int를 스택에 자체 구문으로 시프트하고 다음 입력 심볼 +를 스캔하여 상태 8로 진행해야 함을 안다.

12단계에서 입력 스트림 전체가 사용되었지만 부분적으로만 정리되었다. 현재 상태는 3이다. 상태 3이 미리 보기 eof를 보면, 완료된 문법 규칙을 적용해야 함을 안다.

Sums → Sums + Products

스택의 가장 오른쪽 세 구문(Sums, +, Products)을 하나로 결합한다. 상태 3 자체는 다음 상태가 무엇이어야 하는지 모른다. 이는 축소되는 구문의 바로 왼쪽에 있는 상태 0으로 돌아가서 찾는다. 상태 0이 이 새로운 Sums의 완료된 인스턴스를 보면, 상태 1로 (다시) 진행한다. 오래된 상태를 참조하는 것이 바로 스택에 현재 상태만 유지하는 대신 모든 상태를 유지하는 이유이다.

예제 A * 2 + 1의 문법

LR 파서는 입력 언어의 구문을 패턴 집합으로 공식적으로 정의하는 문법으로부터 구성된다. 문법은 숫자의 크기 또는 전체 프로그램의 컨텍스트에서 이름과 그 정의의 일관된 사용과 같은 모든 언어 규칙을 다루지 않는다. LR 파서는 심볼의 로컬 패턴만을 다루는 문맥 자유 문법을 사용한다.

여기서 사용된 예제 문법은 자바 또는 C 언어의 작은 부분 집합이다.

r0: Goal → Sums eof

r1: Sums → Sums + Products

r2: Sums → Products

r3: Products → Products * Value

r4: Products → Value

r5: Value → int

r6: Value → id

문법의 종결자는 어휘 스캐너에 의해 입력 스트림에서 발견되는 다중 문자 심볼 또는 '토큰'이다. 여기에는 임의의 정수 상수에 대한 + * 및 int, 임의의 식별자 이름에 대한 id, 입력 파일의 끝에 대한 eof가 포함된다. 문법은 int 값이나 id 스펠링이 무엇인지, 공백이나 줄 바꿈에 대해서는 신경 쓰지 않는다. 문법은 이러한 종결자를 사용하지만 정의하지는 않는다. 이들은 항상 파스 트리의 리프 노드(하단 덤불 끝)이다.

Sums와 같이 대문자로 시작하는 용어는 비종결자이다. 이는 언어의 개념 또는 패턴에 대한 이름이다. 이들은 문법에 정의되어 있으며 입력 스트림 자체에서는 결코 발생하지 않는다. 이들은 항상 파스 트리의 내부 노드(하단 위)이다. 이들은 파서가 어떤 문법 규칙을 적용한 결과로만 발생한다. 일부 비종결자는 두 개 이상의 규칙으로 정의된다. 이들은 대체 패턴이다. 규칙은 자신을 참조할 수 있으며, 이를 재귀라고 한다. 이 문법은 재귀 규칙을 사용하여 반복되는 수학 연산자를 처리한다. 완전한 언어의 문법은 재귀 규칙을 사용하여 목록, 괄호 표현식 및 중첩된 문장을 처리한다.

어떤 주어진 컴퓨터 언어도 여러 다른 문법으로 기술될 수 있다. LR(1) 파서는 많은 일반적인 문법을 처리할 수 있지만 전부는 아니다. 일반적으로 LR(1) 파싱 및 생성기 도구의 제한에 맞게 문법을 수동으로 수정하는 것이 가능하다.

LR 파서의 문법은 그 자체로 모호하지 않거나 또는 우선순위 규칙에 의해 보강되어야 한다. 이는 언어의 주어진 유효한 예시에 문법을 적용하는 유일하게 올바른 방법이 단 하나의 의미를 가진 고유한 파스 트리를 생성하고 해당 예시에 대한 고유한 시프트/리듀스 동작 순서를 생성한다는 의미이다. LR 파싱은 단어의 상호작용에 의존하는 모호한 문법을 가진 인간 언어에는 유용한 기술이 아니다. 인간 언어는 일반화된 LR 파서, 얼리 파서 또는 CYK 알고리즘과 같이 한 번에 가능한 모든 파스 트리를 동시에 계산할 수 있는 파서에 의해 더 잘 처리된다.

예제 문법의 파스 테이블

대부분의 LR 파서는 테이블 기반이다. 파서의 프로그램 코드는 모든 문법과 언어에 대해 동일한 간단한 일반 루프이다. 문법과 그 구문적 함의에 대한 지식은 파스 테이블(또는 파싱 테이블)이라고 불리는 불변 데이터 테이블에 인코딩된다. 테이블의 항목은 파서 상태와 미리보기 심볼의 모든 유효한 조합에 대해 시프트할지 또는 리듀스할지(그리고 어떤 문법 규칙에 의해)를 보여준다. 파스 테이블은 또한 현재 상태와 다음 심볼이 주어졌을 때 다음 상태를 계산하는 방법도 알려준다.

파스 테이블은 문법보다 훨씬 크다. LR 테이블은 큰 문법에 대해 손으로 정확하게 계산하기 어렵다. 그래서 비손과 같은 파서 생성기 도구에 의해 문법에서 기계적으로 파생된다.^[6]

상태 및 파싱 테이블이 생성되는 방법에 따라 결과 파서는 SLR(Simple LR) 파서, LALR(Look-Ahead LR) 파서 또는 정규 LR 파서라고 불린다. LALR 파서는 SLR 파서보다 더 많은 문법을 처리한다. 정규 LR 파서는 훨씬 더 많은 문법을 처리하지만, 더 많은 상태와 훨씬 더 큰 테이블을 사용한다. 예제 문법은 SLR이다.

LR 파스 테이블은 2차원이다. 각 현재 LR(0) 파서 상태는 자체 행을 가진다. 각 가능한 다음 심볼은 자체 열을 가진다. 상태와 다음 심볼의 일부 조합은 유효한 입력 스트림에 대해 불가능하다. 이러한 빈 셀은 구문 오류 메시지를 유발한다.

테이블의 액션 왼쪽 절반은 미리보기 종결자 열을 가진다. 이 셀들은 다음 파서 액션이 시프트(상태 n으로)인지 또는 리듀스(문법 규칙 r_n에 의해)인지 결정한다.

테이블의 고투 오른쪽 절반은 비종결자 열을 가진다. 이 셀들은 어떤 리덕션의 좌변이 해당 심볼의 예상되는 새 인스턴스를 생성한 후 어떤 상태로 진행할지를 보여준다. 이는 시프트 액션과 비슷하지만 비종결자를 위한 것이다. 미리보기 종결자 심볼은 변경되지 않는다.

"현재 규칙"이라는 테이블 열은 파서 생성기에 의해 도출된 각 상태에 대한 의미와 구문 가능성을 문서화한다. 파싱 시 실제로 사용되는 테이블에는 포함되지 않는다. •(핑크 점) 마커는 파서가 현재 부분적으로 인식된 문법 규칙 내에서 어디에 있는지 보여준다. • 왼쪽에 있는 항목들은 파싱되었으며, 오른쪽에 있는 항목들은 곧 예상된다. 파서가 가능성을 단일 규칙으로 좁히지 않은 경우 상태는 여러 개의 현재 규칙을 가질 수 있다.

현재		미리 보기					LHS 고투
상태	현재 규칙	int	id	*	+	eof	Sums	Products	Value
0	Goal → • Sums eof	8	9				1	4	7
1	Goal → Sums • eof Sums → Sums • + Products				2	수락
2	Sums → Sums + • Products	8	9					3	7
3	Sums → Sums + Products • Products → Products • * Value			5	r1	r1
4	Sums → Products • Products → Products • * Value			5	r2	r2
5	Products → Products * • Value	8	9						6
6	Products → Products * Value •			r3	r3	r3
7	Products → Value •			r4	r4	r4
8	Value → int •			r5	r5	r5
9	Value → id •			r6	r6	r6

위의 상태 2에서 파서는 문법 규칙의 +를 방금 찾아서 시프트했다.

r1: Sums → Sums + • Products

다음 예상 구문은 Products이다. Products는 종결자 int 또는 id로 시작한다. 미리 보기가 이 둘 중 하나인 경우 파서는 이들을 시프트하고 각각 상태 8 또는 9로 진행한다. Products가 발견되면 파서는 합산 항목의 전체 목록을 축적하고 규칙 r0의 끝을 찾기 위해 상태 3으로 진행한다. Products는 비종결자 Value로도 시작할 수 있다. 다른 미리 보기 또는 비종결자의 경우 파서는 구문 오류를 알린다.

상태 3에서 파서는 방금 Products 구문을 찾았는데, 이는 두 가지 가능한 문법 규칙에서 비롯될 수 있다.

r1: Sums → Sums + Products •

r3: Products → Products • * Value

r1과 r3 사이의 선택은 이전 구문을 뒤로만 살펴서는 결정할 수 없다. 파서는 무엇을 해야 할지 알아내기 위해 미리보기 심볼을 확인해야 한다. 미리보기가 *이면 규칙 3에 있으므로 파서는 *를 시프트하고 상태 5로 진행한다. 미리보기가 eof이면 규칙 1과 규칙 0의 끝에 있으므로 파서는 완료된다.

위의 상태 9에서 비어있지 않고 오류가 아닌 모든 셀은 동일한 축소 r6에 대한 것이다. 일부 파서는 이러한 간단한 경우에 미리보기 심볼을 확인하지 않아 시간과 테이블 공간을 절약한다. 구문 오류는 약간 나중에, 일부 무해한 축소 후에 감지되지만, 다음 시프트 동작 또는 파서 결정 전에는 여전히 감지된다.

개별 테이블 셀에는 여러 대안 동작이 있어서는 안 된다. 그렇지 않으면 파서는 추측 및 백트래킹으로 비결정적이 될 수 있다. 문법이 LR(1)이 아닌 경우, 일부 셀에는 가능한 시프트 동작과 축소 동작 간의 시프트/축소 충돌 또는 여러 문법 규칙 간의 축소/축소 충돌이 발생한다. LR(k) 파서는 첫 번째를 넘어 추가 미리보기 심볼을 확인하여 이러한 충돌을 (가능한 경우) 해결한다.

LR 파서 루프

LR 파서는 시작 상태 0만 포함하는 거의 비어있는 파스 스택으로 시작하며, 미리보기는 입력 스트림의 첫 번째 스캔된 심볼을 담고 있다. 그런 다음 파서는 완료되거나 구문 오류에 갇힐 때까지 다음 루프 단계를 반복한다.

파스 스택의 최상위 상태는 특정 상태 s이고, 현재 미리보기는 특정 종결자 t이다. 미리보기 액션 테이블의 s행 t열에서 다음 파서 액션을 찾는다. 해당 액션은 시프트, 리듀스, 수락 또는 오류 중 하나이다.

시프트 n:

일치하는 종결자 t를 파스 스택에 시프트하고 다음 입력 심볼을 미리보기 버퍼로 스캔한다.

새로운 현재 상태로 다음 상태 n을 파스 스택에 푸시한다.

리듀스 r_m: 문법 규칙 r_m: Lhs → S₁ S₂ ... S_L 적용

일치하는 최상위 L개 심볼(및 파스 트리 및 관련 상태 번호)을 파스 스택에서 제거한다.

이는 Lhs 심볼의 인스턴스를 예상하던 이전 상태 p를 노출한다.

L개의 파스 트리를 Lhs라는 새 루트 심볼을 가진 하나의 파스 트리로 결합한다.

LHS 고투 테이블의 p행 Lhs 열에서 다음 상태 n을 찾는다.

Lhs 심볼과 트리를 파스 스택에 푸시한다.

새로운 현재 상태로 다음 상태 n을 파스 스택에 푸시한다.

미리보기와 입력 스트림은 변경되지 않는다.

수락: 미리보기 t는 eof 마커이다. 파싱 종료. 상태 스택에 시작 상태만 포함되어 있으면 성공을 보고한다. 그렇지 않으면 구문 오류를 보고한다.
오류: 구문 오류를 보고한다. 파서가 종료되거나 복구를 시도한다.

LR 파서 스택은 일반적으로 LR(0) 오토마톤 상태만 저장한다. 왜냐하면 문법 심볼은 이들로부터 파생될 수 있기 때문이다(오토마톤에서 어떤 상태로의 모든 입력 전이는 동일한 심볼로 표시되며, 이는 이 상태와 연관된 심볼이다). 게다가 파싱 결정을 내릴 때 상태가 가장 중요하므로 이러한 심볼은 거의 필요하지 않다.^[7]

LR 생성기 분석

이 문서의 이 섹션은 LR 파서 생성기 사용자 대부분은 건너뛸 수 있다.

LR 상태

예제 파스 테이블의 상태 2는 부분적으로 파싱된 규칙을 위한 것이다.

r1: Sums → Sums + • Products

이는 파서가 더 큰 Sums를 찾으면서 Sums를 본 다음 +를 보면서 여기에 어떻게 도달했는지 보여준다. • 마커는 규칙의 시작을 지나 전진했다. 또한 파서가 완전한 Products를 다음에 찾아 궁극적으로 규칙을 완료할 것으로 예상하는 방법도 보여준다. 그러나 해당 Products의 모든 부분을 파싱하는 방법에 대한 더 자세한 정보가 필요하다.

상태에 대한 부분적으로 파싱된 규칙을 "코어 LR(0) 항목"이라고 한다. 파서 생성기는 예상되는 Products를 구축하는 데 필요한 모든 가능한 다음 단계에 대한 추가 규칙 또는 항목을 추가한다.

r3: Products → • Products * Value

r4: Products → • Value

r5: Value → • int

r6: Value → • id

• 마커는 이러한 추가된 각 규칙의 시작 부분에 있다. 파서는 아직 이들 중 어떤 부분도 확인하고 파싱하지 않았다. 이러한 추가 항목을 코어 항목의 "폐쇄"라고 한다. • 바로 뒤에 오는 각 비종결자 심볼에 대해 생성기는 해당 심볼을 정의하는 규칙을 추가한다. 이는 더 많은 • 마커와 경우에 따라 다른 후행 심볼을 추가한다. 이 폐쇄 과정은 모든 후행 심볼이 확장될 때까지 계속된다. 상태 2의 후행 비종결자는 Products로 시작한다. Value는 폐쇄에 의해 추가된다. 후행 종결자는 int와 id이다.

커널 및 폐쇄 항목은 함께 현재 상태에서 미래 상태로 진행하고 구문을 완료하는 모든 가능한 합법적인 방법을 보여준다. 만약 후행 심볼이 단 하나의 항목에만 나타난다면, • 마커가 전진된 단 하나의 핵심 항목을 포함하는 다음 상태로 이어진다. 따라서 int는 핵심을 가진 다음 상태 8로 이어진다.

r5: Value → int •

만약 동일한 후행 심볼이 여러 항목에 나타난다면, 파서는 어떤 규칙이 여기에 적용되는지 아직 알 수 없다. 따라서 해당 심볼은 • 마커가 전진된 상태에서 모든 나머지 가능성을 보여주는 다음 상태로 이어진다. Products는 r1과 r3 모두에 나타난다. 따라서 Products는 핵심을 가진 다음 상태 3으로 이어진다.

r1: Sums → Sums + Products •

r3: Products → Products • * Value

쉽게 말하면, 파서가 단일 Products를 보았다면 작업이 완료되었거나, 곱해야 할 항목이 더 많을 수 있다는 의미이다. 모든 핵심 항목은 • 마커 앞에 동일한 심볼을 가진다. 이 상태로의 모든 전이는 항상 동일한 심볼로 이루어진다.

일부 전이는 이미 열거된 코어 및 상태로 이어진다. 다른 전이는 새로운 상태로 이어진다. 생성기는 문법의 목표 규칙으로 시작한다. 거기서부터 모든 필요한 상태가 발견될 때까지 알려진 상태와 전이를 계속 탐색한다.

이러한 상태들은 k=0, 즉 미리보기가 없음을 사용하기 때문에 "LR(0)" 상태라고 불린다. 입력 심볼의 확인은 심볼이 시프트될 때만 발생한다. 축소에 대한 미리보기 확인은 파스 테이블에 의해 별도로 수행되며, 열거된 상태 자체에 의해 수행되지 않는다.

유한 상태 기계

파스 테이블은 가능한 모든 LR(0) 상태와 그 전이를 기술한다. 이들은 유한 상태 기계 (FSM)를 형성한다. FSM은 스택을 사용하지 않고 간단한 중첩되지 않은 언어를 파싱하기 위한 간단한 엔진이다. 이 LR 애플리케이션에서 FSM의 수정된 "입력 언어"는 종결자와 비종결자 심볼을 모두 가지며, 전체 LR 파스의 부분적으로 파싱된 스택 스냅샷을 포함한다.

파스 단계 예시의 5단계를 다시 살펴보자.

< 단계	파스 스택 _상태 심볼 _상태 ...	미리 보기	스캔되지 않음
5	₀ Products₄ *₅ int₈	+	1

구문 분석 스택은 시작 상태 0에서 상태 4로, 그리고 5를 거쳐 현재 상태 8로 이어지는 일련의 상태 전환을 보여준다. 구문 분석 스택의 심볼은 이러한 전환에 대한 시프트 또는 고투 심볼이다. 이를 다른 방식으로 보면, 유한 상태 기계는 스트림 "Products * int + 1"을 (또 다른 스택을 사용하지 않고) 스캔하고 다음에 축소되어야 할 가장 왼쪽의 완전한 구문을 찾을 수 있다. 그리고 그것이 바로 그 역할이다!

원래의 파싱되지 않은 언어가 중첩과 재귀를 포함하고 분석기에 스택이 분명히 필요한데, 단순한 FSM이 어떻게 이를 수행할 수 있을까? 핵심은 스택 상단의 왼쪽에 있는 모든 것이 이미 완전히 축소되었다는 점이다. 이는 해당 구문에서 모든 루프와 중첩을 제거한다. FSM은 구문의 모든 오래된 시작 부분을 무시하고, 다음에 완료될 수 있는 가장 새로운 구문만 추적할 수 있다. LR 이론에서 이를 설명하는 모호한 이름은 "유효 접두사"이다.

미리보기 집합

상태와 전이는 파스 테이블의 시프트 동작과 고투 동작에 필요한 모든 정보를 제공한다. 생성기는 또한 각 리듀스 동작에 대한 예상 미리보기 집합을 계산해야 한다.

SLR 파서에서는 이러한 미리보기 집합이 개별 상태와 전이를 고려하지 않고 문법에서 직접 결정된다. 각 비종결자 S에 대해 SLR 생성기는 S의 어떤 발생 직후에 올 수 있는 모든 종결자 집합인 Follows(S)를 계산한다. 파스 테이블에서 S로의 각 축소는 Follow(S)를 해당 LR(1) 미리보기 집합으로 사용한다. 이러한 팔로우 집합은 LL 하향식 파서의 생성기에서도 사용된다. 팔로우 집합을 사용할 때 시프트/리듀스 또는 리듀스/리듀스 충돌이 없는 문법을 SLR 문법이라고 한다.

LALR 파서는 SLR 파서와 동일한 상태를 가지지만, 각 개별 상태에 대해 최소한으로 필요한 축소 미리보기를 계산하는 더 복잡하고 정확한 방법을 사용한다. 문법의 세부 사항에 따라 이는 SLR 파서 생성기가 계산한 팔로우 집합과 동일하거나 SLR 미리보기의 부분 집합이 될 수 있다. 일부 문법은 LALR 파서 생성기에는 적합하지만 SLR 파서 생성기에는 적합하지 않다. 이는 팔로우 집합을 사용할 때 문법에 가짜 시프트/리듀스 또는 리듀스/리듀스 충돌이 있지만 LALR 생성기가 계산한 정확한 집합을 사용할 때는 충돌이 없을 때 발생한다. 이때 해당 문법은 LALR(1)이지만 SLR은 아니다.

SLR 또는 LALR 파서는 중복 상태를 피한다. 그러나 이러한 최소화는 필수가 아니며, 때로는 불필요한 미리보기 충돌을 일으킬 수 있다. 정규 LR 파서는 중복된(또는 "분할된") 상태를 사용하여 비종결자 사용의 왼쪽 및 오른쪽 컨텍스트를 더 잘 기억한다. 문법에서 심볼 S의 각 발생은 자체 미리보기 집합으로 독립적으로 처리되어 축소 충돌을 해결하는 데 도움이 된다. 이는 몇몇 문법을 더 많이 처리한다. 불행히도, 문법의 모든 부분에 대해 수행되면 파스 테이블의 크기가 크게 확대된다. 이러한 상태 분할은 비종결자의 두 개 이상의 명명된 복사본을 만들어서 어떤 SLR 또는 LALR 파서에서도 수동으로, 그리고 선택적으로 수행할 수 있다. 정규 LR 생성기에는 충돌이 없지만 LALR 생성기에는 충돌이 있는 문법을 LR(1)이라고 하지만 LALR(1)도 SLR도 아니다.

SLR, LALR, 정규 LR 파서는 입력 스트림이 올바른 언어일 때 정확히 동일한 시프트 및 리듀스 결정을 내린다. 입력에 구문 오류가 있을 때 LALR 파서는 정규 LR 파서보다 오류를 감지하기 전에 몇 가지 추가 (무해한) 리듀스를 수행할 수 있다. 그리고 SLR 파서는 더 많은 리듀스를 수행할 수도 있다. 이는 SLR 및 LALR 파서가 해당 특정 상태에 대한 실제 최소 미리보기 심볼에 대한 관대한 상위 집합 근사를 사용하기 때문에 발생한다.

구문 오류 복구

LR 파서는 프로그램의 첫 번째 구문 오류에 대해 다소 도움이 되는 오류 메시지를 생성할 수 있다. 예상치 못한 잘못된 미리보기 심볼 대신 다음에 나타날 수 있었던 모든 종결자 심볼을 단순히 열거함으로써 말이다. 그러나 이는 파서가 나머지 입력 프로그램을 파싱하여 추가적인 독립적인 오류를 찾는 데 도움이 되지 않는다. 파서가 첫 번째 오류에서 잘못 복구하면 다른 모든 것을 잘못 파싱하여 쓸모없는 잘못된 오류 메시지의 연쇄를 생성할 가능성이 매우 높다.

yacc 및 Bison 파서 생성기에서 파서는 현재 문장을 포기하고 오류 주변의 파싱된 구문과 미리보기 토큰을 버리고 세미콜론이나 중괄호와 같은 신뢰할 수 있는 문장 수준 구분 기호에서 파싱을 재동기화하는 임시 메커니즘을 가지고 있다. 이는 파서와 컴파일러가 프로그램의 나머지 부분을 검토하는 데 종종 잘 작동한다.

많은 구문 코딩 오류는 간단한 오타 또는 사소한 심볼의 생략이다. 일부 LR 파서는 이러한 일반적인 경우를 감지하고 자동으로 복구하려고 시도한다. 파서는 오류 지점에서 가능한 모든 단일 심볼 삽입, 삭제 또는 대체를 열거한다. 컴파일러는 각 변경 사항으로 시험 파싱을 수행하여 제대로 작동하는지 확인한다. (이는 파서에서 일반적으로 필요 없는 파스 스택 및 입력 스트림의 스냅샷으로의 백트래킹을 필요로 한다.) 최상의 복구가 선택된다. 이는 매우 유용한 오류 메시지를 제공하고 파싱을 잘 재동기화한다. 그러나 이 복구는 입력 파일을 영구적으로 수정할 만큼 신뢰할 수 없다. 구문 오류 복구는 파스 테이블과 명시적 데이터 스택을 가진 파서(예: LR)에서 일관되게 수행하기 가장 쉽다.

LR 파서의 변형

LR 파서 생성기는 파서 상태와 미리보기 심볼의 각 조합에 대해 무엇이 발생해야 하는지 결정한다. 이러한 결정은 일반적으로 읽기 전용 데이터 테이블로 변환되어 문법 및 상태에 독립적인 일반 파서 루프를 구동한다. 그러나 이러한 결정을 활성 파서로 전환하는 다른 방법도 있다.

일부 LR 파서 생성기는 파스 테이블 대신 각 상태에 대해 별도로 맞춤형 프로그램 코드를 생성한다. 이 파서들은 테이블 기반 파서의 일반 파서 루프보다 몇 배 더 빠르게 실행될 수 있다. 가장 빠른 파서는 생성된 어셈블러 코드를 사용한다.

재귀 상승 파서 변형에서는 명시적 파스 스택 구조가 서브루틴 호출에 의해 사용되는 암시적 스택으로 대체된다. 리덕션은 여러 수준의 서브루틴 호출을 종료시키는데, 이는 대부분의 언어에서는 서투른 일이다. 따라서 재귀 상승 파서는 일반적으로 재귀 하향 파서보다 느리고 덜 명확하며 수동으로 수정하기 어렵다.

또 다른 변형은 파스 테이블을 프롤로그와 같은 비절차적 언어의 패턴 매칭 규칙으로 대체한다.

GLR 일반화된 LR 파서는 LR 상향식 기술을 사용하여 입력 텍스트의 가능한 모든 파싱을 찾으며, 단 하나의 올바른 파싱만을 찾지 않는다. 이는 인간 언어에 사용되는 것과 같은 모호한 문법에 필수적이다. 여러 유효한 파스 트리는 백트래킹 없이 동시에 계산된다. GLR은 충돌 없는 LALR(1) 문법으로 쉽게 기술할 수 없는 컴퓨터 언어에 유용할 때가 있다.

LC 좌상향 파서는 LR 상향식 기술을 사용하여 대체 문법 규칙의 왼쪽 끝을 인식한다. 대안이 단일 가능한 규칙으로 좁혀지면 파서는 해당 규칙의 나머지를 파싱하기 위해 하향식 LL(1) 기술로 전환한다. LC 파서는 LALR 파서보다 파스 테이블이 작고 오류 진단이 더 좋다. 결정론적 LC 파서에 대한 널리 사용되는 생성기는 없다. 다중 파싱 LC 파서는 매우 큰 문법을 가진 인간 언어에 유용하다.

이론

LR 파서는 도널드 커누스가 1965년에 우선순위 파서의 효율적인 일반화로 발명했다. 커누스는 LR 파서가 최악의 경우에도 효율적일 수 있는 가장 일반적인 목적의 파서임을 증명했다.

"LR(k) 문법은 문자열의 길이에 비례하는 실행 시간으로 효율적으로 파싱될 수 있다."^[8]

모든 k ≥ 1에 대해, "언어가 LR(k) 문법에 의해 생성될 수 있는 경우는 결정론적 [문맥 자유]인 경우에 한하며, 이는 LR(1) 문법에 의해 생성될 수 있는 경우와 동일하다."^[9]

다른 말로 하면, 효율적인 단일 패스 파서가 가능할 만큼 합리적인 언어라면 LR(k) 문법으로 기술할 수 있었다. 그리고 그 문법은 항상 기계적으로 동등한 (그러나 더 큰) LR(1) 문법으로 변환될 수 있었다. 따라서 이론적으로 LR(1) 파싱 방법은 모든 합리적인 언어를 처리할 수 있을 만큼 강력했다. 실제로 많은 프로그래밍 언어의 자연스러운 문법은 LR(1)에 가깝다.

커누스가 기술한 정규 LR 파서는 너무 많은 상태와 방대한 파스 테이블을 가지고 있어 그 시대의 제한된 컴퓨터 메모리로는 비실용적으로 컸다. LR 파싱은 프랭크 디리머가 훨씬 적은 상태를 가진 SLR 및 LALR 파서를 발명하면서 실용적이 되었다.^[10]^[11]

LR 이론과 LR 파서가 문법에서 어떻게 파생되는지에 대한 자세한 내용은 "Parsing, Translation, and Compiling, Volume 1 (Aho and Ullman)"을 참조하라.^[7]^[2]

얼리 파서는 LR 파서의 기법과 • 표기법을 인간 언어와 같은 모호한 문법에 대한 가능한 모든 파싱을 생성하는 작업에 적용한다.

LR(k) 문법은 모든 k≥1에 대해 동일한 생성 능력을 가지지만, LR(0) 문법의 경우는 약간 다르다. 언어 L은 L에 있는 어떤 단어도 L에 있는 다른 단어의 고유 접두사가 아닌 경우 접두사 속성을 가진다고 한다.^[12] 언어 L이 LR(0) 문법을 가지는 것은 L이 접두사 속성을 가진 결정적 문맥 자유 언어인 경우에 한한다.^[13] 결과적으로 언어 L이 결정적 문맥 자유 언어인 것은 L$이 LR(0) 문법을 가지는 경우에 한하며, 여기서 "$"는 L의 알파벳의 심볼이 아니다.^[14]

추가 예제 1 + 1

이 LR 파싱 예시는 목표 심볼 E를 가진 다음 작은 문법을 사용한다.

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

다음 입력을 파싱한다.

1 + 1

액션 및 고투 테이블

이 문법에 대한 두 LR(0) 파싱 테이블은 다음과 같다.

상태	액션					고투
	*	+	0	1	$	E	B
0			s1	s2		3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2			7
6			s1	s2			8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

액션 테이블은 파서의 상태와 종결자(입력 스트림의 끝을 나타내는 특수 종결자 $ 포함)로 색인화되며 세 가지 유형의 액션을 포함한다.

시프트(shift): "sn"으로 표시되며 다음 상태가 n임을 나타낸다.
리듀스(reduce): "rm"으로 표시되며 문법 규칙 m으로 축소를 수행해야 함을 나타낸다.
수락(accept): "acc"로 표시되며 파서가 입력 스트림의 문자열을 수락함을 나타낸다.

고투 테이블은 파서의 상태와 비종결자로 인덱싱되며 특정 비종결자를 인식한 경우 파서의 다음 상태가 무엇인지를 단순히 나타낸다. 이 테이블은 모든 축소 후에 다음 상태를 알아내는 데 중요하다. 축소 후에는 스택의 맨 위(즉, 현재 상태)와 축소된 규칙의 LHS(즉, 비종결자)에 대한 고투 테이블 항목을 찾아 다음 상태를 찾는다.

파싱 단계

아래 표는 과정의 각 단계를 보여준다. 여기서 상태는 스택의 맨 위(가장 오른쪽 요소) 요소를 나타내며, 다음 액션은 위 액션 테이블을 참조하여 결정된다. 입력 스트림의 끝을 나타내기 위해 입력 문자열에 $가 추가된다.

상태	입력 스트림	출력 스트림	스택	다음 액션
0	1 + 1 $		[0]	시프트 2
2	+ 1 $		[0,2]	리듀스 5
4	+ 1 $	5	[0,4]	리듀스 3
3	+ 1 $	5,3	[0,3]	시프트 6
6	1 $	5,3	[0,3,6]	시프트 2
2	$	5,3	[0,3,6,2]	리듀스 5
8	$	5,3,5	[0,3,6,8]	리듀스 2
3	$	5,3,5,2	[0,3]	수락

자세한 설명

파서는 초기 상태('0')만 포함된 스택으로 시작한다.

[0]

파서가 입력 문자열에서 처음 보는 심볼은 '1'이다. 다음 액션(시프트, 리듀스, 수락 또는 오류)을 찾기 위해 액션 테이블은 현재 상태(스택 맨 위에 있는 것)인 0과 현재 입력 심볼인 '1'로 인덱싱된다. 액션 테이블은 상태 2로 시프트하도록 지정하므로 상태 2가 스택에 푸시된다(다시 말하지만, 모든 상태 정보는 스택에 있으므로 "상태 2로 시프트"하는 것은 2를 스택에 푸시하는 것과 동일하다). 결과 스택은 다음과 같다.

[0 '1' 2]

스택의 맨 위는 2이다. 심볼(예: '1', B)을 설명하기 위해 다음 상태로의 전환을 유발한 원인이 표시되지만, 엄밀히 말하면 스택의 일부는 아니다.

상태 2에서 액션 테이블은 문법 규칙 5를 사용하여 축소하라고 한다(파서가 입력 스트림에서 어떤 터미널을 보든지 상관없이). 이는 파서가 규칙 5의 오른쪽 부분을 방금 인식했음을 의미한다. 이 경우 파서는 출력 스트림에 5를 쓰고, 스택에서 한 상태를 팝하고(규칙의 오른쪽 부분에 심볼 하나가 있기 때문), 상태 0과 B에 대한 고투 테이블의 셀에서 새 상태, 즉 상태 4를 푸시한다. 결과 스택은 다음과 같다.

[0 B 4]

하지만 상태 4에서 액션 테이블은 파서가 이제 규칙 3으로 축소해야 한다고 말한다. 그래서 출력 스트림에 3을 쓰고, 스택에서 상태 하나를 팝하고, 상태 0과 E에 대한 고투 테이블에서 새 상태인 상태 3을 찾는다. 결과 스택은 다음과 같다.

[0 E 3]

파서가 다음에 보는 종결자는 '+'이고, 액션 테이블에 따르면 상태 6으로 시프트해야 한다.

[0 E 3 '+' 6]

결과 스택은 비종결자 E 뒤에 종결자 '+'를 읽은 유한 상태 기계의 기록으로 해석될 수 있다. 이 오토마톤의 전이 테이블은 액션 테이블의 시프트 액션과 고투 테이블의 고투 액션으로 정의된다.

다음 종결자는 '1'이며, 이는 파서가 시프트를 수행하여 상태 2로 이동함을 의미한다.

[0 E 3 '+' 6 '1' 2]

이전의 '1'과 마찬가지로 이 '1'도 B로 축소되어 다음 스택을 제공한다.

[0 E 3 '+' 6 B 8]

스택은 비종결자 E를 읽은 후 '+'와 비종결자 B를 읽은 유한 오토마톤의 상태 목록에 해당한다. 상태 8에서 파서는 항상 규칙 2로 축소를 수행한다. 스택의 최상위 3개 상태는 규칙 2의 오른쪽에 있는 3개 심볼에 해당한다. 이번에는 스택에서 3개 요소를 팝하고(규칙의 오른쪽에 3개 심볼이 있기 때문) E와 0에 대한 고투 상태를 찾아 상태 3을 다시 스택에 푸시한다.

[0 E 3]

마지막으로, 파서는 입력 스트림에서 '$'(입력 끝 심볼)를 읽는데, 이는 액션 테이블(현재 상태는 3)에 따르면 파서가 입력 문자열을 수락한다는 것을 의미한다. 그 때 출력 스트림에 기록된 규칙 번호는 [5, 3, 5, 2]가 되며, 이는 "1 + 1" 문자열의 역 가장 오른쪽 파생이다.

LR(0) 파싱 테이블 구축

아이템

이러한 파싱 테이블의 구성은 LR(0) 아이템(여기서는 간단히 아이템이라고 함) 개념을 기반으로 한다. 이는 오른쪽 부분에 특수 점이 추가된 문법 규칙이다. 예를 들어, E → E + B 규칙에는 다음과 같은 4가지 해당 아이템이 있다.

E → • E + B

E → E • + B

E → E + • B

E → E + B •

A → ε 형태의 규칙은 단일 아이템 A → •만을 가진다. 예를 들어, 아이템 E → E • + B는 파서가 입력 스트림에서 E에 해당하는 문자열을 인식했으며 이제 '+' 뒤에 B에 해당하는 다른 문자열을 읽을 것으로 예상함을 나타낸다.

아이템 집합

파서의 상태를 단일 항목으로 특징짓는 것은 일반적으로 불가능하다. 왜냐하면 파서가 축소를 위해 어떤 규칙을 사용할지 미리 알지 못할 수 있기 때문이다. 예를 들어, E → E * B 규칙도 있다면, E에 해당하는 문자열이 읽힌 후에는 E → E • + B와 E → E • * B 항목이 모두 적용된다. 따라서 이 경우 { E → E • + B, E → E • * B }와 같은 항목 집합으로 파서의 상태를 특징짓는 것이 편리하다.

비종결자 확장을 통한 아이템 집합 확장

E → E + • B와 같이 비종결자 앞에 점이 있는 항목은 파서가 다음에 비종결자 B를 파싱할 것으로 예상함을 나타낸다. 항목 집합이 파서가 파싱 중일 수 있는 모든 가능한 규칙을 포함하도록 하려면, B 자체를 어떻게 파싱할지를 설명하는 모든 항목을 포함해야 한다. 이는 B → 1 및 B → 0과 같은 규칙이 있는 경우 항목 집합에 B → • 1 및 B → • 0 항목도 포함되어야 함을 의미한다. 일반적으로 다음과 같이 공식화할 수 있다.

항목 집합에 A → v • Bw 형태의 항목이 있고 문법에 B → w' 형태의 규칙이 있다면, B → • w' 항목도 항목 집합에 포함되어야 한다.

아이템 집합의 폐쇄

따라서 점 앞에 있는 모든 비종결자가 고려될 때까지 모든 적절한 항목을 재귀적으로 추가하여 모든 항목 집합을 확장할 수 있다. 최소 확장을 항목 집합의 폐쇄라고 하며 I가 항목 집합일 때 clos(I)로 쓴다. 실제로 시작 상태에서 도달할 수 있는 항목 집합만 테이블에 포함되지만, 이 폐쇄된 항목 집합이 파서의 상태로 간주된다.

확장 문법

다른 상태 간의 전이가 결정되기 전에 문법은 추가 규칙으로 확장된다.

(0) S → E eof

여기서 S는 새로운 시작 심볼이고 E는 이전 시작 심볼이다. 파서는 입력 문자열 전체를 수락했을 때 정확히 이 규칙을 축소에 사용할 것이다.

이 예제에서는 위와 동일한 문법이 다음과 같이 확장된다.

(0) S → E eof

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

이 확장된 문법에 대해 항목 집합과 그들 사이의 전이가 결정될 것이다.

테이블 구축

도달 가능한 항목 집합과 그들 사이의 전이 찾기

테이블을 구축하는 첫 번째 단계는 폐쇄된 항목 집합들 간의 전이를 결정하는 것이다. 이 전이들은 우리가 종결자와 비종결자를 모두 읽을 수 있는 유한 오토마톤을 고려하는 것처럼 결정될 것이다. 이 오토마톤의 시작 상태는 항상 추가된 규칙의 첫 번째 항목의 폐쇄이다. S → • E eof:

항목 집합 0

S → • E eof

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

항목 앞의 굵은 "+"는 폐쇄를 위해 추가된 항목을 나타낸다(수학적 '+' 연산자, 즉 종결자와 혼동하지 말 것). "+"가 없는 원래 항목을 항목 집합의 커널이라고 한다.

시작 상태(S0)에서 시작하여 이 상태에서 도달할 수 있는 모든 상태가 이제 결정된다. 항목 집합의 가능한 전이는 점 뒤에 오는 심볼(종결자와 비종결자)을 확인함으로써 찾을 수 있다. 항목 집합 0의 경우 해당 심볼은 종결자 '0'과 '1' 그리고 비종결자 E와 B이다. 각 심볼 ${\textstyle x\in \{0,1,E,B\}}$ 가 이끄는 항목 집합을 찾기 위해 각 심볼에 대해 다음 절차를 따른다.

현재 항목 집합에서 관심 심볼 x 앞에 점이 있는 모든 항목의 부분집합 S를 가져온다.
S의 각 항목에 대해 점을 x의 오른쪽으로 이동한다.
결과 항목 집합을 닫는다.

종결자 '0'(즉, x = '0'인 경우)에 대해 결과는 다음과 같다.

항목 집합 1

B → 0 •

그리고 종결자 '1'(즉, x = '1'인 경우)에 대해 결과는 다음과 같다.

항목 집합 2

B → 1 •

그리고 비종결자 E(즉, x = E인 경우)에 대해 결과는 다음과 같다.

항목 집합 3

S → E • eof

E → E • * B

E → E • + B

그리고 비종결자 B(즉, x = B인 경우)에 대해 결과는 다음과 같다.

항목 집합 4

E → B •

클로저가 항상 새로운 항목을 추가하는 것은 아니다. 예를 들어 위의 새로운 집합들에는 점 뒤에 비종결자가 없다.

위의 절차는 더 이상 새로운 항목 집합이 발견되지 않을 때까지 계속된다. 항목 집합 1, 2, 4에는 점이 어떤 심볼 앞에도 없으므로 전이가 없을 것이다. 하지만 항목 집합 3에는 종결자 '*'와 '+' 앞에 점이 있다. 심볼 ${\textstyle x={\texttt {*}}}$ 에 대해 전이는 다음과 같다.

항목 집합 5

E → E * • B

+ B → • 0

+ B → • 1

그리고 ${\textstyle x={\texttt {+}}}$ 에 대해 전이는 다음과 같다.

항목 집합 6

E → E + • B

+ B → • 0

+ B → • 1

이제 세 번째 반복이 시작된다.

항목 집합 5의 경우 종결자 '0'과 '1', 그리고 비종결자 B를 고려해야 하지만, 종결자에 대해 생성되는 폐쇄된 항목 집합은 이미 발견된 항목 집합 1과 2와 각각 동일하다. 비종결자 B의 경우 전이는 다음과 같다.

항목 집합 7

E → E * B •

항목 집합 6의 경우 종결자 '0'과 '1', 비종결자 B를 고려해야 하지만, 이전과 마찬가지로 종결자에 대해 생성되는 항목 집합은 이미 발견된 항목 집합 1과 2와 동일하다. 비종결자 B의 경우 전이는 다음과 같다.

항목 집합 8

E → E + B •

이 최종 항목 집합 7과 8에는 점 너머의 심볼이 없으므로 더 이상 새로운 항목 집합이 추가되지 않아 항목 생성 절차가 완료된다. 항목 집합을 상태로 하는 유한 오토마톤은 아래에 나와 있다.

이제 오토마톤의 전이 테이블은 다음과 같다.

항목 집합	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

액션 및 고투 테이블 구축

이 테이블과 발견된 항목 집합으로부터 액션 및 고투 테이블은 다음과 같이 구축된다.

비종결자 열은 고투 테이블로 복사된다.
종결자 열은 시프트 액션으로 액션 테이블로 복사된다.
액션 테이블에 '$'(입력 끝)에 대한 추가 열이 추가된다. S → w • eof 형태의 항목을 포함하는 각 항목 집합에 대해 '$' 열에 acc 액션이 추가된다.
항목 집합 i에 A → w • 형태의 항목이 있고 A → w가 m > 0인 규칙 m이라면, 액션 테이블의 상태 i에 대한 행은 완전히 리듀스 액션 rm으로 채워진다.

독자는 이러한 단계들이 이전에 제시된 액션 및 고투 테이블을 생성하는지 확인할 수 있다.

LR(0) 대 SLR 및 LALR 파싱에 대한 참고 사항

위 절차의 4단계만 리듀스 액션을 생성하므로, 모든 리듀스 액션은 전체 테이블 행을 차지해야 하며, 입력 스트림의 다음 심볼에 관계없이 축소가 발생하게 한다. 이것이 바로 이들이 LR(0) 파스 테이블인 이유이다. 즉, 어떤 축소를 수행할지 결정하기 전에 미리보기를 전혀 하지 않는다(즉, 0개의 심볼을 미리 본다). 축소의 모호성을 해소하기 위해 미리보기가 필요한 문법은 다른 열에 다른 축소 액션을 포함하는 파스 테이블 행을 필요로 하며, 위 절차는 그러한 행을 생성할 수 없다.

LR(0) 테이블 구축 절차의 개선 사항(예: SLR 및 LALR)은 전체 행을 차지하지 않는 리듀스 액션을 구축할 수 있다. 따라서 이들은 LR(0) 파서보다 더 많은 문법을 파싱할 수 있다.

구축된 테이블의 충돌

오토마톤은 결정론적임을 보장하는 방식으로 구축된다. 그러나 액션 테이블에 축소 액션이 추가될 때, 동일한 셀이 축소 액션과 시프트 액션(시프트-축소 충돌) 또는 두 개의 다른 축소 액션(축소-축소 충돌)으로 채워지는 경우가 발생할 수 있다. 그러나 이 경우 문법이 LR(0) 문법이 아님을 보여줄 수 있다. 시프트-축소 충돌의 고전적인 실제 예는 매달린 else 문제이다.

시프트-리듀스 충돌이 있는 비-LR(0) 문법의 작은 예시는 다음과 같다.

(1) E → 1 E

(2) E → 1

발견된 항목 집합 중 하나는 다음과 같다.

항목 집합 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

이 항목 집합에는 시프트-리듀스 충돌이 있다. 위 규칙에 따라 액션 테이블을 구축할 때 [항목 집합 1, 종결자 '1'] 셀에는 s1(상태 1로 시프트)과 r2(문법 규칙 2로 축소)가 모두 포함된다.

축소-축소 충돌이 있는 비-LR(0) 문법의 작은 예시는 다음과 같다.

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

이 경우 다음 항목 집합이 얻어진다.

항목 집합 1

A → 1 •

B → 1 •

이 항목 집합에는 축소-축소 충돌이 있다. 이 항목 집합의 액션 테이블 셀에 규칙 3에 대한 축소 액션과 규칙 4에 대한 축소 액션이 모두 있기 때문이다.

위의 두 예는 파서가 비종결자 A의 팔로우 집합(LL 파서 참조)을 사용하여 A의 규칙 중 하나를 축소에 사용할지 여부를 결정하게 함으로써 해결할 수 있다. 파서는 입력 스트림의 다음 심볼이 A의 팔로우 집합에 있는 경우에만 A → w 규칙을 축소에 사용할 것이다. 이 솔루션은 소위 단순 LR 파서를 낳는다.

같이 보기

각주

↑ ^가 ^나 ^다 Knuth, D. E. (July 1965). 《On the translation of languages from left to right》. 《Information and Control》 8. 607–639쪽. doi:10.1016/S0019-9958(65)90426-2.
↑ ^가 ^나 Aho, Alfred V.; Ullman, Jeffrey D. (1972). 《The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.)》 Repr.판. 잉글우드 클리프스 (뉴저지주): 프렌티스 홀. ISBN 978-0139145568.
↑ Language theoretic comparison of LL and LR grammars
↑ Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon, 모건 카우프만 2011.
↑ Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.
↑ Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.
↑ ^가 ^나 Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.
↑ Knuth (1965), p.638
↑ Knuth (1965), p.635. Knuth didn't mention the restriction k ≥ 1 there, but it is required by his theorems he referred to, viz. on p. 629 and p. 630. Similarly, the restriction to 문맥 자유 언어s is tacitly understood from the context.
↑ Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.
↑ Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.
↑ Hopcroft, John E.; Ullman, Jeffrey D. (1979). 《Introduction to Automata Theory, Languages, and Computation》. 애디슨 웨슬리. ISBN 0-201-02988-X. Here: Exercise 5.8, p.121.
↑ Hopcroft, Ullman (1979), Theorem 10.12, p.260
↑ Hopcroft, Ullman (1979), Corollary p.260

더 읽어보기

Chapman, Nigel P., LR Parsing: Theory and Practice, 케임브리지 대학교 출판부, 1987. ISBN 0-521-30413-X
Pager, D., A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977)
"Compiler Construction: Principles and Practice" by Kenneth C. Louden. ISBN 0-534-939724

외부 링크

dickgrune.com, Parsing Techniques - A Practical Guide 1st Ed. 웹페이지에는 다운로드 가능한 pdf 파일이 포함되어 있다.
Parsing Simulator 이 시뮬레이터는 LR 파싱 테이블을 생성하고 책의 연습 문제를 해결하는 데 사용된다.
GNU Bison이 생성한 LALR(1) 파서의 내부 - 구현 문제
LR 파싱에 대한 강의 노트
LALR 파서의 시프트-리듀스 및 리듀스-리듀스 충돌
LR 파서 예제
실용적인 LR(k) 파서 구축
Honalee LR(k) 알고리즘

[Knuth_1965-1] 가 ^나 ^다 Knuth, D. E. (July 1965). 《On the translation of languages from left to right》. 《Information and Control》 8. 607–639쪽. doi:10.1016/S0019-9958(65)90426-2.

[AhoUllman_1972-2] 가 ^나 Aho, Alfred V.; Ullman, Jeffrey D. (1972). 《The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.)》 Repr.판. 잉글우드 클리프스 (뉴저지주): 프렌티스 홀. ISBN 978-0139145568.

[3] Language theoretic comparison of LL and LR grammars

[4] Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon, 모건 카우프만 2011.

[5] Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.

[6] Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.

[Compilers_2006-7] 가 ^나 Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.

[8] Knuth (1965), p.638

[9] Knuth (1965), p.635. Knuth didn't mention the restriction k ≥ 1 there, but it is required by his theorems he referred to, viz. on p. 629 and p. 630. Similarly, the restriction to 문맥 자유 언어s is tacitly understood from the context.

[10] Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.

[11] Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.

[12] Hopcroft, John E.; Ullman, Jeffrey D. (1979). 《Introduction to Automata Theory, Languages, and Computation》. 애디슨 웨슬리. ISBN 0-201-02988-X. Here: Exercise 5.8, p.121.

[13] Hopcroft, Ullman (1979), Theorem 10.12, p.260

[14] Hopcroft, Ullman (1979), Corollary p.260

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]