skyjump's blog

정규문법은 제약이 많아 구문 구조를 표현하기 어렵다.

leftmost derivation, rightmost derivation.

derivation tree (유도트리)
context-free grammar는 문장 유도과정을 트리로 표현할 수 있다.

ambiguous
문법이 어떤 문장에 대해 두개 이상의 유도 트리를 가질 때 그 문법이 모호하다라고 한다.

필요없는 생성 규칙 (useless production) 제거
터미널 심벌로 유도 될 수 없는 생성 규칙들은 제거한다.

ε 생성 규칙 제거해야 될 때도 있다.

A->B같은 simple production(단일 생성규칙) 제거.

CNF(Chomsky Normal Form) 촘스키 정규 형태.
모든 context-free grammar는 CNF로 바꿀 수 있다.
CFG를 나타내는데 필요한 표기법을 간소화 하는데 유용하다.

CFG 표기법
BNF(Backus-Naur Form)
EBNF(Extended BNF)
syntax diagram (문법 흐름도) : 언어의 구문 구조를 쉽게 이해할 수 있도록 문법을 도식화.

PDA (Push Down Automata)
유한오토마타에  지나간 입력에 대한 결과를 알 수 있도록 스택을 추가한 것.
입력스트링을 유지하는 입력테이프와 스택, 전체 행동을 제어하는 유한 상태 제어가 있다.
현재상태와 입력과 스택을 보고 다음 상태와 스택에 들어갈 값을 정한다.
 시작상태에서 입력스트링을 다 봤을 때의 상태가 종결 상태(final state)이면 입력스트링은 이 푸시다운 오토마타에 의해 인식(accept)되었다고 말한다. 푸시다운 오토마타 언어는 이 오토마타에 인식되는 스트링의 집합이다.

PDA언어로 CFG를 구성할 수 있고, CFG로 PDA를 구성할 수 있다.

top-down 구문분석방법 : 시작 심벌로부터 아래로 내려가면서 스트링을 만든다.
bottom-up 구문분석방법 : 생성규칙의 rhs(right hand side)가 스택 top 부분에 나타날때까지 shift하다가 rhs가 되면 reduce를 한다.
shift는 입력에 있는 터미널을 스택 top으로 옮기는 것이고 reduce는 스택 top부분에 있는 생성 규칙의 rhs를 lhs로 바꾸는 것이다.

정규언어는 토큰의 형태를 기술하는데 사용.
regular grammar(정규문법), regular expression(정규표현), finite automata(유한 오토마타)에 의해 표현한다.

정규문법 정의
A->aB 또는 A->a. A와 B는 논터미널, a는 터미널.
S ->ε이면 S가 다른 생성규칙의 오른쪽에 나타나지 않는다.
토큰의 구조를 표현하는데 사용. context-free문법으로도 만들 수 있지만 정규문법으로 더 쉽게 구현할 수 있다.
 
정규표현
기본 소자
Φ(공집합), ε(empty string을 나타내는 집합), terminal 심벌.  
union :  (e1)+(e2) 또는 (e1) | (e2)
concatenation : (e1)(e2)
closure : (e1)*

regular expression equation(정규표현식)
계수가 정규표현인 식.
정규문법을 정규표현식으로 나타낼 수 있고, 정규표현을 구할 수 있다.
정규문법과 정규표현은 같은 종류의 언어를 나타낸다.

유한오토마타
입력으로 스트링을 받아서 그 스트링이 그 언어의 문장이면 yes, 아니면 no을 답하는 인식기.
5개의 요소로 정의
유한개의 상태, 입력 심벌, 사상 함수(mapping function), 시작상태, 종결 상태(final state)
사상함수는 어떤 입력 a가 들어왔을 때, 상태 중에 하나를 결과(다음상태가 된다.)로 내보내는 함수. 전이함수라고 한다.

DFA(Deterministic FA)
전이 함수가 한 입력에 대한 다음 상태로 하나의 상태만을 갖는 경우. 

state transition diagram (상태 전이도)
유한 오토마타를 그림으로 나타낸것. 시작상태를 start, 각 상태는 노드,특히 종료 상태는 이중원인 노드. 입력에 대한 상태의 변화는 edges.

NFA (Non deterministic FA)
한 입력을 보고 다음 상태가 하나 이상 있을 수 있는 유한 오토마타.

NFA를 DFA로 바꿀 수 있다. NFA가 언어의 구조르 쉽게 표현할 수 있지만 프로그램으로 만들기는 어렵다. 그래서 DFA로 변환한다.
NFA에서 한 입력으로 갈 수 있는 노드들을 하나로 묶어서 하나의 상태로 본다.

ε-CLOSURE(s)
NFA에서 입력으로 ε을 가질 수 있을 때, 하나의 상태 s가 ε입력으로 갈 수 있는 모든 상태들의 집합.

DFA state minimization ( DFA 상태수 최소화)
종결상태와 종결아닌 상태로 나누고
각 그룹에서 할 일은 그룹에 있는 상태들이 각 입력에 대해 어느 그룹으로 가는지 조사하고 같은 그룹으로  가는 것들끼리 또 나누는 것.

정규문법을 유한 오토마타로 바꿀 수 있고,
유한 오토마타를 정규문법으로 바꿀 수 있다.

유한 오토마타가 인식하는 언어를 정규표현으로 나타낼 수 있다.
먼저 유한 오토마타로 정규문법을 구하고 그걸로 정규 표현을 얻는다.
또는 정규표현으로 유한 오토마타를 구할 수 있다.
정규 표현의 기본 소자(union, concatenation, closure 등)을 NFA로 표현하고, 간단화하고 DFA으로 변환한다.

펌핑 렘마
어떤 언어가 정규 언어가 아님을 증명하는데 사용.