컴파일러당

L9_문법변환

이히당 2025. 5. 26. 12:00

1. 구문 분석 방법

Syntax Analyzer (Parser) : 구문 분석

어휘 분석 결과인 "토큰 스트림"을 입력 받아, 주어진 문법에 맞는지 검사한다.
기능 : Syntax checking, Tree generation.
출력 : 일반적으로 트리 형태

Context-Free 문법을 위한 구문 분석 방법

top-down 방식 (expand; sentence로)
- 루트 노드로부터 시작해 단말 노드를 만들어나가는 방식
- 좌측 유도와 같은 순서의 생성 규칙이 적용
- recursive descent parser, predictive parser
bottom up 방식 (reduce; start symbol로)
- 단말 노드로부터 루트 노드를 향해 위로 만들어 나가는 방식
- 우측 유도의 역순으로 생성 규칙이 적용
- precedence parser, shift-reduce parser
입력 스트링은 한 번에 한 심볼씩 왼쪽부터 오른쪽으로 스캔 (left to right scanning)

우파스는 "역순"으로 생성 규칙이 적용되는 것을 확인하자.
문장(터미널 심볼로만 이뤄짐)이 있을 때, 우파스의 순서대로 유도를 하면, 최종 결과로 '시작 심볼'이 나오게 된다.

그럼, 문장형태 (터미널, 넌터미널 심볼이 다 존재할 수 있음)에서 어떻게 rhs를 찾을 것인가? 즉, 같은 rhs를 갖는 생성 규칙이 여러 개라면, 어떤 생성 규칙을 적용할 것인가?
-> 이 질문에 대한 해답은 이후에 나올 Bottom-up 방식에서 알아보자.

2. 구문 분석기의 출력

주어진 입력이 올바른 문장인가를 어떻게 확인하는가?

구문 분석

입력으로 문자열 w를 받음 (입력 문자열 w에 대한 어휘 분석 결과 -> a sequence of tokens)
만약 w가 정의된 문법의 문장이라면 -> 구문 분석 정보를 생성
만약 w가 정의된 문법의 문장이 아니라면 -> 에러 메시지를 출력

구문 분석 정보

파스
파스 트리
추상 구문 트리

2.1. 구문 분석 정보 : Parse

아래와 같은 생성 규칙이 있다고 할 때, left parse와 right parse는 어떻게 이뤄지는지 보자.

G :
1. E -> E + T
2. E -> T
3. T -> T * F
4. F -> (E)
5. F -> id

left parse : 좌측 유도 과정에서 생성된 생성 규칙 번호

1 2 4 6 4 6 순의 생성 규칙 번호가 만들어진다.

right parse : 우측 유도 과정에서 적용된 생성 규칙 번호의 역순

6 4 2 6 4 1 순의 생성 규칙 번호가 만들어진다. (역순)

2.2. 구문 분석 정보 : Parse Tree

올바른 문장에 대해 문장의 구조를 트리 형태로 나타낸 것을 말한다.

위 유도 트리를 보면 중간에 의미없이 심볼들이 이어진 것을 확인할 수 있다.
이런 쓸데없는 부분을 제거하고 의미있는 정보만 넘기고 싶을 때, 우리는 "Abstract syntax Tree(추상 구문 트리)"를 이용한다.

추가로 이런 parse tree가 두 개 이상 존재하면 모호한 문법(ambiguous grammer)이라고 한다.

2.3. 구문 분석 정보 : Abstract Syntax Tree

semantic tree라고도 하는 추상 구문 트리가 무엇인지 보자.

parse tree의 변형된 형태다.
코드 생성 단계에서 꼭 필요한 의미 있는 정보 (semantic information)만을 갖는 트리다.
leaf node와 internal node로 이뤄져 있다.
- leaf node : operand (identifier or constant) - 터미널 심볼들이나 상수로 이뤄져 있다.
- internal node : operator (meaningful production rule name) - 의미있는 연산자로 이뤄져 있다.

위의 트리에서도 확인할 수 있듯, 리프노드에는 터미널 심볼과 상수만, 중간 노드에는 연산자만 있다.

중간에 쓸데없는 심볼들이 포함된 parse tree를 개선해

abstract syntax tree(semantic tree)로 만들면서 더욱 트리를 단순화 한 것을 확인할 수 있다.

3. Top-Down 방법

좌측 유도 과정에서 생성 규칙이 잘못 적용 => 그 생성 규칙에서 사용했던 스트링을 다시 스캐닝 하기 위한 입력으로 보내고 다른 생성 규칙을 적용하여 유도를 시도 -> "Backup or Backtracking"

Backtracking 과정

처음에 시작 심볼의 첫 번째 규칙을 적용하여 유도한다.
주어진 입력 스트링과 유도된 문장형태 (sentential form)를 한번에 한 심볼씩 비교한다.
1. 비교 과정에서 nonterminal이 나오면, 이 nonterminal 심볼의 첫 번째 생성 규칙을 적용하여 유도한다.
2. 비교한 두 심볼이 같으면, 계속 비교해 나간다.
3. 비교한 두 심볼이 같지 않으면, 생성 규칙을 잘못 적용한 것이므로 현재 적용된 생성규칙을 제거하고 그 다음 생성 규칙을 적용한다. 이때 입력 심볼의 위치는 제거한 생성규칙에서 보았던 심볼의 개수만큼 입력으로 되돌려 보낸다.
2번 과정을 반복하다가 더 이상 적용할 생성 규칙이 없으면 입력 스트링을 틀린 문장으로 간주하고, 문장 형태에 나타난 스트링이 입력 스트링과 같아지면 올바른 문장으로 인식한다.

해당 방식의 단점에 대해 알아보고, 그 해결책을 공부해보자.

일반적인 Top-down 방식의 구문 분석 (ex. backtracking)
- 한 입력 심볼을 여러 번 반복해서 다룬다. 따라서 시간이 매우 많이 소모된다.
- Left-recursion이 존재하면 무한 루프에 빠진다.
- 결정적인 구문 분석을 위해서는 backtracking을 사용하면 안된다.
Left recursion
- Direct left-recursion : 생성 규칙에서 순환이 직접 나타나는 경우를 말하면, 생성 규칙의 형태가 A -> Aa이다.
- Indirect left-recursion : 유도과정을 통하여 순환이 발생하는 경우를 말하며, A =>+ Aa 형태의 유도과정을 갖는다.

A left-recursive grammer can cause a top down parser to go into an infinite loop. -> eliminate the left recursion.

left-recursive문법은 top down 파서가 무한 루프에 빠지게 할 수 있으므로 left-recursive을 제거해야한다!!

어떻게 제거하면 될까?

-> 새로운 nonterminal을 도입하면 된다.

그렇다. left-recursion의 제거는 새로운 nonterminal을 도입해서 할 수 있다.

그 방법을 자세히 보자.

일반형
A -> Aa | b

개선형
A -> bA'
A' -> aA' | ε

이렇게 일반형을 개선된 형태로 변형하면 left-recursion문제를 해결할 수 있는데,

일반형을 보면 문장형태가 다음과 같이 만들어진다.

Aa, AAa, AAAa, Aba, Aaba, AAaba,

그리고 문장은 다음과 같다.

ba, bba, bbba, baba, bbaba

결국 무조건 문장의 시작은 b가 되고, 문자의 끝은 a가 될 수 밖에 없는 구조다.

이러한 구조를 반영한 새로운 생성규칙이 개선형이다. (개선형이라는 말은 그냥 내가 마음대로 붙힌 말이니까 해당 단어에 매몰되지 마라)

이런 개선형 방식은 자체는 이해가 안되거나 매번 생각하기 귀찮다면 그냥 암기하도록 하자.

아래는 이렇게 새로운 넌터미널을 적용했을 때, 어떤식으로 생성규치깅 변형되는 지를 보여주는 예시다.

이제 또 다른 Top-down 방법들을 알아보자.

Left-factoring (좌 인수분해)
- A -> aB | ar 와 같은 형태의 두 개 이상의 생성 규칙이 있을 때, 주어진 스트링이 올바른 문장인가를 검사할 때 어떤 생성 규칙을 적용해야할 지 모른다.
- 이럴 때, 공통 앞부분 (common prefix) 인 a로 묶어 새로운 nonterminal을 도입하여 새로운 생성 규칙을 추가하여 동등한 문법을 만든다.

이렇게 공통인 a를 묶고 나머지 부분을 지칭하는 새로운 non terminal symbol을 도입했다.
이로써, 비결정적인 것을 결정적인 문법으로 바꿀 수 있게 되었다.

LR (Left-to-right / Rightmost derivation in reverse) → 왼쪽부터 읽으며, 오른쪽(끝 부분)부터 문법을 맞춰감
LL(Left-to-right / Leftmost derivation) → 왼쪽부터 읽으며, 왼쪽(처음 부분)부터 문법을 쌓아감

No-backtracking; LL구문 분석의 조건
- 구문 분석과정에서 입력 심벌에 따라 nonterminal에 대한 생성 규칙을 결정적으로 선택할 수 있어야 한다.
  - 결정적 구문 분석 determinisitc top-down parsing
  - LL조건 (LL condition) : 유도 과정에서 나타난 문장 형태에서 nonterminal을 대체하는 생성 규칙을 결정적으로 선택하기 위한 것
  - FIRST, FOLLOW 등 이용 (다음 장에서 공부한다)

4. Bottom-up 방법

Reduce
- S =>* a b w 이고 A -> B 의 생성 규칙이 존재할 때, 문장 형태 a b w 에서 B를 A로 대치하는 것을 reduce 라고 부른다.
Handle
- S =>* aAw => aBw 의 유도 과정이 있을 때, B를 aBw의 handle이라 한다.
- 즉, 한 문장 형태에서 reduce되는 부분을 말한다.
Handle pruning
- S => w1 => w2 => ... => w(n-1) => w(n)의 우측 유도 과정이 있을 때 각 w(i)의 문장 형태에서 handle을 찾아 w(i-1)로 가면서 시작 심벌로 reduce되는 과정을 handle pruning이라 한다.
- ex. w => w(n) => w(n-1) => ... => w2 => w1 => S

Bottom-Up parsing의 main aspect는 right sentential form에서 handle을 찾아 적용할 production rule을 deterministic하게 선택하는 것이다.

Shift-Reduce 구문 분석

a bottom-up styled of parsing.
Shift-Reduce Parser : 주어진 문장을 맨 밑(토큰)부터 위로(시작 기호) 쌓아 올리며 파싱하는 기법, 입력을 어떤식으로 되돌릴 지(reduce)를 정의해 둔 부분
스택(stack)과 입력버퍼(input buffer)를 사용하여 구현한다.
- stack : 문장 형태에서 handle을 찾을 때까지 필요한 문법 심벌들을 유지 (처리 공간)
- input buffer : 입력 스트링
shift : 현재의 입력 심벌을 스택으로 이동
reduce : 스택의 top부분에 있는 handle을 그에 따른 생성 규칙으로 축약
accept : 주어진 스트링이 올바른 문법임
error : 주어진 스트링이 틀린 문장임
- 만약 입력 (input)이 다 비었는데 ($) stack에 있는 게 시작 심볼이 아닌 경우, error에 해당한다.

How to make a parsing table for a given grammer.
어떻게 주어진 문법을 위한 parsing table을 만들 수 있을까?

SLR (Simple LR)
1. follow 집합만 사용
2. 문법이 간단해야 충돌이 안남
3. 가장 단순해서 계산량 적음
LALR (LookAhead LR)
1. CLR(1)과 정확도는 비슷
2. 메모리 사용량은 SLR과 비슷 (상태 수가 적음)
3. 가장 실용적 (Yacc/Bison 기본)
CLR (Canonical LR)
1. 가장 강력 (LR(1)이라 정확도 높음)
2. 상태 수가 매우 많아짐 (메모리 많이 필요)

728x90