[질문] nfa 최적화 어떻게 해요??

[기괴공학도(mecheng98)]

정규식을 nfa로 바꿨는데 상태 수가 2000개 되니까

dfa로 바꾸는데 5분 넘어가도 못 바꾸더라고요;;

그냥 nfa로 토크나이징 하기엔 너무 느린데 어떡하죠?

[다믜(damhiya)]

nfa 자체에 관한건 아니지만, 하스켈이니까 strict eval 표기 적절히 넣어보셈

[다믜(damhiya)]

특히 tail call할때 strict하게 바꾸면 성능 엄청 오르던데

[기괴공학도(mecheng98)]

ㅇㅋ ㄳ

[LLVM(llvmaster)]

e-closure는 딱히 정해진 방법이 없는걸로 앎 그래서 저는 그냥 구현하고 싶은대로 구현했음. 그리고 상태수보다는 transition(edge) 수 병목이 횔씬 클텐디

[LLVM(llvmaster)]

https://github.com/xxx1720/json-parser/blob/master/json-parser-generator/ScannerGenerator.cs#L553
Delete unnecessary e-closure with pull left, Delete recursive e-closure, Merge rounding e-closure, Delete unnecessary e-closure with pull right 이렇게 네 단계로 세분화함
https://imgur.com/a/CgLzNAr

[기괴공학도(mecheng98)]

엣지 수는 체크 안했습니다요 ..

[기괴공학도(mecheng98)]

아 링크를 못 봤어요 정말 감사합니다 ㅠㅠㅠㅠㅠㅠ

[LLVM(llvmaster)]

opt-nfa에 관한건 딱히 읽을만한 자료는 없는 것 같네염

[기괴공학도(mecheng98)]

선생님, 죄송하지만 자료에서 epsilon closure를 제거한다는 게 무슨 뜻인지를 모르겠습니다. 상태들의 집합 qs에 대하여 qs의 epsilon closure는 qs를 부분집합으로 가지고 qs의 각 상태에서 epsilon 전이로 갈 수 있는 집합 아닌가요? 여기서는 다른 뜻인 것 같은데, 설명해주시면 감사하겠습니다.

[기괴공학도(mecheng98)]

그냥 epsilon transiition을 "epsilon Closure"로 쓰신 건가요?

[LLVM(llvmaster)]

epsilon closure를 제거하는게아니라 epsilon transition을 제거한다고 고쳐서보면되요. 예를 들어서 =A - B - C= 로 연결되어있고, A-B사이의 엣지가 e, B-C사이의 엣지가 e라면 B를 없애고 A-C로 연결할 수 있음. 똑같이 A-C라면 A-C를 합쳐서 A로 만들 수 있구요

[LLVM(llvmaster)]

음 그냥 nfa2dfa의 전처리로 모든 노드에서의 e-closure를 전부다 구해놓고 시작해도 될 것같은데

[기괴공학도(mecheng98)]

선생님 정말 감사드립니다. 복 많이 받으시길 진심으로 바랍니다.

[LLVM(llvmaster)]