심플 LR 파서
Simple LR parser |
컴퓨터 공학에서 단순 LR 또는 SLR 파서는 작은 파스 테이블과 비교적 단순한 파서 발생기 알고리즘을 가진 LR 파서의 일종이다.다른 유형의 LR(1) 파서와 마찬가지로, SLR 파서는 입력 스트림을 통한 단일 좌우 스캔에서 추측이나 역추적 없이 단일의 정확한 상향 파스를 찾는 데 상당히 효율적이다.파서는 그 언어를 위한 공식적인 문법에서 기계적으로 생성된다.
SLR과 보다 일반적인 방법인 LALR 파서와 표준 LR 파서는 파싱 시 동일한 방법과 유사한 표를 가지고 있다. 파서 생성기 도구에 사용되는 수학적 문법 분석 알고리즘에서만 다르다.SLR과 LALR 발전기는 동일한 크기와 파서 상태의 표를 만든다.SLR 발전기는 yacc나 Bison과 같은 LALR 발전기보다 더 적은 그래머를 받아들인다.많은 컴퓨터 언어가 지금처럼 SLR의 제약을 쉽게 맞추지 못한다.언어의 자연 문법을 SLR 문법 형태로 구부리는 것은 더 많은 타협과 문법 해킹을 필요로 한다.그래서 LALR 발전기는 다소 복잡한 도구임에도 불구하고 SLR 발전기보다 훨씬 더 널리 사용되게 되었다.SLR 방법은 컴파일러 이론에 대한 대학 수업에서 유용한 학습 단계로 남아 있다.
SLR과 LALR은 모두 Frank DeRremer에 의해 도날드 크누스의 LR 파서 이론의 첫 번째 실제 사용으로 개발되었다.[citation needed]완전한 LR 방법에 의해 실제 그래머를 위해 만들어진 표는 그 10년의 대부분의 컴퓨터 메모리보다 더 큰 비실용적으로 크며, SLR 및 LALR 방법보다 100배 또는 더 많은 파서 상태를 가지고 있었다.[citation needed]
룩어헤드 세트
SLR과 LALR의 차이점을 이해하려면, SLR과 LALR의 많은 유사점과 둘 다 교대조 감소 결정을 내리는 방법을 이해하는 것이 중요하다. (그 배경은 지금 기사 LR 파서 참조)
SLR과 LALR의 한 가지 차이점은 완성된 생산 규칙이 발견되고 감소될 때마다 발전기가 다음에 나타나야 하는 입력 기호의 룩어헤드 세트를 계산하는 방법이다.
SLR 발생기는 개별 파서 상태와 전환의 세부사항을 무시한 채 문법에 기초하여 직접 쉬운 근사법으로 그 모양을 계산한다.이것은 현재 파서 상태의 특정 컨텍스트를 무시한다.일부 비단어 기호 S가 문법상의 여러 곳에서 사용된다면, SLR은 그 장소들을 개별적으로 다루기보다는 동일한 단일한 방법으로 처리한다.SLR 발전기가 작동함Follow(S)S의 발생을 즉시 따를 수 있는 모든 단자 기호의 집합.구문 분석표에서 S에 대한 각 감소는 LR(1) 룩어헤드 집합으로 팔로우(S)를 사용한다.이러한 후속 세트는 LL 하향 파서용 발전기에도 사용된다.후속 세트를 사용할 때 시프트/축소 또는 충돌을 줄이지/축소하지 않는 문법을 SLR 문법이라고 한다.
LALR 발생기는 파서 상태 및 변환 그래프를 탐색하여 보다 정밀한 방법으로 룩어헤드 세트를 계산한다.이 방법은 현재 파서 상태의 특정 맥락을 고려한다.일부 비단어 S의 문법 발생 시마다의 처리를 커스터마이징한다.이 계산에 대한 자세한 내용은 문서 LALR 파서를 참조하십시오.LALR 발전기가 계산한 룩어헤드 집합은 SLR 발전기가 계산한 근사 집합의 하위 집합이다(따라서 SLR 발전기가 계산한 집합보다 좋다).SLR follows 세트를 사용할 때 문법이 테이블 충돌은 있지만 LALR follow 세트를 사용할 때 충돌이 없는 경우, 이를 LALR 문법이라고 한다.
예
SLR 파서로 구문 분석할 수 있지만 LR(0) 파서로 구문 분석할 수 없는 문법은 다음과 같다.
- (0) S → E
- (1) E → 1 E
- (2) E → 1
LR(0) 파서에 대해 수행된 작업과 goto 테이블을 구성하면 다음과 같은 항목 세트와 테이블이 제공된다.
- 항목 집합 0
- S → • E
- + E → • 1 E
- + E → • 1
- 품목세트1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- 아이템 세트 2
- S → E •
- 아이템 세트 3
- E → 1 E •
작업 및 goto 테이블:
| 액션 | 에 가다 | ||
|---|---|---|---|
| 주 | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1/r2 | r2 | 3 |
| 2 | 악센트를 붙이다 | ||
| 3 | r1 | r1 | |
관찰할 수 있듯이 상태 1과 터미널 '1'에 대해 시프트-감축 충돌이 있다.이는 LR(0) 구문 분석기에 대한 작업 테이블을 만들 때 행 단위로 축소 작업이 삽입되기 때문이다.그러나 추적 세트를 사용하면 축소 작업을 보다 세분화하여 추가할 수 있다.이 문법에 대한 다음 집합:
| 심볼 | S | E | 1 |
|---|---|---|---|
| 뒤따르는 | $ | $ | 1,$ |
특정 조치 열에 해당 조치가 해당 감소와 관련된 후속 조치 집합에 있는 경우에만 감소를 추가하면 된다.이 알고리즘은 감소 동작을 동작 열에 추가해야 하는지 여부를 설명한다.
함수 mustBeAdded(reduceAction, action) { ruleNumber = recreteAction.value; ruleSymbol = ruleNumber.LeftHandSide; return (followSet(규칙 Symbol)의 동작) } 예를 들어,mustBeAdded(r2, "1")규칙 2의 왼손은 "E"이고, 1은 E의 추종 집합에 없기 때문에 거짓이다.반대로,mustBeAdded(r2, "$")"$"는 E의 추종 집합에 있기 때문에 사실이다.
작업 테이블의 각 축소 작업에 mustBeAdded를 사용하면 충돌 없는 작업 테이블이 된다.
| 액션 | 에 가다 | ||
|---|---|---|---|
| 주 | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 | r2 | 3 |
| 2 | 악센트를 붙이다 | ||
| 3 | r1 | ||
