LR 파서

컴퓨터 과학에서, **LR 파서**(LR parser)는 선형 시간에 결정론적 문맥 자유 언어를 분석하는 상향식 파서의 한 종류이다.doi-access = free 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 범위로 왼쪽에서 오른쪽으로 번역 가능"을 의미한다고 제안했다. LR 파서는 결정론적이다. 즉, 추측이나 퇴각검색 없이 선형 시간 내에 단일의 올바른 파싱 결과를 생성한다. 이는 컴퓨터 언어에 이상적이지만, LR 파서는 더 유연하지만 필연적으로 느린 방법을 필요로 하는 인간 언어에는 적합하지 않다. 임의의 문맥 자유 언어를 파싱할 수 있는 일부 방법(예: 콕-영거-카사미, 얼리, GLR)은 최악의 경우 O(n3) 시간 성능을 보인다. 잘못 추측하면 퇴각검색을 하거나 여러 파싱 결과를 산출하는 다른 방법은 지수 시간을 소요할 수도 있다.url=https://archive.org/details/theoryofparsingt00ahoa 위의 **L**, **R**, **k** 속성은 우선순위 파서를 포함한 모든 시프트-리듀스 파서가 공유한다. 그러나 관례적으로 LR이라는 이름은 도널드 커누스가 발명한 파싱 방식을 의미하며, 초기에는 덜 강력했던 우선순위 방식(예: 연산자 우선순위 파서)은 제외한다. LR 파서는 우선순위 파서나 하향식 LL 파싱보다 더 넓은 범위의 언어와 문법을 처리할 수 있다.Language theoretic comparison of LL and LR grammars 이는 LR 파서가 발견한 내용을 확정하기 전에 어떤 문법 패턴의 전체 인스턴스를 볼 때까지 기다리기 때문이다. LL 파서는 그 패턴의 가장 왼쪽 입력 심볼만 보았을 때 훨씬 더 일찍 자신이 무엇을 보고 있는지 결정하거나 추측해야 한다.
# 개요

## 예제 A * 2 + 1에 대한 상향식 파스 트리
LR 파서는 입력 텍스트를 한 번에 한 방향으로 스캔하고 구문 분석한다. 파서는 파스 트리를 추측이나 백트래킹 없이 점진적으로, 상향식으로, 왼쪽에서 오른쪽으로 구축한다. 이 과정의 모든 지점에서 파서는 이미 구문 분석된 입력 텍스트의 서브트리 또는 구문 목록을 축적했다. 이 서브트리들은 파서가 아직 서브트리들을 결합할 구문 패턴의 오른쪽 끝에 도달하지 않았기 때문에 아직 함께 결합되지 않았다. 예제 파싱의 6단계에서는 "A * 2"만 불완전하게 파싱되었다. 파스 트리의 음영 처리된 왼쪽 아래 모서리만 존재한다. 7번 이상 번호가 매겨진 파스 트리 노드는 아직 존재하지 않는다. 노드 3, 4, 6은 각각 변수 A, 연산자 *, 숫자 2에 대한 고립된 서브트리의 루트이다. 이 세 개의 루트 노드는 파스 스택에 임시로 보관된다. 입력 스트림의 나머지 구문 분석되지 않은 부분은 "+ 1"이다.
## 시프트 및 리듀스 동작
다른 시프트-리듀스 파서와 마찬가지로 LR 파서는 시프트 단계와 리듀스 단계를 조합하여 작동한다. * **시프트** 단계는 입력 스트림에서 한 심볼씩 전진한다. 이 시프트된 심볼은 새로운 단일 노드 파스 트리가 된다. * **리듀스** 단계는 완료된 문법 규칙을 최근의 파스 트리 중 일부에 적용하여 새로운 루트 심볼을 가진 하나의 트리로 결합한다. 입력에 구문 오류가 없으면, 파서는 모든 입력이 사용되고 모든 파스 트리가 전체 유효 입력을 나타내는 단일 트리로 축소될 때까지 이러한 단계를 계속한다. LR 파서는 언제 리듀스할지, 그리고 비슷한 끝을 가진 규칙들 중에서 어떻게 선택할지 결정하는 방식에서 다른 시프트-리듀스 파서와 다르다. 그러나 최종 결정과 시프트 또는 리듀스 단계의 순서는 동일하다. LR 파서의 효율성은 결정론적이라는 점에서 비롯된다. 추측을 피하기 위해 LR 파서는 이전에 스캔한 심볼을 어떻게 처리할지 결정하기 전에 종종 다음 스캔된 심볼을 미리 본다(오른쪽으로). 어휘 스캐너는 파서보다 하나 이상의 심볼을 앞서 작업한다. **미리 보기** 심볼은 파싱 결정에 대한 '오른쪽 컨텍스트'이다. Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon, 모건 카우프만 2011.
## 상향식 파스 스택
6단계에서의 상향식 파서 다른 시프트-리듀스 파서와 마찬가지로 LR 파서는 어떤 구성 요소의 모든 부분을 스캔하고 파싱할 때까지 느긋하게 기다린 다음, 결합된 구성 요소가 무엇인지 확정한다. 파서는 더 이상 기다리지 않고 즉시 조합에 대해 동작한다. 파스 트리 예제에서 구문 A는 미리 보기 *가 보이는 즉시 1-3단계에서 Value로, 그리고 Products로 축소되며, 파스 트리의 해당 부분을 나중에 구성하기 위해 기다리지 않는다. A를 처리하는 방법에 대한 결정은 파서와 스캐너가 이미 본 내용만을 기반으로 하며, 훨씬 나중에 오른쪽에 나타나는 내용은 고려하지 않는다. 축소는 가장 최근에 파싱된 것들을 미리 보기 심볼 바로 왼쪽에 재구성한다. 따라서 이미 파싱된 항목 목록은 스택처럼 작동한다. 이 **파스 스택**은 오른쪽으로 커진다. 스택의 베이스 또는 바닥은 왼쪽에 있으며 가장 왼쪽의 가장 오래된 파싱 조각을 보유한다. 모든 축소 단계는 가장 오른쪽의 가장 최신 파싱 조각에만 작동한다. (이 누적 파스 스택은 하향식 파서가 사용하는 예측적이고 왼쪽으로 성장하는 파스 스택과는 매우 다르다.)
## 예제 A * 2 + 1에 대한 상향식 파스 단계
{| class="wikitable" |- ! 단계 !! 파스 스택 !! 미파싱됨 !! 시프트/리듀스 |- | 0 || 비어있음 || align="right" | A * 2 + 1 || 시프트 |- | 1 || id || align="right" | * 2 + 1 || Value → id |- | 2 || Value || align="right" | * 2 + 1 || Products → Value |- | 3 || Products || align="right" | * 2 + 1 || 시프트 |- | 4 || Products * || align="right" | 2 + 1 || 시프트 |- | 5 || Products * int || align="right" | + 1 || Value → int |- | 6 || Products * Value || align="right" | + 1 || Products → Products * Value |- | 7 || Products || align="right" | + 1 || Sums → Products |- | 8 || Sums || align="right" | + 1 || 시프트 |- | 9 || Sums + || align="right" | 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 심볼에 결합되어 저장된다. Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.
## 예제 A * 2 + 1에 대한 LR 파스 단계
LR 파서에서 시프트 및 리듀스 결정은 단순히 단일 최상위 스택 심볼뿐만 아니라 이전에 파싱된 모든 것의 전체 스택을 기반으로 할 수 있다. 만약 영리하지 못한 방식으로 이루어진다면, 이는 더 긴 입력에 대해 점점 더 느려지는 매우 느린 파서를 초래할 수 있다. LR 파서는 모든 관련 왼쪽 컨텍스트 정보를 LR(0) **파서 상태**라는 단일 숫자로 요약하여 일정한 속도로 이를 수행한다. 각 문법 및 LR 분석 방법에 대해 고정된(유한한) 수의 이러한 상태가 있다. 이미 파싱된 심볼을 저장하는 것 외에도 파스 스택은 해당 지점까지 도달한 상태 번호를 기억한다. 모든 파싱 단계에서 전체 입력 텍스트는 이전에 파싱된 구문 스택, 현재 미리 보기 심볼, 그리고 나머지 스캔되지 않은 텍스트로 나뉜다. 파서의 다음 동작은 현재 LR(0) 상태 번호(스택의 가장 오른쪽)와 미리 보기 심볼에 의해 결정된다. 아래 단계에서 모든 검은색 세부 정보는 다른 비-LR 시프트-리듀스 파서와 정확히 동일하다. LR 파서 스택은 스택의 왼쪽에 있는 검은색 구문과 다음에 예상되는 구문 가능성을 요약하는 보라색 상태 정보를 추가한다. LR 파서 사용자는 일반적으로 상태 정보를 무시할 수 있다. 이 상태들은 나중에 설명한다. {| class="wikitable" |- ! Break단계 !! 파스 스택Break상태 [심볼상태]* !! 미리Break보기 !! Break스캔되지 않음 !! 파서Break동작 !! Break문법 규칙|| 다음Break상태 |- |align="center"| 0 || 0 || id || align="right" | * 2 + 1 || 시프트 || ||align="center"| 9 |- |align="center"| 1 || 0 id9 || * || align="right" | 2 + 1 || 리듀스 || Value → id ||align="center"| 7 |- |align="center"| 2 || 0 Value7 || * || align="right" | 2 + 1 || 리듀스 || Products → Value ||align="center"| 4 |- |align="center"| 3 || 0 Products4 || * || align="right" | 2 + 1 || 시프트 || ||align="center"| 5 |- |align="center"| 4 || 0 Products4 *5 || int || align="right" | + 1 || 시프트 || ||align="center"| 8 |- |align="center"| 5 || 0 Products4 *5 int8 || + || align="right" | 1 || 리듀스 || Value → int ||align="center"| 6 |- |align="center"| 6 || 0 Products4 *5 Value6 || + || align="right" | 1 || 리듀스 || Products → Products * Value ||align="center"| 4 |- |align="center"| 7 || 0 Products4 || + || align="right" | 1 || 리듀스 || Sums → Products ||align="center"| 1 |- |align="center"| 8 || 0 Sums1 || + || align="right" | 1 || 시프트 || ||align="center"| 2 |- |align="center"| 9 || 0 Sums1 +2 || int || align="right" | eof || 시프트 || ||align="center"| 8 |- |align="center"| 10 || 0 Sums1 +2 int8 || eof || || 리듀스 || Value → int ||align="center"| 7 |- |align="center"| 11 || 0 Sums1 +2 Value7 || eof || || 리듀스 || Products → Value ||align="center"| 3 |- |align="center"| 12 || 0 Sums1 +2 Products3 || eof || || 리듀스 || Sums → Sums + Products ||align="center"| 1 |- |align="center"| 13 || 0 Sums1 || eof || || 수락 || || |- |} 초기 0단계에서 입력 스트림 "A * 2 + 1"은 다음과 같이 나뉜다. * 파스 스택의 빈 섹션, * id 심볼로 스캔된 미리 보기 텍스트 "A", 그리고 * 나머지 스캔되지 않은 텍스트 "* 2 + 1". 파스 스택은 초기 상태 0만 포함한 채 시작한다. 상태 0이 미리 보기 id를 보면, 해당 id를 스택에 시프트하고 다음 입력 심볼 *****를 스캔하여 상태 9로 진행해야 함을 안다. rule 4단계에서 총 입력 스트림 "A * 2 + 1"은 현재 다음과 같이 나뉜다. * Products와 ***** 두 개의 스택된 구문이 있는 파싱된 섹션 "A *", * int 심볼로 스캔된 미리 보기 텍스트 "2", 그리고 * 나머지 스캔되지 않은 텍스트 " + 1". 스택된 구문에 해당하는 상태는 0, 4, 5이다. 스택의 현재 가장 오른쪽 상태는 상태 5이다. 상태 5가 미리 보기 int를 보면, 해당 int를 스택에 자체 구문으로 시프트하고 다음 입력 심볼 **+**를 스캔하여 상태 8로 진행해야 함을 안다. rule 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 테이블은 큰 문법에 대해 손으로 정확하게 계산하기 어렵다. 그래서 비손과 같은 파서 생성기 도구에 의해 문법에서 기계적으로 파생된다.Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009. 상태 및 파싱 테이블이 생성되는 방법에 따라 결과 파서는 **SLR**(Simple LR) 파서, **LALR**(Look-Ahead LR) 파서 또는 정규 LR 파서라고 불린다. LALR 파서는 SLR 파서보다 더 많은 문법을 처리한다. 정규 LR 파서는 훨씬 더 많은 문법을 처리하지만, 더 많은 상태와 훨씬 더 큰 테이블을 사용한다. 예제 문법은 SLR이다. LR 파스 테이블은 2차원이다. 각 현재 LR(0) 파서 상태는 자체 행을 가진다. 각 가능한 다음 심볼은 자체 열을 가진다. 상태와 다음 심볼의 일부 조합은 유효한 입력 스트림에 대해 불가능하다. 이러한 빈 셀은 구문 오류 메시지를 유발한다. 테이블의 **액션** 왼쪽 절반은 미리보기 종결자 열을 가진다. 이 셀들은 다음 파서 액션이 시프트(상태 n으로)인지 또는 리듀스(문법 규칙 **r**n에 의해)인지 결정한다. 테이블의 **고투** 오른쪽 절반은 비종결자 열을 가진다. 이 셀들은 어떤 리덕션의 좌변이 해당 심볼의 예상되는 새 인스턴스를 생성한 후 어떤 상태로 진행할지를 보여준다. 이는 시프트 액션과 비슷하지만 비종결자를 위한 것이다. 미리보기 종결자 심볼은 변경되지 않는다. "현재 규칙"이라는 테이블 열은 파서 생성기에 의해 도출된 각 상태에 대한 의미와 구문 가능성을 문서화한다. 파싱 시 실제로 사용되는 테이블에는 포함되지 않는다. •(핑크 점) 마커는 파서가 현재 부분적으로 인식된 문법 규칙 내에서 어디에 있는지 보여준다. • 왼쪽에 있는 항목들은 파싱되었으며, 오른쪽에 있는 항목들은 곧 예상된다. 파서가 가능성을 단일 규칙으로 좁히지 않은 경우 상태는 여러 개의 현재 규칙을 가질 수 있다. {| class="wikitable" |- ! 현재 !! !! colspan="5" | 미리 보기 !! !! colspan="3" | LHS 고투 |- ! 상태 !! 현재 규칙 !! int !! id !! * !! + !! eof !! !! Sums !! Products !! Value |- | 0 || Goal → • Sums eof || 8 || 9 || || || |||| 1 || 4 || 7 |- | 1 || Goal → Sums • eof Break Sums → Sums • \+ Products || || || || Break2 || 수락Break |||| || || |- | 2 || Sums → Sums + • Products || 8 || 9 || || || |||| || 3 || 7 |- | 3 || Sums → Sums + Products • Break Products → Products • * Value || || || Break5 || r1 Break || r1 Break |||| || || |- | 4 || Sums → Products • Break Products → Products • * Value || || || Break5 || r2 Break || r2 Break |||| || || |- | 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로도 시작할 수 있다. 다른 미리 보기 또는 비종결자의 경우 파서는 구문 오류를 알린다. rule 상태 3에서 파서는 방금 Products 구문을 찾았는데, 이는 두 가지 가능한 문법 규칙에서 비롯될 수 있다. ::r1: Sums → Sums + Products • ::r3: Products → Products • * Value r1과 r3 사이의 선택은 이전 구문을 뒤로만 살펴서는 결정할 수 없다. 파서는 무엇을 해야 할지 알아내기 위해 미리보기 심볼을 확인해야 한다. 미리보기가 *****이면 규칙 3에 있으므로 파서는 *****를 시프트하고 상태 5로 진행한다. 미리보기가 eof이면 규칙 1과 규칙 0의 끝에 있으므로 파서는 완료된다. rule 위의 상태 9에서 비어있지 않고 오류가 아닌 모든 셀은 동일한 축소 r6에 대한 것이다. 일부 파서는 이러한 간단한 경우에 미리보기 심볼을 확인하지 않아 시간과 테이블 공간을 절약한다. 구문 오류는 약간 나중에, 일부 무해한 축소 후에 감지되지만, 다음 시프트 동작 또는 파서 결정 전에는 여전히 감지된다. 개별 테이블 셀에는 여러 대안 동작이 있어서는 안 된다. 그렇지 않으면 파서는 추측 및 백트래킹으로 비결정적이 될 수 있다. 문법이 LR(1)이 아닌 경우, 일부 셀에는 가능한 시프트 동작과 축소 동작 간의 시프트/축소 충돌 또는 여러 문법 규칙 간의 축소/축소 충돌이 발생한다. LR(k) 파서는 첫 번째를 넘어 추가 미리보기 심볼을 확인하여 이러한 충돌을 (가능한 경우) 해결한다.
## LR 파서 루프
LR 파서는 시작 상태 0만 포함하는 거의 비어있는 파스 스택으로 시작하며, 미리보기는 입력 스트림의 첫 번째 스캔된 심볼을 담고 있다. 그런 다음 파서는 완료되거나 구문 오류에 갇힐 때까지 다음 루프 단계를 반복한다. 파스 스택의 최상위 상태는 특정 상태 s이고, 현재 미리보기는 특정 종결자 t이다. 미리보기 액션 테이블의 s행 t열에서 다음 파서 액션을 찾는다. 해당 액션은 시프트, 리듀스, 수락 또는 오류 중 하나이다. * 시프트 n: ::일치하는 종결자 t를 파스 스택에 시프트하고 다음 입력 심볼을 미리보기 버퍼로 스캔한다. ::새로운 현재 상태로 다음 상태 n을 파스 스택에 푸시한다. * 리듀스 rm: 문법 규칙 rm: Lhs → S1 S2 ... SL 적용 ::일치하는 최상위 L개 심볼(및 파스 트리 및 관련 상태 번호)을 파스 스택에서 제거한다. ::이는 Lhs 심볼의 인스턴스를 예상하던 이전 상태 p를 노출한다. ::L개의 파스 트리를 Lhs라는 새 루트 심볼을 가진 하나의 파스 트리로 결합한다. ::LHS 고투 테이블의 p행 Lhs 열에서 다음 상태 n을 찾는다. ::Lhs 심볼과 트리를 파스 스택에 푸시한다. ::새로운 현재 상태로 다음 상태 n을 파스 스택에 푸시한다. ::미리보기와 입력 스트림은 변경되지 않는다. * 수락: 미리보기 t는 eof 마커이다. 파싱 종료. 상태 스택에 시작 상태만 포함되어 있으면 성공을 보고한다. 그렇지 않으면 구문 오류를 보고한다. * 오류: 구문 오류를 보고한다. 파서가 종료되거나 복구를 시도한다. LR 파서 스택은 일반적으로 LR(0) 오토마톤 상태만 저장한다. 왜냐하면 문법 심볼은 이들로부터 파생될 수 있기 때문이다(오토마톤에서 어떤 상태로의 모든 입력 전이는 동일한 심볼로 표시되며, 이는 이 상태와 연관된 심볼이다). 게다가 파싱 결정을 내릴 때 상태가 가장 중요하므로 이러한 심볼은 거의 필요하지 않다.Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.
# 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단계를 다시 살펴보자. {| class="wikitable" |- ! 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 파서를 낳는다.
# 더 읽어보기
* Chapman, Nigel P., LR Parsing: Theory and Practice, 케임브리지 대학교 출판부, 1987. * 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.