[Compiler] Parser(파서)란 무엇인가?

Parser(Syntax analysis) 이란?

Parsing is the task of determining the syntax, or structure, of a program

 

Parsing(Syntax analysis)는 컴파일러의 과정 중 일부분으로, 프로그램의 syntax 혹은 structure를 결정하는 과정이다.

 

그렇다면 syntax는 어떻게 주어지는가?

The syntax of a programming language is usually given by the grammar rules of a context-free grammar

프로그래밍 언어의 Syntax는 Context-free grammar(CFG, 문맥자유문법)의 grammar rule에 의해 주어진다. (Token의 구조가 regular expression에 의해 주어지는 것처럼 말이다.)

 

Regular expression과 Context-free grammar은 매우 유사한 구조를 가지고 있다. 큰 차이점이 있다면, CFG는 recursive할 수 있다는 것이다.
예를 들자면 아래와 같이 exp를 나타낼 때 exp가 오른쪽에 다시 recursive하게 나타날 수 있다. 

exp -> exp op exp | ( exp ) | number
 op -> + | - | *

위와 같이 CFG는 recursive하기 때문에 이러한 특성을 반영하여 나타내기 위해 사용되는 데이터 구조는 parse tree 또는 syntax tree이다. (syntax tree와 parse tree의 차이점은 이후에 정리하도록 하자)

 

Parse tree & Syntax tree

 

실제로 Parsing을 하는 파싱 알고리즘을 알기 전에 위와 같은 표현 방식을 알아야한다. Parsing은 Scanning과 달리 여러 방식(Top-down parsing, bottom-up Parsing)으로 진행할 수 있다. 

 

그렇다면 Parsing은 무엇을 하는 걸까?

1. Parser는 토큰들(sequence of tokens)을 입력으로 받아 Syntax tree를 만든다.
- 이때 Syntax tree는 프로그래밍 언어의 문법 구조에 따라 달라진다. 
- 보통 Syntax tree는 dynamic한 데이터 구조이다.

 

2. Parsing은 Scanning에 비해 에러를 처리하기가 어렵다.
- Scanner의 경우 Parser에 비해 에러 처리가 간단한 편이다.  하지만 Parser의 경우 에러를 발견한다고 해도 최대한 많은 에러을 찾아내기 위해 parsing을 계속 진행한다. 이를 위해 Parser은 에러가 있다는 것을 출력하는 것 뿐만아니라 매우 간단한 Error repair의 과정도 포함하기도 하다. (해당 하는 부분은 parsing algorithm에서 다시 다루기로하자.)

 

원문 소스 : Compiler Construction : Principles and Practice by Kenneth. C. Louden
틀린 부분이나 미흡한 부분이 있다면 댓글 남겨주세요:)