LR 파서

컴퓨터 과학에서 LR 파서는 결정론적 컨텍스트 프리 언어를 선형 시간으로 분석하는 ^[1]상향식 파서의 일종입니다.LR 파서에는 SLR 파서, LALR 파서, Canonical LR(1) 파서, Minimal LR(1) 파서 및 GLR 파서의 여러 종류가 있습니다.LR 파서는 구문 분석 대상 언어의 구문을 정의하는 형식 문법에서 파서 생성기에 의해 생성될 수 있다.그것들은 컴퓨터 언어 처리에 널리 사용된다.

LR 파서(왼쪽에서 오른쪽으로, 가장 오른쪽에서 역방향)는 백업 없이 입력 텍스트를 왼쪽에서 오른쪽으로 읽고(대부분의 파서에 해당), 역방향으로 가장 오른쪽의 파서를 생성합니다.이 파서는 하향식 LL 해석이나 애드혹 해석을 하지 않습니다.LR(1) 또는 경우에 따라서는 LR(k)와 같이 LR 이름 뒤에 숫자 한정자가 이어지는 경우가 많습니다.역추적 또는 추측을 피하기 위해 LR 파서는 이전 기호를 해석하는 방법을 결정하기 전에 k개의 선행 입력 기호를 엿볼 수 있습니다.일반적으로 k는 1이며 언급되지 않습니다.LR이라는 이름 앞에는 SLR이나 LALR과 같이 다른 수식자가 붙는 경우가 많습니다.Knuth는 문법의 LR(k) 표기법을 "바인드 ^[1]k로 왼쪽에서 오른쪽으로 변환 가능"의 약자로 제안했다.

LR 파서는 결정론적이어서 추측이나 역추적 없이 선형 시간 내에 하나의 올바른 파스를 생성합니다.이것은 컴퓨터 언어에는 이상적이지만 LR 파서는 더 유연하지만 불가피하게 더 느린 방법을 필요로 하는 인간 언어에는 적합하지 않습니다.문맥이 없는 임의의 언어를 해석할 수 있는 일부 방법(예: Coke-)Younger – Kasami, Earley, GLR)의 퍼포먼스가 최악이다.n) 시간. 역추적 또는 여러 파스를 생성하는 다른 방법은 추측이 ^[2]잘못될 때 기하급수적으로 시간이 걸릴 수 있습니다³.

위의 L, R 및 k 속성은 precedence 파서를 포함한 모든 시프트 리듀스 파서에 의해 실제로 공유됩니다.단, 관례상 LR 이름은 Donald Knuth에 의해 발명된 해석 형식을 나타내며, 그보다 더 빠르고 덜 강력한 우선 순위 메서드(예를 들어 연산자-우선순위 ^[1]파서)는 제외됩니다.LR 파서는 precedence 파서 또는 하향식 LL ^[3]구문 분석보다 더 광범위한 언어 및 문법을 처리할 수 있습니다.이는 LR 파서가 검출된 내용을 커밋하기 전에 일부 문법 패턴의 인스턴스 전체를 확인할 때까지 대기하기 때문입니다.LL 파서는 패턴의 가장 왼쪽에 있는 입력 기호만 인식했을 경우, 그 패턴의 표시 내용을 보다 빨리 판단하거나 추측할 필요가 있습니다.

개요

상향식 해석 트리(예: A*2 + 1 )

LR 파서는 입력 텍스트를 텍스트 위로 1회 전진 패스로 스캔하여 구문 분석합니다.파서는 추측이나 역추적 없이 파싱 트리를 증분, 상향 및 왼쪽에서 오른쪽으로 구축합니다.이 패스의 모든 포인트에서 파서는 이미 해석된 입력 텍스트의 하위 트리 또는 구문 목록을 누적합니다.이러한 서브트리는 파서가 결합하는 구문 패턴의 오른쪽 끝에 아직 도달하지 않았기 때문에 결합되지 않았습니다.

해석 예시의 스텝6 에서는, 「A*2」만이 불완전하게 해석되고 있습니다.구문 분석 트리의 왼쪽 아래 구석에 음영 처리된 부분만 있습니다.7 이상의 번호를 가진 해석 트리 노드가 아직 존재하지 않습니다.노드 3, 4, 및 6은 각각 변수 A, 연산자 * 및 숫자2의 독립 서브트리의 루트입니다.이들 3개의 루트노드는 일시적으로 해석스택에 보관 유지됩니다.입력 스트림의 나머지 파싱되지 않은 부분은 "+ 1"입니다.

작업 전환 및 감소

다른 Shift-Reduce 파서와 마찬가지로 LR 파서는 Shift 스텝과 Reduce 스텝을 조합하여 동작합니다.

• Shift 스텝은 입력 스트림에서 한 기호씩 진행됩니다.이 시프트 기호는 새로운 단일 노드 해석 트리가 됩니다.
• Reduce 스텝은 완료된 문법 규칙을 최근 해석 트리의 일부에 적용하여 새로운 루트 기호가 있는 하나의 트리로 결합합니다.

입력에 구문 오류가 없는 경우 파서는 모든 입력이 소비되고 모든 해석 트리가 법적 입력 전체를 나타내는 단일 트리로 축소될 때까지 이러한 단계를 계속합니다.

LR 파서는 축소할 타이밍과 유사한 엔딩을 가진 규칙 사이에서 선택하는 방법에 있어 다른 시프트 리듀스 파서와 다릅니다.그러나 최종 결정과 전환 또는 감소 순서는 동일합니다.

LR 파서의 효율성의 대부분은 결정론에서 비롯됩니다.추측을 피하기 위해 LR 파서는 이전에 스캔한 기호를 어떻게 할지 결정하기 전에 다음 스캔 기호를 앞(오른쪽)으로 보는 경우가 많습니다.어휘 스캐너는 파서보다 앞에 있는1개 또는 복수의 기호를 동작시킨다.미리 보기 기호는 구문 분석 ^[4]결정을 위한 '오른쪽 컨텍스트'입니다.

상향식 해석 스택

다른 시프트 파서 및 리듀스 파서와 마찬가지로 LR 파서는 조합된 구성이 무엇인지 커밋하기 전에 일부 구성의 모든 부분을 스캔하고 구문 분석할 때까지 느긋하게 기다립니다.그러면 파서는 더 이상 기다리지 않고 조합에 따라 즉시 작동합니다.구문 분석 트리의 예에서는 구문 분석 트리의 이러한 부분을 정리하는 것을 기다리지 않고 미리 보기*가 표시되는 즉시 구문 분석 트리 1~3단계에서 구문 A가 Value로 축소되고 다음으로 Products로 축소됩니다.A의 처리 방법에 대한 결정은 파서와 스캐너가 이미 본 내용에 따라 결정되며 훨씬 뒤에 오른쪽에 나타나는 사항은 고려하지 않습니다.

축소는 가장 최근에 구문 분석된 항목을 미리 보기 기호 바로 왼쪽에 재구성합니다.따라서 이미 구문 분석된 항목의 목록은 스택처럼 작동합니다.이 해석 스택은 바로 커집니다.스택의 베이스 또는 하단은 왼쪽에 있으며 가장 왼쪽에 있는 가장 오래된 해석 fragment를 유지합니다.모든 축소 단계는 가장 오른쪽에 있는 최신 구문 분석 fragment에만 적용됩니다.(이 누적 구문 분석 스택은 하향식 구문 분석기가 사용하는 예측 구문 분석 스택과 매우 다릅니다).

A*2 + 1과 같은 상향식 해석 절차

걸음	해석 스택	파싱되지 않다	시프트/축소
0	빈	A*2 + 1	교대하다
1	아이디	*2 + 1	값 → id
2	가치	*2 + 1	제품 → 값
3	상품들	*2 + 1	교대하다
4	제품*	2 + 1	교대하다
5	제품 * int	+ 1	값 → int
6	제품 * 가치	+ 1	제품 → 제품 * 가치
7	상품들	+ 1	합계 → 제품
8	합계	+ 1	교대하다
9	합계 +	1	교대하다
10	합계 + int	이오	값 → int
11	합계 + 값	이오	제품 → 값
12	합계 + 제품	이오	합계 → 합계 + 제품
13	합계	이오	다 했어요.

스텝 6은 여러 부분으로 이루어진 문법 규칙을 적용합니다.

제품 → 제품 * 가치

해석된 문구를 보관하고 있는 스택톱과 일치합니다...제품 * 가치"축소 단계는 규칙의 오른쪽 인스턴스인 "Products * Value"를 규칙의 왼쪽 기호(여기서는 더 큰 제품)로 대체합니다.파서가 완전한 해석 트리를 구축하는 경우 내부 제품의 3가지 트리, * 및 Value가 제품의 새 트리 루트에 의해 결합됩니다.그렇지 않으면 내부 제품 및 값에서 의미 세부 정보가 이후 컴파일러 패스로 출력되거나 결합되어 새 제품 ^[5]기호에 저장됩니다.

LR 해석 절차(예: A*2 + 1 )

LR 파서에서는 시프트와 리덕션 결정이 단일 최상위 스택 기호뿐만 아니라 이전에 구문 분석된 모든 스택을 기반으로 할 수 있습니다.엉클버 방식으로 하면 입력이 길어질수록 파서가 느려질 수 있습니다.LR 파서는 관련된 모든 왼쪽 컨텍스트 정보를 LR(0) 파서 상태라고 하는 단일 번호로 요약함으로써 이를 일정한 속도로 수행합니다.각 문법 및 LR 분석 방법에는 그러한 상태의 수가 고정(유한)되어 있습니다.해석 스택은 이미 해석된 기호를 유지하는 것 외에도 해당 지점까지의 모든 항목에 의해 도달한 상태 번호도 기억합니다.

각 해석 스텝에서 입력 텍스트 전체를 미리 해석된 구문의 스택, 현재 예측 심볼 및 나머지 스캔되지 않은 텍스트로 분할한다.파서의 다음 액션은 현재 LR(0) 상태 번호(스택의 맨 오른쪽)와 미리 보기 기호로 결정됩니다.다음 단계에서는 검은색 세부 정보가 모두 다른 비LR 시프트 리듀스 파서와 동일합니다.LR 파서 스택은 상태 정보를 보라색으로 추가하여 스택 왼쪽에 검은색 문구와 다음에 예상되는 구문 가능성을 요약합니다.일반적으로 LR 파서의 사용자는 상태 정보를 무시할 수 있습니다.이러한 상태에 대해서는, 후술의 항에서 설명합니다.

걸음	해석 스택 state [기호state]*	보라 앞서.	스캔되지 않았다	파서 액션.	문법 규칙	다음 분. 주
0	0	아이디	*2 + 1	교대하다		9
1	0 아이디9	*	2 + 1	줄이자	값 → id	7
2	0 값7	*	2 + 1	줄이자	제품 → 값	4
3	0 제품4	*	2 + 1	교대하다		5
4	0 제품4*5	인트	+ 1	교대하다		8
5	0 제품48 *5 int	+	1	줄이자	값 → int	6
6	0 제품4 *5 가치6	+	1	줄이자	제품 → 제품 * 가치	4
7	0 제품4	+	1	줄이자	합계 → 제품	1
8	0 합계1	+	1	교대하다		2
9	0 합계1 +2	인트	이오	교대하다		8
10	0 합계18 +2 int	이오		줄이자	값 → int	7
11	0 합계17 +2 값	이오		줄이자	제품 → 값	3
12	0 합계1 +2 제품3	이오		줄이자	합계 → 합계 + 제품	1
13	0 합계1	이오		다 했어요.

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

• 해석 스택의 빈 섹션,
• ID 기호로 스캔된 선행 텍스트 "A"
• 나머지 스캔되지 않은 텍스트 "*2 + 1".

해석 스택은 초기 상태0만을 유지하는 것으로 시작합니다.상태 0이 미리 보기 ID를 확인하면 해당 ID를 스택으로 이동하고 다음 입력 기호 *를 스캔하여 상태 9로 이동합니다.

---

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

• 2개의 누적된 문구로 구성된 구문 분석 섹션 "A *"와 *,
• 검색 텍스트 "2"가 int 기호로 스캔되고,
• 나머지 스캔되지 않은 텍스트 " + 1".

스택된 문구에 대응하는 상태는 0, 4, 5 입니다.스택의 현재 오른쪽 끝 상태는 스테이트5 입니다스테이트 5는, 룩어헤드 int를 검출하면, 그 int를 자신의 프레이즈로서 스택에 옮겨, 다음의 입력 기호 + 를 스캔 해 스테이트 8 로 진행시키는 것을 인식합니다.

---

스텝 12에서는 모든 입력 스트림이 소비되지만 부분적으로만 정리됩니다.현재 상태는 3 입니다.상태 3이 예측 eof를 볼 때 완성된 문법 규칙을 적용하는 것을 알고 있다.

합계 → 합계 + 제품

스택의 오른쪽 끝에 있는 Sums, + 및 Products의 세 문구를 하나의 문구로 조합합니다.스테이트 3 자체는 다음 스테이트가 어떻게 될지는 모릅니다.이는 축소되는 문구의 바로 왼쪽에 있는 상태0으로 돌아가면 알 수 있습니다.상태 0이 이 새로운 완료된 합계 인스턴스를 확인하면 상태 1로 진행됩니다(다시).이러한 오래된 상태의 컨설팅은 현재 상태만 유지하는 것이 아니라 스택 상에 유지되는 이유입니다.

예 A*2 + 1의 문법

LR 파서는 입력 언어의 구문을 패턴 집합으로 공식적으로 정의하는 문법으로 구성됩니다.문법은 숫자의 크기와 같은 모든 언어 규칙이나 프로그램 전체의 맥락에서 이름과 정의를 일관되게 사용하는 것을 포함하지는 않습니다.LR 파서는 국소적인 기호 패턴만을 다루는 문맥 없는 문법을 사용합니다.

여기서 사용되는 문법의 예는 Java 또는 C 언어의 작은 서브셋입니다.

r0: 목표 → 합계 eof

r1: 합계 → 합계 + 제품

r2: 합계 → 제품

r3: 제품 → 제품 * 가치

r4: 제품 → 값

r5: 값 → int

r6: 값 → id

문법의 종단 기호는 어휘 스캐너에 의해 입력 스트림에서 발견된 다중 문자 기호 또는 '토큰'입니다.여기에는 정수 상수에는 + * 및 int, 식별자 이름에는 id, 입력 파일 끝에는 eof가 포함됩니다.문법은 int 값이나 id 철자가 무엇인지, 공백이나 줄 바꿈에 대해서는 상관하지 않습니다.문법은 이러한 종단 기호를 사용하지만 정의하지는 않습니다.이들은 항상 해석 트리의 리프 노드(하단 부시 엔드)입니다.

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

주어진 컴퓨터 언어는 몇 가지 다른 문법으로 설명할 수 있습니다.LR(1) 파서는 많은 공통 문법을 처리할 수 있지만 모든 공통 문법을 처리할 수는 없습니다.일반적으로 LR(1) 구문 분석 및 생성 도구의 제한에 맞도록 문법을 수동으로 수정할 수 있습니다.

LR 파서의 문법은 명확해야 합니다.또는 동점이 되는 우선순위 규칙에 의해 강화되어야 합니다.즉, 언어의 특정 법적 예에 문법을 적용하는 올바른 방법은 하나뿐이며, 그 결과 하나의 의미만을 가진 고유한 해석 트리와 그 예에 대한 고유한 시프트/삭감 액션 시퀀스가 생성됩니다.LR 파싱은 단어 상호 작용에 따라 달라지는 애매한 문법을 가진 인간 언어에는 유용한 기술이 아닙니다.인간의 언어는 Generalized LR 파서, Earley 파서, CYK 알고리즘과 같은 파서로 처리되므로 가능한 모든 파서 트리를 한 번에 동시에 계산할 수 있습니다.

예제 문법에 대한 구문 분석 테이블

대부분의 LR 파서는 테이블 구동입니다.파서의 프로그램 코드는 모든 문법과 언어에 동일한 단순한 범용 루프입니다.문법과 그 구문적 의미에 대한 지식은 해석 테이블(또는 해석 테이블)이라고 불리는 변경되지 않은 데이터 테이블로 인코딩됩니다.표의 항목은 파서 상태와 룩어헤드 기호의 모든 법적 조합에 대해 이동 또는 축소(및 어떤 문법 규칙에 따라) 여부를 나타냅니다.해석 테이블은 현재 상태와 다음 기호만 지정하면 다음 상태를 계산하는 방법도 알려줍니다.

구문 분석 테이블이 문법보다 훨씬 큽니다.LR 테이블은 큰 문법의 경우 손으로 정확하게 계산하기가 어렵습니다.즉, ^[6]Bison과 같은 파서 생성 도구에 의해 문법에서 기계적으로 파생된 것입니다.

상태 및 해석 테이블 생성 방법에 따라 생성되는 파서는 SLR(Simple LR) 파서, LALR(Look-Ahead LR) 파서 또는 표준 LR 파서라고 불립니다.LALR 파서는 SLR 파서보다 더 많은 문법을 처리합니다.표준 LR 파서는 더 많은 문법을 처리하지만 더 많은 상태와 더 큰 테이블을 사용합니다.문법의 예는 SLR입니다.

LR 해석 테이블은 2차원입니다.현재의 각 LR(0) 파서 상태에는 고유의 행이 있습니다.가능한 각 다음 기호에는 고유한 열이 있습니다.유효한 입력 스트림에 대해 상태 및 다음 기호의 일부 조합을 사용할 수 없습니다.이러한 공백 셀은 구문 오류 메시지를 트리거합니다.

표의 왼쪽 절반에는 미리 보기 터미널 기호를 나타내는 열이 있습니다.이러한 셀은 다음 파서액션이 시프트(상태n으로)인지, 아니면 환원(문법 규칙r에_n 따라)인지를 결정합니다.

표의 오른쪽 절반에는 비말단 기호 열이 있습니다.이러한 셀은 일부 감소의 왼쪽이 해당 기호의 예상된 새 인스턴스를 만든 후 어떤 상태로 진행할지 보여줍니다.이것은 시프트 동작과 비슷하지만 종단 이외의 경우에는 선행 터미널 기호는 변경되지 않습니다.

표 열 "Current Rules"는 파서 생성기에서 파악한 바와 같이 각 상태의 의미와 구문 가능성을 문서화합니다.해석 시 사용되는 실제 테이블에는 포함되지 않습니다.• (핑크 도트) 마커는 부분적으로 인식된 문법 규칙 내에서 파서가 현재 어디에 있는지 보여줍니다.•의 왼쪽에 있는 것은 구문 분석되었으며, 오른쪽에 있는 것은 곧 예상됩니다.파서가 아직 단일 규칙으로 가능성을 좁히지 않은 경우 상태에는 이와 같은 몇 가지 현재 규칙이 있습니다.

커		미리 보다						LHS 고토
주	현행 규칙	인트	아이디	*	+	이오		합계	상품들	가치
0	목표 → • 합계 eof	8	9					1	4	7
1	목표 → 합계 •eof 합계 → 합계 • + 제품				2	다 했어요.
2	합계 → 합계 + • 제품	8	9						3	7
3	합계 → 합계 + 제품 • 제품 → 제품 • * 가치			5	r1	r1
4	합계 → 제품 • 제품 → 제품 • * 가치			5	r2	r2
5	제품 → 제품 * • 가치	8	9							6
6	제품 → 제품 * 가치 •			r3	r3	r3
7	제품 → 가치 •			r4	r4	r4
8	값 → int •			r5	r5	r5
9	값 → ID •			r6	r6	r6

위의 상태 2에서 파서는 방금 문법 규칙의 +를 찾아 이동했습니다.

r1: 합계 → 합계 + • 제품

다음 예상 문구는 Products입니다.제품은 터미널 기호 int 또는 id로 시작합니다.예측이 둘 중 하나일 경우 파서는 각각 상태 8 또는 상태 9로 전환합니다.Products가 발견되면 파서는 상태 3으로 이동하여 summand의 전체 목록을 누적하고 규칙 r0의 끝을 찾습니다.제품은 nonterminal Value로 시작할 수도 있습니다.다른 룩어헤드 또는 비터미널의 경우 파서는 구문 오류를 방송합니다.

---

상태 3에서 파서는 두 가지 가능한 문법 규칙에서 파생된 Products 문구를 발견했습니다.

r1: 합계 → 합계 + 제품 •

r3: 제품 → 제품 • * 가치

r1과 r3 사이의 선택은 이전 문구를 되돌아보는 것만으로 결정할 수 없습니다.파서는 미리 보기 기호를 확인하여 작업을 지시해야 합니다.예측값이 *인 경우 규칙 3에 있으므로 파서는 *에서 전환되어 상태 5로 이동합니다.검색 결과가 eof인 경우 규칙 1과 규칙 0의 끝에 있으므로 파서는 완료됩니다.

---

위의 스테이트 9에서는 공백이 아닌 비오류 셀은 모두 같은 reduction r6입니다.일부 파서는 이러한 간단한 경우 미리 보기 기호를 선택하지 않음으로써 시간과 테이블 공간을 절약합니다.구문 오류는 어느 정도 감소된 후에 검출되지만 다음 교대 작업 또는 파서의 결정 전에는 검출됩니다.

개별 테이블 셀은 여러 대체 액션을 유지할 수 없습니다.그렇지 않으면 파서는 추측 및 백트래킹에 의해 결정되지 않습니다.문법이 LR(1)이 아닌 경우, 일부 셀은 가능한 시프트 액션 간에 시프트/리듀스 경합을 가지며 액션을 줄이거나 여러 문법 규칙 간의 경합을 축소/리듀스합니다.LR(k) 파서는 가능한 경우 첫 번째 이후의 추가 선행 기호를 확인하여 이러한 충돌을 해결합니다.

LR 파서 루프

LR 파서는 시작 상태 0만을 포함하는 거의 빈 구문 분석 스택에서 시작하여 입력 스트림의 첫 번째 스캔 기호를 보관합니다.그런 다음 파서는 다음 루프 단계를 완료하거나 구문 오류가 발생할 때까지 반복합니다.

해석 스택의 최상위 상태는 몇 가지 상태이며 현재 룩어헤드 상태는 몇 가지 터미널 기호 t입니다.[ Lookahead Action ]테이블의 행과 열 t에서 다음 파서 액션을 검색합니다.이 액션은 Shift, Reduce, Done 또는 Error입니다.

• 시프트 n:

일치하는 터미널 t를 구문 분석 스택으로 이동하고 다음 입력 기호를 검색 버퍼로 스캔합니다.

다음 상태n을 새로운 현재 상태로 해석 스택에 푸시합니다.

• 감소_m r: 문법 규칙_m r: Lhs₂ → S₁...S_L.

일치하는 최상위 L 기호(및 해석 트리 및 관련 상태 번호)를 해석 스택에서 삭제합니다.

이는 Lhs 기호의 인스턴스를 예상한 이전 상태 p를 나타냅니다.

L 구문 분석 트리를 새로운 루트 기호 Lhs와 함께 하나의 구문 분석 트리로 결합합니다.

LHS Goto 테이블의 p행과 Lhs열에서 다음 상태 n을 조회합니다.

LHS 기호와 트리를 구문 분석 스택에 푸시합니다.

다음 상태n을 새로운 현재 상태로 해석 스택에 푸시합니다.

미리 보기 및 입력 스트림은 변경되지 않습니다.

• 완료: 선행 검색은 eof 마커입니다.해석의 종료.상태 스택에 시작 상태 보고서 성공만 포함되어 있는 경우.그렇지 않으면 구문 오류를 보고합니다.
• 오류: 구문 오류를 보고합니다.파서가 종료되거나 회복이 시도됩니다.

LR 파서 스택은 보통 LR(0) 오토마톤 상태만 저장합니다.이러한 상태로부터 문법 기호가 파생될 수 있기 때문입니다(오토마톤에서는 어떤 상태로의 모든 입력 천이는 이 상태와 관련된 기호인 동일한 기호로 표시됩니다).또한 이러한 기호는 구문 분석 ^[7]결정을 내릴 때 상태가 가장 중요하기 때문에 거의 필요하지 않습니다.

LR 발전기 분석

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

LR 상태

해석 테이블의 상태 2는 부분적으로 해석된 규칙에 대한 것입니다.

r1: 합계 → 합계 + • 제품

이것은 파서가 더 큰 Sums를 찾는 동안 Sums를 보고 +를 표시함으로써 어떻게 여기에 도달했는지 보여줍니다.• 마커가 규칙의 시작 부분을 넘어섰습니다.또한 다음에 완전한 제품을 검색하여 파서가 최종적으로 규칙을 완료하는 방법도 보여줍니다.그러나 해당 제품의 모든 부품을 해석하는 방법에 대한 자세한 내용이 필요합니다.

상태에 대해 부분적으로 구문 분석된 규칙을 "핵심 LR(0) 항목"이라고 합니다.파서 생성기는 예상 제품을 빌드할 때 가능한 모든 다음 단계에 대한 규칙 또는 항목을 추가합니다.

r3: 제품 → • 제품 * 가치

r4: 제품 → • 가치

r5: 값 → • int

r6: 값 → • id

• 마커는 추가된 각 규칙의 선두에 있습니다.파서는 아직 이들 규칙의 어떤 부분도 확인하고 구문 분석하지 않았습니다.이러한 추가 항목을 핵심 항목의 "폐쇄"라고 합니다.• 바로 뒤에 있는 각 비단말기호에 대해 제너레이터는 해당 기호를 정의하는 규칙을 추가합니다.따라서 더 많은 • 마커가 추가되고 다른 팔로워 기호가 추가될 수 있습니다.이 닫기 프로세스는 모든 팔로워 기호가 확장될 때까지 계속됩니다.상태 2의 팔로어 비종단은 Products로 시작합니다.그런 다음 닫힘에 따라 값이 추가됩니다.팔로어 터미널은 int 및 id입니다.

커널 항목과 클로징 항목은 현재 상태에서 미래 상태로 진행되며 문구를 완성하기 위한 모든 가능한 법적 방법을 보여 줍니다.하나의 항목에만 팔로워 기호가 나타나면 • 마커가 고급화된 하나의 핵심 항목만 포함하는 다음 상태로 이어집니다.그래서 int는 core를 가진 다음 상태 8로 이어집니다.

r5: 값 → int •

여러 항목에 동일한 팔로어 기호가 나타나면 파서는 여기에 적용되는 규칙을 아직 알 수 없습니다.따라서 이 기호는 나머지 모든 가능성을 보여주는 다음 상태로 이어지며, 다시 • 마커가 확장됩니다.제품은 r1과 r3에 모두 표시됩니다.그 때문에, 제품에서는, 코어를 탑재한 다음의 상태 3으로 이행합니다.

r1: 합계 → 합계 + 제품 •

r3: 제품 → 제품 • * 가치

즉, 파서가 단일 제품을 확인한 경우, 파서는 완료되었을 수도 있고 함께 곱해야 할 것이 더 많을 수도 있습니다.모든 핵심 항목은 • 마커 앞에 동일한 기호를 가집니다. 이 상태로 전환되는 모든 항목은 항상 동일한 기호를 가집니다.

일부 전환은 이미 열거된 코어 및 상태로 이루어집니다.다른 전환은 새로운 상태로 이어집니다.생성자는 문법의 목표 규칙에서 시작합니다.여기서부터 필요한 상태가 모두 발견될 때까지 알려진 상태와 전환을 계속 탐색합니다.

이러한 상태를 "LR(0)" 상태라고 하는데, 이는 k=0의 룩어헤드(즉, 룩어헤드 없음)를 사용하기 때문입니다.입력 기호에 대한 유일한 확인은 기호가 이동될 때 수행됩니다.리덕션 룩헤드의 체크는 열거된 상태 자체가 아니라 해석 테이블에 의해 개별적으로 수행됩니다.

유한 상태 기계

해석 테이블은 가능한 모든 LR(0) 상태와 그 천이를 설명합니다.FSM은 Finite State Machine(FSM; 유한 상태 머신)을 형성합니다.FSM은 스택을 사용하지 않고 단순 비내스트 언어를 해석하는 단순한 엔진입니다.이 LR 어플리케이션에서는 FSM의 변경된 "입력 언어"에는 터미널 기호와 비터미널 기호가 모두 포함되어 LR 해석의 일부 해석된 스택스냅샷이 포함됩니다

해석 스텝의 순서 5를 호출합니다.예:

걸음	해석 스택 state 기호...	보라 앞서.	스캔되지 않았다
5	0 제품48 *5 int	+	1

해석 스택은 시작 상태 0에서 상태 4로, 그 후 5 및 현재 상태 8로 일련의 상태 천이를 보여줍니다.해석 스택의 기호는 이러한 전환에 대한 시프트 기호 또는 고토 기호입니다.또 다른 방법은 유한 상태 머신이 (다른 스택을 사용하지 않고) "Products * int + 1" 스트림을 스캔하여 다음에 축소해야 하는 완전한 구문을 찾는 것입니다.그리고 그것은 정말로 그들의 일이다!

원래 파싱되지 않은 언어에 네스트와 재귀가 있고 스택이 있는 Analyzer가 반드시 필요한 경우 FSM만으로 이를 수행할 수 있는 방법은 무엇입니까?문제는 스택 상단의 왼쪽에 있는 모든 것이 이미 완전히 축소되었다는 것입니다.이것에 의해, 이러한 문구에서 루프와 네스팅이 모두 배제됩니다.FSM은 오래된 구문을 모두 무시하고 다음에 완료될 가능성이 있는 최신 구문을 추적할 수 있습니다.LR 이론에서 이를 이해하기 어려운 이름은 "viable prefix"입니다.

룩어헤드 세트

상태와 전환은 해석 테이블의 시프트 액션과 goto 액션에 필요한 모든 정보를 제공합니다.또한 생성자는 각 축소 작업에 대해 예상되는 룩어헤드 세트를 계산해야 합니다.

SLR 파서에서는 이러한 룩어헤드세트는 개별 상태와 전이를 고려하지 않고 문법에 따라 직접 결정됩니다.SLR 발생기는 각 비단말기 S에 대해 S의 발생 직후에 일어날 수 있는 모든 단자 심볼의 집합인 Follows(S)를 산출한다.해석 테이블에서 S로의 각 축소는 LR(1) 룩어헤드세트로 Follow(S)를 사용합니다.이러한 팔로우 세트는 LL 하향식 파서의 생성기에서도 사용됩니다.Follow sets를 사용할 때 shift/reduce 또는 reduce 충돌이 없는 문법을 SLR 문법이라고 합니다.

LALR 파서는 SLR 파서와 동일한 상태를 가지지만 각 개별 상태에 필요한 최소 축소 룩어헤드를 계산하기 위해 보다 복잡하고 정밀한 방법을 사용합니다.문법의 상세 내용에 따라 SLR 파서 제너레이터에 의해 계산된 Follow set과 같거나 SLR lookaheads의 서브셋으로 판명될 수 있습니다.일부 문법은 LALR 파서 생성기에는 적합하지만 SLR 파서 생성기에는 적합하지 않습니다.이 문제는 후속 집합을 사용하여 문법에 잘못된 이동/축소 또는 감소/축소가 있지만 LALR 생성기에 의해 계산된 정확한 집합을 사용할 경우 충돌이 발생하지 않을 때 발생합니다.이 문법은 LALR(1)이라고 불리지만 SLR은 아닙니다.

SLR 또는 LALR 파서는 중복 상태를 회피합니다.그러나 이러한 최소화는 필요하지 않으며 불필요한 예측 충돌이 발생할 수 있습니다.표준 LR 파서는 복제(또는 "분할") 상태를 사용하여 비단말기 사용의 왼쪽 및 오른쪽 컨텍스트를 더 잘 기억합니다.문법에 있어서의 기호 S의 각 발생은, 독자적인 룩어헤드 세트를 가지는 것으로 독립적으로 취급할 수 있기 때문에, 축소 경합 해소에 도움이 된다.이것은 몇 가지 문법을 더 처리한다.안타깝게도 구문 분석 테이블의 크기가 문법의 모든 부분에 대해 크게 확대됩니다.이러한 상태의 분할은, 일부의 비터미널의 이름 있는 카피를 2개 이상 작성하는 것으로써, 임의의 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 파서 생성기는 해석 테이블이 아닌 각 상태에 대해 개별 맞춤 프로그램 코드를 만듭니다.이러한 파서는 테이블 구동 파서의 일반 파서 루프보다 몇 배 더 빠르게 실행할 수 있습니다.가장 빠른 파서는 생성된 어셈블러 코드를 사용합니다.

재귀적 상승 파서 바리에이션에서는 명시적 해석 스택구조도 서브루틴 콜에 의해 사용되는 암묵적 스택으로 대체됩니다.감소에 의해 서브루틴콜의 몇 가지 레벨이 종료됩니다.이것은 대부분의 언어에서는 서투릅니다.따라서 재귀 상승 파서는 일반적으로 재귀 하강 파서보다 느리고 덜 명확하며 손으로 수정하기가 어렵습니다.

다른 변형은 Prolog와 같은 비프로시저 언어의 패턴 일치 규칙에 의해 해석 테이블을 대체합니다.

GLR Generalized LR 파서는 LR 보텀업 기술을 사용하여 하나의 올바른 파스가 아니라 입력 텍스트의 가능한 모든 파스를 검색합니다.이것은 인간의 언어에서 사용되는 것과 같은 애매한 문법에 필수적입니다.복수의 유효한 해석 트리는 백트래킹 없이 동시에 계산됩니다.GLR은 경합이 없는 LALR(1) 문법에 의해 쉽게 기술되지 않는 컴퓨터 언어에 도움이 될 수 있습니다.

LC Left 코너 파서는 대체 문법 규칙의 왼쪽 끝을 인식하기 위해 LR Bottom-up 기술을 사용합니다.대체 방법이 단일 규칙으로 압축되면 파서는 나머지 규칙을 해석하기 위해 하향식 LL(1) 기술로 전환됩니다.LC 파서는 LALR 파서보다 해석 테이블이 작고 오류 진단 기능이 우수합니다.결정론적 LC 파서에 널리 사용되는 생성기는 없습니다.여러 파스의 LC 파서는 매우 큰 문법을 가진 인간의 언어에 도움이 됩니다.

이론.

LR 파서는 1965년 Donald Knuth에 의해 우선순위 파서의 효율적인 일반화로 발명되었습니다.Knuth는 LR 파서가 최악의 ^{[citation needed]}경우에도 여전히 효율적일 수 있는 가장 범용적인 파서라는 것을 증명했습니다.

"^[8]LR(k) 문법은 기본적으로 문자열 길이에 비례하는 실행 시간으로 효율적으로 구문 분석할 수 있습니다."

모든 k11에 대해, "언어가 결정론적(및 문맥 자유)인 경우에만 LR(k) 문법에 의해 생성될 수 있습니다. LR(1) ^[9]문법에 의해 생성될 수 있는 경우 및 그 경우에만.

즉, 어떤 언어가 효율적인 원패스 파서를 가능하게 할 만큼 합리적이라면 LR(k) 문법으로 기술할 수 있습니다.그리고 그 문법은 항상 동등한 (그러나 더 큰) LR(1) 문법으로 기계적으로 변환될 수 있습니다.따라서 이론적으로 LR(1)의 구문 분석 방법은 어떤 합리적인 언어도 처리할 수 있을 만큼 강력했습니다.실제로 많은 프로그래밍 언어의 자연 문법은 LR(1)^{[citation needed]}에 가깝습니다.

Knuth가 기술한 표준 LR 파서는 상태가 너무 많고 그 시대의 컴퓨터 메모리에 비해 매우 큰 파싱 테이블을 가지고 있었습니다.LR 해석은 Frank DeRemer가 훨씬 적은 상태의 ^[10][11]SLR 및 LALR 파서를 발명하면서 실용화되었습니다.

LR 이론과 LR 파서가 문법에서 어떻게 파생되는지에 대한 자세한 내용은 해석, 번역 및 컴파일 이론, Volume 1(Aho 및 Ullman)^[7][2]을 참조하십시오.

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

LR(k) 문법은 모든 k11에 대해 동일한 생성력을 가지지만 LR(0) 문법은 약간 다릅니다.언어 L은 L ^[12]내의 단어가 L 내의 다른 단어의 적절한 프레픽스일 경우 프리픽스 속성을 ^[13]갖는다고 한다.언어 L은 L이 프리픽스 속성을 갖는 결정론적 컨텍스트 프리 언어일 경우에만 LR(0) 문법을 가진다.따라서 L$가 LR(0) 문법을 가지고 있는 경우에만 L 언어는 결정론적 문맥이 없습니다. 여기서 "$"는 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

액션 테이블과 goto 테이블

이 문법의 2개의 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			액세스
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

액션 테이블은 파서와 단말기(입력 스트림의 끝을 나타내는 특별한 단말기 $ 포함)의 상태에 의해 인덱싱되며 다음 3가지 유형의 액션이 포함됩니다.

• shift. 이는 'sn'로 쓰여져 있으며 다음 상태가 n임을 나타냅니다.
• reduce(rm)는 'rm'으로 표기되며 문법 규칙 m을 사용하여 축소를 수행해야 함을 나타냅니다.
• accept는 'acc'로 표기되며 파서가 입력 스트림의 문자열을 받아들인다는 것을 나타냅니다.

goto 테이블은 파서와 비단말기 상태에 의해 인덱싱되며 특정 비단말기를 인식했을 경우 파서의 다음 상태가 어떻게 되는지 단순히 나타냅니다.이 표는 매번 감소 후 다음 상태를 확인하는 데 중요합니다.리덕션 후, 스택의 톱(즉, 현재 상태)과 리덕션 규칙의 LHS(즉, 비터미널)에 대한 goto 테이블엔트리를 검색함으로써 다음 상태를 찾습니다.

해석 단계

다음 표는 프로세스의 각 단계를 보여줍니다.여기서 상태는 스택의 맨 위에 있는 요소(최우측 요소)를 참조하고, 다음 액션은 위의 액션테이블을 참조하여 결정됩니다.스트림의 끝을 나타내기 위해 입력 문자열에 $가 추가됩니다.

주	입력 스트림	출력 스트림	스택	다음 액션
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'입니다.다음 작업(시프트, 감소, 수락 또는 오류)을 찾기 위해 작업 테이블이 현재 상태("현재 상태"는 스택 상단에 있는 모든 상태임)와 현재 입력 기호인 '1'로 인덱싱됩니다.액션 테이블은 상태2로의 이행이 지정되어 있기 때문에 상태2가 스택에 푸시됩니다(모든 상태 정보가 스택에 있기 때문에 상태2로의 이행은 2를 스택에 푸시하는 것과 같습니다).결과 스택은 다음과 같습니다.

[0 '1' 2]

여기서 스택의 맨 위는 2입니다.엄밀하게 말하면 스택의 일부가 아니지만 다음 상태로의 전이를 일으킨 기호(예: '1', B)를 설명한다.

상태 2에서 액션테이블은 문법 규칙 5에 따라 줄이라고 합니다(입력 스트림에서 파서가 보는 단말기에 관계없이). 즉, 파서는 규칙 5의 오른쪽을 인식한 것입니다.이 경우 파서는 출력 스트림에 5를 쓰고 스택에서1개의 스테이트를 팝하고(규칙의 우측에1개의 심볼이 있기 때문에), 스테이트 0 및 B에 대해 goto 테이블의 셀에서 스테이트를 푸시합니다(스테이트 4).결과 스택은 다음과 같습니다.

[0 B 4 ]

단, 스테이트 4에서는 액션테이블에 의해 파서가 규칙3에 의해 감소한다고 기재되어 있습니다.따라서 출력 스트림에 3을 쓰고 스택에서1개의 상태를 팝하여 상태 0과 상태 E의 goto 테이블에서 새로운 상태(상태 3)를 찾습니다.결과 스택:

[0 E 3 ]

파서에 표시되는 다음 단말기는 '+'이며 액션테이블에 따라 상태6이 됩니다

[0 E 3 '+' 6]

결과 스택은 비단말기 E에 이어 단말기 '+'를 읽은 유한 상태 오토마톤의 이력으로 해석될 수 있습니다.이 자동의 전환 테이블은 작업 테이블의 이동 작업과 goto 테이블의 이동 작업으로 정의됩니다.

다음 단자는 '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의 goto 상태를 검색하여 상태 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 → have 형식의 규칙에는 단 하나의 항목 A → •가 있다.예를 들어 항목 E → E • + B는 파서가 입력 스트림에서 E에 해당하는 문자열을 인식했으며 이제 '+' 뒤에 B에 해당하는 다른 문자열을 읽을 것으로 예상함을 나타냅니다.

아이템 세트

파서가 축소를 위해 어떤 규칙을 사용할지 미리 알 수 없기 때문에 일반적으로 단일 항목으로 파서 상태를 특성화할 수 없습니다.예를 들어, E → E * B 규칙도 있는 경우, E → E • + B 및 E → E • * B 항목이 모두 E에 해당하는 문자열을 읽은 후에 적용됩니다.따라서 파서의 상태를 항목 집합(이 경우 세트 {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'도 항목 집합에 포함되어야 한다.

항목 집합 닫기

따라서 점 앞에 있는 모든 비말단 항목이 설명될 때까지 해당 항목을 모두 반복적으로 추가함으로써 모든 항목 집합을 확장할 수 있습니다.최소 확장자를 항목 집합의 폐쇄라고 하며, 항목 집합인 경우 Clos(I)로 씁니다.이러한 닫힌 항목 세트는 파서의 상태로 간주되지만 실제로는 시작 상태에서 도달할 수 있는 항목 세트만 테이블에 포함됩니다.

증강 문법

다른 상태 간의 전이가 결정되기 전에 문법은 추가 규칙으로 보강됩니다.

(0) S → Eof

여기서 S는 새 시작 기호이고 E는 이전 시작 기호입니다.파서는 입력 문자열 전체를 받아들였을 때 정확히 이 규칙을 사용하여 축소를 수행합니다.

이 예에서는 위와 같은 문법이 다음과 같이 증강됩니다.

(0) S → Eof

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

이 증강문법을 위해 항목 세트와 항목 간의 전환이 결정됩니다.

테이블 구성

도달 가능한 항목 세트 및 항목 세트 간의 전환 찾기

테이블을 구성하는 첫 번째 단계는 닫힌 항목 집합 간의 전환을 결정하는 것으로 구성됩니다.이러한 전환은 터미널뿐만 아니라 터미널을 읽을 수 있는 유한 오토마톤을 고려하는 것처럼 결정됩니다.이 자동화의 시작 상태는 항상 추가된 규칙의 첫 번째 항목인 S → • E:를 닫는 것이다.

아이템 세트0

S → • EOF

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

항목 앞에 굵은 글씨로 표시된 "+"는 닫힘을 위해 추가된 항목을 나타냅니다(단말기인 수학적 '+' 연산자와 혼동하지 마십시오)."+"가 없는 원래 항목을 항목 집합의 커널이라고 합니다.

시작 상태(S0)에서 시작하여 이 상태에서 도달할 수 있는 모든 상태가 결정됩니다.항목 집합의 가능한 전환은 점 뒤에 있는 기호(단말 및 비단말)를 보면 알 수 있습니다. 항목 집합 0의 경우 이러한 기호는 단자 '0'과 '1' 및 비단말 E와 B입니다.$각$ $기호$ x$0$ {$$0 , $1$, $E$ , B $}$ { $textstyle$x \ $in$\ {$0$ , $1$, E , $B$\ } leads$$ to set that that that that that세트를 찾으려면 각 기호별로 다음 절차를 수행합니다.

1. 관심 기호 x 앞에 점이 있는 현재 항목 집합의 모든 항목 중 부분 집합 S를 취합니다.
2. S의 각 항목에 대해 점을 x의 오른쪽으로 이동합니다.
3. 결과 항목 집합을 닫습니다.

단자 '0'(즉, 여기서 x = '0')의 경우 다음과 같이 됩니다.

아이템 세트1

B → 0 •

단자 '1'(즉, 여기서 x = '1')의 경우 다음과 같은 결과가 된다.

아이템 세트 2

B → 1 •

그리고 비단자 E(즉, x = E)의 경우 다음과 같은 결과가 됩니다.

아이템 세트 3

S → E • e/

E → E • * B

E → E • + B

그리고 비단자 B(즉, x = B)의 경우 다음과 같이 됩니다.

아이템 세트 4

E → B •

폐쇄가 모든 경우에 새 항목을 추가하는 것은 아닙니다. 예를 들어 위의 새 집합에서는 점 뒤에 끝 이외의 항목이 없습니다.

더 이상 새로운 항목 세트가 발견되지 않을 때까지 위의 절차를 계속합니다.항목 세트 1, 2, 4의 경우 점이 기호 앞에 없으므로 전환이 없습니다.단, 3세트의 경우 터미널 '*'와 '+' 앞에 점이 있습니다.$기호$ x $=$* {\$textstyle$ x$=squaltext {*}}$의 경우 다음과 같이 전환됩니다.

아이템 세트 5

E → E * • B

+ B → • 0

+ B → • 1

x $=$+ {\$textstyle$ x$=substextt {+}}}$의 경우 다음과 같이 전환됩니다.

아이템 세트 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

작업 및 goto 테이블 구성

이 테이블과 발견된 항목 집합에서 액션 및 goto 테이블은 다음과 같이 구성됩니다.

1. 종단 이외의 컬럼은 goto 테이블에 복사됩니다.
2. 터미널 열은 이동 작업으로 작업 테이블에 복사됩니다.
3. S → w • eof 형식의 항목을 포함하는 모든 항목 집합에 대해 acc를 포함하는 작업 테이블에 '