프로그래밍노리터

앞의 글에서 문법에 대해 RDP(Recursive Descent Parser)를 직접 만드는 방법을 살펴보았습니다. 그러나 문법이 아주 큰 경우 모든 넌터미널 심볼에 대해 직접 메소드를 만들고 모든 터미널 심볼을 직접 다루는 것은 결코 쉬운 일이 아닙니다. 그래서 많은 경우 토큰을 읽어들이는 일은 Lexer라는 툴을 많이 이용하고 파서는 역시 파서를 만들어주는 툴을 많이 사용합니다. 그리고 그런 파서는 LL 또는 LR 파싱 방법으로 구현되어 있습니다. 여기서는 LL 파싱 알고리듬이 어떻게 동작하는지를 설명해 보려고 합니다. 사실 이것을 몰라도 바로 파서생성기를 이용하는 것이 가능하나 RDP 방법을 익힌 다음이라면 체계적인 파싱 알고리듬으로서 LL 알고리듬을 이해하는 것이 어렵지 않습니다. 앞의 글에서 살..

이전 포스트에서 E -> T { (+|-) T }, T -> num | (E) 라는 문법의 파서를 만들어보았습니다. 여기서는 문법을 좀더 확장하고 수식 계산 과정을 보여줄 수 있는 파서를 만들어보도록 하겠습니다. (완성된 코드와 실행결과는 하단에 링크되어 있습니다.) /* * E -> T { (+|-) T } * T -> F { (*|/) F } * F -> num * | ( E ) */ 이전 포스트에서 +와 - 연산만 지원하는 문법에서 *와 /를 지원하는 문법으로 확장한 것입니다. 우선순위를 고려하기 위해 새로운 넌터미널을 도입하여 괄호()로 둘러싼 부분이 가장 우선순위가 높고 *|/가 그 다음 순위고 +|-가 가장 우선순위가 낮아서 마지막으로 처리되도록 문법을 만든 것입니다. 이렇게 되면 T() 메소..