observe_db

[컴파일러] 10. 형식언어 본문

학교 공부/컴파일러(3-1)

[컴파일러] 10. 형식언어

쩡윤 2023. 5. 30. 01:06

알파벳과 스트링

  • 잘 정의된 언어는 문장으로 구성
  • 알파벳은 문장을 이루는 기본적인 심볼
  1. 알파벳: 심벌들의 유한집합
  2. 스트링(문장, 단어): 알파벳 T에 속하는 하나 이상의 심벌의 나열
  3. 길이: 스트링을 이루는 심벌의 갯수. |ω|로 표시
  4. empty 스트링: 스트링 길이가 0인것. ε또는 λ로 표시
  5. T*: 알파벳 T에 대해서 empty스트링까지 포함한 모든 스트링의 집합
  6. 접속(concatenation): 스트링을 연속으로 연결한 것.
    • u●v를 보통 uv로 표기
    • u=a1a2a3a4...an, v=b1b2b3...bm, u●v=a1a2a3...anb1b2b3...bm
    • uε = u = εu
    • ∀u,v ∈T*, uv∈ T*
    • |uv| = |u| + |v|
  7. a^n : n개의 a.
  8. 문자 ω의 반전은 문자 ω에 반전표시를 (ω^R)^R=ω로 표시한다.

 

언어(Language): 알파벳 T에 대해 언어 L은 T*의 부분집합( L ⊆T*)

  • 잘 정의된 언어는 문장으로 구성됨
  • 알파벳은 문장을 이루는 기본적인 심볼
  • 알파벳 T는 항상 유한집합, 반면에 T*는 항상 무한집합
  • 언어는 T*에 속하는 스트링 중 특정 형태만 모은 것
  • 유한 언어: 스트링 수가 유한개
  • 무한 언어: 스트링 수가 무한개

언어연산

  • 언어 곱(product)
    • LL' = {xy|x∈L and y∈L'}
  • 언어 L의 거듭제곱(powers)은 순환적으로 정의
    • L0 = {ε}
    • Ln = LL(n-1) for n>=1
  • L*: 재귀 전이 클로저(reflexive transitive closure)
    • L0∪L1∪L2∪L3....Ln∪..
  • L+: 전이 클로저(transitive closure)
    • =L1∪L2∪L3...Ln∪..
    • =L*-L0

언어 표현의 문제점

  1. 어떻게 언어를 표현할 것인가
    • 유한언어는 쉽게 표현 가능
    • 무한 언어는 유한 표현법이 필요
      • 집합 표현으로 조건 제시
      • 언어 생성 시스템인 문법: Scheme의 생성
      • 언어의 인식기: Scheme의 인식
  2. 모든 언어는 유한한 표현을 가지는가?
    • 항상 모든 언어에 대해 유한 표현이 존재하지는 않는다.

문법: 무한 언어의 유한 표현 방법

문법 요소

  • 단말기호(terminal): 정의된 언어의 알파벳
  • 비단말기호(nonterminal): 문법에서 스트링을 생성하는데 사용되는 중간 과정의 기호. 언어 구조를 정의하는데 사용
  • 문법 기호: 단말 기호와 비단말기호를 합한 것. 보통 V(vocabulary)로 표시
  • 생성 규칙: α->β (α를 β구조로 정의한다는 뜻. 유도과정에서 α가 β로 대체)

G = (Vn, VT, P, S)

  • VN: 비단말 기호의 유한집합
  • VT: 단말 기호의 유한집합
  • P: 생성규칙의 유한집합
  • S: 시작 심벌(문장 심벌)

유도(derivation)

  • =>: 직접생성 또는 직접 유도
  • =*>: 0번 이상의 유도
  • =+>: 한번 이상의 유도

L(G): 문법 G에 의해 생성되는 언어

={ω|S=*>ω,ω∈VT*}

 

G1 = ({S}, {a}, P, S)을 dldydgkdu L(G1)

P:S->a|aS

L(G1) = {a^n|n>=1}

언어 설계: Grammar - Language(생성되고 설계되고)

 

 

촘스키 계층(Chomsky Hierarchy)

생성 형식에 따라(α->β)

  • Type 0: 무제한 문법(unrestricted grammar, UG)
  • Type 1: 문맥 의존문법(Context-Sensitive Grammar, CSG)
    • α->β, |α|<=|β|
  • Type 2: 문맥 자유문법(Context Free Grammar, CFG)
    • A->α, 여기서 A: nonterminal, α∈V*
  • Type 3: 정규문법(Regular Grammar, RG)
    • A->tB or A->t(우선형)
    • A->Bt or A->t(좌선형)
    • 여기서 A, B: non-terminal, t∈VT*

형식언어

  • REL(Recursively Enumerable Language)
  • CSL(COntext Sensitive Language)
  • CFL(Context Free Language)
  • RL(Regular Language)
  •  예시
    • 단순 매칭 언어
    • 중복 매칭 언어
    • 좌우 대칭 언어
    • 회문 언어
    • 괄호 언어

+사람은 type 2와 type3. 원숭이는 type 3만을 인식할 수 있다.

FSG: finite state grammar

PSG: phrase structure grammar

'학교 공부 > 컴파일러(3-1)' 카테고리의 다른 글

[컴파일러] 12. 오토마타  (0) 2023.05.31
[컴파일러] 11. 정규언어  (0) 2023.05.31
[컴파일러] Lex 실습  (0) 2023.04.14
[컴파일러] 9. Yacc  (0) 2023.04.14
[컴파일러] 8. Lex  (0) 2023.04.07
Comments