컴파일러 - 구문 분석

구문 분석

1. 개요

어휘 분석기에서는 입력 받은 토큰 스트림이 생성 가능한 것인지 판별했다.
토큰 스트림이 생성 가능하다고 판별되면 이는 구문 분석기로 넘겨져 파스 트리(Parse tree)나 추상 구문트리(AST)를 생성하게 된다.

이를 가능케하는 것은 컴파일러 형식언어에서 이야기하는 문법이며, 이 문법은 유도를 이용해서 도출하는 것을 따른다. 이 유도 에 대해서는 관련 포스팅을 참고하기 바란다.

기본적으로 어휘분석기가 분리한 토큰을 가지고 트리를 생성하게 되는데 이러한 구문 분석을 위한 방법에는 크게 세 가지 방법이 있다.

2. 보편적(Universal) 구문 분석

Cocke-Younger-Kasami 알고리즘이나 Earley의 알고리즘과 같은 방법을 말하는데 이들 알고리즘은 임의의 문맥 자유 문법(CFG)을 파싱할 수 있다는 장점이 있다. 보편적 파서의 장점은 표현력이 크다는 점이지만, 실제 컴파일러에서는 더 빠르고 메모리 효율적인 특수 목적 파서(LL, LR 계열)를 선호한다.

• CYK 알고리즘: 문법을 챔벌-노멀형(Chomsky Normal Form)으로 변환한 뒤 동적 계획법으로 파싱을 수행한다. 시간 복잡도는 입력 길이 n에 대해 $O(n^{3})$ 이다.

• Earley 알고리즘: 모든 CFG에 대해 동작하며, 일반적인 경우 $O(n^{3})$ 문법이 잘 구조화된 경우에는 $O(n^{2})$ 에 $O(n)$ 에 가까운 성능을 보일 수도 있다. 자연어 처리 등에서는 유용하지만, 일반적인 컴파일러 구현에서는 시간·공간 측면에서 비효율적이기 때문에 널리 쓰이지 않는다.

3. 하향식(Top-down) 구문 분석

하향식 파서는 문법의 시작 기호에서 출발해 입력을 생성하기 위해 비단말을 점차 확장해 나가며 파싱한다. 대표적인 방법으로 재귀적 하강과 LL 계열 파서가 있다.

1) 재귀적 하강(Recursive-descent)

문법의 비단말(직접 사용되는 표현- ex: “if”, “else”)에 대해 하나의 함수를 작성하고 입력 토큰을 재귀 호출로 내려가며 문법 규칙을 구현하는 파서를 말한다. 구현에 직관적이고 디버깅이 쉽다.

a. 장점

구현이 직관적이고 코드가 읽기 쉽다. 디버깅과 유지보수가 용이하다.

b. 단점 및 한계

• 왼쪽 재귀(left recursion) 를 직접 처리하지 못한다. 예를 들어

A -> A a | b

같은 규칙은 재귀적 호출이 무한 루프에 빠진다. (A가 Aa를 유도하고, Aa의 A가 다시 Aa를 유도하면서 무한 루프) 이를 해결하려면 왼쪽 재귀를 제거해야 한다. 위 문법은 다음과 같이 변환할 수 있다:

A -> b A'
A' -> a A' | ε

• 문법에 백트래킹(backtracking)이 필요하면 성능이 급격히 떨어질 수 있다.

• 복잡한 문법에서는 함수 구조가 복잡해지고 관리가 어려워진다.

c. 왼쪽 재귀 제거 및 좌측 인자 분리(left factoring)

왼쪽 재귀는 문법을 변환하여 제거할 수 있으며, 재귀적 하강 파서를 LL(1) 스타일의 예측 파서로 바꾸려면 좌측 인자 분리(Left-factoring) 가 필요할 때가 있다. 예를 들어 다음과 같은 규칙:

S -> if E then S else S | if E then S

은 좌측 인자 분리로 다음과 같이 바꿀 수 있다:

S -> if E then S S'
S' -> else S | ε

이렇게 변환하면 첫번째 토큰(예: if)만 보고도 어떤 규칙을 선택할 수 있게 되어 예측 파싱이 가능해진다.

재귀적 하강 파서는 단순하고 명시적인 제어가 필요한 경우 매우 유용하지만, 실무용 복잡한 문법을 처리하려면 문법 변환이나 다른 파싱 기법이 필요하다.

2) LL 계열

재귀 하향 파서의 단점을 보안하기 위해 고안된 파서로 LL 파서는 왼쪽에서 입력을 읽고(Left-to-right), 왼쪽 유도(Leftmost derivation)를 생성하는 파서들이다. 흔히 LL(k) 파서라 부르며, 보편적으로는 LL(1) 예측 파서가 가장 널리 알려져 있다.

a. 정의와 원리

LL(1) 파서는 입력의 다음 하나의 토큰(lookahead 1)과 현재 상태만으로 어떤 생산 규칙을 적용할지 결정할 수 있어야 한다. 이를 위해 FIRST와 FOLLOW 집합을 계산하고, 파싱 표(parse table)를 만들어 사용한다.

• FIRST 집합
  어떤 문법 기호(논터미널 또는 문자열)로부터 파생될 수 있는 첫 번째 토큰들의 집합

• FOLLOW 집합
  어떤 논터미널 기호 바로 뒤에 올 수 있는 터미널(토큰)들의 집합

• 파싱표
  테이블 형태로 정리된 규칙 모음으로 해당 테이블이 있다면 테이블을 참조해 어떤 파싱 동작(어떤 생산규칙을 적용할지 또는 shift/reduce/accept 같은 동작)을 할지 결정하기 쉬워진다.

b. 문법 변환

LL 계열 파서가 동작하려면 문법에서 왼쪽 재귀를 제거하고(또는 변환) 좌측 인자 분리(Left-factoring)가 필요할 때가 많다.

c. 장점

파서 테이블 기반으로 구현하면 매우 빠르고 결정적이다. 생성된 파서는 구현과 디버깅이 비교적 쉽다.

d. 단점

표현력이 제한적이다. LL(1)으로 파싱될 수 없는 유용한 문법들이 많다. 일부 문법은 lookahead를 늘리거나 문법을 대폭 수정해야 한다.

LL 파서는 교육용, 간단한 언어, 또는 문법이 LL(1)으로 맞춰질 수 있는 경우에 적합하다.

4. 상향식(Bottom-up) 구문 분석

상향식 파서는 입력 토큰 스트림에서 부분 문자열을 점차적으로 축소(reduce)해가며 시작 기호로 도달하려 한다. 부분적으로 인식된 기호들을 하나의 비단말로 축소하는 방식이다. 대표적으로 LR 계열 파서가 있다

1) LR 계열

LR 파서는 왼쪽에서 입력을 읽고(Left-to-right), 가장 오른쪽 유도(Rightmost derivation)의 역을 구성한다. 보편적으로 LR 파서는 shift-reduce 메커니즘을 사용한다.

a. 기본 개념

Shift: 입력에서 토큰을 더 읽어 스택에 푸시한다. Reduce: 스택의 심볼들이 어떤 생산 규칙의 우변과 일치하면 이를 해당 논터미널로 환원한다. 파싱 결정은 상태(아이템 집합)과 다음 입력 토큰에 의해 이루어진다. 상태 전이는 항목 집합(item set)과 상태 전이 표로 구성된다.

b. 종류

LR(0): lookahead 없이 아이템 집합만으로 동작하는 가장 단순한 형태. SLR(1)(Simple LR): FOLLOW 집합을 이용해 일부 결정을 개선한 버전. LALR(1)(Look-Ahead LR): 계산량과 테이블 크기 사이의 실용적 절충안으로, 대부분의 실제 컴파일러 생성기(yacc, bison 등)에서 사용된다. Canonical LR(1): 가장 표현력이 크지만 상태 수가 매우 많아 테이블이 커진다.

c. 충돌(conflict)

Shift–Reduce conflict: 상태에서 특정 토큰에 대해 shift할지 reduce할지 애매한 경우. Reduce–Reduce conflict: 같은 상태에서 두 개 이상의 서로 다른 규칙으로 reduce할 수 있는 경우. 충돌 해결 방법으로는 문법을 수정하거나(우선순위 부여를 위한 재구성), 파서 생성기에서 연산자 우선순위와 결합성(associativity)을 선언해서 해결하는 방법이 있다.

d. 장단점

장점: LR 계열 파서는 매우 강력하여 대부분의 실용적인 프로그래밍 언어 문법을 처리할 수 있고, 결정적이며 효율적(보통 입력 길이에 대해 선형 시간)이다. 단점: 테이블 생성이 복잡하고, 특히 Canonical LR(1)은 테이블 크기가 커질 수 있다. 또한 문법 충돌이 발생했을 때 원인 파악이 다소 어려울 수 있다.

LR 파서는 실전 컴파일러와 언어 도구에서 널리 쓰이며, LALR(1)은 현실적인 성능과 메모리 요구량의 균형 때문에 자주 선택된다.

5. 모호성 제거

1) 모호성

어떤 문장에서 2개 이상의 파스트리를 생성하는 문법은 모호하다라고 표현한다.
이러한 문법은 동일한 문장에 대해 2개 이상의 최 좌단 유도나 2개 이상의 최 우단 유도를 생성하는 문법이다.

아래의 예시를 보자.

E -> E + E | E * E | ( E ) | num

위와 같은 생성 규칙이 있다면 1 + 2 * 3 같은 문장이 있을때 (1 + 2) * 3 로 처리할지 혹은 1 + (2 * 3) 처리할지 모호하다.

2) 모호성 제거 방식

a. 문법 재구성: 연산자 우선순위와 결합성을 문법 구조 자체에 반영하여 모호성을 제거한다.

E  -> E + T | T
T  -> T * F | F
F  -> ( E ) | num

위 문법은 *이 +보다 우선이도록 구조화되어 있어 모호성이 제거된다.

b. 파서 생성기의 우선순위/결합성 선언

yacc, bison 같은 도구에서는 토큰의 우선순위와 결합성을 선언해 shift/reduce 충돌 시 어떤 동작을 취할지 결정할 수 있다(예: left ‘+’; left ‘*’;).

c. 암시적 규칙(언어 실무 규약)

예를 들어 dangling else 문제(가장 가까운 if에 else를 결합) 처럼 잘 알려진 모호성은 파서에서 기본 규칙(예: shift를 우선)으로 해결하기도 한다.

d. 정적 분석 및 테스트

모든 입력 케이스를 테스트하거나, 문법 분석 도구를 통해 모호성 경고를 찾고 문법을 다듬는다.

※ 주의 사항

어떤 문법이 모호한지를 자동으로 완전하게 판정하는 일반 알고리즘은 존재하지 않기 때문에 휴리스틱하게 처리하거나 도구를 쓰거나 하는 여러 방식으로 회피 혹은 해결 한다.

6. 오류 처리

1) 오류의 종류

a. 어휘 오류

식별자, 키워드, 연산자등의 철자 오류

b. 구문 오류

잘못 넣은 세미콜론이나 중괄호를 더 넣거나 빠뜨리는 경우
혹은 C나 JAVA에서 포함되지 않은 case문이 나타나는 경우

c. 의미 오류

연산자와 피연산자들의 타입이 일치하지 않는 경우

d. 논리 오류

비교 연산자(==) 대신 대입 연산자(=)를 쓰는 경우 같이 논리적으로 문제가 발생할 경우

2) 오류 복구 기법

a. 공황 모드 복구

파서가 오류를 발견시 동기화 토큰(세미콜론, 중괄호)를 만날때까지 입력된 토큰들을 버리는 것이다.
많은 양의 데이터를 오류 검사 하지 않지만 무한 루프에 따지지 않아서 빠르다.

ex)

x = 3 / * 2 ;

위 코드에서 *에서 에러가 나면 ;를 만날때까지 입력 토큰 버림

b. 문구 수준 복구

오류 발견시 남아있는 입력에 대해서 부분적 교정을 수행하는 것이다.
파서가 남아있는 입력 앞부분을 계속 수행이 가능 할 수 있게 하는 문자열로 대체하는 것인데, 가령 세미콜론을 빠뜨린 문제라던지 세미콜론 대신 다른 값으로 들어가있는걸 바꾼다던지하는 것이다.
컴파일러 제작자에게 어디까지 고칠수 있게 할 것인가가 달려있는데, 개인적인 입장을 javascript외에 이렇게까지 극단적으로 수정되게 한 언어는 본적이 없는것 같다.
물론 위와 같은 기능이 있다면 사용자에게 복구 정보를 쉽게 전달 가능하다. (가령, 여기 세미콜론이 없는 것 같습니다라던지)

c. 오류 생성 규칙

통상적인 오류가 발생할 것을 예상하면서 오류 구조를 생성하는 생성 규칙을 추가하는 것이다.
아예 특정 케이스에 대해서 에러라고 못 박아두는 것이며, 이 경우 좀 더 정확한 정보를 전달 할 수 있지만 규칙이 많아 질 경우 문법이 지저분해진다.

d. 전역적 교정

개발하면서 에러가 났을때 가장 적게 수정하기를 바란다. 최소 비용의 편집을 찾아서 전달하면 가장 좋을 텐데 이는 시간이랑 공간 관점에서 비용이 너무 커서, 최적 대체 문자열을 찾아서 전달하는 방식으로 변경되었으며 많이 사용되고 있다.

추가 업데이트 및 검증 예정

참고자료

• 컴파일러 : 원리, 기법, 도구 제 2판. ALFRED V. AHO, MONICA S. LAM, RAVI SETHI, JEFFREY D. ULLMAN. 우원희, 신승철, 우균, 하상호 옮김
• 위키 백과 - 파스 트리