=정규식 해석 엔진=




정규식 많이 쓰죠

매우 좆습니다


스캐너 제네레이터를 만드려믄

정규식을 입력받아서 지지고 볶고 해야댑니다.

그래서 정규식을 입력받아 해석할수 있는 

로직을 만들어야 댑니다.




정규식 개념은 오토마타 책에 나옴니다.

이 정규식은

regular grammar,와  finite automata 와 동급입니다.

근데 이 finite automata 에 여러 종류가 있듭니다.

NFA-e

NFA

DFA

이렇게 나눠지는데요 , 별차이는 없고, 한상태에서 중복된 간선이 있는가

그냥 연결된 (나중에 설명하겠듬)

간선이 있는가 없는가 여부입니다.


DFA는 한 상태에서 중복된 간선이 단 한개도 없는 것이고

NFA 는 중복을 허용하며

NFA-e 는 중복 간선 뿐만 아니라 상태 (그냥 연결됨) 까지 중복인 것입니다.




DFA가 프로그램 돌리기에 갠춘하고, 속도도 빠르고 하지만

이해하기 어렵고, 엿같이 길다는 단점이 있습니다.

주로  컴파일러나, grep 류 와 같이 변경이 잘 없고 대량의 텍스트를 

사용하는 프로그램에 적합힙니디


NFA 정규식 엔진은 이해하기 쉽고 , 매우 짧아지지믄, 

속도가 엄충 느리다는 단점이 있습니다.

주로 스크립트 언어의 인터프리터나, 자바, C#,... 각종 편집기 안에서 쓰이는 

정규식 (VIM, EMACS, 에디트 플러스 등등등)에 쓰입니다.




Regular Expression  줄여서 RE 는

재밌게도 NFA-e 로 쉽게 변경할 수 있습니다!!

근데 파싱을 해야됩니다.

이 파싱은 CFG, 에서 최소한 LL(0) 파싱은 해야됩니다


NFA-e 는 NFA로 아주 쉽게 변환 되고

NFA 는 DFA로 변경할 수 있습니다. (이부분은 좀 ㅈ같습니다)

이 얻어진 DFA를 

프로그래밍 언어로 (저는 c언어로 하겟읍니다)

쉽게 표현할 수 있습니다.


즉 순서는 이렇게 됩니다

RE -> NFA-e -> (NFA 생략가능)  -> DFA -> C언어 함수





어쨋건 다음에

이 정규식을 해석하는 (인식만 하는)

로직을 만들겠습니다.


목표하는 정규식은 , DFA 이하에서 최대한으로 확장할 수 있는 정규식입니다.

기대해주세요