LALR 문법에서 시프트 감소 충돌을 극복하는 방법

Question

양수와 음수를 구문 분석하려고합니다.

number(N) ::= pnumber(N1). 

number(N) ::= nnumber(N1). 

number(N) ::= pnumber(N1) DOT pnumber(N2). 

number(N) ::= nnumber(N1) DOT pnumber(N2). 

pnumber(N) ::= NUMBER(N1). 

nnumber(N) ::= MINUS NUMBER(N1). 

처음 두 규칙의 포함

는 이동/줄일 충돌을 제공하지만 난 충돌이 발생 결코 문법은 쓸 수있는 방법을 모르겠어요. 레몬 파서를 사용하고 있습니다.

편집 :이 .out 파일에서 충돌이

State 79: 
    (56) number ::= nnumber * 
      number ::= nnumber * DOT pnumber 

          DOT shift  39 
          DOT reduce  56  ** Parsing conflict ** 
        {default} reduce  56  number ::= nnumber 

State 80: 
    (55) number ::= pnumber * 
      number ::= pnumber * DOT pnumber 

          DOT shift  40 
          DOT reduce  55  ** Parsing conflict ** 
        {default} reduce  55  number ::= pnumber 
State 39: 
      number ::= nnumber DOT * pnumber 
      pnumber ::= * NUMBER 

         NUMBER shift-reduce 59  pnumber ::= NUMBER 
         pnumber shift-reduce 58  number ::= nnumber DOT pnumber 

State 40: 
      number ::= pnumber DOT * pnumber 
      pnumber ::= * NUMBER 

         NUMBER shift-reduce 59  pnumber ::= NUMBER 
         pnumber shift-reduce 57  number ::= pnumber DOT pnumber 

편집 2 : 최소한의 문법 문제

start ::= prog. 
prog ::= rule. 
rule ::= REVERSE_IMPLICATION body DOT. 
body ::= bodydef. 
body ::= body CONJUNCTION bodydef. 
bodydef ::= literal. 
literal ::= variable. 
variable ::= number. 
number ::= pnumber. 
number ::= nnumber. 
number ::= pnumber DOT pnumber. 
number ::= nnumber DOT pnumber. 
pnumber ::= NUMBER. 
nnumber ::= MINUS NUMBER. 

Answer 1

당신이 보여 갈등의 원인이되는 number 비 터미널 를 사용하는 방법에 문제가 있음을 나타냅니다, 아니 number 자체.

기본적인 문제는이 number (줄의 끝해야하는 경우 pnumber 또는 nnumber을보고 난 후에, 내다보기의 다음의 토큰이 DOT 때, 너무 DOT은 다른의 일부를 결정할 수 없다는 것입니다 비 종단 number) 후, 또는 DOT 취급되어야 하는지를 나중에 DOT의 PNUMBER 규칙 nNUMBER 개의 /는 P 하나 줄일 수 있도록 시프트 number 부분 (등.)

따라서 진단을 위해 문제가 발생하면 오른쪽에있는 number을 사용하는 모든 규칙을 표시해야합니다. 옳게 그 규칙들 중 하나를 사용하는 다른 모든 규칙들. 하여 LR 파서 건설 과정은 규칙이 다른 문법에서 사용되는 경우의 상황에 크게 의존대로, 문법의 단지 조각을 게시 거의 유용

주 ...

---

여기서 문제는 DOT (실제) numberliteral과 DOT (rule 끝)을 구별하기 위해 두 개의 토큰 미리보기가 필요하다는 것입니다.

쉬운 수정은 함께 렉서 거래를하도록하는 것입니다 - 당신이 NUMBER에서 별개의 비 터미널로 REAL_NUMBER을 인식 할 수 있도록 렉서는, 그래서 -없이 여전히 아마 (아주 쉽게 내다 적은 양의 작업을 수행 할 수 있습니다 ' 룩어 충돌을 제거하기 위해 문법을 리팩토링

number ::= NUMBER | MINUS NUMBER | REAL_NUMBER | MINUS REAL_NUMBER 

의 문법을 감안하여 충돌을 제거하기 더 힘들어 만이 수행 할 수 있습니다. 일반적으로

---

로 결국 D, 충돌을 나타내는 규칙 (rule 및 number은 여기에 있음)을 찾아내어 모호한 부분까지 충분히 도달 할 때까지 공통 접두사가있는 규칙을 함께 가져와야합니다.

먼저, 여기에 덧붙일 수있는 number 외에 다른 규칙이 있다고 가정합니다. 그렇지 않으면 모든 개재 규칙을 제거 할 수 있습니다.

variable ::= number | name 

우리는 DOT와 rule으로 같은 장소에 그것을 얻기 위해 문법에서 "최대"를 number 규칙을 이동하려는. 따라서 포함 규칙을 number으로 끝나면 특별한 경우로 분할해야합니다. 우리는 number로 끝나는 모든 버전과 원래의 규칙에 해당하는 규칙을 표시하기 위해 접미사를 추가

variable ::= number | variable_n 
variable_n ::= name 

을 분할 ... 그리고 progate 그

literal ::= number | literal_n 
literal_n ::= variable_n 

"최대"... 및 agin

bodydef ::= number | bodydef_n 
bodydef_n := literal_n 

... 다시

body ::= number | body_n 
body := body CONUNCTION number 
body_n ::= bodydef_n 
body_n ::= body CONJUNCTION bodydef_n 

당신이 그것을 위로 움직이면서 점점 더 많은 규칙들을 나눌 필요가 있음을 주목하십시오, 그래서이 과정은 문법을 꽤 날려 버릴 수 있습니다. 그러나 리팩토링중인 rhs 끝에 만 사용되는 규칙은 결국 _n 버전 만 필요하므로 결국 규칙 수를 두 배로 늘릴 필요가 없습니다.

... 마지막 단계

rule ::= REVERSE_IMPLICATION body_n DOT 
rule ::= REVERSE_IMPLICATION number DOT 
rule ::= REVERSE_IMPLICATION body CONJUNCTION number DOT 

는 이제 number 규칙 모두 같은 장소에서 점을, 그래서 확장 :

rule ::= REVERSE_IMPLICATION body_n DOT 
rule ::= REVERSE_IMPLICATION integer DOT 
rule ::= REVERSE_IMPLICATION integer DOT pnumber DOT 
rule ::= REVERSE_IMPLICATION body CONJUNCTION integer DOT 
rule ::= REVERSE_IMPLICATION body CONJUNCTION integer DOT pnumber DOT 

하고, 충돌이 사라 변화를-줄일 수 있기 때문에 규칙은 사용할 미리 결정하기 위해 필요한 미리보기를 통과 할 때까지 공통 접두어를 사용합니다. 내가

integer ::= pnumber | nnumber 

Answer 2

를 추가하여 최종 확장의 규칙의 수를 감소했습니다 당신은 %left 또는 %right으로 DOT 운영자 토큰의 연관성을 선언해야합니다.

또는 다른 아이디어는이 중간 감소를 제거하는 것입니다. 문법의 분명한 특징은 숫자가 DOT에이어서 숫자가 증가한다는 것입니다. 즉 하나의 규칙을 캡처 할 수 있습니다 :

number : number DOT NUMBER 

NUMBER 토큰 다음에 DOT 뒤에 숫자는 여전히 숫자입니다.

이 규칙은 모호성이 없으므로 DOT에 연관성을 선언 할 필요가 없습니다. 이 규칙은 순수하게 왼쪽 재귀 적이며, 오른쪽의 DOT은 터미널 토큰입니다. 파서는 상태 머신이 시점에서 때 number에 스택의 상단을 감소하고 DOT을 이동해야합니다

number : number DOT NUMBER 

여기에 분석 된 언어가 일반입니다 재귀없이 정규 표현식으로 구문 분석 될 수 있습니다. 그렇기 때문에 왼쪽과 오른쪽 재귀가 모두 있고 연관성을 선언해야하는 규칙은 다소 큰 망치입니다.