8P by dalinaum 2021-04-02 | favorite | 댓글 3개

Go언어 개발자 러스 콕스가 2010년에 올린 글의 번역.

- yacc같은 구문 생성기가 구문 오류를 잘 만들어내지 못한다는 미신이 퍼져있었음.
- 하지만 이 문제는 클린턴 제퍼리가 2003년에 풀어냈던 문제고 손으로 파서를 짜야 해결되는 문제가 아님.
- (bison) 상태와 입력 토큰에 일치하는 내용을 테이블에서 찾으면 단순한 구문 오류 보다 나은 오류를 사용할 수 있다.

(이하 한국 Rust 디스코드 서버에서 쓴 내용을 정리했습니다.)

이 글의 최대 문제는 그래서 Go가 지금 파서 생성기를 쓰느냐는 겁니다. 아닙니다. 여전히 메인 Go 파서는 손으로 짜여져 있습니다. 이유는 잘 모르겠습니다만 rsc가 오케이라고 다른 Go 개발자들도 오케이라고 생각하지 않았을 가능성이 높습니다.

Jeffrey의 아이디어는 컴파일러로 따지자면 peephole optimizer에 비교할 수 있습니다. 기계어를 뱉어내기 전에, 최근 뱉은 기계어 명령을 고정된 갯수만큼 유지(그래서 그 window를 엿보는peep 구멍hole이라 저런 이름이지요)하고 있다가 특정 패턴이 보이면 그 자리에서 해당 명령을 더 빠른 명령으로 치환합니다. peephole optimizer는 다른 일반적인 최적화 패스와 병행 사용할 수 있는 편리한 물건이지만, peephole optimizer만 갖고 컴파일러가 요구하는 모든 종류의 최적화를 수행할 수는 없습니다. 마찬가지로 최근 토큰으로부터 오류를 생성하는 접근은 모든 파싱 오류를 커버할 수 없습니다. 게다가 딱히 파서 생성기가 아니어도 준용할 수 있는 독립된 접근이므로, 이 접근이 존재한다고 파서 생성기의 문제가 사라진다고 주장함은 옳지 않습니다.

개인적으로는 파서 생성기라는 개념이 나쁜 게 아니라 파서 생성기가 "강요"하는 사상이 문제라고 생각합니다. 파서를 짜게 되면 이를테면 생성을 하든 손으로 짜든 left recursion과 right recursion을 고려해야 하고, "자연스러운" 문법을 그대로 코드화할 수 없습니다. 근데 손으로 짜는 건 그걸 감수하고 그러는 건데, 파서 생성기를 써 봤자 LL/LR과 같은 특정 파싱 알고리즘에 매여 있는 "문법"의 부분집합에 맞춰 짜야 한다면 생성기의 장점은 반감됩니다. (GLR 같은 알고리즘은 좀 더 숨통을 틔워 주긴 하지만 한계가 있습니다.) 현재 대부분의 프로덕션 레벨 언어 구현들이 파서 생성기를 쓰지 않거나, 간혹 PEG 같이 파서 생성기기는 한데 *전혀* 일반적인 생성기의 장점을 취하지 않는 접근을 쓰는 것은 다 이유가 있습니다.

파서 생성기가 제한하는 문법에 메이기 싫어 파서 생성기를 쓰지 않는다는 점은 공감하지만, 그렇다고 파서 생성기가 사용자에게 특정 문법을 강요하고 있다고 주장하는 건 이상해요.

파서 생성기는 선형시간 파싱의 장점이 있는 LR문법 파싱 테이블 제작이 너무 어려워서 이를 돕기위해 나온거지, 파싱이 비결정적인 context-sensitive 문법이나 파싱이 언제 끝날지도 모르는 재귀적인 파서를 생성해주는건 파서 생성기 연구자/개발자들의 관심대상이 아닐 거에요.

따라서 파서 생성기는 비직관적인 LR LALR 문법을 맹신하고 강요하는 프로그램이 아니라 선형시간 파싱과 이를 위한 파싱 테이블 제작이라는 아주 어려운 문제를 푸는 도구로서 제 역할을 다하고 있다고 생각합니다.

현실에서 볼 수 있는 거의 모든 언어는 LL(1) 문법을 가지고 있어서 LR 파서를 쓰지 않아도 선형 시간 파싱이 가능합니다. (해당 언어에 선호되는 문법이 LL(1)이라는 뜻은 아닙니다.) 따라서 선형 시간 파싱을 위해서 LR 파서를 써야 하는데 파싱 테이블을 만들기 어렵기 때문에 생성기가 필요하다는 말씀은 선후관계가 뒤집힌 것입니다. 또한 파싱 테이블을 만드는 과정 자체가 본질적으로 복잡하지는 않습니다(알고리즘의 증명이 어렵죠).