파싱이론 이야기 2

앞서의 글에서 파싱에 오토마타 이론을 활용하는 드래곤북의 접근방법은 그 복잡성에도 불구하고 실효성은 되려 낮다고 이야기했다.

그러면 대안은 무엇일까? 그냥 “재귀적 분석 파서(recursive descent parser)” 를 만들어 쓰면 된다. 7년쯤 전에 스스로의 가설을 확인하면서 리서치를 진행하다가 같은 생각을 이미 1973년에 하신 Vaughan Pratt 교수님의 논문을 찾을 수 있었다.

“나는 개인적으로 오토마타 이론 자체는 매혹적이라고 생각하지만, 컴파일러 구현에 있어서 오토마타 이론을 적용한 성과는 현재까지 미미했으며, 이 접근방법의 미래 가능성에 대해서도 회의적이다. 나는 오히려 오토마타 이론이 프로그래밍 언어의 발전에 도움이 될 여러 아이디어들의 발전을 가로막고 있다고 생각한다.”

Pratt 교수님은 이어서 표현식(expression)을 재귀 분석적으로 파싱하는 매우 간단하고 우아한 알고리즘에 대한 설명을 이어나간다. 이미 1973년에. 왜 이 논문이 더 일찍 주목을 받지 못했을까? 1) Pratt 교수님 말씀처럼 사람들이 파싱 문제에 오토마타 이론을 적용하는 것에 너무 매료돼 있었고 2) 논문의 설명은 (이런 종류의 논문들이 늘 그렇듯이) 간단하고 우아하지 못했기 때문이 아닐까 싶다..

다행히 이 논문이 영영 잊혀져 있던 것은 아니고, 자바스크립트 진영에서 유명한 Douglas Crockford 에 의해 2007년에 조명됐고, 2011년에는 Bob Nystrom 이 좀더 친절한 설명을 블로그에 공유했다. 최근 몇 년 사이에는 “Pratt 파서” 라는 이름으로 점차 알려지는 단계에 있다.

3편에서는 Pratt 파서를 구현하는 방식을 코드와 함께 살펴보려고 한다.

Copyright @ 2018 Dae San Hwang (Theme: Doo by ThemeVS)