CompileTime - 컴파일 단계_2

Compile

Posted Jan 3, 2025 Updated Jan 8, 2025

By SJH

15 min read

컴파일 단계2

어제 어휘 분석 단계에 이어서 오늘은 구문 분석 단계에 대해 공부했다.

구문 분석

어휘 분석 단계에선 전처리된 소스 코드를 토큰으로 만들었다.

이제 구문 분석 단계에서 토큰들이 정의된 문법에 맞게 작성 되었는지 검사한다.

Parser

어휘 구문 단계에서 구문 분석을 수행하는 모듈을 파서(Parser)라고 하고, 파서가 토큰 스트림으로부터 파스 트리(pase tree)를 생성한다.

참고로 이 단계에서 중요한 것은 토큰의 타입과 순서가 문법과 일치하는 지 확인하는 것으로, 토큰의 값은 중요하지 않다.

파서의 유형

파서의 유형으로는 보편적(universal), 하향식(top-down), 상향식(bottom-up)이 있다.

보편적 파싱 방법은 어떠한 문법도 파싱이 가능하지만, 과정이 매우 비효율적이라 상용 컴파일러에서는 적용할 수 없다고 한다.

따라서 하향식 또는 상향식 파서를 이용한다.

문맥 자유 문법(Contex-free gramma)

파서는 프로그래밍 언어 정의에 이용된 문법을 이해해야 문법적 오류를 검출할 수 있다.

C/C++은 문맥 자유 문법(줄여서 CFG) 기반으로 정의되어있다.

문맥 자유 문법은 V, T, P, S 의 순서쌍으로 정의된 문법이다. 각각 설명하자면,

V : 비단말 기호(nonterminal)의 유한집합
T : 단말 기호(terminal)의 유한 집합
P : 생성규칙(Production)의 유한집합
S : 시작 기호

단말 기호와 비단말 기호

단말 기호(terminal)

문법적으로 더 이상 쪼갤 수 없는 기본 단위다.
터미널 기호는 최종적으로 생성될 문자열을 구성하는 실제 문자다.
변환 과정에서 치환되지 않는 기호다.
문법 변환 과정이 끝난 후, 최종적으로 남는 기호들은 모두 단말 기호다.
ex) if, else, +, (, ), 42(숫자), x(식별자) 등 이 단말 기호다.

비단말 기호(nonterminal)

언어의 중간 상태를 나타내는 기호로, 다른 기호로 변환 가능하다.
언어의 구조적 계층을 정의한다.
시작 기호와 함께 문법의 유도 과정을 이끌어간다.
ex) stmt(문장), expr(식), term(항), factor(요소) 등 이 비단말 기호다.

단말 기호와 비단말 기호는 서로소 관계(서로 겹치지 않는 관계)다.

문맥 자유 문법의 생성 규칙

문맥 자유 문법에서 생성규칙의 가장 큰 규칙은 생성규칙의 좌변에 항상 1개의 비단말만 올 수 있다는 것이다.

하나의 비단말만 고려해 문자열을 생성하므로 문맥에 자유로울 수 있다.

비단말 기호 중 자주 사용하는 것들

prog : 프로그램 전체를 나타내는 비단말 기호
stmt_list : 문장들의 나열 또는 시퀀스
stmt : 단일 문장
block : 블록 구조를 나타냄 (중괄호로 묶인 구조)
decl : 변수나 함수 선언
type : 데이터 타입
id : 식별자
value : 값 또는 리터럴
expr : 표현식
term : 단항 요소
factor : 기본 단위

예시

  
int a = 10;
int b = a;
int c = a + b;

위 소스코드가 주어졌을 때 유도 방법을 예시로 들어보겠다.

우선 소스 코드들이 어휘 분석기에서 토큰 스트림으로 변경된다.

[KEYWORD:int, IDENTIFIER:a, OPERATOR:=, LITERAL:10, DELIMITER:;]
[KEYWORD:int, IDENTIFIER:b, OPERATOR:=, IDENTIFIER:a, DELIMITER:;]
[KEYWORD:int, IDENTIFIER:c, OPERATOR:=, IDENTIFIER:a, IDENTIFIER:b, DELIMITER:;]

각 문장이 변수 선언과 초기화, 변수간 참조, 연산 등을 한다.

기호와 규칙 정의

이를 다룰 수 있는 문법 규칙을 정의해야한다.

필요한 비단말 기호 V

prog : 프로그램
stmt_list : 문장 목록
decl : 선언
type : 데이터 타입
id : 식별자
value : 값
expr : 식

필요한 단말 기호
int, a, =, 10, b, c, +, ;

생성 규칙 P

prog -> stmt_list                         //프로그램은 여러 문장으로 구성된다.
stmt_list -> stmt stmt_list | stmt        //문장 목록은 하나 이상의 문장으로 구성된다.
stmt -> decl ;                            //각 문장은 선언 또는 대입문을 포함한다.
decl -> type id = value | type id = expr  //선언은 데이터 타입 변수 = 값 또는 데이터 타입 변수 = 연산
type -> int                               //타입은 int
id -> a | b | c                           //id 는 a, b, c 중 하나
value -> number | id                      //value는 리터럴 숫자 또는 식별자
expr -> id + id | id                      //expr는 변수간 연산 또는 변수
number -> 10                              //number는 10
operator -> = | +                         //연산자는 = 나 +
delimiter -> ;                            //구분자는 ;

시작 기호 S S = prog

int a = 10;의 경우

토큰 스트림 : [KEYWORD:int, IDENTIFIER:a, OPERATOR:=, LITERAL:10, DELIMITER:;]

토큰을 문법에 따라 유도

prog -> stmt_list  
stmt_list -> stmt  
stmt -> decl ;  
decl -> type id = value  
type -> int  
id -> a  
operator -> =  
value -> number  
number -> 10  
delimiter -> ;  

최종 결과 : prog -> stmt_list -> stmt -> decl ; -> type id = value ; -> int a = number ; -> int a = 10 ;

int b = a; 의 경우

토큰 스트림 : [KEYWORD:int, IDENTIFIER:b, OPERATOR:=, IDENTIFIER:a, DELIMITER:;]

토큰을 문법에 따라 유도

prog -> stmt_list 
stmt_list -> stmt
stmt -> decl ;
decl -> type id = value
type -> int
id -> b
operator -> =
value -> id -> a
delimiter -> ;

최종 결과 : prog -> stmt_list -> stmt -> decl ; -> type id = value ; -> int b = id ; -> int b = a ;

int c = a + b; 의 경우

토큰 스트림 : [KEYWORD:int, IDENTIFIER:c, OPERATOR:=, IDENTIFIER:a, IDENTIFIER:b, DELIMITER:;]

** 토큰을 문법에 따라 유도**

prog -> stmt_list -> stmt
stmt -> decl ;
decl -> type id = expr
type -> int
id -> c
expr -> id + id
id -> a
operator -> +
id -> b
delimiter -> ;

최종 결과 : prog → stmt_list → stmt → decl ; → type id = expr ; → int c = id + id ; → int c = a + b ;

이렇게 가장 왼쪽에 있는 비단말 기호부터 차례대로 치환하는 방식을 최좌단 유도라고 한다. 최우단 유도도 있는데, 이건 파스 트리를 뒤집을 때 주로 사용한다고 한다.

파스 트리(Parse Tree)

파스 트리는 유도 과정에서 각 단계의 확장을 트리의 노드로 표현하고, 그 확장 규칙이 트리의 간선으로 연결되는 방식이다.

파스 트리의 끝엔 터미널 기호들이 배치된다.

어떤 문자열에 대해 두 개 이상의 서로 다른 파스 트리를 생성하는 문법을 모호하다고 한다.

모호한 문법은 동일한 문자열에 대해 2개 이상의 유도를 생성하는 문법이다.

예를 들어

문법이 expr -> expr + expr | expr * expr | id 일 때

id + id * id 가 입력되면

트리는 2개가 생성된다.

각 트리는 연산의 순서가 다르게 나오기에 문법을 정의할 때는 모호한 문법이 되지 않도록 하는 것이 중요하다.

또한 좌재귀 제거와 좌인수분해 등 문법의 모호성을 제거하기 위한 다양한 방법들이 있다.

하향식 파싱 (Top-down parsing)

하향식 파싱은 root node에서 시작하여 파스 트리의 노드들을 전위 순서에 따라 생성한다.
따라서, 하향식 파싱은 항상 문자열의 가장 왼쪽 nonterminal부터 유도가 이루어지기에 최좌단 유도를 찾는 것과 같다.

하향식 파싱에는 가장 일반적인 형태인 재귀적 하강 파싱과 재귀가 필요없는 예측 파싱 등이 있다.

재귀적 하강 파싱

void E() 
{
    select production rule of the nonterminal E
    
    for(i = 1; i < NUM_PRODUCTION_RULES;) 
    {
        if(X == NONTERMINAL) 
        {
            call X()
        }
        else if(X == TERMINAL) 
        {
            read next symbol
        }
        else 
        {
            print error
        }
    }
}

의사코드(pseudocode)로 표현하면 이렇다.

LL(1) 파서

재귀적 하강 파싱의 단점을 보완하기 위해 고안된 파서다.

LL(1) 파서는 파싱 테이블을 사용해 각각의 비단말 기호호에 대한 가능한 규칙을 미리 결정한다.

또한 비단말 기호에에 대해 단일 규칙만 선택할 수 있도록 문법을 조정한다.

이로 인해 다음에 어떤 규칙이 적용될 지 예측할 수 있으며, 백트래킹이 가능해진다고 한다.

LL(1)은 스택을 이용해 구문 분석을 한다.

동작

스택의 top은 시작 기호로 시작
입력 스트림의 첫 번째 토큰을 읽기
스택의 top과 입력 스트림의 현재 기호를 비교
만약 스택의 top이 비단말 기호면 문법에 따라 그 비단말 기호를 규칙으로 치환.
만약 스택의 top이 터미널 기호라면 입력 기호가 해당 터미널 기호와 일치하면 그 기호를 소비, 입력 포인터를 이동.
만약 스택의 top이 입력 기호와 일치하지 않으면 오류 발생하고 파싱을 중지.

예시
S -> a A
A -> b | e

초기 상태 입력 스트림: a b 스택 : S

1번째 동작 입력 스트림의 첫 번째 토큰 : a 스택의 top에 S를 확인

규칙 S -> a A를 적용해, 스택에 A 넣기 (S는 팝하고 a는는 소모) 입력 스트림: b 스택 : A

2번째 동작 입력 스트림의 첫 번째 토큰 : b 스택의 top에 A를 확인

규칙 A -> b | e를 적용해, 스택에서 A를 제거하고 b를 소모

전부 다 순회를 마치면 문법에 문제가 없음을 확인할 수 있다.

그 다음 파싱 트리를 의미 분석 단계로 넘긴다.

C++로 구현 중인데, 생각보다 속도가 나오지 않아서 다음에 올리도록 하겠다.

Compile, Compileprocess

Compile Compileprocess

This post is licensed under CC BY 4.0 by the author.