부정적 예측 분석 알고리즘

Question

는 (등 예 YACC, 들소,)는 LR-가족 구문 분석 발전기 문법 같은 규칙을 고려 :

Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; 

그것은 그것이 제한이 점을 제외하고, 일반적인 규칙입니다 :이 규칙으로 생성 된 문구는 Terminal1, ..., TerminalN으로 시작할 수 없습니다. (물론,이 규칙은 일반적인 규칙 세트로 대체 될 수 있지만 더 큰 문법이 될 것입니다.) 이는 충돌을 해결할 때 유용 할 수 있습니다.

질문은 그러한 제한을 허용하는 LR 테이블 생성 알고리즘이 수정 되었습니까? 그러한 수정은 가능합니다 (우선 순위 관계와 같은).

확실히, 그것은 런타임 체크,하지만 난 체크인 시간 컴파일을 의미 할 수있다 (%prec처럼 파싱 테이블을 구축하는 동안 수행되는 검사, %left, yacc를-compartible 발전기 %right 및 %nonassoc 지시를.)

Answer 1

왜 이것이 가능하지 않아야하는지 모르겠다. 그러나 유용 할 이유가 없다. 당신은 명심해야 할 것이 있습니까?

가장 쉬운 방법은 괄호 안에있는 문법 변환을하는 것입니다. 이것은 더 큰 문법을 만들지 만 인위적으로 LR 상태의 수를 늘리지는 않습니다.

기본 변환 손을 흔들며의 비트와 함께 : 단말 제한 임의 제조

: 생산 비 널 아닌 단말기로 시작

• 상기 대체 터미널 제한 버전의 비 터미널. 제조 터미널 제한 목록에서 단말기로 시작하면 생산이 단말이 아닌 단말 제한 목록에 변화가 필요하지 않다로 시작

• 생산을

• 제거. 생산이 널 (NULL)이 아닌 터미널로 시작하면

, 당신은 두 가지 버전을 만들 수있는 널 (NULL)이 아닌 터미널 중 하나는 항상 null, 비 - 널 (NULL) 인 다른입니다; 새로운 비 터미널 각각으로 시작하는 두 가지 버전의 프로덕션을 작성하십시오. 그런 다음 위의 변환을 적용하지만 "다음으로 시작"을 해석하는 것은 "항상 널이 아닌 비 터미널 이후부터 시작합니다."

위의 변환은 LR (0) 및 LALR (1) 구문에 대해 기본 SLR 시스템을 구성하는 동안 즉석에서 수행 할 수 있기 때문에 실제로는 문법을 수정할 필요가 없습니다.