충돌

다음 문법 조각을 lox로 처리하면 grammar has conflicts 오류와 함께 실패합니다:

expr = expr '+' expr
     | expr '*' expr
     | NUMBER

-report 플래그와 함께 lox를 실행하면 자세한 내용을 확인할 수 있습니다:

I5:
  expr = expr .PLUS expr, EOF
  expr = expr .PLUS expr, PLUS
  expr = expr .PLUS expr, MUL
  expr = expr PLUS expr., EOF
  expr = expr PLUS expr., PLUS
  expr = expr PLUS expr., MUL
  expr = expr .MUL expr, EOF
  expr = expr .MUL expr, PLUS
  expr = expr .MUL expr, MUL
    on EOF reduce expr
    on MUL reduce expr <== CONFLICT
    on MUL shift I3 <== CONFLICT
    on PLUS shift I4 <== CONFLICT
    on PLUS reduce expr <== CONFLICT

위 내용은 파서 상태 머신의 한 상태를 나타냅니다. 이 상태에서 파서는 방금 expr PLUS expr(예: 2 + 2)을 파싱했습니다. 다음 토큰이 MUL이라고 가정하면, 무엇을 해야 할까요? expr PLUS expr을 expr로 축약(reduce)하거나 MUL을 이동(shift)할 수 있습니다. 문법이 어떤 동작을 수행해야 하는지 명확하지 않으므로 모호합니다.

이를 해결하는 한 가지 방법은 문법을 리팩토링하는 것입니다:

expr = expr '+' term
     | term

term = term '*' factor
     | factor

factor = number

number = NUMBER
       | '-' NUMBER

일부 충돌은 리팩토링으로만 해결할 수 있지만, 많은 종류의 충돌은 우선순위 수식어를 사용하여 해결할 수 있습니다:

expr = expr '+' expr  @left(1)
     | expr '*' expr  @left(2)
     | NUMBER

문법의 @left 수식어는 lox에게 expr '+' expr와 expr '*' expr 사이에 충돌이 발생하면 후자가 전자보다 우선순위를 가져야 한다고 알려줍니다.