때때로 Bison 문법이 가끔 가끔씩 실패합니다.

Question

저는 처음으로 Bison 문법으로 광범위하게 연구하고 있습니다. 문법을 설정하고 결과를 연관시키는 약간의 테스트 슈트가 있습니다.

때때로, 테스트 스위트는 전달합니다

Reducing stack by rule 101 (line 613): 
    $1 = nterm mathenv() 
-> $$ = nterm closedTerm() 
Stack now 0 5 3 
Entering state 120 
Reading a token: Next token is token ENDMATH() 
Reducing stack by rule 28 (line 517): 
    $1 = nterm closedTerm() 
-> $$ = nterm compoundTerm() 
Stack now 0 5 3 
Entering state 119 
Reducing stack by rule 12 (line 333): 
    $1 = nterm compoundTerm() 
-> $$ = nterm compoundTermList() 
Stack now 0 5 3 
Entering state 198 
Next token is token ENDMATH() 
Shifting token ENDMATH() 
Entering state 325 

... continues to completion ... 

때때로, 그렇지 않습니다 :

Reducing stack by rule 101 (line 613): 
    $1 = nterm mathenv() 
-> $$ = nterm closedTerm() 
Stack now 0 5 3 
Entering state 120 
Reading a token: Next token is token MN() 
Reducing stack by rule 28 (line 517): 
    $1 = nterm closedTerm() 
-> $$ = nterm compoundTerm() 
Stack now 0 5 3 
Entering state 119 
Reducing stack by rule 12 (line 333): 
    $1 = nterm compoundTerm() 
-> $$ = nterm compoundTermList() 
Stack now 0 5 3 
Entering state 198 
Next token is token MN() 
Shifting token MN() 
Entering state 11 

... errors eventually ... 

Now at end of input. 
Line: 9 Error: syntax error at token 

ENDMATH가로 전환 할 수있는 올바른 토큰이지만, 때로는 MN가 결정된다. 테스트를 실행할 때마다 일관성없는 결과가 나타납니다. 그러한 "무작위"모호성이 정상입니까? 무엇 때문에 그 원인이 될 수 있습니까? 일부 %precedence 규칙을 정의해야합니까?을 y.output 의 상단에

, 내가

State 0 conflicts: 3 shift/reduce 
State 120 conflicts: 2 shift/reduce 
State 127 conflicts: 2 shift/reduce 
State 129 conflicts: 2 shift/reduce 
State 154 conflicts: 1 shift/reduce 
State 207 conflicts: 3 shift/reduce 
State 265 conflicts: 109 shift/reduce 
State 266 conflicts: 109 shift/reduce 
State 267 conflicts: 109 shift/reduce 
State 268 conflicts: 109 shift/reduce 
State 269 conflicts: 109 shift/reduce 
State 342 conflicts: 2 shift/reduce 
State 390 conflicts: 109 shift/reduce 
State 391 conflicts: 109 shift/reduce 
State 396 conflicts: 1 shift/reduce 
State 397 conflicts: 1 shift/reduce 

같은 상태에 대한 몇 가지 충돌을 볼 수 있습니까 그것은 이러한 충돌을 모두 제거하는 것이 좋습니다? 상태 (120)는 충돌이있는 것으로서 나열되고,이 랜덤 에러가 발생하기 바로 직전의 상태이다.

Answer 1

문법의 충돌은 문법이 LALR (1)이 아님을 의미합니다. 그 이유는 문법이 모호하기 때문이거나 문지기가 하나 이상 있어야하는 문법 때문일 수 있습니다. 충돌이있을 때마다 들소는 우선 순위 지시어에 따라 가능한 조치 (전환 또는 축소) 중 하나를 선택하여 해결합니다. 결과적으로 문법에 의해 기술 된 언어의 일부 하위 집합을 인식 (파싱)하는 파서가됩니다.

모호성 때문에 충돌이 발생한 경우 모호한 구문 분석을 제거하고 실제로 언어를 줄이지 않을 수 있습니다. 이러한 경우 우선 순위 규칙을 사용하여 모호성을 해결하는 것이 문제를 해결하는 올바른 방법입니다. 원하는 언어를 구문 분석 할 수있는 문법을 제공하기 때문입니다.

더 많은 미리보기가 필요하기 때문에 충돌이 발생하면 우선 순위 규칙은 일반적으로 도움이되지 않습니다. 미리보기를 필요로하지 않거나 렉서가 입력 또는 기타 정보의 추가 미리보기를 기반으로 여분의 합성 토큰을 삽입하는 것과 같은 다른 기술 (해킹)을 사용하여 문법을 재정렬함으로써 문제를 해결해야합니다.

직접적인 문제는 렉서에있는 것 같습니다. 즉 토큰 ENDMATH을 반환하고 또 다른 경우 MN을 반환합니다. y.output에서 볼 수있는 충돌과 관련된 문법에 모호성이나 미리보기 문제가있을 수도 있지만 이러한 문제는 언뜻보기에 렉서와 관련된 문제와 완전히 독립적입니다.