LALR 파서 및 미리보기

Question

전혀 이유없이 LALR 구문 분석 테이블을 자동으로 구현하고 있습니다. 이 파서에는 LALR (0)과 LALR (1)의 두 가지 맛이 있습니다. 여기서 숫자는 미리보기 양을 나타냅니다.

저는 미리보기 의미에 대해 혼란스러워했습니다.

입력 스트림이 'abc'이고 다음 제작물이있는 경우 0 선행 또는 1을 사용해야합니까?

 
    P :== a E 

같은 질문이지만 입력에서 'a'만보고 올바른 P 제작을 미리 선택할 수는 없습니다.

 
    P :== a b E 
     | a b F 

LALR 파서 생성기를 만들 때 후반 P- 제작이 실제로 발생하지 않는다는 점에서 나는 혼란을 겪고 있습니다. 그 이유는 클로저를 계산할 때 문법이 효과적으로 자동으로 왼쪽으로 계산된다는 것입니다.

나는 working through this page이었고 첫 번째/따라 가기까지 괜찮 았습니다. 여기 내 문제는 을으로 계산하는 것이므로 내 머리 속에서 이것을 추상화하는 데 어려움이 있습니다.

는 거의 모양 미리가 입력을 이동 관련이없는 것으로 생각을하지만, 대신 결정에 에를 줄일 때.

나는 드래곤 책을 읽었지 만, 타란티노 스크립트만큼 선형 적입니다. 이미이 작업을 수행하는 방법을 알고있는 사람들에게 훌륭한 참고 자료 인 것 같습니다.

Answer 1

상향식 파싱 (예 : LALR)에 대해 배울 때 가장 먼저해야 할 일은 하향식 파싱과 완전히 다르다는 점을 기억하는 것입니다. 하향식 구문 분석은 프로덕션의 왼쪽 (LHS) 인 비 터미널 (nonterminal)에서 시작하여 사용할 오른쪽 (RHS)을 추측합니다. 반면에 Bottom-up 파싱은 RHS를 식별하여 시작하고 어떤 LHS를 선택할지 계산합니다.

더 자세히 말하면, 상향식 파서는 오른쪽이 대기열의 오른쪽 끝에있을 때까지 수신 토큰을 대기열에 누적합니다. 그런 다음 은 해당 RHS로 대체하여 RHS를으로 줄이고 적절한 RHS가 수정 된 누적 입력의 오른쪽 가장자리에 있는지 확인합니다. 입력에서 해당 지점에서 더 이상 축소가 발생하지 않을 때까지 계속 수행 한 다음 새 토큰을 읽습니다. (즉, 다음 입력 토큰을 가져 와서 을으로 바꿉니다. 큐).

이것은 마지막 토큰을 읽고 가능한 모든 축소가 수행 될 때까지 계속됩니다.이 시점에서 남은 것이 "시작 심볼"인 단일 비 터미널이면 해석을 허용합니다.

파서가 현재 대기열의 끝에 나타나기 때문에 RHS를 줄이지 않아도되지만 대기열의 끝 부분에있는 RHS를 줄일 수는 없습니다. 즉, 다른 토큰을 이동하기 전에 줄이거 나하지 않을지를 결정해야합니다. 결정이 항상 명확한 것은 아니기 때문에 결정을 내리기 위해 아직 읽지 않은 하나 이상의 토큰 ("미리보기 토큰", 이는 입력을 미리보고 있기 때문에)을 검사 할 수 있습니다. 그러나 다음의 k 토큰은 k의 값 (일반적으로 1)으로 만 볼 수 있습니다.

다음은 매우 간단한 예입니다. 쉼표로 구분 된 목록 :

1. Start -> List 
2. List -> ELEMENT 
3. List -> List ',' ELEMENT 

가의 입력을 가정하자입니다

초에

ELEMENT , ELEMENT , ELEMENT 

, 입력 큐가 비어있는, 더 RHS가 비어 없기 때문에 유일한 대안이 이동하는 것입니다

ELEMENT     , ELEMENT , ELEMENT    REDUCE 2 

: 다음 단계에서

queue     remaining input     action 
---------------------- ---------------------------  ----- 
         ELEMENT , ELEMENT , ELEMENT  SHIFT 

는, 파서는 생산 2를 사용 줄이기로 결정

대기열의 끝에 List이 있으므로 퍼서가 프로덕션 1 사용을 줄일 수 있지만 수신 입력에 ,이 있다는 사실을 기반으로하지 않기로 결정했습니다. 이것은 잠시 계속됩니다 :

List     , ELEMENT , ELEMENT    SHIFT 
List ,     ELEMENT , ELEMENT    SHIFT 
List , ELEMENT   , ELEMENT      REDUCE 3 
List     , ELEMENT      SHIFT 
List ,     ELEMENT       SHIFT 
List , ELEMENT   --        REDUCE 3 

이제 lookahead 토큰은 "end of input"의사 토큰입니다. 이번에는 다음을 줄이기로 결정했습니다.

List     --        REDUCE 1 
Start     --        ACCEPT 

구문 분석에 성공했습니다.

그래도 몇 가지 질문이 남습니다. 우선 FIRST와 FOLLOW 세트를 어떻게 사용합니까?

간단히 대답하면 비 종단의 FOLLOW 집합은 비 종단 다음에 오는 비 종단의 첫 번째 집합을 알지 못하면 계산할 수 없습니다. 감소가 수행되어야하는지 여부를 결정할 수있는 한 가지 방법은 미리보기가 감소의 대상이 아닌 터미널에 대해 FOLLOW 세트에 있는지 여부를 확인하는 것입니다. 그렇지 않은 경우 축소가 수행되지 않아야합니다. 이 알고리즘은 위의 간단한 문법으로는 충분합니다. 예를 들어, ,의 약어로 Start -> List의 축소를 수행 할 수 없습니다. ,이 FOLLOW(Start)이 아니기 때문입니다. 이런 식으로 유일한 갈등을 해결할 수있는 문법은 SLR 문법입니다 (여기서 S은 "단순함"을 의미합니다).

대부분의 문법은 충분하지 않으며 더 많은 분석이 수행되어야합니다. 심볼이 비 터미널의 FOLLOW 세트에있을 수 있지만 현재 스택 구성으로 이어지는 컨텍스트에는없는 것이 가능합니다. 이를 확인하기 위해 현재 구성에 어떻게 도달했는지 더 자세히 알아야합니다. 가능한 다양한 분석은 다른 가능성 중에서도 LALR, IELR 및 표준 LR으로 파싱합니다.