Yantra - LALR(1) parser generator for C++
Show HN: Yantra – an LALR(1) parser generator for C++
Yantra는 C++로 작성된 강력한 컴파일러 컴파일러이자 LALR(1) 파서 생성기입니다. 통합 렉서, AST 빌더, AST 워커를 내장하고 있어 별도의 도구 없이 하나의 문법 파일로 렉서, 파서, AST를 모두 생성할 수 있습니다. 기존 Bison이나 Yacc와 달리 파싱 후 AST를 먼저 구축한 뒤 탑다운 방식으로 순회하므로, 부모 규칙의 액션이 자식 노드보다 먼저 실행됩니다. 이는 재귀 하강 파서에서 추가 클래스와 순회 패스를 구현해야 하는 번거로움을 없애줍니다. 또한 ANTLR과 달리 Java 없이 순수 C++ 실행 파일로 동작하며, UTF-8 지원과 모드 스택 렉서, 아말가메이티드 모드 등의 기능을 제공합니다. MIT 라이선스로 공개되어 있어 누구나 자유롭게 사용할 수 있습니다.
Yantra는 LALR(1)이라는 상향식 알고리즘에서 ANTLR이 LL(*)로 자연스럽게 얻는 탑다운 순회를 구현해냈습니다. 이로써 LALR(1)의 시간과 공간 효율성을 유지하면서도, 부모 규칙의 액션이 자식보다 먼저 실행되는 직관적인 AST 워킹이 가능해졌습니다.
HN 토론
15- MichaelMoser123
행운을 빌어요.
예전에는 shift/reduce, reduce/reduce 오류를 고치는 방법을 알고 있었는데, 그게 꽤 오래전 일이네요.
recursive descent parser를 쓰면 left recursion을 확인해야 하는데, 그건 좀 덜 까다로운 편이죠.
- mingodad
이 주제에 관심 있는 분들께 Ben Hanson의 https://github.com/BenHanson/parsertl17 도 꼭 살펴보시길 강력히 추천합니다. 그리고 그것을 기반으로 저는 여기에 온라인 LALR(1) 놀이터를 만들어 두었습니다: https://mingodad.github.io/parsertl-playground/playground/ 여기서는 약 350개의 만만치 않은 문법들을 실험해 볼 수 있습니다 (`Examples` 드롭다운에서 하나를 선택한 다음 `Parse`를 클릭하면 `Input`에 있는 입력에 대한 파스 트리를 볼 수 있습니다). 또한 https://www.bottlecaps.de/rr/ui 에서 보기 좋고 탐색 가능한 railroad diagram을 생성할 수 있는 EBNF도 만들어 줍니다.
- userbinator
대다수의 컴파일러가 이미 recursive descent / precedence climbing으로 정착한 지 한참 뒤에 새로운 parser generator가 작성되는 걸 보는 건 조금 놀랍네요 (지금 프런트 페이지 근처에 있는 https://news.ycombinator.com/item?id=49913192 도 포함해서요).