- 어휘분석기(스캐너): 원시 프로그램을 읽어 들여 토큰이라는 의미 있는 문법적 단위로 분리하여 출력
- 구문분석기(파서): 어휘분석 단계의 결과들인 토큰들을 받아 이 토큰들이 주어진 문법에 맞는지 검사
- 형식언어: 어떤 알파벳에서 얻은 기호(symbol)들로 구성되는 문자열들의 집합
- 형식문법: 형식언어 생성을 위해 사용하는 여러 규칙
- 형식문법 표현을 위해 정규표현, 문법도표, BNF, EBNF 등의 방법을 사용한다.
- 정규문법
- A→tB A→t 또는 A→Bt A→t 단, t ∈ A, B ∈ VN 생성규칙에 따라 두 가지 종류가 있다.
- A → tB, A → t 와 같은 생성규칙을 갖는 것을 우선형(right-linear)문법이라 하고 A → Bt, A → t와 같은 생성규칙을 갖는 것을 좌선형(left-linear)문법이라 함.
- 정규표현: 정규문법을 가장 잘 표현할 수 있는 방법
- 유한 오토마타: 형식언어 인식을 위해 사용한다
- DFA(결정적 유한 오토마타): 하나의 입력문자열에 대하여 오직 하나의 다음 상태 결정
- NFA: 어떤 상태에서 주어진 하나의 입력기호에 갈 수 있는 다음 상태가 하나 이상 존재
- 정규표현, 정규문법, 유한 오토마타는 서로 동치관계에 있으며 서로 변환 가능하다
4장. Context-Free 언어와 문법의 효율화
구문분석을 위해서는 context-free 문법과 푸시다운 오토마타가 필요하다
4.1. Context-Free 언어와 푸시다운 오토마타
context-free 문법으로 생성되는 context-free 언어는 문장을 표현하는 데 매우 편리한 구조를 가지고 있다.
푸시다운 오토마타: context-free 문법으로 구성된 문장을 인식
4.2. 유도트리
좌단유도: 문장 형태의 가장 왼쪽에 있는 논터미널 기호를 계속해서 대체
우단유도: 가장 오른쪽에 있는 논터미널 기호를 계속 대체
좌문장 형태: 좌단유도 시 나타나는 문장형태
우문장 형태: 우단유도 시 나타나는 문장형태
좌파스: 좌단유도에 의해서 적용된 일련의 생성규칙 순서 (top-down 구문분석은 좌파스 생성)
우파스: 우단유도에 의해서 적용된 생성규칙 순서의 **역순** (bottom-up 구문분석은 우파스 생성)
유도트리/파스트리: 구문분석 과정에서 문장 유도 과정을 트리 형태로 표현
CFG(context-free grammar) G = (VN, VT, P, S)에 대한 유도 트리는 다음과 같이 정의한다
- 모든 노드(vertex, node)는 문법기호를 레이블로 갖는다
- 루트의 레이블은 시작기호 S이다.
- 만약 어떤 노드가 하나 이상의 자식노드를 갖는다면 이 노드는 논터미널 기호를 레이블로 갖는다
- 왼쪽부터 순서적으로 X1, X2, X3, .. , Xn의 n개의 자식노드를 갖는 어떤 노드 A가 존재한다면 생성규칙 A -> X1 X2 ... Xn이 존재한다
- 만약 어떤 노드가 자식노드를 하나도 갖고 있지 않다면 이 노드를 잎이라 하고 잎은 터미널 노드를 레이블로 갖는다.
어떤 문법에서는 하나의 똑같은 문장을 유도하는데 여러 개의 유도트리가 생길 수 있다. 좌단유도나 우단유도 둘 중 한가지 유도방법을 이용하더라도 생성규칙을 다르게 적용할 경우 서로 다른 유도트리가 만들어지는 경우가 있는데, 이런 경우를 문법이 모호하다ambiguous 라고 한다.
4.3. 모호성
구문분석 단계에는 출력으로 유도트리를 생성하는데, 문법이 모호한 경우에는 문장의 유도트리를 결정적으로 구성하기가 어려워진다.
따라서 이를 막기 위하여 모호하지 않은 문법으로 바꿔주어야 한다.
모호한 문법은 연산자의 우선순위와 결합법칙을 이용해 모호하지 않은 문법으로 바꿀 수 있다.
결합법칙: 연산자 우선순위가 같은 경우에 왼쪽부터 오른쪽으로 계산하느냐, 오른쪽부터 왼쪽으로 계산하느냐 하는 것
- 좌측결합: 왼쪽부터 오른쪽으로 계산
- 우측결합: 오른쪽부터 왼쪽으로 계산
- 통상의 경우 결합법칙도 좌측결합을 취한다
모호하지 않은 문법이라도 효율적인 구문분석을 하기에는 적당하지 않을 수 있다.
4.4. 불필요한 생성규칙의 제거
불필요한 기호useless symbol
- 터미널 문자열을 생성할 수 없는 논터미널 기호
- 시작 기호로부터 도달 불가능한 기호
불필요한 생성규칙: 불필요한 기호를 가지고 있는 생성규칙
- 문장을 생성하는 유도과정에서 사용되지 않는다.
불필요한 생성규칙의 제거
- 터미널 문자열을 생성할 수 없는 논터미널 기호를 가진 불필요한 생성규칙 제거
- 시작기호로부터 도달 불가능한 기호를 갖는 생성규칙 제거
4.5. ε-생성규칙의 제거
ε-생성규칙: A -> ε 형태의 생성규칙
ε이 L(G) 안에 없다면 ε-생성규칙을 완전히 제거할 수 있다.
4.6. 단일 생성규칙의 제거
단일 생성규칙: 생성규칙 중 생성규칙의 오른쪽이 단 한 개의 논터미널로 구성되어 있는 생성규칙이 존재하는 경우
- 불필요한 유도과정으로 효율을 떨어뜨린다.
4.7. Backtracking과 Left-factoring
left-factoring: 같은 기호들을 prefix로 갖는 두 개 이상의 생성규칙이 존재할 경우 공통된 prefix를 인수분해하는 것
- top-down 구문분석의 한 종류인 predictive 구문분석에 효율적인 문법을 생성하는 데 사용
4.8. Left-recursion의 제거
left-reculsive: 문법이 어떤 문자열 α에 대해 A => Aα의 유도과정이 존재하는 경우
- top-down 구문분석을 시행할 경우 무한루프에 빠지게 된다
- 직접 left-recursion: 생성규칙이 A -> Aα의 형태
- 간접: A => Aα의 유도과정이 존재
4.9. 푸시다운 오토마타
푸시다운 오토마타: 유한 상태 제어와 입력 테이프 외에 무한정의 용량을 가진 스택으로 구성된다.
- NPDA: 비결정적인 푸시다운 오토마타
- DPDA: 결정적 푸시다운 오토마타
5장. 구문분석
주어진 문장의 구문구조가 문법규칙에 올바른지 올바르지 않은지를 검사하는 것
5.1. 구문분석의 종류
구문분석: 문장 w를 입력으로 받아서, 만약 w가 정의된 문법의 문장이라면 w에 대한 파스트리를 생성하고 w가 정의된 문법의 문장이 아니면 오류메시지를 내는 작업
top-down 방법: 시작기호로부터 출발하여 정의된 문법의 규칙들을 적용하여 유도에 의한 주어진 문자열을 찾아가는 방법
- backtracking 방지 위한 문법이 LL(k)
bottom-up 방법: 입력된 문자열에서 reduce에 의해 시작기호를 찾아가는 방법 (가장 많이 사용하는 구문분석 방법)
- 현재 실용화: LR(1)
전이행렬(파싱표): 스택의 top 연산자 Ti와 읽어 들인 연산자 Tj에 대한 동작 Aij의 행렬로 표현한 것
5.2. Bottom-up 구문분석
reduce: S => αAw => αβw의 유도과정이 존재할 때, 문장 형태 αβw에서 β를 A로 대체하는 것
- β: 문장형태 αβw의 handle (한 문장형태에서 reduce되는 부분)
shift-reduce 구문 방법: bottom-up 구문분석 방법으로 stack과 입력 버퍼를 사용하여 구현한다
- 스택은 handle을 찾을 때까지 현재의 입력기호를 유지하고, 입력 버퍼는 주어진 문자열을 간직한다.
- 일반적으로 $를 사용하여 스택의 바닥과 입력의 끝을 표시한다.
- shift: 스택의 top에 handle이 나타날 때까지 입력기호를 하나씩 스택으로 옮김으로써 작동
- shift를 반복하다가 handle이 발견되면 handle에 해당하는 문자열이 생성규칙의 오른쪽에 있는 것을 찾아서 왼쪽에 있는 기호로 reduce
- 시작기호가 나타나면 구문분석을 멈추고 구문분석에 의해 주어진 입력문자열은 주어진 문법에 의해 받아들여질 수 있음을 나타낸다.
shift-reduce 구문분석의 네 가지 행동
1. shift: 입력기호를 stack의 top에 옮긴다 (스택의 top에 handle이 나타날 때까지 반복)
2. reduce: handle이 스택의 top에 나타나면 스택의 top이 handle의 오른쪽 끝이 되고, handle의 왼쪽 끝을 찾아서 완전한 handle을 찾은 다음, handle에 해당되는 생성규칙의 왼쪽에 있는 기호로 대체
3. accept: 주어진 문자열이 주어진 문법에 맞는 문장임을 나타냄
4. error: 현재 보고 있는 입력기호가 그 상태에서 나타낼 수 없기 때문에 틀린 문장임을 의미
shift-reduce 구문분석의 문제점
- handle을 어떻게 찾을 것인가?
- 찾은 handle에 대해서 생성규칙이 여러 개 존재한다면 어떤 것을 적용할 것인가
순위 구문분석 방법: handle을 생성규칙의 문법기호 상호 간의 순위관계에 의해서 찾는 방법 중 가장 간단한 순위 구문분석 방법
연산자 언어: 연산자 문법에 의해 정의되는 언어
연산자 문법: ε-생성규칙을 갖지 않고, 생성규칙의 오른쪽에 두 개 이상의 논터미널이 연속해서 나올 수 없다.
연산자순위 문법: 연산자 문법이면서 두 개의 터미널 기호 사이에 많아야 한 개의 연산자순위 관계를 갖는 것
단순순위 문법: (1, 1) 순위문법이라고도 하며, 다음과 같은 조건을 만족한다.
- ε-생성규칙을 갖지 않는다
- 오른쪽 부분이 같은 생성규칙은 존재하지 않는다
- 기호 사이에 많아야 한 개의 Wirth-Weber 순위관계를 갖는다
확장순위 문법 (m, n) 순위문법
- ε-생성규칙을 갖지 않는다
- 오른쪽 부분이 같은 생성규칙은 존재하지 않는다
- |x| = m, |y| = n인 두 문자열 x, y 사이에 많아야 한 개의 확장순위 관계를 갖는다
한정순위 문법: 단순순위 문법과 마찬가지로 ε-생성규칙을 갖지 않고, 오른쪽 부분이 같은 생성규칙이 존재하지 않는다. 또한 단순순위 문법처럼 기호 사이에 많아야 한 개의 Wirth-Weber 순위관계를 갖는데, 단 .> 관계만 갖는다.
혼합순위 문법: 한정순위 문법에서 생성규칙 중 오른쪽 부분이 같은 생성규칙이 존재하지 않아야 한다는 규칙이 없다.
- handle을 찾기 위해서 한정순위 문법과 마찬가지로 handle의 tail을 먼저 찾고, 생성규칙 중에서 오른쪽 부분이 같은 것이 존재하면 생성규칙을 유일하게 선택하기 위해서 이제까지 본 입력 문자열의 local context를 이용한다.
FIRST(α): 문자열 α로부터 유도되어 첫 번째로 나타날 수 있는 터미널 기호들의 집합
nullable: 논터미널 A가 ε을 유도할 수 있으면 A를 nullable하다고 한다.
FOLLOW(A): 어떤 문장형태에서 논터미널 A 다음에 나타나는 터미널 기호들의 집합. $기호는 입력문자열의 끝을 나타낸다. (ε는 제외)
단순순위 구문분석: 논터미널과 터미널, 논터미널과 논터미널 사이에 순위관계를 부여해서 구문 분석이 이루어진다.
LR(k) 문법: 모든 엔트리에 대해 유일하게 정의되는 파싱표를 만들 수 있는 문법
- k를 lookahead의 길이라고 하며, 이는 handle을 결정하는 데 k개의 입력기호에 이르기까지 조사하는 것을 말한다
LR(0) 항목: 생성규칙의 오른쪽에 점기호(dot symbol)을 가진 생성규칙
closure: 마크기호가 논터미널인 경우에 이 논터미널을 생성규칙의 왼쪽으로 갖는 LR(0) 항목을 구하는 것을 closure라고 한다.
- closure는 반복적으로 계속 적용되며, 한 상태에서 valid한 모든 LR(0) 항목을 구하는 것이다.
GOTO 함수: 현재 마킹한 상태에서 구문분석을 하기 위해 마크기호를 하나씩 읽는 것
SLR 구문분석기 만드는 과정
1. 주어진 문법에 증가문법을 만든다
2. LR(0) 항목 집합의 canonical collection을 구한다
3. reduce 행동을 결정하기 위해서 FOLLOW를 계산한다
4. SLR 파싱표를 작성한다
5.2. Top-down 구문분석
시작기호로부터 생성규칙을 적용하여 유도해 나가는 방법
LL 구문분석: backtracking을 하지 않고 결정적으로 구문분석할 수 있는 방법
LL 문법: LL 구문분석의 조건을 만족하는 문법
무한루프 등 문제점 해결 방법
- left-factoring으로 backtracking을 없애 준다. (같은 기호들을 prefix로 갖는 두 개 이상의 생성규칙이 존재하면 공통된 prefix로 인수분해한다.
- left-recursion이 발생하면 right-recursion으로 바꾸어 준다.
LL: 이제까지 본 기호와 현재 보고 있는 기호에 따라 구문분석 행동 결정. 지나온 기호에 대한 정보가 있기 때문에 strong LL보다 더 큰 종류의 언어를 인식할 수 있다.
strong LL: 현재 보고 있는 기호에 따라 구문분석 행동 결정
recursive-descent 구문분석: 하나의 구문분석기가 backtracking 없이 입력을 인식하기 위해서 재귀적 프로시저의 집삽을 사용하는 방법
- 구문분석의 행동을 결정적으로 정하기 위해서 생성규칙의 lookahead를 사용한다.
strong LL 문법: 생성규칙의 lookahead를 이용하여 생성규칙을 결정적으로 선택할 수 있는 문법
terminal에 대한 프로시저: 생성규칙이 있는 터미널 기호와 입력기호가 같은지를 비교하여 같다면 다음 입력기호를 볼 수 있도록 구성한다
recursive-descent 구문분석기 장점
- 재귀적 프로시저를 이용하여 문법으로부터 구문분석기를 쉽고 빠르게 구성할 수 있다
- 오류 발생 가능성이 적다
단점
- 프로시저를 부르는 시간이 많이 걸려서 속도가 느리다
- 구문분석기의 크기가 크다
- 생성규칙에 대한 프로시저를 작성함으로써 생성규칙이 바뀔 때마다 구문분석기를 다시 고쳐야 한다
Predictive 구문분석
- recursive-descent 구문분석 방법에서 생성규칙이 바뀔 때마다 구문분석기를 바꾸지 않고, 파싱표만 고쳐서 구문분석기를 구현한다
- 4가지 행동
- 제거pop: 스택의 top과 현재 입력기호가 같으면 스택의 top기호를 제거하고 현재 입력기호를 입력문자열에서 제거
- 확장expand: 스택의 top이 논터미널인 경우로 생성규칙을 적용하여 확장
- 인식accept: 스택의 top 기호와 현재 입력기호가 모두 $인 경우로 입력문자열이 올바른 문자열임을 알려 준다
- 오류error: 스택의 top이 논터미널 기호인 경우로 그 기호로부터 현재 보고 있는 기호를 결코 유도할 수 없음을 나타낸다
5.4. YACC
구문분석기 생성기
- 입력으로는 문법이 들어가고, 출력으로는 구문분석기 파일이 나온다
YACC: 1975년 벨 연구소에서 스티븐 C.존슨을 중심으로 개발된 LALR(1) 구문분석기 생성기로 문법규칙에 대한 수행코드를 일반적인 프로그래밍 언어로 기술할 수 있도록 만들었다.
선언 부분 - 변환규칙 부분 - 사용자 프로그램 부분
6장. 의미분석과 기호표
의미분석: 구문분석 단계에서 얻은 파스트리를 중심으로 의미를 부여하여 코드 생성이 가능하도록 하는 일을 한다
6.1. 의미분석 개요
중간코드: 의미분석 단계에서 얻은 코드
의미분석 단계에서는 구문분석 단계로부터 얻은 파스트리가 입력이 되며, 출력으로는 의미분석이 이루어진 파스트리가 생성된다.
구문분석기는 주로 수학적인 정의를 이용한 자동화가 목적이었으나 의미분석기는 각기 적당한 뜻을 부여하여 컴파일러가 구현이 되도록 해야 한다
과정
- 상수정의: 상수의 이름이 기호표에 들어가 적당한 기회에 기억장소를 배정받고 초깃값을 갖는다
- 유형정의: 주어진 생성규칙들의 의미에 따라 유형의 해당 자료구조가 구성
- 변수의 유형선언
- 프로시저 선언