일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 클래스
- 객체지향설계
- 파싱
- 프로세스
- 정보검색
- 웹소프트웨어
- 스케줄러
- 파싱테이블
- OS
- 데이터분석
- 가상메모리
- 836
- 자연어처리
- C언어
- 데이터베이스
- 오픈소스웹소프트웨어
- 애자일
- 벡터
- 운영체제
- 소프트웨어공학
- css
- Agile
- NLP
- DB
- 언어모델
- React
- Linear Algebra
- 컴파일러
- 컴파일
- 랩실일기
Archives
- Today
- Total
observe_db
[컴파일러] 10. 형식언어 본문
알파벳과 스트링
- 잘 정의된 언어는 문장으로 구성
- 알파벳은 문장을 이루는 기본적인 심볼
- 알파벳: 심벌들의 유한집합
- 스트링(문장, 단어): 알파벳 T에 속하는 하나 이상의 심벌의 나열
- 길이: 스트링을 이루는 심벌의 갯수. |ω|로 표시
- empty 스트링: 스트링 길이가 0인것. ε또는 λ로 표시
- T*: 알파벳 T에 대해서 empty스트링까지 포함한 모든 스트링의 집합
- 접속(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|
- a^n : n개의 a.
- 문자 ω의 반전은 문자 ω에 반전표시를 (ω^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
언어 표현의 문제점
- 어떻게 언어를 표현할 것인가
- 유한언어는 쉽게 표현 가능
- 무한 언어는 유한 표현법이 필요
- 집합 표현으로 조건 제시
- 언어 생성 시스템인 문법: Scheme의 생성
- 언어의 인식기: Scheme의 인식
- 모든 언어는 유한한 표현을 가지는가?
- 항상 모든 언어에 대해 유한 표현이 존재하지는 않는다.
문법: 무한 언어의 유한 표현 방법
문법 요소
- 단말기호(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 |