표준 LR 파서

컴퓨터 과학에서 표준 LR 파서(canical LR parser) 또는 LR(1) 파서는 k=1에 대한 LR(k) 파서이며, 즉 단일 선행 단자가 있습니다.이 파서의 특별한 속성은 k>1의 모든 LR(k) 문법을 LR(1) ^[1]문법으로 변환할 수 있다는 것입니다.그러나 k를 줄이려면 역치환이 필요하며 역치환이 증가함에 따라 문법이 빠르게 크고 반복적이며 이해하기 어려울 수 있습니다.LR(k)는 모든 결정론적 컨텍스트프리 ^[1]언어를 처리할 수 있습니다.과거에는 이 LR(k) 파서는 LALR이나 LL(1) 파서 등 성능이 낮은 대체품을 위해 메모리 요건이 크기 때문에 회피되었습니다.그러나 최근에는 공간 요건이 LALR 파서에^{[citation needed]} 가까운 "최소 LR(1) 파서"가 여러 파서 생성기에 의해 제공되고 있습니다.

대부분의 파서와 마찬가지로 LR(1) 파서는 GNU Bison, MSTA, Menhir,^[2] HYACC,^[3][4] LRSTA와 같은 컴파일러에 의해 자동으로 생성됩니다.

역사

1965년 Donald Knuth는 기존 우선순위 파서의 일반화로서 시프트 리듀스 파서의 일종인 LR(k) 파서를 발명했다.이 파서는 모든 결정론적 문맥이 없는 언어를 인식할 수 있는 잠재력을 가지고 있으며 입력 파일에서 발생하는 문장의 왼쪽 및 오른쪽 파생을 모두 생성할 수 있습니다.Knuth는 k=1에 대한 최대 언어 인식력에 도달했음을 증명하고 LR(k), k > 1 문법을 LR(1) ^[1]문법으로 변환하는 방법을 제공했다.

표준 LR(1) 파서는 내부 파서 테이블 표현에 막대한 메모리 요건이 있다는 실질적인 단점이 있습니다.1969년 Frank DeRemer는 LALR과 SLR이라는 이름의 LR 파서의 두 가지 단순화된 버전을 제안했습니다.이러한 파서는 Canical LR(1) 파서보다 훨씬 적은 메모리를 필요로 하지만 언어 인식 능력이 약간 ^[5]떨어집니다.LALR(1) 파서는 LR 파서의 가장 일반적인 구현입니다.

그러나 LR(1) 파서의 새로운 유형인 "Minimal LR(1) 파서"는 1977년에 David Pager에 의해 도입되었습니다.David^[6] Pager는 LR(1) 파서의 메모리 요건과 동등한 LR(1) 파서를 만들 수 있음을 보여 줍니다.최근^[when?] 일부 파서 제너레이터는 메모리 요건 문제뿐만 아니라 LALR(1) 파서 제너레이터 ^{[citation needed]}고유의 알 수 없는 충돌 문제를 해결하는 Minimal LR(1) 파서를 제공하고 있습니다.또한 최소 LR(1) 파서는 시프트 축소 액션을 사용할 수 있으므로 표준 LR(1) 파서보다 빠릅니다.

개요

LR(1) 파서는 결정론적 자동화이므로 정적 상태 전이 테이블을 기반으로 합니다.이것들은, 인식되는 언어의 문법을 코드화해, 통상은 「파싱 테이블」이라고 불립니다.

LR(1) 파서의 해석 테이블은 미리 보기 터미널을 사용하여 파라미터화됩니다.LR(0) 파서에서 사용되는 것과 같은 단순한 구문 분석 테이블은 형식의 문법 규칙을 나타냅니다.

A1 → A B

즉, 입력 A에 이어서 B를 입력하면 다음에 무슨 일이 있어도 쌍을 A1로 줄일 수 있습니다.이러한 규칙을 미리 보고 매개 변수를 지정하면 다음과 같은 이점이 있습니다.

A1 → A B, a

즉, 선행 단말기가 a인 경우에만 감소가 수행됩니다.이를 통해 검색 컨텍스트에 따라 단순한 규칙이 다른 의미를 가질 수 있는 보다 풍부한 언어를 사용할 수 있습니다.예를 들어, LR(1) 문법의 경우, 같은 상태 시퀀스에 근거하고 있어도, 다음의 규칙은 모두 다른 리덕션을 실행합니다.

A1 → A B, a

A2 → A B, b

A3 → A B, c

A4 → A B, d

선행 단말기가 고려되지 않은 경우에는 이와 동일하지 않습니다.해석 오류는 일부 규칙을 오류로 선언함으로써 파서가 입력 전체를 읽을 필요 없이 식별할 수 있습니다.예를들면,

E1 → B C, d

에러라고 선언되어 파서가 정지할 가능성이 있습니다.즉, 다음 예시와 같이 사전 검색 정보를 사용하여 오류를 캐치할 수도 있습니다.

A1 → A B, a

A1 → A B, b

A1 → A B, c

E1 → A B, d

이 경우 룩어헤드(lookahead)가 a, b 또는 c일 경우 A B가 A1로 축소되고 룩어헤드(lookahead)가 d일 경우 오류가 보고됩니다.

미리 보기는 규칙을 줄일 시기를 결정하는 데도 유용합니다.룩어헤드(Lookahead)는 룩어헤드(Lookahead)가 유효하지 않은 경우 특정 규칙이 축소되는 것을 방지하는 데 도움이 됩니다.이는 현재 상태를 이전 상태가 아닌 다음 상태와 결합해야 함을 의미합니다.즉, 다음 예에서는

• 입력 시퀀스:A B C
• 규칙:

A1 → A B

A2 → B C

순서는 로 환원할 수 있다

A2

대신

A1 C

파서가 B 상태가 된 후 사전 조회가 허용되지 않는 경우, 즉 전환 규칙이 존재하지 않습니다.다음과 같이 터미널에서 직접 절감 효과를 얻을 수 있습니다.

X → y

여러 시퀀스를 표시할 수 있습니다.

LR(1) 파서는 각 규칙을 완전한 LR(1) 방식, 즉 특정 룩어헤드(lookahead)를 가진 두 상태의 시퀀스로 표현해야 한다는 요건을 가지고 있습니다.그 때문에, 다음과 같은 간단한 룰이러한 규칙은

X → y

기본적으로 모든 가능한 상태와 그에 따른 예측 단말기의 조합을 열거하는 수많은 인위적인 규칙을 필요로 한다.다음과 같은 비예측 규칙을 구현하는 경우에도 유사한 문제가 발생합니다.

A1 → A B

가능한 모든 룩어헤드를 열거해야 합니다.이것이 LR(1) 파서가 실질적으로 구현될 수 없는 이유입니다.메모리의 대폭적인 ^[6]최적화 없이는.

LR(1) 구문 분석 테이블 구성

LR(1) 구문 분석 테이블은 LR(0) 구문 분석 테이블과 동일한 방식으로 구성되며 각 항목에 사전 검색 터미널이 포함되도록 수정됩니다.즉, LR(0) 파서와 달리 처리할 항목에 다른 단말기가 뒤따를 경우 다른 액션이 실행될 수 있습니다.

파서 항목

언어의 생산 규칙에서 시작하여 먼저 이 언어의 항목 세트를 결정해야 합니다.쉽게 말해 항목 세트는 현재 처리된 기호가 포함될 수 있는 생산 규칙 목록입니다.아이템 세트는 파서 상태에 일대일 대응관계를 가지며, 세트 내의 아이템은 다음 심볼과 함께 어떤 상태 전이 및 파서 액션을 적용해야 하는지를 결정하기 위해 사용된다.각 항목에는 현재 처리된 기호가 해당 항목이 나타내는 규칙에 나타나는 시점을 나타내는 마커가 포함되어 있습니다.LR(1) 파서의 경우 각 항목은 선행 단말기에 고유하기 때문에 선행 단말기도 각 항목 내부에 기록되었습니다.

예를 들어 터미널 기호 'n', '+', '(', '), 비터미널 'E', 'T', 시작 규칙 'S' 및 다음 생산 규칙으로 구성된 언어를 가정해 보겠습니다.

S → E

E → T

E → (E )

T → n

T → + T

T → T + n

항목 세트는 LR(0) 파서의 절차와 유사하게 생성됩니다.초기 상태를 나타내는 항목 집합 0이 시작 규칙에서 생성됩니다.

[S → • E, $]

점 '•'은 이 규칙 내에서 현재 구문 분석 위치의 마커를 나타냅니다.이 규칙을 적용하기 위해 예상되는 선행 검색 터미널은 쉼표 뒤에 표시됩니다.'