시프트-리듀스 파서

시프트-리듀스 파서는 컴퓨터 언어와 문법에 의해 공식적으로 정의된 다른 명세에 대한 효율적이고 테이블 기반의 상향식 파싱 방법의 클래스다.프로그래밍 언어의 파싱에 가장 일반적으로 사용되는 파싱 방법인 LR 파싱과 그 변동은 시프트 감소 방법이다.^[1]LR파싱이 발명되기 전에 사용된 우선파수 역시 시프트-리듀스 방법이다.모든 시프트-리듀스 파서들은 파스 트리를 만들거나 특정 출력 동작을 호출하는 증분 순서로 유사한 외부 효과를 가진다.

개요

Shift-Reduce 파서 스캔을 줄이고 입력 텍스트를 백업하지 않고 텍스트 위로 한 번의 전진 패스로 파싱한다.파서(parser)는 추측이나 역추적 없이 파스 트리를 점진적으로, 아래 위로, 왼쪽에서 오른쪽으로 쌓는다.이 패스의 모든 지점에서 파서는 이미 구문 분석된 입력 텍스트의 하위 트리 또는 구문 목록을 누적한다.파서가 아직 이들을 결합시킬 구문 패턴의 오른쪽 끝에 도달하지 않았기 때문에 그 하위 트리는 아직 결합되지 않았다.

문자열 고려A = B + C * 2.

예제의 7단계에서는 "A = B +"만 구문 분석하였다.파스 트리의 음영 처리된 왼쪽 하단 구석만 존재한다.8개 이상의 파스 트리 노드가 아직 존재하지 않는다.노드 1, 2, 6, 7은 항목 1..7을 모두 포함하는 격리된 하위 트리의 루트다.노드 1은 변수 A, 노드 2는 구분 기호 =, 노드 6은 합계 B, 노드 7은 연산자 +이다.이 네 개의 루트 노드는 임시로 파스 스택에 저장된다.입력 스트림의 나머지 비포함 부분은 "C * 2"이다.

Shift-Reduce 파서는 Shift step과 Reduced step의 일부 조합으로 작동하며, 따라서 명칭을 사용한다.

• Shift 단계는 하나의 기호로 입력 스트림에서 전진한다.이동된 기호는 새로운 단일 노드 파스 트리가 된다.
• 축소 단계는 완성된 문법 규칙을 최근의 파스 나무들 중 일부에 적용하여, 그것들을 새로운 뿌리 기호가 있는 하나의 나무로 결합한다.

파서는 모든 입력을 소비하고 모든 파스 트리가 전체 법적 입력을 나타내는 단일 트리로 축소될 때까지 이러한 단계를 계속한다.

나무 쌓기 단계

구문 분석 단계마다 전체 입력 텍스트는 구문 분석 스택, 현재 룩어헤드 기호 및 나머지 비분석 텍스트로 나뉜다.파서의 다음 동작은 가장 오른쪽 스택 기호와 룩어헤드 기호에 의해 결정된다.이 작업은 스택과 룩어헤드 기호의 모든 구문론적으로 유효한 조합을 포함하는 표에서 읽힌다.

스텝	파스 스택	보라 앞에	언애너드	파서 액션
0	텅 빈	id	= B + C*2	시프트
1	id	=	B + C*2	시프트
2	id =	id	+ C*2	시프트
3	id = id	+	C*2	값 ← id로 감소
4	id = 값	+	C*2	제품별 감소 ← 가치
5	id = 제품	+	C*2	총계별 감소 ← 제품
6	id = 합계	+	C*2	시프트
7	id = 합 +	id	*2	시프트
8	id = 합 + id	*	2	값 ← id로 감소
9	id = 합 + 값	*	2	제품별 감소 ← 가치
10	id = 합계 + 제품	*	2	시프트
11	id = 합계 + 제품 *	인트로	eof	시프트
12	id = 합계 + 제품 * int	eof		가치별 감소 int int
13	id = 합계 + 제품 * 값	eof		제품별 감소 ← 제품 * 가치
14	id = 합계 + 제품	eof		합계 ← 합계 + 제품별로 감소
15	id = 합계	eof		← id 할당을 통해 감소 = 합계
16	할당하다	eof		끝

더 간단한 예는 을 참조하십시오.

그라마르스

문법은 입력 언어에 대한 패턴 또는 구문 규칙의 집합이다.그것은 전체 프로그램의 맥락에서 숫자의 크기, 또는 이름과 그 정의의 일관성 있는 사용과 같은 모든 언어 규칙을 다루지 않는다.시프트-리듀스 파서들은 국부적인 기호 패턴만을 다루는 문맥 없는 문법을 사용한다.

일치하는 Java 또는 C 언어의 작은 부분 집합으로서 문법의 예A = B + C*2다음과 같을 수 있다.

← id 할당 = 합계

합계 ← 합계 + 제품

Sums products

제품 ← 제품 * 가치

제품 ← 가치

값 ← int

값 ← id

문법의 단자 기호는 어휘 스캐너에 의해 입력 스트림에서 발견되는 다문자 기호 또는 '토큰'이다.여기에는 정수 상수에 대한 = + * 및 int와 식별자 이름에 대한 ID가 포함된다.문법은 int 값이나 id 철자가 무엇인지는 신경 쓰지 않고, 빈칸이나 줄 바꿈도 신경 쓰지 않는다.문법은 이러한 단자 기호를 사용하지만 그것을 정의하지는 않는다.그들은 항상 파스 나무의 맨 아래쪽에 있다.

Sums와 같이 대문자로 표기된 용어는 비단어적 상징이다.이것들은 언어의 개념이나 패턴을 나타내는 이름이다.그것들은 문법에 정의되어 있고 입력 스트림에서는 결코 저절로 발생하지 않는다.그들은 항상 파스나무 밑바닥 위에 있다.그것들은 파서가 문법 규칙을 적용한 결과일 뿐이다.일부 비터미널은 두 개 이상의 규칙으로 정의된다; 이것들은 대체 패턴이다.규칙은 스스로에게 되돌아갈 수 있다.이 문법은 반복적인 수학 연산자를 다루기 위해 반복적인 규칙을 사용한다.전체 언어에 대한 그래머는 재귀적 규칙을 사용하여 목록, 괄호화된 표현식 및 중첩된 문을 처리한다.

주어진 컴퓨터 언어는 여러 가지 다른 문법들로 설명할 수 있다.시프트-리듀스 파서의 문법은 그 자체로 명확해야 하며, 또는 동점선호 규칙에 의해 강화되어야 한다.이것은 언어의 주어진 법적 예에 문법을 적용하는 단 하나의 올바른 방법이 있다는 것을 의미하며, 그 예에 대해 고유한 파스 트리와 독특한 시프트/감소 작용의 순서를 초래한다.

테이블로 움직이는 파서는 문법에 대한 모든 지식을 파서 테이블이라 불리는 불변의 데이터로 부호화한다.파서의 프로그램 코드는 많은 문법이나 언어에 변하지 않고 적용되는 단순한 일반 루프다.그 표들은 우선순위 방법을 위해 손으로 작성될 수 있다.LR 방법의 경우, 복잡한 표는 바이슨과 같은 일부 파서 발생기 도구에 의해 기계적으로 문법에서 파생된다.^[3]파서 테이블은 보통 문법보다 훨씬 크다.재귀적 강하와 같이 테이블 구동이 아닌 다른 파서에서는 각 언어 구문을 다른 서브루틴에 의해 파싱되며, 그 하나의 구문에 특화되어 있다.

파서 작업

시프트-리듀스 파서는 백업이 필요 없기 때문에 효율적이다.총 실행 시간은 입력 길이와 전체 구문 분석 트리의 크기에 따라 선형적으로 조정된다.역추적하는 다른 파서 방법은 그들이 잘못 추측했을 때 기하급수적인 시간이 걸릴 수 있다.^{[citation needed]}

추측을 피하기 위해 Shift-Reduce 파서는 이전에 스캔한 기호로 무엇을 할지 결정하기 전에 다음 스캔한 기호를 (좌우 텍스트의 오른쪽) 앞으로 보는 경우가 많다.어휘 스캐너는 나머지 파서 앞에 하나의 기호를 사용한다.룩어헤드 기호는 각 파싱 결정을 위한 '우측 컨텍스트'라고도 불린다. (대부분의 실용적인 그래머는 룩어헤드 기호를 사용하도록 설계될 수 있지만, 두 개 이상의 룩어헤드 기호를 사용할 수 있다.)

Shift-Reduce 파서는 조합된 구문이 무엇인지 커밋하기 전에 일부 구문의 모든 부분을 스캔하고 구문 분석할 때까지 기다린다.그러면 파서는 더 이상 기다리지 않고 즉시 조합에 따라 행동한다.위의 파스 트리 예에서 구문 B는 파스 트리의 그러한 부분을 정리하기 위해 더 이상 기다리지 않고 룩어헤드에서 +가 보이자마자 가치로 축소되고 3-6단계의 Products and Sums로 감소한다.B를 어떻게 처리할 것인가 하는 결정은 훨씬 뒤에 오른쪽에서 나타나는 것들을 고려하지 않고 파서와 스캐너가 이미 본 것에 근거한다.

감소는 가장 최근에 구문 분석된 것, 즉 룩어헤드 기호의 바로 왼쪽에 있는 것들을 재구성한다.그래서 이미 포장된 것들의 목록은 쌓이는 것과 같은 역할을 한다.이 파스 스택은 오른쪽으로 자란다.스택의 밑부분이나 밑부분은 왼쪽에 있고 가장 왼쪽, 가장 오래된 파스 조각을 가지고 있다.모든 감소 단계는 가장 오른쪽 최신 파스 조각에만 작용한다.(이 누적 파스 스택은 하향식 파서들이 사용하는 예측, 좌향 성장 파스 스택과는 매우 다르다.)

다음과 같은 문법 규칙이 있을 때

제품 ← 제품 * 가치

적용되고, 스택 탑이 파스 트리를 잡고 있다...제품 * 가치".이 규칙의 오른편에서 발견된 예를 손잡이라고 한다.감소 단계는 손잡이 "제품 * 값"을 좌측 비단자(이 경우 더 큰 제품)로 대체한다.파서가 완전한 파스 트리를 만드는 경우, 내부 제품, * 및 가치에 대한 세 개의 트리가 더 큰 제품을 위한 새로운 트리 루트에 의해 결합된다.그렇지 않으면 내부 제품 및 가치의 의미 세부 정보가 일부 후기 컴파일러 패스로 출력되거나 새로운 제품 기호에 결합되어 저장된다.^[4]

파서는 거기서 새로 완성된 문법 규칙의 예를 계속 찾아내는 한 계속해서 파스 스택의 맨 위에 감소를 적용한다.더 이상 규칙을 적용할 수 없으면 파서는 룩어헤드 기호를 파스 스택으로 옮기고 새로운 룩어헤드 기호를 스캔한 후 다시 시도한다.

Shift-Reduce 파서의 유형

파서 표는 최상위 파서 스택 기호와 룩어헤드 기호의 모든 법적 조합에 대해 다음에 수행할 작업을 보여준다.그 다음 행동은 반드시 독특해야 한다; 이동하거나 축소하거나 둘 다가 아니라. (이는 모호하지 않은 것을 넘어 문법에 대한 몇 가지 추가적인 한계를 내포하고 있다.테이블 디테일은 시프트-리듀스 파서 유형에 따라 크게 다르다.

우선 구문 분석기에서 핸들의 오른쪽 끝은 상단 스택 기호의 우선 순위 수준 또는 문법 조임 정도를 룩어헤드 기호의 그것과 비교함으로써 발견된다.위의 예에서 int와 id는 문장 구분 기호 ;에 비해 내부 문법 수준에 속한다.따라서 int와 id는 둘 다 ;보다 높은 우선순위로 간주되며;가 뒤따를 때마다 다른 것으로 감소되어야 한다.핸들의 왼쪽 끝을 찾고 적용할 올바른 규칙을 선택하는 방법이 각각 다른 선순위 파서가 있다.

• 연산자 프리덴스 파서(Operator-prepresence parser)는 표현에 대해 작동하지만 일반적인 프로그램 구문은 작동하지 않는 매우 간단한 숫자 방법이다.
• 단순 우선 순위 분석기, 하나의 큰 MxN 테이블을 사용하여 오른쪽과 왼쪽 끝을 찾는다.PL360에 사용된다.^[5]공통 프로그래밍 언어를 처리하지 않음.
• 취약한 우선 순위 구문 분석기, 핸들의 오른쪽 끝을 찾기 위해 우선 순위 표만 사용한다.단순 우선 순위보다 많은 그래머를 처리한다.^[6]
• 확장된 우선 순위 분석기.

• XPL의 원래 버전에서 사용되는 혼합 전략 우선 순위 구문 분석기.모든 우선 순위 인식기에 내재된 "문제"를 "삼중"으로 확장한다.SLR보다 강력하지 않다.일반적으로 XPL 자체와 같이 비교적 작은 언어에도 매우 큰 표를 가지고 있는데, 이는 우선 방법에 의해 부과된 한계를 벗어나는 그래머를 인식해야 하는 매우 많은 "트리플" 때문이다.^[7]

우선순위 파서들은 그들이 다룰 수 있는 문법들에 제한되어 있다.그들은 결정을 내릴 때 대부분의 파스 스택을 무시한다.그들은 문법에서 그 기호들이 현재 나타나는 전체 문맥이 아니라 가장 위에 있는 기호들의 이름만을 고려한다.우선순위는 유사해 보이는 기호 조합은 문법 전체에 걸쳐 동일한 방법으로 구문 분석 및 사용해야 하지만 문맥에 관계없이 조합이 이루어진다.

LR 파서는 더 많은 그래머를 처리하면서 시프트-듀스 파싱의 더 유연한 형태다.^[8]

LR 파서 처리

LR 파서들은 각 교대조 또는 감소 작용에 대한 상태 전환을 수행하는 상태 기계와 같은 기능을 한다.이들은 교대조 작용에 의해 현재 상태가 밀리는 스택을 사용한다.그러면 이 스택은 감소 작용에 의해 튀어 오른다.이 메커니즘은 LR 파서가 모든 결정론적 맥락 없는 그래머를 처리할 수 있도록 하며, 이는 우선 순위 그래머의 상위 집합이다.LR 파서는 표준 LR 파서에 의해 완전히 구현된다.Look-Ahead LR 및 Simple LR 파서들은 메모리 요구 사항을 크게 줄인 단순화된 변형을 구현한다.^[9][10]최근의 연구에서는 크누스의 테이블 구축 알고리즘에 대한 테이블 요건을 대폭 줄여서 표준 LR 파서를 구현할 수 있는 방법을 밝혀냈다.^[11]

LR이든, LALR이든, SLR이든, 기본 상태 기계는 같다; 테이블만 다르고, 이 테이블들은 거의 항상 기계적으로 생성된다.또한, 이러한 표들은 REVENT가 상태 기계 외부에 있는 폐쇄 서브루틴에 대한 CTALL을 초래하고 REVENd인 문법 규칙의 의미론에서 암시하는 기능을 수행하는 것과 같이 보통 구현된다.따라서 파서는 불변 상태 기계 부분과 변종 의미 기계 부분으로 분할된다.이러한 근본적인 구분이 유달리 신뢰할 수 있는 고품질 파서들의 개발을 장려한다.

특정 스택 상태와 룩어헤드 기호가 지정되면 정확히 오류, 시프트, 감소, 정지(이하 구성이라 한다)의 네 가지 가능한 동작이 있다.구성에서 점 존재, • 점의 존재는 점의 오른쪽에 룩어헤드 기호가 표시되고(그리고 항상 터미널 기호에 해당), 점의 왼쪽에 현재 스택 상태가 표시되며(그리고 일반적으로 비터미널 기호에 해당함) 현재 룩어헤드 위치를 나타낸다.

더 높은 성능을 포함한 실용적인 이유로 테이블은 대개 다소 큰 2비트 기호의 보조 배열에 의해 확장되며, 바이트 지향 기계의 효율적인 접근을 위해 4개의 2비트 기호와 1바이트로 압축되며, 종종 다음과 같이 암호화된다.

00b는 ERROR를 나타낸다.

01b는 SHIFT를 나타낸다.

10b는 REVEN을 나타낸다.

11b는 STOP을 나타낸다.

(STOP은 SHIFT의 특별한 케이스가 된다.)일반적으로 전체 배열은 대부분 ERROR 구성, 문법적으로 정의된 SHIFT 및 ROWN 구성 수, 하나의 STOP 구성을 포함한다.

XPL과 같이 4분위수 시스템(기본 4, 2분위수당 2비트)의 값 사양을 지원하는 프로그래밍 시스템에서 이러한 값들은 예를 들어 다음과 같이 코딩된다.

"(2)……0…"은 ERROR를 나타낸다.

"(2)……1"은 SHIFT를 나타낸다.

"(2)……2…"는 REVENT를 나타낸다.

"(2)……3"은 STOP을 나타낸다.

SHIFT 및 REVENT 테이블은 어레이와 별도로 구현된다.보조 배열은 현재 상태 및 룩어헤드 기호에 대해서만 "프로브"된다.(보조) 배열이 "완전"인 반면, (이동 및 감소) 표는 실제로 매우 "분산"할 수 있으며, 그러한 SHIFT 및 REVENT 표의 최적 "배분"을 통해 상당한 효율을 달성할 수 있다(오류 및 STOP은 표 필요 없음).

SHIFT-REDUce 파서의 기본 정의에서 SHIFT와 RENSE 구성은 명백하다.

그러면 STOP은 스택의 맨 위에 있는 상태와 룩어헤드 터미널 기호가 주제 문법 내에 있는 구성을 나타내며 프로그램의 끝을 나타낸다.

⊥ <프로그램> • ⊥

개념적으로 도달하기 위해 최종 ⊥ 이상으로 SHIFT하는 것은 불가능하다.

⊥ <프로그램> ⊥ •

그러면 오류는 스택의 맨 위에 있는 상태와 룩어헤드 터미널 기호가 주제 문법 내에 없는 구성을 나타낸다.이것은 아마도 가장 단순한 형태로 오류 복구 절차를 호출하여 lookahead 터미널 기호를 삭제하고 다음 터미널 기호를 읽을 수 있는 기회를 제공하지만, 스택을 제거하거나 lookahead 터미널 기호를 폐기하고 스택(및 병리학)을 제거하는 등 다른 많은 프로그래밍된 작업이 가능하다.l case, 보통 얻을 수 있다.

⊥ <프로그램> • ⊥

여기서 <프로그램>은 오직 "진술서"로만 구성된다.

대부분의 경우 스택은 의도적으로 사전 로드(즉, 초기화됨)되며

⊥ • <프로그램> ⊥

여기서 초기의 ⊥은 이미 인정된 것으로 가정한다.그러면 이는 프로그램의 시작을 나타내며, 따라서 개념적으로 별도의 START 구성을 갖는 것을 방지한다.

• ⊥ <프로그램> ⊥

⊥은 문법에 기계적으로 첨가된 특별한 사이비-비-단어 기호인 것처럼, 문법에 기계적으로 첨가된 특별한 사이비-비-단어 기호(프로그래머가 문법에 <프로그램>을 명시적으로 포함하지 않았다면, 프로그래머를 대신하여 <프로그래밍>이 자동으로 문법에 추가될 것이다.

분명히, 그러한 파서는 정확히 하나의 (불확실한) START 구성과 하나의 (명확한) STOP 구성을 가지고 있지만, 그것은 대개 수백 개의 SHIFT 및 ROWRN 구성과 아마도 수천 개의 ERROR 구성을 가질 수 있다.

참조