TL;DR

  • Klar 파서 오류 복구는 언어 서버(Language Server)에서 유효하지 않은 프로그램도 처리하면서, 하나의 토큰에서 오류가 연쇄적으로 발생하지 않고 수정 가능한 오류에 대해 유효한 추상 구문 트리(AST)를 생성하는 것을 목표로 함.
  • 파서는 어떤 프로그램에서도 충돌하거나 멈추지 않아야 하며, 사용자가 입력한 토큰을 삭제하지 않고 서식 지정기가 오류를 바로잡을 수 있어야 함.
  • 오류 뒤 토큰을 건너뛸 때 함수 선언, 타입 선언, 함수 호출별로 지정한 계속 토큰(continuing token)에 도달하면 건너뛰기를 중단하는 방식임.
  • 중첩된 구문 수준의 계속 토큰을 관리하려면 여러 스택이 필요하며, 컬렉션 종료 상태를 기록해 오류 복구 시점을 추적함.
  • 제안된 구현은 비트마스크 스택과 복구 상태 필드를 사용하며, 예상하지 못한 토큰에서 계속 토큰까지 건너뛰는 방식임.

Klar 파서 오류 복구

파서 목표

  • KlarLS와 같은 언어 서버가 사용자의 입력 도중에도 계속 작동하려면 오류를 허용하는 파서가 필요함.
  • 일치하지 않는 괄호 하나가 여러 오류를 추가로 유발하지 않도록 해 사용자 경험을 개선하는 것이 목표임.
  • LSP(Language Server Protocol)에서 사용할 범용 파서의 목표는 다음과 같음.
  • 유효하지 않은 프로그램을 포함해 어떤 프로그램이 주어져도 충돌하거나 멈추지 않음.
  • 하나의 토큰에서 오류가 연쇄적으로 발생하지 않음.
  • 수정 가능한 오류가 있어도 유효한 AST를 생성함. 이를 통해 LSP의 서식 지정기가 오류를 수정할 수 있으며, 사용자가 입력한 토큰을 삭제하지 않음.
  • 괄호 배치와 같은 사소한 스타일 선호는 오류로 취급하지 않는 것이 권장됨. 서식 지정기가 이를 수정할 수 있기 때문임.

시나리오

  • a(b, c+ 다음에 return true가 오는 경우, 파서는 문장 키워드에서 복구를 멈추는 방식임.
  • when x { _ -> print(1) 뒤에 return이 오면 해당 위치에서 복구를 이어가는 시나리오임.
  • type X: {처럼 타입 선언에서 타입이 필요한 위치에 중괄호가 오면 expected type 오류가 발생하는 상황임.
  • type Z가 구조체 필드나 열거형 항목에 유효하지 않은 토큰으로 나타나면, 새 문장을 시작하는 상황으로 처리함.
  • type A: B<Int {에서는 해당 위치부터 복구를 이어가며, 서식 지정 시 >를 자동 삽입할지 검토할 수 있음.
  • f(a+,에서는 해당 위치부터 복구를 이어가고, f(,)에서는 expected expression 오류를 낸 뒤 토큰을 건너뛰는 시나리오임.
  • func x(name( ) {}에서는 해당 위치부터 복구를 이어가고 이후 토큰을 건너뛰는 시나리오임.

계속 토큰

  • 오류 뒤 토큰을 건너뛸 때 다음 토큰 중 하나에 도달하면 건너뛰기를 멈춤.
  • 함수 선언: ), =, }
  • 타입 선언: :, {
  • 함수 호출: ,, )

스택

  • f(1, ['a', +)와 같이 안쪽 구문에서 바깥쪽 계속 토큰을 만나면 두 구문 수준을 모두 빠져나와야 하므로, 각 수준에서 계속 토큰을 추적해야 함.
  • ]와 , 같은 토큰을 한 수준의 계속 토큰으로 쌓고, 그 안에 ,와 ) 같은 다른 수준의 계속 토큰을 쌓는 구조임.
  • func x(name: Result<String {에서는 함수 선언의 끝을 나타내는 }를 계속 토큰으로 추적함.
  • y := process([1, 2,처럼 컬렉션이 중첩된 상황에서는 각 수준의 ,, ], }를 추적하며, 닫는 중괄호에서 리스트·호출·함수 구문이 끝날 수 있음.
  • 이전 수준의 계속 토큰을 추적하려면 여러 스택이 필요함.

또 다른 시나리오

  • func x() = 다음에 func y() {}가 오면 func y() {}를 람다 표현식으로 파싱하는 경우가 있음.
  • func z() = 다음에 while {}가 오면 표현식 파싱을 시작하지만, 실제로는 문장인 상황이 발생함.

해결 방안

  • 다음 세 가지 방안이 제시됨.
  • a. 오류 복구 모드의 람다 표현식에서 이름을 허용하고, for 표현식에서 중괄호를 허용함.
  • b. 들여쓰기를 기준으로 판단함. 들여쓰기가 없으면 두 문장으로 처리하고, 들여쓰기가 있으면 람다 표현식에서 이름을 허용하지 않음.
  • c. 이 시나리오를 무시하고 오류를 더 보고함.

구현

  • 파서에 계속 토큰을 위한 stack, 괄호이거나 컬렉션을 나타내는 계속 토큰을 위한 collectionStack, 현재 컬렉션이 끝났는지를 나타내는 collectionEnd 필드를 추가하는 구상임.
  • 스택 유형은 Klar 언어에서 가능한 계속 토큰을 각각의 비트로 나타내는 비트마스크임. 토큰 수에 따라 uint16 또는 uint32를 사용할 수 있음.
  • 괄호와 쉼표 같은 토큰은 각각 별도 비트로 표현함.

스택 추적

  • 다음 경우 collectionEnd를 true로 설정함.
  • x := [(1, 2), (3]처럼 계속 토큰인 ]에 도달하는 경우.
  • func x() = while {}처럼 새 문장이 시작되는 경우.
  • 파서의 restoreTokenStack()은 복구가 완전히 끝나면 collectionEnd를 false로 설정함.
  • 컬렉션 표현식을 시작할 때 메서드가 계속 토큰을 스택에 넣고, defer 호출에서 스택을 복원함. 이 방식은 계속 토큰과 종료 여부를 각각 기록하는 스택 노드 슬라이스 대신 O(1) 공간의 스택을 유지할 수 있게 함.
  • x := #{a: [(1, 2), (3}에서는 튜플과 리스트의 collectionEnd가 true가 되며, 컬렉션을 빠져나오면 즉시 false로 돌아감.
  • y := [1, 2, 3, 다음에 func z() {}가 오는 경우 리스트의 collectionEnd가 true가 되고 리스트를 빠져나오면 false가 됨.
  • type A: B<C {에서는 해당 위치에서 이전 컬렉션이 끝나고 다른 컬렉션이 시작되며, {가 collectionStack에 추가됨.
  • Go에서 리스트를 파싱할 때는 오른쪽 대괄호와 쉼표를 계속 토큰으로, 오른쪽 대괄호를 컬렉션 토큰으로 스택에 넣고, 파싱이 끝나면 기존 스택을 복원함.
  • 리스트 항목을 파싱하는 동안 토큰이 남아 있고 컬렉션이 끝나지 않았으며 현재 토큰이 오른쪽 대괄호가 아니면 항목을 계속 읽음.
  • collectionEnd가 false이고 현재 토큰이 오른쪽 대괄호가 아닐 때 쉼표를 요구함. 대안으로 collectionEnd 검사를 생략하고, 컬렉션이 끝난 상태에서 쉼표가 빠져도 오류를 보고하지 않는 방식도 제시됨.

토큰 건너뛰기

  • 예상하지 못했거나 유효하지 않은 토큰이 나오면, 어느 위치에서든 계속 토큰에 도달할 때까지 토큰을 건너뜀.

참고 자료