[컴개/CI] 구문 분석 방법

구문 분석 (= parse)

구문 분석

구문 분석이란 주어진 문자열이 정의된 문법에 의해

생성될 수 있는지의 여부(적합성)를 결정하는 과정이다.

따라서, 문법에 대해 유도가 되는지를 확인하면 되는데,

올바를 문장에 대해서는 문장 구조를, 틀린 문장에 대해서는 오류 메세지를 나타낸다.

 

구문 분석기(= parser)

파스 트리(parse tree)

파스트리는 문장 구조를 나타내는 트리로,

문법을 나타내는 생성 규칙을 적용한 유도 트리와 같은 모양의 트리이다.

• 루트 노드: 정의된 문법의 시작 심벌
• 중간 노드: 각 생성 규칙의 좌측 nonterminal 심벌
• 단말 노드(잎 노드): 주어진 스트링을 생성하는 terminal 심벌

 

생성 규칙 번호 리스트

문법의 생성 규칙을 통해 유도하는 과정에서 적용되어 온

일련의 생성 규칙 번호로, 간단한 자료구조를 통해 저장할 수 있다.

 

구문 분석 방법

구문을 분석할 때에는 Top-down방식과, Bottom-up방식을 사용 할 수 있다.

 

Top-down 방식

루트 노드로부터 시작하여 단말 노드를 생성하며 확인한다.

Top-down 방식은 좌측유도와 같은 순서의 생성 규칙을 적용한다.

이때, 좌측 유도 중 적용된 생성 규칙들의 리스트를 좌파스라고 한다.

 

Bottom-up 방식

단말 노드로부터 루트 노드를 향하여 위로 생성하며 확인한다.

Bottom-up 방식은 우측 유도의 역순과 같은 순서의 생성 규칙을 적용한 것과 같다.

입력 스트링의 왼쪽에서부터 매치하기 때문이다.

이때, 우측 유도 중 적용된 생성 규칙 리스트의 역순을 우파스라고 한다.

 

아래 예시를 통해 두 방법의 차이를 알아보자