Software blog

NFA를 DFA로 변경

• NFA의 Simulation을 생성하기 위해 필요한 작업임.
• 주요 키 함수
  • Move(si , a)
    Si로 부터 a 심볼에 의해서 도달 할 수 있는 state의 set임
  • ε-closure(si)
    Si로 부터 ε 에 의해 도달 할 수 있는 state.
• 알고리즘
  • 시작 state는 NFA의 S0로 부터 derivate함.
  • ε-closure S0 를 취함.
    • NFA의 시작은 ε move를 가질 수 있기 때문에 이를 통하여 제거
  • α ∈ Σ인 알파 각각에 대하여 move를 취하고 Move(S0, α)나서 ε-closure를 취함.
    • 다시 말해 NFA의 요소를 모드 제거하여 Merge하는 작업임.
  • 더 이상의 state가 추가 될 것이 없을 만큼 iteration.
• Pseudo code

  s0 ← ε-closure({n0})

  S ← { s0 }

  W ← { s0 }

  while ( W ≠ Ø )

  select and remove s from W

  for each α ∈ Σ

  t ← ε-closure(Move(s,α))

  T[s,α] ← t

  if ( t ∉ S ) then

  add t to S

  add t to W

• Example
  • 시작 state에 ε move가 없으므로 ε-closure 를 통해 s0의 set으로 q0를 얻음.
    이에 대하여 s0라는 status로 정의하고 table에 등록한다.

    

  • a, b, c에 대한 transit을 통하여 각 심볼에서 얻어지는 ε-closure(Move(s,α))의 state set을 구한다.

    

  • Transition 이 존재하는 a의 에 대하여 ε-closure(Move(s0,a))에 의해 얻어진 set 들을 s1의 status로 묶어 내고 정의한다.

    

  • S0 status가 등록 되었을 때와 마찬가지로 s1에 대하여서도 Merge작업을 수행한다.

    

       

    

  • Transition function이 존재하는 b,c 의 레코드에 대해서 각 set에 순차적인 status의 이름을 부여 하고 row에 등록함.

    

       

    

  • 이를 반복 함으로서 결국 아래와 같은 table을 얼을 수 있다.

    

  • DFA로 옮기기 전에 final state에 대해서 생각 해볼 필요가 있다. NFA에서 Accept를 위한 final state는 모두 DFA에서도 Final state가 되어야 하므로 NFA의 final state인 q9이 포함된 DFA의 모든 State를 final state로 등록 한다.

    

  • 결과적으로 얻어진 DFA는 가 없으므로 NFA보다 적다
  • 모든 Transition은 deterministic하다.

    

       

       

Quick review

Non-deterministic Finite Automata

• ( a | b )* abb 와 같은 RE를 표현 하는 NFA

  

  • 각각의 RE는 Deterministic finite automaton에 부합한다.
    • 각 RE를 위한 DFA가 존재한다는 사실을 알고 있음.
    • DFA를 바로 만드는 것은 어려운 작업이기 때문에 일반적으로 정해진 규칙에 따르는 자동화 테크닉을 사용한다.
• 좀 더 간단한 형태의 Recognizer를 살펴보자.

  

  • 앞서 제시된 형태의 recognizer보다 좀 더 단순한 형태이다.
  • RE의 구조 흐름과 유사하게 작성되었다.
  • 하지만 이 Recognizer는 DFA가 아니다.
    • S0 이 ε 트랜지션을 가지고 있기 때문에.
    • S1 은 두 개의 a 트랜지션을 가지고 있기 때문에

Non-deterministic Finite Automata, NFA

• NFA는 S0로 부터 final state에 이르는 모든 transition graph와 if and only if라면 스트링 x를 인식(accept)한다.
• ε 트랜지션은 no input을 소거함.
• NFA를 실행 하기 위해서는 S0부터 시작하고 매 스텝마다 올바른 트랜지션이 일어나고 있는 지 확인 해야 한다.
  • 항상 올바른 추론이 필요
  • 만약 올바른 추론들의 특정 시퀀스가 x를 accept하면 그때 accept된 것임.
• NFA가 필요한 이유.
  • RE에서 DFA로 변환 하는 과정의 Automating의 키임.
  • NFA 두 개를 ε 트랜지션으로 연결 하여 붙임으로써 손쉽게 확장 할 수 있음.

    

     

NFA와 DFA의 관계

• DFA는 NFA의 특별한 케이스임.
  • DFA는 ε 트랜지션을 가지고 있지 않음
  • DFA의 트랜지션 함수는 Single value임.
• DFA는 명백히 NFA를 simulate할 수 있음.
• NFA는 덜 명백히 DFA를 simulate할 수 있음.
  • 개인적으로 less obvious라는 단어에서 어떠한 기준으로 obvious라고 하는 것인지 모르겠음.
  • State space가 기하급수적으로 늘어 날 수 있음.

Automating Scanner Construction

• 코드를 만들어 내기 위한 일반적인 절차는 아래와 같음
  • 입력 언어를 위한 RE를 작성
  • 커다란 그림의 NFA를 구성
    • RE를 NFA를 구성하기 위해서 각 Term에 대한 NFA를 제작
    • 제작된 NFA를 ε 트랜지션으로 결합시킴
  • NFA를 Simulate할 수 있는 DFA를 구성함.
  • DFA를 체계적으로 Shrink함.
    • Minimal DFA
    • Hopcroft's algorithms
  • 코드로 변경
    • 결국 변경된 코드는 DFA를 RE를 인식.

    

Tompson's Construction

• RE를 가지고 NFA를 생성하는 것.
• NFA는 각각의 심볼과 오퍼레이터를 구성함
• 그리고 precedence한 (앞서 있는 state) 오더로 부터 ε move를 만들면 최종적으로 Big NFA를 구성 할 수 있음.

  

• Example
  • RE, a ( b | c )*에 대한 NFA를 구성하는 탐슨 알고리즘
    • a, b, c 심볼에 대한 오퍼레이터로 각각의 NFA를 구성함.

      

1. b | c를 구성하는 NFA를 만들기 위해 ε move 추가.

   

2. ( b | c )*를 위한 ε move 추가.

   

3. 1,2,3을 통해서 만들어진 NFA를 ε move으로 Combine.

   

• 실재로 탐슨 알고리즘을 통해서 기계적으로 생성하는 것이 아니라 사람이 설계하면 훨씬 간단하게 만들어 질 수 있음.

  

     

The Front End

• Front End는 monolithic이 아님.
• 
• 일반적으로 스케너와 파서로 구분하여 구현
  • 스캐너는 워드를 분류함
  • 파서는 문법적 derivation을 하도록 함.
  • 파싱은 좀 더 어렵고 느림.
• 구현 정책

  

• 크게 봤을 때 Front end의 기능
  • 프론트 엔드는 syntax를 주로 다루게 됨.
    • Language syntax는 speech 의 부분을 같이 명세함.
    • Syntax 체크는 grammar에 대하여 speech의 부분을 매치 시키는 것임.
      • 마치 Terminal을 찾는 것과 유사함.

Set Operation

• Union, Concatenation, Kleene Closure, Positive Closure

  

Regular Expression

• Feature
  • Set Operation 기반으로 함.
  • ε 는 Regular Expression에서 집합 {ε}을 의미함.
  • a, 알파가 Σ 안에 있다는 의미는 RE에서 {a} 집합을 의미함.
  • L(x)와 L(y)로 되어 있는 x와 y가 있으면 아래와 같은 의미를 가짐
    • x |y 는 RE에서 L(x) ∪ L(y)로 표기 할 수 있음.
    • xy 는 RE에서 L(x)L(y)로 표기 할 수 있음.
    • x* 와 같은 kleene closure는 RE에서 L(x)*로 표기 할 수 있음.
• Example
  • Identifiers

    

  • Numbers

    

• Points
  • Lexical analyzer를 위해서 워드와 speech의 부분을 매핑 하는 것을 명세 하기 위해서 Regular Expression을 사용 함.
  • Automata theory와 알고리즘의 결과를 사용 함으로서 RE를 인식하는 작업을 자동화 할 수 있음.
• Example
  • Register → r (0|1|2| … | 9) (0|1|2| … | 9)*

    

  • 이렇게 만들어진 DFA(Recognizer)는 반드시 코드로 컨버트 되어야 함.
  • 테이블을 룩업이 direct이므로 character 또는 Transition당 cost는 O(1)임.( 더 복잡한 DFA도 마찬가지)

    

  • 이렇게 만들어지는 recognizer에 각 transition 마다 우리는 action을 추가 할 수 있음.
  • 각 Action들은 일반적으로 lexeme을 capture한 것과 다를 바 없음.

    

  • 예제의 구현에서 추가 되어야 할 것.
    • r0부터 r31까지 만으로 레지스터를 제한 해야 하는 경우
    • Regular Expression을 좀 더 tight 하게 구성할 필요가 있음.
      • Register → r ( (0|1|2) (Digit | ε) | (4|5|6|7|8|9) | (3|30|31) )
      • Register → r0|r1|r2| … |r31|r00|r01|r02| … |r09
    • DFA

      

    • Table

      

    • Table of action

      

         

The back end

• Responsibilities
  • IR을 타겟 머신의 코드로 번역하는 역할을 함
  • 각 IR 오퍼레이션에 해당하는 인스트럭션을 선택
  • 어떤 Value를 레지스터에 유지 할 것인지 결정
  • 시스템 인터페이스에 conformance해야 함.
  • 
• Instruction Selection
  • 빠르고 컴팩트한 코드를 생성함
  • Addressing mode와 같은 타겟 피쳐의 어드벤테이지를 적용함
  • 보통 패턴 매칭 문제의 관점에서 접근을 함.
  • 
• Register Allocation
  • Value가 사용 될 때 각각의 레지스터에 value를 가지고 있어야 함.
  • 리소스의 집합이 제한적인 것을 관리함.
  • Load & store를 삽입하여 인스트럭션을 변경 할 수 있음
  • Allocation optimal 문제는 NP Complete임.
  • 
• Instruction Scheduling
  • 하드웨어 stall과 interlock을 피하기 위해서 스케줄링함.
  • Variable들의 라이프 타임을 증가 시킬 수 있다.
  • 
  • 메모리 레이턴시를 커버하기 위해서 value 를 레지스터로 로드하는 것을 스케줄링 한다

Traditional Tree-pass compiler

• 코드 개선 및 최적화
  • IR과 rewrite IR을 분석함.
  • 주요 goal은 컴파일 코드의 런타임 러닝 시간을 줄이는 것임.
  • 물론 power consumption, space improve와 같은 일도 중요 골임
  • 코드의 meaning은 반드시 보존 해야 함.
  • 

The Optimizer or Middle End

• 적은 빈도의 실행으로 컴퓨테이션 할 수 있도록 함.
• Redundant 컴퓨테이션을 발견하고 그것을 제거함
• 코드가 동작하지 않거나 사용되지 않는 부분을 찾아 제거함.
• 

Role of the Runtime system

• 메모리 관리 서비스
  • Allocate
  • Deallocate
  • Collect garbage
• 런타임 타입 체킹
• 에러 프로세싱
• OS를 위한 Interface
• Parallelism 지원.

High-level view of a compiler

• Legal, illegal 프로그램을 모두 인식 할 수 있어야 함
• 올바른 코드를 생성할 수 있어야 함
• 모든 변수와 코드의 저장소를 관리 할 수 있어야 함
• 오브젝트 코드를 위한 포맷에 대하여 OS & 링커가 인정 해야 함.
• 

Traditional Two-pass Compiler

• IR(Intermediate representation)을 사용함
• Front end는 legal 소스 코드를 IR로 변경함.
• Back end는 IR을 타겟 머신 코드로 변경함
• 멀티플 프론트 앤드와 멀티플 패스를 가지는 것도 혀 용함.
• 

A Common Fallacy

• 멀티플 프론트 앤드와 멀티플 백앤드를 가지는 컴파일러는 잘못된 생각.
• 
• n+m 컴포넌트의 컴퍼일러를 우리가 만들 수 있는가?
  • 각각의 프론트 앤드는 모든 언어에 specific knowledge를 가지고 있어야 함.
  • 모든 피쳐들은 single IR로 바뀌어야 함.
  • 각각의 백앤드들은 모든 타겟 Specific knowledge를 가지고 있어야 함.

The Front End

• 
• Responsibility
  • 프로그램 인식
  • 유용한 방법으로 에러 리포트
  • IR을 생산
  • 컴퍼일러의 나머지를 위한 코드 형태
  • 대부분의 프론트 앤드 contruction은 자동으로 될 수 있어야 함.
• Scanner
  • Character 스트림을 syntax의 기본 유닛인 워드로 매핑 함
  • 발음 부분과 워드의 페어를 생성함.
    • 
    • 발음 부분은 token type과 유사하고
    • 워드는 렉심과 유사하며 페어는 토큰과 유사하다.
  • 스캐너의 속력은 매우 중요함.
  • 
• Parser
  • CFG를 인식하고 에러를 리포트한다.
  • Context sensitive("Semantic") 분석 (Type checking)을 함
  • 소스 프로그램을 위한 IR을 생성
  • 
• Grammar
  • Context-free syntax는 grammar를 명세함.
  • Context-free syntax는 다양한 BNF(Backus-Naur Form)으로 작성 될 수 있다.
  • 전형적으로 grammar G = (S,N,T,P)
    • S, Start symbol
    • N, Non-terminal symbols
    • T, Terminal symbols
    • P, Production & rewrite rules
  • Context free syntax는 아래와 같은 CFG로 표현된다.
    • 
    • 주어진 CFG로 우리는 반복적인 교체(substitution)을 통해 Sentence를 derive할 수 있다.
    • 
    • 다시 말하면 우리는 이러한 프로세스를 역으로 사용 함으로서 특정 CFG에 유효한 Sentence를 인식 할 수 있고 parse를 빌드 할 수 있다.
  • Parse는 tree에 의해 표현 될 수 있다.
    • 
    • 이러한 파스 트리는 필요 없는 정보들도 보유하고 있는데 간혹 이를 제거한 트리로서도 파스를 표현 하기도 한다.
  • Abstract Syntax Tree
    • AST는 문법적 구조를 요약한 것으로 Derivation에 관한 세부 정보를 가지고 있지 않다.
    • AST는 간결 해야 하며 IR의 일종으로 볼 수 있다.
    •