LR 파싱에서 S '-> S가 필요함

Question

추가 규칙 인 S -> S'없이는 문법 언어에없는 단어를 수락 할 수 있다고 들었는데, ? 또한 하나 이상의 상태로가는 SLR 구문 분석을 줄이는 예제가 있습니까?

Answer 1

이 추가 생산 규칙이 필요한 주된 이유는 입력 문자열을 실제로 읽었을 때를 결정할 수 있기 때문입니다. 포함시키지 않으면 잘못된 반응을 보일 수 있습니다. 예를 들어

는,이 문법을 고려 :

S →로를 | b

추가 시작 제작으로이 문법을 늘리지 않고 대신 LR (0) 파서를 작성하기 시작했다고 가정 해 보겠습니다. 이 상태를 되 찾을 것입니다.

이제이 LR (0) 파서를 사용하여 abb 문자열을 구문 분석한다고 가정 해 보겠습니다. 이 문자열은 문법 언어로 이 아니고이 아니므로 동의하지 않아야합니다. 발생하는 흔적은 다음과 같습니다.

Stack    | State | Input   | Action 
-------------------+-------+------------------+---------- 
        | (1) | abb    | Shift, go to (3) 
a     | (3) | bb    | Shift, go to (2) 
ab     | (2) | b    | ??? 

그래서 여기에 문제가 있습니다. 이 상태에서 항목 S →을 줄일 수 있습니다. b. 이제 여기에서 축소를 수행하고 구문 분석을 계속 하시겠습니까? 아니면 구문 분석으로 끝났습니까? 우리가 여기에서 멈추기로 결정하면 실제로 존재하지는 않지만 문자열이 언어에 있다고 잘못보고 할 것입니다. 여기에서 멈추지 않는다면 입력을 정확하게 파싱 할 것입니다.하지만 다른 입력 (예 : 문자 b)을 얻었 으면 실제로해야하는 경우를 줄일 수 있습니다. 파싱을 중단하십시오. 이 문제는 SLR (1) 구문 분석기를 사용하여 해결되지 않습니다. 왜냐하면 미리보기가 이러한 경우를 구별하는 데 도움이되지 않기 때문입니다.

처음에 추가 제작을 추가함으로써 파서는 해당 제작을 고려하기 때문에 "나는 완전히 끝났습니다"에서 "나는 시작 기호와 무언가를 일치했습니다"를 모호하게 구분할 수 있습니다 if S를 줄이고 파싱 스택이 비어 있습니다.