컴파일러의 구문 분석

개요

컴파일러의 구문 분석에 대해 알아본다. 이 글은 내공 있는 프로그래머로 길러주는 컴파일러의 이해의 내용을 기반으로 함을 미리 밝힌다. 책 내용이 괜찮으니 관심있으신 분들은 사보는것을 추천한다.(필자는 이해관계자는 아님을 밝힌다.)

학습목표

구문 분석의 개요
하향식 구문 분석
상향식 구문 분석
모호한 문법의 사용과 에러 처리 루틴

문맥 자유문법

정의: leftmost derivation, rightmost derivation

좌파스, 우파스

파스트리의 정의

구문 분석방법은 크게 두종류가 존재
- 하향식 구문분석
- 좌파스
- 상향식 구문분석
- 우파스
파스트리는 올바른 문장에 대해 그 문장을 트리구조로 나타낸 것
구성
- 루트노드 정의된 문법의 시작기호
- 중간 노드 각 생성규칙의 좌측 논 터미널 기호
- 리프 노드는 터미널 기호

파스트리 만들기 예제

구문분석

주어진 입력이 올바른 프로그램인가 검사
토큰을 입력받아 주어진 문법에 맞는지 검사
- 맞으면 파스트리 생성
- 아니면 에러
구문 분석을 담당하는 도구를 구문분석기라 부름

구문분석 방법

파스 트리만드는 순서에 따른 분류
- 하향식 : 좌단유도에 따른 좌파스 생성
- 상향식 : 우단유도의 역순에 의한 우파스 생성

[예제 6-1]하향식 구문 분석 with backtracking

빨간색 글처럼 백트랙킹의 단점은 트리순회를 리프까지 내려갔다가 구문이 맞지 않으면 다시 위로 올라와 다시 트리 순회를 진행해야 한다는 점이다.

6.2 하향식 구문 분석: LL 문법

글자처럼 왼쪽에서 오른쪽으로 구문을 읽음
Left scan, Left Parse를 일컬어 LL
Backtracking 있으면 한 입력 기호를 반복해서 검사(scan) 할 때가 있어 시간이 많이 소요되어, 결정적인 구문 분석을 할 수 있는 방법이 필요

First와 Follow 정의

재귀적 하강 구문 분석(Recursive Descent)

재귀적 하강 구문분석
- LL 방법의 일종
- 주어진 입력 문자열을 구문 분석하기 위해 재귀적 프로시저를 사용
- 재귀적 프로시저는 각 논터미널에 해당하는 것으로 논터미널에 대한 유도를 재귀적 프로시저 호출로 처리하는 방법
재귀적 하강 구문분석기 구현방법
- $이면 accept이고 그렇지 않으면 에러로 처리
장단점
- 문법적으로 재귀적 프로시저를 이용하여 구문 분석기를 쉽고 빠르게 구성하며 오류 가능성이 낮음
- 프로시저를 부르는 시간이 많이 걸려서 속도가 느리고 구문분석기가 커짐
- 생성 규칙이 바뀔때마다 구문분석기를 고쳐야함

재귀적 하강 구문 분석기 예제

예측 구문분석 (Predictive parser)

생성 규칙이 바뀌더라도 전체 구문분석기를 고치지 않고 파싱테이블만 수정해서 구문 분석기를 구현하는 방법
실제로 스택을 이용하여 구현하며 입력과 스택, 파싱 테이블, 출력으로 구성
- 입력은 아래 2가지로 구성
- 구문 분석이 입력될 문자열과 $을 저장함
- 스택은 문장형태에서 입력 문자열과 아직 매칭되지 않은 부분을 유지하며 스택 맨 밑에 역시 $를 갖음
- 출력은 파스트리나 구문 분석시 적용된 일련의 생성 규칙 번호(좌파스)가 출력 될 수 있음

예측 구문 분석기의 행동

예측 파싱표 구성 방법

예측 파싱표 구성하기 예제

아래 파싱표의 추가 기준은 아래와 같다.
– First는 무조건 다 추가한다.
– Follow는 $ \epsilon$으로 유도되는 규칙만 추가한다. 즉 E’, T’이다.

상향식 구문 분석

상향식 구문분석은 감축에 의해 시작기호를 찾아가는 방법임
주어진 문자열이 시작기호로 감축되면 올바른 문장으로 판단함

우단유도와 핸들찾기 예제

상향식 구문 분석: LR 구문 분석

LR 구문 분석
- 결정적인 상향식 구문 분석 방법
- LR (Left to right scanning and Right parse)은 입력 문자열을 왼쪽에서 오른쪽으로 읽어가며, 출력으로 우파스를 생성
LR 구문 분석의 장점
- LR 구문 분석기는 모호하지 않은 문맥자유 문법으로 쓰인 거의 모든 프로그래밍 언어에 대해 구성이 가능하다.
- LR 구문 분석기는 입력을 왼쪽에서 오른쪽으로 scan 하면서 구문 오류를 쉽게 발견할 수 있다.
LR 구문 분석의 단점
- 프로그래밍 언어에 대해 LR 구문 분석기를 직접 작성하는 일이 너무 방대
LR 구문 분석 종류 – 파싱표 구성 방법에 따라
- SLR(simple LR) 구문 분석 – LR(0) 항목의 집합과 FOLLOW
- CLR(canonical LR) 구문 분석 – LR(1) 항목의 집합
- LALR(lookahead LR) 구문 분석 – LR(0) 항목의 집합과 lookahead로부터 또는 LR(1) 항목의 집합

상향식 구문 분석: LR parser

구문 분석기의 구성
- 구동 프로그램 및 action과 GOTO 두 부분을 포함한 파싱표로 구성되고, 구동 프로그램은 LR 구문 분석기가 모두 같지만 파싱표는 다르다
LR 구문 분석에 대한 장단점
- SLR 방법은 구현하기가 쉽지만 강력하지 못하며, CLR 방법은 가장 강력하지만 구현하기가 매우 어렵다. LALR 방법은 SLR과 CLR의 중간 형태로 강력함은 CLR과 유사하고 파싱표의 크기는 SLR 방법으로 구성 가능.

증가문법

LR(0) 항목

LALR 구문분석기

Lookahead 정보를 이용하기 때문에 LALR 방법이라 한다.
SLR 방법보다 훨씬 강력하고, 파싱표의 크기가 CLR 방법보다 상당히 작으면서 도 프로그래밍 언어의 구문 구조를 대부분 편리하게 표현할 수 있다는 것이 장점이다.
파싱표의 크기를 비교해보면 SLR 파싱표와 LALR 파싱표는 주어진 문법에 대해 항상 동일한 개수의 상태로 만들 수 있으며, C 언어의 경우 전형적으로 수백 개 정도이다. 반면에 CLR 파싱표는 동일한 규모의 언어에 대해 전형적으로
수천 개의 상태이다. 그러므로 CLR 파싱표보다 SLR 파싱표나 LALR 파싱표를 구성하는 것이 훨씬 더 쉽고 경제적이다.
모호하지 않은 문맥자유 문법으로 표현된 거의 모든 언어를 인식할 수 있으며, 에러를 초기에 탐지할 수 있다.
CLR 방법은 SLR 방법보다 매우 강력하지만 lookahead를 구해야 하므로 과정이 복잡하고 시간이 오래 걸리며 파싱표가 커진다는 단점이 있다. 따라서 이러한 단점을 보완하기 위해 LR(1)의 경우처럼 감축 행동은 lookahead를 이용하고 파싱표의 크기는 되도록 작게 구성 할 수 있는 방법을 적용하게 되었는데이를 LALR 방법이라 한다.

파싱표 크기

[표 6-9]의 파싱표에 2개 이상의 행동이 함께 정의되어 있지 않으므로 주어진 문법은 LALR 문법이다.
[예제 6-30], [예제 6-34], [예제 6-38]에서 한 가지 문법을 가지고 SLR, CLR, LALR 파싱표를 만들어보았다. 파싱표에 충돌이 있는지 없는지에 따 라 문법을 말할 수 있는데, 이 문법은 CLR, LALR 문법이지만 SLR 문법은 아니다. CLR, LALR 문법에 맞으므로 파싱표의 크기를 비교할 수 있으며, LALR 파싱표가 CLR 파싱표보다 매우 작다.
모든 SLR, CLR, LALR 문법은 모호하지 않지만, 모호하지 않지만 SLR, CLR, LALR 이 아닌 문법이 존재한다.

모호한 문법

모호한 문법의 예

모호한 문법일 때 파스 트리를 하나로 만드는 방법

모호한 문법의 사용

모호한 문법은 언어의 명세에서 매우 유용하다.
- 표현식과 같은 언어 구조에 대해 모호한 문법은 동등한 모호하지 않은 문법보다 더 짧고 더 자연스러운 명세를 제공. 즉 모호한 문법이 모호하지 않은 문법보다 문법의 표현이 간단하며, 사람들이 사용하기에 훨씬 자연스러운 문법
모호한 문법에서 결정적인 구문분석기를 만들기
- 모호한 문법을 동등한 의미를 가진 모호하지 않은 문법으로 변환.
- 모호한 문법을 가지고 파싱표를 만든 다음 파싱표에서 충돌을 제거
이동-감축 충돌을 해결하는 방법
- 감축되는 생성규칙과 입력 기호의 우선 순위를 비교하여 결정
- 생성규칙의 순위가 높으면 감축을 선택, 그렇지 않으면 이동을 선택
- 같은 순서인 경우에는 결합 법칙을 이용
  - 좌측 결합을 만족하면 감축, 우측 결합을 만족하면 이동을 선택
감축-감축 충돌을 해결하는 방법
- 감축되는 생성규칙들의 순위를 비교하여 어느 생성규칙으로 감축할 것인가를 결정하는데 우선 순위가 높은 것을 선택
- 생성규칙의 순위는 그 생성규칙 내에 있는 터미널 기호로 결정 가능

SLR 파싱표를 만들고 충돌 제거하기 예제

SLR 파싱표를 만들고 충돌 제거하기

모호한 문법의 사용과 에러 처리 루틴

에러 복구를 위한 구문 분석하기 예제

테스트

용어설명

아래와 같이 정리한다.

- FIRST
  - First(alpha)는 alpha로 부터 유도되어 첫번째로 나타날 수 있는 터미널 기호
- FOLLOW
  - Follow(A)는 논터미널 기호 A 다음에 나오는 터미널 기호들의 집합, $는 입력문자열의 끝을나타내는 기호로 Follow는 $를 포함
- 백 트랙킹
  - S->cAd, A -> ab | a이면 유도과정에서 A를 먼저 ab로 유도해보고 맞지 않으면 다시 트리 위로 거꾸로 돌아가 a를 선택하는 과정을 거치는데 이를 백트랙킹이라 한다.
- LL조건
  - 하향식 구문 분석 방법
  - Left Scan, Left Parse
- 감축
  - A -> beta 규칙에서 beta가 A로 치환되는 과정을 감축이라 부름
- 핸들
  - 감축되는 부분을 핸들이라 부름

구문 분석기란?

주어진 입력이 올바른 프로그램인가 검사
토큰을 입력받아 주어진 문법에 맞는지 검사
- 맞으면 파스트리 생성
- 아니면 에러
구문 분석을 담당하는 도구를 구문분석기라 부름

상향식/하향식 구문분석 방법에 대해 설명하고 장단점 비교

하향식
- 좌단유도에 의해 좌파스 생성
상향식
- 우단유도의 역순에 의한 우파스 생성
장단점
- 하향식
- 장점 : 구현이 심플
- 단점 : 백트랙킹, 시간이 오래걸림
- 상향식
- 장점 : 거의 모든 프로그래밍에서 사용
- 단점 : LR 구문 분석기를 직접 작성하면 방대함

각 논터미널 기호의 FIRST와 FOLLOW를 구해보자

첫번쨰는 아래와 같다.

S-> aRTb | bRR
R -> cRd | e
T -> RS | TaT

First 구하는 법
- 시작 문자열
- 시작 기호가 논터미널이면 추적하여 다시 시작문자열 확보
Follow 구하는법
- 해당 기호 뒤에 붙은 논 터미널
- 해당기호뒤에 빈칸으로 끝나면 해당기호가 감축되는 기호의 Follow를 더함
  즉 Follow(B)를 구하는데 A -> xxxB 이런식이면 Follow(B) 에 Follow(A)를 더함
- A -> BCxxx 에서 Follow(B)를 구하면 First(C)를 더함

	First	Follow
S	a,b	Follow(T)=b, $
R	c,e	d,c,e,b, $
T	c,e	b, $

두번째는 아래와 같다.

S -> ABC | BCA
A -> abc | BC
B -> SAa | C

	First	Follow
S	a	a, $
A	a	a, $
B	a	$
C		$

하향식 구문 분석 방법의 문제점

백트랙킹이 있으면 검사에 시간이 많이 소요되고 결정적인 구문분석을 할 수 있는 방법이 필요

LL(1) 문법인지 판단하고 왜 그런지 설명하자

S -> Ab
A -> a
A -> B
A -> e
B -> b
B -> e