[프로그래밍 언어론] Parser와 추상 구문 트리

파서의 구현

 이전 포스팅에서 프로그래밍 언어 정의의 필수 요소인 구문법은 파서(Parser)를 통해 검사할 수 있다고 했었다. 이번 포스팅에서는 프로그래밍 언어 S의 파서 구현을 위해 필요한 요소를 알아보자.

 

파서의 주요 요소는 다음과 같다.

1. 어휘 분석기(Lexical Analyzer): 입력 프로그램을 토큰 단위로 분리하여 반환

2. 파서(Parser): 프로그램 내 문장들의 추상 구문 트리를 생성하여 반환

3. 추상 구문 트리(Abstract Syntax Tree, AST): 프로그램의 구문 구조를 추상적으로 보여주는 트리. 인터프리터의 입력.

4. 인터프리터(Interpreter): 프로그램 내 각 문장의 AST를 순회하며 각 문장의 의미에 따라 해석하여 수행.

 

S 언어

 S 언어는 실제 있는 언어는 아니고 프로그래밍 언어론을 공부할 떄 사용한 책의 저자가 직접 설계한 샘플 언어이다. 간단한 교육용 언어로 이용할 수 있도록 설계하였고 블록 구조이며 강한 타입의 언어이다. 블록 구조와 강한 타입의 언어는 차후 설명하게 될 것이다. 기본적인 문법이 주로 사용하는 C++, Java 등의 언어와는 약간 차이가 있으니 이에 대해서는 반드시 유의하자. 다음은 언어 S의 문법이다.

 

언어 S의 문법

<program> -> { <command> }

<command> -> <decl> | <stmt> | <function>

<decl> -> <type> id [ = <expr>] ;

<stmt> -> id = <expr>; | ' { '  <stmts>  ' } ' | if ( <expr> ) then <stmt> [ else <stmt> ]

               | while ( <expr> ) <stmt> | read id; | print <expr>; | let <decls> in <stmts> end;

<stmts> -> { <stmt> }

<decls> -> { <decl> }

<type> -> int | bool | string

 

언어 S의 수식 문법

<expr> -> <bexp> {& <bexp> | ' | ' <bexp> } | !<expr> | true | false

<bexp> -> <aexp> [<relop> <aexp>]

<relop> -> == | != | < | > | <= | >=

<aexp> -> <term> {+ <term> | - <term>}

<term> -> <factor> {* <factor>  | / <factor>}

<factor> -> [ - ] ( number | ' ( ' <aexp> ' ) ' | id) | strliteral

 

이렇게 S 언어의 기본 문법을 알아보았고, 아래에서 S 언어 설계를 위해 추상 구문 트리에 대해 알아보겠다. 

 

추상 구문 트리(Abstrack Syntax Tree, AST)

 추상 구문 트리는 앞서 말했듯 프로그램의 구문 구조를 추상적으로 요약해 보여주는 것으로, 세세한 정보는 생략되어 있다. 예시를 통해 살펴보자. 

 

수식 문법 1

< expr > -> <term> {+ <term>}

<term> -> <factor> {* <factor>}

<factor> -> [ - ] ( number | ' ( ' <expr> ' ) ' | id)

 

위 수식 문법 1을 이용해 a + b * c의 유도 과정을 아래에 적어보겠다.

<expr> => <term> + <term> => <factor> + <term> => a + <term> => a + <factor> * <factor> => a + b * c

유도 과정을 파스 트리로 작성해 보았다. 이제 이것을 더 간단하게 추상화해보자. 

이렇게 a + b * c의 AST를 연산자 중심으로 간단하게 작성해 보았다. 이것이 a + b * c 수식에 대한 추상 구문 트리이다. 수식 Expr의 AST는 다음과 같이 구분할 수 있다.

Expr = Identifier(변수 명) | Value(값) | Binary(이항 연산) | Unary(단항 연산)

 

이제 여러 구문의 AST를 살펴보자. 

이항 / 단항 연산의 AST

 이항 연산의 예시로 x + y를 생각해 보자. 첫 번째 Expr은 x, 연산자 Operator는 +, 두 번째 Expr은 y이다. 단항 연산의 예시 -x에서 연산자 Operator는 -, Expr은 x이다.

 

선언문의 AST

 Decl은 Declation에서 앞 4자만 따온 것으로 변수 선언문을 뜻한다. 우리가 코딩을 할 때에는 변수 타입, 변수 명, 변수에 할당할 값을 작성하는데 그것에 대한 AST를 표현한 것이다. 아래의 AST는 변수 선언문 int x = 1;에 대한 AST이다. 

 

대입문의 AST

 대입문(Assignment Statement)은 변수 선언문(Decl)과 같다고 생각할 수 있지만, 둘은 엄연하게 다르니 유의하자. 대입문과 선언문의 큰 차이는 대입문에서는 변수 타입(Type)을 사용하지 않는다는 점이다. 다음은 대입문의 AST이다.

 아래 AST는 대입문 x = y + 10에 대한 예시이다. 변수 명 x에 y + 10 이항 연산을 대입하는 과정으로, 대입하는 이항 연산 y + 10은 변수 명 y와 연산자 +, 값 10을 이용한다.

 

Read, Print 문의 AST

 Read문은 간단하게 변수 이름만 이용하고, Print 문은 수식(Expr)을 이용한다. 따라서 Read와 Print 문의 AST는 다음과 같이 구성할 수 있다.

 

복합문의 AST

 복합문은 여러개의 문장들(Stmts)로 구성된다. 이것을 문법 형식으로 표현하면 다음과 같다.

<stmts> -> { <stmt> }

조건문의 AST

 조건문 If는 조건문과 조건식이 일치(then)했을 때 실행할 문장, 조건식이 불일치(else)할 때 실행할 문장으로 구성된다. 

 아래는 if (x > 0) then x = 3; else x = 0;의 AST이다. 조건식 x > 0은 이항 연산(Binary), 조건식이 일치한 경우 실행할 문장 x = 3은 대입문, 조건식이 불일치할 때 실행할 문장 x = 0도 대입문이므로 위와 같이 AST를 작성할 수 있다. 참고로, 이항 연산과 대입문 아래는 생략한 것이니 참고하길 바란다. 

while 문의 AST

 while문 역시 조건식(Expr)과 조건식이 일치하였을 때 실행할 문장(Stmt)로 구성된다.

Let 문의 AST

 Let 문은 let <decls> in <stmt> end 구조를 가지고 있다. 즉, 여러 변수 선언(Decls)와 여러 실행 문장들(Stmts)로 구성된다.