개요

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

목차

컴파일러 강의 다른 포스팅은 아래의 링크를 참고하자.

문맥 자유문법(Context-free grammar)

  • 잘 설계된 문법은 소스 프로그램을 정확한 목적코드로 번역할 때 유용한 구조를 제공
  • 문법자유 문법은 프로그래밍 언어설계 뿐만 아니라 효율적인 컴파일러 작성시에도 중요하게 사용
  • 문법 정의, $ G=(V_N, V_T, P,S) $
    • $V_N$ : 논 터미널 기호들의 유한 집합
    • $V_P$ : 터미널 기호들의 유한 집합
      $V_N \cap V_T = \Phi, V_N \cup V_T = V $
    • P : 생성규칙의 집합
      $ \alpha \rightarrow \beta, \alpha \in V^+, \beta \in V^* $
    • S : $V_N$에 속하는 기호로서 다른 논터미널 기호들과 구별되는 시작기호
  • 모든 생성규칙이 $ A \rightarrow \beta$ 형태일때 문맥자유문법. 단 $ A \in V_N, \beta \in V^* $
    • A가 $\beta$로 치환 : A는 $\beta$로 유도, A는 $\beta$를 생성
    • $\beta$가 A로 치환 : $\beta$는 A로 reduce

정의: leftmost derivation, rightmost derivation

  • 좌단 유도는 유도과정의 각 단계에서 가장 왼쪽에 있는 논터미널 기호를 계속 대체하는 경우
    으로 표시
  • 우단 유도는 유도 과정의 각 단계에서 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우
    로 표시

좌파스, 우파스

  • 좌파스, 우파스
    • 좌파스 : 좌단 유도에 의해 적용된 생성규칙 순서
    • 우파스 : 우단 유도에 의해 적용된 생성규칙 순서의 역순

파스 트리(parse tree) 의 정의

  • 구문 분석 방법은 크게 두 종류가 존재
    • 하향식(top-down) 구문분석
      좌파스를 생성
    • 상향식(bottom-up) 구문분석
      우파스를 생성
  • 파스트리는 루트노드, 중간노드, 리프노드로 구성
    • 루트노드 : 정의된 문법의 시작기호
    • 중간노드 : 각 생성규측의 좌측 논터미널 기호
    • 리프노드 : 터미널 기호

파스 트리 만들기

  • E -> E + T | E – T | T
  • T -> T * F | T / F | F
  • F -> (E) | id

모호한 문법

  • 모호한 문법
    하나의 문장이 서로 다른 두개이상의 파리트리를 갖을때 문법 G는 모호하다라고 표현함

모호한 문법의 예

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

  • 모호한 문법을 모소하지 않게 변환한 문법으로 구문 분석기를 만들어 처리
  • 모호한 문법으로 구문 분석기를 만든 다음 충돌이 생긴 부분을 없앰

좌단 유도로 파스 트리 만들기 2

연산자의 우선순위, 결합법칙

  • 예: 3 + 4 * 5 를 (3 + 4) * 5와 3 + (4 * 5)로 계산 가능
  • 연산의 우선순위는 모호하게 해석가능한 수식에서 어느 연산을 먼저 계산할 것인가를 결정하는 규칙
  • 예: 3-4-5 를 (3-4)-5 와 3-(4-5)로 계산 가능
  • 연산자의 결합 법칙은 연산자의 우선순위가 같을 때,
    • 좌측 결합(left associative): 가장 왼쪽에 있는 연산자부터 계산
    • 우측 결합(right associative): 가장 오른쪽에 있는 계산
  • 대부분의 프로그래밍 언어에서는 좌측 결합 방식을 취한다.

모호하지 않은 문법으로 변환 예

  • E -> E+E | E-E | E*E | E/E | (E) | 0 | 1 | 2 | 3 | 4 | 5
  • 모호한 문법에 대해 연산자 우선순위를 *, /, >, +, – 순서로 적용함
  • 모든 연산자들이 좌측 결합 법칙을 취하면 모호하지 않은 문법으로 변환 가능
  • 아래 그림은 3 + 4 * 5와 3-4-5에 대해 만들어진 유일한 파스트리를 보여줌

예제: 모호한 문법을 모호하지 않은 문법으로 변환

예제: 현수 else(dangling else)

  • 하나의 문장에 대해 서로 다른 2개의 파스 트리가 생성되므로 이 문법은 모호한 문법 이다.
  • 현수 else를 모호하지 않은 문법으로 변환하는 방법 중 [그림 (a)]와 같이 else를 그 앞에 있는 가장 가까운 if와 연결하는 것으로 일반적인 프로그래밍 언어 에서 사용하는 방법이다.
  • 다음과 같은 모호하지 않은 문법으로 변환할 수 있다.

문법 변환

  • 문법 변환
    • 주어진 문법을 동등한 언어를 생성하는 다른 문법으로 변환
    • 비효율 적인 구문분석을 하는 문법을 효율적인 구문분석 문법으로 변환
  • 변환 방법
    • 불필요한 생성규칙의 제거
    • ε -생성규칙의 제거
    • 단일 생성규칙의 제거
    • 좌인수분해(left-factoring)
    • 좌재귀(left-recursion)의 제거 등

불필요한 생성 규칙 (useless production)의 제거

터미널 문자열을 생성할 수 있는 논터미널 기호

예제: 터미널 문자열을 생성하지 못하는 논터미널을 가진 생성 규칙 제거

불필요한 생성규칙 제거

푸시다운 오토마타

  • 정의 : 푸시다운 오토마타는 7개의 요소로 구성
    • $M = (Q, \sum, T, \delta, q_0, z_0, F)$
    • 여기서 Q : 상태들의 유한집합
    • $\sum$ : 입력기호들의 유한집합
    • T : 스택 기호들의 유한집합
    • $ q_0 \in $ Q : 시작상태
    • $ z_0 \in $ T : 스택의 시작기호
    • F $\subseteq $ Q : 종결상태의 집합
    • $\delta$ : 사상함수 Q × ($\sum \cup $ {$\epsilon$}) × T $\rightarrow$ Q × $T^*$
  • (q, a, z) = {(p, r)}이라 하면
    • q의 상태에서 입력기호 a를 받았을 때 스택의 톱(top)에 z가 있다면 상태는 p로 이전
    • 스택의 톱인 z가 스택에서 삭제(pop)되고 스택에는 r이 삽입(push)되는 것
    • 만약 r이 ε인 경우는 스택에서 삭제만이 이루어진다.
    • 일반적인 사상함수 δ(q, a, z) = {($p_1$, $r_1$), ($p_2$, $r_2$), ···, ($p_m$, $r_m$)}이라 하면
    • 상태는 pi로 전이가 되고 스택의 톱인 z가 삭제되고 스택에는 ri가 삽입
    • 이때 입력 제어는 한자리 오른쪽으로 이동
    • m=1이면 결정적 푸시다운 오토마타(deterministic push-down automata)
    • m ≥ 2이면 비결정적 푸시다운 오토마타(non-deterministic push-down automata)
  • δ(q, $\epsilon$, z) = {($p_1$, $r_1$), ($p_2$, $r_2$), ···, ($p_m$, $r_m$)} 이라 하면
    • q의 상태에서 입력기호에 관계없이 스택의 톱(top)에 z가 있다면 상태는 p로이전
    • 스택의 톱인 z가 스택에서 삭제(pop)되고 스택에는 ri이 삽입(push)되는 것
    • 만약 r이 ε인 경우는 스택에서 삭제만이 이루어진다.
    • 입력 제어는 이동이 없다

푸시다운 오토마타 #2

예제: 푸시다운 오토마타에 의한 인식 1

푸시다운 오토마타: 푸시다운 오토마타의 확장

요약

  • 문맥자유문법
    문맥자유문법은생성 규칙이 A $\rightarrow$ $\beta$ 단 $ A \in V_N, \beta \in V^* $ 의형태
  • 파스트리
    • 좌단 유도: 유도 과정의 각 단계에서 문장 형태의 가장 왼쪽에 있는논터미널 기호를 계속해서 대체^[는 경우
    • 우단 유도 : 유도 과정의 각 단계에서 문장 형태의 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우
    • 좌파스: 하나의 문장을만들 때좌단유도에 의해 적용된 일련의 생성 규칙 순서
    • 우파스: 하나의 문장을 만들때우단유도에 의해 적용된 생성 규칙 순서의 역순
    • 파스트리 : 문맥자유문법 G에대한파스 트리는 다음과 같음
    • 모든노드의 이름은문법 기호
    • 루트 노드의 이름은시작 기호 S
    • 만약 어떤노드가하나 이상의 자식을가지고 있다면 이노드의 이름은 논터미널 기호
    • 왼쪽부터 순서적으로 $X_1$, $X_2$, …, $X_n$의 n개 자식을 가진 어떤 노드 A가 존재한다면 생성 규칙 A $\rightarrow$ $X_1$, $X_2$, …, $X_n$가 존재
    • 만약 어떤노드가자식을하나도 가지고 있지 않다면 이노드를 터미널 노드 또는 잎이라 함
  • 모호한문법
    문법 G에의해 생성되는 어떤문장이 2개이상의 파스트리를 가진 경우문법 G를 모호하다고 함
  • 문법변환
    • 불필요한생성 규칙: 불필요한기호를 가지고 있는생성 규칙
  • 푸시다운오토마타
    푸시다운오토마타는유한 상태 제어, 입력 테이프, 무한정의 용량을 가진스택으로 구성됨