파싱 알고리즘 (parsing algorithm)

한 줄 정의: 토큰들의 나열로 이루어진 입력이 주어진 문법 규칙에 맞는지 판별하고, 그 구조를 구문 트리 형태로 구성하는 알고리즘.

쉽게 풀면

파싱 알고리즘은 프로그램의 소스 코드(또는 어떤 형식화된 텍스트)를 읽어 들여 그 문법적 구조를 파악하는 절차다. 한 글자씩 앞에서부터 순서대로 읽어 나가며 트리를 구성해 나가는 하향식 방법과, 작은 조각들을 먼저 인식한 뒤 이를 점점 더 큰 구조로 결합해 나가는 상향식 방법으로 크게 나뉜다. LL 파서, LR 파서 등 다양한 종류의 파서가 서로 다른 트레이드오프(지원하는 문법의 범위, 구현 난이도, 오류 메시지의 품질 등)를 가진다.

왜 중요한가

파싱 알고리즘은 컴파일러와 인터프리터 설계의 핵심 단계일 뿐 아니라, 자연어 처리에서 문장의 문법 구조를 분석하거나 데이터 형식(JSON, XML 등)을 처리하는 등 다양한 분야에 응용됩니다. 어떤 파싱 알고리즘을 선택하느냐에 따라 처리 가능한 문법의 범위와 처리 속도가 달라지기 때문에, 언어 설계나 시스템 성능 논의에서 자주 비교 대상이 됩니다. 또한 구문 분석 오류를 얼마나 정확하고 친절하게 알려줄 수 있는지도 프로그래밍 언어 도구의 사용성과 직결되어 연구되는 주제입니다.

논문에서는 이렇게 쓰입니다

"본 컴파일러는 상향식 LALR 파싱 알고리즘을 사용하여 구문 분석 단계를 수행한다."

컴파일러나 인터프리터의 구문 분석 단계에 사용된 구체적인 알고리즘의 종류를 명시할 때 사용된다.

"의존구문분석기는 전이 기반 파싱 알고리즘을 이용해 문장 내 단어들 사이의 의존 관계를 선형 시간에 예측한다."

자연어 처리 분야에서 파싱 알고리즘이 문장의 문법적 관계를 분석하는 데 사용되는 사례를 보여준다.

"제안된 파서는 오류가 포함된 입력에 대해서도 부분적인 구문 트리를 복구할 수 있는 오류 복구 파싱 알고리즘을 채택하였다."

소프트웨어 공학 분야에서 오류가 있는 입력을 다루는 파싱 알고리즘의 강건성을 다루는 예문이다.

조금 더 깊게 보면

파싱 알고리즘을 좀 더 깊이 이해하려면 파서가 처리할 수 있는 문법의 종류를 구분하는 촘스키 위계(Chomsky hierarchy)와, LL이나 LR처럼 파서가 입력을 읽는 방향과 결정을 내리는 시점에 따라 붙는 분류 체계를 함께 살펴보는 것이 도움이 됩니다. 또한 파싱 성능은 시간 복잡도뿐 아니라 모호한 문법을 얼마나 잘 처리하는지, 오류 발생 시 얼마나 유용한 정보를 제공하는지로도 평가됩니다. 논문에서 특정 파싱 알고리즘을 제안할 때는 이러한 표현력, 효율성, 오류 처리 능력 중 어떤 측면을 개선하는지 확인하며 읽으면 논지를 파악하기 쉽습니다.

주의할 점

문법마다 적용 가능한 파싱 알고리즘의 종류가 다르며, 특정 파서(예: LL(1))가 처리할 수 없는 모호하거나 좌재귀적인 문법 규칙은 사전에 재작성이 필요할 수 있다.