Java에서 PEG(구문 표현 문법) 구현: Parboiled 라이브러리를 사용한 간단한 스캐너리스 파서 구현

오늘날의 웹 애플리케이션과 소프트웨어 개발 환경에서는 사용자 입력을 구문 분석하고 처리하는 것이 매우 중요한 요소로 자리 잡고 있습니다. 이러한 구문 분석을 보다 효율적으로 처리하기 위해 많은 개발자들이 **PEG(Parsing Expression Grammar, 구문 표현 문법)**을 사용하고 있습니다. 특히 PEG는 정규 표현식보다 더 유연하고 강력한 방식으로 구문을 정의하고 처리할 수 있습니다. 이번 글에서는 Java에서 PEG를 구현하는 방법에 대해 알아보고, Parboiled라는 라이브러리를 사용해 구문 분석기를 작성하는 예시를 다뤄보겠습니다.

 

 

Java에서 PEG(구문 표현 문법) 구현: Parboiled 라이브러리를 사용한 간단한 스캐너리스 파서 구현

 

 

PEG(구문 표현 문법)란 무엇인가?

구문 표현 문법(PEG)은 문법을 기반으로 한 파서를 작성하기 위한 공식적인 방법입니다. PEG는 CFG(문맥 자유 문법)와 비슷하지만, 모호성을 허용하지 않고 선택적인 규칙이 더 명확하게 처리된다는 차이점이 있습니다. 즉, PEG 파서는 입력을 한 번만 읽어들이면서 파싱을 진행하며, 각 입력에 대해 명확한 해석을 제공합니다.

전통적인 CFG 기반의 파서는 여러 가지 해석 방법이 존재할 수 있으며, 이를 해결하기 위해 추가적인 디스앰비규에이션(disambiguation) 과정이 필요합니다. 반면, PEG는 이러한 모호성이 없기 때문에 보다 단순한 방식으로 동작하며, 구문 분석 과정에서 결정적인 방식을 사용합니다.

 

 

Parboiled 라이브러리 소개

Parboiled는 Java 및 Scala에서 PEG를 기반으로 한 텍스트 구문 분석을 수행할 수 있는 가벼운 라이브러리입니다. 이 라이브러리는 DSL(Domain-Specific Language, 도메인 특화 언어)을 제공하여 구문 규칙을 정의하고 파서를 자동으로 생성하는 기능을 지원합니다. 다른 파서와 달리, Parboiled는 외부 파일로부터 문법 규칙을 가져오지 않고, 코드 내에서 직접 구문 규칙을 정의할 수 있기 때문에 개발 속도가 빠르고, 별도의 파싱 및 렉싱(lexing) 단계가 필요하지 않습니다.

 

 

Parboiled 설치

Parboiled는 Maven 중앙 저장소에서 쉽게 다운로드할 수 있으며, Java와 Scala에서 사용할 수 있는 구현 아티팩트가 있습니다. Maven을 사용하는 프로젝트에서는 아래의 의존성을 추가하여 Parboiled를 사용할 수 있습니다.

<dependency>
  <groupId>org.parboiled</groupId>
  <artifactId>parboiled-java</artifactId>
  <version>1.4.1</version>
</dependency>

 

 

구문 규칙 정의하기

이제 실제 예제를 통해 Parboiled를 사용해 구문 규칙을 정의해보겠습니다. 여기서는 간단한 산술 표현식을 파싱하는 예시를 사용할 것입니다.

public class CalculatorParser extends BaseParser<Object> {

    Rule Expression() {
        return Sequence(Term(), ZeroOrMore(AnyOf("+-"), Term()));
    }

    Rule Term() {
        return Sequence(Factor(), ZeroOrMore(AnyOf("*/"), Factor()));
    }

    Rule Factor() {
        return FirstOf(Number(), Sequence('(', Expression(), ')'));
    }

    Rule Number() {
        return OneOrMore(CharRange('0', '9'));
    }
}

 

 

위의 코드에서 CalculatorParser 클래스는 BaseParser를 상속받아 Parboiled의 DSL 기능을 활용하여 규칙을 정의합니다. 각 메서드는 특정 구문 규칙을 나타내며, 규칙을 조합하여 복잡한 표현식을 처리할 수 있습니다.

• Expression: 산술 표현식을 파싱하는 규칙으로, 하나 이상의 Term을 더하거나 뺄 수 있습니다.
• Term: 곱셈 또는 나눗셈으로 연결된 하나 이상의 Factor를 처리합니다.
• Factor: 숫자 또는 괄호로 묶인 표현식을 처리합니다.
• Number: 연속된 숫자를 파싱합니다.

 

파서 생성

Parboiled는 생성된 파서 클래스를 바이트 코드로 변환하여 런타임에 사용할 수 있도록 지원합니다. 이를 위해 createParser 메서드를 사용하여 파서를 생성할 수 있습니다.

CalculatorParser parser = Parboiled.createParser(CalculatorParser.class);

 

 

이렇게 생성된 파서는 입력을 처리하기 위해 사용됩니다.

 

 

파서 실행 및 결과 처리

생성된 파서를 이용하여 실제 입력을 처리하는 과정은 매우 간단합니다. 아래 예시에서는 "1+2"라는 문자열을 파싱하여 결과를 출력하는 방법을 보여줍니다.

String input = "1+2";
ParseRunner runner = new ReportingParseRunner(parser.Expression());
ParsingResult<?> result = runner.run(input);

 

파싱 결과는 ParsingResult 객체에 저장되며, 이를 통해 파싱 성공 여부와 결과를 확인할 수 있습니다.

또한, 파싱 결과로 생성된 트리를 시각화하거나, 특정 정보를 추출하기 위해 ParseTreeUtils를 사용할 수 있습니다.

String parseTreePrintOut = ParseTreeUtils.printNodeTree(result);
System.out.println(parseTreePrintOut);

 

 

 

구문 분석 트리 이해하기

파싱이 성공하면, Parboiled는 파싱 트리를 생성합니다. 이 트리는 입력이 어떻게 파싱되었는지를 나타내며, 이를 활용하여 보다 세부적인 처리를 할 수 있습니다. 예를 들어, 수식 계산기에서는 파싱된 트리를 순회하며 각 연산을 수행할 수 있습니다.

 

 

Parboiled의 장단점

Parboiled는 사용하기 쉽고 가벼운 라이브러리로, 복잡한 구문을 처리하는 데 적합합니다. 그러나 입력이 매우 크거나 규칙 트리가 복잡할 경우, 성능 문제나 메모리 사용량이 증가할 수 있습니다. 따라서 대규모 입력을 처리할 때는 규칙의 복잡성과 성능 최적화에 주의해야 합니다.

 

 

결론

이번 글에서는 PEG와 Parboiled 라이브러리를 사용하여 Java에서 구문 분석기를 구현하는 방법을 살펴보았습니다. Parboiled는 간단한 DSL을 통해 복잡한 구문 규칙을 쉽게 정의할 수 있으며, 런타임에 파서를 생성하여 효율적으로 입력을 처리할 수 있습니다.

다만, 대규모 입력이나 복잡한 규칙 트리의 경우 성능 저하가 발생할 수 있으므로, 이를 최적화하기 위한 전략도 함께 고려해야 합니다. Parboiled를 사용하면 빠르고 간편하게 구문 분석기를 작성할 수 있으며, 특히 간단한 프로젝트나 학습 목적으로 매우 유용한 도구가 될 수 있습니다.