증강 문법없이 LR 파싱을 수행 할 수없는 경우는 무엇입니까?

Question

많은 표준 컴파일러 디자인 텍스트는 LR 구문 분석의 첫 번째 단계로 증강 된 문법을 구축하는 것입니다.

이유는 자주

1. 시작 기호가 생산
의 오른쪽에 오는 경우가 필요합니다.
2. 시작 기호의 RHS가 여러 개의 생산을 가지고있을 때 필요합니다.

DFA의 첫 번째 상태의 파스 테이블의 조치 부분에서 우리는 '$'를 입력 할 때 "성공"을 제공한다면 우리는 증강 문법을 요구하지 않을 것입니다.그게 정확하지 않거나 내가 뭔가 빠졌습니까?

편집 : 여기에 우리가 성공으로 구문 분석을 선언 할 수있는 방법은 다음과 같습니다.

S -> .a. 우리가 현재 상태에서 우리의 현재 상태에서 스택의 ttop에서 goto (s)를 줄이는 대신 'A'를 줄이면, 우리는 단순히 '$'와 출력 성공

Answer 1

파싱 테이블이 있으면 문법에 대한 참조없이 문장을 구문 (또는 거부) 할 수 있습니다. 그래서 그 시점에서, 문법이 있었거나 증강되지 않았다는 사실은 본질적으로 싫어합니다. (증강 시작 기호의 유일한 생산에 첨부 된 사용자 의미 론적 조치가 있지만 증강 된 시작 기호의 생산이 사용자가 아닌 자동으로 추가되므로 불가능한 것처럼 보입니다.)

그리고 실제로 대부분의 파서 발생기가 증강 된 시작을 기다리는 대신에 입력 끝 마커의 shift 을 shift 으로 만들어 그들의 파싱 테이블을 최적화하는 경우가 있습니다 기호의 생산이 줄어 듭니다. 해당 최적화를 사용하면 Augmented Start 기호가 파서 작업에서 결코 사용되지 않으므로 기호 자체가 존재할 필요가 없습니다. 파서 생성기가 문법을 증가 시키면 해당 증가는 본질적으로 취소 된 것으로 본질적으로 실행 취소되었습니다 :이 끝날 수있는 기호는 무엇입니까? 그것은 축소 가능한 오른쪽에 나타나지 않습니다.

어쨌든, 요점은 증강 문법이 필요한 구문 분석이 아닙니다. 증강 된 문법은 파싱 테이블을 만들려면 필요합니다. 필요한 경우 본질적으로 입력 된 심볼 LookAhead와 관련된 기본값이 아닌 약간의 절감 동작이있는 경우입니다. 해당 감량 조치는 증강 시작 심볼의 생산을 포함하는 상태의 분석을 통해 파싱 테이블에만 올바르게 추가 될 수있었습니다.

(엄격하게 말하기, 이전에 알아려고, 입력 된 심볼은 문법의 오른쪽쪽에 있지 않으면 파싱 테이블에 실제로 구문 분석 테이블에 존재할 수 없습니다. 문법은 증가합니다. 증가는 추가가 아닌 터미널을 추가 할뿐만 아니라 입력 끝 부분을 추가합니다.)