Shift-reduce : 언제 줄이기를 멈 춥니 다?

Question

저는 shift-reduce 구문 분석에 대해 배우려고합니다. 우리가 ANSI C Yacc grammar에서 영감을 작업의 순서를 시행 재귀 규칙을 사용하여 다음과 같은 문법을 가지고 가정 :

S: A; 

P 
    : NUMBER 
    | '(' S ')' 
    ; 

M 
    : P 
    | M '*' P 
    | M '/' P 
    ; 

A 
    : M 
    | A '+' M 
    | A '-' M 
    ; 

그리고 우리는 구문 분석을 교대-감소하여 1 + 2를 구문 분석합니다. 먼저 1이 숫자로 이동합니다. 제 질문은 P로, M으로, A로, 마지막으로 S로 줄입니까? 어디에서 멈출 지 어떻게 알 수 있습니까?

S로 줄이고 '+'시프트한다고 가정합니다. 우리는 지금 포함하는 스택 거라고 : 우리가 '2'시프트를하면

S '+' 

을 감축 될 수 있습니다

S '+' NUMBER 
S '+' P 
S '+' M 
S '+' A 
S '+' S 

이제 마지막 줄의 양쪽에, S가 될 수있다 P, M, A 또는 NUMBER를 포함 할 수 있으며 모든 조합이 텍스트의 올바른 표현이라는 의미에서 여전히 유효합니다. 파서는 그것을 어떻게 알 수 있습니까?

A '+' M 

그래서 전체 표현식을 A로 줄이면 S? 즉, 다음 토큰을 이동하기 전에 줄이기를 중지하는 것을 어떻게 알 수 있습니까? 이것이 LR 파서 생성에있어 핵심적인 어려움입니까?

---

편집 : 질문에 추가가 다음.

이제 1+2*3을 구문 분석한다고 가정합니다. 일부 시프트/축소 작업은 다음과 같습니다.

Stack | Input | Operation 
---------+-------+---------------------------------------------- 
     | 1+2*3 | 
NUMBER | +2*3 | Shift 
A  | +2*3 | Reduce (looking ahead, we know to stop at A) 
A+  | 2*3 | Shift 
A+NUMBER | *3 | Shift (looking ahead, we know to stop at M) 
A+M  | *3 | Reduce (looking ahead, we know to stop at M) 

정확합니까 (아직 완전히 파싱되지 않았습니다)? 더욱이, 1 심볼에 의한 미리보기는 또한 A+M을 A으로 줄이지 말라고 말하면, *3을 읽은 후에 필연적 인 구문 오류가 발생하게됩니까?

Answer 1

설명하는 문제는 LR(0) 파서를 만드는 문제입니다. 즉, 파서를 분석하는 현재의 기호 이외의 기호에 대한 미리보기를 수행하지 않는 상향식 파서입니다. 설명하신 문법은 LR(0) 문법으로 보이지 않으므로 미리보기가 없으면 구문 분석을 시도 할 때 문제가 발생합니다. 그러나 은이 LR(1) 인 것처럼 보입니다. 따라서 입력에서 1 심볼 앞을보고 이동하거나 축소할지 여부를 쉽게 결정할 수 있습니다. 이 경우, 1이 스택 상에있을 때 파서가 앞을 내다 보았을 때 다음 심볼이 + 인 것을 확인하고 이후로는 A을 줄이지 않아야한다는 것을 알고 있습니다. 두 번째 위치의 + 규칙과 여전히 일치합니다.

는

LR 문법의 흥미로운 특성은 k>1위한 LR(k) 임의 문법,이 등가 인 LR(1) 문법을 구성하는 것이 가능하다는 것이다. 그러나 동일한 것이 모두 LR(0)으로 확장되지 않습니다. LR(0)으로 변환 할 수없는 많은 문법이 있습니다.

는 LR(k) -ness에 대한 자세한 내용은 여기를 참조하십시오 :

http://en.wikipedia.org/wiki/LR_parser

Answer 2

나는 Yacc에/들소 구문 분석 알고리즘의 정확히 모르겠어요하고 감소를 통해 이동 선호한다 때, 그러나 나는 들소 지원하는 것을 알고있다 LR (1) 구문 분석은 미리보기 토큰이 있음을 의미합니다. 즉, 토큰은 즉시 스택으로 전달되지 않습니다. 오히려 더 이상 감축이 일어나지 않을 때까지 기다린다. 그런 다음, 다음 토큰을 이동하면 해당 작업이 적용됩니다.

첫 번째로, 1 + 2를 평가하는 경우 1을 이동합니다. '+'미리보기 토큰이 유일한 유효한 코스임을 나타내므로 토큰을 A로 줄입니다. 감소가 없으므로 '+'토큰을 스택으로 이동시키고 2를 미리보기로 유지합니다. A와 M이 A를 생성하고 표현이 완료되기 때문에 2를 이동시키고 M으로 줄 것입니다.